Assignment 5.  Java

STACK Extensions -- Arrays, Macros and Variables                DUE: Nov. 10, 1999 -- 6:00pm

In this assignment you will add arrays, variables, and macros 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_]*
  
• Brackets are square brackets to be used as array delimiters:
                                               [ and ] (not in Perl notation)
  Like other symbols, brackets must be surrounded by whitespace to separate them from neighboring symbols.

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. The test data you are graded on will have no ID or numeral (integer or floating point number) longer than 20 characters. You are still free to accept longer symbols.

Arrays.

An array is a collection of values, all of the same type (any of the four basic types - string, integer, float or boolean) whose elements may be randomly accessed by means of integer indices. We first consider whole array objects and postpone random access to the later discussion of variables. For the purposes of this assignment, all arrays must be one-dimensional; the index of the first element of an array is 1. It is an error if all the values in the array do not have the same type.

An array value is constructed as a sequence of symbols set off by square brackets. If none of the symbols are operators, then

[ symbol₁ symbol₂ ... symbol_n ]

is a one-dimensional array of n elements.

You do not have to check that arrays are one-dimensional; we guarantee that no input will have a left or right bracket inside an array definition.

Symbols are evaluated normally before being stored as part of the array object. For example,

[ foo quote 2 quote false quote quote ]

in the input results in an array of four strings, [ foo 2 false quote ], being pushed onto the stack, and

[ 7 9 sub 2 3 add ]

results in the array [ 2 5 ] being pushed onto the stack.

Implementation suggestion: after [, push a marker on the stack and process normally until you see ]. Then pop from the stack into an array object until you reach the marker. This means that all the error conditions that can happen within the regular stack can also happen during an array definition.

An array object occupies a single location on the stack. Only some of the operations defined in Assignment 4 may legally be applied to array objects:

• pop, exch, dup, clear, count -- each treat an array object the same as any other non-array object on the stack.
  

• add, sub, mul, div, int, float, equal, greater, lessthan, and, or -- may be applied to two arrays of the same length OR to an array and a scalar. The result is an array of the same length, with each element the result of the operation applied to the corresponding elements of the operand arrays (when one of the operands is a scalar, the scalar is used as one operand for all the operations to build the result array). When applying an operation to the elements is a type error, you should report a type error on the array. An error should also be reported if the two operand arrays are not the same length.
                                       [ 1 2 3 ] [ 4 5 6 ] add
  will leave [ 5 7 9 ] on the stack, while
                                       [ 5 6 7 ] 6 lessthan
  will leave [ false false true ] on the stack.
                                       [ true false ] [ 1 ] greater
  is an error for two reasons: the arrays are of different size, and the second operand to greater cannot be booleans.

• if -- can't have an array as the first operand (a single boolean should be at the top of the stack), but the other operand can be an array
  
• ifelse -- can have anything as its second and third operands, if the first operand is a non-array boolean. If the first operand is an array, all its elements must be booleans, and the second and third operands must be arrays of the same length as the first operand and of the same type as each other:
                                       [ 99 63 47 ] [ 4 5 6 ] [ true false false ] ifelse
  will leave [ 4 63 47 ] on the stack.
  
• show -- prints the array with the elements displayed between square brackets:
                                       [ 1 2 add 3 ] show
  will cause [ 3 3 ] to be printed.

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

Variables.

The last 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 (or array elements) 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. Additional operators called access and update allow manipulation of the individual elements of array variables.

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 x store
assigns the value 2 to the variable x, while
                               [ 2 3 4 ] x store
assigns the array value [ 2 3 4 ] 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,
                              [ 2 3 4 ] x store x dup mult show
should print the value [ 4 9 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 just pushed on the stack as a string as was done for Assignment 4.

Referencing an array element
The access operator takes two operands. The first operand is an array name (the array name has to be quoted to be pushed on the stack) and the second gives the integer subscript of a particular element. The value of the element is pushed on the stack. For example,
                              [ 2 3 4 ] y store
                              2 quote y access show
should print 3. It is an error if the subscript is less than 1 or greater than the length of the array.

Modifying an array element
The update operator takes three operands. The first operand is the name of an array variable (as for an array reference, the array name has to be quoted to be pushed on the stack), the second is an integer giving the subscript of a particular array element, and the third is the value to be stored into the element. Given y as above,
                              12 2 quote y update
                              y show
should print [ 2 12 4 ]. It is an error if the type of the value to be stored is not the same as that of the elements already in the array, or if the subscript is less than 1 or greater than the length of the array.

Some other things to keep in mind:

• Make sure that all parts of the assignment work together. For example,
                   3 x store macro square dup mult 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 (scalar or array) 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). The left and right bracket ([ and ]) are also reserved, and will not appear in input tokens except by themselves as array delimiters.
  
• Whenever an operation cannot be executed give an error message and dump the stack, as for Assignment 4.

Instructions for submitting your work:

• Put one class in each source file, and name the file with the class name (e.g., my_class.java).
  
• tar the Java file(s) and a Makefile for submission (e.g., tar cvf submit5.tar *.java Makefile).
  
• 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).
  
• submit the tar file: ~as330003/alpha.bin/submit 5 submit5.tar

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