This page is no longer maintained — Please continue to the home page at www.scala-lang.org

questioning FP

254 replies
Tony Morris
Joined: 2008-12-19,
User offline. Last seen 30 weeks 4 days ago.
Re: questioning FP

You're already used to lazy evaluation. Take the function

def f = false && _

You already know that (there exists)

f(bottom) != bottom

since (any x)

f(x) == false

Ergo, f is lazy in its argument.

Lazy evaluation is easy to understand at least. Just understand this much and you are making far far far less mistakes than some.

On Dec 15, 2011 11:39 PM, "Dennis Haupt" <h-star [at] gmx [dot] de> wrote:
i think i know what you mean, but i think once you understand it, you don't need to know what it means, and if you don't understand it, f(x) != x doesn't help at all :)

-------- Original-Nachricht --------
> Datum: Thu, 15 Dec 2011 07:27:11 -0600
> Von: ejc <eric [dot] j [dot] christeson [at] gmail [dot] com>
> An: "tmorris [at] tmorris [dot] net" <tmorris [at] tmorris [dot] net>
> CC: "scala-debate [at] googlegroups [dot] com" <scala-debate [at] googlegroups [dot] com>
> Betreff: Re: [scala-debate] questioning FP

> On Wednesday, December 14, 2011, Tony Morris <tonymorris [at] gmail [dot] com> wrote:
> > On 12/15/2011 11:44 AM, Dave wrote:
> >> The idea of lazy evaluation is that an expression is evaluated on
> >> demand
> > The "idea of" (definition of/mechanical test for) lazy evaluation is
> > such that f(bottom) != bottom. The rest is a consequence or
> > implementation detail.
> >
> >
> > --
> > Tony Morris
> > http://tmorris.net/
> >
> >
> >
ichoran
Joined: 2009-08-14,
User offline. Last seen 2 years 3 weeks ago.
Re: questioning FP
I think we're in danger here of losing the distinction between _branched execution_ and _lazy evaluation_. 

With branched execution, you have
  (test condition) {
    case 0 => this thing runs
    case 1 => this thing runs
    ...
  }
(two cases are enough in general if you nest them; in practice, multi-target jumping is what all modern computer architectures implement).

In contrast, with lazy evaluation, you have
  label = computation that produces a value
and you avoid actually running the computation until you need the value that the label says.

These are dramatically different ways to think about the problem; in particular, lazy evaluation requires branched execution but not vice versa (not without adding a function that is essentially the "branched execution function").

Branched execution is _absolutely necessary_ to get anything useful done.  Lazy evaluation is only rarely _required_, though in many cases one can recast branched execution problems more cleanly and efficiently as lazy evaluation problems.  The confusing part is that many strictly-evaluating languages have abnormal syntax for branched execution.  For instance:

Normal:
  if (tf) { x } else { y }
Sneaky:
  a && b   // means if (a) { return b; } else { return false;  }
  a || b   // means val x=a; if (x) { return x; } else { return b;  }

Interpreting these as lazy evaluation is both highly useful--as it lets you abstract over implementation details--and highly dangerous, as it sometimes matters what those implementation details are, and in most languages there is not in fact any ability to curry or otherwise manipulate the expressions that go into a short-circuiting boolean operator, and there is no guarantee that you won't get multiple evaluation of expressions that nominally appear to be the same thing.  For example, in

  lazy val x = f(y)
  if ( (x && a) || (!x && b) ) return g(z);

one has mixed lazy evaluation with short-circuiting in a way that may not immediately answer the question of whether f(y) is evaluated zero, one, or two times, and if the compiler doesn't help you out and write what you really mean:

  val x = f(y)
  if ( (x && a) || (!x && b) ) return g(z);

then you are spending the overhead of lazy evaluation for no reason whatsoever.

Since the point of the discussion is not whether lazy evaluation produces _correct results_ (it does), but rather whether it _performs well_ (it may or may not), this distinction is important.  As is the knowledge of how much your compiler is going to help you out when it comes to promoting to strictness those things whose structure makes laziness a waste of time.

  --Rex

 

On Thu, Dec 15, 2011 at 8:53 AM, Tony Morris <tmorris [at] tmorris [dot] net> wrote:

You're already used to lazy evaluation. Take the function

def f = false && _

You already know that (there exists)

f(bottom) != bottom

since (any x)

f(x) == false

Ergo, f is lazy in its argument.

Lazy evaluation is easy to understand at least. Just understand this much and you are making far far far less mistakes than some.

On Dec 15, 2011 11:39 PM, "Dennis Haupt" <h-star [at] gmx [dot] de> wrote:
i think i know what you mean, but i think once you understand it, you don't need to know what it means, and if you don't understand it, f(x) != x doesn't help at all :)

-------- Original-Nachricht --------
> Datum: Thu, 15 Dec 2011 07:27:11 -0600
> Von: ejc <eric [dot] j [dot] christeson [at] gmail [dot] com>
> An: "tmorris [at] tmorris [dot] net" <tmorris [at] tmorris [dot] net>
> CC: "scala-debate [at] googlegroups [dot] com" <scala-debate [at] googlegroups [dot] com>
> Betreff: Re: [scala-debate] questioning FP

> On Wednesday, December 14, 2011, Tony Morris <tonymorris [at] gmail [dot] com> wrote:
> > On 12/15/2011 11:44 AM, Dave wrote:
> >> The idea of lazy evaluation is that an expression is evaluated on
> >> demand
> > The "idea of" (definition of/mechanical test for) lazy evaluation is
> > such that f(bottom) != bottom. The rest is a consequence or
> > implementation detail.
> >
> >
> > --
> > Tony Morris
> > http://tmorris.net/
> >
> >
> >

