- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
questioning FP
body
p { margin-bottom: 0cm; margin-top: 0pt; }
Hi All,
(I welcome any sort of replies, even containing foul language, as
long as there's also information inside.)
I'm about to give a lecture on FP. Now, some concepts in FP I love, but for some I have a hard time finding a good angle. Specifically, the IO monad.
Consider the following imperative code:
service.fetchData
service.closeObviously, both method calls create side effects.
Now, (discarding iteratees), lets consider making this with the IO monad:
for (data <- service.fetchData;
_ <- service.close)
yield data
where all methods are changed to return IO[Data], IO[Unit] and also the calling code must now return an IO[X] for some X.
The question is, what have we gained?
Instead of sequencing by line order, we're explicitly sequencing in the for comprehension. Not much of a gain here, since any mistake that causes code to be written in the first order in the imperative case can also be done in the functional case.
I also don't see anything that makes the code less prone to other mistakes. Such as forgetting to close or calling close twise. Obviously, there are ways to fix this such as service.withData(f: Data => X), but again, the more imperative style of silently calling close inside withData doesn't loose to the functional style that must return IO[X].
What am I missing? I'd appreciate any other examples which show how the use of IO is superior by making code that is more robust.
Regards,
Ittay
Re: Re: questioning FP
2011/12/14 Runar Bjarnason <runarorama [at] gmail [dot] com>
Both are needed for sure. One is great for designing modular abstractions and the other permits to control the execution. Now, I think a programming language must permit to compile lazy expressions directly to the bare metal without incurring a high runtime baggage overhead. This offers a tight control on the execution (strict) of high-level abstractions (lazy). Despite that they are not perfect and there is still a lot of ground to be covered, strict programming languages like ML and Scala show that it is possible without dedicated runtime support for laziness.
Cheers,
Sébastien
Re: Re: questioning FP
On Wed, Dec 14, 2011 at 8:22 AM, Runar Bjarnason <runarorama [at] gmail [dot] com> wrote:
Can't you just wrap it in a function that will return that thunk when evaluated? Now you have laziness.
While I like the theoretical appeal of laziness, my main problem with it is reasoning about its complexity. It's pretty easy to see that an algorithm making use of eager constructs is O(n^2) but good luck doing this math for any non-trivial piece of lazy code.
-- Cédric
Re: Re: questioning FP
2011/12/14 Cédric Beust ♔ :
>
> On Wed, Dec 14, 2011 at 8:22 AM, Runar Bjarnason
> wrote:
>>
>> You can always force a lazy thunk, but it's impossible to unforce a strict
>> one.
>
>
> Can't you just wrap it in a function that will return that thunk when
> evaluated? Now you have laziness.
That's not lazy. That's evaluation on demand.
scala> val a = { () => println("eval"); 5 }
a: () => Int =
scala> a()
eval
res2: Int = 5
scala> a()
eval
res3: Int = 5
If that made things actually lazy, eval would only be printed once.
>
> While I like the theoretical appeal of laziness, my main problem with it is
> reasoning about its complexity. It's pretty easy to see that an algorithm
> making use of eager constructs is O(n^2) but good luck doing this math for
> any non-trivial piece of lazy code.
>
> --
> Cédric
>
>
>
>
Re: questioning FP
On 14 dec, 22:26, Richard Wallace wrote:
> 2011/12/14 Cédric Beust ♔ :
>
>
>
> > On Wed, Dec 14, 2011 at 8:22 AM, Runar Bjarnason
> > wrote:
>
> >> You can always force a lazy thunk, but it's impossible to unforce a strict
> >> one.
>
> > Can't you just wrap it in a function that will return that thunk when
> > evaluated? Now you have laziness.
>
> That's not lazy. That's evaluation on demand.
The idea of lazy evaluation is that an expression is evaluated on
demand
>
> scala> val a = { () => println("eval"); 5 }
> a: () => Int =
The expression is partially evaluated: the expression
"println("eval"); 5" is lifted in a thunk.
This is "call by name" lazy evaluation. Every time you call a with a
function application the whole expression is evaluated
>
> scala> a()
> eval
> res2: Int = 5
>
> scala> a()
> eval
> res3: Int = 5
>
> If that made things actually lazy, eval would only be printed once.
Probably you mean "It is not memoized" which is a technique to speedup
by making a lookup table.
If you memoize it too then it is called "call by need"
REPL
====
scala> val a = { () => println("eval"); 5 }
a: () => Int =
Now a is "call by name" lazy evaluation by lifting the expression in a
thunk
scala> lazy val b = a()
b: Int =
Now I made the expression memoized (i.e. cached) too. If I don't use
the lazy keyword the expression would be directly evaluated.
This is "call by need" lazy evaluation.
scala> b
eval
res28: Int = 5
scala> b
res29: Int = 5
You can do this also inside a method
call by need lazy evaluation (memoized)
=======================================
scala> def m(f: => Int) = { lazy val a = f ; a + a + a}
m: (f: => Int)Int
scala> val b = m({println("eval");5})
eval
b: Int = 15
call by name lazy evaluation (non-memoized)
===========================================
scala> def m(f: => Int) = { f + f + f }
m: (f: => Int)Int
scala> val b = m({println("eval");5})
eval
eval
eval
b: Int = 15
Re: Re: questioning FP
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.
Re: 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/
>
>
>
Re: questioning FP
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
> An: "tmorris [at] tmorris [dot] net"
> CC: "scala-debate [at] googlegroups [dot] com"
> Betreff: Re: [scala-debate] questioning FP
> On Wednesday, December 14, 2011, Tony Morris 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/
> >
> >
> >
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:Re: questioning FP
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:
Re: questioning FP
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:
Re: Re: questioning FP
That is what I meant. The point was it's not quite as simple to make
things lazy as was made out, even in the simplest case. But it
requires quite a lot of work to do it everywhere since you can't
return a lazily evaluated value from a function. So you need to wrap
it everywhere. And then there is no strictness evaluation, so you
have to do more work that the compiler could be doing for you.
Strict by default makes sense for a language on the JVM. But that,
along with other factors, just makes me question the usefulness of the
JVM.
On Wed, Dec 14, 2011 at 6:44 PM, Dave wrote:
>
>
> On 14 dec, 22:26, Richard Wallace wrote:
>> 2011/12/14 Cédric Beust ♔ :
>>
>>
>>
>> > On Wed, Dec 14, 2011 at 8:22 AM, Runar Bjarnason
>> > wrote:
>>
>> >> You can always force a lazy thunk, but it's impossible to unforce a strict
>> >> one.
>>
>> > Can't you just wrap it in a function that will return that thunk when
>> > evaluated? Now you have laziness.
>>
>> That's not lazy. That's evaluation on demand.
>
>
> The idea of lazy evaluation is that an expression is evaluated on
> demand
>
>
>>
>> scala> val a = { () => println("eval"); 5 }
>> a: () => Int =
>
>
> The expression is partially evaluated: the expression
> "println("eval"); 5" is lifted in a thunk.
> This is "call by name" lazy evaluation. Every time you call a with a
> function application the whole expression is evaluated
>
>>
>> scala> a()
>> eval
>> res2: Int = 5
>>
>> scala> a()
>> eval
>> res3: Int = 5
>>
>> If that made things actually lazy, eval would only be printed once.
>
>
> Probably you mean "It is not memoized" which is a technique to speedup
> by making a lookup table.
> If you memoize it too then it is called "call by need"
>
>
> REPL
> ====
>
> scala> val a = { () => println("eval"); 5 }
> a: () => Int =
>
> Now a is "call by name" lazy evaluation by lifting the expression in a
> thunk
>
> scala> lazy val b = a()
> b: Int =
>
> Now I made the expression memoized (i.e. cached) too. If I don't use
> the lazy keyword the expression would be directly evaluated.
> This is "call by need" lazy evaluation.
>
> scala> b
> eval
> res28: Int = 5
>
> scala> b
> res29: Int = 5
>
>
> You can do this also inside a method
>
> call by need lazy evaluation (memoized)
> =======================================
>
> scala> def m(f: => Int) = { lazy val a = f ; a + a + a}
> m: (f: => Int)Int
>
> scala> val b = m({println("eval");5})
> eval
> b: Int = 15
>
> call by name lazy evaluation (non-memoized)
> ===========================================
>
> scala> def m(f: => Int) = { f + f + f }
> m: (f: => Int)Int
>
> scala> val b = m({println("eval");5})
> eval
> eval
> eval
> b: Int = 15
>
>
>
>
Re: Re: questioning FP
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.
It makes sense in a much broader ecosystem than the JVM alone (native, LLVM, .net, most interpreted languages, etc...) and there is even a growing part of the Haskell community which thinks that lazy is not the right default, as we already discussed.
It depends on the "usefulness for what", I guess. It might not be the right technology for you, but seems to work fine for millions of developers on the planet.
-- Cédric
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.
Re: Re: questioning FP
On Wed, Dec 14, 2011 at 09:55:31AM -0800, Cédric Beust ♔ said
> While I like the theoretical appeal of laziness, my main problem with it is
> reasoning about its complexity. It's pretty easy to see that an algorithm
> making use of eager constructs is O(n^2) but good luck doing this math for
> any non-trivial piece of lazy code.
On the other hand, lazy evaluation is essentially required for effecient
implementation of persistent data structures; cf. Okasaki's Purely
Functional Data Structures.
Re: Re: questioning FP
On Wed, Dec 14, 2011 at 16:28, Geoff Reedy wrote:
> On Wed, Dec 14, 2011 at 09:55:31AM -0800, Cédric Beust ♔ said
>> While I like the theoretical appeal of laziness, my main problem with it is
>> reasoning about its complexity. It's pretty easy to see that an algorithm
>> making use of eager constructs is O(n^2) but good luck doing this math for
>> any non-trivial piece of lazy code.
>
> On the other hand, lazy evaluation is essentially required for effecient
> implementation of persistent data structures; cf. Okasaki's Purely
> Functional Data Structures.
???
I suspect ML people would heartily disagree with this...
Re: Re: questioning FP
Laziness helps Okasaki use amortization arguments for certain
functional data structures. He uses laziness to maintain reasonable
runtime efficiencies when considering operations across different
persistent states of an functional data structure. For example, you
could have a queue where the next dequeue involves reversing a list.
If you had many copies of this queue and dequeue on all of them is
O(n), your amortization argument is ruined. With laziness, only the
first call to dequeue is O(n). Subsequent calls on copies of the
queue are O(1).
On Wed, Dec 14, 2011 at 10:45 AM, Daniel Sobral wrote:
> On Wed, Dec 14, 2011 at 16:28, Geoff Reedy wrote:
>> On Wed, Dec 14, 2011 at 09:55:31AM -0800, Cédric Beust ♔ said
>>> While I like the theoretical appeal of laziness, my main problem with it is
>>> reasoning about its complexity. It's pretty easy to see that an algorithm
>>> making use of eager constructs is O(n^2) but good luck doing this math for
>>> any non-trivial piece of lazy code.
>>
>> On the other hand, lazy evaluation is essentially required for effecient
>> implementation of persistent data structures; cf. Okasaki's Purely
>> Functional Data Structures.
>
> ???
>
> I suspect ML people would heartily disagree with this...
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
Re: Re: questioning FP
You might also be interested in this from his thesis:
"The above implementation of queues is asymptotically optimal | you can't ask
for better bounds than O(1) time per operation. However, in practice, it tends
to be fairly slow. There are at least two reasons for this. First,
lazy evaluation is
slower than strict evaluation, because of the need to create and memoize suspen-
sions. Compilers for lazy languages recognize this fact and use
strictness analysis
to turn lazy evaluation into strict evaluation whenever possible. However, when
lazy evaluation serves an algorithmic purpose, as it does here, it will never be
eliminated by strictness analysis. But even if we need lazy evaluation, maybe we
don't need so much of it."
Bottom line it depends on how we are defining "efficient".
On Wed, Dec 14, 2011 at 11:04 AM, Michael Schmitz
wrote:
> Laziness helps Okasaki use amortization arguments for certain
> functional data structures. He uses laziness to maintain reasonable
> runtime efficiencies when considering operations across different
> persistent states of an functional data structure. For example, you
> could have a queue where the next dequeue involves reversing a list.
> If you had many copies of this queue and dequeue on all of them is
> O(n), your amortization argument is ruined. With laziness, only the
> first call to dequeue is O(n). Subsequent calls on copies of the
> queue are O(1).
>
> On Wed, Dec 14, 2011 at 10:45 AM, Daniel Sobral wrote:
>> On Wed, Dec 14, 2011 at 16:28, Geoff Reedy wrote:
>>> On Wed, Dec 14, 2011 at 09:55:31AM -0800, Cédric Beust ♔ said
>>>> While I like the theoretical appeal of laziness, my main problem with it is
>>>> reasoning about its complexity. It's pretty easy to see that an algorithm
>>>> making use of eager constructs is O(n^2) but good luck doing this math for
>>>> any non-trivial piece of lazy code.
>>>
>>> On the other hand, lazy evaluation is essentially required for effecient
>>> implementation of persistent data structures; cf. Okasaki's Purely
>>> Functional Data Structures.
>>
>> ???
>>
>> I suspect ML people would heartily disagree with this...
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
Re: Re: questioning FP
On Wed, Dec 14, 2011 at 7:28 PM, Geoff Reedy wrote:
> On Wed, Dec 14, 2011 at 09:55:31AM -0800, Cédric Beust ♔ said
>> While I like the theoretical appeal of laziness, my main problem with it is
>> reasoning about its complexity. It's pretty easy to see that an algorithm
>> making use of eager constructs is O(n^2) but good luck doing this math for
>> any non-trivial piece of lazy code.
>
> On the other hand, lazy evaluation is essentially required for effecient
> implementation of persistent data structures; cf. Okasaki's Purely
> Functional Data Structures.
Maybe for some of them. But Scala's persistent vectors and hash tries
do just fine with strict evaluation. Would be interesting to see some
performance comparisons.
Re: Re: questioning FP
On Wed, Dec 14, 2011 at 07:31:21PM +0100, martin odersky said
> Maybe for some of them. But Scala's persistent vectors and hash tries
> do just fine with strict evaluation. Would be interesting to see some
> performance comparisons.
True, it's only needed to ensure amortized performance bounds. If the
worst case bounds are good enough, which they are for the persistent
vectors and hash tries, then laziness is indeed unnecessary.
Re: Re: questioning FP
Guys,
It's not an either or, us vs. them debate.
In Haskell you can force strict evaluation, and in scala you can use lazy evaluation. It's kind of a continuum.
While Haskell s runtime is optimized for thunks and laziness, the jvm is not and laziness is sort of kludged on top. This is what I mean by scala choosing the right default. We swing the continuum towards strict for our runtime. If the JVM had a better laziness story, maybe things would be different. However we're trying to make optimal use of HotSpot.
On Dec 14, 2011 12:55 PM, "Cédric Beust ♔" <cedric [at] beust [dot] com> wrote:Re: Re: questioning FP
2011/12/14 Josh Suereth :
> Guys,
>
> It's not an either or, us vs. them debate.
> In Haskell you can force strict evaluation, and in scala you can use lazy
> evaluation. It's kind of a continuum.
>
> While Haskell s runtime is optimized for thunks and laziness, the jvm is not
> and laziness is sort of kludged on top. This is what I mean by scala
> choosing the right default. We swing the continuum towards strict for our
> runtime. If the JVM had a better laziness story, maybe things would be
> different. However we're trying to make optimal use of HotSpot.
>
And, of course, laziness really requires purity, which Scala does not
have. But I agree, implementing lazy languages on the JVM looks like a
challenge.
Cheers
Re: Re: questioning FP
I was just stating that it's no surprise you can emulate the
observational behaviour of lazyness using thunks, but that it doesn't
implement graph reduction semantics. Of course, once you have
references you can implement the graph reduction semantics.
Now, I totally agree with Josh. The situations are symmetric: you can
express the same things with one or the other by default and the other
as an option. And it totally makes sense to chose CBV as the default
on the JVM.
Paul
2011/12/14 Josh Suereth :
> Guys,
>
> It's not an either or, us vs. them debate.
> In Haskell you can force strict evaluation, and in scala you can use lazy
> evaluation. It's kind of a continuum.
>
> While Haskell s runtime is optimized for thunks and laziness, the jvm is not
> and laziness is sort of kludged on top. This is what I mean by scala
> choosing the right default. We swing the continuum towards strict for our
> runtime. If the JVM had a better laziness story, maybe things would be
> different. However we're trying to make optimal use of HotSpot.
>
> On Dec 14, 2011 12:55 PM, "Cédric Beust ♔" wrote:
>>
>>
>> On Wed, Dec 14, 2011 at 8:22 AM, Runar Bjarnason
>> wrote:
>>>
>>> You can always force a lazy thunk, but it's impossible to unforce a
>>> strict one.
>>
>>
>> Can't you just wrap it in a function that will return that thunk when
>> evaluated? Now you have laziness.
>>
>> While I like the theoretical appeal of laziness, my main problem with it
>> is reasoning about its complexity. It's pretty easy to see that an algorithm
>> making use of eager constructs is O(n^2) but good luck doing this math for
>> any non-trivial piece of lazy code.
>>
>> --
>> Cédric
>>
>>
>>
>>
>
Re: Re: questioning FP
Although in the logical sense I see why you equate untyped with strict evaluation, I think in the cognitive sense it is the other way around. If something is untyped I have, by default, a lack of knowledge about what operations make sense with it, just as in a lazy-by-default I have, by default, a lack of knowledge about if the value has been evaluated yet. It's this lack of knowledge that makes it harder to intuitively reason about lazy code. When the context changes, different things go from waiting to be computed to being computed, and this can generally only be reasoned through starting at the outer-most context, working in. This makes it extremely hard to reason about lazy code in a modular, monotonic manner.
Matthew
On 14 December 2011 16:22, Runar Bjarnason <runarorama [at] gmail [dot] com> wrote:
--
Dr Matthew PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle Universitymailto: turingatemyhamster [at] gmail [dot] com gchat: turingatemyhamster [at] gmail [dot] commsn: matthew_pocock [at] yahoo [dot] co [dot] uk irc.freenode.net: drdozerskype: matthew.pococktel: (0191) 2566550mob: +447535664143
Re: Re: questioning FP
On Wednesday, December 14, 2011 11:45:13 AM UTC-5, Matthew Pocock wrote:
I don't follow very well what you have just said, except maybe that laziness and side-effects don't work well together. That is certainly true. If you want to remain lazy, you also have to remain pure. But reasoning about the execution of lazy pure code is as simple as possible. You just substitute equals for equals.
Then again, working with side-effects is pretty difficult even in strict code. Consider:
if (true) "hooray" else error("oops")
What is the result of this? Well, if "if" weren't lazy then it would always generate an error. Turns out that you need to introduce laziness to do anything useful.
We don't really need the "if" construct (or other control constructs) if we have laziness:
sealed trait Bool {
def apply[A](t: => A, f: => A): A
}
case object False extends Bool {
def apply[A](t: => A, f: => A) = t
}
case class True extends Bool {
def apply[A](t: => A, f: => A) = f
}
We can write a strict "if":
def strictIf[A](b: Bool, a1: A, a2: A) = b(a1, a2)
But if Bool.apply were already strict, it would be impossible to write the lazy version. Ergo, the only way to get anything useful done in strict languages is by adding special forms like "if" that introduce non-strictness.
Re: questioning FP
On 2011-12-14 11:15:00 -0600, Runar Bjarnason said:
> But if Bool.apply were already strict, it would be impossible to write
> the lazy version. Ergo, the only way to get anything useful done in
> strict languages is by adding special forms like "if" that introduce
> non-strictness.
Smalltalk does this by simply passing blocks into ifTrue:ifFalse:
condition ifTrue: [block to be evaluated if true]
ifFalse: [block to be evaluated if false]
The blocks respond to value: and can be evaluated when needed. So:
cond ifTrue: [ 2 + 3 ] ifFalse: [ 4 + 5 ] will only evaluate one +
while
cond ifTrue: (2 + 3) ifFalse: (4 + 5) will evaluate both +'s
This seems to have worked fine for Smalltalk, no laziness built in.
Re: Re: questioning FP
Laziness is thunkification + caching so, you can always emulate its behaviour in cbv using closures but you'all miss the truly lazy part.
On Dec 14, 2011 6:45 PM, "Sophie" <itsme213 [at] hotmail [dot] com> wrote:Re: Re: questioning FP
s/all/ll
On Dec 14, 2011 6:52 PM, "Paul Brauner" <polux2001 [at] gmail [dot] com> wrote:Crappy phone...
Re: Re: questioning FP
On 14 December 2011 17:15, Runar Bjarnason <runarorama [at] gmail [dot] com> wrote:
No, it had nothing to do with side-effects. It's about having knowledge about if something has already been evaluated. In a lazy language, some value can be in one of two states - evaluated or waiting to be evalutated. As someone looking at the code, your knowledge about its state is one of three values: you know that it will have been evaluted, you know that it will not have been evaluted, you do not know if it has or has not been evaluated.
Sure, but change this to:
something(x: Boolean) = if(x) "horray" else error("oops")
Now, we don't know if this terminates or not until we know the value of x. This isn't really the sort of case I was thinking of though. Perhaps a list with lazy evaluation of head and tail would be better. As someone who has been handed a List[X], I have no idea what the complexity of head or tail is on it, as I have no idea if the head or tail has been previously evaluated, and indeed have no idea what the complexity of the operation to be evaluated would be. I know this isn't legal scala, but:
trait List[+A] { def head: A def tail: List[A]}
case object Nil extends List[Nothing] { def head: A = throw new NoSuchElementException("No head on the Nil list") def tail: List[A] = throw new NoSuchElementException("No tail on the Nil list")}
case class Cons[A](lazy val head: A, lazy val tail: List[A]) extends List[+A]
Now, if I give you an instance x: List[A] using the above definition, what is the complexity of calling x.head or x.tail? You have no way of knowing without also knowing the intimate details of how x was built and if x.head or x.tail have previously been invoked. To reason about the complexity of any part of your program, you have to know about an ever expanding wider, prior-evaluated portion of it. As you showed with `lazy if`, potentially we can't even hope to reason about lower bound estimates on complexity without running portions of the program to know what branch it takes.
Matthew
--
Dr Matthew PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle Universitymailto: turingatemyhamster [at] gmail [dot] com gchat: turingatemyhamster [at] gmail [dot] commsn: matthew_pocock [at] yahoo [dot] co [dot] uk irc.freenode.net: drdozerskype: matthew.pococktel: (0191) 2566550mob: +447535664143
Re: Re: questioning FP
Thanks for this clear and concise example! The list example clearly illustrates, in a lazy setting, the difficulty of reasoning about complexity in a modular fashion. Without a modular approach to reasoning about complexity, the computational complexity of code is a brittle phenomenon with small changes leading to changes in computational complexity that are neither expected -- nor could they be.
The list example means that someone can checkin in a completely different part of the codebase a resource -- that even conforms to some type class -- and a client of the collection code suddenly goes completely wonky from a complexity perspective. This is reminiscent of the untyped dynamic setting, such as Ruby, where someone can monkey-patch in a completely different part of the codebase and code i am working on suddenly breaks.
The situation is not without hope -- i think. One recourse is to move resource usage into the type system. Linear types and other disciplines offer this and it seems to me not inconceivable to combine linear and (some modified form of) lazy computation. Still, we are a certain distance away from being able to plugin in resource tracking type disciplines into industrial languages -- even advanced languages like Scala.
Best wishes,
--greg
On Wed, Dec 14, 2011 at 9:38 AM, Matthew Pocock <turingatemyhamster [at] gmail [dot] com> wrote:
--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136
+1 206.650.3740
http://biosimilarity.blogspot.com
Re: Re: questioning FP
On Wed, Dec 14, 2011 at 15:38, Matthew Pocock
wrote:
>
>> Then again, working with side-effects is pretty difficult even in strict
>> code. Consider:
>>
>> if (true) "hooray" else error("oops")
>>
>> What is the result of this? Well, if "if" weren't lazy then it would
>> always generate an error. Turns out that you need to introduce laziness to
>> do anything useful.
>
>
> Sure, but change this to:
>
> something(x: Boolean) = if(x) "horray" else error("oops")
>
> Now, we don't know if this terminates or not until we know the value of x.
Only if there's non-strictness. If "if" wasn't non-strict, it would
always generate an error, irrespective of the value of x. A strict
"if" would work like this:
something(x: Boolean) = {
val ifTrue = "horray"
val ifFalse = error("oops")
if(x) ifTrue else ifFalse
}
Replace "val" with "lazy val" and you have lazy behavior. Replace
"val" with "def" and you have another kind of non-strictness, more in
line with how "if" actually works.
Re: Re: questioning FP
That should work:
sealed trait Bool {
def apply[A](t: => A, f: => A): Unit => A
}
case object False extends Bool {
def apply[A](t: => A, f: => A) = x => t
}
case class True extends Bool {
def apply[A](t: => A, f: => A) = x => f
}
Re: Re: questioning FP
Please, forgive/forget my preceeding email.
I meant this one:
def strictIf[A](b: Bool, a1: Unit => A, a2: Unit => A) = b(a1, a2) ()
It should work with Bool.apply being strict.
Re: Re: questioning FP
On Wed, Dec 14, 2011 at 15:30, nicolas [dot] oury [at] gmail [dot] com
wrote:
> Please, forgive/forget my preceeding email.
>
> I meant this one:
> def strictIf[A](b: Bool, a1: Unit => A, a2: Unit => A) = b(a1, a2) ()
>
> It should work with Bool.apply being strict.
Only because b doesn't use a1 or a2 in any way. In other words, this
work-around only works for special cases.
Re: Re: questioning FP
- Josh
On Wed, Dec 14, 2011 at 11:22 AM, Runar Bjarnason <runarorama [at] gmail [dot] com> wrote:
Re: Re: questioning FP
Oh, this might actually be exactly what I am saying. Take a look at my language Babel-17 (www.babel-17.com). ;-)
Cheers,
Steven
On 14.12.2011, at 16:22, Runar Bjarnason wrote:
> > Strictness should be the default in a general purpose language, and laziness a feature that can be turned on when the situation calls for it.
>
> Or, you know, the other way around. Once you are strict, it is too late to be lazy. You can always force a lazy thunk, but it's impossible to unforce a strict one.
>
> In a very real way, what you're saying is analogous to: "untyped should be the default in a general purpose language, and types are a feature that can be turned on when the situation calls for it". Think about it.
>
Re: Re: questioning FP
On Mon, Dec 12, 2011 at 12:44 PM, Paul Brauner <polux2001 [at] gmail [dot] com> wrote:
Yes. But note that you can do Hughes' example even with plain iterators! When he wrote that it was the high tide of laziness; everybody believed you needed to be lazy. Now the pendulum has swung back.
Cheers
-- Martin
Re: questioning FP
2011/12/6 Tony Morris <tmorris [at] tmorris [dot] net>
Not for systems programming though.
http://hasp.cs.pdx.edu/overview.html
Haskell would be pretty useless outside academia without C and its FFI. Isn't that because lazy languages lie about their underlying platform using a lot of built-in runtime magic? I heard kernel devs compare Haskell to swan swim: beautiful above the surface but with little legs paddling frenetically under the water. I don't know if it is entirely true but a funny analogy nonetheless.
Re: questioning FP
On Wed, Dec 7, 2011 at 5:52 AM, Sébastien Bocq wrote:
> Haskell would be pretty useless outside academia without C and its FFI.
> Isn't that because lazy languages lie about their underlying platform using
> a lot of built-in runtime magic? I heard kernel devs compare Haskell to swan
jvms are written in c, no?
garbage collectors are written in c, no?
java most often runs on an operating system written in c, probably, no?
yet we use the java ecosystem and don't belittle it that much.
so how far away is haskell really? in some ways not so far. in other
ways, yes, far.
but that's the power of smart people working on good abstractions! :-)
once they refine it over, say, 50 years, then we've got a wonderful
thing.
Re: questioning FP
martin odersky wrote:
The title is probably too much of a troll. Sorry about that.
My questioning is specifically about making functions pure. And the hoops one need to jump through to get that (at least the way I know which is the IO monad). More specifically:
1. what does it buy me? in theory, pure functions are nice since they behave better, but i want to find a use case that appeals to everyday java developers. That is, a case where making a function pure removes pitfalls (while the function remains basically the same)
2. what are the alternatives to IO monad? an implicit World argument?
Thank you,
Ittay
Re: questioning FP
On Mon, Oct 10, 2011 at 7:16 AM, Ittay Dror wrote:
>
>
> martin odersky wrote:
>
> The IO monad was a neat trick for combining side effects with lazy
> evaluation. But your title seems to be wrong. Questioning FP? FP is much
> broader than lazy evaluation. In fact, there is only one lazily evaluated
> language in wide usage today and even its creators have said that laziness
> was probably a mistake. Strict languages don't need the IO monad, and
> generally don't have it, even though they could. Bob Harper's posts in his
> "existential type" series are a good explanation on why not. An interesting
> quote from Simon Peyton Jones is that "laziness has kept us pure". That is,
> it has motivated the use of monads to represent effects. I agree that a
> static representation of effects is very useful, but my gut feeling is that
> there must be a more lightweight and polymorphic way to get effect checking
> than what monads provide. -- Martin
>
> The title is probably too much of a troll. Sorry about that.
>
> My questioning is specifically about making functions pure. And the hoops
> one need to jump through to get that (at least the way I know which is the
> IO monad). More specifically:
> 1. what does it buy me? in theory, pure functions are nice since they behave
> better, but i want to find a use case that appeals to everyday java
> developers. That is, a case where making a function pure removes pitfalls
> (while the function remains basically the same)
> 2. what are the alternatives to IO monad? an implicit World argument?
>
The IO monad does not make a function pure. It just makes it obvious
that it's impure.
An explicit world argument would make the function technically pure,
but again, doing so
is dubious in practice.
If I'd search for good examples where purity is useful, I'd look
elsewhere. For instance, parallel collections allow automatic speedups
in exchange for all computations being pure.
Cheers
Re: questioning FP
> The IO monad does not make a function pure. It just makes it obvious
> that it's impure.
I have to disagree here, or at least ask why you think so. Let's
consider the function `putStrLn` from Haskell with the type `String ->
IO ()`. The definition of "purity" I am used to basically requires that
`putStrLn "foo"` does not execute a side-effect (true) and does not
depend on (hidden) state such that subsequent executions yield exactly
the same value (also true). The side-effect is executed by the
underlying system only if it is somehow included in `main`.
Re: Re: questioning FP
On Mon, Oct 10, 2011 at 10:04 AM, Lars Hupel wrote:
>> The IO monad does not make a function pure. It just makes it obvious
>> that it's impure.
>
> I have to disagree here, or at least ask why you think so. Let's
> consider the function `putStrLn` from Haskell with the type `String ->
> IO ()`. The definition of "purity" I am used to basically requires that
> `putStrLn "foo"` does not execute a side-effect (true) and does not
> depend on (hidden) state such that subsequent executions yield exactly
> the same value (also true). The side-effect is executed by the
> underlying system only if it is somehow included in `main`.
>
You can do the same trick for every language: You can say *all* Scala
functions just "assemble" a computation which then gets executed only
by calling main. So instead of Monadic bind, Scala has
val x = a; b
On the type level, every type T would be interpreted as IO[T]. Every
function application is a bind. And voila! No side effects!
So the only thing IO provides is that code *not* using it is certified
to be pure, whereas in Scala everything is in the IO monad.
Cheers
Re: questioning FP
> You can do the same trick for every language: You can say *all* Scala
> functions just "assemble" a computation which then gets executed only
> by calling main. So instead of Monadic bind, Scala has
>
> val x = a; b
>
> On the type level, every type T would be interpreted as IO[T]. Every
> function application is a bind. And voila! No side effects!
But you agree that this interpretation is not useful at all? Having no
possibility to choose whether to use IO or not does not make an effect
system.
Re: questioning FP
Re: Re: questioning FP
You can also measure how often you want to circuvemt a type system. | think that the main problem is the coarsity of IO.
Re: Re: questioning FP
Martin, you stated that possibility a few times already - I'm sure we're all really curious now about what you have in mind :)
Also, since monads don't compose etc, why hasn't the discussion mutate to Applicative?
Thanks,Razvan
On 2011-10-10, at 2:32 PM, "nicolas [dot] oury [at] gmail [dot] com" <nicolas [dot] oury [at] gmail [dot] com> wrote:
Re: Re: questioning FP
On Mon, Oct 10, 2011 at 10:50 AM, Runar Bjarnason <runarorama [at] gmail [dot] com> wrote:
--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136
+1 206.650.3740
http://biosimilarity.blogspot.com
Re: Re: questioning FP
On Mon, Oct 10, 2011 at 3:18 PM, Lars Hupel wrote:
>> You can do the same trick for every language: You can say *all* Scala
>> functions just "assemble" a computation which then gets executed only
>> by calling main. So instead of Monadic bind, Scala has
>>
>> val x = a; b
>>
>> On the type level, every type T would be interpreted as IO[T]. Every
>> function application is a bind. And voila! No side effects!
>
> But you agree that this interpretation is not useful at all? Having no
> possibility to choose whether to use IO or not does not make an effect
> system.
Of course.
Re: questioning FP
martin odersky epfl.ch> writes:
> So the only thing IO provides is that code *not* using it is certified
> to be pure, whereas in Scala everything is in the IO monad.
That's quite a huge thing, don't you agree?
/Jesper Nordenberg
Re: Re: questioning FP
On Mon, Oct 10, 2011 at 12:56 PM, Jesper Nordenberg wrote:
> martin odersky epfl.ch> writes:
>> So the only thing IO provides is that code *not* using it is certified
>> to be pure, whereas in Scala everything is in the IO monad.
>
> That's quite a huge thing, don't you agree?
Sure. But I think there will at some point be better ways to track
effects than monads. Monads are too
rigid. Adding a single println somewhere means you have to rewrite
your whole program.