nested local predicate definitions
fjh at cs.mu.oz.au
Sat May 31 22:52:41 AEST 1997
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
:- 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 18.104.22.168 | -- the last words of T. S. Garp.
More information about the users