The GRIPS pre-processor
allows you to write Prolog clauses as function
definitions which it translates into Prolog 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). sum_diff( A,B,C) <- A+B-C. small( P ) if P < 24. divides_by_4( N ) if ( N rem 4 ) = 0.
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
ex if f.
f <-
a if b
else
c if d
else
ex.
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 `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 'CONS'(E), where E is an
atom or a
compound term F(A1,A2,...), is translated into a goal that evaluates
A1, A2, ... and the result
F(EA1,EA2,...) where EAi is the result
of evaluating Ai. For example, 'CONS' pair(1+1,2)
evaluates to pair(2,2). And
'CONS' map
evaluates to map.
This is a convenient way
of constructing terms with a specified functor that isn't
to be treated as a function.
Any expression twist(E), where E is a
compound term F(A1,A2,...), is translated as E
would be, except that it's F's first argument
rather than the final one that gives the result.
I introduced this as a way to permute arguments to
maplist and similar higher-order predicates.
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 (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.
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 into GRIPS.
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 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. The goal
grips(E) treats its
argument E 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.
There is also the exported predicate grips/2.
The goal grips(E,V) treats its
argument E as an expression, translates and evaluates it,
and instantiates V to the result.s
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( 990, fy, user:(grips) ). :- op( 700, xfx, user:(grips) ). :- op( 990, fy, user:(echo) ).For immediate-mode evaluation, as in the previous section.
:- op( 1200, xfx, user:(<-) ). :- op( 1200, xfx, user:(does) ). :- op( 1090, 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( 800, xfy, user:(where) ).Introduces a subsidiary definition in an expression.
:- op( 150, fx, user:(`) ).Quotation operator in expressions.
:- op( 150, fx, user:('CONS') ).
Term-building operator in expressions.
:- op( 150, fx, user:(twist) ).Argument-permutation operator in expressions.
Use module file grips2.pl. This reads the GRIPS
pre-processor 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. It also modifies goal_expansion
in order to translate goal arguments with functor grips/1.
The file grips2_test.pl contains the
examples given in the introduction.
Below, we show them being compiled and executed.
1 ?- cd('c:/kb7/grips').
Yes
2 ?- use_module(grips2).
% grips compiled into grips 0.03 sec, 19,880 bytes
Yes
3 ?- [grips2_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 sum_diff(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
compiler2. 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('c:/kb7/grips').
Yes
2 ?- use_module(grips2).
% grips compiled into grips 0.03 sec, 19,880 bytes
Yes
3 ?- cd(compiler2).
Yes
4 ?- [compile].
% plusplus.pl compiled 0.02 sec, 1,088 bytes
% ordset.pl compiled 0.00 sec, 6,820 bytes
% map.pl compiled 0.02 sec, 13,108 bytes
% lex.pl compiled 0.00 sec, 6,612 bytes
% parser.pl compiled 0.00 sec, 16,148 bytes
% code_generate.pl compiled 0.02 sec, 19,108 bytes
% load.pl compiled 0.00 sec, 1,128 bytes
% machine.pl compiled 0.00 sec, 12,056 bytes
% compile compiled 0.05 sec, 78,180 bytes
true.
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. Just type an
end of file. It will then run, showing the machine instructions
executed as it does so. The file demo shows a run.
12 February 2010