PicoLisp Explored: The fifo function

Today we will discuss an interesting function called fifo: First-In-First-Out.

As always in "PicoLisp Explored", we will check the documentation and the internal representation of the data to understand what is happening.

---

The FIFO principle

The FIFO principle is nothing special or fancy - it just says that "old" items should be used first. Think of a supermarket where the employee always puts the new items behind the old ones.

Obviously the same principle is also possible with data, for example a task list, where the older items should be done first. We can create such a list and take out its items using the fifo function.

---

Creating a fifo list

Let's check the documentation of the fifo function.

(fifo 'var ['any ..]) -> any

Implements a first-in-first-out structure using a circular list. When called with any arguments, they will be concatenated to end of the structure. Otherwise, the first element is removed from the structure and returned.

Sounds pretty straightforward - let's create a simple to-do List using the fifo function. We need to define the list variable, for example ToDo, followed by its items.

: (fifo 'ToDo "buy groceries")
-> "buy groceries"
: (fifo 'ToDo "make dinner")
-> "make dinner"
: (fifo 'ToDo "clean up the kitchen")
-> "clean up the kitchen"

Now let's check the content of ToDo.

: ToDo
-> ("clean up the kitchen" "buy groceries" "make dinner" .)

What do you think? Well, we have all the items, but isn't it a bit strange that the list is starting with "clean up the kitchen", ? Isn't that supposed to be the last point?

Actually, it is not. The point is that the list is circular (note the . at the end!). Internally, or ToDo list looks something like this:

We can confirm this by checking the car and cdr of fifo.

: (car ToDo)
-> "clean up the kitchen"
: (cdr ToDo)
-> ("buy groceries" "make dinner" "clean up the kitchen" .)

As you can see, (cdr ToDo) delivers us the output that we expected - all list items in chronological order. This is because of the circular nature of the list.

---

Taking out items

As the docs told us, we just need to write (fifo <var>) to get out the next item. After that, there will be only two more items in our list.

: (fifo 'ToDo)
-> "buy groceries"
: (cdr ToDo)  
-> ("make dinner" "clean up the kitchen" .)

---

What's the point?

Imagine you have a really super large list. We add new items to the beginning, and always take out the item at the end. What does that mean?

If the list is not circular, we would need to traverse the whole list down and basically jump from pointer to pointer until we reach the last item. This means the cost of this operation increases linearly with the list length.

On the other hand, with ourfifo function, we can do it in constant time: No matter how long the list, we can always get the last item by (cadr list).

---

A little teaser

Well, that's basically all there is to say about the fifo function.

If this post was too easy for you, here is a little homework: How can we implement the level-inorder function of the binary tree traversal?

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

Expected output: 1 2 3 4 5 6 7 8 9

Hint 1: Use the fifo function.

Hint 2: No recursion needed.

---

Sources

• Photo by Franki Chamaki on Unsplash
• https://software-lab.de/doc/index.html