- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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 Wed Nov 11 1998 - 12:28:00 CET

Date: Wed, 11 Nov 1998 12:19:35 +0000

Michael Hanus wrote:

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 Wed Nov 11 1998 - 12:28:00 CET

*
This archive was generated by hypermail 2.3.0
: Wed Sep 18 2019 - 07:15:04 CEST
*