Infinite fibonacci sequence on wiki

[Graham Fawcett]

Hi folks,

On the wiki, this example is offered as an "infinite seq of
fibonaccis":

(def fib-seq
(concat
[0 1]
((fn rfib [a b]
(lazy-cons (+ a b) (rfib b (+ a b)))) 0 1)))

Yet it leaks memory: calling (nth fib-seq N) for a large N results in
an OutOfMemoryError.

I know that the JVM does not offer tail-call optimization, but is
there a way to rewrite the example (perhaps with (recur ...)) so that
(nth fib-seq N) runs in constant space?

Thanks,
Graham

[Graham Fawcett]

On Jun 16, 12:24 pm, Graham Fawcett <graham.fawc...@gmail.com> wrote:
> I know that the JVM does not offer tail-call optimization, but is
> there a way to rewrite the example (perhaps with (recur ...)) so that
> (nth fib-seq N) runs in constant space?

I wanted to add that this would be a good case for a closure with a
mutable lexical environment. One could implement a fibonacci generator
using (repeatedly) and a closure that referred to the last two
generated elements in the sequence. Is there a way to do this in
Clojure?

Graham

[Christophe Grand]

Graham Fawcett a écrit :

> Yet it leaks memory: calling (nth fib-seq N) for a large N results in
> an OutOfMemoryError.
>

What you get is a java.lang.OutOfMemoryError: Java heap space and not a
stack overflow: you get out of memory because:
- the sequence is memoized
- the sequence is rooted (for the GC) and thus can't be reclaimed.

> I know that the JVM does not offer tail-call optimization, but is
> there a way to rewrite the example (perhaps with (recur ...)) so that
> (nth fib-seq N) runs in constant space?
>

Turning the seq into a fn will allow it to be reclaimed and thus the
computation will run in constant space.

(defn fib-seq[]

(concat
[0 1]
((fn rfib [a b]
(lazy-cons (+ a b) (rfib b (+ a b)))) 0 1)))

(let [r (nth (fib-seq) 100000)] r)

