Learning fbForth 2.0 - Lesson 3: Stack Manipulation and a Little Programmin

RSS Bot · July 30, 2015

In this lesson we will learn a few new arithmetic words, several words for stack manipulation and how to use them all in programming, i.e., defining new words.

Before we do much more Forth arithmetic, let’s exercise our brains with some infix-to-postfix and postfix-to-infix conversions. Remember that infix notation is the same as algebraic notation and postfix is the same as RPN. Many of these exercises are based on or taken directly from Brodie’s Starting FORTH.

Convert the following infix expressions to their postfix counterparts. Each answer is in the spoiler following the infix expression:

1. a + bc

Spoiler

Answer: a b c * +

2. a(b + c)

Spoiler

Answer: a b c + *

3. (a - 10b)/3 + c

Spoiler

Answer: a 10 b * - 3 / c +

4. 2a + 5b + (c + d)/3

Spoiler

Answer: 2 a * 5 b * + c d + 3 / +

5. 0.5ab/100

Spoiler

Answer: a b * 2 / 100 / or a b * 200 /

6. (a - b)/c

Spoiler

Answer: a b - c /

Convert the following postfix expressions to their corresponding infix expressions:

1. a b - a b + /

Spoiler

Answer: (a-b)/(a+b)

2. a b 10 * /

Spoiler

Answer: a/(10b)

Now, let’s try to define some words that do calculations, using only the arithmetic operators we have learned to this point. Let’s define words that convert liquid measure in gallons, quarts, pints and fluid ounces to fluid ounces. We want to write out a phrase such as

2 GALLONS 3 QUARTS + 5 CUPS + 25 FLUID OUNCES +

to put on the stack the result in fluid ounces. Starting with pints, we can define the next higher volume in terms of the next lower as follows:

: FLUID ( -- ) ; a no-op, i.e., do-nothing visual place-holder word.
: OUNCES ( floz -- floz ) ; a no-op visual place-holder word that indicates a value in fluid ounces is on the stack and unchanged by OUNCES .
: PINTS ( pt -- floz ) 16 * ; converts pints to fluid ounces.
: QUARTS ( qt -- floz ) PINTS 2 * ; converts quarts to fluid ounces.
: GALLONS ( gal -- floz ) QUARTS 4 * ; converts gallons to fluid ounces.

Note that the stack effects are comments in the above definitions for reminding us of each word’s function. You do not need to type them to have a functional definition.

We can define the singular forms of the above words, with identical stack effects, in terms of the plural word names above as follows:

: OUNCE OUNCES ;
: PINT PINTS ;
: QUART QUARTS ;
: GALLON GALLONS ;

These are now synonyms of the words included in each definition. Now we can write such phrases as the following:

You can verify with a calculator that each result printed by . is the total liquid measure in fluid ounces of the quantities added before printing.

Now, let’s define words to perform the arithmetic in the above six infix-to-postfix exercises. We will name each word as Exn , where n is the exercise number:

1.

Spoiler

: EX1 ( a b c -- n ) * + ;
For a = 10, b = 3, c = 5:

2.

Spoiler

: EX2 ( a b c -- n ) + * ;
For a = 21, b = 4, c = 3:

3.

Spoiler

: EX3 (c a b -- n ) 10 * - 3 / + ;
For a = 11, b = 2, c = 35:

4.

Spoiler

: EX4 ( c d a b -- n ) 15 * 6 / + 6 * + + 3 / ;
For a = 13, b = 28, c = 2, d = 103:

This solution is far too convoluted to be useful! To get to this solution, the original expression, 2a + 5b +(c + d)/3, must be transformed to (c + d + 6(a + 15b/6))/3! You should definitely not feel inadequate if it did not occur to you. We will work out a much better one once we have a few stack manipulation words under our belts.

5.

Spoiler

: EX5 ( a b -- n ) * 200 / ;
For a = 235, b = 29:

6.

Spoiler

You should have found this one impossible with what we have learned so far. The problem here is that, after we perform one operation, we need to change the stack order to continue. We will learn shortly how to manipulate the stack to make this definition tractable.

We can only do integer arithmetic with the Forth we have learned thus far. Two more division operators can help us manage this a little better, viz., MOD (pronounced “mod”) and /MOD (pronounced “slash-mod”):

MOD ( n₁n₂ — rem ) leaves on the stack the remainder rem from n1/n2.
/MOD ( n₁n₂ — rem quot ) leaves on the stack the remainder rem and the quotient quot from n1/n2.

As we discovered in the exercise definitions above, #4 is very difficult and #6 is impossible without some stack manipulation we haven’t yet learned. Here are some words that will help us to manipulate the stack:

DUP ( n — n n ) duplicates the top stack cell.
SWAP ( n₁ n₂ — n₂n₁ ) reverses the top two stack cells.
OVER ( n₁ n₂ — n₁ n₂n₁ ) copies the second cell to the top of the stack.
ROT ( n₁ n₂n₃ — n₂ n₃n₁ ) rotates the third cell to the top of the stack.
DROP ( n — ) drops the top cell from the stack.

EX4 can now be defined as

Spoiler

: EX4 ( a b c d -- n ) + 3 / SWAP 10 * + SWAP 2 * + ;

Here is a commented version of EX4 to explain a little better how it works. The running contents of the stack are shown in comments as “stack:...” when the stack is changed by a line of code:

Spoiler

: EX4 ( a b c d -- n ) ( stack:a b c d)

+ ( stack:a b c+d)

3 ( stack:a b c+d 3)
/ ( stack:a b [c+d]/3)
SWAP ( stack:a [c+d]/3 b)
10 ( stack:a [c+d]/3 b 10)
* ( stack:a [c+d]/3 10b)
+ ( stack:a [c+d]/3+10b)
SWAP ( stack:[c+d]/3+10b a)
2 ( stack:[c+d]/3+10b a 2)
* ( stack:[c+d]/3+10b 2a)
+ ( stack:[c+d]/3+10b+2a)

; ( exit)

and EX6 is now tractable as

Spoiler

: EX6 ( c a b -- n ) - SWAP / ;

and the commented version to monitor the stack:

Spoiler

: EX6 ( c a b -- n ) ( stack:c a b)

- ( stack:c a-b)

SWAP ( stack:a-b c)
/ ( stack:[a-b]/c)

; ( exit)

Let’s try our hand at defining words for these two formulas for converting between Fahrenheit (°F) and Celsius (°C) temperatures:

F = 9C/5 + 32
C = 5(F - 32)/9

