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 OSIL3. OSIL3 is the same as OSIL2, but it uses square brackets instead of parentheses for grouping and uses commas rather than just white space to separate list elements.
Here is an example OSIL3 program that computes the sum of the integers from 1 to 5 (a direct translation of the OSIL2 example in the program 2 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 2 assignment):
[
[ n, :=, 1 ],
[ e, :=, 0 ],
[ while, 10, -, n, do,
[
[ if, e, then,
[
[ print, n ],
[ e, :=, 0, -, 1 ]
],
else,
[ ]
]
[ n, :=, n, +, 1 ],
[ e, :=, e, +, 1 ]
]
]
]
OSIL3 follows all of the same rules as OSIL2, with these exceptions:
Every statement is surrounded by square brackets ( ... ) rather than parentheses.
All square-bracketed lists have comma-separated elements rather than white space-separated elements.
For this assignment, your program must be written in Prolog.
You will be programming
in a "logic programming" style, as described in Chapter 16 of the text
book. Since this program must be written in Prolog, appropriate use of
logic programming language features is expected. In particular, you
may not use any versions of assert, retract,
record, erase, flag, or any
of the other database features of Prolog.
As with prior programs, your solution must adhere to good programming style, including correct use of parameter passing, identifier naming, predicate length, commenting, headers for each predicate, etc.
Write your program as a Prolog predicate called
interpret_OSIL3. Your predicate should take a
single argument: a list corresponding to the OSIL3 program to
execute. For example, you might invoke your interpreter
as follows:
interpret_OSIL3( [
[ 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_OSIL3 predicate is being passed a Prolog 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 OSIL3 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_OSIL3 predicate should execute the OSIL3 program
that is passed as its argument. This OSIL3 program
will consist of a sequence of zero or more OSIL3 statements.
The "end" of the OSIL3 program is simply the end of the list that is passed
in.
OSIL3 programs are made up of the following tokens (arranged inside Prolog nested lists):
do
else
if
print
then
while
To be more precise, the following EBNF grammar describes the syntax of allowable OSIL3 programs (here, backslashes in front of square brackets are used to denote literal parenthesis characters used to form Prolog 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> { , <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 OSIL3 program. Note, however, that you won't be able to implement these as "global variables" in Prolog, since you are not allowed to have any global names 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 Prolog 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 OSIL3 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 OSIL3 input. This can happen for one of two reasons. First, the input may contain invalid token(s), such as misspelled keywords, 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 brackets. While the input you receive will always contain appropriately balanced brackets with commas between all list elements, those brackets 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.
Your Prolog 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 Prolog predicate 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 4-Prolog 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.