Joshua.Suereth
Joined: 2008-09-02,
User offline. Last seen 32 weeks 5 days ago.
Re: questioning FP
I don't think the point really means a whole lot if you want to view Scala's code as expressions.
Again, there's a continuum of lazy evaluated expressions vs. strictly evaluated expressions.   Scala has both.  if-expressions lazily evaluate some sub expressions.  
I don't really think this debate is bringing to light a lot of useful material at this point, besides, In Haskell, lazily evaluated expressions are pretty rockin and have first class support in the runtime, and in Scala we support them as best as we can on the JVM.  
Perhaps some of these Haskellers could work on a JSR for first-class thunk support and associated optimisatoins on the JVM?   That would drastically alter my opinion on when to use laziness and eager evaluation.

- Josh
Note:  I use a lot more lazily evaluated expresisons in Scala than I ever did in Java, but no where near the line where Haskell is.

On Thu, Dec 15, 2011 at 10:24 AM, Rex Kerr <ichoran [at] gmail [dot] com> wrote:
I think we're in danger here of losing the distinction between _branched execution_ and _lazy evaluation_. 

With branched execution, you have
  (test condition) {
    case 0 => this thing runs
    case 1 => this thing runs
    ...
  }
(two cases are enough in general if you nest them; in practice, multi-target jumping is what all modern computer architectures implement).

In contrast, with lazy evaluation, you have
  label = computation that produces a value
and you avoid actually running the computation until you need the value that the label says.

These are dramatically different ways to think about the problem; in particular, lazy evaluation requires branched execution but not vice versa (not without adding a function that is essentially the "branched execution function").

Branched execution is _absolutely necessary_ to get anything useful done.  Lazy evaluation is only rarely _required_, though in many cases one can recast branched execution problems more cleanly and efficiently as lazy evaluation problems.  The confusing part is that many strictly-evaluating languages have abnormal syntax for branched execution.  For instance:

Normal:
  if (tf) { x } else { y }
Sneaky:
  a && b   // means if (a) { return b; } else { return false;  }
  a || b   // means val x=a; if (x) { return x; } else { return b;  }

Interpreting these as lazy evaluation is both highly useful--as it lets you abstract over implementation details--and highly dangerous, as it sometimes matters what those implementation details are, and in most languages there is not in fact any ability to curry or otherwise manipulate the expressions that go into a short-circuiting boolean operator, and there is no guarantee that you won't get multiple evaluation of expressions that nominally appear to be the same thing.  For example, in

  lazy val x = f(y)
  if ( (x && a) || (!x && b) ) return g(z);

one has mixed lazy evaluation with short-circuiting in a way that may not immediately answer the question of whether f(y) is evaluated zero, one, or two times, and if the compiler doesn't help you out and write what you really mean:

  val x = f(y)
  if ( (x && a) || (!x && b) ) return g(z);

then you are spending the overhead of lazy evaluation for no reason whatsoever.

Since the point of the discussion is not whether lazy evaluation produces _correct results_ (it does), but rather whether it _performs well_ (it may or may not), this distinction is important.  As is the knowledge of how much your compiler is going to help you out when it comes to promoting to strictness those things whose structure makes laziness a waste of time.

  --Rex

 

On Thu, Dec 15, 2011 at 8:53 AM, Tony Morris <tmorris [at] tmorris [dot] net> wrote:

You're already used to lazy evaluation. Take the function

def f = false && _

You already know that (there exists)

f(bottom) != bottom

since (any x)

f(x) == false

Ergo, f is lazy in its argument.

Lazy evaluation is easy to understand at least. Just understand this much and you are making far far far less mistakes than some.

On Dec 15, 2011 11:39 PM, "Dennis Haupt" <h-star [at] gmx [dot] de> wrote:
i think i know what you mean, but i think once you understand it, you don't need to know what it means, and if you don't understand it, f(x) != x doesn't help at all :)

-------- Original-Nachricht --------
> Datum: Thu, 15 Dec 2011 07:27:11 -0600
> Von: ejc <eric [dot] j [dot] christeson [at] gmail [dot] com>
> An: "tmorris [at] tmorris [dot] net" <tmorris [at] tmorris [dot] net>
> CC: "scala-debate [at] googlegroups [dot] com" <scala-debate [at] googlegroups [dot] com>
> Betreff: Re: [scala-debate] questioning FP

> On Wednesday, December 14, 2011, Tony Morris <tonymorris [at] gmail [dot] com> wrote:
> > On 12/15/2011 11:44 AM, Dave wrote:
> >> The idea of lazy evaluation is that an expression is evaluated on
> >> demand
> > The "idea of" (definition of/mechanical test for) lazy evaluation is
> > such that f(bottom) != bottom. The rest is a consequence or
> > implementation detail.
> >
> >
> > --
> > Tony Morris
> > http://tmorris.net/
> >
> >
> >


dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Re: questioning FP

2011/12/15 Cédric Beust ♔ :
>
> It still gets you very close to the kind of laziness we want. Actually, Tony
> made the same mistake in this post where he says that you can't add laziness
> to Java but you can in Scala, and to illustrate it, he shows a simple
> example of a boolean short circuit. However, during his demonstration, he
> silently modifies this signature:
>
> def lazyAnd(a: Boolean, b: Boolean)
>
> to
>
> def lazyAnd(a: Boolean, b: => Boolean)
>
> Well, if you allow this kind of rewriting of the original problem, then you
> can do the same kind of thing in Java (although it will be more verbose and
> with slightly different semantics, but the idea remains) and in pretty much
> any strict language that offers even the most minimalistic support for
> lambdas.

Not without changing the call-site. In Scala, there's no change in the
call-site, just in the declaration-site.

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland