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.

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`{ }`

.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.

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.

- Forth, interpreted or compiled?
- Files I/O handling in Forth
- Reverse the data stack using loops
- How can I get a words string representation on the data stack in Forth (gforth)?
- Create a new word from string on stack in Forth
- A weird problem in Forth when printing out the data stack and floating-point stack
- How can I check whether enough arguments are passed to a word in Forth?
- Making use of the return stack in the fibsum example in Forth
- How to define VALUE and TO
- gforth : using the return stack
- gforth : Attempt to use zero-length string as a name
- What implementation of Forth should I use for learning Forth?
- Save and restart a forth 'image'
- Print double quotes in Forth
- how to trap/disable CTRL+C in GFORTH
- How can I write my own colon definition in ColorForth?
- Gforth storing string values in variables
- Forth: associate a name with a memory address
- How does the colorForth /mod algorithm work?
- How is a Forth value different from a variable?
- How to include a C library in Forth
- How would one go about implementing a vector or dynamic array in forth?
- What are the primitive Forth operators?
- Memory management in Forth
- Where can I find a Forth / Gforth API?
- How do you keep track of all strings allocated in Forth and free them on time?
- How do I compile Forth code for the J1 CPU?
- What might cause a SIGILL (other than an illegal instruction) on RISC-V?
- How can I exit Forth with a non-zero exit status?
- How can I access a shadowed definition in Forth?