Functional - lazy or not?

Author

lazy or not?

Oliver Bandel

2007-05-10, 10:04 pm

Hello,

for which kinds of application/problems is
lazy evaluation a good or the best choice,
and for what problems/applications is lazy
evaluation the wrong choice?

TIA,
Oliver

Mark T.B. Carroll

2007-05-10, 10:04 pm

Oliver Bandel <oliver@first.in-berlin.de> writes:

> for which kinds of application/problems is
> lazy evaluation a good or the best choice,
> and for what problems/applications is lazy
> evaluation the wrong choice?

I don't think that jumping either way is usually very wrong. Strict
evaluation may make it easier to understand your code's complexity and,
I suspect, simplifies the runtime system. Lazy evaluation can be
convenient when you are often wanting to process just a few of many
possibilities, or for when you have complex data structures that depend
upon each other recursively (if can both be sufficiently evaluated by
step-by-step non-simultaneous reasoning about their parts), or when you
are wanting to cache expensive-to-evaluate results. But, to the extent
necessary, one can normally find a way to get the effects of one in a
language that tends toward the other (for example, replacing infinite
lists with stateful generator functions), and for most of your code it
probably doesn't greatly matter which is being used.

-- Mark

Justin Crites

2007-05-15, 4:17 am

On May 10, 8:32 am, Oliver Bandel <oli...@first.in-berlin.de> wrote:
> Hello,
>
> for which kinds of application/problems is
> lazy evaluation a good or the best choice,
> and for what problems/applications is lazy
> evaluation the wrong choice?
>
> TIA,
> Oliver

Hi Oliver,

It is hard to answer a question like this. Every programming language
has a mix of both strict and non-strict (lazy) functions. For
example, consider:

if (a && b) {
f();
}

We would say, here, that the function && is non-strict because it does
not evaluate its argument "b" except on demand.

I don't know of a general principle that governs when to use strict or
non-strict components.

Here are some rules I can think of about when to use non-strict
structures:

1) When you think it's possible that the data might not be used (for
example, a function might return a lazy list, whose contents are only
computed on access).

2) When you want to represent infinite structures in a way that makes
them appear infinite in code. For example, you might represent the
ordered set of natural numbers as a lazy-evaluated linked list. To
any code that examines the list, it appears infinite, because there
are always more elements generated on demand. Note that there are
many times you represent infinite structures in a way where they do
*not* appear infinite in code -- or you just include a limited subset
of the infinity.

Well, those are the ones I can think of right now. The concept of
strictness has wide implications, all the way from the design level to
the syntactic level of programming languages.

Hope this helps.

Joachim Durchholz

2007-05-15, 8:05 am

Justin Crites schrieb:
> On May 10, 8:32 am, Oliver Bandel <oli...@first.in-berlin.de> wrote:
>
> Hi Oliver,
>
> It is hard to answer a question like this. Every programming language
> has a mix of both strict and non-strict (lazy) functions. For
> example, consider:
>
> if (a && b) {
> f();
> }
>
> We would say, here, that the function && is non-strict because it does
> not evaluate its argument "b" except on demand.

