2016-08-30
Kicking the tires of Shen Prolog
Shen is a lisp based programming language with some interesting features. Some of these include:
- Pattern matching for destructuring function arguments
- Optional static types
- An extensible type system
- A portable base language, called KLambda, that it is implemented on to make porting to systems easier
- Inbuilt 'compiler compiler'
- Integrated Prolog system
It's the last point I want to look at in this post. I've been doing some programming in Prolog recently and wanted to explore how to do similar things in Shen. This post compares some prolog examples to the equivalent Shen prolog to compare the differences.
Installing
There are quite a few options for installing Shen. For this post I used shen-scheme running on chibi-scheme.
First I installed Chibi:
$ git clone https://github.com/ashinn/chibi-scheme/
$ cd chibi-scheme
$ sudo make install
Then shen-scheme:
$ git clone https://github.com/tizoc/shen-scheme
$ cd shen-scheme
$ make
$ chibi-scheme -Rshen.runner
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 19.2
running under Scheme, implementation: chibi-scheme
port 0.14 ported by Bruno Deferrari
(0-)
There is a JavaScript port of Shen that is available online to try that may work for these examples depending on browser support. I was able to use it in Firefox.
For prolog I use SWI Prolog. This comes with many great libraries and examples to use prolog for 'real world' use cases. The examples can be tried online using Swish.
Member of a list
A popular example of using prolog is the member function (here I use mem to not clash with a builtin member function):
mem(X, [X|_]).
mem(X, [_|Y]) :- mem(X, Y).
In prolog syntax a variable is in uppercase and a list is destructured into its head and tail using the syntax [Head | Tail]. The first rule states that X is a member of a list if it appears at the head of the list. The second rule states that X is a member of a list if it is member of the tail of the list.
Some examples of membership testing (?- is the prolog prompt):
?- mem(1,[1,2,3]).
true
?- mem(3,[1,2,3]).
true
Thanks to the magic of prolog it's possible to use the same function to enumerate all items of the list:
?- mem(X,[1,2,3]).
X = 1 ;
X = 2 ;
X = 3.
In this case the prolog toplevel first gives the result X = 1 with a prompt to continue. Using ; prints each result in turn. The query can be read as "What value of X, given the following list, will return true for a call to mem".
The prolog function findall can be used to return a list of all results without needing interaction from the toplevel:
?- findall(X, mem(X, [1,2,3]), Y).
Y = [1, 2, 3].
findall binds to the third argument a list containing all the values of the first argument when substituted in the query in the second argument that result in true. In this case a 1, 2 or 3 value of X results in mem(X, [1,2,3]) being true.
Shen prolog uses s-expression syntax and requires a defprolog construct to introduce rules. The equivalent to the mem function above would be:
(defprolog mem
X [X|_] <--;
X [_|Y] <-- (mem X Y);
)
Shen uses '<--' in place of the prolog ':-' syntax, ';' in place of '.' and calls are made in s-expression format. Calling prolog definitions requires the use of prolog?. The membership testing examples become (the (1-), etc are Shen prompts):
(1-) (prolog? (mem 1 [1 2 3]))
true
(2-) (prolog? (mem 3 [1 2 3]))
true
Shen has the equivalent of prolog's findall:
(3-) (prolog? (findall X [mem X [1 2 3]] Y)
(return Y))
[3 2 1]
Note that the second argument to findall needs to be an atom. In this case, a list (hence the square brackets), not an s-expression function call. To get the actual results of the Y variable the return function is used. return terminates a prolog query and returns the value of its argument.
Appending lists
Another common prolog example is appending two lists. Given the call append(X, Y, Z), Z will contain the result of appending Y to X:
app([],Y,Y).
app([H|T],Y,[H|T2]) :- app(T, Y, T2).
This states that appending an empty list to a second list results in the second list. Appending a list X and Y will put the head of X at the head of the result and recursively call append with the tail of the first list, the original second list and the currently unbound tail of the result list.
All three arguments can be unbound when calling app. Here are some examples:
# Is [1] appended to [2] the list [1,2]
?- app([1],[2],[1,2]).
true.
# What is the result of appending [1,2,3] and [4,5,6]
?- app([1,2,3],[4,5,6],X).
X = [1, 2, 3, 4, 5, 6].
# What list, when appended to [7,8,9] produces [4,5,6,7,8,9]
?- app(X,[7,8,9],[4,5,6,7,8,9]).
X = [4, 5, 6] ;
# What lists can be append to each other to produce [1,2,3]
?- findall([X,Y], app(X, Y, [1,2,3]), Z).
Z = [
[[], [1, 2, 3]],
[[1], [2, 3]],
[[1, 2], [3]],
[[1, 2, 3], []]
].
The direct translation to Shen prolog is:
(defprolog app
[] Y Y <--;
[H|T] Y [H|T2] <-- (app T Y T2);
)
/* Is [1] appended to [2] the list [1 2] */
(4-) (prolog? (app [1] [2] [1 2]))
true
/* What is the result of appending [1,2,3] and [4,5,6] */
(5-) (prolog? (app [1 2 3] [4 5 6] X)
(return X))
[1 2 3 4 5 6]
/* What list, when appended to [7,8,9] produces [4,5,6,7,8,9] */
(6-) (prolog? (app X [7 8 9] [4 5 6 7 8 9])
(return X))
[4 5 6]
/* What lists can be append to each other to produce [1,2,3] */
(7-) (prolog? (findall [X Y] [app X Y [1 2 3]] Z)
(return Z))
[[[1 2 3] []]
[[1 2] [3]]
[[1] [2 3]]
[[] [1 2 3]]
]
Factorial
One way of defining factorial in Prolog is:
fac(0,1).
fac(N,R) :- N > 0,
N1 is N - 1,
fac(N1, R1),
R is N * R1.
The is predicate in prolog is used for binding the result of arithmetic expressions to a variable. Use of fac looks like:
# Is 120 the factorial of 5
?- fac(5,120).
true ;
# What is the factorial of 10?
?- fac(10, X).
X = 3628800 ;
# What factorial gives the result of 5040?
?- fac(X, 5040).
ERROR: >/2: Arguments are not sufficiently instantiated
Note that in this case the backtracking to compute the answer to the last question was not possible. This is because of the way prolog handles boolean and arithmetic expressions. They are non-logical operations and are calculated using an arithmetic evaluator using efficient system arithmetic. Many prolog systems provide a way around this using constraint logic programming which I'll demonstrate later.
Translating to Shen prolog:
(defprolog fac
0 1 <--;
N R <-- (when (> N 0))
(is N1 (- N 1))
(fac N1 R1)
(is R (* N R1));
)
The boolean comparison is introduced using the Shen prolog when function. The is predicate becomes the is function. Other than this the translation is straightfoward as is usage:
# Is 120 the factorial of 5
(8-) (prolog? (fac 5 X) (identical X 120))
true
# What is the factorial of 10?
(9-) (prolog? (fac 10 X) (return X))
3628800
# What factorial gives the result of 5040?
(10-) (prolog? (findall X [fac X 5040] Y) (return Y))
invalid type, expected Number: (#(shen.pvar 2))
Note the use of identical in the first example. My first attempt at trying the direct prolog translation gave the following:
(8-) (prolog? (fac 5 120))
vector-ref: not a vector: (120)
I raised a question on the mailing list about it and the answer was that is in Shen Prolog was specifically designed to bind a variable and it has found a number and not a variable. The use of identical was suggested for the solution.
In the third example backtracking doesn't work with arithmetic expressions in Shen prolog as in the Prolog example.
As mentioned previously, many prolog systems include constraint logic programming libraries that can be used to provide backtracking with arithmetic. This is the equivalent factorial programming using one such library in SWI Prolog:
:- use_module(library(clpfd)).
fac(0,1).
fac(N,R) :- N #> 0,
N1 #= N - 1,
R #= N * F1,
fac(N1, F1).
?- fac(X,5040).
X = 7 ;
Databases
A common use of prolog is querying databases of facts. An example from here presents some bible facts and queries:
parent(abraham,ismael).
parent(abraham,isaac).
parent(isaac,esau).
parent(isaac,iacob).
# Did Abraham have children
?- parent(abraham, _).
true ;
# All the father/son pairs
?- findall([F, S], parent(F, S), Y).
Y = [[abraham, ismael], [abraham, isaac], [isaac, esau], [isaac, iacob]].
# Find the grandchildren of abraham
?- findall(G, (parent(abraham, X), parent(X, G)), Y).
Y = [esau, iacob].
Translating to Shen prolog:
(defprolog parent
abraham ismael <--;
abraham isaac <--;
isaac esau <--;
isaac iacob <--;
)
/* Did Abraham have children */
(11-) (prolog? (parent abraham _))
true
# All the father/son pairs
(12-) (prolog? (findall [F S] [parent F S] Y) (return Y))
[[isaac iacob] [isaac esau] [abraham isaac] [abraham ismael]]
# Find the grandchildren of abraham
(defprolog grandchild
F G <-- (parent F X) (parent X G);
)
(13-) (prolog? (findall G [grandchild abraham G] Y) (return Y))
[iacob esau]
In the last example I had to add a new relation for grandchild as I could not see a way of including multiple clauses in findall as the prolog example did.
Calling Prolog to Shen and vice versa
Calling from prolog to Shen can be done with the is function as shown previously with arithmetic:
(defprolog hi
N <-- (is _ (output "Hello ~S~%" N));
)
(14-) (prolog? (hi "World"))
Hello "World"
It's also possible to use return to return the result of a Shen expression to the top level:
(defprolog double
X <-- (return (* X 2));
)
(15-) (prolog? (double 5))
10
To pass values from Shen to prolog in variables, use receive to bind a prolog variable with the equivalent shen variable. Given the Shen prolog version of factorial earlier it can be called from a Shen function as follows:
(define shen-fac
N -> (prolog? (receive N)
(fac N R)
(return R)))
shen-fac
(16-) (shen-fac 5)
120
Shen functions are introduced using define and arguments are pattern matched similar to ML-like languages. The arguments to pattern match against appear first, followed by -> and then the body to be run if that pattern matched. In this case the shen-fac function is defined to take one argument, N.
Palindromes
This one is a bit of a prolog mind bender and makes use of difference lists. The goal is to have a predicate, palindrome, that is true if the list given to it is a palindrome. That is, the list is the same when read forwards or backwards. The description of the solution is based on this stackoverflow answer.
In a difference list a list is represented as the difference between a normal list and some sublist of the tail of that list that is unknown. So if (X,Y) represents a difference list of list X that has some tail Y then an empty list would be represented as (Xs, Xs). That is, if Xs is the tail of a difference list Xs, then the actual list it represents is the empty list. A single element dffference list is ([X|Xs], Xs) which is a list containing X as the head and any tail, where the difference is that tail. Notice the tails here are unbound - they have no actual concrete representation and any tail would work.
Difference lists are useful for things like efficient concatenation since only binding the tail of a list is needed to concatenate. Given a difference list ([1 2 3|X], X) and ([4 5 6|Y], Y), the concatenation of the two only requires binding X to [4 5 6|Y], giving the difference list ([1 2 3 4 5 6|Y],Y). No copying of lists needs to occur and the concatenation is done in constant time.
In the following example the idea is used to determine if a list is a palindrome. Here is the prolog code:
palindrome(L, L).
palindrome([_|L], L).
palindrome([E|Xs], Tail) :- palindrome(Xs, [E|Tail]).
palindrome takes two arguments to represent the difference list. The first clause states that the difference list (L,L) is always a palindrome. A difference list where its tail is the list itself is an empty list as described previously and an empty list is always a palindrome.
The second clause states that a single element list is always a palindrome. As noted before, a difference list ([X|Xs], Xs) is a single element list containing X.
The third clause is describing that for a list with more than one element to be a palindrome it must be of the form E ... E, where E is a single element and ... is the elements between them and those elements are also a palindrome. Using difference lists the list will have some tail, Tail. This means that E ... E | Tail is a palindrome if ... is a palindrome and Tail is the ignored part of difference list to be subtracted.
So the head of the third clause obtains the first element of the list with [E|Xs] and some Tail for the difference. It states that this is a palindrome if the difference list (Xs, E|Tail) is also a palindrome. And this matches our explanation in the previous paragrah - E ... E | Tail is a palindrome if ... is a palindrome where ... is Xs in our clause.
Using difference lists to solve palindromes allows efficiently pattern matching against the last item of the list - the Tail part of the difference list is effectively used as a pointer to the end of the list so the match against E ... E can be done.
Prolog usage example:
?- palindrome([1,2,2,1],[]).
true ;
?- palindrome([1],[]).
true ;
?- palindrome([1,2,3],[]).
false.
Prolog can even generate solutions interactively:
?- palindrome(X, []).
X = [] ;
X = [_4402] ;
X = [_4402, _4402] ;
X = [_4402, _4414, _4402] ;
X = [_4402, _4414, _4414, _4402] ;
X = [_4402, _4414, _4426, _4414, _4402] ;
X = [_4402, _4414, _4426, _4426, _4414, _4402] .
Note how the list contains anonymous elements but are palindromes.
The translation to Shen is:
(defprolog palindrome
L L <--;
[_|L] L <--;
[E|Xs] Tail <-- (palindrome Xs [E|Tail]);
)
(17-) (prolog? (palindrome [1 2 2 1] []))
true
(18-) (prolog? (palindrome [1] []))
true
(19-) (prolog? (palindrome [1 2 3] []))
false
I've not found a way to interactively generate solutions as in the prolog example.
Wrapping the Shen prolog definition of palindrome into a Shen function for easy use from programs can be done with:
(define palindrome?
L -> (prolog? (receive L) (palindrome L [])))
(20-) (palindrome? [a b b a])
true
Conclusion
There are other features of Shen prolog, including an equivalent of cut, other builtin functions and the ability to suspend unification and use pattern matching in places for efficiency. These are described in The Book of Shen.
The typechecker for Shen is implemented using the prolog facilities in Shen.
For more information on Shen, try:
