[Caml-list] laziness

[Caml-list] laziness

[skaller]

Since I've been fiddling with various optimisations in
my own compiler, I've become quite curious about
laziness and its relation to both performance and semantic
guarrantees.

As motivation consider:

	let f c a b = if c then a else b

As I understand it Ocaml will handle a call

	f c' a' b'

by evaluating f,c',a',b' in some order then
applying f to c' a' b' -- eager evaluation.
However if the call is *inlined* to get

	if c' then a' else b'

then perhaps a' or b' will never be evaluated.

[As I understand it, inlining is substitution aka
normal order evaluation for lambda terms; 
that is, a lazy evaluation strategy.]

In particular my 'impression' that ocaml evaluates
function arguments eagerly would be wrong.

It seems that procedural code (which includes 
functional expressions) is actually a way to
specify evaluation order and timing and typically
control flow is used to delay evaluation -- so that
procedural programming is actually quite lazy.

OTOH procedural languages (including Ocaml) also
allow early evaluation.

>From a performance viewpoint, both eager and lazy
evaluation have advantages -- lazy evaluation avoids
gratuitously evaluating a term which the result does
not depend on, whereas eager evaluation can be used to
prevent an evaluation being done twice. Hence procedural
languages like Ocaml can be very fast because you can
hand tune the tradeoffs (also making it harder to 
reason about the outcome .. )

There seems to be some kind of sliding scale like this
for functional code:

C/C++ --> sequence points (functions have side effects)
Ocaml --> looser assurances
Felix --> no side effects but not fully parametric
Haskell --> everything is lazy, immutable, and parametric

So I have two questions:

(1) exactly what does Ocaml guarrantee?

(2) what kind of performance and semantic
tradeoffs are involved with perturbations
on these assurances?

What I'm actually finding at the moment with Felix is that
my optimisation efforts, mainly inlining, are actually
'lazifying' code, and thus involve a change in semantics --
although Felix functions can't have side effects, there
are also procedures which can, and functions may depend
on variables which procedures modify, so that in general
the result of a function does depend on when it is
executed. This effect is also available in Ocaml via
references.

I used to think the difference between lazy and eager
evaluation were minor quirks -- I'm tending to think now
the difference is quite fundamental, eg a purely functional
language is necessarily lazy, because lazy evaluation
is mandatory -- an eager evaluation strategy *requires* 
procedural constructions to provide the laziness, and so
can't work with a purely functional language.

Any comments would be appreciated.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[Marcin 'Qrczak' Kowalczyk]

skaller <skaller@users.sourceforge.net> writes:

> However if the call is *inlined* to get
>
> 	if c' then a' else b'
>
> then perhaps a' or b' will never be evaluated.

No. Inlining is considered an optimization, which implies that it
doesn't change the semantics except when it was not fully specified
in the first place. E.g. the order of evaluation of arguments is
unspecified, so it might be different depending on inlining; but
OCaml does specify that each argument are evaluated exactly once
and inlining doesn't change that.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[skaller]

On Sat, 2004-09-04 at 18:40, Marcin 'Qrczak' Kowalczyk wrote:
> skaller <skaller@users.sourceforge.net> writes:
> 
> > However if the call is *inlined* to get
> >
> > 	if c' then a' else b'
> >
> > then perhaps a' or b' will never be evaluated.
> 
> No. Inlining is considered an optimization, which implies that it
> doesn't change the semantics except when it was not fully specified
> in the first place.

I understand that argument -- but that doesn't mean the
compiler conforms to the specification, nor that the
specification is best.

> E.g. the order of evaluation of arguments is
> unspecified, so it might be different depending on inlining; but
> OCaml does specify that each argument are evaluated exactly once
> and inlining doesn't change that.

Must they be evaluated before the function is called?

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[Richard Jones]

