Well, I started a collection of "useful" FORTH words to be used once I need them. It also seems like a nice exercise / passtime activity.
When searching for some FORTH implementation with a specific feature (I will probably write about this later) I stumbled across a specific Hacker News post which I, as one could expect, forgot to bookmark. The post itself is not really important, but someone in the replies complained about FORTH not having resizable arrays. This statement is true in fact, as FORTH does not have any type of arrays. It does however have ALLOCATE and RESIZE, which are sufficent enough.
It made me feel like writing a more complex dynamic list system tho, so here it is I guess...
I started by making a simple 'list%' structure.
begin-structure list% field: list-len field: list-ptr end-structure : new-list64 ( n -- a ) \ len \ list list% allocate throw \ contents 2dup list-len ! swap cells allocate throw over list-ptr ! ;
The words have 'list64' because one cell is 64 bits in most modern FORTHs (at least in those that I used). It should still work on non-64-bit-cell FORTHs. I specified size, as user might want to add more types of lists later.
'list%' itself is quite universal tho, so it is still just 'list%'.
I'm not sure what the correct naming of constructors is, but 'new-<STRUCT_NAME>' seems fine by me.
Then I thought that I might want to inicialise the new list with some values right away, so I made 'new-list64-fill':
: new-list64-fill ( n* -- a ) \ list of values ended by length
dup new-list64 \ example: 14 6 42 3 new-list64-fill
swap
dup 0<> if
0 swap 1- do \ start from the end, so that the order is preserved
\ n* list-ptr
swap
over list-ptr @ i cells + !
-1 +loop
else
drop
then
;
Again, I have no idea what the correct way for this type of argument is, and I was (and still am) too lazy to search the archives so I improvised.
You call it with a bunch of valuse on the stack ended by their length. The order is preserved so that is nice.
Now the main part, resizing:
: list64-resize { n a -- } \ delta list64
a list-ptr dup @
a list-len dup @ n +
\ ptr-adr ptr len-adr new-len
dup rot !
cells resize throw
swap !
;
First of all yes, I use local variables. I felt like it was a bit too much juggling with values so I made it a bit more readable. I believe that you should use the best tool for the job, and sometimes local variables are the right tool, even in a concatenative languages. Maybe someone more skilled would be able to write it in a readable manner even without locals, but not me.
Next, it takes the difference in element count. If you try to remove more elements than there are, it will error out. I think that errorring out is a resonable responce, as it is what RESIZE itself does after all.
Remember that ALLOCATE and RESIZE take number of bytes. I forgot and wondered why it doesn't copy.
So I have a dynamic list, right.
YES!
But I want more features, so here we go:
: list64-remove { n a -- } \ index (starting at 0!) list64
\ if remove the last, use normal resize
n a list-len 1- = if
-1 a list64-resize
exit
then
a list-ptr @ n cells + \ position of remove
a list-len @ n 1- - \ number of items left
\ shift all values comming after
0 do
dup i 1+ cells + @
over i cells + !
loop
drop
\ resize anyways
\ probably could be all written better,
\ but I want it to be single and readable word
-1 a list64-resize
;
I just shift all items after the removed one one spot back and remove the last item with 'list64-resize'. Standard procedures.
And yes, I should learn dictionaries next...
: list64-append ( n a -- ) 1 over list64-resize dup list-len @ 1- cells swap list-ptr @ + ! ;
Just resize and write a value to the last position.
: list64-insert { v n a -- } \ value index (still 0 based) list64
\ give to regular append if inserting at the end
n a list-len @ = if
v a list64-append
exit
then
1 a list64-resize
a list-ptr @ n cells + \ position of append
a list-len @ n - 1- \ number of items after insertion
\ shift everything one further
1 swap do
dup i 1- cells + @
over i cells + !
-1 +loop
v swap !
;
Very similar to 'list64-remove'. Now I just add space and start shifting from the end. Then just write in the value.
\ remove last and return it's value : list64-pop ( a -- n ) dup list-ptr @ over list-len @ 1- cells + @ -1 rot list64-resize ; \ remove first and return it's value : list64-shift ( a -- n ) dup list-ptr @ @ 0 rot list64-remove ;
If you want to remove first or last item. Will also return the value removed.
How do you end this again?