GRIPS: a Preprocessor for Functional Notation in Prolog

Although Prolog can be remarkably concise, it's far from ideal when we want to compose function calls. Even an expression as simple as "length of list A appended to list B" must be unwrapped into "append A to B giving C, then return the length of C". I'll explain how I overcame this by writing a preprocessor that translates functional notation into Prolog. It lets me define predicates as if defining functions, and write nested function calls without having to do what Fortran implementors had taught their compilers to do in the 1950s. The version described here works with SWI-Prolog.

Contents

• Introduction: the problem with Prolog
• Translating function calls
• Conjoining goals
• Using goal_expansion
• Translating function definitions
• Using term_expansion
• Extending Grips
• What's the semantics?
• Applications

Introduction: the problem with Prolog

Let us suppose that Prolog's designers had never invented the arithmetic operator is. Assume instead that they gave us predicates such as plus and mult, each performing arithmetic operation on its first two arguments and returning the result in the third. Then instead of writing

  X is A*B + A*C.

  mult( A, B, V1 ),
  mult( A, C, V2 ),
  plus( V1, V2, X ).

Fortunately, we do have is, which spares us this inconvenience when doing arithmetic. But when we want to manipulate sets, vectors, complex numbers, lists — indeed, any time we just want to nest function calls — we are still forced to do this unwrapping.

So I have written a preprocessor named "Grips" that does it for me. One of its benefits is that I can pass arithmetic expressions as arguments to goals, avoiding the eternal NextLength is Length + 1's and NextCounter is Counter-1's that disfigure so many programs. As an example, instead of defining "factorial" as

  fac( 0, 1 ).

  fac( N, F ) :-
    Nd is N-1,
    fac( Nd, Fd ),
    F is Fd * N.

  fac( N, F ) :-
    fac( grips N-1, Fd ),
    F is Fd * N.

Here, grips is my evaluation operator. It tells the translator to generate a goal that evaluates N-1, and prepend it to the call of fac.

Indeed, I can move the evaluation operator further out and define:

  fac( N, F ) :-
    F is N * grips( fac( N-1 ) ).

I can also write fac as a function, promoting functional evaluation to cover all of the body, as it were. Here is fac defined in this way:

  fac( 0 ) <- 1.

  fac( N ) <-
    N * fac( N-1 ).

In the rest of the essay, I'll explain how I implemented Grips for SWI-Prolog. Some of the techniques may be useful if you want to write other preprocessors.

Translating function calls

The idea is to translate each expression into a pair consisting of a goal and a "result". The result will be the original expression if that needs no evaluation. Otherwise it will be a variable which the goal will bind to the result of evaluation. For example:

Expression	Goal	Result
1	none	1
f(1)	f(1,R)	R
f(g(1),h(2))	g(1,V1),h(2,V2),f(V1,V2,R)	R

I do this as follows. If the expression is a number, return it as the result. The goal doesn't need to do anything, so make it true.

Otherwise, assume the expression is a function call. Split this into the function, F, and its arguments. Translate the arguments into a goal ArgsGoal which evaluates them, together with a variable to hold the result of evaluation. Then conjoin to ArgsGoal another goal FGoal, formed by calling F on a list of the evaluated arguments to which a result variable is appended.

Here are some examples. To translate plus(1,2), no code is needed to evaluate the arguments, so ArgsGoal becomes true. The goal FGoal is the function F — that is, plus — called on the evaluated arguments with a result variable appended. In this case, the evaluated arguments are the same as the originals, so FGoal becomes plus(1,2,R), where R is the result variable.

For the more complicated expression plus( mult(1,2), 3 ), ArgsGoal becomes mult(1,2,R1). The evaluated arguments becone [ R1, 3 ], where the first one is replaced by the variable holding the result of evaluating it. The goal FGoal becomes plus( R1, 3 ). And finally, the goal for evaluating the entire expression becomes ArgsGoal conjoined with FGoal, or

  mult( 1, 2, R1 ), plus( R1, 3, R )

Here is the translation code. The predicate trans_expr translates the expression in its first argument into a result in its second and a goal in its third. It calls trans_arglist to translate function arguments:

  trans_expr( Expr, Expr, true ) :-
    number( Expr ), !.

  trans_expr( Expr, Expr, true ) :-
    var( Expr ), !.

  trans_expr( Expr, ResultVar, Goal ) :-
    Expr =.. [ F | Args ],
    trans_arglist( Args, ArgResults, ArgGoals ),
    append( ArgResults, [ResultVar], ArgsAndResultVar ),
    FGoal =.. [ F | ArgsAndResultVar ],
    Goal = ( ArgGoals , FGoal ).


  trans_arglist( [ Arg1 | Args ], [ Result1 | Results ], Goal ) :-
    trans_arglist( Args, Results, Goals ),
    trans_expr( Arg1, Result1, Goal1 ),
    Goal = ( Goal1 , Goals ).

  trans_arglist( [], [], true ).

I have added a clause that checks for expressions that are variables. These shouldn't occur as the argument to grips, but will turn up when Grips translates definitions, which could contain variables (possibly from their head) in the tail expression, in the way that the second clause for factorial above did:

  fac( N ) <-
    N * fac( N-1 ).

Conjoining goals

If you try this code, you will find the generated goals contain a good deal of unnecessary trues. By writing a goal-conjoining predicate, I made Grips remove these:

  conjoin( true, G, G ) :- !.
  conjoin( G, true, G ) :- !.
  conjoin( G1, G2, (G1,G2) ).

Using goal_expansion

SWI-Prolog contains several preprocessor hooks: predicates that you can define in order to make the compiler preprocess various syntactic entities in your code. These are not in the ISO Prolog standard, but several other implementations, such as SICStus, also provide them. If your Prolog doesn't, you will have to find another way to hook your preprocessor into it. The easiest is to write your own version of consult.

I use the goal_expansion hook to add the grips macro mentioned earlier. As it reads a file, SWI-Prolog hands each goal G appearing in the body of a clause to goal_expansion, passing it as the first argument. If the call succeeds, G gets replaced by goal_expansion's second argument, assumed to be its translation.

This is how I make goal_expansion act. First, I write a predicate to translate goals whose arguments could contain a grips:

  trans_goal( G, GTranslated ) :-
    G =.. [ F | Args ],
    trans_goal_args( Args, ArgResults, ArgGoals ),
    FGoal =.. [ F | ArgResults ],
    GTranslated = ( ArgGoals , FGoal ).


  trans_goal_args( [], [], true ) :- !.

  trans_goal_args( [Arg1|Args], [Result1|Results], Goal ) :-
    trans_goal_arg( Arg1, Result1, Goal1 ),
    trans_goal_args( Args, Results, Goals ),
    Goal = ( Goal1 , Goals ).


  trans_goal_arg( Arg, Result, Goal ) :-
    nonvar( Arg ),
    Arg =.. [ grips , E ], !,
    trans_expr( E, Result, Goal ).

  trans_goal_arg( Arg, Arg, true ).

  write( grips( plus(1,2) ) )

  plus( 1, 2, R ), write( R ).

Notice that the first clause to trans_goal_arg needs to test whether it is dealing with a grips(E). I took care not to write the grips(E) explicitly, instead calling =.. to test for it. If I hadn't, then if I already had the preprocessor installed (which I might if repeatedly editing, cnsulting, and testing it), it would try expanding this particular grips(E), with amusing but non-terminating results.

Now I can connect trans_goal to goal_expansion, by writing a clause for the latter. I make this clause test whether the goal actually needs translating — whether it does contain a grips — and fail if not. This is good practice, because some Prologs might call goal_expansion over and over again on the same goal if I make it return the original without any change. Here is the code:

  needs_translating( G ) :-
    nonvar( G ),
    G =.. [ _ | Args ],
    member( Arg, Args ), nonvar( Arg ), functor( Arg, grips, 1 ), !.


  :- multifile user:goal_expansion/2.


  :- dynamic user:goal_expansion/2.


  user:goal_expansion( G, GTranslated ) :-
    needs_translating( G ), !,
    trans_goal( G, GTranslated ).

There could be could be several different clauses for goal_expansion in force at the same time if you or someone else have installed other preprocessors. You'll need to ensure these work correctly together, especially if a single goal contains constructs from different preprocessors, or gets translated by one preprocessor into a construct handled by another.

Translating function definitions

Translating function definitions is now straightforward. To translate

  double(N) <- plus(N,N).

  double( N, R ) :- plus( N, N, R ).

Here is the translation code, in which the main predicate is trans_def:

  :- op( 1200, xfx, user:(<-) ).


  trans_def( (Head <- Expr) , (PrologHead:-Tail) ) :-
    !,
    trans_expr( Expr, ResultVar, Tail ),
    trans_head( Head, ResultVar, PrologHead ).


  trans_head( Head, ResultVar, PrologHead ) :-
    Head =.. [ F | Args ],
    append( Args, [ResultVar], ArgsAndResultVar ),
    PrologHead =.. [ F | ArgsAndResultVar ].

Using term_expansion

In the same kind of way that I connected trans_goal to goal_expansion, I can now connect trans_def to the term_expansion preprocessor hook. This resembles goal_expansion, but translates complete terms in the source file.

For Grips, term_expansion is simpler to use than goal_expansion: I can test whether a definition needs translating just by whether it contains a <- connective; I don't need to decompose definitions in the same way I did with goals; and I don't need to worry about avoiding explicit calls to <- in the translator. Here is the code:

  :- multifile user:term_expansion/2.


  :- dynamic user:term_expansion/2.


  user:term_expansion( Def, DefTranslated ) :-
    trans_def( Def, DefTranslated ).

Extending Grips

For real-world applications, the code above will need extending. For example, I have made Grips treat the empty-list atom [] as a constant that stands for itself in the same way as numbers. Non-empty lists, it evaluates element by element.

One construct that I added is an expression-disjunction operator named ;. The expression E1;E2 evaluates E1 and returns its result if it succeeds, otherwise returning that of E2.

Turning to arithmetic, Grips translates +, * and other arithmetic operators into calls to is. I find this terribly convenient.

What's the semantics?

We do need to take care with the semantics. One question is how to distinguish between atom constants and functions of no arguments. For example, how should we invoke read/1 in functional notation? We can't write read(), because it's not valid syntax. But if we make Grips take the atom read to denote a call to the predicate, how can we write the atom constant read?

On the other hand, if read denotes the atom, then we need a special notation for the function call. I eventually decided that an atom on its own should be a call, and that to make it a literal, I should precede it by a backquote operator `. In fact, I use ` to quote any term, not just atoms.

A different question: what about the evaluation operator grips? Should the translator recognise it if it occurs at any level inside a goal, or only at the top level? That is, should the goal

  write( pair( grips( plus(1,2) ), 3 ) )

Applications

I use Grips more than I do Definite Clause Grammars. It is just so convenient when writing complicated expressions. It also saves thinking up names for result variables, thus mitigating the psychological disorder known as "naming fatigue" — a steadily increasing inability, as the day wears on, to invent meaningful identifiers.

Functional notation is also wonderful because it makes data flow explicit. When reading a goal such as

  bar( C, D, A ), foo( A, B ), fred( B, D )

  fred( foo( bar(C,D) ), D )