# A Linked List Implementation for RetroForth

Source: https://rickcarlino.com/2021/a-linked-list-implementation-for-retroforth.html
Published: 2021-06-30

**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](https://gist.github.com/RickCarlino/8818dab7b6d0a2fb5b5f54bcf526b637).

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