DEV Community

Cover image for Learning Pilog - 5: Lists
Mia
Mia

Posted on • Originally published at picolisp-explored.com

Learning Pilog - 5: Lists

Today we will talk about an important data structure which is often used in Pilog programming: Lists.

This post is based on this tutorial.


What is a list in Pilog?

Basically, it's the same like in PicoLisp: A sequence of elements. Here are some examples:

(John Vincent Jules  Yolanda)
(John (robber Honey_Bunny) @X 2 John)
()
( () (dead z) (2 (b c)) () @Z (2 (b c))) 
Enter fullscreen mode Exit fullscreen mode

(the empty list () is equivalent to NIL).

From the examples we learn:

  • list elements can be a mix of data structures, like numbers (2), variables (@X, complex terms ((dead @Z).
  • a list can have duplicated values.
  • an empty list is still a list.
  • lists can be nested: (2 (b c)).

A list can be divided by the built-in dot operator .. By default, it splits the list in two parts: the head, which is the first element and the tail, which is a list of the remaining elements.

: (? (equal (@X . @Y) (John Vincent Jules Yolanda)))
 @X=John @Y=(Vincent Jules Yolanda)
-> NIL

: (? (equal (@X . @Y) (John Vincent)))
 @X=John @Y=(Vincent)
-> NIL
Enter fullscreen mode Exit fullscreen mode

As you can see, the tail of a list is always a list, even if there is only a single element inside. So, what is head and tail of an empty list?

: (? (equal (@X . @Y) ()))
-> NIL
Enter fullscreen mode Exit fullscreen mode

An empty list can't be split up.


However, we don't always have to split up between the head and tail. We can also customize it further:

: (? (equal (@X @Y . @W) (John Vincent Jules Yolanda)))
 @X=John @Y=Vincent @W=(Jules Yolanda)
-> NIL
Enter fullscreen mode Exit fullscreen mode

Now we have the first and second element stored in variables.

Or, if we only cared for the third element and don't need all the rest, we could also use the anonymous variable @:

: (? (equal (@ @ @Z . @) (John Vincent Jules Yolanda)))
 @Z=Jules
-> NIL
Enter fullscreen mode Exit fullscreen mode

The member predicate

Pilog has a built-in predicate called member which takes two arguments: an element and a list. The usage is pretty straightforward:

  • Query: Is john a member of the list?
: (? (member John (John Vincent Jules Yolanda)))
-> T
Enter fullscreen mode Exit fullscreen mode

Its function is defined in the pilog.l library file:

(be member (@X (@X . @)))
(be member (@X (@ . @Y)) (member @X @Y))
Enter fullscreen mode Exit fullscreen mode

These two lines use the recursive structures of list to find out if an element is a member or not. How does it work?

  1. The first line merely checks if the first list element is equal to @X.
  2. The second element splits the list in head and tail. We know that the head is not @X, otherwise we would have already received T after the first line. So we can try our luck with the tail: member @X @Y).

Example: A small Translator

Let's say we have a "dictionary" with the numbers from one to nine in German and English:

(be tran (eins one))
(be tran (zwei two))
(be tran (drei three))
(be tran (vier four))
(be tran (fuenf five))
(be tran (sechs six))
(be tran (sieben seven))
(be tran (acht eight))
(be tran (neun nine))
(be tran (zehn ten))
Enter fullscreen mode Exit fullscreen mode

Let's write a Pilog script that translates a list of German number words to the corresponding list of English number words and vice versa. The structure should be like this:

(? (listtran (eins neun zwei) @X)) should return @X = (one nine two), and (? (listtran (@X (one nine two))) should return @X=(eins zwei neun).


Let's implement our listtran predicate. We start with the base case: The translation of an empty list - if we have nothing to translate, the translated side will also be empty. The empty list is equivalent to NIL.

(be listtran (NIL NIL))
Enter fullscreen mode Exit fullscreen mode

Now let's say we have exactly one item (which means it's the head of the list). In this case, we can just look it up in our tran dictionary that we defined above:

(be listtran ((@Hg . @Tg) (@He . @Te))
   (tran @Hg @He)
Enter fullscreen mode Exit fullscreen mode

@Hg/@Tg stands for Head-German, Tail-German, @He/@Te for the English equivalent.

Now we have the translation of the first list element. The only thing we still need to do is travel down our list until the remaining list is empty.

(be listtran (NIL NIL))

(be listtran ((@Hg . @Tg) . (@He  . @Te))
   (tran @Hg @He)
   (listtran @Tg @Te) )
Enter fullscreen mode Exit fullscreen mode

That's it!

: (? (listtran (eins zwei drei) @X))
 @X=(one two three)
-> NIL
Enter fullscreen mode Exit fullscreen mode

You can find the finished script in this folder.


In the next post, we will study recursive patterns for nested lists.


Sources

Top comments (0)