[ Jocelyn Ireson-Paine's Home Page | Free software | Publications ]

GRIPS - a pre-processor for functional programming in Prolog

Introduction

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.

Obtaining the software

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 definitions

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.

Function definitions

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.

Examples of function definitions

  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.

Command definitions

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.

Examples of command definitions

  converse does write_list(reply_to(readline('?'))) and converse.
    translates to
  converse :-
    readline(?, V) , reply_to(V, V`) , write_list(V`),
    converse, !.

Predicates

The connective if defines a predicate. Thus

  A if B0
translates to
  A :- B1
where 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.

Examples of predicate definitions

  divides_by_4( N ) if ( N/2 rem 2 ) = 0.
    translates to
  divides_by_4(V) :-
    V` is _1 / 2 rem 2,
    V` = 0.

Expressions

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.

Guards

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 =.

Immediate evaluation

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.

Operators

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.

Using grips

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.

Test programs

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

Test program - the demonstration mini-compiler

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 Ireson-Paine's Home Page | Free software | Publications ]