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
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] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
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
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
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
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
participants (4)
-
Brandon S. Allbery KF8NH -
Brent Yorgey -
Thomas Davie -
Tom Poliquin