Scheme辅导 | CSE 3341 Project 2

CSE 3341 Project 2
The goal of this lab is to write an interpreter for a simple functional language called PLAN. The
interpreter itself should be written in Scheme. A PLAN program is a list, as defined by the following
hP rogrami ::= ( prog hExpri )
hExpri ::= hIdi
| hConsti
| ( myignore hExpri )
| ( myadd hExpri hExpri )
| ( mymul hExpri hExpri )
| ( myneg hExpri )
| (mylet hIdi hExpri hExpri )
hIdi ::= a | b | . . . | z
hConsti ::= integer constant
Here are five valid PLAN program
1. (prog 5)
2. (prog (myadd (myadd 7 (myignore (mymul 4 5))) (mymul 2 5)))
3. (prog (mylet z (myadd 4 5) (mymul z 2)))
4. (prog (mylet a 66 (myadd (mylet b (mymul 2 4) (myadd 2 b)) (mymul 2 a))))
5. (prog (mylet x 66 (myadd (mylet x (mymul 2 4) (myadd 2 x)) (mymul 2 x))))
Each PLAN program and expression evaluates to a particular integer value. The semantics of a
program are defined as follows:
1. The entire program (prog hExpri) evaluates to whatever hExpri evaluates to.
2. (myignore hExpri) evaluates to the integer value 0, regardless of what the subexpression
hExpri looks like.
3. (myadd hExpri hExpri) evaluates to the sum of whatever values the two sub-expression
evaluate to.
4. (mymul hExpri hExpri) evaluates to the product of whatever values the two sub-expression
evaluate to.
5. (myneg hExpri) evaluates to X · (−1), where X is the integer value that the sub-expression
evaluates to.
6. (mylet hIdi hExpri1 hExpri2) has the following semantics. First, hExpri1 is evaluated. The
resulting integer value is bound to the identifier hIdi. Then the second sub-expression hExpri2
is evaluated, and the result of that evaluation serves as the value of the entire mylet expression.
The binding between the id and the integer value is active only while hExpri2 is being
7. hIdi evaluates to the value to which the identifier has been bound by a surrounding mylet
expression. If there are multiple bindings for the identifier, the last (i.e. latest, innermost)
such binding is used.
8. hConsti evaluates to the value of the integer constant.
Based on these rules, the five programs from above evaluate to:
1. 5
2. 17
3. 18
4. 142
5. 142
Write a Scheme function called myinterpreter that takes as input a list of PLAN programs and
produces a list of the corresponding values. For example, an invocation
( m yi n t e r p r e t e r
’ ( (prog 5 )
(prog ( mylet z (myadd 4 5 ) (mymul z 2 ) ) )
should produce the list (5 18).
Your implementation must work on scheme48 on stdlinux.
Instructions and suggestions intended to help you and/or simplify your interpreter’s implementation:
1. You do not need to write a scanner or a parser, we will let the scheme interpreter handle that
for us.
2. You are guaranteed that the list given to the interpreter will not be empty, and will contain
only valid PLAN programs. The programs will be valid both syntactically and semantically.
Syntactically, you can assume that any program given is valid with respect to the grammar
from above. Semantically, you can assume that any evaluation of an identifier has at least
one existing binding for that identifier. Your implementation does not have to contain errorhandling code. Do not worry about arithmetic issues such as underflow or overflow.
3. Two very useful Scheme library functions for your interpreter to use are integer? and symbol?.
The first one checks if its parameter is an integer constant, and the second one checks if its
parameter is a symbol such as a, b, ect.
4. In order to maintain the set of bindings, consider using a list where each element of the list
is one specific binding. A binding is really just a pair: the symbol and the integer value.
5. Using (load “FILENAME”) or ,load FILENAME inside the scheme48 interpreter allows you
to load a file named FILENAME with your implementation of myinterpreter and any other
helper functions.
Instructions that limit what your interpreter can do:
1. A PLAN program is not a Scheme program. The PLAN program is input to your interpreter,
not to the Scheme interpreter. For example, do not try to make the Scheme interpreter execute
PLAN programs by defining Scheme functions like this
( d e f i n e (myadd x y ) (+ x y ) )
and then giving a PLAN program directly to the Scheme interpreter.
2. The only built-in Scheme functions you are allowed to use are
• define, let, equal?, car, cdr, cons, cond, if, quote, ’, +, *, null?, list?, symbol?, integer?
It is also ok to use any car/cdr variant such as cadadr. You should not use any other built-in
3. Make sure your code is purely function: in particular, do not use define to try to create global
Extra Credit
Only attempt this extra credit if you are fully confident your ”myinterpreter” function described
in the previous section is working correctly.
Create a ”myextra” function which handles this modification of the grammar:
hP rogrami ::= ( prog hExpri )
hExpri ::= hIdi
| hConsti
| ( myignore hExpri )
| ( myadd hExpri hExpri )
| ( mymul hExpri hExpri )
| ( myneg hExpri )
| (mylet hIdi hExpri hExpri )
| (mylet hIdi hF unctioni hExpri )
hF unctioni ::= ( myfunction hIdi hExpri )
hIdi ::= a | b | . . . | z
hConsti ::= integer constant
This change allows users of the PLAN language to define their own functions. The semantics
for the addition are as follows: When a mylet expression containing a myfunction expression like
(mylet hIdi1 (myfunction hIdi2 hExpri1) hExpri2)
is evaluated, the myfunction expression is evaluated by binding the body of the function hExpri1
to hIdi1. This binding is only active while hExpri2 is being evaluated.
If an expression (hIdi1 hExpri) is encountered while evaluating hExpri2 and a new binding
for hIdi1 has not been introduced, then the value of hExpri is bound to hIdi2 and hExpri1 is
evaluated (once this finishes, the binding of the value of hExpri and hIdi2 is removed). The value
from evaluating hExpri1 is the value of (hIdi1 hExpri).
So for example,
1. (prog (mylet a (myfunction b (myadd b b)) (a 5))) evaluates to 10
2. (prog (mylet a (myfunction b (myadd b b)) (mylet a 1 (mymul a a)))) evaluates to 1
Project Submission
On or before 11:59 pm November 22nd, you should submit a single file called “”
containing all the function definitions needed for your project, including the main function myinterpreter. If you are doing the extra credit, submit a zip file containing “” and “”,
where “” contains all function definitions for the myinterpreter project, and “”
contains all the function definitions for the myextra project. Do not use any other name for the file
or for the main function. Other functions you define may have whatever names you choose. Use
white spaces appropriately so that your function definitions are easy to read. Also, include some
documentation in the same file (not a separate README file). Comment lines in Scheme program
start with a semicolon (e.g. ;this is a scheme comment).
Submit your project to the dropbox on Carmen for Project 2.
If the time stamp on your submission is 12:00 am on November 23rd or later, you will receive
a 10% reduction per day, for up to three days. If your submission is more than 3 days late, it will
not be accepted and you will receive zero points for this project. If you resubmit your project, only
the latest submission will be considered.
Your myinterpreter function will be tested against 10 valid test cases. The correct outputs for
these test cases are worth 8 points each. An additional 20 points are for code readability and
documentation. 100 points total.
If you chose to create a myextra function, it will be tested against 3 test cases, worth 4 points
each. 12 points total.
Academic Integrity
The project you submit must be entirely your own work. Minor consultations with others in the
class are OK, but they should be at a very high level, without any specific details. The work on the
project should be entirely your own; all the design, programming, testing, and debugging should
be done only by you, independently and from scratch. Sharing your code or documentation with
others is not acceptable. Submissions that show excessive similarities (for code or documentation)
will be taken as evidence of cheating and dealt with accordingly; this includes any similarities with
projects submitted in previous instances of this course.
Academic misconduct is an extremely serious offense with severe consequences. Additional
details on academic integrity are available from the Committee on Academic Misconduct (see If you have any questions about university policies or
what constitutes academic misconduct in this course, please contact me immediately.