Ground Representation

Appeared in Volume 9/3, August 1996

fjh@mundook.cs.mu.oz.au
Fergus Henderson
7th May 1996

This article is a joint response by myself and Zoltan Somogyi.

Paul Tarau writes:
In Mercury, the mode and type declarations are enough to break meta-programming once and for all.

That's not the case. Of course, you can't use the non-ground representation, since it is non-logical. But using the non-ground representation is a bad idea anyway.

If you want examples of meta-programming in Mercury, see < http://www.cs.mu.oz.au/~fjh/mercury/interpreter.m>, or download the Mercury source distribution - after all, the Mercury compiler is itself one big meta-program.

Paul Tarau continues:
The same happened with Turbo Prolog. A 100-times slower meta-interpreter for 'Edinburgh Prolog functionality'. It was a little bit smaller and a lot slower than if it had been coded in C.

The reason the Turbo Prolog meta-interpreter is so slow is the same reason that the Goedel meta-interpreter is slow - lack of destructive update. Although the support for unique modes and destructive update in Mercury is not quite complete, there is probably enough there to write a reasonably efficient meta-interpreter using uniq_array.m.

Paul Tarau continues:
I would switch to Visual Prolog if it had type inference, and to Mercury if it had at least as much mode inference as Visual Prolog :-).

Type and mode inference will be available in the next release of Mercury.

Here's a short meta-interpreter:

:- module meta_interpreter.
:- import_module term, varset, clause_db.
:- pred solve(database::in, term::in, varset::in, varset::out).

solve(DB, functor(atom(","), [A, B], _)) --> 
     solve(DB, A) , solve(DB, B).

solve(DB, functor(atom(";"), [A, B], _)) --> 
     solve(DB, A) ; solve(DB, B).

solve(Database, Goal) -->
     { clause(Database, Goal, ClauseVarSet, Head0, Body0) },
     rename_apart(ClauseVarSet, [Head0, Body0], [Head, Body]),
     unify(Goal, Head),
     solve(Database, Body).

We don't think this meta-interpreter is very useful. Nor is a similar Prolog meta-interpreter. If you want to do anything meaningful with either, then they're both going to need plenty of work.

dominic@aethos.demon.co.uk
Dominic Binks
13th May 1996

(1) Mercury's syntax for meta-programming is not that much less concise than Prolog's and (2) Prolog's concise syntax for meta-programming is based on a fundamentally flawed semantics which creates real practical problems when meta-programming in Prolog. I agree that Prolog's non-ground meta-programming has advantages in terms of conciseness, but I think these are outweighed by the additional complications caused by the flawed semantics.

In my experience of extensive ground meta-programming (in Goedel) and reasonable experience of programming non-ground in Prolog, I would not even consider writing anything but a trivial program in the non-ground representation. There are simply too many pitfalls. Some of the most important predicates for the non-ground representation are those that are used to avoid incorrectly binding variables (i.e. renaming variables and grounding the term in some reversible way). Both these are far more easily and (more importantly) cleanly implementable in a ground representation.

Paul Tarau) writes:
Meta-programming in Prolog is not only useful but it's fun too. Because of its non-ground representation! It really adds practical expressiveness. And declarativeness in the (real) sense that you do not have to say how, but just what you mean.

I don't find non-ground meta-programming in Prolog fun, because I have to continually be on my guard to avoid making errors as a result of the dangerous non-ground representation semantics.

I find that the ground representation and the type system are essential for me to even hope to program well. Types and the ground representation are essential because they make the compiler more helpful.

tarau@info.umoncton.ca
Paul Tarau
15th May 1996

It would be interesting to see how the ground representation of append/3 actually looks (type/mode info included!) in Goedel and Mercury.

I am not against using ground representation. Having a built-in ground representation carefully packaged as an abstract data-type (as in Goedel or Mercury) does no harm. The important thing is having the choice to use whatever is more suitable. My hesitation is about language design which makes ground representation the only way to go.

Another, maybe neglected topic is the ability to chose the right 'granularity'. A fixed built-in ground representation might force you to deal with too much detail (like quoting each ASCII code occurring in a name :-)). I guess some 'zooming' ability is present in the ground representation libraries of Goedel and/or Mercury and this is not currently a problem.

