In the last post, we showed how lists look like and discussed recursion concepts and the member predicate. Today we will look into some further list functions: appending and reversing, and the concept of accumulators.

This post is based on this tutorial.

The append predicate

Another built-in predicate in Pilog is the "append" predicate, which takes three arguments: The first two are the sublists and the third one is the concatenated list.

: (? (append (a b) (c) @X))
 @X=(a b c)
-> NIL

Let's see how many possibilities we have to create [a,b,c] out of two sublists:

: (? (append @X @Y (a b c)))
 @X=NIL @Y=(a b c)
 @X=(a) @Y=(b c)
 @X=(a b) @Y=(c)
 @X=(a b c) @Y=NIL
-> NIL

Let's now take a look at the definition of append (you can find it in the pilog.l library file of your PicoLisp installation). Like member, it is defined recursively. The base case is appending a list @L to an empty list NIL, which means that the result is equal to the final list @L.

(be append (NIL @X @X))

If we are at the base case, the resulting list is equal to the second argument. Now, if the first argument only had one item @A, the new list would be equal to the second argument (now called @Y) prepended by the head of of the first list, right? And this can be repeated recursively, like this:

(be append ((@A . @X) @Y (@A . @Z)) (append @X @Y @Z))

So, to be precise, the (Prolog) predicate name append was maybe not the best choice. concatenated would have fit better (see SWI prolog docs). Let's trace what is happening:

: (? append (append (a b) (c) @X))
2 (append (a b) (c) (a . @Z))
2 (append (b) (c) (b . @Z))
1 (append NIL (c) (c))
 @X=(a b c) 
-> NIL

The first list is reduced down to an empty list, then the second argument is set equal to the third argument. After that, the third argument is "filled up" until we reach the final result.

As you can see, it works, but it takes a lot of steps and can become quite unefficient quickly.

The reversepredicate

Let's look at another predicate called reverse (not built-in in pilog). It returns true if the elements of the first argument are in reverse order compared to the second argument:

: (? (reverse (a b c) @X))
 @X = (c b a)

We could implement it using append again with a recursive approach: starting from an empty list and then building it up by concatenating the head.

(be reverse (NIL NIL))

(be reverse ((@A . @X) @R)
   (reverse @X @Z)
   (append @Z (@A) @R))

However, due to the low efficiency of append, this is not to be recommended. Let's find a better approach.

Using an accumulator

A better idea is to use an accumulator to solve this task. An accumulator is basically a list that "takes up" the elements that are processed.

(be accRev ((@H . @T) @A @R)
   (accRev @T (@H . @A) @R) )

(be accRev (NIL @A @A))

The result (which is the third argument) corresponds exactly to the reversed list. So all we need to do is then to define our (reverse (@L @R)) predicate as follows:

(be reverse (@L @R)
   (accRev @L NIL @R))

Let's trace it in order to check if it does what we think it does:

: (? reverse accRev ( reverse (a b c) @X))
1 (reverse (a b c) @R)
1 (accRev (a b c) NIL @R)
1 (accRev (b c) (a) @R)
1 (accRev (c) (b a) @R)
2 (accRev NIL (c b a) (c b a))
 @X=(c b a)
-> NIL

The advantage is that the result is directly available after the last step, while our "naive" reverse needed to travel the whole recursion tree back up.

Example: Palindrome Checker

Speaking of reversed lists, one example should not be missing: How to write a simple palindrome checker. Actually we have all we need already except for the actual palindrome predicate which only takes one argument, a list:

(be palindrome (@L)
   (reverse @L @L) )

For reverse, we can use one of our previously defined predicates. Let's test it:

: (? (palindrome ( r o t a t o r)))
-> T

: (? (palindrome ( a b c d e f g)))
-> NIL

You can find the sources for all examples here.

In the last post of the Prolog Crash Course series, we will take a look at "Cuts and Negations".

Sources

https://www.swi-prolog.org/pldoc/man?predicate=append/3