How would one go about implementing a vector or dynamic array in forth?

Question

I need to a dynamic array in forth, but I don't have any idea of how I could implement it. I searched online, and couldn't find any results either. I'm very new to forth, and just starting to learn it. I think I could just use a variable to store the length, and allocate more as I go, but I don't know if this even works since I am also able to write outside of the allocated space of the array.

Answer 1

It depends on what you really need. Below is code to create dynamic arrays of cells. Quickly tested in VFX Forth and GForth. There's probably neater and better optimised versions around.

0 [IF]
    dynamic array is an address stored in the dictionary pointing to 
    a structure stored in allocated memory 
        0 CELL   \ data size in bytes  n CELLS 
        1 CELL   \ start of data
        ...
        n CELL   \ End of data 
[THEN]

\ Take dictionary address and return addresses of the array 
: array-size   \ a -- n ;
  @ @ ;

: array-data    \ a -- a' ;
  @ CELL + ;
\ **********************************************************

\ **********************************************************
\ Expand the data structure and copy the 'old' data into it.
\ This either expands the data to size or to twice the 
\ original size whichever is larger.   
\ ALLOCATE THROW and FREE THROW catch & report any memory 
\ errors. 
\ **********************************************************
: dyn-expand   \ size a-dict -- ;
  DUP >R
    array-size 2* MAX             \ new-size  = largest of the ix offset 
                                  \ or 2 * current size.
    DUP CELL + ALLOCATE THROW     ( new-size new-addr )
    2DUP CELL + SWAP ERASE        \ zero the newly allocated memory
    R@ array-data OVER CELL + R@ array-size    
    ( size new-addr old-data-a new-data-a old-size )
    MOVE    \ Shift existing data to the new addr.   ( size new-addr )
    R@ @ FREE THROW      \ Free the old data's memory
    TUCK !               \ Store the new size
  R> ! ;            \ Store the new address in the dictionary

: dynamic-array   \ CREATE: count -- ; DOES> ix -- a
  \ Creates a dynamic array of count cells in ALLOCATED memory.  
  CREATE   \ count -- ;
    CELLS DUP CELL + ALLOCATE THROW   ( count addr )
    DUP ,                     \  Store the data address in the dictionary
    2DUP !                    \  Store the data size in the allocated memory                    
    CELL + SWAP ERASE         \  Zero the new data region. 
  DOES>   \ ix -- addr-of-ix-cell ;
    \ Returns the address of the ix th cell.  Expanding the array if required.
    ( ix a )
    SWAP CELLS SWAP 2DUP array-size >= IF   \ ix not in allocated range
      2DUP dyn-expand
    THEN   
    ( ix-cells a )  array-data + ;

: dyn-stats.   \ a -- ; Prints base address and array size 
  ." Base data address: " DUP .
  ." Data size in bytes: " CELL - @ . ;

Quick tests and use:

16 dynamic-array ]test   ok
456 0 ]test !    4560  10 ]test !  ok
CR 0 ]test dyn-stats.  ." 0th and 10th Data: " 0 ]test @ . 10 ]test @ .  CR 
Base data address: 9459864 Data size in bytes: 128 0th and 10th Data: 456 4560 
                   *******                     ***
 ok
1600  16 ]test !   \ This extends the array.  ok
CR 0 ]test dyn-stats.  ." 0th and 10th Data: " 0 ]test @ . 10 ]test @ .  CR 
Base data address: 10502952 Data size in bytes: 256 0th and 10th Data: 456 4560 
 ok                ******** Address Changed     *** & size changed    unchanged!!
." 16th data: " 16 ]test @ .  16th data: 1600  ok