Operational behaviour of Clean Programs...

John van Groningen johnvg@cs.kun.nl
Tue, 18 Jul 2000 15:11:26 +0200


>I am just beginning to delve into the graph-rewriting operational
>semantics of Clean, and I would like to have some explanations about the
>following :
>
>     How is it that :
>          ...
>          fibonaci =3D [ 1,2:zipWith (+) fibonaci ( tl fibonaci ) ]
>
>          where
>            zipWith o xl yl =3D zipWitho xl yl
>
>            where
>              zipWitho [x:xl] [y:yl] =3D [o x y:zipWitho xl yl ]
>              zipWitho []     []     =3D []
>
>     seems to be running in exponential space and time, while :

'fibonaci' is defined as a function (with zero arguments). The result of=
 this function is calculated each time this function is called.

>
>          fibonaci =3D [ 1,2:rest fibonaci ]
>          where
>            rest f =3D zipWith (+) f ( tail f )
>            ...
>     seems to be running in linear time and space ?

In this case the function 'rest' is called with the result of the 'fibonaci'=
 function, so both occurences of 'f' refer to this result. However the=
 'fibonaci' function is still evaluated more than once.

>This is of some concern to me because the first program is running in
>linear time under the Haskell interpreter Hugs98 without any problem.

In Haskell top level functions with no arguments are treated as CAFs, so=
 that the function is evaluated at most once. In Clean these functions are=
 by default treated as ordinary functions, but can also be defined as a CAF,=
 by writing =3D: instead of =3D in the function definition.

So if you define:

          fibonaci =3D: [ 1,2:zipWith (+) fibonaci ( tl fibonaci ) ]

The result of 'fibonaci' is remembered after the first time 'fibonaci' is=
 evaluated, and subsequent calls of 'fibonaci' will yield this first result=
 (without recomputing).

Note that the memory used to store the result of such a function will never=
 be freed by the garbage collecter, and that the type of the function's=
 result cannot be a unique (*) type.

Another way to obtain a linear time and space version is to define

          fibonaci =3D fibonaci
                where
                        fibonaci =3D [ 1,2:zipWith (+) fibonaci ( tl=
 fibonaci ) ]

In this case the local definition of 'fibonaci' defines a value, and not a=
 function. A local function with zero arguments can be defined by writing =
=3D> instead of =3D .

Regards,

John van Groningen