Let’s define TC>TF to do the Fahrenheit-to-Celsius conversion (formula #1) and TF>TC for the opposite conversion (formula #2). Try it yourself before opening the spoiler below to see one way to do it:
: TC>TF

Spoiler

( degC -- degF ) 9 * 5 / 32 + ;

: TF>TC

Spoiler

( degF -- degC ) 32 - 5 * 9 / ;

Now let’s improve these words to round to the nearest degree using /MOD instead of / so we can work with the remainder of the integer division. We also need to expand the factors 9/5 and 5/9 to 18/10 and 10/18, respectively, so we can halve the divisor and still get an integer:
: TC>TF

Spoiler

( degC -- degF ) 18 * 10 /MOD 32 + SWAP 5 + 10 / + ;

: TF>TC

Spoiler

( degF -- degC ) 32 - 10 * 18 /MOD SWAP 9 + 18 / + ;

Here are commented versions for clarity:
: TC>TF

Spoiler

( degC -- degF ) ( stack:C)

18 ( stack:C 18)

* ( stack:18C)
10 ( stack:18C 10)
/MOD ( stack:r q) ( rem & quot of 18C/10)
32 ( stack:r q 32)
+ ( stack:r q+32)
SWAP ( stack:q+32 r) ( remainder to top)
5 ( stack:q+32 r 5) ( half divisor for rounding)
+ ( stack:q+32 r+5)
10 ( stack:q+32 r+5 10)
/ ( stack:q+32 [r+5]/10)
+ ( stack:q+32+[r+5]/10) ( round up)

; ( exit)

: TF>TC

Spoiler

( degF -- degC ) ( stack:F)

32 ( stack:F 32)

- ( stack:F-32)
10 ( stack:F-32 10)
* ( stack:10[F-32])
18 ( stack:10[F-32] 18)
/MOD ( stack:r q) ( rem & quot of 10[F-32]/18)
SWAP ( stack:q r) ( remainder to top)
9 ( stack:q r 9) ( half divisor for rounding)
+ ( stack:q r+9)
18 ( stack:q r+9 18)
/ ( stack:q [r+9]/18)
+ ( stack:q+[r+9]/18) ( round up)

;

Be sure to try some negative temperatures. Compare the results with a calculator. Anything wrong? The following fbForth 2.0 word will help us craft a better rounding solution:

SGN ( n — -1|0|1 ) leaves on the stack the sign (-1 or 1) of n or 0 for n = 0. The symbol ‘|’ in the stack effects means “or” and separates possible results, only one of which will be left on the stack.

To get the above temperature-conversion words to round properly in both the positive and negative directions, we need to change the sign of the half-divisor term to match the remainder given by /MOD . Because SGN consumes the number it is testing, we need to DUP it before we hand it off to SGN . All we need to do now is to multiply the half-divisor term by the sign, add the result to the remainder term and divide again. This time we don’t care about the remainder. This quotient will be our rounding term of 1, -1 or 0, which, when added to the previous integer result, will give us our correctly rounded conversion:
: TC>TF

Spoiler

( degC -- degF ) 18 * 10 /MOD 32 + SWAP DUP SGN 5 * + 10 / + ;

: TF>TC

Spoiler

( degF -- degC ) 32 - 10 * 18 /MOD SWAP DUP SGN 9 * + 18 / + ;

And commented versions for clarity:
: TC>TF

Spoiler

( degC -- degF ) ( stack:C)

18 ( stack:C 18)

* ( stack:18C)
10 ( stack:18C 10)
/MOD ( stack:r q) ( rem & quot of 18C/10)
32 ( stack:r q 32)
+ ( stack:r q+32)
SWAP ( stack:q+32 r) ( remainder to top)
DUP ( stack:q+32 r r) ( copy of r for SGN)
SGN ( stack:q+32 r -1|0|1) ( sign of r)
5 ( stack:q+32 r -1|0|1 5) ( half divisor for rounding)
* ( stack:q+32 r -5|0|5) ( signed half divisor)
+ ( stack:q+32 r+h) ( h = signed half divisor)
10 ( stack:q+32 r+h 10) ( normalizing divisor)
/ ( stack:q+32 -1|0|1) ( normalized rounding term)
+ ( stack:q+32+[-1|0|1]) ( round down|none|up)

;

: TF>TC

Spoiler

( degF -- degC ) ( stack:F)

32 ( stack:F 32)

- ( stack:F-32)
10 ( stack:F-32 10)
* ( stack:10[F-32])
18 ( stack:10[F-32] 18)
/MOD ( stack:r q) ( rem & quot of 10[F-32]/18)
SWAP ( stack:q r) ( remainder to top)
DUP ( stack:q r r) ( copy of r for SGN)
SGN ( stack:q r -1|0|1) ( sign of r)
9 ( stack:q r -1|0|1 9) ( half divisor for rounding)
* ( stack:q r -9|0|9) ( signed half divisor)
+ ( stack:q r+h) ( h = signed half divisor)
18 ( stack:q r+h 18) ( normalizing divisor)
/ ( stack:q -1|0|1) ( normalized rounding term)
+ ( stack:q+[-1|0|1]) ( round down|none|up)