22C:18, Lecture 27, Summer 1997

Extending the Calculator Language

Our RPN calculator's programming language is very limited, but we can easily extend it to support enough features to allow serious programming. Consider, for example, the problems of adding control structures to this calculator's language:

Loops

To make a programmable calculator truly interesting, it should have the ability to execute programs that contain loops! The simplest way to support this would be to allow conditional gotos of some kind, but it is more fun to support some kind of structured notion of iteration. Consider the following:

Pop and print top of stack - P

We add a print command so that we can see what is happening while we execute loops!

Duplicate stack top - D

We add a command to duplicate (push a copy of) the stack top so we can work with a copy of a value without destroying the original. The calculator command sequence DP will print the item on the stack top without destroying it (first make a copy, then print and pop that copy).

Begin Loop - (

End Loop - )

Enclosing a block of calculator commands in parentheses causes that block of commands to be iterated. Parentheses may be nested arbitrarily, and as we will discuss later, there are loop exit commands. The following example will print an infinite sequence of integers:

     E (DP E1+)

How can these iteration commands be implemented in an interpreter for our calculator? There are two ways to do this, and each illustrates useful ideas.

Consider, as a basic framework, the following bit of Pascal code, an abridged version of the code given when the calculator example was originally presented:

        procedure calculate(var line: string);
        var i: 0..stringsize;
        begin
            i := 0;
            while s[i] <> endofstring do begin
                case s[i] of
                'E':begin
                        sp := sp + 1;
                        stack[sp] := 0;
                    end;
		    ... { other commands }

		'(': { code for begin loop }

		')': { code for end loop }

                end;
                i := i + 1;
            end;
        end;

		'(': { ignore begin loop }

		')': { code for end loop }
		    repeat
			i := i - 1;
		    until s[i] = '{';

		')': { code for end loop }
		    begin
			level := 1;
			repeat
			    i := i - 1;
			    if s[i] = '{'
			      then level := level - 1
			    else if s[i] = '}'
			      then level := level + 1;
			until level = 0;
		    end;

The above approach uses a search for the start of the loop, but it is clearly more elegant to use something analogous to a direct branch. This can be done quite easily by remembering the location of the loop start when the start of the loop is encountered, as illustrated by the following:

		'(': { remember begin loop }
		    looploc := i;

		')': { code for end loop }
		    i := looploc;

		'(': { remember begin loop }
		    push_on_loop_stack( i );

		')': { code for end loop }
		    i := pop_from_loop_stack;

Conditionals

Loops without a loop exit mechanism are of only limited interest, so consider adding the following commands to the calculator:

Exit if equal zero - =

Exit if greater than zero - >

Exit if less than zero - <

The loop exit commands pop one element from the stack and compare it with zero. If the comparison is true, the loop is terminated. Their use is illustrated by the following examples:

     (E1=)   -- an infinite loop (1 = 0 is always false)
     (E1>)   -- an infinite loop (1 > 0 is always false)
     (E1<)   -- never iterates (1 < 0 is always true).

	v = 5;
	for (;;) {
		printf( "%d ", v );
		if (v < 1) break;
		v = v - 1;
	}

	E5 ( DP D< E1- )

How can we implement these loop exit commands in an interpretive implementation of our calculator? Consider using a simple search for the end of loop whenever a loop exit fails, and merging this with the first implementation of loops given above:

		'(': { ignore begin loop }

		')': { code for end loop }
		    repeat
			i := i - 1;
		    until s[i] = '(';

		'=': { code for compare on equal }
		    begin
			if stack[sp] = 0 then begin
			    { search for end loop }
			    repeat
				i := i + 1;
			    until s[i] = ')';
			end;
			sp := sp - 1;
		    end;

But! This approach to loops is not efficient! It would be far better to scan the source line once, before trying to calculate what is going on, and build an auxiliary line that indicates, for each "branch" instruction, where on the source line that branch is to go. Consider the following:

         _______________________________________________________________
        |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
Source: | E | 5 |   | ( |   | D | P |   | D | < |   | E | 1 | - |   | ) | 
        |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
          0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  
         _______________________________________________________________
        |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | 
Branch: |   |   |   |   |   |   |   |   |   | 16|   |   |   |   |   | 3 | 
        |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|