Re: Local pattern declarations in Curry

From: Herbert Kuchen <kuchen_at_uni-muenster.de>
Date: Tue, 10 Nov 1998 14:40:29 +0000

Michael Hanus wrote:

> The proposed solution:
> ======================
> Introduce a syntactic distinction between the local declaration
> of a variable (pattern) or a function:
> ...
>
> An example:
> ===========
> The following example shows the application of the local pattern
> definition to define a demand-driven version of permutation sort nicely:
>
> -- Non-deterministic insertion in a list with local choose function
> insert x [] = [x]
> insert x (y:ys) = choose (x:y:ys) (y:insert x ys)
> where choose x _ = x
> choose _ y = y
>
> -- Non-deterministic generation of permutations
> permute [] = []
> permute (x:xs) = insert x (permute xs)
>
> -- Permutation sort with a lazy (demand-driven) generation of permutations:
> psort xs | sorted ys = ys where ys <- permute xs
>
> ("sorted ys" delivers True if ys is a sorted sequence).
> Note that the alternative definition
>
> psort xs | sorted ys = ys where ys = permut xs
>
> computes all possible permutations since the occurrences of ys
> are not shared.

Dear Michael,

the Münster group is not happy with this proposal.
One major design goal for a language is that it should
be fool safe and that it should not enable subtle
errors as in

psort xs | sorted ys = ys where ys = permut xs

The behavior in this case seems to be counter-intuitive.

Thus, we suggest the following alternative:

0-ary functions are treated like variables, i.e. via
sharing. This would avoid the above strange behaviour.
As far as we can see, non-deterministic nullary functions
are rarely useful in practice, and in the few cases where one
would really like to have them (with a "non-sharing-behaviour"),
one could instead use (e.g.) a unary function
with a dummy argument.

A small problem is that, in order to enable sharing, the computed
value of a nullary function has to be stored until it is clear that it is
no longer needed. But this not worse than in Haskell, and the
corresponding analysis techniques can be re-used in Curry.
Moreover, your proposal suffers from the same problem (if the
"pattern syntax" is used).

Cheers,

Herbert and Wolfgang
Received on Di Nov 10 1998 - 14:48:00 CET