(The let is here to prevent the Repl to retain the sequence -- I don't know why teh Repl keeps a reference to the computed value of the arg.)

Christophe

[Graham Fawcett]

On Jun 16, 1:07 pm, Christophe Grand <christo...@cgrand.net> wrote:
> Graham Fawcett a écrit :> Yet it leaks memory: calling (nth fib-seq N) for a large N results in
> > an OutOfMemoryError.
>
> What you get is a java.lang.OutOfMemoryError: Java heap space and not a
> stack overflow: you get out of memory because:
> - the sequence is memoized
> - the sequence is rooted (for the GC) and thus can't be reclaimed.

Ah, that makes sense. Thanks for the clarification.

> > I know that the JVM does not offer tail-call optimization, but is
> > there a way to rewrite the example (perhaps with (recur ...)) so that
> > (nth fib-seq N) runs in constant space?
>
> Turning the seq into a fn will allow it to be reclaimed and thus the
> computation will run in constant space.
>
> (defn fib-seq[]
>
>   (concat
>    [0 1]
>    ((fn rfib [a b]
>         (lazy-cons (+ a b) (rfib b (+ a b)))) 0 1)))
>
> (let [r (nth (fib-seq) 100000)] r)
>
> (The let is here to prevent the Repl to retain the sequence -- I don't know why teh Repl keeps a reference to the computed value of the arg.)

Hm, REPLs in some other languages let you refer to earlier
computations made in the REPL (e.g. an asterisk, in SBCL, can be used
to refer to the previous computation). I wonder whether the same is
happening in the Clojure REPL?

Thanks again,
Graham

[Graham Fawcett]

On Jun 16, 1:07 pm, Christophe Grand <christo...@cgrand.net> wrote:

> Graham Fawcett a écrit :> Yet it leaks memory: calling (nth fib-seq N) for a large N results in
> > an OutOfMemoryError.
>
> What you get is a java.lang.OutOfMemoryError: Java heap space and not a
> stack overflow: you get out of memory because:
> - the sequence is memoized
> - the sequence is rooted (for the GC) and thus can't be reclaimed.
>
> > I know that the JVM does not offer tail-call optimization, but is
> > there a way to rewrite the example (perhaps with (recur ...)) so that
> > (nth fib-seq N) runs in constant space?
>
> Turning the seq into a fn will allow it to be reclaimed and thus the
> computation will run in constant space.
>
> (defn fib-seq[]
>
>   (concat
>    [0 1]
>    ((fn rfib [a b]
>         (lazy-cons (+ a b) (rfib b (+ a b)))) 0 1)))
>
> (let [r (nth (fib-seq) 100000)] r)

Hm, sadly it does not work: I still run out of heap space, running
this version of the code.

Graham

[Christophe Grand]

Graham Fawcett a écrit :

> Hm, sadly it does not work: I still run out of heap space, running
> this version of the code.
>

Did you restart the Repl after the first OoM?

Christophe

[Graham Fawcett]

Yes, I did. I tried it on 3 machines -- fortunately, on the third one
(which has a fairly recent Clojure from svn head) your code worked as
advertised, in constant space (thanks). But the first two machines I
tried were older versions of Clojure, and both failed with an
OutOfMemory.

I'll update them and try again, to verify that the code was sensitive
to the Clojure version.

Thanks,
Graham

[Graham Fawcett]

Updating to svn head (r906) did not help on one of the machines; that
one is running java 1.5.0_10 on Intel/Linux, but still runs out of
heap. I cannot update clojure on the other "bad" machine right now,
which was running java 1.6x on win32. My "good" machine was Intel/
Linux running Java 1.6.0_03 (it calculated the millionth Fibonacci in
constant space, after a nice long wait). Strange.

Graham

[Christophe Grand]

Graham Fawcett a écrit :

> Updating to svn head (r906) did not help on one of the machines; that
> one is running java 1.5.0_10 on Intel/Linux, but still runs out of
> heap. I cannot update clojure on the other "bad" machine right now,
> which was running java 1.6x on win32. My "good" machine was Intel/
> Linux running Java 1.6.0_03 (it calculated the millionth Fibonacci in
> constant space, after a nice long wait). Strange.
>

I tried on some computers but can't report failures here (1.6/linux
intel64, 1.5 and 1.6/solaris sparc64, 1.6/winxp intel32). Strange, indeed.

[Graham Fawcett]

Yes. I've narrowed it down somewhat; I installed the latest release on
the 1.6/winxp intel32, box, and it now works correctly. But svn head
on my 1.5.0_10/linux/intel32 still fails. It's a production box, so I
cannot upgrade Java at the moment, but will try later.

G

[Graham Fawcett]

For what it's worth, upgrading to java 1.6.0 did the trick -- no more
OutOfMemory error.

Graham

>
> G

[lpetit]

Hello,

As far as we go for concision, what do you think of this slightly more
concise definition (also seems more understandable at first to me) :

(defn fib-seq []
((fn rfib [a b]
(lazy-cons a (rfib b (+ a b))))
0 1))

Is there something wrong with this approach (maybe not using concat at
the front having some effect I did not see).
Because with the above definition you don't have any code repetition.

My 0.02 €,

--
Laurent

[toyvo]

Hi Clojurians,

> (defn fib-seq []
> ((fn rfib [a b]
> (lazy-cons a (rfib b (+ a b))))
> 0 1))

Can be roughly translated to Haskell as:

fix f = f (fix f)
fibs = 0 : 1 : fix (\rfib a b -> a+b : rfib b (a+b)) 0 1

Well, this function also eats up memory - my computer can't get to the
50000th number neither in Closure nor GHCi. GHCi could get there but
not much further with this slightly more Haskellish version:

fibs = 0 : 1 : [ a + b | (a, b) <- fibs `zip` tail fibs ]

It think this has nothing to do with the excellent Clojure
implementation - just with the fact that it takes a lot of memory to
handle numbers in the 1.68^100K range.


As to

> (defn fib-seq []
> ((fn rfib [a b]
> (lazy-cons a (rfib b (+ a b))))
> 0 1))

This is more concise but it isn't it "cheating" in that fib-seq is a
function, not a lazy sequence? :)


