Fibonacci numbers in Cat

Example for versions Online Cat 1.3

This example uses recursive definition of Fibonacci numbers. First part defines a function fib which works as follows. When it is called, the top element of the stack is index of Fibonacci number to be calculated. First the commands dup and 1 push a copy of this element and a 1 on the stack. Then command <= (which is equivalent of lteq) pops and compares top two elements and pushes true if index is less than or equal to 1, and false otherwise.

Next goes conditional expression: two quotations are pushed on the stack, and then if the third-top element of the stack is true, first of them is evaluated, otherwise second one is. In this case true-quotation is empty (Fibonacci numbers 0 and 1 are equal to 0 and 1, respectively, so no calculations are required), and false-quotation is the following. It duplicates the top element of the stack (which is index N of the number again), decrements the duplicated value (N-1), calculates Fibonacci number N-1 and replaces the index with the number itself, swaps two top elements of the stack (so now they are Fib(N-1) N), subtracts 2 from the top element (N-2) and replaces it with respective Fibonacci number. Finally, two Fibonacci numbers are added to get the number which was required.

Second part of the program is its body which loops over the indices from 1 to 16, calculates numbers and prints them. It uses a while-loop, with body [dup fib write ", " write inc] which duplicates top element of the stack, calculates its Fibonacci number, writes it, writes comma after it and increments the loop counter. [dup 16 lteq] is condition of repeating the loop — while loop counter is less than or equal to 16. 

define fib {
    dup 1 <=
        []
        [dup 1 - fib swap 2 - fib +]
    if
}

    1
    [dup fib write ", " write inc]
    [dup 16 lteq]
while
"..." writeln