Skip to content

Instantly share code, notes, and snippets.

@niconii
Last active May 29, 2024 19:24
Show Gist options
  • Save niconii/2e2857fb062f46abc164a2cb73db782b to your computer and use it in GitHub Desktop.
Save niconii/2e2857fb062f46abc164a2cb73db782b to your computer and use it in GitHub Desktop.
Simple linked list implementation in Forth
0 constant nil
: cons ( car cdr -- list ) here >r swap , , r> ;
: list ( x... #x -- list ) nil swap 0 ?do cons loop ;
: list: ( x... #x "name" -- ) list constant ;
: car ( list -- car ) @ ;
: car! ( car list -- ) ! ;
: cdr ( list -- cdr ) cell+ @ ;
: cdr! ( cdr list -- ) cell+ ! ;
: list. ( list -- ) begin ?dup while dup car . cdr repeat ;
: >end ( list -- end ) begin dup cdr while cdr repeat ;
: append ( l1 l2 -- list ) over >end cdr! ;
( Example usage )
100 200 300 3 list: foo
foo car . \ prints "100 "
foo cdr car . \ prints "200 "
foo cdr cdr car . \ prints "300 "
foo list. \ prints "100 200 300 "
400 500 2 list: bar
foo bar append list. \ prints "100 200 300 400 500 "
foo list. \ prints "100 200 300 400 500 "
bar list. \ prints "400 500 "
600 700 800 3 list: baz
baz bar append list. \ prints "600 700 800 400 500 "
444 bar car!
bar list. \ prints "444 500 "
foo list. \ prints "100 200 300 444 500 "
baz list. \ prints "600 700 800 444 500 "
@tkurtbond
Copy link

: acons ( car cdr -- list ) 2 cells allocate throw   >r  r@ cdr!   r@ car!  r> ;

: alist  ( x... #x -- list ) nil swap  0 ?do acons loop ;
: alist: ( x... #x "name" -- ) alist constant ;

1 2 3 4 5 5 alist: al
cr   al list.   .( printed: 1 2 3 4 5)

@tkurtbond
Copy link

tkurtbond commented May 29, 2024

Now, the interesting question is: should I use deferred words so that you can have the same code use either the original cons or acons, without having to change any other code? That would eliminate the need to write alist and alist:, but is it worth the non-obviousness of using deferred words? Maybe not, if you only want to use the original words, but what if you add other words that manipulate lists, like an ordered insert? And then a generalized ordered insert that is passed an XT for the comparison function and works with any data type? It only takes changing cons to acons in one place for those to use ALLOCATEd memory, so its a pain to have two versions of the hanging around.

Am I missing anything?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment