Recursive Let

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Recursive Let

Tom Poliquin

I'm working on learning arrows.
This has led me to ArrowLoop, which then led me
to trying to understand the following,

> tracePlus b = let (c,d) = (d,b:d)
>               in c
>
> main = do
>      w <- return $ take 10 $ tracePlus 7
>      print w
>

which yields [7,7,7,7,7,7,7,7,7,7]


My confusion two pronged,

1) How let actually 'recurses'

2) How things get started (since d is undefined).


I have some vague understanding of both issues but
I want to make sure what's *really* going on so I
don't base my Haskell learning experience on a house
of cards. Help greatly appreciated.

My ramblings

1) How does recursion happen?

Being an ex-Schemer I recalled that let x = 3
get translated into something like

   (lambda (x) ... ) 3

So now there's a function involved. It's clear that b:d is

   (cons b d)

another function. So with appropriate plumbing
I could see the thing recurses but the Haskell viewpoint
eludes me.

2) How do things get started?

It seems that Haskell could figure out that
'd' is a list. If an uninitialized (undefined?)
list contains [] then things are reasonably
straightforward ..

tracePlus gets applied to 7

   (b:d) then becomes [7]
   (c,d) then becomes ([],7)
   
   Given there's an infinite loop (stream) then
   'take' grabs 'c' (an [])  and asks for another.
   Haskell's laziness works for us here.

   (b:d) then becomes [7,7]
   (c,d) then becomes (7,[7,7])

   ...
   ...

This is all fine. The only thing that subconsciously
nags me is that we appear to 'return' each time  which
would imply that we would leave the closure causing 'd'
to be undefined again.

I know this isn't true and if I close my eyes, think
really hard, and recall how streams are implemented
in Scheme (with a value-promise pair; the closure is
actually passed around) then I can see how this would
all work.

Back to the undefined list ... if it's *not* an
[] and has something to do with bottom ( _|_ )
then my eyes glaze over and I have to go watch a
Woody Allen movie to reset.

Sorry for the rambling.

I really like Haskell and I have found
it very powerful.

Any help greatly appreciated.

Thanks,

Tom
Reply | Threaded
Open this post in threaded view
|

Recursive Let

Brandon S Allbery KF8NH
On 2009 Feb 9, at 20:43, Tom Poliquin wrote:

> I'm working on learning arrows.
> This has led me to ArrowLoop, which then led me
> to trying to understand the following,
>
>> tracePlus b = let (c,d) = (d,b:d)
>>              in c
>>
>> main = do
>>     w <- return $ take 10 $ tracePlus 7
>>     print w
>
> 1) How does recursion happen?
>
> Being an ex-Schemer I recalled that let x = 3
> get translated into something like
>
>   (lambda (x) ... ) 3
>
> So now there's a function involved. It's clear that b:d is
>
>   (cons b d)
>
> another function. So with appropriate plumbing
> I could see the thing recurses but the Haskell viewpoint
> eludes me.

The trick is that the c and d on both sides of the equal sign are  
identical.  Since this asserts that d = b:d, Haskell repeatedly  
prepends b to d (lazily, so "take 10" halts the recursion).

let (c,d) = (d,b:d) in c         = d
let (c,d) = (b:d,b:b:d) in c     = b:d
let (c,d) = (b:b:d,b:b:b:d) in c = b:b:d
...

As long as something consumes elements from c, that let will continue  
to expand recursively.

--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [hidden email]
system administrator [openafs,heimdal,too many hats] [hidden email]
electrical and computer engineering, carnegie mellon university    KF8NH


-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 195 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/beginners/attachments/20090209/7e0ecc3d/PGP.bin
Reply | Threaded
Open this post in threaded view
|

Recursive Let

Brent Yorgey-2
In reply to this post by Tom Poliquin
On Mon, Feb 09, 2009 at 05:43:03PM -0800, Tom Poliquin wrote:

>
>
> 1) How does recursion happen?
>
> Being an ex-Schemer I recalled that let x = 3
> get translated into something like
>
>    (lambda (x) ... ) 3
>
> So now there's a function involved. It's clear that b:d is
>
>    (cons b d)
>
> another function. So with appropriate plumbing
> I could see the thing recurses but the Haskell viewpoint
> eludes me.

