Alex M
The definition of fix presented in class today was:
今日の授業で教わった fix の定義
fix :: (a -> a) -> a
fix f = let x = f x in x
However, an alternative definition of fix (from
http://en.wikipedia.org/wiki/Fixed-point_combinator#Implementing_fixe...)
appears to be:
けれども、Wikipedia にあった別の定義ではこうでした
fix' :: (a -> a) -> a
fix' f = f (fix' f)
The two exhibit the same behavior on, say, (const 9):
この二つは同じ動作をします
Prelude> fix (const 9)
9
Prelude> fix' (const 9)
9
Prelude>
However, if we have some f like this:
けれども次の f のようなものがあると
Prelude> let f x = 5 + x
then evaluating the below expression just loops forever without running out of stack:
次の式を評価するとスタックを食いつぶすことなく無限ループします
Prelude> fix f
whereas evaluating this expression quickly results in stack overflow:
一方こちらを評価した場合には即座にスタックオーバーフローします
Prelude> fix' f
Also, if we instead do:
同様に、
Prelude> fix' (\x -> 5 + x)
then we don't run out of stack and just loop forever.
のようにすると、スタックを食いつぶさず、無限ループします。
So I'm quite confused by all this. Also, it's not clear to me how
recursion is "implemented using the fixed-point combinator" in the
"Background: recursive bindings" slide.
ということで、わたしはとても混乱しています。
また、"Background: recursive bindings" slide で
再帰がどのように "implemented using the fixed-point combinator"
(fixed-point コンビネーターを使って実装されているのか)
なのかがよくわかりません。
Any clarification on the above would be appreciated.
Thanks,
Alex
David Terei
Good question! The answer pulls in some of the trickiness of the RTS
so its going to be a long but interesting answer. High level is that
fix doesn't actually loop forever, it blocks and fix' does loop
forever with stack allocation so eventually overflows.
To start though, I don't get any difference in behaviour between:
fix' f
fix' (\x -> 5 + x)
Both report stack overflow for me (using 7.2.2), in fact if I look at
the code that GHC generates it's exactly the same for both cases.
As for fix vs fix' the STG code for them is as follows (top line
Haskell, bottom line STG):
fix f = let x = f x in x
=>
fix f = let x = f x in x
fix' f = f (fix' f)
=>
fix' f = let x = fix' f in f x
So fix is translated to STG directly as it uses only Haskell
constructs that are also in STG, fix' gets translated a little to
handle laziness (remember from my lecture that 'let' = thunk
creation). Notice fix is a self recursive thunk while fix' is a
recursive function and not tail recursive (so stack allocation).
One thing to be careful of here is that the behaviour in GHCi is a
little different from compiled code.
If you compile the fix' function, it still overflows so same behaviour
in both ghc and ghci.
The cool thing though, is if you compile fix then ghc instead of ghci
when it executes it throws a NonTermination exception!
http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Co...
It seems pretty magical but ghc can actually detect a very small
number of cases of infinite loops and throw an exception instead. As I
covered a little in the lecture, a thunk is not just a suspended
computation but can also be updated. So when a thunk is unevaluated,
pointers to it point to an actual thunk, something that is a piece of
code with an environment that needs to be executed (forced in
functional terminology) to get the actual result. Once the result is
computed, rather than just return it to the original caller that
forced the thunk, the thunk itself is replaced with a pointer to the
computed value. So if any other pointers to the thunk exist (i.e a
shared variable) the work is shared since they now get the value and
not a thunk when they try to force it.
There is an extra detail here. Something called 'blackholes'.
Basically when a thunk is first forced, the thunk is initially
replaced with a kind of sentinel value called a blackhole which simply
indicates that the thunk is currently being forced. If any other
threads come along and try to force the thunk while its in a blackhole
state, they block on the thunk instead of starting a duplicate
computation. (blackholes are also needed for a complication with
garbage collection and thunks).
Now what happens with the fix function when you call it with a non
terminating function like you did is that the thunk that is doing the
know tying here ends up being forced twice. First when you enter fix
and again after the first iteration. At the second iteration it
doesn't re-enter the thunk (which if it did wouldn't cause a stack
overflow but consume the heap and so eventually all memory) but blocks
on the thunk since its in blackhole status.
This paper has a good description of what I just explained:
http://research.microsoft.com/pubs/68449/new-rts.ps.gz
in section '5.1 Space leaks and black holes'.
So in the compiled version of fix this second attempt to force a
blackholed function with the same thread is detected and a
NonTermination exception thrown.
In GHCi though, blackhole detection doesn't work. So the thread blocks
forever. (if you look at your cpu and memory you'll notice nothing is
being consumed since its not looping but blocked). The reason it
doesn't work in GHCi is more a bug than some fundamental limitation.
See bug report:
http://hackage.haskell.org/trac/ghc/ticket/2786
Cheers,
David
dm-list-class-11aucs2
At Mon, 28 Nov 2011 21:44:03 -0800,
Alex M wrote:
> So I'm quite confused by all this. Also, it's not clear to me how
> recursion is "implemented using the fixed-point combinator" in the
> "Background: recursive bindings" slide.
> Any clarification on the above would be appreciated.
I have nothing to add to David T's great explanation of why the two
definitions of fix fail differently. I will say that I find your fix'
function easier to understand, and would have shown that in lecture if
not for the memory issues. However, if you find:
fix' f = f (fix' f)
easier to understand, then I think it's fair to imagine that this is
how fix is defined, except that fix has some optimization you don't
care about for understanding how code works.
Now as to how fixed point combinators allow you to implement
recursion, this is also a good question. First off, what do I even
mean by implementing recursion? Well, recursion is when you have a
binding or set of bindings, and the set of symbols on the left hand
side can also be used on the right-hand side. The two examples I gave
are:
x = (1, snd y)
y = (fst x, 2)
and
fibList = 1 : 1 : zipWith (+) fibList (tail fibList)
Now by implement recursion I meant implement something equivalent to
the above two code fragments (i.e., that the above two fragments can
be mechanically translated to), but in which the symbols to the left
of the equals sign do not appear to the right of the equals sign.
How does the fixed-point combinator help? Well, it lets you have two
names for the same value, so you can use one name to the right of the
equals sign, and another to the left. In particular, consider this
translation of the definition of x and y:
(x, y) = fix $ \ ~(x0, y0) -> let x1 = (1, snd y0)
y1 = (fst x0, 2)
in (x1, y1)
Consider just the let statement: If you replace both x0 and x1 with
x, and replace both y0 and y1 with y, you end up with something
identical to the original recursive definition above. But now think
about what a fixed-point combinator does--it ensures the input value
of the function is the same as the output value. So that means that
indeed x0 = x1 and y0 = y1, and thus the above fix call is equivalent
to the recursive code.
Now why does this work? Well, if you think about the way fix is
implemented, it passes in a thunk that causes an extra copy of the
function to be evaluated. So in the above code, when the system goes
to evaluate "snd y0", it causes another copy of the function to be
executed. This second evaluation returns:
((1, another-recursive-call), (another-recursive-call, 2))
Forcing either of the thunks marked "another-recursive-call" would
cause yet another copy of the function to be evaluated. Fortunately,
this isn't necessary, since the code is only asking about the slots
containing 1 and 2, so the recursion terminates.
So far we've considered cases in which the recursion happens exactly
once, or in which it happens infinitely and the program diverges.
However, in the case of functions, recursion often happens some finite
number of times. Consider the following code:
fact :: Integer -> Integer
fact = \n -> if n == 0 then 1 else n * fact (n - 1)
This is a straight-ahead recursive definition of factorial. (I've
just put the \n to the right of the = for clarity with what follows.)
Now consider this code:
ffact :: (Integer -> Integer) -> Integer -> Integer
ffact f = \n -> if n == 0 then 1 else n * f (n - 1)
What is "fix ffact"? Well, fix ffact should return a particular value
of x such that x = ffact x, right (since fix f = let x = f x in x)?
Well what happens if we expand the definition of ffact x on the right
hand side of that equation?
x = ffact x
==> x = \n -> if n == 0 then 1 else n * x (n - 1)
But wait a second, x now has the exact same (recursive) definition as
fact above, so x is the factorial function. Another way to look at
this, which I think makes it seem a lot less magical and easier to
understand, is if you imagine using your definition of fix'. Let's
expand fix' ffact:
fix' ffact
==> \n -> if n == 0 then 1 else n * (fix' ffact) (n - 1)
The key behavior of fix' is that it is self-replicating. Every time
you force the evaluation of fix' ffact, it spits out another copy the
function ffact, where ffact's argument f is another, identical copy of
"fix' ffact". So you see that expanding, say, "fix' f 5" will cause
"fix' f" to be expanded 6 times (for n = 5, 4, 3, 2, 1, 0), and when
finally n = 0, there will be no need for further expansion and the
computation can terminate.
![The Art of Computer Programming,Volume 4, Fascicle 2: Generating All Tuples and Permutations[日本語版] (アスキー・アジソンウェスレイシリーズ)](http://ecx.images-amazon.com/images/I/4176EYEPY0L._SL160_.jpg)
