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

From: Paco Lopez Fraguas <fraguas_at_eucmax.sim.ucm.es>

Date: Mon, 03 Feb 1997 11:53:23 +0100

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.

Date: Mon, 03 Feb 1997 11:53:23 +0100

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.

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.

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

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.

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

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.esReceived on Mo Feb 03 1997 - 12:17:40 CET

*
This archive was generated by hypermail 2.3.0
: Mi Jul 28 2021 - 07:15:02 CEST
*