4 ms·

How would you code a tail recursive Fibonacci in LISP?

by jonsen 5y ago

gibsonf1 5y ago
I haven't looked at trying and don't really have time to, so I don't know, but with lisp, you can make anything fast as a general rule, very very fast. (at least with compiled sbcl)
emptybits 5y ago
There may be a faster or cleverer way to do it but here's a basic tail recursive fibonacci: (defun nth-fibonacci (n &optional (a 0) (b 1)) (if (= n 0) a (nth-fibonacci (- n 1) b (+ a b))))
- Jtsummers 5y ago
  Yep, that's how you'd do it. So long as your CL implementation supports tail call optimization, that will be on par with the same algorithm using loop or another looping construct.
- gibsonf1 5y ago
  WEB> (time (nth-fibonacci 9999)) Evaluation took: 0.005 seconds of real time 0.004520 seconds of total run time (0.000168 user, 0.004352 system) 100.00% CPU 13,120,881 processor cycles 4,716,256 bytes consed 20793608237133498072112648988642836825087036094015903119682945866528501423455686648927456034305226515591757343297190158010624794267250973176133810179902738038231789748346235556483191431591924532394420028067810320408724414693462849062668387083308048250920654493340878733226377580847446324873797603734794648258113858631550404081017260381202919943892370942852601647398213554479081823593715429566945149312993664846779090437799284773675379284270660175134664833266377698642012106891355791141872776934080803504956794094648292880566056364718187662668970758537383352677420835574155945658542003634765324541006121012446785689171494803262408602693091211601973938229446636049901531963286159699077880427720289235539329671877182915643419079186525118678856821600897520171070499437657067342400871083908811800976259727431820539554256869460815355918458253398234382360435762759823179896116748424269545924633204614137992850814352018738480923581553988990897151469406131695614497783720743461373756218685106856826090696339815490921253714537241866911604250597353747823733268178182198509240226955826416016690084749816072843582488613184829905383150180047844353751554201573833105521980998123833253261228689824051777846588461079790807828367132384798451794011076569057522158680378961532160858387223882974380483931929541222100800313580688585002598879566463221427820448492565073106595808837401648996423563386109782045634122467872921845606409174360635618216883812562321664442822952537577492715365321134204530686742435454505103269768144370118494906390254934942358904031509877369722437053383165360388595116980245927935225901537634925654872380877183008301074569444002426436414756905094535072804764684492105680024739914490555904391369218696387092918189246157103450387050229300603241611410707453960080170928277951834763216705242485820801423866526633816082921442883095463259080471819329201710147828025221385656340207489796317663278872207607791034431700112753558813478888727503825389066823098683355695718137867882982111710796422706778536913192342733364556727928018953989153106047379741280794091639429908796650294603536651238230626 WEB>
  - Jtsummers 5y ago
    You may want to put extra spaces in front of those lines, and also manually break up that massive number.
- weavie 5y ago
  SBCL doesn't optimize tail calls by default. If I recall you have to set the optimization level prior to compiling the function using `(declaim (optimize xxx))` - where xxx is something I've forgotten. Perhaps someone can come along and point out what xxx should be?
  - gibsonf1 5y ago
    Oh thats interesting!, we don't use that but use tail recursion extensively https://0branch.com/notes/tco-cl.html#sec-2-2 https://0branch.com/notes/tco-cl.html#sec-2-2
  - Jtsummers 5y ago
    ; disassembly for NTH-FIBONACCI ; Size: 94 bytes. Origin: #x2264E531 ; NTH-FIBONACCI ; 31: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 35: 488945F8 MOV [RBP-8], RAX ; 39: 488B55F0 MOV RDX, [RBP-16] ; 3D: 31FF XOR EDI, EDI ; 3F: E8AC343BFF CALL #x21A019F0 ; GENERIC-= ; 44: 750A JNE L0 ; 46: 488B55E8 MOV RDX, [RBP-24] ; 4A: 488BE5 MOV RSP, RBP ; 4D: F8 CLC ; 4E: 5D POP RBP ; 4F: C3 RET ; 50: L0: 488B55F0 MOV RDX, [RBP-16] ; 54: BF02000000 MOV EDI, 2 ; 59: E8C2323BFF CALL #x21A01820 ; GENERIC-- ; 5E: 488BC2 MOV RAX, RDX ; 61: 488945D8 MOV [RBP-40], RAX ; 65: 488B55E8 MOV RDX, [RBP-24] ; 69: 488B7DE0 MOV RDI, [RBP-32] ; 6D: E84E323BFF CALL #x21A017C0 ; GENERIC-+ ; 72: 488BF2 MOV RSI, RDX ; 75: 488B45D8 MOV RAX, [RBP-40] ; 79: 488BD0 MOV RDX, RAX ; 7C: 488B7DE0 MOV RDI, [RBP-32] ; 80: B906000000 MOV ECX, 6 ; 85: FF7508 PUSH QWORD PTR [RBP+8] ; 88: E99507DBFD JMP #x203FED22 ; #<FDEFN NTH-FIBONACCI> ; 8D: CC10 INT3 16 ; Invalid argument count trap Looks like it's doing tail call optimization to me, this is without doing anything special with declaim. Note that where it returns to the top is with JMP not CALL. http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion
lowbloodsugar 5y ago
If you were a non LISP programmer and thought "Fibonacci using recursion", you might think you'd have something like fib(a)=fib(a-1)+fib(a-2), and scoff at its possible performance, and also wonder how that would be tail call optimized. But as a LISP programmer, you'll think of this in the way a Java programmer would think of a loop, and just treat this as a count over two values n times, adding along the way. And this is why I don't like LISP: because I have programmed assembly and built up from there, and doing loops using tail call recursion seems to be a lie. It is a faulty abstraction. It is a loop. You'd be better off doing it in a loop, in any sane language, and if you do it right in LISP, the code will generate a loop in assembly language. Just the fact that this thread devolved into how to specify compiler options so that it actually generates that loop shows how absurd the whole thing is.
- oconnor663 5y ago
  I think the appeal of expressing loops with recursion is that it lets you to avoid mutation. But I agree with the point that Rust folks frequently make, about how being able to mutate things safely is a lot nicer than avoiding all mutation.
- dTal 5y ago
  Do "for" and "while" constructs also seem silly? After all they "compile to a loop" as well. The purpose of all these loop constructs is to place constraints on some essential aspect of the loop up front, thus narrowing the possible range of effects of that wicked goto, by encoding common patterns. "For" loops guarantee the number of iterations. "While" loops guarantee the exit condition. And tail recursion guarantees what state gets modified in the loop. It is strange the way you say "better off doing it in a loop". As you say, it is a loop. What construct would you prefer? GOTO?
- dunefox 5y ago
  And where exactly is the problem with the compiler rewriting tail calls into a loop on the assembly level? Calling this a "lie" is pretty childish.
randomswede 5y ago
If I absolutely had to write a recursive solution, something like this (should have all recursive calls in a tail position, may require trading debugability for speed): (defun tail-fib (n &optional (v0 0) (v1 1) (cond ((zerop n) v0) (t (tail-fib (1- n) v1 (+ v0 v1)))))
- jonsen 5y ago
  I don’t know much Lisp. Is that why I, except for syntax, see no difference from emptybits’s nth-fibonacci?
deleted 5y ago
[deleted]

How would you code a tail recursive Fibonacci in LISP?

by jonsen 5y ago

How would you code a tail recursive Fibonacci in LISP?

I haven't looked at trying and don't really have time to, so I don't know, but with lisp, you can make anything fast as a general rule, very very fast. (at least with compiled sbcl)

emptybits 5y ago

There may be a faster or cleverer way to do it but here's a basic tail recursive fibonacci: (defun nth-fibonacci (n &optional (a 0) (b 1)) (if (= n 0) a (nth-fibonacci (- n 1) b (+ a b))))

Jtsummers 5y ago
Yep, that's how you'd do it. So long as your CL implementation supports tail call optimization, that will be on par with the same algorithm using loop or another looping construct.
gibsonf1 5y ago
WEB> (time (nth-fibonacci 9999)) Evaluation took: 0.005 seconds of real time 0.004520 seconds of total run time (0.000168 user, 0.004352 system) 100.00% CPU 13,120,881 processor cycles 4,716,256 bytes consed 20793608237133498072112648988642836825087036094015903119682945866528501423455686648927456034305226515591757343297190158010624794267250973176133810179902738038231789748346235556483191431591924532394420028067810320408724414693462849062668387083308048250920654493340878733226377580847446324873797603734794648258113858631550404081017260381202919943892370942852601647398213554479081823593715429566945149312993664846779090437799284773675379284270660175134664833266377698642012106891355791141872776934080803504956794094648292880566056364718187662668970758537383352677420835574155945658542003634765324541006121012446785689171494803262408602693091211601973938229446636049901531963286159699077880427720289235539329671877182915643419079186525118678856821600897520171070499437657067342400871083908811800976259727431820539554256869460815355918458253398234382360435762759823179896116748424269545924633204614137992850814352018738480923581553988990897151469406131695614497783720743461373756218685106856826090696339815490921253714537241866911604250597353747823733268178182198509240226955826416016690084749816072843582488613184829905383150180047844353751554201573833105521980998123833253261228689824051777846588461079790807828367132384798451794011076569057522158680378961532160858387223882974380483931929541222100800313580688585002598879566463221427820448492565073106595808837401648996423563386109782045634122467872921845606409174360635618216883812562321664442822952537577492715365321134204530686742435454505103269768144370118494906390254934942358904031509877369722437053383165360388595116980245927935225901537634925654872380877183008301074569444002426436414756905094535072804764684492105680024739914490555904391369218696387092918189246157103450387050229300603241611410707453960080170928277951834763216705242485820801423866526633816082921442883095463259080471819329201710147828025221385656340207489796317663278872207607791034431700112753558813478888727503825389066823098683355695718137867882982111710796422706778536913192342733364556727928018953989153106047379741280794091639429908796650294603536651238230626 WEB>
- Jtsummers 5y ago
  You may want to put extra spaces in front of those lines, and also manually break up that massive number.
weavie 5y ago
SBCL doesn't optimize tail calls by default. If I recall you have to set the optimization level prior to compiling the function using `(declaim (optimize xxx))` - where xxx is something I've forgotten. Perhaps someone can come along and point out what xxx should be?
- gibsonf1 5y ago
  Oh thats interesting!, we don't use that but use tail recursion extensively https://0branch.com/notes/tco-cl.html#sec-2-2 https://0branch.com/notes/tco-cl.html#sec-2-2
- Jtsummers 5y ago
  ; disassembly for NTH-FIBONACCI ; Size: 94 bytes. Origin: #x2264E531 ; NTH-FIBONACCI ; 31: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer ; 35: 488945F8 MOV [RBP-8], RAX ; 39: 488B55F0 MOV RDX, [RBP-16] ; 3D: 31FF XOR EDI, EDI ; 3F: E8AC343BFF CALL #x21A019F0 ; GENERIC-= ; 44: 750A JNE L0 ; 46: 488B55E8 MOV RDX, [RBP-24] ; 4A: 488BE5 MOV RSP, RBP ; 4D: F8 CLC ; 4E: 5D POP RBP ; 4F: C3 RET ; 50: L0: 488B55F0 MOV RDX, [RBP-16] ; 54: BF02000000 MOV EDI, 2 ; 59: E8C2323BFF CALL #x21A01820 ; GENERIC-- ; 5E: 488BC2 MOV RAX, RDX ; 61: 488945D8 MOV [RBP-40], RAX ; 65: 488B55E8 MOV RDX, [RBP-24] ; 69: 488B7DE0 MOV RDI, [RBP-32] ; 6D: E84E323BFF CALL #x21A017C0 ; GENERIC-+ ; 72: 488BF2 MOV RSI, RDX ; 75: 488B45D8 MOV RAX, [RBP-40] ; 79: 488BD0 MOV RDX, RAX ; 7C: 488B7DE0 MOV RDI, [RBP-32] ; 80: B906000000 MOV ECX, 6 ; 85: FF7508 PUSH QWORD PTR [RBP+8] ; 88: E99507DBFD JMP #x203FED22 ; #<FDEFN NTH-FIBONACCI> ; 8D: CC10 INT3 16 ; Invalid argument count trap Looks like it's doing tail call optimization to me, this is without doing anything special with declaim. Note that where it returns to the top is with JMP not CALL. http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion http://www.sbcl.org/manual/index.html#Debug-Tail-Recursion

lowbloodsugar 5y ago

If you were a non LISP programmer and thought "Fibonacci using recursion", you might think you'd have something like fib(a)=fib(a-1)+fib(a-2), and scoff at its possible performance, and also wonder how that would be tail call optimized. But as a LISP programmer, you'll think of this in the way a Java programmer would think of a loop, and just treat this as a count over two values n times, adding along the way. And this is why I don't like LISP: because I have programmed assembly and built up from there, and doing loops using tail call recursion seems to be a lie. It is a faulty abstraction. It is a loop. You'd be better off doing it in a loop, in any sane language, and if you do it right in LISP, the code will generate a loop in assembly language. Just the fact that this thread devolved into how to specify compiler options so that it actually generates that loop shows how absurd the whole thing is.

oconnor663 5y ago
I think the appeal of expressing loops with recursion is that it lets you to avoid mutation. But I agree with the point that Rust folks frequently make, about how being able to mutate things safely is a lot nicer than avoiding all mutation.
dTal 5y ago
Do "for" and "while" constructs also seem silly? After all they "compile to a loop" as well. The purpose of all these loop constructs is to place constraints on some essential aspect of the loop up front, thus narrowing the possible range of effects of that wicked goto, by encoding common patterns. "For" loops guarantee the number of iterations. "While" loops guarantee the exit condition. And tail recursion guarantees what state gets modified in the loop. It is strange the way you say "better off doing it in a loop". As you say, it is a loop. What construct would you prefer? GOTO?
dunefox 5y ago
And where exactly is the problem with the compiler rewriting tail calls into a loop on the assembly level? Calling this a "lie" is pretty childish.

randomswede 5y ago

If I absolutely had to write a recursive solution, something like this (should have all recursive calls in a tail position, may require trading debugability for speed): (defun tail-fib (n &optional (v0 0) (v1 1) (cond ((zerop n) v0) (t (tail-fib (1- n) v1 (+ v0 v1)))))

jonsen 5y ago
I don’t know much Lisp. Is that why I, except for syntax, see no difference from emptybits’s nth-fibonacci?

deleted 5y ago

[deleted]