Talk:Lazy evaluation

From Wikipedia, the free encyclopedia

Contents

[edit] Expressions and variables

Surely it is expressions which are evaluated, not variables? -- The Anome

Yes, I think that's the usual way to say it. If you have referential transparency, like Haskell, then it doesn't make much difference. It's been a while since I did much Scheme, and I don't think it had delayed variables then, but around R4RS there was a promise function, that delayed evaluation of an expression, and force to deliver on a promise.

So, IMHO, we should talk about expressions first, with delayed variables as one possible way of expressing lazy evaluation.

We should also say something about graph versus tree reduction.

Tim Goodwin

[edit] X Window

I'm not sure if the analogy to XWindow's windowmanagers is valid. AFAIK, the windowmanager in X is only responsible for the contents and behaviour of window borders, and manipulation of those. Exposing and redrawing window content is something part of the X protocol, and implemented by the 'widget set', a software library to help abstract drawing and manipulation of objects within a window.

Mark-Jan

[edit] C/C++ exapmle

The C/++ example with the compound predicate was wrong. I check Stroustrup (it was closer to hand than K&R), and C++ guarantees the same behaviour with these operators as Java does. If your compiler doesn't, it's broken. --Robert Merkel 05:03, 20 Apr 2004 (UTC)

Actually I am not sure what the example is trying to show. Isn't it just an example of short-circuited evaluation? Besides, I don't see what a short-circuit has to do with lazy evaluation at all. -- Taku 05:11, Apr 20, 2004 (UTC)
I agree with Taku -- if C was a language that documented that it might short-circuit an expression as an optimisation, the example could be valid. If I have time I'll look for a better example. I guess the right way to say it is that short-circuiting is lazy evaluation at the meta level: "In theory I want to evaluate myfunc(b), but in fact it is never needed". -- Mark Hurd 16:09, 19 Jun 2004 (UTC)

[edit] Lazy evaluation as a design pattern

I think the "lazy evaluation as design pattern" section is misguided. This kind of pattern is usually called either "event-driven" or "reactive" (depending on the community you're a part of). This design pattern is fundamentally based on a push model, where changes are actively propagated to their dependents, rather than the pull model that lazy evaluation uses.

Kimbly 16:46, 7 January 2006 (UTC)

I also think it's misleading to talk about design patterns (which are ad hoc techniques that programmers adopt when they are using languages that are inadequate to express the abstractions they need to express) in an article about lazy evaluation, which is a programming language design construct that is backed up with formal semantics. Perhaps it would be best to merge this section into Design patterns, and add a note about the "lazy evaluation as design pattern" idea under "See also" or such. Catamorphism 19:18, 7 January 2006 (UTC)
The terms "lazy evaluation" and "design pattern" are both very loaded words in certain parts of CS; the section on "lazy evaluation as a design pattern" doesn't even describe a design pattern as described in that article. The idea that section was trying to express seems to be well-covered in "minimal evaluation", which is already linked. --bmills 04:56, 8 January 2006 (UTC)

[edit] Evaluation strategies

I'm not sure I'm completely qualified to write it, but this page should probably mention terms like "call by need", and "leftmost outermost evaluation". The latter tends term is used when describing lazy evaluation in the context of lambda calculus, so a brief section (or at least a link) to LC would be useful. Kimbly 19:36, 14 January 2006 (UTC)

Evaluation strategy covers the call-by-need/call-by-name distinction, so I added a paragraph linking to that. Catamorphism 21:10, 14 January 2006 (UTC)
I also edited Evaluation strategy to mention the terms "leftmost outermost" and "leftmost innermost". Catamorphism 21:25, 14 January 2006 (UTC)

[edit] Fuzziness

The article is really fuzzy with respect to actually defining lazy evaluation (probably in part because lazy programming literature tends to be a bit vague). The article explains what lazy evaluation does, but not what it is. Does lazy evaluation encompass all non-strict evaluation strategies? What about parallel call-by-need, which maximizes (rather than minimizes) the amount of computation performed? Similarly, delayed evaluation is also left undefined. —donhalcon╤ 04:19, 7 March 2006 (UTC)


[edit] Narrower Definition

From the research that I've done lazy evaluation refers to how expressions are evaluated when they are passed as arguments to functions and entails the following three points:

  1. The expression is only evaluated if the result is required by the calling function.
  2. The expression is only evaluated to the extend that is required by the calling function.
  3. the expression is never evaluated more than once.
The article seems to be erroneous here. Following David A. Schmidt, "Denotational Semantics", p.181: Delayed evaluation is the first item above. The third item is in David A. Watt, "Programming Language concepts and Paradigms", p. 100, called applicative-order evaluation or eager evaluation; the opposite is called normal-order evaluation. Adding the two last items gives lazy evaluation. Call-by-need evaluation requires full evaluation once it has been started.Haberg 09:29, 17 October 2007 (UTC)

This is something quite similar to call by need though the context is a bit different. The definition given in this entry is broader and is equivalent to what I would have called non-strict evaluation. My reading has been pretty much confined to functional programming so there may well be a bias here, but could someone provide a citation where the broader definition shown in this entry is given? To play fair, one citation for the narrower definition above is given in "Conception, Evolution, and Application of Functional Programming Languages", Paul Hudak, ACM Computing Surveys, Vol. 21, No.3, September 1989, pg. 383-385. Abcarter 15:56, 14 December 2006 (UTC)

I'm continuing to survey the literature and it confirms that lazy evaluation is a type of non-strict evaluation, which is essentially equivalent to call-by-name. For example

  1. Concepts, Techniques, and Models of Computer Programming by Peter Van Roy, pg 334-335.
  2. Practical Foundations for Programming Languages by Robert Harper, pg. 268
  3. Programming Languages by Mike Grant, Christian Skalka, and Scott Smith, pg. 28
  4. Type Theory and Functional Programming by Simon Thompson, pg. 31

I'm not saying this is an absolute, but it does appear to be the more common definition, a fact that should be taken note of in the entry. Abcarter 02:30, 19 December 2006 (UTC)

[edit] Should not be merged with delay

I think these are sufficiently distinct concepts that they ought to live in separate articles. --Saforrest 02:31, 14 April 2007 (UTC)

I agree, as I have never heard of "delay programming", while lazy evaluation is a somewhat important and basic topic in functional programming. If nobody thinks the articles should be merged, can we remove the banner from the front page? (Perhaps next time someone sees this note, if nobody has responded with disagreement, the banner should be removed.) --Piojo 19:30, 4 October 2007 (UTC)

Since it's been over a month since the previous comment, I removed the tag. Nibios 15:16, 9 November 2007 (UTC)

[edit] List of Lazy Languages

I am a Haskell neophyte, looking for a list of lazy programming languages. It seems to me that lazyness and type inference are orthogonal features. Does laziness have any "low-level" implementations?... maybe in terms of the Π-calculus, for example?