[-- Attachment #1: Type: text/plain, Size: 1099 bytes --]

Should be easy enough to test this:

-------------------------------------------------------------- iftest.ml
let f a b c =
  if c then a else b

let r =
  f (print_endline "function a"; 'a')
    (print_endline "function b"; 'b')
    true;;

Printf.printf "r = %c\n" r
----------------------------------------------------------------------

When compiled with ocamlc and run, this prints:

function b
function a
r = a

When compiled with ocamlopt -inline 99 and run, this prints:

function a
function b
r = a

I examined the assembler output from ocamlopt, and it looks to me like
it's doing inlining and significant optimizations.

So it all works fine, I think.

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
MONOLITH is an advanced framework for writing web applications in C, easier
than using Perl & Java, much faster and smaller, reusable widget-based arch,
database-backed, discussion, chat, calendaring:
http://www.annexia.org/freeware/monolith/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] laziness

[Hartmann Schaffer]

skaller wrote:

>On Sat, 2004-09-04 at 18:40, Marcin 'Qrczak' Kowalczyk wrote:
>  
>
>>skaller <skaller@users.sourceforge.net> writes:
>>
>>    
>>
>>>However if the call is *inlined* to get
>>>
>>>	if c' then a' else b'
>>>
>>>then perhaps a' or b' will never be evaluated.
>>>      
>>>
>>No. Inlining is considered an optimization, which implies that it
>>doesn't change the semantics except when it was not fully specified
>>in the first place.
>>    
>>
>
>I understand that argument -- but that doesn't mean the
>compiler conforms to the specification, nor that the
>specification is best.
>
>  
>
>>E.g. the order of evaluation of arguments is
>>unspecified, so it might be different depending on inlining; but
>>OCaml does specify that each argument are evaluated exactly once
>>and inlining doesn't change that.
>>    
>>
>
>Must they be evaluated before the function is called?
>
>  
>
on the first pass, yes (in order maintain the meaning of the code).  
depending on the optimizer, later optimizations might be able to 
suppress some of the evaluations (e.g. if the value of c' can be 
determined at compile time)

hs

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[Jon Harrop]

On Saturday 04 September 2004 07:30, skaller wrote:
> ...
> by evaluating f,c',a',b' in some order then
> applying f to c' a' b' -- eager evaluation.
> However if the call is *inlined* to get
>
> 	if c' then a' else b'
>
> then perhaps a' or b' will never be evaluated.

That is true for manual inlining but false for automatic inlining by the 
compiler (which must retain obide by the specifications).

Actually, for any single evaluation a' or b' will never be evaluated. ;-)

> In particular my 'impression' that ocaml evaluates
> function arguments eagerly would be wrong.

OCaml evaluates eagerly by default. There are some lazy special cases. 
Specifically the usual binary infix boolean operators, the "if" expression 
and pattern matches.

There was a discussion fairly recently, by Pierre Weis among others, that it 
might be cool to be able to declare your own functions as non-strict. The 
functionality can be obtained regardless, by wrapping expressions in closures 
and only evaluating them when you need to, but it's a pfaff.

> It seems that procedural code (which includes
> functional expressions) is actually a way to
> specify evaluation order

I would say that imperative style allows you to determine evaluation order, 
not specify it.

> and timing and typically 
> control flow is used to delay evaluation -- so that
> procedural programming is actually quite lazy.

I think inability to build a closure makes imperative languages even more 
strict. You may be referring to a way of "faking it" using imperative style 
but I wouldn't say that writing Haskell in C makes C lazy.

> From a performance viewpoint, both eager and lazy
> evaluation have advantages -- lazy evaluation avoids
> gratuitously evaluating a term which the result does
> not depend on, whereas eager evaluation can be used to
> prevent an evaluation being done twice.

Lazy evaluation is often (typically?) used to refer to memoizing as well as 
evaluating on demand. In which case lazy evaluation also prevents an 
evaluation being done twice.

> Hence procedural 
> languages like Ocaml can be very fast because you can
> hand tune the tradeoffs (also making it harder to
> reason about the outcome .. )

Reasoning about lazy programs is difficult, AFAIK. I imagine this is because 
lazy programs end up building stacks of closures which act as data structures 
(require memory etc.) and which are a function of the input (i.e. they have 
non-trivial complexities).

Such problems can appear in OCaml. For example, I'd assume that converting 
(I'm using Array to avoid discussions of tail recursion ;-):

Array.map f (Array.map f l)

to:

Array.map (fun e -> f (f e)) l

would be a deforesting optimisation. However, for short arrays and longer 
stacks of composited functions, there will probably come a time when an 
equivalent "optimisation" slows things down by "foresting" stacks of 
functions.

> (1) exactly what does Ocaml guarrantee?

I think you're looking for: "strict evaluation of function and constructor 
arguments in an unspecified order by default".

> (2) what kind of performance and semantic
> tradeoffs are involved with perturbations
> on these assurances?

Are you asking if it would be productive to change the specs to something like 
in-order evaluation? I'm no expert but I think the non-specific order of 
evaluation is a good opportunity for optimising and the strictness vs 
laziness choices set OCaml in a nice position with regard to imperative 
programming.

> a purely functional
> language is necessarily lazy, because lazy evaluation
> is mandatory

I'd have thought that you cannot determine evaluation order in a purely 
functional language and, therefore, you couldn't distinguish between eager 
and lazy evaluation in this case.

> -- an eager evaluation strategy *requires* 
> procedural constructions to provide the laziness, and so
> can't work with a purely functional language.

I think that the way OCaml provides (memoized) laziness is inherently 
imperative but you could write a functional equivalent by providing an API 
which lets you recreate the lazy construct each time you use it.

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[skaller]

On Sun, 2004-09-05 at 20:50, Jon Harrop wrote:

> Are you asking if it would be productive to change the specs to something like 
> in-order evaluation? 

Thats the kind of question I'm asking (and others like it).
A recent post actually discussed a language with a more complex
evaluation strategy aimed at better optimisation opportunities.

> I'm no expert but I think the non-specific order of 
> evaluation is a good opportunity for optimising and the strictness vs 
> laziness choices set OCaml in a nice position with regard to imperative 
> programming.

I have some difficulty with the loss of referential transparency
in Ocaml. Yes you can write purely functional code, but then at least
one reason for eager evaluation (side effects) is lost.

> I'd have thought that you cannot determine evaluation order in a purely 
> functional language and, therefore, you couldn't distinguish between eager 
> and lazy evaluation in this case.

That isn't so if you can have functions that fail or fail to terminate.
In those case laziness matters. Clearly that's more cases than
you'd guess, otherwise Haskell would be a pointless language:
I'm not a Haskell programmer but I imagine the laziness is actually
exploited (just as Ocaml programmers exploit HOF's and closures
so routinely we forget we're doing it until some C++ programmers
asks if we actually use such advanced features .. :)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] laziness

[Jason Smith]

>> > However if the call is *inlined* to get
>> >
>> > 	if c' then a' else b'
>> >
>> > then perhaps a' or b' will never be evaluated.
>I understand that argument -- but that doesn't mean the
>compiler conforms to the specification, nor that the
>specification is best.

I'm not sure about OCaml but in GHC we could garuentee that the arguments a' 
and b' would be reduced using the 'case' syntax in GHC's intermediate language 
"Core". This the code would become something like this:

case c' of 
{ c'' ->
   case a' of
   { a'' ->
      case b' of
      { b'' -> if c'' then a'' else b'';
      }
   }
}

case forces evaluation to WHNF form, thereby garuenteeing correct eager order 
evalation. I presume O'Caml would do the same to keep side-effects evaluting 
correctly.

>> E.g. the order of evaluation of arguments is
>> unspecified, so it might be different depending on inlining; but
>> OCaml does specify that each argument are evaluated exactly once
>> and inlining doesn't change that.
>
>Must they be evaluated before the function is called?

