Jump to content
  • entries
    4
  • comments
    13
  • views
    6,958

Lesson 3: Stack Manipulation and a Little Programming


Lee Stewart

1,408 views

blog-0077161001438265571.gif

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

Answer: a b c * +

2. a(b + c)

Answer: a b c + *

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

Answer: a 10 b * - 3 / c +

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

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

5. 0.5ab/100

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

6. (a - b)/c

Answer: a b - c /

Convert the following postfix expressions to their corresponding infix expressions:

1. a b - a b + /

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

2. a b 10 * /

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:

blogentry-29677-0-17635800-1438262511.png

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.

: EX1 ( a b c -- n ) * + ;

For a = 10, b = 3, c = 5:

blogentry-29677-0-09765700-1438262558.png

2.

: EX2 ( a b c -- n ) + * ;

For a = 21, b = 4, c = 3:

blogentry-29677-0-31972000-1438262560.png

3.

: EX3 (c a b -- n ) 10 * - 3 / + ;

For a = 11, b = 2, c = 35:

blogentry-29677-0-82774100-1438262559.png

4.

: EX4 ( c d a b -- n ) 15 * 6 / + 6 * + + 3 / ;

For a = 13, b = 28, c = 2, d = 103:

blogentry-29677-0-40630500-1438262559.png

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.

: EX5 ( a b -- n ) * 200 / ;

For a = 235, b = 29:

blogentry-29677-0-65409500-1438262558.png

6.

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 ( n1 n2rem ) leaves on the stack the remainder rem from n1/n2.

/MOD ( n1 n2rem quot ) leaves on the stack the remainder rem and the quotient quot from n1/n2.

 

blogentry-29677-0-59633300-1438262636.png

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 ( nn n ) duplicates the top stack cell.

SWAP ( n1 n2n2 n1 ) reverses the top two stack cells.

OVER ( n1 n2n1 n2 n1 ) copies the second cell to the top of the stack.

ROT ( n1 n2 n3n2 n3 n1 ) rotates the third cell to the top of the stack.

DROP ( n — ) drops the top cell from the stack.

 

blogentry-29677-0-16413200-1438262637.png

EX4 can now be defined as

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

: 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

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

and the commented version to monitor the stack:

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

  1. F = 9C/5 + 32
  2. 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

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

blogentry-29677-0-62085900-1438262703.png

: TF>TC

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

blogentry-29677-0-25254200-1438262705.png

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

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

blogentry-29677-0-78380700-1438262705.png

: TF>TC

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

blogentry-29677-0-74903700-1438262704.png

Here are commented versions for clarity:

: TC>TF

( 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

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

 

blogentry-29677-0-67530300-1438262637.png

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

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

blogentry-29677-0-27744000-1438262706.png

: TF>TC

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

blogentry-29677-0-30241000-1438262704.png

And commented versions for clarity:

: TC>TF

( 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

( 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)

;

That’s all for this session. Please, feel free to ask questions and make suggestions; and certainly, let me know of any mistakes you find.

  • Like 3

3 Comments


Recommended Comments

There are better ways to define the temperature conversion words that round the results than what I posted. I will give you a couple of hints:

  • No /MOD and
  • Only 1 division

Anyone care to try?

 

...lee

Link to comment

How costly is it to have those no-op words like...

: GALLON GALLONS ;

?

 

Do they just take up memory for easier readability, because the compiler works some magic? or Do they actually introduce extra runtime overhead?

Link to comment

Though it was written “for easier readability”, GALLON is not a no-op word. When it is defined, the CFA ( Code Field Address = execution address) of GALLONS is compiled into the definition. When GALLON executes, the fbForth address interpreter will next execute the CFA of GALLONS . The runtime cost of GALLON is one extra nesting level for the address interpreter to unwind; so, GALLON does, indeed, take longer to execute than GALLONS .

 

The no-op words, FLUID and OUNCES , also have a runtime cost; but, it is less than that of words such as GALLON because they simply return from their added nesting level.

 

By now, you have probably figured out that OUNCE will take longer to execute than OUNCES due to the extra nesting level and that there was no need to define OUNCE the way that I did unless I actually wanted it to take more time to do nothing. That was my mistake. I should have defined it just like OUNCES :

 

: OUNCE ;

 

You can determine the memory that a given definition occupies with the following:

 

HERE <definition> HERE SWAP - .

 

For the definition of OUNCE :

 

HERE : OUNCE ; HERE SWAP - . 12 ok:0 <---computer's response is underlined

 

..lee

Link to comment
Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...