In the first program assignment, you wrote a program that interpeted OSIL programs. For this assignment, you are to write an interpreter for a variation of this same language called OSIL2. OSIL2 is the same as OSIL, but it uses parentheses for punctuation rather than semicolons, so it looks superficially a bit more like Scheme than Pascal.
Here is an example OSIL2 program that computes the sum of the integers from 1 to 5 (a direct translation of the OSIL example in the program 1 assignment):
(
( n := 5 )
( s := 0 )
( while n do
(
( s := s + n )
( n := n - 1 )
)
)
( print s )
)
Here is another example, that prints the positive even integers less than 10 (another direct translation from the corresponding example in the program 1 assignment):
(
( n := 1 )
( e := 0 )
( while 10 - n do
(
( if e then
(
( print n )
( e := 0 - 1 )
)
else
( )
)
( n := n + 1 )
( e := e + 1 )
)
)
)
OSIL2 follows all of the same rules as OSIL, with these exceptions:
Every statement is surrounded by parentheses ( ... ), rather than being terminated with a semicolon.
Blocks are no longer defined by begin/end;
instead, a block is indicated by grouping a series of statements
inside another pair of parentheses (see both examples above).
The skip statement is now represented by an empty list--a
pair of parentheses with nothing between them, rather than with
the keyword skip in between. See the second example
above.
For this assignment, the implementation language is Scheme. You will be programming in a "functional" style, as described in Chapter 15 of the text book. Since this program must be written in Scheme, appropriate use of functional language features is expected. Hence,
set!, setcar!, setcdr!, and all
other operations with named ending in "!" are not allowed.
do and
begin. That still leaves you with plenty of control
structures to work with, though.
Here are some suggestions:
cond or if. The
if function is a special case of cond. If
you only use cond, you'll probably never miss
begin.
let. That
means using recursion in spirit whenever you need to repeat
a series of actions. Alternatively, you can define a separate
recursive function if you prefer.
let (instead of define). This most
commonly arises if you want to perform more than one action with
the return value produced by some expression. Use let
to bind the value to a new local name, and then you can refer to it in
multiple places.
Write your program as a Scheme function called
interpret-OSIL2. Your function should take a
single argument: a list corresponding to the OSIL2 program to
execute. For example, you might invoke your interpreter
as follows:
(interpret-OSIL2 '(
( n := 5 )
( s := 0 )
( while n do
(
( s := s + n )
( n := n - 1 )
)
)
( print s )
)
)
Note that this input format means that the process of lexing has already
been taken care of for you. Instead of raw file input,
your interpret-OSIL2 function is being passed a Scheme list
structure that also contains nested lists. The top-level list represents
a sequence of statements, and each of its nested list elements represents
an OSIL2 statement of some kind. This means you will not have to focus on
lexical analysis, input buffering, skipping over white space, identifying
tokens, converting strings to integers, or constructing an internal
representation of the program, since all this work has been done for you.
Your interpret-OSIL2 function should execute the OSIL2 program
that is passed as its argument. This OSIL2 program
will consist of a sequence of zero or more OSIL2 statements.
The "end" of the OSIL2 program is simply the end of the list that is passed
in.
OSIL2 programs are made up of the following tokens (arranged inside Scheme nested lists):
do
else
if
print
then
while
To be more precise, the following EBNF grammar describes the syntax of allowable OSIL2 programs (here, backslashes in front of parentheses are used to denote literal parenthesis characters used to form Scheme lists):
<program> --> <block_stmt>
<statement> --> <assignment_stmt>
| <print_stmt>
| <block_stmt>
| <if_stmt>
| <while_stmt>
| \( \)
<assignment_stmt> --> \( <variable> := <expression> \)
<print_stmt> --> \( print <expression> \)
<block_stmt> --> \( { <statement> } \)
<if_stmt> --> \( if <expression> then <statement> else <statement> \)
<while_stmt> --> \( while <expression> do <statement> \)
<expression> --> <operand> { ( + | - ) <operand> }
<operand> --> <variable>
| <integer>
<variable> --> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
<integer> --> a sequence of one or more digits
Variables: Think of the 26 variables as "global" variables that are initialized to 0 at the start of the OSIL2 program. Note, however, that you won't be able to implement these as "global variables" in Scheme, since you are not allowed to have "variables" that are assigned different values over time.
Assignment: An assignment expression contains a variable on the left hand side and a value on the right:
( x := 2 + 3 )
The meaning of such a statement is to compute the value on the right, then assign it to the variable on the left (in OSIL). You'll have to do this without using assignment, however, in the Scheme implementation.
Precedence: The grammar above indicates all arithmetic operators (that is, + and - in this case) are of equal precedence.
Associativity: As with most languages, the expectation here is that operators at the same precedence level should be left-associative. Your solution must implement associativity correctly.
Your interpreter will execute each statement in the
input OSIL2 program. Most statements will only result in internal
state changes within the interpreter, however, and will not produce
any visible output. Only the print statement produces
output. Each print statement should print the corresponding
expression value followed by a newline on standard output.
Your interpreter may also encounter invalid statements in the OSIL2 input. This can happen for one of two reasons. First, the input may contain invalid token(s), such as misspelled keywords, missing white space between tokens, inappropriate punctuation, or incorrect operator symbols. Second, the input may contain correct tokens but still fail to match the grammar listed in this assignment--a "syntax error." Of particular interest when considering such syntax errors is the placement of parentheses. While the input you receive will always contain appropriately balanced parentheses, those parentheses may not always be placed properly. If any such error happens, your program is to print the following error message on standard output:
Incorrect statement syntax.
Because of the use of the Curator, be sure your error message appears exactly as above (without any leading or trailing white space).
After printing the error message, your interpreter should "skip" the remainder of the list it was processing when it discovered the error. Note: this will produce different behavior than the "skip to the next semicolon" action used in program 1.
Your Scheme implementation is to be organized in a single file. All documentation and identifying information should be placed in comments within the single source file. The comments at the beginning of the file should identify the assignment and give your full name. Every Scheme function (as well as each global constant) should be preceded by a comment block explaining its purpose, the meaning of each parameter, and the general strategy of its implementation if applicable.
Your program will be submitted electronically through the Curator for automatic grading against a randomly generated test suite. To submit your program, login to the Curator using your PID and password. Be sure to select the 91389-CS 3304 Comparative Languages section when logging in. Click on "Submit", choose 2-Scheme from the project drop-down list, click "Browse" to specify your solution, and then click "Upload."
In addition, you must also turn in a printed version of your program source in class according to the rules specified in the syllabus, which also describes the late policy. Your hardcopy printout must match the highest-scoring submission sent to the Curator earliest. In other words, you may not submit your program until it works, go back and add comments and documentation, and then make a final submission of the printable version of your program. Once you receive full credit from the Curator on a submission, that is the version you must print and hand in.