If O'Caml follows the usual eager order semantics then evaluation is AOR or 
Applicative order redection. (Which is what I use in Mondrian).

There are several locations where we may attempt to reduce this overhead.

Strictness analysis: Determines usuing some form of abstract reduction 
semantics weather the argument is "strict" in the function, i.e. that it will 
be used at all. If it isn't then there is no need to reduce it. The problem 
with this is that in O'Caml u once again have side-effect's raise there ugly 
head. This means that even if the argument is not used in the function, the 
results of evaluating the argument which uses side-effects is. So you may have 
to analyse the argument itself and see if it uses any reference semantics.

Usage analysis: Determines "how many times" an argument is used. Not so much 
applicable to eager order evaluation but very handy in lazy languages. We can 
save the cost of a THUNK update by determining if we actually need to update 
the thunk with the new value once the argument has been reduced.

There are a range of other analysis techniques that "increase the degree of 
laziness" aka full-laziness transformation, reduce the cost of creating 
intermediate data structures aka deforestation, let-floating etc.. refer to a 
great body of literature for comments on these area's.

HTH
Jason.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] laziness

[skaller]

On Sun, 2004-09-05 at 11:07, Jason Smith wrote:

> >Must they be evaluated before the function is called?
> 
> If O'Caml follows the usual eager order semantics then evaluation is AOR or 
> Applicative order redection. (Which is what I use in Mondrian).
> 
> There are several locations where we may attempt to reduce this overhead.

Let me rephrase the question then. Suppose you wanted to
reduce the overhead "almost all the time". 
You can't do this if you specify the usual eager semantics.

So the question is: what changes to the semantic specification
would allow the optimisations?

For example: for 'simple' functions, it makes no difference
if evaluation is eager or lazy, so  the optimiser can choose
to evaluate lazily if it is possible the result will not
be used, or eagerly if it is used many times.

Many functions programmers write will have this property.

In a language where functions could have side effects,
clearly you'd have to either make some statement about
when and if the side effects occur, or simply
exclude such a function from the optimisation.

OTOH in Haskell I would guess there are only two properties
which would prevent an arbitrary evaluation time: if the
function could fail, or if it could fail to terminate.
So if the function is pure, total, and terminating,
there's no reason to specify when, if, or how many
times it is executed.

So you could, for example, simply allow the programmer
to state a function is 'nice' to allow the optimiser
maximum freedom (and on the programmers head it will
be if they lied :)

I'm not recommending this -- just giving an example
of one way one might try to get around what seems
to be a vast overconstraint for many functions
in languages that mandate some rigid mix of
eager/lazy semantics (and then try to optimise
the result preserving the semantics).

What would give the optimiser more freedom,
without sacrificing the *ability* to use eager
or lazy semantics when it is actually necessary
semantically?

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[Richard Jones]

