Re: Comments from Madrid

From: Michael Hanus <hanus_at_margaux.informatik.rwth-aachen.de>
Date: Fri, 24 Jan 1997 17:53:54 +0100

Dear Paco,

Thanks for your contribution. I would like to answer to point 2+3
of your message.

> 2. With respect to the question of allowing extra variables in
> right-hand sides, our opinion is quite radical: we strongly
> advocate to adopt non-deterministic functions as the fundamental
> notion underlying the language, instead of the 'classical'
> of deterministic function. The problem of variables in rhs
> vanishes, since they can be used freely. Some arguments
> supporting this (admitedly controversial) point of view follow:

Although I like your framework of non-deterministic functions,
I think it is too early to base the language on this framework
for the following reasons:

1. 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
   (but this is a matter of taste).

2. 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. However, the computation with
   non-deterministic functions requires the computation with
   sharing which is also considered in your calculus. Without
   sharing, the calculus is unsound. This is also the reason
   why our prototype implementation (which is not based on
   sharing) does not compute the correct results of your example,
   although it can deal with non-deterministic functions.

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

4. The combination of your calculus, which is based on narrowing,
   with residuation is not so clear for me. This requires
   some further work. The combination of residuation and narrowing
   is one of the most important points if Curry should provide
   a basis for the different developments in this area.

Although I think that your framework can be extented to
include the last two points, 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.


> 3. The question of equality (p. 4-5 in the Curry report) should
> be clarified. Some comments and suggestions about that:
> * We accept the convenience of considering two kinds of equality,
> otherwise disequality constraints should be used and this
> complicates the language in the overall.
> * In a first moment, in p.4, some rules are given for strict equality,
> which are meant to correspond to the equality used in functional
> languages. This is not true: equality in FL is two-valued (may return
> 'true' or 'false'), and this is not the case for the mentioned set
> of rules. The set of rules appropriate for equality in FL is
> in fact the rules given for == in p.5.
> * Contrary to the case of ==, the equality =, as described in p. 5,
> can only return the value 'true'. Therefore, it is not correct to speak
> about
> "two kinds of equalities which have identical meaning on
> ground expressions". In fact, = could be 'defined' by means of
> the set of rules in p.4 (although the implementation would
> not follow the 'normal' mechanism of evaluation, because the generation
> of infinite ground solutions is replaced by unification).

You are completely right and raised a subtle point.
Actually, I am not happy with the current description
and I am looking for a better one. Maybe a more constrained-oriented
view helps to understand it. The "test equality" == can be considered
as a Boolean function like in Haskell. However, the "unification
equality" = should better be considered as the addition of a constraint
to the current substitution part. In particular, = cannot be
used as a test since it cannot deliver the result value "false".
>From this point of view, it may be better to restrict the
use of = in conditions only (like in logic programming),
but not as an argument to another function (in contrast to ==).
Thus, = could be considered as a language primitive (rather
than a built-in function) to add new constraints on variables.
What do you think?

> * A question: do you think that the report should fix the evaluation
> strategy for = and ==? We think not. For instance, one implementation
> could, for simplicity, evaluate e=e' by reducing e and e' to normal
> form before performing unification (this is the mechanism suggested
> in p. 5). But other implementations could try more sophisticated
> ways for performing unification incrementally. This done so,
> e.g, in our implementations (TOY, BabLog).

This is a wrong formulation in the report. In our prototype,
we use the same implementation as in Toy or Bablog, and I intended
exactly this behavior. I am not sure whether we should leave the
evaluation strategy open since otherwise the termination behavior
of identical programs maybe different w.r.t. different
implementations.

> That's all for the moment for the technical stuff. In the organizative
> level of the Curry iniciative, we think that it would be convenient:
>
> 1. To identify the different institutions o groups which want
> to be involved in the Curry initiative.
> 2. To have a representant of each group.
> 3. To start thinking about possible mechanisms for taking decisions.

We decided in Dagstuhl that, in principle, the discussion on
Curry is open to every interested person. I hope that the
discussion will be constructive so that we will find a
good agreement on the core language. There was also an agreement
that the core language should be as small as possible, i.e.,
particular features and new developments should first be considered
as extensions of the core. If almost everybody is convinced
that the addition of some feature is necessary, it should
be included in a further version. First of all, it is more
important to find an agreement on the basic core.
However, if you think that a more formal structure is
necessary, I am open to proposals.

Best regards,

Michael
Received on Fri Jan 24 1997 - 17:55:41 CET

This archive was generated by hypermail 2.3.0 : Mon Sep 16 2019 - 07:15:04 CEST