[mercury-users] The Logic of Mercury

[Lee Naish]

>One point is that the expressiveness difference between call/N and
>apply/3 is really not that great.

Its basically the difference between (implicit) currying not no
(or explicit) currying.  I would say currying is a good thing -
it allows greater re-use of code, which is what higher order
is mostly about.

>reusability -- the distinction between call/3 and apply/3 is a far less
>important issue than polymorphic modes, IMHO.

Thats probably true with quite a lot of Prolog-style code.  For
Haskell-style code there is only one simple mode so it shouldn't
be a problem.  I think it would be nice to aim to be able to do
everything Haskell can do plus more.

>Another point is that Lee's discussion of efficiency in that paper is
>rather simplistic.  Although compilers will be able to partially evaluate
>higher-order code into first-order code in many situations, there will
>also be many situations in which that is not possible.  A full and proper
>consideration of efficiency issues needs to take into account the case
>where higher-order code cannot be partially evaluated away. 
>And in fact with straightforward implementation techniques applyN/N will
>be significantly worse than call/N in that case, I believe, particularly
>for large N.  Lee's paper does not consider that issue.

Unless you create data structures containing higher order objects (eg,
lists of functions) its easy to optimise away all higher order overheads.
This should cover more than 95% of cases.

If you create data structures containing functions and you know the type
of their output (ie, the data structure is not polymorphic in the output
type, so the output may or may not be functions) then the type information
can be used to specialise code (eg, calls to apply/3 can be replaced by calls
to call/N).  Mercury is statically typed so this should present no problem.
For code which works with call/N or apply/3 there is no significant
difference in efficiency.  You only pay the additional cost when
you use the additional flexibility.


>A final point is that a large amount of work would need to be done to go
>from the idea in Lee's paper to a concrete proposal for a change to Mercury.


>For example, Lee advocates the use of type systems for higher-order code
>but in that paper he does not make any attempt to say how apply/3 could
>or should be typed.

See Lambda Prolog and related work.

>  So it's a long way from
>idea to concrete proposal to production-quality implementation.

About the same distance as it is from call/N to production-quality
implementation (slightly more if you bother with type-based specialisation),
and the result is a language where you can reuse as much code as in Haskell.

	lee
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------