[mercury-users] Higher order programming

[Fergus Henderson]

On 23-Apr-1999, Lee Naish <lee at cs.mu.OZ.AU> wrote:
> 
> In message <19990422171708.A5772 at murlibobo.cs.mu.OZ.AU>Fergus wrote:
> >> I think this problem would be easier to solve if there was less
> >> distinction between predicates and functions.
> >
> >That could solve the problem of predicates not taking `function' HO args.
> >
> >But I don't think it would solve the problem of the compiler not being
> >able to infer the modes for higher-order terms.
> 
> I mentioned this for the multi-moded case - the map2 predicate call.
> 
> >If a predicate
> >has more than one det mode, which one would the compiler choose?
> 
> The (only) one declared as a function by the user.

So I guess you're thinking of something like say

	:- pred plus(int, int, int).
	:- mode plus(in, in, out) is function.
				% meaning the same as `is det',
				% plus you are also allowed to use
				% functional syntax for this mode
	:- mode plus(out, in, in) is det.
	:- mode plus(in, out, in) is det.

?
If we only allowed functions to have one mode, then that might make sense.
But given that we allow functions to have multiple modes, I don't think
that would be a very good idea.

> >Why would only one mode be associated with the function?
> 
> The same reason you allow only one determinism: it allows the functional
> syntax to convey more meaning (to the compiler and the human reader).

Well, Mercury allows more than one determinism: forwards modes of functions
can be semidet, and reverse modes of functions can have any determinism at all.
(A "forwards mode" is one with all arguments input and only the function
result output.)

Mercury doesn't allow functions to be nondet in their forwards modes
because that would break referential transparency.

Disallowing reverse modes of functions would allow the functional
syntax to convey more meaning, but I think the cost in terms of reduced
expressiveness would be much too high.  When doing constraint programming,
for example, you want to have multiple modes available, but functional
syntax is still highly desirable in that case.  For the Mercury CLP(R)
interface, we clearly want to use functional syntax; using relational
syntax for arithmetic expressions leads to code which is much harder
to read.

> >Well, in Mercury functions are allowed to have more than one mode.
> >The `+' function may be reversible.  So a goal using a functional
> >expression like `Cs = map2((+), As, Bs)' might be computing
> >As from Bs and Cs rather than computing Cs from As and Bs.
> 
> If + also had the nondet mode computing A and B from C (reasonable if
> they are known to be natural numbers) you could use the syntax above for
> a nondeterministic computation also.

Yes.

> Is this a good idea?  It adds more
> "power"/flexibility, but I would argue its *not* a good idea.

For that particular example, you may be right.
Having reverse modes of functions which are nondeterministic
could lead to creation of choice points in places where you
don't expect it; even though Mercury's determinism declarations
and inference will prevent most such surprises,
it is still probably better style to include an explicit call to
some generator predicate which is clearly nondeterministic.

But having reverse modes of functions which are semidet or det
is much less problematic and I can think of many examples where
it is useful and some examples which I think are compelling.

> Similarly, multi-moded functions are not a good idea.

I don't think this more general conclusion follows.
I think the examples of multi-moded functions in the Mercury CLP(R)
interface are compelling examples.  Bidirectional conversion
functions are another example where multi-moded functions may be
useful.

> In the original design of NUE-Prolog functional syntax was flattened
> into predicates but there was no restriction on the directionality or
> determinism.  In later versions this was changed.  This allowed the
> translator to add when declarations (since the mode was known), thus
> avoiding choice points ever being created, and to check determinism and
> generate warning messages.

In Mercury, the mode and determinism of functions default to
`func(in, in, ...) = out is det', but we also allow users to
override that default by provide explicit mode declarations.
The compiler of course checks the modes and determinism.
Choice points can only be created by functions calls only if
the programmer explicitly declares a mode for that function
which is nondeterministic.  So this gives us pretty much all
of benefits listed above, but we also have more flexibility.

> Similarly the human reader was able to infer
> mode and determinism information whenever functional syntax was used.
> This gained more benefit from the functional syntax.

This is one benefit that the Mercury design doesn't have.
If you see code such as

	p(X, Y) :- X = f(Y).

then you don't immediately know whether this code is deterministic.
However, in Mercury the benefit of knowing _immediately_ is minor,
because it's very easy to find out.  In order to find out whether the code
is deterministic, all you need to do is to look at the declaration for
f/1.  If there is no mode declaration for f/1, then you know it is
deterministic.  If there is an explicit mode declaration, then the
determinism will normally be stated explicitly too.

(The only tricky case is if the programmer explicitly declared the modes
for a function, but let the compiler infer the determinism of those modes.
Mercury allows this case, but in practice I don't think people use it much.
In this case, you might have to compile the file to see from the compiler's
messages what determinism was inferred for that mode.  Making use of this
case for anything other than program development might be considered bad
style, but I don't think it is sufficiently bad for us to disallow it.)

> In the case of
> Mercury, an advantage you would get is the compiler could figure out the
> modes in Cs = map2((+), As, Bs).

Yes.  But in the long term we might be able to get the compiler to figure
that out by itself, without needing to reduce the language's expressiveness.

> The functional programmers get by without nondeterministic/multi-moded
> functions.  If you are programming in that style you don't need them.
> If you are not programming in that style, why not use relational syntax
> instead?

Because functional syntax is often much more readable, even for
programs that make use of multiple modes.  Solving arithmetic constraints
is an important example of this.

> And as a matter of style, if you have a function with an inverse which
> is also a function, for example plus, I suspect the inverse is
> best called something else, for example, minus.  Instead of
> X = plus(Y,Z), you could write Z = minus(Y,X) (more readable, no?),

Certainly using `minus' is more readable if the calling procedure only works
in a single mode.  But if you want the calling procedure to work in multiple
modes, then you need `plus' to have multiple modes, and yet often you would
still prefer to use functional syntax for `plus'.

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