Writing code in PicoLisp means to think a lot in lists and list structures. This is because lists are one of only three data types in PicoLisp, the other two being numbers and symbols. So, every complex construct (like stacks, functions, trees, graphs, and so on), are basically lists.
Thus it is not surprising that PicoLisp has a lot of built-in functions to work with lists. We have already introduced some of them in the Getting Started series, especially in the post 60 PicoLisp Functions You Should Know - 6: Lists and Strings.
Today I will introduce some further functions that all have one thing in common - they allow us to manipulate a list by adding or removing one specific item from a given list.
What is a list?
Before we dive into it, let's make a very quick review of the PicoLisp list structure. A list is built up of chained cells, where each cell has a CAR and a CDR. The CDR of each cell points to the next cell. While linear lists have NIL in the last element of the CDR, a circular list has a pointer back to the first cell.
This is an example of a linear list, (1 2 3):
+-----+-----+ +-----+-----+ +-----+-----+
| 1 | ---+---->| 2 | ---+---->| 3 | / |
+-----+-----+ +-----+-----+ +-----+-----+
This is a nested list, (1 2 (3 4) 5):
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| 1 | ---+---->| 2 | ---+---->| | | ---+---->| 5 | / |
+-----+-----+ +-----+-----+ +--+--+-----+ +-----+-----+
|
v
+-----+-----+ +-----+-----+
| 3 | ---+---->| 4 | / |
+-----+-----+ +-----+-----+
And this is a circular list (1 2 3 .):
+-----+-----+ +-----+-----+ +-----+-----+
| 1 | ---+---->| 2 | ---+---->| 3 | | |
+-----+-----+ +-----+-----+ +-----+-----+
^ |
| v
+-----------------------------------------+
The push function
A list of items can be used to represent a number of things - for example a stack). Like the name says, a stack is simply a number of items "piled up" (like a stack of plates). When you add or remove an item, you do so from the head of the list.
Stacks are famously used to allocate and access memory, but of course there are many other use cases as well (we will see example of this in the Project Euler series).
Adding items to a stack is also referred to as pushing. The usage is very straightforward:
: (push 'L 1)
-> 1
: (push 'L 2)
-> 2
: (push 'L 3)
-> 3
: L
-> (3 2 1)
As we can see, the items have been pushed to the head of the list.
Now what happens if we push to a circular list?
: (setq L (3 2 1 .))
-> (3 2 1 .)
: (push 'L 4)
-> 4
: L
-> (4 . (3 2 1 .))
The new item is added again to the head of the list, but not as part of the circular list, but as a linear element.
+-----+-----+ +-----+-----+
| 4 | ---+---->| | | / |
+-----+-----+ +--+--+-----+
|
v
+-----+-----+ +-----+-----+ +-----+-----+
| 3 | ---+---->| 2 | ---+---->| 1 | / |
+-----+-----+ +-----+-----+ +-----+-----+
^ |
| v
+-----------------------------------------+
The resulting list is (4 . (1 2 3 .)). As we can see, the . after the 4 connects the circular list with the linear list so that the elements remain on the same level - (1 2 3 .) is not a sublist of L.
The pop function
Now let's see what we can do with pop:
: L
-> (3 2 1)
: (pop 'L)
-> 3
: L
-> (2 1)
Note: instead of pop 'L, you can also write ++ L.
pop returns the CAR element of a list and sets the pointer of the list to its CDR. Now this has an interesting effect when we handle circular lists:
: (setq 'L (3 2 1 .))
-> (3 2 1 .)
: (pop 'L)
-> 3
: L
-> (2 1 3 .)
Because of the nature of circular lists, the popped element is still in the circular list - but now at the tail! Why is that? Let's check CAR and CDR of the circular list L to understand what is happening:
: (car L)
-> 2
: (cdr L)
-> (1 3 2 .)
cdr L still contains all elements, including the CAR.
This can be useful for alternating. Consider the following sequence 1, 2, 4, 5, 7, 8, 10, 11, 13, ... It is formed by adding 1 and 2 alternatingly. Now, with help of a circular list, we can create this list (and more complex ones) very easily by using a circular list (1 2 .) and always popping the next summand. The next post will show an example of this.
The fifo function
Now a stack does not always represent what we need - sometimes we want to get the first item, i. e. the item at the very end of the list.
If this use case, we can use the fifo function. fifo 'var 'any adds an item 'any to a list 'var, and fifo 'var returns that item destructively:
: (fifo 'L 1)
-> 1
: (fifo 'L 2)
-> 2
: (fifo 'L 3)
-> 3
: (fifo 'L)
-> 1
: (fifo 'L)
-> 2
The underlying data structure is a circular list, as explained in detail in this post.
The queue function
Instead of fifo, we can also use a combination of queue and pop to get the first item back. queue adds an item to the tail of a (linear) list.
: (queue 'L 1)
-> 1
: (queue 'L 2)
-> 2
: (queue 'L 3)
-> 3
: L
-> (1 2 3)
: (pop 'L)
-> 1
Removing items: del and rid
Finally let's also check out how to remove specific items from a list. With del ("delete"), we can remove the first occurence of a specific symbol from a linear list.
: L
-> (1 1 2 2 3 3 4 4)
: (del 2 'L)
-> (1 1 2 3 3 4 4)
In order to delete all occurences, we call del with a non-NIL flag:
: (del 3 'L T)
-> (1 1 2 4 4)
In circular lists, it pushes the "deleted" item to the end (similar to pop). Effectively this means that the item is deleted only from the first "round".
: (setq L (1 1 2 2 3 3 .))
-> (1 1 2 2 3 3 .)
: (del 2 'L)
-> (1 1 . (2 3 3 1 1 2 .))
However, this doesn't work with circular lists - the interpreter will hang in an infinitive loop until you kill the process (press Ctrl-\ in the REPL or type kill -9 <pid> in a second terminal).
In order to remove all occurences, we can use rid (from "getting rid of"). This works in linear as well as in circular lists:
: (setq L ( 1 1 2 2 3 3 .))
-> (1 1 2 2 3 3 .)
: (rid 'L 3)
-> (1 1 2 2 .)
: (setq L2 (1 2 3 1 2 3))
-> (1 2 3 1 2 3)
: (rid 'L2 3)
-> (1 2 1 2)
In the next post, we will see how push and pop can help us to get all prime divisors from an integer.
Sources
- https://software-lab.de/doc/index.html
