[mercury-users] Manipulating higher order terms.

[Fergus Henderson]

On 07-Dec-1998, Nick <nad101 at york.ac.uk> wrote:
> I'm trying to implement part of an inductive logic programming algorithm
> in mercury. This involves the construction of clauses, which are called to
> see if they entail a set of examples. The obvious way to represent these
> clauses is higher order terms.
> 
> However, I need to know some extra information about the clauses.
> Specifically, I need to be able to extract the names of all of the
> predicates. Is this possible?

No.  The current implementation doesn't keep that information around at
runtime (for efficiency, among other reasons).

However, it would be possible to extract *some* information from closures,
in particular the procedure address and the partially applied arguments,
if any.  The current implementation doesn't provide
any library procedures for getting that information from a closure, but
they wouldn't be very difficult to implement, using some `pragma c_code'
to get at the representation.  I'd been thinking of doing this at
some stage.

One thing you need to be careful about is ensuring that any such procedures
respect the declarative semantics.  In particular, the declarative semantics
for equality between higher-order terms is semantic equality, not name
equivalence or syntactic equality.  Any operation which distinguishes
between higher-order terms on the basis of their form (be it name or address)
rather than their meaning must therefore use committed choice nondeterminism
if it is to avoid being impure.  That's one reason why the standard library
procedure `deconstruct' in the module `std_util' doesn't provide the
functionality.  Eventually there ought to be a similar procedure
called say `deconstruct_rep', with determinism `cc_multi' rather than `det';
this would do much the same thing as `deconstruct', but in addition it
would let you deconstruct the representation of higher-order terms, or of
types with user-defined equalities.

Anyway, if you had that information about the representation of the closure,
you could use the procedure addresses to form predicate names, but of course
they wouldn't be very human-readable.
On the other hand, the same could apply (to a lesser degree) even if the
actual predicate names were available, because in the process of optimization
the compiler may introduce new predicates that don't directly correspond
to any predicates in the original source code.

> The only alternative I can see is to use a ground representation of the
> clause and pass the name around with the predicates,

This is the solution I would recommend.

> which I'd prefer not to do for efficiency reasons.

If the compiler kept predicate names around at runtime, it would have
to incur some of the same efficiency costs that you pay if you do the
same thing yourself, and it would have to incur them even for code
which didn't make use of that feature.

On the other hand, keeping the predicate names around would be useful
for debugging, and keeping other information about predicates around at
runtime may be needed for accurate garbage collection.  So if we could
avoid or minimize the distributed fat problem, then it would be nice to
have them.  We have considered this issue before.  It is in fact
possible to reduce the distributed costs to just the data space
required to hold the predicate names, plus a tiny reduction in code
density which might cause very very slightly worse cache behaviour.
However, doing so requires the use of some tricky assembly-level hacks
(the papers on C-- describe the technique) which are quite
architecture-specific, and we have not yet got around to implementing
them.  Still, even without using this technique, the distributed
fat costs are not *that* bad, and so the mere fact that a better solution
exists may be enough -- we could just take the cost of the distributed
fat now, and implement the tricky assembly-level hacks only if/when
it becomes a significant enough performance issue.

I suppose that answer was longer than you were expecting ;-)

Cheers,
	Fergus.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh>  |   but source code lives forever"
PGP: finger fjh at 128.250.37.3        |     -- leaked Microsoft memo.