I recall from my TurboProlog experience that some of my concerns w.r.t ground representations were speed-related. Rememeber Borland's 50-100 times slower Prolog-in-TurboProlog (meta)-interpreter!

Reflective representations directly benefit from fast object level unification compilation. This is also important for good compilation time when the compiler is written in the language itself. Having learned a few things from the 'minefields of purity', BinProlog now compiles itself to bytecode in about 50 seconds (on a Toshiba 210 laptop) and to C in about 70 seconds.

Actually, Prolog's reflective non-ground representation helps a lot when going even further: self-adjusting dynamic recompilation which happens on the fly, only when needed (see BinProlog 5.00). While benefiting from compilation, the user has consult times typical for interpreted code i.e. only limited by the speed of the parser. Not being restricted in expressiveness by mandatory ground representation was crucial.

My Prolog 'dream-machine' is just one step further: the emulator itself can be written in Prolog. Actually the BinWAM is simple enough (a minimal emulator for pure Prolog would fit in about 8 instructions). Some impurity might be needed to make the abstract machine completely transparent as a Prolog data structure. Once the thing works on top of Prolog, passing it directly to Java or C by a compilation scheme which knows enough about itself would close the loop.

fjh@mundook.cs.mu.oz.au
Fergus Henderson
15th May 1996

Paul Tarau writes:
It would be interesting to see how the ground representation of append/3 actually looks.

The Mercury compiler actually uses about three different representations of Mercury programs (not to mention a couple of representations of the generated C code).

The 'term' representation is the closest to Prolog's standard non-ground representation. But unlike the standard Prolog representation, it includes information about the source code file and line number where the terms were read from.

I started writing down the 'term' representation of append/3 in Mercury, but then I realized that there was no point. The Mercury representations are a mixture of concrete and abstract data types. If the representation you are using is an abstract data type, why does it matter what it looks like?

The important question is how difficult is it to write programs that manipulate this representation.

Paul Tarau writes:
Actually, Prolog's reflective non-ground representation helps a lot when going even further: self-adjusting dynamic recompilation which happens on the fly, only when needed (see BinProlog 5.00).

I think having the interpreter and compiler are the key ingredients; I don't see how using a non-ground representation would help.

Paul Tarau:
My Prolog 'dream-machine'...

In Mercury, you could use unique modes to do this sort of thing without any impurity.

dominic@aethos.demon.co.uk
Dominic Binks
16th May 1996

Paul Tarau writes:
It would be interesting to see how the ground representation of append/3 actually looks.

Granted the Goedel version is enormous. However, this is a somewhat unfair example. append/3 is a very short predicate in Prolog (2 clauses). However, in Goedel the representation is not of Append/3 but of the program that contains Append/3 which includes typing information, the Lists module and the Integers module. This is like including part of the Prolog interpreter.

Fergus Henderson wrote:
The important question is how difficult is it to write programs that manipulate this representation.

Exactly. In order to program meta-programs using the ground representation you never have to trouble yourself with what the representation looks like. In Goedel (and presumably Mercury) there is a set of modules that provide access to a representation. What they do is of no interest to the programmer.

Fergus Henderson continues:
My experience is that it is easy to write meta-programs in Mercury.

Well, I have to somewhat disagree with this. Writing meta-programs with the ground representation is easy once you've unlearnt the (rather unnatural) non-ground representation. I say unnatural because if you were writing a Prolog interpreter/compiler in C, C++, Haskell, Java, etc, you would implement a set of functions/objects for manipulating the representation of the program. So Prolog is unnatural in it's treatment of object programs.

Paul Tarau writes:
I recall from my TurboProlog experience that some of my concerns w.r.t ground representations were speed-related. Rememeber Borland's 50-100 times slower Prolog-in-TurboProlog (meta)-interpreter!.

Yes, Goedel meta-programs are slow to run. But, it is still easier to write a correct meta-program that is more amenable to specialisation in the ground representation than in the non-ground representation. Consider Corin Gurr's self applicable partial evaluator.

Paul Tarau writes:
My Prolog 'dream-machine'...

This doesn't sound too far from Corin Gurr's partial evaluator that uses an interpreter that uses WAM like structures and can be partially evaluated to be a compiler to WAM instructions. The system is written entirely in Goedel.