Dear colleagues,
Sorry for my delay. In the meantime,
Michael has done the work for me, with respect
to Sergio's questions. Next time I will try to react
quicker (especially to concrete things).
First, Sergio's questions.
Michael explanation is right, and the 'coin' example
is quite illustrative. Let's add some words:
- The distinction 'call-time-choice'<-> 'run-time-choice'
is classical, gives raise to quite different semantics,
and correspond more or less to
'call-by-value' and 'call-by-name' parameter passing, which
behave completely different in presence of nondeterministic rules.
- The 'call-time-choice' rule is quite intuitive, if you
think that variables in a rule range over a domain of 'values'
constructed by means of constructor symbols (which by the way
are deterministic constructs). That is, think in a rule
f(X1,...,Xn) = e as specifying that, for all _values_ X1,...,Xn,
a possible (set of) value(s) for f(X1,...Xn) is given by
the (set of) value(s) denoted by e.
This coincides with the usual reading of rules in constructor-based
(deterministic) functional programs, the difference being that
in the deterministic case equational reasoning (i.e., unfolding)
is possible since every expression denotes exactly one value.
In our case, this is not true, and equational reasoning is not possible
(i.e., unfolding is not sound, unless sharing is taken into
account).
- For the technical stuff, the good reference for our approach is
http://mozart.mat.ucm.es/papers/1996/full_esop96.ps.gz
Now, let's continue a bit with the question of nondeterministic
functions as discussed by Michael.
> If Curry is based from the beginning on non-deterministic
> functions, it will be more difficult to convince functional
> programmers that Curry covers their programming paradigm
We do not see why. Maybe some functional programmers could think that
non-deterministic functions are too strange things, but it seems
clear that 'usual' functions are a particular case, hence
Curry would cover FP.
>More importantly, the computation with non-deterministic
> functions complicates from the beginning the operational
> meaning of programs. The current semantics consists of
> replacing equals by equals plus a (possibly) non-deterministic
> instantiation of free variables.
If we are not wrong, all relevant (and more difficult to
explain and understand) aspects of Curry's operational
mechanism (definitional trees, evaluation annotations for
residuation...) are concerned solely with left hand sides of rules.
There is nothing specially complicated (from the point of view
of how to proceed with computations) with having different rules
applicable to the same left hand side, as it already happens, f.i.,
with predicate-like definitions.
Therefore, it seems that we may formulate
Non-deterministic Curry's operational mechanism =
Curry's operational mechanism + Sharing
> However, the computation with
> non-deterministic functions requires the computation with
> sharing which is also considered in your calculus.
This is true, but should not be considered as a real inconvenient,
since surely all people who presumably could be interested in Curry
is perfectly well accustomed to sharing as a real must in the
operational
behaviour of lazy functional languages.
> As far as I know, the calculus in your ESOP paper does only
> implement simple lazy narrowing and does not include the
> improvements developed in the last years which makes
> lazy narrowing as efficient as lazy reduction in functional
> languages.
This is true, with respect to our theoretical work. But we
strongly feel that to fit more sophisticated strategies into
(the theory of) our approach is matter of dedication. From the
practical point of view, our systems (the last one, TOY, in
particular), which implement definitional trees, support
for free (as expected!) nondeterministic functions (the permutation
sort example, f.i., runs perfectly).
> I think it is too early
> to base the core language on non-deterministic functions.
> Thus, I would propose non-deterministic functions as one
> (maybe the first) possible extension of the core language.
We could agree on that. But in this case, we think
that the core language should be _simple_, and therefore
should avoid complicated conditions related to extra variables.
Let's wait for non-deterministic functions, and the problem
will dissapear.
Best regards,
Paco.
--
Francisco J. Lopez-Fraguas
Dep. Informatica y Automatica
Fac. Matematicas Av. Complutense s/n
Universidad Complutense de Madrid
28040 Madrid
SPAIN
Phone: +34 1 3944429
Fax: +34 1 3944607
email: fraguas_at_dia.ucm.es
Received on Mo Feb 03 1997 - 12:17:40 CET