Actually, if() alone is enough to demonstrate that every language must
have both strict and nonstrict evaluation.
if() is strict in its condition, and non-strict in the "then" and "else"
parts.
And that's necessary, because you can't write terminating recursive
functions unless you have an if() with a strict condition and nonstrict
then/else branches. (If you have no recursion but loops, you'll need
strictness in the loop's termination condition and nonstrictness in the
loops's body.)

> I don't know of a general principle that governs when to use strict or
> non-strict components.

I don't either. I think that's because the decision whether something
should be lazy or strict can be influenced by large-scale architectural
considerations, and that's an area where there is little consensus.

Regards,
Jo

Christopher Browne

2007-05-15, 10:04 pm

Centuries ago, Nostradamus foresaw when Oliver Bandel <oliver@first.in-berlin.de> would write:
> for which kinds of application/problems is
> lazy evaluation a good or the best choice,
> and for what problems/applications is lazy
> evaluation the wrong choice?

It's "good" when it makes the problem easier to solve, and "bad" when
it doesn't. That's pretty useless, as observations go :-(.

I haven't seen many problems where I could easily perceive the use for
lazy evaluation.

It may be that if I did more work in Haskell, I'd perceive more such
cases.

When I encountered the relevant functions in Scheme
(delay/promise/force), there weren't a lot of examples that popped out
where it was actually useful to use these functions.

It might be that having "syntactic sugar" for laziness might make it
vastly more convenient to use, and might cause it to be used a lot
more. But that doesn't seem obvious.
--
"cbbrowne","@","gmail.com"
http://cbbrowne.com/info/slony.html
"Success is something I will dress for when I get there, and not
until." -- Unknown

rossberg@ps.uni-sb.de

2007-05-16, 8:04 am

On 15 Mai, 12:13, Joachim Durchholz <j...@durchholz.org> wrote:
>
> Actually, if() alone is enough to demonstrate that every language must
> have both strict and nonstrict evaluation.

Not at all. If that was true then the CBV lambda calculus would not be
Turing complete.

You just have to make a conditional with type

Bool -> (() -> Bool) -> (() -> Bool)

i.e. protect the branches by a suspension. In fact, some languages
actually do this, e.g. Smalltalk. Most languages typically don't
because their function syntax is too inconvenient.

- Andreas

rossberg@ps.uni-sb.de

2007-05-16, 8:04 am

I wrote:
>
> Bool -> (() -> Bool) -> (() -> Bool)

Of course, I meant

Bool -> (() -> a) -> (() -> a) -> a

- Andreas

rossberg@ps.uni-sb.de

2007-05-16, 8:04 am

On 15 Mai, 21:40, Neelakantan Krishnaswami <n...@cs.cmu.edu> wrote:
>
> let (x, y) = e in (x, y) == e
>
> holds in ML, but not in Haskell. Conversely:

I don't think that is true for this particular example - in Haskell
tuples are "irrefutable" patterns, which are matched lazily.

- Andreas

Marcin 'Qrczak' Kowalczyk

2007-05-16, 7:06 pm

Dnia 16-05-2007, =C5=9Bro o godzinie 04:53 -0700, rossberg@ps.uni-sb.de
napisa=C5=82(a):

> I don't think that is true for this particular example - in Haskell
> tuples are "irrefutable" patterns, which are matched lazily.

Tuples are not special in this respect.

"let" matches lazily on the toplevel, and that's the reason those
expressions were *not* equivalent.

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

Neelakantan Krishnaswami

2007-05-16, 7:06 pm

In article <1179316400.180977.198110@u30g2000hsc.googlegroups.com>,
rossberg@ps.uni-sb.de wrote:
>
> I don't think that is true for this particular example - in Haskell
> tuples are "irrefutable" patterns, which are matched lazily.

I did not know that -- thanks! So changing the example to sums, we
would get:

f _ = 5

case loop of
Left x -> f (Left x)
Right y -> f (Right y)

which loops, and

f loop

which doesn't, whereas in ML they would both loop.

--
Neel R. Krishnaswami
neelk@cs.cmu.edu

rossberg@ps.uni-sb.de

2007-05-16, 7:06 pm

On 16 Mai, 16:31, Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> wrote:
>
>
> Tuples are not special in this respect.
> "let" matches lazily on the toplevel, and that's the reason those
> expressions were *not* equivalent.

I stand corrected. Somehow I remembered (admittedly, I haven't had a
chance to use Haskell for ages) tuples always being treated as
irrefutable, in which case the equivalence would hold AFAICS. Sorry
for the confusion.

- Andreas

rossberg@ps.uni-sb.de

2007-05-16, 7:06 pm

On 16 Mai, 16:31, Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> wrote:
>
>
> Tuples are not special in this respect.
>
> "let" matches lazily on the toplevel, and that's the reason those
> expressions were *not* equivalent.

I stand corrected. Somehow I misremembered (admittedly, I did not have
a chance to use Haskell in ages) tuples always being treated as
irrefutable, in which case the equivalence would hold AFAICS. Sorry
for the confusion.

- Andreas

Florian Kreidler

2007-05-16, 7:06 pm

Joachim Durchholz <jo@durchholz.org> schrieb:
(...)
>
> Actually, if() alone is enough to demonstrate that every language must
> have both strict and nonstrict evaluation.
> if() is strict in its condition, and non-strict in the "then" and "else"
> parts.
> And that's necessary, because you can't write terminating recursive
> functions unless you have an if() with a strict condition and nonstrict
> then/else branches. (If you have no recursion but loops, you'll need
> strictness in the loop's termination condition and nonstrictness in the
> loops's body.)

If your evaluator stops at weak head normal forms, you can use
the old trick:

(if a then
\ x -> b
else
\ x -> c) ()

Joachim Durchholz

2007-05-16, 7:06 pm

rossberg@ps.uni-sb.de schrieb:
> On 15 Mai, 12:13, Joachim Durchholz <j...@durchholz.org> wrote:
>
> Not at all. If that was true then the CBV lambda calculus would not be
> Turing complete.
>
> You just have to make a conditional with type
>
> Bool -> (() -> Bool) -> (() -> Bool)
>
> i.e. protect the branches by a suspension.

Isn't a suspension just explicit laziness?
Just guessing, I'm not sure what the term exactly means (and wikipedia
came up empty and I suspect it will mean slightly different things to
different people anyway...)

Regards,
Jo

dbenson@eecs.wsu.edu

2007-05-16, 7:06 pm

Oliver --- I program almost exclusively in SML/NJ, which offers mostly-
strict but with the possiblity of using lazy evaluation. I almost
never use the laziness, however. First of all, it's a bit of extra
work. Second, and more important, in general laziness consumes both
more time and space than strict computations.

The exception is the virtue of avoiding a potentially expense
calculation which is just going to be thrown away. The way I design my
programs this is rare.

When it happens, once in a blue moon, the simplest technique is to
promote the expensive-to-calculate expression, expr, to a function, fn
() => expr and call the function once it is determined that the value
is indeed required.

Now that I've written it out, I suppose I do this once a new moon...

Paul Rubin

2007-05-17, 8:04 am

Joachim Durchholz <jo@durchholz.org> writes:
> Isn't a suspension just explicit laziness?
> Just guessing, I'm not sure what the term exactly means (and wikipedia
> came up empty and I suspect it will mean slightly different things to
> different people anyway...)

I read "suspension" as just meaning an unevaluated thunk, i.e. any
kind of laziness, not just explicit.

AFAIK, Haskell's if-condition is lazy. I'm not sure exactly how anything
ever gets forced. Maybe there's a forcing monad or something.

Phil Armstrong

2007-05-17, 8:04 am

Paul Rubin <http://phr.cx@nospam.invalid> wrote:
> Joachim Durchholz <jo@durchholz.org> writes:
>
> I read "suspension" as just meaning an unevaluated thunk, i.e. any
> kind of laziness, not just explicit.
>
> AFAIK, Haskell's if-condition is lazy. I'm not sure exactly how anything
> ever gets forced. Maybe there's a forcing monad or something.

Pretty much: values get forced by the IO Monad at the top level as I
understand things.

Phil

--
http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt

Joachim Durchholz

2007-05-17, 8:04 am

Paul Rubin schrieb:
> AFAIK, Haskell's if-condition is lazy. I'm not sure exactly how anything
> ever gets forced. Maybe there's a forcing monad or something.

It's the main function that gets forced by the run-time system.
(The main function also happens to be an IO monad, so that forcing main
has an effect, but I think that's unrelated to "when does it get forced".)

If an expression is forced, the top-level construct forces its strict
constituents: for function calls, it's the expression that determines
the function; for if-then-else, it's the condition; for pattern
matching, it's the patterns, possibly just the "refutable" ones, I'm not
100% sure here.
The lazy constituents may or may not be forced, depending on the
semantics of the top-level construct: for function calls, the parameters
are simply passed down and not forced by the function call; for
if-then-else, either the then part or the else part is forced, depending
on the result of the condition; for pattern matching, the expression in
the succeeding branch is forced.

Regards,
jo

Joachim Durchholz

2007-05-17, 8:04 am

Florian Kreidler schrieb:
> Joachim Durchholz <jo@durchholz.org> schrieb:
> (...)
>
> If your evaluator stops at weak head normal forms,

^^^^^^^^
I'd see that more as a transformation rather than as evaluation.
At least in my book, the end result of evaluation is an irreducible
expression. If the example you gave is WHNF, then evaluation simply
isn't complete, and asking whether that's "strict" or "lazy" doesn't
have an answer since it's not an evaluation.

(I'm pretty sure that there are a lot of people who'd apply a definition
where WHNF is indeed evaluation. I haven't seen such a definition
applied in a non-experimental language though.)

Regards,
Jo

Marcin 'Qrczak' Kowalczyk

2007-05-17, 7:07 pm

Dnia 17-05-2007, czw o godzinie 00:11 -0700, Paul Rubin napisa=C5=82(a):

> AFAIK, Haskell's if-condition is lazy. I'm not sure exactly how anything
> ever gets forced. Maybe there's a forcing monad or something.

Various expressions force some of their arguments or other values they
refer to, e.g.:

=E2=80=A2 pattern matching forces the value being examined when the pattern
expects a particular constructor or constant
=E2=80=A2 primitive functions like arithmetic or I/O force their arguments
=E2=80=A2 =E2=80=98if=E2=80=99 forces the condition
=E2=80=A2 =E2=80=98seq=E2=80=99 forces its first argument, even though it d=
oesn=E2=80=99t further
examine it

which includes, as the last step, entering some expression (forcing it
in order to return its result), possibly in an enriched environment,
e.g.:

=E2=80=A2 function application enters function body (after matching argumen=
ts
against parameter patterns)
=E2=80=A2 =E2=80=98case=E2=80=99 and =E2=80=98if=E2=80=99 enter the branch =
corresponding to the matching case
=E2=80=A2 =E2=80=98let=E2=80=99 enters the expression after =E2=80=98in=E2=
=80=99
=E2=80=A2 =E2=80=98seq=E2=80=99 enters its second argument

A separate story is the IO monad. Executing IO actions is distinct from
forcing expressions. Executing an action built with =E2=80=98>>=3D=E2=80=99=
forces and
executes its left argument, forces the application of right argument to
the value produced by the left argument, and executes the result.

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

Aatu Koskensilta

2007-05-17, 7:07 pm

On 2007-05-17, in comp.lang.functional, Joachim Durchholz wrote:
> Paul Rubin schrieb:
>
> It's the main function that gets forced by the run-time system.
> (The main function also happens to be an IO monad, so that forcing main
> has an effect, but I think that's unrelated to "when does it get forced".)

Forcing main does not have an effect, it just evaluates it to a value of type
IO (). Executing such values is not something that is describable using such
notions as forcing, as is easily seen by noting that the Haskell IO monad
could be a part of a pure strict language without much (any?) essential
changes.

--
Aatu Koskensilta (aatu.koskensilta@xortec.fi)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

Neelakantan Krishnaswami

2007-05-17, 7:07 pm

In article <<f2hbtn$vp2$1@online.de>>,
Joachim Durchholz <jo@durchholz.org> wrote:
> Florian Kreidler schrieb:
>
> ^^^^^^^^
> I'd see that more as a transformation rather than as evaluation.
> At least in my book, the end result of evaluation is an irreducible
> expression. If the example you gave is WHNF, then evaluation simply
> isn't complete, and asking whether that's "strict" or "lazy" doesn't
> have an answer since it's not an evaluation.

Your standard would make both strict and lazy evaluation as
transformations, not evaluations. In both Haskell and ML,

fun x -> 3 + 5

is a value. But 3 + 5 is still reducible to 8.

--
Neel R. Krishnaswami
neelk@cs.cmu.edu

Sponsored Links