Assignment 5. Java

STACK Extensions -- Macros, Variables and Iteration             DUE: April 13, 2000 -- 6:00pm

In this assignment you will add variables, macros and loops to the STACK language.

First, you will need to handle a bit more variety in the input language, as defined here in Perl-like notation:

• Identifiers (IDs) are alphanumeric strings beginning with a letter:
  [a-zA-Z][a-zA-Z0-9_]*
  

Whitespace still consists of blanks, tabs and newlines -- these separate symbols in the input, but otherwise the amount of whitespace should have no effect on the output.

Macros

A macro is essentially an abbreviation for a list of instructions. Macros are defined with the macro operator. To
define a macro users must enter a number of unevaluated symbols and give a name, which must be an ID (as defined previously), to those symbols. If the macro name is encountered later in the program the interpreter textually substitutes the macro definition for the macro name and continues interpreting the resulting program (this should remind you of the pass-by-name parameter passing method).

The syntax for macro definitions is as follows:

macro name symbol₁ symbol₂ ... symbol_n orcam

The symbols macro and orcam delimit the macro definition, and name is the macro's identifier. The macro body must have at least one symbol (i.e. n >= 1). Macro definitions cannot be nested, so the symbols between macro and orcam should not be evaluated during macro definition. Once defined, a macro name can later be bound to another set of symbols, but there is no way to undefine a macro name.

For example, if the user entered

macro average add 2 exch div orcam

this would define a new macro called average. If we then entered

4 8 average show

the value 6 would be printed out.

There are many ways to implement macros. We will describe one particular approach, but you are free to choose your own
as long as your results are consistent with ours.

One way to handle macros is to create an artificial input stream for each  new macro. If a macro name is encountered during evaluation, then the interpreter begins reading from the macro's input stream.  Thus, the macro definition is the next set of symbols to be evaluated. After the macro has been processed, the macro stream is reset and the interpreter returns to reading the standard input stream.  It is legal for a macro to be called during execution of another macro (but using a macro name within the macro definition of that name will cause the program to infinitely recurse when the macro is called).

Variables

The second part of the assignment is to add variable assignment and use to the STACK language. As with macros, users
must be able to assign values to identifiers and use those values later.

A STACK variable is a name, which must be an ID (as defined previously), bound to one or more locations in memory.
Specific values may be stored in a variable and retrieved. Variables are assigned values by the store operator.

Modifying a variable

The store operator takes two operands. The first operand is the variable name and the second is the value to be associated with that name. For example,

2 quote x store

assigns the value 2 to the variable x.  Variables can be redefined, meaning that a store to an already defined variable overwrites
the old value.

Referencing a variable

A variable's value should be returned when the variable name is evaluated. For example,

4 quote x store x dup mul show

should print the value 16. Note that the use of the token x after the store operator causes the value of variable x to be pushed on the stack. This means that any (unquoted) token appearing in the input stream that may be a variable name must be checked to see whether it is a variable name that must be evaluated (and its associated value pushed on the stack), and not cause an error as was done for Assignment 4.

Loops

In languages like C++ and Java, looping constructs allow you to execute a list of statements multiple times. In this assignment, we will restrict the loop body to one operation.

For the third part of the assignment you will implement two types of loops.

• Repeat. The repeat operator is a loop that executes for a fixed number of iterations. The repeat operator pops two operands off the stack, with the first operand a symbol (i.e., the loop body) and the second operand a non-negative integer. The integer indicates the number of times the loop body is to be evaluated. It is an error if the integer is less than zero.

The syntax for a repeat loop is as follows:

n quote body repeat

where n is the number of loop iterations and body is the symbol to be evaluated for each loop iteration.

• While. The while operator is used to conditionally evaluate a loop body multiple times. The while operator pops two operands, with the first operand a symbol to be evaluated and the second operand a boolean. If the boolean is true the loop body is evaluated, otherwise the while operation terminates.

For all subsequent iterations, a boolean value is expected on the top of the stack. This value is popped from the stack. If it is true the loop body is re-evaluated, otherwise the while operation terminates.

The syntax for a while loop is as follows:

quote body while

where body is the symbol to be evaluated for each loop iteration.

In C++ you might write the factorial function as follows:

acc = 1;
n = 10;
while (n > 0) {
acc = acc * n;
n--;
}

Here's one way to write it using first the repeat and then the while operator.

1 quote acc store
10 quote n store
macro fact n acc mul quote acc store 1 n sub quote n store orcam
n quote fact repeat

1 quote acc store
10 quote n store
macro fact n acc mul quote acc store 1 n sub quote n store 0 n greater orcam
0 n greater
quote fact while

Note that the loop body for either type of iteration may be  either a predefined symbol (one of the ones from Assignment 4)
or a user-defined symbol (i.e. a macro or variable).

Some other things to keep in mind:

• Make sure that all parts of the assignment work together. For example,

3 quote x store macro square dup mul orcam x square show

should print the value 9.

• STACK programs have a single name space. So at any given time, you can't  have more than one macro or variable with the same name.

• The names of built-in operators (and other keywords, such as macro) are reserved. Consequently, they cannot be redefined (as either variables or macros).

• Whenever an operation cannot be executed properly give an error message and dump the stack, as for Assignment 4.

Instructions for submitting your work:

1. Put one class in each source file, and name the file with the class name (e.g., my_class.java).
2. tar the Java file(s) and a Makefile for submission (e.g., tar cvf submit5.tar *.java Makefile);
3. Your Java program should start from a class named Main (which must have a member function named main), read test data from an input data file specified on the command line, redirected from stdin, and write its output to stdout, also perhaps redirected to a file (e.g., java Main < test_data.txt > test_output.txt);
4. submit the tar file: ~al330001/bin/submit 5 submit5.tar.

Your work may not be graded if these procedures are not followed exactly.