[mercury-users] Higher order programming

[Lee Naish]

In message <19990426093333.N2059 at cs.mu.oz.au>you write:
>I agree with Lee that the interface between the functional and
>relational parts of Mercury could be smoother.  But I disagree with
>his suggestion to make functions single-moded versions of predicates
>with one fewer argument.

>  The view you're
>taking is that functions are relations

>  The other view is that a predicate is
>just a function which returns a bool

>But unfortunately the distinction between predicates and functions
>returning bool means, eg, you can't define:
>
>	:- func small(int) = bool.
>	small(N) = N < 10.
>
>unless someone goes off and defines a whole raft of predicates as
>functions returning bool.

You could do it with a single function which takes a predicate and
returns a bool (and use this wrapper).  Alternatively, there is no
particular reason in Mercury why the standard test predicates (where
everything is input) could not be functions returning a type bool if it
was allowable to call a bool.

The key reason why the "predicates are functions" view is less natural,
in my opinion, crops up when you consider modes(and determinism).
Specifically, the predicate view allows you to write rules with
local (existentially quantified) variables on the RHS.  Writing

p(X,Z) :- q(X,Y), r(Y,Z).

is natural.  With the functional view, it must be understood as

p(X,Z) = q(X,Y) & r(Y,Z).

which does not fit well with the FP view due to the local variable Y,
which complicates the declarative view as well as the procedural view
required to implement this flexibility.  In contrast, *any* flattened
functional program can be viewed as a relational program with no
conceptual difficulty (you actually lose information, making lazy
evaulation difficult, but thats not an issue for Mercury right now at
least).

>More seriously, if you manage to define the
>small/1 function (predicate), you still can't write
>
>	if small(X) then ... else ...

You just want a different if-then-else construct for function and
predicates - overloading tends to be messy.  In NUE-Prolog I used the
?: construct from C, the condition being a *predicate*.

>My second objection to Lee's suggestion is that I believe reversable
>functions are potentially a very useful feature, especially with type
>classes.  In fact, I would like to see Mercury move toward removing
>the distinction between functors and functions.  This would, in my
>opinion, provide a cleaner model of abstract vs. concrete types: an

>We can push this even further, by providing a type that appears to be
>a concrete type, but in fact its constructors are actually just
>functions that construct some representation of the term.

The functors = functions view is less radical than the predicates =
functions view.  In fact, the theory usually refers to function symbols
rather than functors - its really just a matter of the equality theory
used.  I understand the desire for this flexibility, but I'm not
convinced you want the full power of reversible functions, particularly
nondeterministic ones (this is likely to make the theory a bit of a
mess).  The standard (syntactic) equality theory allows equality to be
determined in flexible modes (via unification) but maintaining determinism.

In NUE-Prolog I went some way towards this, but used a different
syntax and some strong restrictions.  For example, you could define

cons(X,Y) == X.Y.
nil == [].

as a concrete implementation of your abstract cons and nil.  The
NUE-Prolog preprocessor doesn't restrict the directionality of
"functions" defined using == (it actually inlines them so you don't lose
indexing etc - the main reason Prolog programmers *don't* use abstract
types), and complains if there are multiple == equations for a function
(thus inling won't lead to bad code bloat and the functions must be
deterministic).  Something along these lines could possibly be
incorporated into Mercury without the full generality of reversible
(nondet) functions.

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