[-- Attachment #1: Type: text/plain, Size: 1959 bytes --]

On Sun, Sep 05, 2004 at 01:07:48PM +1200, Jason Smith wrote:
> There are several locations where we may attempt to reduce this overhead.
>
> Strictness analysis: Determines usuing some form of abstract
> reduction semantics weather the argument is "strict" in the
> function, i.e. that it will be used at all. If it isn't then there
> is no need to reduce it. The problem with this is that in O'Caml u
> once again have side-effect's raise there ugly head. This means that
> even if the argument is not used in the function, the results of
> evaluating the argument which uses side-effects is. So you may have
> to analyse the argument itself and see if it uses any reference
> semantics.

One thing that worries me about laziness.

Doesn't laziness often indicate a bug in the code?  ie.  You've
written an expression in the program, but that expression is never
used.  This is dead code, right?  Hence a bug?

The only thing I can think of which countradicts this case is the
common Haskell example of the "infinite" list:

  numbersFrom n = n : numbersFrom (n+1)
  squares = map (^2) (numbersFrom 1)
  take 10 squares

But in a sense this contains dead code too.  You've written down your
desire to construct all the squares, and then later you change your
mind and take only the first 10.  In OCaml you'd write this correctly
as something like:

  List.map (fun x -> x * x) (range 1 10)

(Sorry if this appears like a troll, but actually I'm genuinely
interested in whether laziness is useful, or indicates a bug).

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
MONOLITH is an advanced framework for writing web applications in C, easier
than using Perl & Java, much faster and smaller, reusable widget-based arch,
database-backed, discussion, chat, calendaring:
http://www.annexia.org/freeware/monolith/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] laziness

[Nicolas Cannasse]

> Doesn't laziness often indicate a bug in the code?  ie.  You've
> written an expression in the program, but that expression is never
> used.  This is dead code, right?  Hence a bug?

Laziness can be useful in some cases (eg : enums in ExtLib) and I use it for
example in a typing algorithm where you need to duplicate big objects type
for unification but you're not sure in advance which field(s) will be
unified, so you delay it when they get accessed. It's kind of internet
browser cache.

Evaluated part of a program can depends on several kind of inputs, and is
undecidable. Then you cannot make automated assertion about what part will
never be evaluated in the general case (although this can be done in
specific cases). However what you can do is automated flow analysis to check
which part of your program are not accessible through some entry points :
this is interesting for dead code removal and test coverage but can be
tricky to do in OCaml.

Regards,
Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[skaller]

On Mon, 2004-09-06 at 10:57, Richard Jones wrote:

> Doesn't laziness often indicate a bug in the code?  ie.  You've
> written an expression in the program, but that expression is never
> used.  This is dead code, right?  Hence a bug?

But that dead code if executed eagerly will result
in a value stored in a variable which is never used.
So the code is still 'dead code' and still a bug
(assuming it is a bug) whether evaluation is eager
or lazy.

Actually the lazy case might make it easier to
track this down by adding a debugging print
in the expression -- in the eager case you get
a diagnostic but can't deduce the result is used,
in the lazy case you know the result is being used
when you get the diagnostic.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[Erik de Castro Lopo]

On Mon, 6 Sep 2004 01:57:41 +0100
Richard Jones <rich@annexia.org> wrote:

> One thing that worries me about laziness.
> 
> Doesn't laziness often indicate a bug in the code?  ie.  You've
> written an expression in the program, but that expression is never
> used.  This is dead code, right?  Hence a bug?

Not necessarily, but I'm not 100 sure I can justify that.

Consider mathematical code that uses lazy evaluation. Certain
expressions might be expressed in terms of an infinite sum of
terms. It would also be possible to have two expressions
declared like this, divide one by the other and have something
which when evaluated results in a finite constant and without 
even trying to evaluate the two infinite sums.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"I don't think any MS Exec will ever die of old age. Satan
doesn't need the competition."
-- Digital Wokan on LinuxToday.com

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[Jon Harrop]

On Monday 06 September 2004 01:57, Richard Jones wrote:
> One thing that worries me about laziness.
>
> Doesn't laziness often indicate a bug in the code?

No. Hence some languages (like Haskell) are completely lazy. Some people 
advocate the use of approaches which are lazy by default (like Haskell's), 
others prefer to use laziness explicitly, only when they feel it is 
necessary. The principle problem with lots of laziness is the difficulty in 
predicting memory usage, which is very implementation dependent.

> ie.  You've 
> written an expression in the program, but that expression is never
> used.  This is dead code, right?  Hence a bug?

Laziness is used when there is code which *might* need executing, not when an 
expression is never going to be executed.

Examples include recurrence relations, when the code will be executed until 
the base case is reached. This is true for lazy lists. Another example is 
propagators (where further computations may be performed, up to the 
discretion of a predicate).

[lazy list]
> ...
> But in a sense this contains dead code too.  You've written down your
> desire to construct all the squares, and then later you change your
> mind and take only the first 10.

You haven't written down a "desire to construct all squares" any more than 
writing the equivalent recurrence relation does:

x_0 = 0
x_(n+1) = 1 + 2 x_n

You have simply defined how any square may be computed.

> In OCaml you'd write this correctly as something like:
>
>   List.map (fun x -> x * x) (range 1 10)

This assumes that you know the 10 in advance, it also loses out on 
memoization. What if you want to compute up to 10, 12 and 14?

> (Sorry if this appears like a troll, but actually I'm genuinely
> interested in whether laziness is useful, or indicates a bug).

Laziness can definitely be useful. Whilst writing a compiler, I recently noted 
that my computing and storing the set of types used in each expression and 
subexpression was not always used. By making the construction lazy, I avoided 
many unnecessary computations (but not all!, hence it isn't dead code) and 
the program now runs much faster.

From a theoretical standpoint, Okasaki pointed out that imperative programs 
are often faster because they choose to amortise the costs of a sequence of 
operations, grouping them into batches. In contrast, functional programs 
often don't amortise costs. This gives them better worst case behaviour but 
worse average case behaviour. The Map and Hashtbl data structures are fine 
examples of this. Okasaki suggested that the solution might be to use 
laziness in functional approaches to amortise the costs of operations, lazily 
storing the necessary changes and then forcing the evaluation of all 
outstanding changes only when necessary.

So laziness can be used as an optimisation.

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[William Lovas]

On Mon, Sep 06, 2004 at 01:55:05PM +0100, Jon Harrop wrote:
> On Monday 06 September 2004 01:57, Richard Jones wrote:
> > One thing that worries me about laziness.
> >
> > Doesn't laziness often indicate a bug in the code?
>
> [...]
> 
> So laziness can be used as an optimisation.

Laziness has a particularly special place for pure languages like Haskell.
Some algorithms cannot be expressed with the same asymptotic complexity in
a pure eager language as in an impure eager language.  But this complexity
gap can be closed by making the pure language lazy:

    http://web.comlab.ox.ac.uk/oucl/work/geraint.jones/morehaste.html

cheers,
William

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[Hartmann Schaffer]

Richard Jones wrote:

> ...
>
>One thing that worries me about laziness.
>
>Doesn't laziness often indicate a bug in the code?  ie.  You've
>written an expression in the program, but that expression is never
>used.  This is dead code, right?  Hence a bug?
>  
>

well, programs supposedly run against quite a few different data sets, 
and depending on the particular data set, some code segments might never 
be executed

>...
>  
>
hs

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] laziness

[Richard Jones]

[-- Attachment #1: Type: text/plain, Size: 1034 bytes --]

On Mon, Sep 06, 2004 at 06:35:37PM -0400, Hartmann Schaffer wrote:
> Richard Jones wrote:
> 
> >...
> >
> >One thing that worries me about laziness.
> >
> >Doesn't laziness often indicate a bug in the code?  ie.  You've
> >written an expression in the program, but that expression is never
> >used.  This is dead code, right?  Hence a bug?
> > 
> >
> 
> well, programs supposedly run against quite a few different data sets, 
> and depending on the particular data set, some code segments might never 
> be executed

I was really talking about code that would never be executed under any
inputs.

The example was given of:

  let x = ... in let y = ... in x

Under lazy evaluation, "y" is never evaluated, but it's still dead code.

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
If I have not seen as far as others, it is because I have been
standing in the footprints of giants.  -- from Usenet

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] laziness

[Nicolas Cannasse]

> The example was given of:
>
>  let x = ... in let y = ... in x
>
> Under lazy evaluation, "y" is never evaluated, but it's still dead code.

let x = f() in

might trigger some mutations or IO, it can't be safely considered dead code
in an impure functional language such as OCaml.

Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] laziness

[Jason Smith]

>But that dead code if executed eagerly will result
>in a value stored in a variable which is never used.
>So the code is still 'dead code' and still a bug
>(assuming it is a bug) whether evaluation is eager
>or lazy.

This is where dead code elimination comes into play. A trivial optimization 
performed by the GHC compiler.

e.g.

let x = <long computation>
    y = ...
in  ...y....

we can remove 'x'.

Again, side-effects make this harder in o'caml.

>Actually the lazy case might make it easier to
>track this down by adding a debugging print
>in the expression -- in the eager case you get
>a diagnostic but can't deduce the result is used,
>in the lazy case you know the result is being used
>when you get the diagnostic.

The compiler should optimize it out. There shouldn't be any need for using 
explicit print statements.

Jason.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] laziness