In Haskell, thinking of let expressions as being translated into
lambda expressions is not very helpful, precisely because of the
special ability to have recursive let bindings.  In Haskell it is
perfectly OK to have something like

  let x = 1:y
      y = 0:x
  in  ...

but it is not clear how this would get translated into function
application (which would come first?).  It's better just to think of
let as a special, primitive construct.

>
> 2) How do things get started?
>
> It seems that Haskell could figure out that
> 'd' is a list. If an uninitialized (undefined?)
> list contains [] then things are reasonably
> straightforward ..

An "uninitialized" list does not contain [].  I think perhaps your use
of the terms "uninitialized/undefined" might betray an imperative
mindset (?); in any case these are not the right words to use, since
they give an incorrect picture of what is going on.

Here's what actually happens: as a first example, let's consider the
let-binding

  let x = 1:x
  in ...

What happens here is that x is bound to a closure or 'thunk'
(suspended computation) which, *when needed*, will evaluate to 1:x.
This is laziness at work.  x is not 'uninitialized'; it is perfectly
well initialized to this thunk.  It is definitely not equal to []; at
this point the runtime doesn't know anything about x other than the
fact that it is a list, and that there is a thunk which may be
evaluated if and when the value of x is actually needed.  If you don't
use x anywhere in the ..., nothing will ever happen and the thunk will
eventually get garbage collected (in fact, it's likely that the
compiler would optimize x away and it would never be in memory at
all).

But suppose the value of x is needed (that is, some code
pattern-matches on x). Then the thunk will be evaluated just far
enough to allow the pattern-match: in particular, x will now be a list
with first element 1, and remainder of the list... another thunk.  At
this point x is not [1]; it is [1:...] where the ... represents
another thunk which will evaluate to x.  This process repeats as more
elements of x are needed, with each thunk evaluating just far enough
to allow the necessary pattern-matches, and suspending the remainder
of computation in another thunk.

Now, let's look at your example:

  let (c,d) = (d,b:d)

Of course, c and d will both be initialized to thunks which will
evaluate to lists as needed.  It's important to realize that from a
semantic point of view, b, c, and d never change.  They always
represent the same, unchanging values, as defined by this let
statement; it's just that operationally, only part of those values may
be actually evaluated, as needed.

If b has the value 7, then d = 7:d, which means d = 7:7:d, which means
d = 7:7:7:d, and so on, and the runtime will expand d out as far as
needed (in this case, 10 elements). You really can think of d as
*being* an infinite list of 7's, only part of which is evaluated.
 
> This is all fine. The only thing that subconsciously
> nags me is that we appear to 'return' each time  which
> would imply that we would leave the closure causing 'd'
> to be undefined again.

One way to think about it is that we only 'return' once: when
tracePlus 7 is evaluated, it returns, once and for all, a value 'c',
the evaluation of which happens to be suspended; it will be evaluated
further as needed.  Of course, if you want, you can indeed think of
execution jumping back and forth between main and tracePlus as c is
evaluated bit by bit, but I think this view is unhelpful, as it
suggests procedure calls in an imperative language, where local
variables such as 'd' would indeed go out of scope each time tracePlus
'exited'.  Instead, think of tracePlus as returning a closure, which
packages up the values of b, c, and d; it is this closure which is
then evaluated incrementally as execution continues.
 
> Back to the undefined list ... if it's *not* an
> [] and has something to do with bottom ( _|_ )
> then my eyes glaze over and I have to go watch a
> Woody Allen movie to reset.

A truly _undefined_ list is indeed _|_, and not []. [] is quite
defined; it is the list with no elements.  _|_ just means 'the
completely undefined value'.  However, as I hope I have made clear
above, the c and d in your example are neither [] nor undefined, so
this is immaterial.

There is much more to say on the topic, and doubtless there are places
where I've told some small fibs because the truth is more
complicated.  But hopefully this helps provide a useful way to
understand things.

-Brent
Reply | Threaded
Open this post in threaded view
|

Recursive Let

Tom Poliquin


On Tuesday 10 February 2009 07:57, Brent Yorgey wrote:
> On Mon, Feb 09, 2009 at 05:43:03PM -0800, Tom Poliquin wrote:

