Search code examples
forthgforth

Making use of the return stack in the fibsum example in Forth

While learning gforth I have implemented the Fibonacci sequence in a few forms.

Below are some implementations of the fibsum definition, which sums up all the Fibonacci values up to a certain rank.

In other words the Fibonacci sequence being: 0 1 1 2 3 5 8 13 21 34 55 89

fibsum will produce: 0 1 2 4 7 12 20 33 54 88 ....

Here is my first implementation of fibsum

variable fbsum
: fibsum ( u -- u.sum ) { p } 0 1 \ Fibonacci-Sum.
\ This sums the first u values of the Fibonacci sequence.
0 fbsum !
p 0= if drop dup else 1 fbsum ! endif
p 1 u+do
 over over +
 dup fbsum +!
 rot drop
loop
2drop fbsum ? ;

Here is the second implementation

variable fbsum
: fibsum2x ( u -- u.sum ) { p } 0 1 \ Fibonacci recursive (1)
p dup 1 > if
  dup 1- recurse swap
  2 - recurse +
  nip nip
else
  p 1 = if 1 fbsum +! endif \ Here p matches the argument to the top call!
  nip nip
endif ;
: fibsum2 ( u -- u.sum ) \ Fibonacci-Sum.
\ This sums the first u values of the Fibonacci sequence.
{ m }
0 fbsum !
m 1+ 1 u+do
  i fibsum2x drop
loop
fbsum ? ;

And this is the third implementation

variable fbsum
: fibsum3x ( u -- u.sum ) { p } 0 1 \ Fibonacci recursive (2)
p dup 1 > if
  dup 1- recurse swap
  2 - recurse +
  nip nip
else
  \ p 1 = if 1 fbsum +! endif \ Here p matches the argument to the top call!
  nip nip
endif ;
: fibsum3 ( u -- u.sum ) \ Fibonacci-Sum.
\ This sums the first u values of the Fibonacci sequence.
{ m }
0 fbsum !
m 1+ 1 u+do
  i fibsum3x
  fbsum +!
loop
fbsum ? ;

As one can see I am not making use of the return stack in my code. In fact I tried but failed. So here comes my question.

How can I modify the code above and make a correct use of the return stack ?

Solution

  • A few notes.

    1. Gforth is an implementation for the Forth programming language. Implementations for Forth are also known as Forth systems. It's better to learn Forth in general (using Gforth, or another Forth system) than the Gforth system particularities. For example, use {: :} to declare local variables, instead of { }.

    2. Usually, if you use variables, whether they are static or local (temporary), you have less need for the return stack to rearrange arguments. Therefore, to demonstrate the use of the return stack, we will eliminate variables.

    3. The return stack is just an additional stack available with known limitations for a Forth program. The return stack cannot be used to pass arguments into a definition, or return them from a definition.

    To correctly pose the problem on the Fibonacci sequence, we should describe it more carefully to show what indexing is used. From the recurrence relation:

    fib(0) = 0
fib(1) = 1
fib(n) = fib(n-2) + fib(n-1)

    it's obvious that we start from 0.

    Just for reference, the word fib can be inefficiently implemented from this recurrence relation like this:

    : fib ( u.index -- u.value )
  dup 2 u< if exit then
  dup 2 - recurse  swap 1 - recurse  +
;

    So, the sum of the Fibonacci sequence elements up to a certain rank means the sum of elements up to the certain index, starting from 0. And the recurrence relation for fibsum() is following:

    fibsum(0) = 0
fibsum(n) = fibsum(n-1) + fib(n)

    Let's define the test cases for the word fibsum from the very beginning:

    t{ 0 fibsum ->  0 }t
t{ 1 fibsum ->  1 }t
t{ 2 fibsum ->  2 }t
t{ 3 fibsum ->  4 }t
t{ 4 fibsum ->  7 }t
t{ 6 fibsum -> 20 }t

    In the Gforth distribution, the words t{ -> }t are defined in test/ttester.fs, include this file to run the above tests.

    From the recurrence relation for fibsum() we can get the following recursive implementation for the word fibsum:

    : fibsum ( u.index -- u.sum )
  dup 0= if exit then
  dup 1- recurse swap fib +
;

    And an iterative implementation is even shorter (but slightly more complicated):

    : fibsum ( u.index -- u.sum )
  0 swap 1+ 0 do  i fib +  loop
;

    These implementations are simple, but they perform a lot of excessive computation.

    An efficient way is to calculate both the value and the sum on each step. The idea is that we define the word fibsum-next ( u1 u2 u.sum2 -- u2 u3 u.sum3 ), that calculates the next value and next sum from the previous value and previous sum; actually, to calculate the next value, we should use two previous values: u3=u1+u2, u.sum3=u3+u.sum2.

    The test cases:

    t{ 0 0 0 fibsum-next  -> 0 0 0 }t
t{ 0 0 1 fibsum-next  -> 0 0 1 }t

t{ 0 1 1 fibsum-next  -> 1 1 2 }t
t{ 1 1 2 fibsum-next  -> 1 2 4 }t
t{ 1 2 4 fibsum-next  -> 2 3 7 }t

    NB: this word returns the correct values recurrently starting from the index 2 only, i.e., staring from the input ( 0 1 1 ).

    An implementation without using the return stack:

    : fibsum-next ( u1 u2 u.sum2 -- u2 u3 u.sum3 )
  -rot tuck + rot over +
;

    And the variant with using the return stack (finally!):

    : fibsum-next ( u1 u2 u.sum2 -- u2 u3 u.sum3 )
  >r tuck + dup r> +
;

    In this case the use of the return stack does not make code shorter, but can be easier to implement, and more efficient.

    As a beginner, you'll probably want to write more stack diagrams, like this:

    : fibsum-next ( u1 u2 u.sum2 -- u2 u3 u.sum3 )
  >r    ( u1 u2 ) ( R: u.sum2 )
  tuck  ( u2 u1 u2 )
  +     ( u2 u3 )
  dup   ( u2 u3 u3 )
  r>    ( u2 u3 u3 u.sum2 ) ( R: )
  +     ( u2 u3 u.sum3 )
;

    In the implementation for fibsum we should correctly prepare the initial arguments for fibsum-next and run the loop:

    : fibsum ( u.index -- u.sum )
  dup 2 u< if exit then
  1- >r  0 1 1  r>  0 do fibsum-next loop  nip nip
;

    In this case, it's difficult to rearrange the arguments without an additional stack or variables. And we just used the return stack.

    Well, we can use the word roll, but it's usually very inefficient.