--A

[Graham Fawcett]

Hi,

On Mon, Jul 21, 2008 at 8:59 PM, toyvo <Anton.Ta...@gmail.com> wrote:

Hi Clojurians,

> (defn fib-seq []
>   ((fn rfib [a b]
>      (lazy-cons a (rfib b (+ a b))))
>     0 1))

Can be roughly translated to Haskell as:

fix f = f (fix f)
fibs = 0 : 1 : fix (\rfib a b -> a+b : rfib b (a+b)) 0 1

Well, this function also eats up memory - my computer can't get to the
50000th number neither in Closure nor GHCi. GHCi could get there but
not much further with this slightly more Haskellish version:

fibs = 0 : 1 : [ a + b | (a, b) <- fibs `zip` tail fibs ]

It think this has nothing to do with the excellent Clojure
implementation - just with the fact that it takes a lot of memory to
handle numbers in the 1.68^100K range.

One point six eight to the power of one hundred thousand? Yes, that might take a lot of memory! :-)
 

As to

> (defn fib-seq []
>   ((fn rfib [a b]
>      (lazy-cons a (rfib b (+ a b))))
>     0 1))

This is more concise but it isn't it "cheating" in that fib-seq is a
function, not a lazy sequence? :)

No cheating. Both your Haskell and Clojure examples are function definitions. Under the covers, your Haskell code defines a thunk (a zero-argument function) that memoizes its result (the head of a lazy list) -- the memoization occurs because it's a toplevel definition. Because it's a thunk, it will never be evaluated until you call 'fibs' in your Haskell program. You can confirm this at the GHCi prompt:

Prelude> let fibs = 0 : 1 : [ a + b | (a, b) <- fibs `zip` tail fibs ]
Prelude> :print fibs
fibs = (_t4::[Integer])

... where :print displays a value without forcing its evaluation. In this case the value of 'fibs' is the thunk with the label _t4. Once we force evaluation of part of the list:

Prelude> take 10 fibs
[0,1,1,2,3,5,8,13,21,34]
Prelude> :print fibs
fibs = 0 : 1 : 1 : 2 : 3 : 5 : 8 : 13 : 21 : 34 : (_t6::[Integer])

...we see that fibs has memoized the first part of the list, but the tail of it is still a thunk (_t6). A memoized lazy sequence in Clojure would have a similar structure.

So the memoization is the biggest difference, I'd say, not the function/sequence stuff. As you noted, the memory-eating behaviour isn't specific to one language or the other, but is due to the fact that you're building (and not reclaiming any of) a very large data structure. Just as you could write a memoizing Clojure version, you could write a non-memoizing Haskell version -- no cheating here, just a programmer decision to be made.

Best,
Graham

[toyvo]

Sorry for not being clear, the "cheating" part is a very minor
complaint of mine, that fibs-seq is a function type, e.g. you can't
(nth 10000 fib-seq) but rather (nth 10000 (fib-seq)). This is easily
fixed:

(def fibs (fibs-seq))

Sorry for nitpicking.

--A

[toyvo]

Hi!

While we are at it, I took 1.68^100K as a rough estimate because fib
n / fib (n-1) converges to ~1.68. But how much memory does that take?
Less then 2^100K which is (naively) (log2 (2^100K)) = 100K (bits) or ~
10 kilobytes. That shouldn't be too much? The program really needs to
keep in memory only two numbers like that. Actual memory use seems
much higher. Anyone knows what's behind the hood?

--A

[Graham Fawcett]

On Tue, Jul 22, 2008 at 10:30 AM, toyvo <Anton.Ta...@gmail.com> wrote:

Sorry for not being clear, the "cheating" part is a very minor
complaint of mine, that fibs-seq is a function type, e.g. you can't
(nth 10000 fib-seq) but rather (nth 10000 (fib-seq)). This is easily
fixed:

(def fibs (fibs-seq))

Sorry for nitpicking.

Ah. Yes, I'd call that a decision rather than a cheat. :-)

Re: 1.68^100K -- sorry, I had read hastily and misunderstood you. (I don't know about Java bignum internals, so can't help there.)

Best,
Graham