Re: prelude extension proposal

From: Bernd Brassel <bbr_at_informatik.uni-kiel.de>
Date: Fri, 14 Oct 2005 11:34:42 +0200

Wolfgang Lux wrote:
> It is not a question of
> sweeping problems under the rug, but a function like allValuesOf
> is simply nonsense in an implementation that is based on weak
> encapsulation! Just look at Bernd's example again. In MCC, which
> uses weak encapsulation, the expression allValuesOf coin
> non-deterministically computes the solutions [0] and [1] (not 0 and 1
> as Bernd incorrectly wrote). So this function does not compute all
> values as its name suggests, but non-deterministically chooses one
> of the values. In fact, allValuesOf is equal to \e -> [e] in any
> implementation based on weak encapsulation.

Yes, this is exactly the point, and much better (and correctly - sorry!)
stated. We could of course explain these things to the user in the
comments, although it might get somewhat awkward. Nevertheless, I think
Sergio's point is very important as well:

> There is another reason for having this function defined in an
> easily accessible place. In an introductory lecture on FLP, I
> explain non-determinism as a feature that allows the programmer to
> both choose an arbitrary value that will likely be constrained
> later and easily compute a set (list, multiset) of values, which
> could be ranked, filtered or further processed. Using allValuesOf
> instead of findall makes this introductory lecture easier and more
> effective

I also think that allValuesOf is much easier to comprehend than the
findall concept. But there could be an equivalent for allValuesOf in an
implementation based on weak encapsulation, could there not? This would
then be a primitive and could not be defined using findall. There are of
course problems defining a denotational semantics for this function, as
Wolfgang correctly stated:

> IMHO, the whole problem is based on an misunderstanding of the
> underlying lazy evaluation semantics of Curry. Note that the
> semantics of a call-by-need calculus (i.e. non-strict evaluation
> with sharing) in a language with non-determinism is much closer to
> a call-by-value calculus than to a call-by-name calculus (i.e.,
> non-strict evaluation without sharing). In fact, for expressions
> that do not involve bottom, a call-by-need and a call-by-value
> calculus will compute exactly the same results. All of this simply
> applies to a hypothetical allValuesOf function as well. When this
> function is applied to some argument, the value of the argument
> is already fixed -- though not yet evaluated -- so there is nothing
> to encapsulate or to choose from in the body of the definition of
> allValuesOf. And please note that the previous sentence is just
> a paraphrase of the description of call-time choice in Sect. 2.3.1
> of the Curry report.

This section and esp. the contained reference to the denotational
semantics are indeed incompatible with the intended behaviour of
allValuesOf. But the Curry-Report does, as far as I know, not state much
about the denotational semantics of encapsulation. It rather talks about
why encapsulation is needed, esp. for use within I/O actions and how the
search operators should behave operationally. Unfortunately, weak
encapsulation is not much use in ensuring determinism and therefore I
would prefer in these situations something which can only be defined
operationally over not being able to do what is needed. The semantical
problems are the very reason we put getSearchTree in the I/O-Monad.

_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Fri Oct 14 2005 - 12:23:00 CEST

This archive was generated by hypermail 2.3.0 : Mon Nov 11 2019 - 07:15:06 CET