[skaller]

On Mon, 2004-09-06 at 19:07, Jason Smith wrote:

> The compiler should optimize it out. There shouldn't be any need for using 
> explicit print statements.

Yes but the original issue is that the programmer
is seeing an expression they expect to be evaluated
and it isn't being evaluated -- so there is a bug
somewhere. So your point is kind of backwards --
the compiler may well optimise it away, but the programmer
is actually looking for evidence that it *isn't*
optimised away.

In an eager language, no conclusions can be drawn
from a debugging output - you still don't know
if the returned value is used or not.

In a lazy language, debugging output indicates
the code *is* being used and hence not dead,
and lack of output means it isn't, at least
in one particular environment. You might
investigate further and discover the result
is only used in an unreachable branch of a match,
so the code really is dead: that function argument
will never be used (so you can remove it,
and also the unreachable branch).


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] laziness

[Jason Smith]

>> I'd have thought that you cannot determine evaluation order in a purely
>> functional language and, therefore, you couldn't distinguish between eager
>> and lazy evaluation in this case.
>
>That isn't so if you can have functions that fail or fail to terminate.
>In those case laziness matters.
>Clearly that's more cases than
>you'd guess, otherwise Haskell would be a pointless language:

A function in haskell 'that fails to terminate' will either recurse ad 
infinitum. In which case thats the programmers fault, if Haskell evaluates it 
and it doesn't stop, ur problem.

