[m-dev.] Why does the language insist on explicit lambdas?

[Fergus Henderson]

On 10-May-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> I posted a whinge about the error concerning the following 
> not being valid code to the bugs list:
>
> :- module foo.
> :- interface.
> 
> :- func foo(func(A, B, C) = Z, A, B, C) = Z.
> 
> :- implementation.
> 
> foo(F, A, B, C) = foooo(F(A), B, C).
> 
> :- func foooo(func(B, C) = Z, B, C) = Z.
> 
> foooo(F, B, C) = F(B, C).
> 
> The language requires that we instead write
> 
> foo(F, A, B, C) = foooo((func(X, Y) = F(A, X, Y)), B, C).
> 
> This seems unnecessarily cumbersome to me.  I'm not asking
> the compiler to do any higher order mode inference or
> anything like that: it has all the information it needs to
> construct the closure (my particular bug was in pred based
> code where all the types and modes were explicitly listed),
> but for some reason the reference manual says that ain't 
> going to happen.  I've had a look through 
> compiler/higher_order.m, but couldn't find any explanation 
> for the restriction.
> 
> Is this restriction really necessary or is it just a matter
> of getting round to making the compiler do the deed?

This has come up before (a long time ago, I think).
The old answer was as follows.  But I think the
situation may have changed somewhat now.

----------

The basic issue is that it's hard to implement.
There's also some difficulties with type inference
(as opposed to type checking).

The typechecker is doing constraint solving.
Currently it does all the constraint solving eagerly,
using a breadth-first algorithm.  If you allow
code like the above, then some constraints would
have an infinite number of solutions, and so can't be
handled eagerly.  Instead, the typechecker would need to
delay those constraints.

The constraints with an infinite number of solutions correspond
to higher-order calls. E.g. for an expression of the form

	F(A)

we could infer the types

	F :: func(T1) = T
	A :: T
or
	F :: func(T1, T2) = T
	A :: func(T2) = T
or
	F :: func(T1, T2, T3) = T
	A :: func(T2, T3) = T
etc.

This also causes problems if we're trying to infer the type of
a function such as

	foo(F, A) = F(A).

because the type of this would be ambiguous.

----------

OK, so that was the old story.  But now that I think about it a bit
more, I suppose the type checker doesn't handle all constraints eagerly
any more.  In particular, type class constraints get delayed.  Maybe we
could do something similar here, with a higher-order call adding a class
constraint for some builtin type class constraint.  i.e. for

	p(P, A) :- P(A).

we'd infer

	:- pred p(T1, T2) <= call(T1, T2).

Then we'd just need to have some builtin instances of this type class
for the builtin higher-order types.  Hmmm, interesting...
I haven't thought through all the ramifications of this.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------