Re: laziness in functional programming

Re: laziness in functional programming

[Greg Meredith]

John, et al,

The last statement is not true. Laziness is relatively new as the default
evaluation strategy in more mainstream functional languages. You can always
effect it with "thunks" (wrapping things up in lambdas), but it's not a
standard semantic in the dynamic functional languages (Lisp, Scheme, Dylan,
...) nor is it standard in the ML family of the statically typed functional
languages (ML, OCaml, F#, ... ). Scala gives a keyword to cause this to be
the evaluation strategy. Haskell is fairly unique as a high profile
functional language with the property that evaluation is lazy unless forced
to be eager.

Note that while laziness may be wiser from the point of view of not tripping
over potentially divergent computations, it is often very challenging to get
lazy code to be memory efficient (because you must pay for the deferred
computation in space). Moreover, laziness appears to give very brittle
performance characteristics, in the sense that small changes to lazy
algorithms can result in dramatic differences in performance
characteristics. Unfortunately, there seems to be a "no free lunch" theorem
behind this.

If ever there were a place where theory could help practice, this is one
(hint, hint). Finding good conceptual tools to aid in the design of *
appropriately* lazy algorithms for large scale computations would be a real
boon. There is no dirth of experience papers of the form "We (computational
biologists, computational financiers, machine learning theorists, ...)
thought we'd give Haskell a try. We loved the productivity, but we found
that there was a significant cost in optimizing our code to meet production
level memory and other resource requirements."

Best wishes,

--greg

On Thu, Mar 19, 2009 at 7:24 AM, John Baez <john.c.baez@gmail.com> wrote:

> Bill Lawvere wrote:
>
>
> I don't know the technical meaning of "lazy"; was it an attempt to avoid
> the
> > processing speed and ram needed to take account of the composition with
> > inclusion maps, etcetera?
> >
>
> No, "lazy evaluation" is a strategy of putting off computations until their
> results are known to be necessary.  The opposite is called "eager
> evaluation".  Laziness is often wiser.
>
> For example, a programming statement
>
> x:=y
>
> calls for the value of x to be set equal to y.  A strategy of eager
> evaluation will do this right away, while lazy evaluation will put off
> doing
> it until the variable x is used in some other task.  If x is never used,
> this saves work.
>
> I think most functional programming languages either delay evaluation in
> this way, or give the user the option to do this.
>
> Best,
> jb
>
>
>


-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com

Re: laziness in functional programming

[Miles Gould]

On Thu, Mar 19, 2009 at 07:24:55AM -0700, John Baez wrote:
> I think most functional programming languages either delay evaluation in
> this way, or give the user the option to do this.

It's generally fairly easy to roll your own lazily-evaluated
data-structures in any modern language. All you do, instead of
returning the value in question, is return a function of no arguments
(often called a "thunk", or a "promise") which calculates said value
when called. When the value is needed, the thunk is called (and then
usually replaced with the value, to save future computation). In
languages without first-class functions (functions which can be stored
in variables, constructed on-the-fly, etc) you have to do slightly more
work to construct the thunk, but this is tedious rather than hard. See
http://blog.plover.com/prog/defunctionalization.html for a discussion of
how Java programmers work around the lack of first-class functions.

At the other end of the scale, some strictly-evaluated languages (Scheme
and O'Caml, for example), provide convenient interfaces for constructing
lazily-evaluated data-structures, which are implemented using thunks.

It's perhaps worth mentioning that lazy evaluation, though often a Very
Good Thing, is not all roses: it makes the run-time performance (speed
and memory consumption) of a program more complex to predict.

Miles

-- 
An extensible program is a double-edged sword, but recent experience has
shown that users prefer a double-edged sword to a blunt one.
  -- Paul Graham

laziness in functional programming

[John Baez]

Bill Lawvere wrote:


I don't know the technical meaning of "lazy"; was it an attempt to avoid the
> processing speed and ram needed to take account of the composition with
> inclusion maps, etcetera?
>

No, "lazy evaluation" is a strategy of putting off computations until their
results are known to be necessary.  The opposite is called "eager
evaluation".  Laziness is often wiser.

For example, a programming statement

x:=y

calls for the value of x to be set equal to y.  A strategy of eager
evaluation will do this right away, while lazy evaluation will put off doing
it until the variable x is used in some other task.  If x is never used,
this saves work.

I think most functional programming languages either delay evaluation in
this way, or give the user the option to do this.

Best,
jb