> tracePlus b = let (c,d) = (d,b:d)
> ? ? ? ? ? ? ? in c
> main = do
> ? ? ?w <- return $ take 10 $ tracePlus 7
> ? ? ?print w
>
> > 1) How does recursion happen?

> In Haskell, thinking of let expressions as being translated into
> lambda expressions is not very helpful, precisely because of the
> special ability to have recursive let bindings.  In Haskell it is
> perfectly OK to have something like
>
>   let x = 1:y
>       y = 0:x
>   in  ...
>
> but it is not clear how this would get translated into function
> application (which would come first?).  It's better just to think of
> let as a special, primitive construct.

Ah, this is what I needed, a mental model that actually fits
what's happening.

> > 2) How do things get started?

> An "uninitialized" list does not contain [].  I think perhaps your use
> of the terms "uninitialized/undefined" might betray an imperative
> mindset (?)

I've been doing FP for about 3 years (and imperative for 30)
I guess old habits are hard to break :-)  I went from Scheme
to ML and now Haskell and it seems like every day there's
something new for me to try to wrap my head around.
(Is category theory next ??!! ... into the rabbit hole .. no
pejorative intent)

> Here's what actually happens: as a first example, let's consider the
> let-binding
>
>   let x = 1:x
>   in ...
>
> What happens here is that x is bound to a closure or 'thunk'
> (suspended computation) which, *when needed*, will evaluate to 1:x.
> This is laziness at work.  x is not 'uninitialized'; it is perfectly
> well initialized to this thunk.

Great point. It seems like laziness is the major part of my misunderstanding.
Thinking about thunks will help a lot.

> Now, let's look at your example:
>
>   let (c,d) = (d,b:d)
>
> Of course, c and d will both be initialized to thunks which will
> evaluate to lists as needed.  It's important to realize that from a
> semantic point of view, b, c, and d never change.  They always
> represent the same, unchanging values, as defined by this let
> statement; it's just that operationally, only part of those values may
> be actually evaluated, as needed.

Ok, this clears things up a lot !   I just need to internalize it.

> A truly _undefined_ list is indeed _|_, and not [].
> However, as I hope I have made clear
> above, the c and d in your example are neither [] nor undefined, so
> this is immaterial.

Good. I'm not ready for _|_ yet .. :-)

> There is much more to say on the topic, and doubtless there are places
> where I've told some small fibs because the truth is more
> complicated.  But hopefully this helps provide a useful way to
> understand things.
>
> -Brent

Yes it does, and you're right I'm probably not ready for the 'truth' yet :-)

Thanks for the very detailed reply. It was extremely helpful!

Tom
Reply | Threaded
Open this post in threaded view
|

Recursive Let

Brent Yorgey-2
>
> Good. I'm not ready for _|_ yet .. :-)

There's actually nothing all that difficult about _|_; it is the value
of divergent computations--i.e. infinite recursion which never
actually produces any data.  We usually also say that anything which
results in a run-time error is _|_. For example, each of the following
is _|_:

  undefined
  error "blarg"
  let x = x in x
  let y = y + 1 in y
 
> Thanks for the very detailed reply. It was extremely helpful!

Glad to hear it!

-Brent
Reply | Threaded
Open this post in threaded view
|

Recursive Let

Thomas Davie

On 11 Feb 2009, at 09:29, Brent Yorgey wrote:

>>
>> Good. I'm not ready for _|_ yet .. :-)
>
> There's actually nothing all that difficult about _|_; it is the value
> of divergent computations--i.e. infinite recursion which never
> actually produces any data.  We usually also say that anything which
> results in a run-time error is _|_. For example, each of the following
> is _|_:
>
>  undefined
>  error "blarg"
>  let x = x in x
>  let y = y + 1 in y

Note though that it's not the value of divergent computations, but  
instead of divergent computations that also never produce any output.  
For example, this divergent computation is not _|_, because it  
produces values:

ones = 1 : ones

More precisely, in haskell bottom is a value in every type which we  
can give no information about at all.

In mathematics, bottom is a value which contains the *least*  
information of any value in the set, this is true in Haskell also, but  
also guarenteed by the fact that types are extended to include a  
special "I know nothing at all" value.

Bob