Here is just another proposal for a language change in Curry, that grew
out of a discussion with Herbert. We propose to add a new evaluation
annotation, choice, to define functions that use committed choice as
their evaluation strategy.
E.g. the non-deterministic merge function could be implemented as
merge eval choice
merge [] l2 = l2
merge l1 [] = l1
merge (e:r) l2 = e : merge r l2
merge l1 (e:r) = e : merge l1 r
Informally the semantics of a function defined with the choice
annotation would be as follows:
For every argument that is demanded in one the patterns, check if the
argument is in WHNF and not an unbound variable. If any of the rules
can be selected based on these arguments, select it. (If more than one
rule can be selected one will be chosen randomly.)
Otherwise, if any of the demanded arguments is not in WHNF, evaluate
it to WHNF and then try to select a rule, again.
If there are no demanded arguments, which are not in WHNF, but there
are uninstantiated variables in demanded positions, suspend until (at
least) one of these variables is instantiated.
In any other case the evaluation fails.
The reason for making this proposal is that, IMHO, the current choice
expression using constraints is unsatisfactory. It confuses the
(desired) pattern matching of arguments with (undesired) solving of a
constraint. Consider the merge function again. Quoting the current
report its definition using choice is as follows:
merge l1 l2 =
choice {l1=[]} -> l2
{l2=[]} -> l1
{l1=e:r} -> e:merge r l2 where e,r free
{l2=e:r} -> e:merge l1 r where e,r free
Because equality is strict in Curry, this function is flawed for
infinite lists. E.g. the call
length (take 10 (merge (repeat 1) (repeat 2)))
where repeat x = x : repeat x
will enter an infinite loop, which is odd for a *lazy* functional
logic language. The result of merging two infinite lists
non-deterministically should be just another infinite list and it
should be perfectly possible to take the first ten elements of such a
list and compute the length of that list.
I do not see any way, how this could be achieved using the choice
expression. (Except if you are going to tell me that = should have
another meaning, viz. unification, when it occurs in a constraint that
is evaluated as part of choice expression.)
Any comments?
Wolfgang
--
Wolfgang Lux Phone: +49-251-83-38263
Institut fuer Wirtschaftinformatik FAX: +49-251-83-38259
Universitaet Muenster Email: lux_at_helios.uni-muenster.de
Received on Di Okt 27 1998 - 06:42:00 CET