Or, it will recurse over a Sum type. Haskell like most mainstream functional 
languages does not support recursive types, therefore we have to structure it 
explicitly over the Sum data type. With this you can create 'infinite' data 
structures, e.g.

fib = 1 : 1 : [ a + b | (a, b) <- zip fib (tail fib)]

we can keep on accessing this list by popping of the head element "forever".

>I'm not a Haskell programmer but I imagine the laziness is actually
>exploited (just as Ocaml programmers exploit HOF's and closures
>so routinely we forget we're doing it until some C++ programmers
>asks if we actually use such advanced features .. :)

Laziness is a *very* usefull feature, you can save *huge* amounts of unneeded 
calcluations. Any recursive data structure be it binarytree's, octtree's, 
lists etc.. benefits from this, you only evaluate expressions in the structure 
*when u need them* i.e. when u need there WHNF values, say in a condition 
statement.

Jason.


p.s. John skaller, I was wondering why I keep getting undeliverable errors 
when I send things to your address?

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] laziness

[Jason Smith]

>===== Original Message From skaller@users.sourceforge.net =====
>On Mon, 2004-09-06 at 19:07, Jason Smith wrote:
>
>> The compiler should optimize it out. There shouldn't be any need for using
>> explicit print statements.
>
>Yes but the original issue is that the programmer
>is seeing an expression they expect to be evaluated
>and it isn't being evaluated -- so there is a bug
>somewhere.

I'm not sure i follow you here. How can you *not* use something? if you want 
to use an expression you "use" it, I'm sorry, I'm missing something obviously.

>So your point is kind of backwards --
>the compiler may well optimise it away, but the programmer
>is actually looking for evidence that it *isn't*
>optimised away.

Um, ok so ur depositing debug statements in code to check if the expression is 
still there.  I still fail to see why u can't just *look* at your code and see 
if ur using the value or not. Can I get an example?

