- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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 Fr Jan 24 1997 - 17:55:41 CET

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.

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.

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

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?

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.

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 Fr Jan 24 1997 - 17:55:41 CET

*
This archive was generated by hypermail 2.3.0
: Mi Sep 30 2020 - 07:15:03 CEST
*