Re: Factor

About 14 years ago, I wrote about Fibonacci Wars which described the relative performance of three different methods of calculating Fibonacci numbers. Today, I wanted to address a style question that someone in the Factor Discord server asked:

How could I write this better?

: fib ( n -- f(n) ) 0 1 rot 1 - [ tuck + ] times nip ;

In a more concatenative style.

I’ve written before about conciseness, concatenative thinking and readability. I found this question to be a good prompt that provides another opportunity to address these topics.

Their suggested solution is an iterative one and is fairly minimal when it comes to “short code”. It uses less common shuffle words like tuck that users might not understand easily. It is probably true that even rot is more inscrutable to people coming from other languages.

Let’s look at some potential variations!

You could use simpler stack shuffling:

: fib ( n -- f(n) )
    [ 1 0 ] dip 1 - [ over + swap ] times drop ;

You could factor out the inner logic to another word:

: fib+ ( f(n-2) f(n-1) -- f(n-1) f(n) )
    [ + ] keep swap ;

: fib ( n -- f(n) )
    [ 0 1 ] dip 1 - [ fib+ ] times nip ;

You could use higher-level words like keepd:

: fib ( n -- f(n) )
    [ 1 0 ] dip 1 - [ [ + ] keepd ] times drop ;

You could use locals and use index 0 as the “first” fib number:

:: fib ( n -- f(n) )
    1 0 n [ [ + ] keepd ] times drop ;

You could write a recursive solution using memoization for improved performance:

MEMO: fib ( n -- f(n) )
    dup 2 < [ drop 1 ] [ [ 2 - fib ] [ 1 - fib ] bi + ] if ;

You could use local variables to make it look nicer:

MEMO:: fib ( n -- f(n) )
    n 2 < [ 1 ] [ n 2 - fib n 1 - fib + ] if ;

But, in many cases, beauty is in the eye of the beholder. And so you could start at a place where you find the code most readable, and that might even be something more conventional looking like this version that uses mutable locals and comments and whitespace to describe what is happening:

:: fib ( n -- f(n) )
    0 :> f(n-1)!
    1 :> f(n)!

    ! loop to calculate
    n [
        ! compute the next number
        f(n-1) f(n) + :> f(n+1)

        ! save the previous
        f(n) f(n-1)!

        ! save the next
        f(n+1) f(n)!
    ] times

    ! return the result
    f(n) ;

Are any of these clearly better than the original version?

Are there other variations we should consider?

There are often multiple competing priorities when improving code style – including readability, performance, simplicity, and aesthetics. I encourage everyone to spend some time iterating on these various axes as they learn more about Factor!