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.
First I installed Chibi:
$ git clone https://github.com/ashinn/chibi-scheme/ $ cd chibi-scheme $ sudo make install
$ 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-)
Member of a list
A popular example of using prolog is the
member function (here I use
mem to not clash with a builtin
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
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
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
(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.
Another common prolog example is appending two lists. Given the call
append(X, Y, Z),
Z will contain the result of appending
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
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  appended to  the list [1,2] ?- app(,,[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]], [, [2, 3]], [[1, 2], ], [[1, 2, 3], ] ].
The direct translation to Shen prolog is:
(defprolog app  Y Y <--; [H|T] Y [H|T2] <-- (app T Y T2); ) /* Is  appended to  the list [1 2] */ (4-) (prolog? (app   [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] ] [ [2 3]] [ [1 2 3]] ]
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.
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 ;
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,
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
[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
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
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(,). 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  )) 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
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: