6 ms·

Can't mention Fibonacci and memoization in the same sentence without me breaking out my favorite Python party trick: def fib(n, cache = {0: 0, 1: 1}):

Can't mention Fibonacci and memoization in the same sentence without me breaking out my favorite Python party trick: def fib(n, cache = {0: 0, 1: 1}): if n not in cache: cache[n] = fib(n-1) + fib(n-2) return cache[n]

jaggederest 2y ago
The directly translated ruby version (from stack overflow of course) is even shorter: def fib(n, cache=Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }) cache[n] end It runs out of stack around 7146 on my machine at least. The python one is limited by the recursion depth limit in my test but of course that's configurable at your own risk.
- vidarh 2y ago
  If you're first going to golf it, endless-def: def fib(n, cache=Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }) = cache[n]
  - jaggederest 2y ago
    It's actually kind of ungolfed. The default version would be just fib = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] } fib[7145]
    - inopinatus 2y ago
      This is the proper Ruby form since it relies on the [] operator and is therefore substitutable for any other callable esp. procs/lambdas, and able to wrap them as well. This isn’t just golf, it’s an excellent way to pass around a lazily computed, self-caching closure. I use it often in preference to memoization gems. Aside from noting the false/nil equivalence concern, the original article seems over-engineered to me. Excessive metaprogramming is a common trap for Ruby devs.
  - nyrikki 2y ago
    IMHO, the mamul form is even better for golf, F(n) in O(n log n)
- x86x87 2y ago
  RUBY_THREAD_VM_STACK_SIZE for Ruby
- jez 2y ago
  The Python version and this Ruby version are not equivalent. In Ruby, default parameters are allocated for each call to the function, which means that they are not shared across calls. In Python, default parameters are allocated once and shared across all calls, allowing them to be mutated. This becomes obvious if we change the Python and Ruby versions to print when they're computing something that is not yet cached. For back-to-back calls to `fib(10)`, the Python version prints only on the first call to `fib(10)`. The Ruby version must recompute all values from 2 – 10 again.
- deleted 2y ago
  [deleted]
- technion 2y ago
  It's definitely something I remember being interested to find out about the hard way. Every recursion class talks about the Fib algorithm and why it's nice with recursion. But the iterative version doesn't have these stack limitations, presumably uses less memory and is just as fast. Doesn't that make it a better implementation?
  - Jtsummers 2y ago
    > Every recursion class talks about the Fib algorithm and why it's nice with recursion. It is nice with recursion in the sense that it's a straightforward, easy algorithm (what college CS student doesn't know basic arithmetic?) that illustrates recursion. It's also trivial to write the recursive version based on the mathematical definition. It is not nice in that it's very slow and blows up due to the exponential growth of the recursive calls. No one outside of CS 101 or an algorithms class is going to ever write the recursive version again. But that not-nice aspect makes it nice again, because it's a good jumping off point in how to improve an algorithm's runtime by understanding its structure (the iterative version) or throwing more memory at it (the memoized version). > But the iterative version doesn't have these stack limitations, presumably uses less memory and is just as fast. There is no "presumably", unless you store every Fibonacci number and not just the last two, the iterative Fibonacci does use less memory than the naive recursive Fibonacci. And there's no "just as fast". The iterative Fibonacci is faster, unless you've done something horribly wrong. It runs in linear time wrt N rather than exponential. If your linear algorithm is only just as fast as an exponential one, you haven't made a linear algorithm. > Doesn't that make it a better implementation? Yes, obviously. Which is why after CS 101 or an algorithms class you pretty much never write anything like that except maybe as a prototype. "This recursive program follows the definition closely, but it blows up memory/time." Start there and improve is a very reasonable thing. Start there and stop is just silly.
  - eru 2y ago
    The stack is just an implementation detail of some languages. Some other languages have non-broken function calls, and don't need to grow the stack for all of them. In those languages, you don't need to have loops as built-in to work around broken function calls. You can just write your own loops as library functions. (Of course, the naive recursive definition of Fibonacci would still be slow. You'd want to write a version that can be efficiently evaluated. You are already familiar with the linear time version in the iterative form. You can also write a logarithmic time version of Fibonacci.)
- macrocosmos 2y ago
  This is fun. Just wanted to say that both my 64 gb desktop and my 16 gb of RAM laptop reach the same stack limit at exactly 7692 when using pry. And reached the limit at 7694 with irb.
azhenley 2y ago
That’s beautiful. Why didn’t I think of that?!
- rplnt 2y ago
  Probably because not using mutable default arguments is python 101. Just something you don't do or think about. But this is indeed clever use of that gotcha.
kccqzy 2y ago
You should see the Mathematica version: fibonacci[0] = 0; fibonacci[1] = 1; fibonacci[n_] := fibonacci[n] = fibonacci[n-1] + fibonacci[n-2] It cleverly uses both = and := together. Usually people use = for immediate assignment (such as constants) and := for delayed assignment (such as functions) but this combines the two.
kazinator 2y ago
Does that work due to Ruby having Python-like broken semantics for evaluating the default value expressions for optional arguments? (I have no idea.) Or does it work due to the object denoted by {...} being a real literal? If the default value expression is evaluated on each call to the function in which it is required rather than at function definition time, and if the { ... } syntax is a constructor that creates a fresh object, then this wouldn't work; one of those two conditions (or both) must be broken.
- x3n0ph3n3 2y ago
  Python's default argument is evaluated once. It's very sibtle behavior that is inlile Ruby.
kazinator 2y ago
TXR Lisp version: (defun fib (n : (cache #H(() (0 1) (1 1)))) (or [cache n] (set [cache n] (+ (fib (pred n)) (fib (ppred n)))))) TXR Lisp does not have broken Python semantics for evaluating the default expressions for optional arguments. The expressions are freshly evaluated on each call in which they are needed, in the lexical scope in in which the prior parameters are already visible, as well as the scope surrounding the function definition. Why this works is that the #H hash literal syntax is a true literal. Every time that expression is evaluated, it yields the same hash table, which is mutable. This wouldn't work in an implementation of TXR Lisp in which literals are put into a ROM image or mapped into read only virtual memory. We will not likely see such a thing any time soon. If we change #H(...) to, say, (hash-props 0 1 1 1), it won't work any more.
- PittleyDunkin 2y ago
  > Why this works is that the #H hash literal syntax is a true literal. Every time that expression is evaluated, it yields the same hash table, which is mutable. While this is cool and I think I grok the semantics, the identification of it as a "true literal" has me scratching my head. To me a literal is a syntactical term, so putting a literal into a rom image only makes sense in terms of storing the source itself (which is not necessary most of the time, but might make sense in a lisp). First-class support for partial evaluation looks really cool. I've been playing around with a scheme dialect built around this very concept.
  - kazinator 2y ago
    A literal is not purely a syntactical term. A literal is an object that is embedded in the program itself. As such, it is necessarily part of the syntax: the piece of syntax denoting the literal is understood to be that object itself. However, note that syntax disappears when the program is compiled. The literal itself does not!!! (Unless identified as dead code and eliminated, of course). Even using the C language as an example we can readily distinguish between literal syntax and semantics. The string literal syntas "abc\n" includes the double quotes and backslash. Yet the string literal object at run time has no double quotes or backslash, and the n after the backslash was turned into a newline (linefeed in ASCII). (C compilers on Unix-like platforms do in fact map string literals to read-only memory. It's not ROM, but wite-protected VM. Firmwares written in C being burned into ROM are thing also. The literals are then in ROM.) In Lisp, we think of the objects as being source code, so it's a little different. The C idea of the double quotes and backslash being source is called "read syntax" in Lisp, particularly Common Lisp. Scheme might use "read syntax", I'm not sure. In any case, "surface syntax" or "character-level syntax" are also useful synonyms. Note Lisp compilers and interpreters take the scanned-surface-syntax-turned-object as their input. We could call that deep syntax. So a quoted literal is literally a chunk of the deep syntax, turned into a datum for the program: (quote X) embeds the syntax X into the program, making it available as a datum, and the compiler will process that quote construct by propagating X as is into the compiled image, arranging it to be part of some table or literals or whatever. Some object are self-quoting, like numbers of strings, or #(...) vectors in Common Lisp and Scheme. The TXR Lisp #H(...) hash syntax is like this. If it appears as an evaluated expression in code, then it is a literal. The compiler must propagate that to the compiled image, just like a vector, string, or number.
ngcazz 2y ago
Have always appreciated Haskell's tail-recursive one fib = (fibs !!) where fibs = 0 : 1 : zipWith (+) fibs (tail fibs) main = putStrLn $ show $ fib 1000
- bmacho 2y ago
  You probably just jest, either way fibs is not tail recursive [0], since its returning value is a list constructor, and not a call to itself. [0] : https://stackoverflow.com/questions/33923/what-is-tail-recursion https://stackoverflow.com/questions/33923/what-is-tail-recur...
  - ngcazz 2y ago
    No jest, I just recalled this formulation incorrectly as being tail-recursive. Thanks for reminding me.
darrenf 2y ago
Not memoization, but I like the Raku version: $ raku -e 'my @fib = 0,1,{$^a + $^b} ... *; @fib[0..40].say' (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155)
- librasteve 2y ago
  sorry couldn't resist... raku -e '(0,1,*+*...*)[^40] .say'
klysm 2y ago
I’ve been bitten by this behavior before where default argument values are shared across invocations.

jaggederest 2y ago

The directly translated ruby version (from stack overflow of course) is even shorter: def fib(n, cache=Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }) cache[n] end It runs out of stack around 7146 on my machine at least. The python one is limited by the recursion depth limit in my test but of course that's configurable at your own risk.

vidarh 2y ago
If you're first going to golf it, endless-def: def fib(n, cache=Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }) = cache[n]
- jaggederest 2y ago
  It's actually kind of ungolfed. The default version would be just fib = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] } fib[7145]
  - inopinatus 2y ago
    This is the proper Ruby form since it relies on the [] operator and is therefore substitutable for any other callable esp. procs/lambdas, and able to wrap them as well. This isn’t just golf, it’s an excellent way to pass around a lazily computed, self-caching closure. I use it often in preference to memoization gems. Aside from noting the false/nil equivalence concern, the original article seems over-engineered to me. Excessive metaprogramming is a common trap for Ruby devs.
- nyrikki 2y ago
  IMHO, the mamul form is even better for golf, F(n) in O(n log n)
x86x87 2y ago
RUBY_THREAD_VM_STACK_SIZE for Ruby
jez 2y ago
The Python version and this Ruby version are not equivalent. In Ruby, default parameters are allocated for each call to the function, which means that they are not shared across calls. In Python, default parameters are allocated once and shared across all calls, allowing them to be mutated. This becomes obvious if we change the Python and Ruby versions to print when they're computing something that is not yet cached. For back-to-back calls to `fib(10)`, the Python version prints only on the first call to `fib(10)`. The Ruby version must recompute all values from 2 – 10 again.
deleted 2y ago
[deleted]
technion 2y ago
It's definitely something I remember being interested to find out about the hard way. Every recursion class talks about the Fib algorithm and why it's nice with recursion. But the iterative version doesn't have these stack limitations, presumably uses less memory and is just as fast. Doesn't that make it a better implementation?
- Jtsummers 2y ago
  > Every recursion class talks about the Fib algorithm and why it's nice with recursion. It is nice with recursion in the sense that it's a straightforward, easy algorithm (what college CS student doesn't know basic arithmetic?) that illustrates recursion. It's also trivial to write the recursive version based on the mathematical definition. It is not nice in that it's very slow and blows up due to the exponential growth of the recursive calls. No one outside of CS 101 or an algorithms class is going to ever write the recursive version again. But that not-nice aspect makes it nice again, because it's a good jumping off point in how to improve an algorithm's runtime by understanding its structure (the iterative version) or throwing more memory at it (the memoized version). > But the iterative version doesn't have these stack limitations, presumably uses less memory and is just as fast. There is no "presumably", unless you store every Fibonacci number and not just the last two, the iterative Fibonacci does use less memory than the naive recursive Fibonacci. And there's no "just as fast". The iterative Fibonacci is faster, unless you've done something horribly wrong. It runs in linear time wrt N rather than exponential. If your linear algorithm is only just as fast as an exponential one, you haven't made a linear algorithm. > Doesn't that make it a better implementation? Yes, obviously. Which is why after CS 101 or an algorithms class you pretty much never write anything like that except maybe as a prototype. "This recursive program follows the definition closely, but it blows up memory/time." Start there and improve is a very reasonable thing. Start there and stop is just silly.
- eru 2y ago
  The stack is just an implementation detail of some languages. Some other languages have non-broken function calls, and don't need to grow the stack for all of them. In those languages, you don't need to have loops as built-in to work around broken function calls. You can just write your own loops as library functions. (Of course, the naive recursive definition of Fibonacci would still be slow. You'd want to write a version that can be efficiently evaluated. You are already familiar with the linear time version in the iterative form. You can also write a logarithmic time version of Fibonacci.)
macrocosmos 2y ago
This is fun. Just wanted to say that both my 64 gb desktop and my 16 gb of RAM laptop reach the same stack limit at exactly 7692 when using pry. And reached the limit at 7694 with irb.

azhenley 2y ago

That’s beautiful. Why didn’t I think of that?!

rplnt 2y ago
Probably because not using mutable default arguments is python 101. Just something you don't do or think about. But this is indeed clever use of that gotcha.

kccqzy 2y ago

You should see the Mathematica version: fibonacci[0] = 0; fibonacci[1] = 1; fibonacci[n_] := fibonacci[n] = fibonacci[n-1] + fibonacci[n-2] It cleverly uses both = and := together. Usually people use = for immediate assignment (such as constants) and := for delayed assignment (such as functions) but this combines the two.

kazinator 2y ago

Does that work due to Ruby having Python-like broken semantics for evaluating the default value expressions for optional arguments? (I have no idea.) Or does it work due to the object denoted by {...} being a real literal? If the default value expression is evaluated on each call to the function in which it is required rather than at function definition time, and if the { ... } syntax is a constructor that creates a fresh object, then this wouldn't work; one of those two conditions (or both) must be broken.

x3n0ph3n3 2y ago
Python's default argument is evaluated once. It's very sibtle behavior that is inlile Ruby.

kazinator 2y ago

TXR Lisp version: (defun fib (n : (cache #H(() (0 1) (1 1)))) (or [cache n] (set [cache n] (+ (fib (pred n)) (fib (ppred n)))))) TXR Lisp does not have broken Python semantics for evaluating the default expressions for optional arguments. The expressions are freshly evaluated on each call in which they are needed, in the lexical scope in in which the prior parameters are already visible, as well as the scope surrounding the function definition. Why this works is that the #H hash literal syntax is a true literal. Every time that expression is evaluated, it yields the same hash table, which is mutable. This wouldn't work in an implementation of TXR Lisp in which literals are put into a ROM image or mapped into read only virtual memory. We will not likely see such a thing any time soon. If we change #H(...) to, say, (hash-props 0 1 1 1), it won't work any more.

PittleyDunkin 2y ago
> Why this works is that the #H hash literal syntax is a true literal. Every time that expression is evaluated, it yields the same hash table, which is mutable. While this is cool and I think I grok the semantics, the identification of it as a "true literal" has me scratching my head. To me a literal is a syntactical term, so putting a literal into a rom image only makes sense in terms of storing the source itself (which is not necessary most of the time, but might make sense in a lisp). First-class support for partial evaluation looks really cool. I've been playing around with a scheme dialect built around this very concept.
- kazinator 2y ago
  A literal is not purely a syntactical term. A literal is an object that is embedded in the program itself. As such, it is necessarily part of the syntax: the piece of syntax denoting the literal is understood to be that object itself. However, note that syntax disappears when the program is compiled. The literal itself does not!!! (Unless identified as dead code and eliminated, of course). Even using the C language as an example we can readily distinguish between literal syntax and semantics. The string literal syntas "abc\n" includes the double quotes and backslash. Yet the string literal object at run time has no double quotes or backslash, and the n after the backslash was turned into a newline (linefeed in ASCII). (C compilers on Unix-like platforms do in fact map string literals to read-only memory. It's not ROM, but wite-protected VM. Firmwares written in C being burned into ROM are thing also. The literals are then in ROM.) In Lisp, we think of the objects as being source code, so it's a little different. The C idea of the double quotes and backslash being source is called "read syntax" in Lisp, particularly Common Lisp. Scheme might use "read syntax", I'm not sure. In any case, "surface syntax" or "character-level syntax" are also useful synonyms. Note Lisp compilers and interpreters take the scanned-surface-syntax-turned-object as their input. We could call that deep syntax. So a quoted literal is literally a chunk of the deep syntax, turned into a datum for the program: (quote X) embeds the syntax X into the program, making it available as a datum, and the compiler will process that quote construct by propagating X as is into the compiled image, arranging it to be part of some table or literals or whatever. Some object are self-quoting, like numbers of strings, or #(...) vectors in Common Lisp and Scheme. The TXR Lisp #H(...) hash syntax is like this. If it appears as an evaluated expression in code, then it is a literal. The compiler must propagate that to the compiled image, just like a vector, string, or number.

ngcazz 2y ago

Have always appreciated Haskell's tail-recursive one fib = (fibs !!) where fibs = 0 : 1 : zipWith (+) fibs (tail fibs) main = putStrLn $ show $ fib 1000

bmacho 2y ago
You probably just jest, either way fibs is not tail recursive [0], since its returning value is a list constructor, and not a call to itself. [0] : https://stackoverflow.com/questions/33923/what-is-tail-recursion https://stackoverflow.com/questions/33923/what-is-tail-recur...
- ngcazz 2y ago
  No jest, I just recalled this formulation incorrectly as being tail-recursive. Thanks for reminding me.

darrenf 2y ago

Not memoization, but I like the Raku version: $ raku -e 'my @fib = 0,1,{$^a + $^b} ... *; @fib[0..40].say' (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155)

librasteve 2y ago
sorry couldn't resist... raku -e '(0,1,*+*...*)[^40] .say'

klysm 2y ago

I’ve been bitten by this behavior before where default argument values are shared across invocations.