It has been said that
Prolog is the Fortran of
logic-programming; but in one respect,
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
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?
pre-processor allows you to write
clauses as function
definitions which it translates into
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.
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
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.
<- 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
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.
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``... indicate new Prolog< variables introduced by GRIPS.
GRIPS may optimise some of these translations.
does defines a command. Commands are translated
into predicates with the same number of arguments. GRIPS translates the
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
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, !.
if defines a predicate. Thus
A if B0translates to
A :- B1where
B0is 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.
E is translated into a goal
G and a
V, such that when
G is called, it
Numbers, variables, and atoms (including
) are translated into
true and a result which is the thing itself.
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.
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
E is not an atom, is translated as
do(G) is translated to a
goal formed by translating
G as a guard. The result variable is
bound to the atom
test( X=1+2 ). translates to GOALS: _1 is 1 + 2 RESULT VAR: true
pr(G) is translated to the goal
The result variable is bound to
true. This is as for
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: trueThis 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
G as a guard, and then translating
G should instantiate something in
[ 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
E. It is translated by translating
a guard, and then translating
The expression forms
A if B else ...are extended conditionals. If
Bsucceeds they return
A; otherwise they go on to the thing after the else. This can be another
else. You can write
A if B.
An expression of the form
(all E where G) returns a list of all
E's that satisfy
Structures of other kinds are translated into function calls. How depends on
whether they are evaluable (in Prolog) by
If, according to the built-in predicate
current_arithmetic_function, they are, then GRIPS will build
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.
G is an arbitrary term, is left as
G. This is a
way of getting untranslated Prolog code into GRIPS.
do(G) means the same as
G, and is translated by translating
G. This is
pointless, except that it's analogous to the way
do behave with expressions.
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.
(A and B) or
B' are the translations of
(A or B) or
is translated likewise into
(A foreach C) is translated into
A for as many times as
C can be
resatisfied, and succeeds after all resatisfactions of
A must be guards;
call(A) is translated into
B' are the
B as guards.
(B if A) is translated into
B' are the
B as guards.
else(A,B) is translated into
This gives the guard equivalent of the conditional expressions.
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
(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
=:=, which partly
evaluate their arguments anyway; and for
GRIPS exports the
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
?- grips 1. Result = 1. ?- grips 1+2. Result = 3. ?- grips length( append( [a,b], [c,d] ) ). Result = 4.
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
:- 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
Consult the file
grips.pl. This reads
the GRIPS pre-processor
grips_core.pl in module
grips_core, and then
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.
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
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
demoshows a run.
2 December 2003
[ Jocelyn Ireson-Paine's Home Page | Free software | Publications ]