. A Linked List Implementation for RetroForth

Rick Carlino

Personal blog of FarmBot co-founder Rick Carlino.

Covering Open Source news, history and best practices.

Stack Overflow Reddit Github Linkedin RSS

[ 💬 Contact ] [ 👤 About ] [ 📰 Recent Reading ] [ ✉️ Subscribe ]

A Linked List Implementation for RetroForth

NOTE: RetroForth allows the execution of Markdown files as code. The code below is written in the literate style and can be directly run via retro. A copy/paste-able version can be found here.

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
+------+
|VALUE |
+------+

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 ;

---reveal---

  :ll:next  (a-) #2 + ;
  :ll:value (a-) n:inc fetch ;
  :ll:append (v-)
    set-current-value
    set-current-addr
    set-backlink
    maybe-set-ll:first
    @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 ]
choose

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

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

Iteration

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)
    @current-node
    [ call-iterator fetch-next-node TRUE ]
    [ FALSE ]
    choose
  ;
---reveal---
  :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 ;

  ---reveal---

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

Tests

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 ]
  choose
;

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

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

: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.