nested local predicate definitions

[Fergus Henderson]

In mail to mercury-bugs at cs.mu.oz.au, Seth LaForge wrote:
> ... (bug report omitted) ...
> One other aspect of mercury which bugs me: higher-order anonymous
> predicates seem rather weak, in particular they're not very useful as
> nested predicates.  As far as I can tell, there's no way to write a
> recursive anonymous predicate...  Is there something I'm missing?

I'm mailing this to mercury-users, since I remember that several
people have asked me this question.

The short answer is no.  From its Prolog ancestry, Mercury has
inherited a flat syntax.  In general, definitions can't be nested.

The long answer is that it is in fact technically possible to achieve
something very close to the desired effect; you do need to use an
auxiliary function, and strictly speaking the local definition you get
is not a recursive one, but the effect is the same.  In the example
below, I've called the auxiliary function `letrec'; it is basically the
same as the Y combinator in lambda calculus.

	:- func factorial6 = int.
	factorial6 = apply(Factorial, 6) :-
		Factorial = letrec( func(Self::in(plain_func), N::in) =
					(R::out) is det :-
			R = (if N = 0 then 1 else N * apply(Self, N - 1))).

In this example, `factorial6' uses a local function `Factorial' that
is defined using letrec -- effectively a local recursive definition.
The `letrec' function used in the first example can be defined as
follows:

	:- type letrec_func(T1, T2) == (func(func(T1) = T2, T1) = T2).
	:- inst letrec_func == (func(in(plain_func), in) = out is det).
	:- inst plain_func  == (func(in) = out is det).

	:- func letrec(letrec_func(T1, T2), T1) = T2.
	:- mode letrec(in(letrec_func), in) = out is det.

	letrec(Func, X) = apply(Func, letrec(Func), X).

By way of contrast, here's a definition of `factorial7' using a
non-nested function `factorial'.

	:- func factorial7 = int.
	factorial7 = factorial(7).

	:- func factorial(int) = int.
	factorial(N) = (if N = 0 then 1 else N * factorial(N - 1)).

Well, I guess when all is said and done, there is a lot to be said for
simplicity, and so this `letrec' function probably isn't of much value
(except perhaps for the Obfuscated Mercury competition ;-).  Still, I
was pleasantly surprised to find that the code the Mercury compiler
generates for `factorial6' is almost exactly the same as the code it
generates for `factorial7' -- apart from one unnecessary branch
instruction, it manages to optimize away all the higher-order code.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.