Re: Local pattern declarations in Curry

From: Herbert Kuchen <kuchen_at_uni-muenster.de>
Date: Wed, 11 Nov 1998 12:19:35 +0000

Michael Hanus wrote:

> ...This means that local definitions are lifted
> into global ones. During this lifting process, arguments
> might be added to local functions so that the arity is changed.
> For instance, consider the following definition:
>
> f x = g xs where xs = x:xs
>
> By lifting, we obtain the following global function definitions:
>
> f x = g (xs x)
> xs x = x:(xs x)
>
> Now, the originally 0-ary function xs has been transformed into
> a function with one argument. Following your proposal, a programmer
> might think that xs is shared while actually it is not after
> the transformation. In my opinion, this destroys the "fool safeness".

Of course, simple lambda lifting is no longer possible.

One solution would be to preserve the nesting and compile
the program directly to some abstract machine code.
This is easy for us, since we are implementing Curry from
scratch, but difficult, if you are aiming for a
translation to Prolog. (Moreover, the direct translation
is more efficient!)

Another solution would be to use a more sophisticated
translation scheme. For non-recursive nullary functions,
one could just use the scheme proposed for the treatment
of patterns.

 In the following, I'll try to sketch a scheme for the recursive
case. Let's first make the example a bit more complicated,
since xs in the above example is deterministic:

f x = g xs where xs = x:xs
                  xs = []

With our proposed semantics,
possible values for xs are:

1) an infinite list, where all elements are x, i.e.
   x:x:x:x:...
2) []

but NOT: x:x:...:x:[] !!!

This could be translated as follows
(here without optimizations):

f x = h x
h x = g (xs1 x)
h x = g (xs2 x)
xs1 x = x:(xs1 x)
xs2 x = []

Generally speaking, an auxilliary function h is introduced,
which is responsible for choosing non-deterministically
one alternative. In fact, h could be inlined and it is
mainly used here for clarity. For each alternative, there is
separate (deterministic) code.

As far as I can see, this scheme works. In the case of
mutually recursive nullary functions (who
really wants to have those???), there would be
a code explosion (about which I don't care, since
this does not occur in practice):

f x = g xs ys where xs = x:ys
                    xs = []
                    ys = (x+1):xs
                    ys = (x+2):xs

could be translated to:

f x = h x

h x = g (xs11 x) (ys11 x)
h x = g (xs12 x) (ys12 x)
h x = g (xs21 x) (ys21 x)
h x = g (xs22 x) (ys22 x)

xs11 x = x:(ys11 x)
xs12 x = x:(ys12 x)
xs21 x = []
xs22 x = []

ys11 x = (x+1):(xs11 x)
ys12 x = (x+2):(xs12 x)
ys21 x = (x+1):(xs21 x)
ys22 x = (x+2):(xs22 x)

(of course, this can be easily optimized)

Cheers,

Herbert
Received on Mi Nov 11 1998 - 12:28:00 CET