It has been said that
Prolog is the Fortran of
logic-programming; but in one respect,
Prolog
is even closer to
machine-code than Fortran. When writing
Prolog, things which are
conceptually function calls must be rewritten relationally. This requires you to
invent extra variables to pass the output of one relation into the input of the
next. In addition, relations, unlike function calls, can't be nested; so you
have to unwind sequences such as f(g(h(x))) into h(x,V1),
g(V1,V2), f(V2,Result). This becomes tedious.
Another problem is the lack of cues for the reader. Is a predicate conceptually a function, where all but one argument will be inputs and the final one an output? Is it a general relation, with many outputs for one input? Or is it a command, being called for its side-effects?
The
GRIPS
pre-processor allows you to write
Prolog
clauses as function
definitions which it translates into
clauses. Consulting
GRIPS
will automatically
install such expansions via term_expansion, so you can then write
function definitions in your source file in the same way you write grammar
rules. In these definitions, the right-hand side of a definition is an
expression, consisting of (possibly nested) calls to other functions.
GRIPS
allocates result
variables and unwinds calls as described above. You can also write definitions
as commands, to make it clear that they are being called for their side-effects.
As an example, here are an assortment of definitions in GRIPS:
double( N ) <- N*2. quadruple( N ) <- double( double(N) ). factorial(N) <- 1 if N =< 0. factorial(N) <- N * factorial(N-1) if N > 0. factorial1(0) <- 1. factorial1(N) <- N*factorial1(N-1). count( [] ) <- 0. count( [_|T] ) <- 1 + count(T). join( [], L ) <- L. join( [H|T], L ) <- [ H | join(T,L) ]. sum( [] ) <- 0. sum( [H|T] ) <- H + sum(T). sum1( L ) <- 0 if L = []. sum1( [H|T] ) <- H + sum1(T). twist( A,B,C) <- A+B-C. small( P ) if P < 24. divides_by_4( N ) if ( N rem 4 ) = 0.
I developed GRIPS as an experiment in making Prolog easier to teach; at the moment, I'm doing a project which requires defining templates similar to those of Nonsense for building text-valued functions from many large chunks of text interspersed with function calls, and I am using GRIPS as a convenient way to abbreviate the notation. The original version of GRIPS is in my public-domain Prolog library, which also contains a demonstration mini-compiler written in GRIPS. The version linked from this page has been set up to work under SWI-Prolog.
The software is here, as
a zip file. The top-level directory in the file contains the source code and
documentation, plus some small tests. Subdirectory compiler
contains the mini-compiler.
GRIPS recognises and translates the following definitions:
Head <- Expression. (function) Head does Command. (command) Head if Guard. (predicate)
I use it mainly to expand function definitions, and added commands and predicates mainly as an experiment in making Prolog easier for novice students to read.
The connective <- defines a function. Functions are
translated into predicates with an extra argument on the right. The right-hand
side of the function is translated as described under Expressions, into a goal
and a result variable. This result variable becomes the extra argument of the
predicate.
If the right-hand side contains a guard, that guard is translated as described under Guards.
The functions are made deterministic - GRIPS inserts a cut after each translated condition, or (if none), after the final tail goal.
The forms
f <- a if b.
f <- b => a.
f <-
a if b
else
c if d
else
e if f.
f <-
a if b
else
c if d
else
e.
are definitions where the right-hand side is a conditional expression.
double( N ) <- N*2.
translates to
double( N, V ) :- V is N*2, !.
quadruple( N ) <- double( double(N) ).
translates to
quadruple( N, V ) :- double( N, V` ), double( V`, V ), !.
factorial(N) <- 1 if N =< 0.
factorial(N) <- N * factorial(N-1) if N > 0.
translates to
factorial(N, 1) :-
N =< 0,
!.
factorial(N, V) :-
N > 0 , !,
V` is N - 1 , factorial(V`, V``), V is N * V``.
count( L ) <- 0 if L = [].
count( L ) <- 1 + count( tail(L) ) if L \= [].
translates to
count([], 0) :-
!.
count(L, V) :-
L \= [] , ! ,
tail(L, V`) , count(V`, V``),
V is 1 + V``.
where V, V`, V``... indicate new
Prolog< variables introduced
by GRIPS.
GRIPS may optimise some of these translations.
The connective does defines a command. Commands are translated
into predicates with the same number of arguments. GRIPS translates the
actions
in the command body as if they were guards, and places them after the translated
guards. The commands are made deterministic - GRIPS inserts a cut
between
the conditions and actions, or (if no conditions), after the final tail goal.
converse does write_list(reply_to(readline('?'))) and converse.
translates to
converse :-
readline(?, V) , reply_to(V, V`) , write_list(V`),
converse, !.
The connective if defines a predicate. Thus
A if B0translates to
A :- B1where
B0 is treated as a guard and translated into
B1. The difference between these predicate definitions and pure <
Prolog
ones is that
arguments in the guards are treated as function calls and expanded.
divides_by_4( N ) if ( N/2 rem 2 ) = 0.
translates to
divides_by_4(V) :-
V` is _1 / 2 rem 2,
V` = 0.
Any expression E is translated into a goal G and a
result variable V, such that when G is called, it
instantiates V.
Numbers, variables, and atoms (including []) are translated into
the goal true and a result which is the thing itself.
Any expression q(E) is translated into the goal
true and the result E. This is a way of protecting
things that you don't want evaluated.
An expression eval(A) where A is an atom, is
translated into the goal A(V) and the result variable
V. That is, it calls the one-argument goal whose functor is
A. This provides a way of calling parameterless functions. Since
such "functions" are likely only to be of use for their side-effects, this use
won't be frequent. Any other expression eval(E), where
E is not an atom, is translated as E.
Any expression test(G) or do(G) is translated to a
goal formed by translating G as a guard. The result variable is
bound to the atom true. Thus
test( X=1+2 ).
translates to
GOALS: _1 is 1 + 2
RESULT VAR: true
Any expression pr(G) is translated to the goal G.
The result variable is bound to true. This is as for
test and do except that G is left alone,
not treated as a guard. Thus:
pr( X=1+2 ).
translates to
GOALS: _1 = 1 + 2
RESULT VAR: true
This is one way of getting
Prolog
goals into
GRIPS
untranslated.
Lists are translated by making a new list, each of whose elements will be the result of evaluating the corresponding original element. Thus:
[ a, b, 1+2, double(4) ] .
translates to
GOALS: _1 is 1 + 2 , double(4, _2)
RESULT VAR: [a, b, _1, _2]
An expression of the form A++B is treated as list concatenation.
Each list is translated separately, and a goal is then generated in which
they're combined by append. The operator ++ has the same precedence
and associativity as binary +.
An expression of the form (E where G) is translated by
translating G as a guard, and then translating E.
G should instantiate something in E. Thus:
[ 1 + V ] where V=4/5 .
[ 1 + (V where V=4/5) ].
translate to
GOALS: _1 is 4 / 5 , _2 is 1 + _1
RESULT VAR: _2
An expression of the form (E if G) or (G => E)
is a conditional expression. It fails if G fails, otherwise it
returns result E. It is translated by translating G as
a guard, and then translating E.
The expression forms
A if B
else
...
are extended conditionals. If B succeeds they return
A; otherwise they go on to the thing after the else. This can be
another if...else. You can write B=>A
instead of A if B.
An expression of the form (all E where G) returns a list of all
E's that satisfy G.
Structures of other kinds are translated into function calls. How depends on
whether they are evaluable (in Prolog) by is.
If, according to the built-in predicate
current_arithmetic_function, they are, then GRIPS will build
an
is goal to evaluate as much as possible, with subsidiary goals to
evaluate some arguments. Otherwise, GRIPS will just build
subsidiary goals, which add an output argument to the structure: Thus:
1 + 3
translates to
GOALS: _1 is 1 + 3
RESULT VAR: _1
1 + 3 * sin(3)
translates to
GOALS: _1 is 1 + 3 * sin(3)
RESULT VAR: _1
1 + 3 + double(3)
translates to
GOALS: double(3, _1) , _2 is 1 + 3 * _1
RESULT VAR: _2
factorial(1+3*double(3))+4).
translates to
GOALS: double(3, _1) , _2 is 1 + 3 * _1 , factorial(_2, _3) ,
_4 is _3 + 4
RESULT VAR: _4
Notice that interior structures are also evaluated, and not left as structures.
These are conditions within a GRIPS definition, which GRIPS translates into Prolog goals.
Any guard pr(G) where
G is an arbitrary term, is left as G. This is a
way of getting untranslated Prolog code into GRIPS.
Any guard
test(G) or do(G) means the same as
G, and is translated by translating G. This is
pointless, except that it's analogous to the way test and
do behave with expressions.
The guard
nothing is translated to true. This allows you
to write the command definition:
c(A) does nothing if A=1.
A guard that is a variable at translation-time is left alone.
Any guard (A and B) or (A,B) is
translated into (A',B'), where A' and
B' are the translations of A and B
as guards.
Any guard (A or B) or (A;B)
is translated likewise into (A';B').
Any guard
(A foreach C) is translated into foreach(C,A),
which does A for as many times as C can be
resatisfied, and succeeds after all resatisfactions of C.
C and A must be guards; A should
contain commands.
Any guard not(A) or
call(A) is translated into not(A') or
call(A'), where A' and B' are the
translations of A and B as guards.
Any
guard (A=>B) or (B if A) is translated into
(A',!,B'), where A' and B' are the
translations of A and B as guards.
Any
guard else(A,B) is translated into (A';B').
This gives the guard equivalent of the conditional expressions.
Guards P(A), where P is assert,
asserta, retract, or retractall,
are left alone. This ensures that A is treated as a term to
be used with the database, and not an expression to be evaluated.
A guard of the form phrase(G,L) is assumed to be a call to
the DCG predicate phrase/2. The first argument G
(which will be a non-terminal symbol) is left alone. The second argument
(which will be a list to be evaluated) is translated as an expression.
Other structures are translated by treating their arguments as
GRIPS expressions and
recursively translating them. This process can be optimised for arithmetic
operators like < and =:=, which partly
evaluate their arguments anyway; and for =.
GRIPS exports the
predicate grips/1. This treats its argument as an expression,
translating it, evaluating the resulting goal, and displaying the result.
It can therefore be used to evaluate GRIPS expressions from the top-level
interpreter.
Examples:
?- grips 1. Result = 1. ?- grips 1+2. Result = 3. ?- grips length( append( [a,b], [c,d] ) ). Result = 4.
The functor echo/1 causes grips/1 to display
its translation, which may be useful in debugging. For example:
?- grips echo length( append( [a,b], [c,d] ) ) * 3.
GOALS: (append([a, b], [c, d], _G551),
length(_G551, _G542)),
_G627 is _G542*3
RESULT VAR: _G627
Result = 12.
grips declares these operators:
:- op( 1200, fy, user:(grips) ). :- op( 1200, fy, user:(echo) ).For immediate-mode evaluation, as in the previous section.
:- op( 1200, xfx, user:(<-) ). :- op( 1200, xfx, user:(does) ). :- op( 1100, xfx, user:(if) ). :- op( 1100, yfx, user:(else) ). :- op( 1100, xfx, user:(=>) ).Definitions and conditional expressions.
:- op( 1000, xfy, user:(and) ). :- op( 1100, xfy, user:(or) ).Alternatives to
, and ;.
:- op( 1100, xfx, user:(foreach) ). :- op( 150, fx, user:(all) ).Iteration.
:- op( 900, fx, user:(do) ).Invoking commands.
:- op( 200, xfy, user:(where) ).Introduces a subsidiary definition in an expression.
:- op( 500, yfx, user:(++) ).Handy way to call
append.
Consult the file
grips.pl. This reads
the GRIPS pre-processor
from grips_core.pl in module grips_core, and then
modifies term_expansion so as to add a clause for translating
GRIPS definitions. These can
be written into any Prolog source file as you
would grammar rules.
The file grips_test.pl contains the examples given in the introduction. Below,
we show them being compiled and executed.
1 ?- cd('d:\\grips').
Yes
2 ?- [grips].
% grips_core compiled into grips_core 0.03 sec, 20,160 bytes
% grips compiled 0.04 sec, 20,768 bytes
Yes
3 ?- [grips_test].
% grips_test compiled 0.03 sec, 13,732 bytes
Yes
4 ?- grips double(3).
Result = 6.
Yes
5 ?- double(3,D).
D = 6 ;
No
6 ?- listing(double).
double(A, B) :-
B is A*2.
Yes
7 ?- grips echo double(3).
GOALS: double(3, _G338)
RESULT VAR: _G338
Result = 6.
Yes
8 ?- grips quadruple(3).
Result = 12.
Yes
9 ?- grips factorial(5).
Result = 120.
Yes
10 ?- grips factorial1(5).
Result = 120.
Yes
11 ?- grips count([a,b,c,d]).
Result = 4.
Yes
12 ?- grips count( join( [1,2,3,4], [a,b,c] ) ).
Result = 7.
Yes
13 ?- grips sum([1,2,3,4,5]).
Result = 15.
Yes
14 ?- grips sum1([1,2,3,4,5]).
Result = 15.
Yes
15 ?- grips sum1([1,2+0,1.5*2,2^2,25/5]).
Result = 15.
Yes
16 ?- grips twist(1,2,3).
Result = 0.
Yes
17 ?- small(23).
Yes
18 ?- small(24).
No
19 ?- divides_by_4( 3 ).
No
20 ?- divides_by_4( 4 ).
Yes
There is a bigger test program in the subdirectory compiler.
This is a demonstration mini-compiler which takes programs in a very small
subset of Pascal. It lexically analyses them into tokens, parses the token list
into a tree, generates code from the tree, fixes up references in the code, and
then interprets the code on a stack virtual machine. It displays the output of
each stage, and the interpreter displays the machine state as each instruction
is obeyed. The compiler is written in a functional style, using functions
(sometimes represented as sets of domain->codomain pairs) to represent
well-known concepts in programming language semantics, such as the store and the
environment. I wrote it to explain in his own idiom, compiling to a
mathematician starting a computer science M.Sc.
Here is an example program that it can compile and run.
program p;
label
99, 100;
const
five = 5;
var
v : integer;
w : integer;
begin
write('Hello.');
v := 1;
w := 1;
99:
if v=five then goto 100;
v := v + 1;
w := w * v;
goto 99;
100:
write('v = ');
write(v);
write('v! = ');
write(w)
end.
To try the compiler, do as follows:
1 ?- cd('d:\\grips').
Yes
2 ?- [grips].
% grips_core compiled into grips_core 0.02 sec, 19,380 bytes
% grips compiled 0.02 sec, 20,020 bytes
Yes
3 ?- cd(compiler).
Yes
4 ?- [compile].
% ordset.pl compiled 0.02 sec, 6,924 bytes
... you will get lots of 'singleton' warnings ...
5 ?- demo.
This will cause the compiler to try compiling program.pas. It
will display the tokenised program, parse tree, environment, and generated
virtual machine code. It will then ask for input. Give an end of file. It will
then run, showing the machine instructions executed as it does so. The file
demo shows a run.
2 December 2003
[ Jocelyn Paine's Home Page | Free software | Publications ]