>In an eager language, no conclusions can be drawn
>from a debugging output - you still don't know
>if the returned value is used or not.

True, well almost true. The compiler can determine even in a strict language 
if the value is used or not, using strictness analysis. So you could put 
debugging statements in an expression and expect to see them and then volla, 
do not. For example,

val f x y => x + 2;

> f 2 (some computation that yields a number)

4

the long compuation was never actually used within 'f' so we don't have to 
evaluate it eagerly in haskell. Unforunately as I have already pointed out in 
a previous post in O'Caml it'd be harder to make this decision, but not 
impossible.

>In a lazy language, debugging output indicates
>the code *is* being used and hence not dead,

Yup.

>and lack of output means it isn't, at least
>in one particular environment.

Yup.

>You might investigate further and discover the result
>is only used in an unreachable branch of a match,
>so the code really is dead: that function argument
>will never be used (so you can remove it,
>and also the unreachable branch).

Ah nope, if its 'unreachable' then the original expression will never be 
evaluated, and you won't get the debug statements, and more so GHC won't 
compile it to start with. As soon as you use the expression, u reduce it. The 
*result* of evaluating the scrutinee expresion for a case (aka conditional 
expression) must be used because it determines the branch of the conditional 
to take. Weather that branch actually uses the result is irrelevant at that 
point.

Cheers, 
Jason.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] laziness

[skaller]

On Mon, 2004-09-06 at 22:17, Jason Smith wrote:

> I'm not sure i follow you here. How can you *not* use something? 

Like this:

	let f x y  = x in
	f 1 (2/0)

Well y isn't used in the function. If you rewrite it like
this (eagerly):

	x = 1
	y = (2/0)
	x

then you divide by zero, but if you rewrite it like this (lazily):

	1

then (2/0) isn't used. 

> Um, ok so ur depositing debug statements in code to check if the expression is 
> still there.  I still fail to see why u can't just *look* at your code and see 
> if ur using the value or not. 

You can certainly try to do that, but it may be difficult.
If you have a function f with argument a, and an application
(f a) is an argument of a function g, .... it isn't
so easy to determine that the final result of your program
actually depends on the value of a: the result of f applied
to a may be used by another application, but is its result used?

Well if you have a fully lazy language, you can actually do
an experiment which can positively say 'yes'.

> Can I get an example?

Hehe -- sure, download Felix and tell me if
the 7'th argument to the 23'rd function in
the module 'flx_inline' is 'used' :)

[Arggg .. no don't actually do that .. you're supposed
to just throw up your hands in horror and admit defeat :]

> True, well almost true. The compiler can determine even in a strict language 
> if the value is used or not, using strictness analysis. So you could put 
> debugging statements in an expression and expect to see them and then volla, 
> do not. 

AHA! Can you?? 

Consider this: you aren't using an argument,
so you optimise it away.

Then you change the function so the argument
is *conditionally* used -- but call it
so the condition is never satisfied.

OK, so you have a dumb analyser that
can't tell the condition is never satisfied so
it keeps the parameter -- and now
suddenly the argument is eagerly evaluated.

Problem is the argument was a division by zero.
And a change in the function encoding with
no impact on the result it returns suddenly
never even gets entered (the program crashes
before the function is called).

This won't happen with a lazy language I think.

I asked 'Can you??' above and really meant it:
I'm actually inlining and optimising things
in my compiler now and I'm just NOT sure what
I can get away with and what I can't.

However it seems to me at the moment,
'sloppy specification of evaluation order
tending to laziness' actually allows more
optimisation opportunties than either
fully eager or  lazy semantics. The problem 
is I don't know if you can still write
enough useful deterministic programs with
sloppy semantics or not..?

[Felix doesn't allow side effects in functions
BUT procedures can modify variables so
the result of a function can vary depending
on when it is called compared to any procedures
hanging around ..]

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners