Channels ▼

Jocelyn Paine

Dr. Dobb's Bloggers

GRIPS: a Preprocessor for Functional Notation in Prolog

February 11, 2010

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

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.<br />
we would have to unwrap the expression so it becomes
  mult( A, B, V1 ),<br />  mult( A, C, V2 ),<br />  plus( V1, V2, X ).<br />

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 ).<br /><br />  fac( N, F ) :-<br />    Nd is N-1,<br />    fac( Nd, Fd ),<br />    F is Fd * N.<br />
I can code its second clause as
  fac( N, F ) :-<br />    fac( grips N-1, Fd ),<br />    F is Fd * N.<br />

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 ) :-<br />    F is N * grips( fac( N-1 ) ).<br />
Grips knows about "is", so it will correctly translate this mixture of arithmetic operators and ordinary predicates.

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.<br /><br />  fac( N ) <-<br />    N * fac( N-1 ).<br />

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 )<br />

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 ) :-<br />    number( Expr ), !.<br /><br />  trans_expr( Expr, Expr, true ) :-<br />    var( Expr ), !.<br /><br />  trans_expr( Expr, ResultVar, Goal ) :-<br />    Expr =.. [ F | Args ],<br />    trans_arglist( Args, ArgResults, ArgGoals ),<br />    append( ArgResults, [ResultVar], ArgsAndResultVar ),<br />    FGoal =.. [ F | ArgsAndResultVar ],<br />    Goal = ( ArgGoals , FGoal ).<br /><br /><br />  trans_arglist( [ Arg1 | Args ], [ Result1 | Results ], Goal ) :-<br />    trans_arglist( Args, Results, Goals ),<br />    trans_expr( Arg1, Result1, Goal1 ),<br />    Goal = ( Goal1 , Goals ).<br /><br />  trans_arglist( [], [], true ).<br />

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 ) <-<br />    N * fac( N-1 ).<br />

Conjoining goals

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

  conjoin( true, G, G ) :- !.<br />  conjoin( G, true, G ) :- !.<br />  conjoin( G1, G2, (G1,G2) ).<br />
This is a good utility to have whenever we write programs that code-generate Prolog.

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 ) :-<br />    G =.. [ F | Args ],<br />    trans_goal_args( Args, ArgResults, ArgGoals ),<br />    FGoal =.. [ F | ArgResults ],<br />    GTranslated = ( ArgGoals , FGoal ).<br /><br /><br />  trans_goal_args( [], [], true ) :- !.<br /><br />  trans_goal_args( [Arg1|Args], [Result1|Results], Goal ) :-<br />    trans_goal_arg( Arg1, Result1, Goal1 ),<br />    trans_goal_args( Args, Results, Goals ),<br />    Goal = ( Goal1 , Goals ).<br /><br /><br />  trans_goal_arg( Arg, Result, Goal ) :-<br />    nonvar( Arg ),<br />    Arg =.. [ grips , E ], !,<br />    trans_expr( E, Result, Goal ).<br /><br />  trans_goal_arg( Arg, Arg, true ).<br />
This predicate, trans_goal, runs over the arguments of a goal "G". If any argument is a term "grips(E)", trans_goal calls trans_expr on the expression "E". It collects the goals for evaluating the arguments and prepends them to "G". Thus, the goal
  write( grips( plus(1,2) ) )<br />
gets transformed into
  plus( 1, 2, R ), write( R ).<br />

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 ) :-<br />    nonvar( G ),<br />    G =.. [ _ | Args ],<br />    member( Arg, Args ), nonvar( Arg ), functor( Arg, grips, 1 ), !.<br /><br /><br />  :- multifile user:goal_expansion/2.<br /><br /><br />  :- dynamic user:goal_expansion/2.<br /><br /><br />  user:goal_expansion( G, GTranslated ) :-<br />    needs_translating( G ), !,<br />    trans_goal( G, GTranslated ).<br />
As with trans_goal, I've taken care to avoid an explicit "grips(E)" in the code.

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).<br />
I translate "plus(N,N)", giving the goal "plus(N,N,R)". I use this as the tail of the new predicate. I then insert "R" as the final argument of "double(N)". And lo and behold:
  double( N, R ) :- plus( N, N, R ).<br />

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

  :- op( 1200, xfx, user:(<-) ).<br /><br /><br />  trans_def( (Head <- Expr) , (PrologHead:-Tail) ) :-<br />    !,<br />    trans_expr( Expr, ResultVar, Tail ),<br />    trans_head( Head, ResultVar, PrologHead ).<br /><br /><br />  trans_head( Head, ResultVar, PrologHead ) :-<br />    Head =.. [ F | Args ],<br />    append( Args, [ResultVar], ArgsAndResultVar ),<br />    PrologHead =.. [ F | ArgsAndResultVar ].<br />

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.<br /><br /><br />  :- dynamic user:term_expansion/2.<br /><br /><br />  user:term_expansion( Def, DefTranslated ) :-<br />    trans_def( Def, DefTranslated ).<br />

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 ) )<br />
stay as it is, or evaluate to "write( pair( 3, 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 )<br />
one has to examine the predicate definitions and accompanying comments or mode declarations before being sure of the data flow. But the same call in functional notation makes the flow immediately clear:
  fred( foo( bar(C,D) ), D )<br />
So I have used functional notation in teaching Prolog, to make it easier for novices to read Prolog code.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video