[mercury-users] Recursive lambdas

[Thomas Conway]

On Tue, Jan 25, 2000 at 04:32:48AM EST, Ralph Becket wrote:
> The 0.9 compiler's just complained about the following:
> 
> ...,
> P = (pred(...) :- <<stuff which includes a recursive call to P>>)
> ...
> 
> saying that
> 
> atom.m:1275:   expected instantiatedness for non-local variables
> atom.m:1275:   of lambda goals is `ground'.
> 
> I realise this is slightly naughty in terms of the occurs check,
> but for lambdas this seems to be an entirely reasonable thing to
> want to do.
> 
> Is there a solution?

I thought long and hard about this one when I was writing higher
order parser combinators for my SGML parser. The best I could
come up with was to abstract out the recursing into a separate
combinator. For example, consider the grammar [fragment]:

expr --> term
expr --> exper + term

term --> ...

It'd be nice to be able to write:
	ExprParser = (TermParser or (ExprParser and token(+) and TermParser)),
	...

Instead I ended up with:

:- pred rec(parser(T), list(T), list(T)).
:- mode rec(in(parser), in, out) is semidet.

lrec(RecCase) -->
	( RecCase ->
		lrec(RecCase)
	;
		[]
	).

Which we can use by transforming the grammar:

expr' --> term rest_expr

rest_expr --> []
rest_expr --> + term rest_expr

and writing:
	ExprParser = (TermParser and lrec(token(+) and TermParser))


-- 
 Thomas Conway )O+     Every sword has two edges.
     Mercurian            <conway at cs.mu.oz.au>
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------