How lazy is lazy? 
Author Message
 How lazy is lazy?

I think I understand "strict" functional languages: the arguments
are simply evaluated before the function is called.  However, I'm
having some trouble seeing exactly how long the evaluation of
arguments should be delayed in a lazy language.  The FAQ simply
says that the arguments are not evaluated until their value
is "required", but it seems to me that this is not sufficiently
concrete.

For example, suppose I define a function which just calls the "car"
function; that is, it returns the first element of a given list.
Then I call my new function (let's name it "head") from within
some other function ("goober"), passing head one of goober's own
arguments.

Looking at the body of goober, it appears that its argument
should be evaluated before the call to head, since it is
required to satisfy the call to head.  Looking closer, however,
it seems that the argument still need not be completely
evaluated; only enough that the car function can determine
the argument's first element.

So I'm a bit confused as to just how lazy a lazy language can be.
Clearly, if it's too lazy, it never calculates anything.  :-)
Is there a simple rule like that for strict languages?

Thanks.

--
--
Patrick Doyle                      TINCC



Mon, 27 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

Quote:

>I think I understand "strict" functional languages: the arguments
>are simply evaluated before the function is called.  However, I'm
>having some trouble seeing exactly how long the evaluation of
>arguments should be delayed in a lazy language.  The FAQ simply
>says that the arguments are not evaluated until their value
>is "required", but it seems to me that this is not sufficiently
>concrete.

A value is "required" when you do a test on that value,
e.g. the condition of an if-then-else is required,
and if you use pattern matching, then those parts of the
value which you match against are required.
Also evaluating many primitive functions, such as "+" on integers,
will require evaluating the values of their arguments.

If you write

        head (x:xs) = x

then evaluating `head ys' does not require evaluating the tail of ys.
Indeed, if you write

        nonempty (x:xs) = True

then evaluating `nonempty ys' does not require evaluating either the
head or tail of ys; it only requires evaluating the top-level constructor,
to see whether it is nil or cons.

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"



Tue, 28 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

Quote:

> If you write

>         head (x:xs) = x

> then evaluating `head ys' does not require evaluating the tail of ys.
> Indeed, if you write

>         nonempty (x:xs) = True

> then evaluating `nonempty ys' does not require evaluating either the
> head or tail of ys; it only requires evaluating the top-level constructor,
> to see whether it is nil or cons.

But this is true for your first example as well, isn't it? The value
returned is left unevaluated.

        - Andreas

--

:: be declarative. be functional. just be. ::



Tue, 28 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

Quote:

>A value is "required" when you do a test on that value,
>e.g. the condition of an if-then-else is required,
>and if you use pattern matching, then those parts of the
>value which you match against are required.
>Also evaluating many primitive functions, such as "+" on integers,
>will require evaluating the values of their arguments.

>If you write

>    head (x:xs) = x

>then evaluating `head ys' does not require evaluating the tail of ys.

Yes, but that begs the question: when is "head (x:xs) = x" evaluated at
all?

The impression I get is that a lazy language like Haskell basically just
"executes" a program by evaluating the main "do" block sequentially, and
building up lazy evaluation trees for everything called by it, evaluating
only as much of those trees as is needed to generate whatever result is
needed by the main "do" block. Is this correct?

I'm also not quite sure how strict statements within lazy functions are
handled -- say, if I write a function that happens to call foldl', which is
strict. Is the call to foldl' evaluated only if and when the enclosing
function is evaluated?

Craig



Tue, 28 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

Quote:

>>If you write

>>       head (x:xs) = x

>>then evaluating `head ys' does not require evaluating the tail of ys.

>Yes, but that begs the question: when is "head (x:xs) = x" evaluated at
>all?

>The impression I get is that a lazy language like Haskell basically just
>"executes" a program by evaluating the main "do" block sequentially, and
>building up lazy evaluation trees for everything called by it, evaluating
>only as much of those trees as is needed to generate whatever result is
>needed by the main "do" block. Is this correct?

>I'm also not quite sure how strict statements within lazy functions are
>handled -- say, if I write a function that happens to call foldl', which is
>strict. Is the call to foldl' evaluated only if and when the enclosing
>function is evaluated?

There are various ways of describing what is required, here's a rather
old-fashioned one that used to work well for students.

A program is an expression to be evaluated (ignore all the monads and stuff
for the purpose of worrying about strictness/laziness) - and the program is
finished when it has succeeded in displaying the value of that expresion.
Calling the program "demands" the value of the expression.
To evaluate the expression, you have to evaluate the outermost function
call(s) (if any), and they may need to partially evaluate some of their
arguments to discover whether there is a pattern match.  For each argument
that needs matching, the "demand" is propogated to that argument. So we have
to evaluate that argument until it has a constructor as its outermost
component.  If that constructor matches the pattern, and the pattern is deeper
than that constructor, we have to propogate demand to arguments of the
constructor to see if the next level of match is ok - and so on, until either
we have a match, in which case we can rewrite the expression or until we know
this pattern doesn't match and have to try another pattern.  
When we've rewritten the top level expression, we can look and see if it still
has functions at the outermost level: if it has, it still isn't adequately
evaluated and we have to go through the same process again.  If it hasn't, the
program has been evaluated to an expression in head normal form, which is
either a single constructor (like an integer, if that's one of our fundamental
types, for example, or NIL if it's a list expression) or a constructor with
some arguments; as we want to display the whole value of the expression, we
propogate demand to each of those arguments - and so the process goes on,
until we have nothing but constructors left.

Unless demand gets propagated to a function, none of its arguments are ever
evaluated so it doesn't matter whether the function is strict or not. If
demand is propogated to its function, what happens to its arguments depends on
its strictness properties.

A function may be a function which is strict up to head normal form in all its
arguments (like head or tail on lists); it may be a function which is strict
to complete normal form in all its arguments; or it may be strict to different
degrees in different arguments (there are no non-trivial functions that are
lazy in all their arguments - only constant functions and the identity).  
Often a lazy language will allow the programmer to park annotations in
function declarations to specify that it should be strict (to one degree or
the other) in certain arguments.  Often the compiler can deduce whether a
function is strict (completely, or to head normal form) in some of its
arguments, by looking at the body of the function. So sometimes the programme
will go off and evaluate arguments before demand is propagated to them
according to the description given above, so that the lazy evaluation tree you
described is short circuited when the compiler knows it is safe to do so -
that tree is just an implementation technique (one of several possible) not
the definition of laziness.

An alternative description of laziness can be given in terms of combinators:
the program is a combinator string. If the leftmost combinator is reducible,
that reduction is carried out and we look again at whatever is now leftmost;
otherwise, if any of the arguments of that leftmost combinator is reducible,
one of those reductions (can be selected at random, or leftmost argument, or
rightmost argument, or any other way you choose) is carried out and then we
go back to the outer level; when neither the outermost combinator nor any of
its arguments heads a redex, the next level in is considered; and so on.



Tue, 28 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

Quote:


>> If you write

>>         head (x:xs) = x

>> then evaluating `head ys' does not require evaluating the tail of ys.
>> Indeed, if you write

>>         nonempty (x:xs) = True

>> then evaluating `nonempty ys' does not require evaluating either the
>> head or tail of ys; it only requires evaluating the top-level constructor,
>> to see whether it is nil or cons.

>But this is true for your first example as well, isn't it? The value
>returned is left unevaluated.

No, if you have to evaluate `head (x:xs)', then you will have to evaluate `x'.

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"



Wed, 29 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

Quote:

>The impression I get is that a lazy language like Haskell basically just
>"executes" a program by evaluating the main "do" block sequentially, and
>building up lazy evaluation trees for everything called by it, evaluating
>only as much of those trees as is needed to generate whatever result is
>needed by the main "do" block. Is this correct?

Yes.

Quote:
>I'm also not quite sure how strict statements within lazy functions are
>handled -- say, if I write a function that happens to call foldl', which is
>strict. Is the call to foldl' evaluated only if and when the enclosing
>function is evaluated?

No, the call to foldl' will be evaluated if and when its return value is
needed.

The thing that is special about a strict function is that
evaluating the function result always requires evaluating the argument.
This means that the argument to a strict function can be evaluated when
the function is called, rather than waiting until when the function
demands the value of that argument.

For example, suppose you have the following code,

        foo c f x1 x2 l l2 = if c then x else x2
                where   ...
                        x0 = sum l2
                        x = (foldl' f x0 l)
                        ...

If you call `foo False ...', then the call to foldl' will not be evaluated,
since `x' is not needed.  If you call `foo True ...', then `x' is needed,
and so the call to fold' will be evaluated; because foldl' is strict,
the compiler can evaluate x0 before calling foldl' rather than having
to allocate a closure for the expression `sum l2' and pass the
closure to foldl' so that foldl' could evaluate it if needed.

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"



Wed, 29 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

: >>
: >> If you write
: >>
: >>         head (x:xs) = x
: >>
: >> then evaluating `head ys' does not require evaluating the tail of ys.
: >> Indeed, if you write
: >>
: >>         nonempty (x:xs) = True
: >>
: >> then evaluating `nonempty ys' does not require evaluating either the
: >> head or tail of ys; it only requires evaluating the top-level constructor,
: >> to see whether it is nil or cons.
: >
: >But this is true for your first example as well, isn't it? The value
: >returned is left unevaluated.

: No, if you have to evaluate `head (x:xs)', then you will have to evaluate `x'.

This seems rather strange. It shouldn't matter what x is, all that matters
is that the argument list is non-null. For example,

       head [(1+2),4]
    => head ((1+2) : [4])
    => (1+2)

If you try this in hugs, and compare the reduction counts, hugs only
seems to evaluate (1+2) if it needs to show it. Thus:

    zap :: t -> Int
    zap _ = 0

    zap (head [(1+2),4])
    (9 reductions, 9 cells)

    zap (head [3,4])
    (9 reductions, 9 cells)

Perhaps we are confusing what we mean by `evaluate' ?

Regards,
Andrew



Fri, 31 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

Quote:

> This seems rather strange. It shouldn't matter what x is, all that matters
> is that the argument list is non-null. For example,

>        head [(1+2),4]
>     => head ((1+2) : [4])
>     => (1+2)

Which then evaluates to 3.  Think of it like this: if the value of "head
(x:xs)" is demanded, then the value of "x" will be demanded.

Quote:
> If you try this in hugs, and compare the reduction counts, hugs only
> seems to evaluate (1+2) if it needs to show it.

Right; the initial demand is always "show the value of the main expression".

Quote:
> Thus:

>     zap :: t -> Int
>     zap _ = 0

>     zap (head [(1+2),4])
>     (9 reductions, 9 cells)

>     zap (head [3,4])
>     (9 reductions, 9 cells)

zap ignores its argument; head is not even called in these cases.  That's why
the count is the same.  Try any other argument; you should still get 9
reductions.  In other words, to evaluate "zap M" you never need to evaluate
"M".

Cheers,

Andy



Fri, 31 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

: > This seems rather strange. It shouldn't matter what x is, all that matters
: > is that the argument list is non-null. For example,
: >
: >        head [(1+2),4]
: >     => head ((1+2) : [4])
: >     => (1+2)

: Which then evaluates to 3.  Think of it like this: if the value of "head
: (x:xs)" is demanded, then the value of "x" will be demanded.

But is this in fact true? I admit I really fluffed it with my _zap_ example,
which had nothing to do with the crux of the issue. However, I'll try again.
So, why should you need to evaluate _x_ if you are only going to, eg, cons it
it to another list, vis:

    transfer :: ([t],[t]) -> ([t],[t])



        = transfer (tail list, (head list):ys)  -- Using functions.
    --  = transfer (xs, x:ys)                   -- Using pattern matching.

So in this contrived example, _head_ takes the first element of _list_
in order to cons it to ys. At no stage do we need to know what the
value returned by _head_ actually evaluates to. We can remove the
actual _head_ function via pattern matching ourselves and still get the
_x_, which we obviously need not evaluate.

Is there any way to get hugs (or something else) to show the intermediate
stages of processing? I guess it is all hidden in the guts of the GRS and,
as such, hard to translate back into Haskell. But it would be good to be
able to "single-step" or set "breakpoints" at, eg, the base case.

Thanks,
Andrew



Fri, 31 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

Quote:

> : Which then evaluates to 3.  Think of it like this: if the value of "head
> : (x:xs)" is demanded, then the value of "x" will be demanded.

> But is this in fact true?

Yes, absolutely.  See below.

Quote:
>     transfer :: ([t],[t]) -> ([t],[t])



>         = transfer (tail list, (head list):ys)  -- Using functions.
>     --  = transfer (xs, x:ys)                   -- Using pattern matching.

> So in this contrived example, _head_ takes the first element of _list_
> in order to cons it to ys. At no stage do we need to know what the
> value returned by _head_ actually evaluates to. We can remove the
> actual _head_ function via pattern matching ourselves and still get the
> _x_, which we obviously need not evaluate.

If transfer is called it will return a pair, in doing so it will
not have evaluated `tail list', nor `head list'.
Say that you take the second component of this pair, you will
the get a cons back, `head list' will still not have been evaluated.
If you now inspect the head of that cons (i.e. the expression
`head list') the `head list' expression will be evaluated.
And it will be evaluated to whnf since you asked for the value.

So to repeat what Andy Moran said, if a function is called it should
evaluate its result to whnf since the only reason you called the function
in the first place was that you needed the result.

--

        -- Lennart Augustsson
[This non-signature is unintentionally not left unblank.]



Fri, 31 Aug 2001 03:00:00 GMT  
 How lazy is lazy?



 >
 >: > This seems rather strange. It shouldn't matter what x is, all that matters
 >: > is that the argument list is non-null. For example,
 >: >
 >: >        head [(1+2),4]
 >: >     => head ((1+2) : [4])
 >: >     => (1+2)
 >
 >: Which then evaluates to 3.  Think of it like this: if the value of "head
 >: (x:xs)" is demanded, then the value of "x" will be demanded.
 >
 >But is this in fact true?

Yes.

 >I admit I really fluffed it with my _zap_ example,
 >which had nothing to do with the crux of the issue. However, I'll try again.
 >So, why should you need to evaluate _x_ if you are only going to, eg, cons it
 >it to another list, vis:
 >
 >    transfer :: ([t],[t]) -> ([t],[t])
 >

 >

 >        = transfer (tail list, (head list):ys)  -- Using functions.
 >    --  = transfer (xs, x:ys)                   -- Using pattern matching.

This example is incomplete.  What's the main function?
What's the top-level expression which we are trying to evaluate?
If you're trying to determine what will be evaluated, that
is crucial information.

 >So in this contrived example, _head_ takes the first element of _list_
 >in order to cons it to ys. At no stage do we need to know what the
 >value returned by _head_ actually evaluates to. We can remove the
 >actual _head_ function via pattern matching ourselves and still get the
 >_x_, which we obviously need not evaluate.

That transformation is valid.  But it is not clear whether or not
`x' needs to be evaluated -- that depends on how `transfer' is called.
It remains true that (with the second definition) `x' needs to be evaluated
iff (with the first definition) `(head list)' needs to be evaluated.

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"



Fri, 31 Aug 2001 03:00:00 GMT  
 How lazy is lazy?

Quote:

>So I'm a bit confused as to just how lazy a lazy language can be.
>Clearly, if it's too lazy, it never calculates anything.  :-)
>Is there a simple rule like that for strict languages?

After posting this, I received a response in email which was a
very nice explanation of WHNF.  I thought it was also posted
to the newsgroup, so I was saving my response for when it
appeared here; unfortunately, it seems never to have arrived.

Whomever sent me that great response: would you mind either
posting it here, or resending it to me?  I'd like to keep
a copy of it, as I didn't read it as thoroughly as I should
have (since I thought I'd see it again on the newsgroup :-).

Thanks.  (And sorry to the rest of you for the waste of
bandwidth!)

--
--
Patrick Doyle



Fri, 31 Aug 2001 03:00:00 GMT  
 
 [ 13 post ] 

 Relevant Pages 

1. lazy.py 0.7 - Lazy expressions and datastructures

2. lazy (non-eager) Scheme ??? (lazy, but eager me)

3. lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

4. lazy.py 0.7 - Lazy expressions and datastructures

5. lazy (non-eager) Scheme ??? (lazy, but eager me)

6. Lazy DBResultSet in ListView?

7. Art and all that Jazz: they are hating before lazy, without sad, alongside wet balls

8. Lazy evaluation?

9. Lazy Accessor Questions

10. we're feeling quite lazy today...

11. we're feeling quite lazy today...

12. Is Topspeed Personel ashamed or just very lazy ????

 

 
Powered by phpBB® Forum Software