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