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)))
(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
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
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
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
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
Its function is defined in the pilog.l library file:
(be member (@X (@X . @)))
(be member (@X (@ . @Y)) (member @X @Y))
These two lines use the recursive structures of list to find out if an element is a member or not. How does it work?
- The first line merely checks if the first list element is equal to
@X.
- 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))
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))
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)
@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) )
That's it!
: (? (listtran (eins zwei drei) @X))
@X=(one two three)
-> NIL
You can find the finished script in this folder.
In the next post, we will study recursive patterns for nested lists.
Sources
http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pageid=lpn-htmlch4
