Skip to content

Instantly share code, notes, and snippets.

Created June 30, 2021 12:42
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
A Linked List Implementation in RetroForth

Singly Linked List

This snippet provides a generic implementation of a singly linked list. Each value in the list points forward to the next item.

Currently only supports one list per VM, which is acceptable for my use case.

|LINK  |---*
+------+   |
|VALUE |   |
+------+   |
+------+ <-*
|LINK  | --,
+------+   |
|VALUE |   |
+------+   |
+------+ <-`
|LINK  |---,
+------+   |
|VALUE |   |
+------+   |
+------+   |
|LINK  | <-` The last link points to 0x0

Head and Tail, First and Last

Because the links point forward (instead of backward), we need to keep track of the head and tail of the linked list.

We store the start of the list at ll:first. We also store the most recent item with ll:last.

Null values indicate the list has a size of 0.

#0 'll:first var-n
#0 'll:last  var-n

Node Management

The library defines methods to handle single nodes:

  • ll:append adds a new node.
  • ll:next fetches the pointer to the next node in the list. A null value here indicates the final node in the chain.
  • ll:value fetches the nodes contents. Nodes only store one value. Hint: Use arrays to store more than one value.
  'current-value var
  'current-addr  var

  :set-current-value (s-s) s:keep !current-value $= , ;
  :set-current-addr  (a-)  here !current-addr ;
  :maybe-set-ll:first (-)  @ll:first [ @current-addr !ll:first ] -if ;
  :set-backlink       (-)  @ll:last [ here @ll:last store ] if ;


  :ll:next  (a-) #2 + ;
  :ll:value (a-) n:inc fetch ;
  :ll:append (v-)
    @current-addr !ll:last
    FALSE , @current-value ,

Test: Creating a List of Strings

{ 'One 'Two 'Three } &ll:append a:for-each

@ll:first ll:value 'One s:eq?
[ 'Test_1_pass s:put nl     ]
[ 'Test_1_FAIL s:put nl bye ]

@ll:first ll:next 'Two s:eq?
[ 'Test_2_pass s:put nl     ]
[ 'Test_2_FAIL s:put nl bye ]

@ll:last ll:value 'Three s:eq?
[ 'Test_3_pass s:put nl     ]
[ 'Test_3_FAIL s:put nl bye ]


Iteration is possible via ll:for-each. ll:for-each will push a pointer to a linked list node onto the stack and then execute the provided quotation once for each node in the linked list.

The diagram below uses the list created in the previous tests as an example:

3D6D: O
3D6E: n
3D6F: e
3D70: 0x0
3D71: 0x3D77 >---.
3D72: 0x3D6D      \
3D73: T            |
3D74: w            |
3D75: o            |
3D76: 0x0         /
3D77: 0x3D7F <---:
3D78: 0x3D73      \
3D79: T           |
3D7A: h           |
3D7B: r           |
3D7C: e           |
3D7D: e           |
3D7E: 0x0        /
3D7F: 0x0 <-----'
3D80: 0x3D79

Iterating Through the List

With the ability to create a list, we now need a way to iterate over each item in the list.

We will define a word, ll:for-each, for this purpose.

The word will internally track two things:

  • A quotation that will be called once per iteration (iterator).
  • The current node that we need to pass to said iterator (current-node).

I would like to factor these variables out of a future version, but alas, my stackrobatics are not yet strong enough.

  'iterator     var
  'current-node var

call-iterator does just that- it calls the iterator, and passes it the address of the current-node:

  :call-iterator   (-)  @current-node @iterator call ;

After we call the iterator, we set current-node to whatever value is contained in the node's link field. Don't forget that the last node in the list will have a null link field!

  :fetch-next-node (-)  @current-node fetch !current-node ;

The last private word is iterate, which ties all the pieces together:

  • Attempts to fetch the current node.
  • Calls the user's iterator if a node is found.
  • Leaves TRUE on the stack if the next node in the list is available.
  :iterate         (-a)
    [ call-iterator fetch-next-node TRUE ]
    [ FALSE ]
  :ll:for-each (q(a-)-)
    @ll:first 0;
    !current-node !iterator
    &iterate while

Each With Index

This word is similar to ll:for-each except that it passes the current index along with the node address when iterating.

  'quote   var
  'counter var

  :counter:inc (-n) @counter n:inc dup !counter ;
  :iterator    (a-) counter:inc @quote call ;


  :ll:each-with-index (q(an-)-)
    #-1 !counter
    &iterator ll:for-each


The final test will iterate over the prviously defined list of strings. We will cross check the node's ll:value against its index. Everything should be in the correct order:

:test4 (s-)
  ll:value 'One s:eq?
  [ 'Test_4_pass s:put nl ]
  [ 'Test_4_FAIL s:put nl s:put nl s:put nl bye ]

:test5 (s-)
  ll:value 'Two s:eq?
  [ 'Test_5_pass s:put nl ]
  [ 'Test_5_FAIL s:put nl bye ]

:test6 (s-)
  ll:value 'Three s:eq?
  [ 'Test_6_pass s:put nl ]
  [ 'Test_6_FAIL s:put nl bye ]

:tests (sn-)
  #0 &test4 case
  #1 &test5 case
  #2 &test6 case

&tests ll:each-with-index

Project TODOs / Wishlist

  • Support more than one list via ll:new
  • Shave a few bytes of memory usage by removing local vars in favor of stack allocation.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment