Re: Local pattern declarations in Curry

From: Michael Hanus <hanus_at_informatik.rwth-aachen.de>
Date: Fri, 13 Nov 1998 16:35:25 +0100

Herbert Kuchen wrote:
> I think, we have (at least) four options:
> ...
> 2) transform out nullary functions (such that the
> existing theory can used)
> 3) adopt Michael's original proposal
> (no sharing of values for locally defined nullary functions)
> 4) Michael's last proposal
> locally defined nullary functions are handled like variables
> (i.e. their values are shared); locally defined recursive
> nullary functions are forbidden
>
> I will comment below on possibilities 2) and 4). Moreover, I would
> like to remember that 3) leads to some surprising behaviour, e.g. in
>
> psort xs | sorted ys = ys where ys = permut xs
>
> Honestly, who was able to spot immediately that this
> definition does not work as expected?!

Agreed, since one usually considers local declarations
of the form "where x = ..." as denoting some local variable
rather than a function. On the other hand, one considers
all global definitions as functions (rather than variables,
since a functional logic program is a set of function definitions)
and thus the "nullary function = variable" approach might
also lead to surprising results. Maybe this is an argument for
possibility 4).

> Thus, the "top level" definitions would be handled just
> like local definitions as pointed out in my last email.
>
> > coin = 0
> > coin = 1
> > ...
> > f xs = ...coin...
> > g ys = ...coin...
> > ...
>
> For the example, this means:
> (assuming the goal is f Xs)
>
> dummy_lhs = h xs
> h xs = f1 xs
> h xs = f2 xs
> f1 xs = ... coin1 ...
> f2 xs= ... coin2...
> g1 xs= ... coin1...
> g2 xs= ... coin2 ...
> coin1 = 0
> coin2 = 1

But this must be done for each 0-ary function which means that
the code must be duplicated for each 0-ary function which
leads to a dramatic code explosion in larger programs.

> Note that this just serves to transform the program to the
> kernel language in order to explain its meaning based on the
> existing theory (i.e. mainly the ESOP'96 paper). It does
> NOT imply that Curry programs have to implemented
> like this. A possible implementation could preserve
> the nesting and avoid the code explosion.

Right, but I am thinking also of other tools than compilers
like program transformation systems, partial evaluators,
abstract interpreters and so on. All such tools have then
two options:

- Consider the special treatment of 0-ary functions: such
  special treatments makes these tools often much more complicated.

- Consider the transformation: this makes the tools often much
  more inefficient due to the code explosion.

Therefore, I think that the sharing of 0-ary functions is
ok for local declarations (since the code explosion caused by
the transformation is usually rather limited) but not for
global functions. Thus, I am very much in favor to your
recent proposal:

> to 4) this proposal avoids the surprising behaviour in the
> permutation sort example, but restricts the language.
> Unfortunately, it also destroys the compatibility with
> Haskell. In order to recover it, one could allow
> deterministic locally defined recursive
> nullary functions (and handle them by lambda
> lifting). Thus, only non-deterministic locally defined
> recursive nullary functions remain excluded.

Yes, maybe one could specify this behavior by distinguishing
the recursive and non-recursive cases (like in the Haskell report).
If the locally introduced variables are not recursively used,
one could specify the meaning by a simple transformation
(adding arguments), and the general recursive case is
specified by your more complicated transformation
(which will be seldom used). Then there is no distinction
between deterministic and non-deterministic local functions,
which is quite reasonable.

Best regards,

Michael
Received on Fr Nov 13 1998 - 16:39:00 CET