Michael's proposal is very reasonable and accommodating. I
favor it, though I am a bit wary of select. I am not familiar
with indeterminism. The semantics, as I understand it, is
like choose followed by a cut a la Prolog. Why should we
provide this cut for choose and not for other or all the
functions of a program?
I think that it boils down to the intuition of
non-determinism. My intuition is that any result of a
non-determinism computation carries the same information of
any other. Hence, when you get one result theere is no point
in getting any other. E.g., if you print the elements of a
finite set, you can print them in different orders, but one
order does not tell you anything more than any other order.
Hence, a computation should give you only one result (if you
want all of them use the set function). But giving you only
one result before the computation is finished conflicts with
the overall approach of current interpreter and destroys
completeness.
Sergio
On Thu, 24 Jan 2013, at 17:13, Michael Hanus <mh_at_informatik.uni-kiel.de> wrote:
> On 01/23/2013 02:02 PM, Sebastian Fischer wrote:
> > There seems to be a tension that has not been mentioned yet in the
> > discussion. Lists support the implementation of other evaluation-order
> > dependent constructs such as committed choice. I could not define the
> > function `once` in Evaluator.lcurry with the "pure" interface on sets
> > that you describe (and is provided by the Values type in the
> > SetFunctions module). Values can be turned into a list by sorting them
> > but it seems counter productive to sort all values in order to commit to
> > one and sorting does not terminate for infinite lists.
>
> So maybe one could distinguish between a nondeterministic operation
>
> choose :: Values a -> (a,Values a)
>
> that chooses some element and returns the remaining ones from a set
> of values (following Sergio's proposal) and an *indeterministic*
> operation
>
> select :: Values a -> (a,Values a)
>
> that commits to some element and returns the remaining ones.
> Hence, if we define chooseElem by
>
> chooseElem x = fst (choose x)
>
> then the set function chooseElem_set of chooseElem is the identity
> on value sets. The use of the indeterministic operation "select"
> may destroy referential transparency if there is more than one
> value in the set.
>
> > Maybe we should aim for a pure approach (like set functions) on one hand
> > and a more powerful approach that allows more control (like commited
> > choice or heuristics such as findbest based on try) on the other.
>
> In the KiCS2 implementation of set functions, there are some
> possibilities for this. Set functions are parameterized over
> the search strategy to be used, e.g., one can use depth-first
> search or breadth-first search to construct the sets.
> This is useful to test various search strategies and might
> influence the result of emptiness tests (e.g., an emptiness
> test might loop with dfs but could terminate with bfs)
> and could be also interesting when an indeterministic select
> operation is applied.
>
> Best regards,
>
> Michael
> _______________________________________________
> curry mailing list
> curry_at_lists.RWTH-Aachen.DE
> http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Sa Jan 26 2013 - 17:04:37 CET