Tail call optimization

Help & Support
1

Hi
I am new to crystal and trying small programming exercises to understand the language.
This exercise is about use tail recursion to implement Fibonacci series.

def fib(n, x = 1_i64, y = 1_i64)
  n <= 1 ? y : fib(n - 1, y, x + y)
end

puts fib(46)

it works, but it can be called wrong, like so fib(42, 2, 4)

what i want to be able to do is something like

def fib(n)
  def fib_impl(n, x = 1_i64, y = 1_i64)
    n <= 1 ? y : fib_impl(n - 1, y, x + y)
  end
  fib_impl(n)
end

puts fib(46)

How can i achieve something like this?
Thanks

2 
def fib(n)
  fib(n, 1, 1)
end

private def fib(n, a, b)
  n <= 1 ? b : fib(n - 1, b, a + b)
end

def fib(n : Int64)
  fib = nil
  fib = ->(n : Int64, a : Int64, b : Int64) { n <= 1 ? b : fib.not_nil!.call(n - 1, b, a + b) }
  fib.not_nil!.call(n, 1i64, 1i64)
end
3

Thank you!
I tried the private implementation approach.
What i really wanted was your second solution, a way to use procs.

Thanks for your time!!!

4

I do prefer the private approach personally, I think it’s a little cleaner :)

1 Like
5

Just exploring the crystal toolbox.
I wanted to learn how to call a proc recursively. thanks for showing me the fib = nil trick

6

Admittedly it shouldn’t be necessary. There’s nothing wrong with a proc capturing a local variable it’s being assigned to.

7

@radha I don’t think that llvm’s tail call optimization explained in http://llvm.org/docs/CodeGenerator.html#tail-call-optimization will be applied. We don’t meet those requirements.

If you want to see how the call is emitted in llvm, a slightly modified version of the program that can be compiled without the std-lib prelude can be compiled without debug information and with either --emit=llvm-ir or DUMP=1

def fib(n, x = 1_i64, y = 1_i64)
  n <= 1 ? y : fib(n &- 1, y, x &+ y)
end

fib(46)

$ DUMP=1 crystal build --prelude=empty --no-debug foo.cr

; Function Attrs: uwtable
define i64 @"*fib<Int32, Int64, Int64>:Int64"(i32 %n, i64 %x, i64 %y) #0 {
entry:
  %0 = icmp sle i32 %n, 1
  br i1 %0, label %then, label %else

then:                                             ; preds = %entry
  br label %exit

else:                                             ; preds = %entry
  %1 = sub i32 %n, 1
  %2 = add i64 %x, %y
  %3 = call i64 @"*fib<Int32, Int64, Int64>:Int64"(i32 %1, i64 %y, i64 %2)
  br label %exit

exit:                                             ; preds = %else, %then
  %4 = phi i64 [ %y, %then ], [ %3, %else ]
  ret i64 %4
}
1 Like
8

I actually was curious about this exact question the other day! For a simple Fibonacci implementation like the first one I had above (I didn’t check for the second one), in --release mode LLVM does actually turn it into tail calls!

2 Likes
9

I am sorry, reading llvm-ir is out of my league, but i can confirm optimizations are applied in release builds.

> time ./fibonacci
2971215073

________________________________________________________
Executed in   10.56 secs   fish           external
   usr time   10.56 secs  825.00 micros   10.56 secs
   sys time    0.01 secs  189.00 micros    0.01 secs

> time ./fibonaccitail
2971215073

________________________________________________________
Executed in    9.61 millis    fish           external
   usr time    0.59 millis  589.00 micros    0.00 millis
   sys time   10.35 millis  141.00 micros   10.21 millis

maybe because i built crystal from source against llvm 10?

> crystal --version
Crystal 0.35.0-dev [9057e8d80] (2020-06-08)

LLVM: 10.0.0
Default target: x86_64-pc-linux-gnu

please let me know if i can provide any more details

1 Like