Question on how thunking works

[Arthur Chan]

So suppose I have some simple expressions like:

let a = 4 * 4

let b = square a

square a = a * a

How exactly does b get reduced? Does 'a' get thunked, and then when the value of b gets reduced, it reuses the reduced thunk of 'a'? Or will we get the usual call-by-name situation where 'a' gets reduced twice?

i.e. is the reduction path like

square a

a * a

(4*4) * (a)

(64) * (a)

64 * (4*4)

64 * 64

4096

or is it

square a

a * a

(a = 4*4) * (a)

(a = 64) * (a)

(a = 64) * (a = 64)

4096

It was to my understanding that there were some issues surrounding the latter optimization and the monomorphism restriction.

Anyway, I ask because Martin Odersky's new class highlights that weakness in an unoptimized call-by-name approach and I was never clear on how Haskell behaved in practice.

[Eugene Kirpichov]

Hi,

It's graph reduction actually - like call-by-name, but without
duplication of computations.

b = square a =>
(\a -> a*a) a =>
a*a =>
a@(4*4) * a =>
16*16 =>
256

> --
> You received this message because you are subscribed to the Google Groups
> "Bay Area Haskell Users Group" group.
> To post to this group, send email to baha...@googlegroups.com.
> To unsubscribe from this group, send email to
> bahaskell+...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>



--
Eugene Kirpichov
http://www.linkedin.com/in/eugenekirpichov
We're hiring! http://tinyurl.com/mirantis-openstack-engineer

[Shachaf Ben-Kiki]

On Thu, Sep 20, 2012 at 3:01 PM, Arthur Chan <lambdas...@gmail.com> wrote:

The latter reduction is more like what you'd get with laziness.
Neither of the "a"s is distinguished, though; they're just the same
value. It's more like "let a = 4*4 in a*a" ==> "let a = 16 in a*a" ==>
"256".

Cale has a nice explanation of different evaluation schemes:
<http://www.reddit.com/r/haskell/comments/ywula/yet_another_reason_not_to_be_lazy_or_imperative/c5znykk>.

The most useful way to think about this, unless you have a reason to
care about low-level details, isn't as "thunks" but as sharing nodes
in a graph that's being reduced. See e.g.
<http://www.vex.net/~trebla/haskell/lazy.xhtml>. This is enough to
reason about the behavior of most lazily-evaluated programs, and is
much higher-level.

Note that, although every practical implementation uses it, the
Haskell Report doesn't specify lazy evaluation explicitly, just
non-strict semantics. You could write a compliant Haskell
implementation that uses call-by-name, because at the end of a
reduction call-by-name and laziness both produce the same results.

The monomorphism restriction is a mostly unrelated issue -- it comes
from the fact that you might write something like "let x :: Num a =>
a; x = 5*5 in ...", in which case the computed value 25 *won't* get
shared between uses of x (because x gets compiled into a function, not
a numeric value). So with the MR, when you write "let x = 5*5 in ...",
its type will be required to be concrete.

Shachaf

[Zaki Manian]

I like this stack overflow answer on this topic.

http://stackoverflow.com/questions/11466284/how-is-this-fibonacci-function-memoized

India phone:+91 9945111824
US phone:+1 (650) 492-8286
http://www.google.com/profiles/zmanian