Computing Fibonacci Numbers

The following is an example that everyone likes, computing Fibonacci number recursively.

using NiLang

@i function rfib(out!, n::T) where T
    @routine begin
        n1 ← zero(T)
        n2 ← zero(T)
        n1 += n - 1
        n2 += n - 2
    end
    if (value(n) <= 2, ~)
        out! += 1
    else
        rfib(out!, n1)
        rfib(out!, n2)
    end
    ~@routine
end

The time complexity of this recursive algorithm is exponential to input n. It is also possible to write a reversible linear time with for loops. A slightly non-trivial task is computing the first Fibonacci number that greater or equal to a certain number z, where a while statement is required.

@i function rfibn(n!, z)
    @safe @assert n! == 0
    out ← 0
    rfib(out, n!)
    @from n! == 0 while out < z
        ~rfib(out, n!)
        n! += 1
        rfib(out, n!)
    end
    ~rfib(out, n!)
    out → 0
end

In this example, the postcondition n!=0 in the while statement is false before entering the loop, and it becomes true in later iterations. In the reverse program, the while statement stops at n==0. If executed correctly, a user will see the following result.

rfib(0, 10)

(55, 10)

compute which the first Fibonacci number greater than 100.

rfibn(0, 100)

(12, 100)

and uncompute

(~rfibn)(rfibn(0, 100)...)

(0, 100)

This example shows how an addition postcondition provided by the user can help to reverse a control flow without caching controls.

This page was generated using Literate.jl.