Scheme代写涉及编译原理完成一个名叫PLAN的简单函数语言解释器Compiler

CSE 3341 Project 2 Overview
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 grammar:
⟨P rogram⟩ ⟨Expr⟩
::= ( prog ⟨Expr⟩ ) ::= ⟨I d⟩
| ⟨Const⟩
| ( myignore ⟨Expr⟩ )
| ( myadd ⟨Expr⟩ ⟨Expr⟩ )
| ( mymul ⟨Expr⟩ ⟨Expr⟩ )
| ( myneg ⟨Expr⟩ )
| (mylet ⟨Id⟩ ⟨Expr⟩ ⟨Expr⟩ )
::=a|b|…|z
::= integer constant Here are five valid PLAN program
⟨Id⟩ ⟨C onst⟩
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 ⟨Expr⟩) evaluates to whatever ⟨Expr⟩ evaluates to.
2. (myignore ⟨Expr⟩) evaluates to the integer value 0, regardless of what the subexpression
⟨Expr⟩ looks like.
3. (myadd ⟨Expr⟩ ⟨Expr⟩) evaluates to the sum of whatever values the two sub-expression
evaluate to.
4. (mymul ⟨Expr⟩ ⟨Expr⟩) evaluates to the product of whatever values the two sub-expression evaluate to.
5. (myneg ⟨Expr⟩) evaluates to X · (−1), where X is the integer value that the sub-expression evaluates to.
6. (mylet ⟨Id⟩ ⟨Expr⟩1 ⟨Expr⟩2) has the following semantics. First, ⟨Expr⟩1 is evaluated. The resulting integer value is bound to the identifier ⟨Id⟩. Then the second sub-expression ⟨Expr⟩2 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 ⟨Expr⟩2 is being evaluated.
1

7. ⟨Id⟩ 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. ⟨Const⟩ 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
Implementation
Write a Scheme function myinterpreter that takes as input a list of plan programs and produces a list of the corresponding values. For example, an invocation
( myinterpreter
’( (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 implemen-
tation:
• 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 cn 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 error- handling code. Do not worry about arithmetic issues such as underflow or overflow.
• Two 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.
• 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 of a symbol and an integer value.
• (load “myfns.ss”) inside the scheme48 interpreter allows you to load a file myfns.ss with your implementation of myinterpreter and any other helper functions.
2

Instructions that limit what your interpreter can do (otherwise the project would be trivial):
1. A PLAN program is not a Scheme program. A PLAN program should not be directly given as input to the Scheme interpreter. Do not try to make the Scheme interpreter execute PLAN programs by defining Scheme functions myadd, mymul, ect. The PLAN program is input to your interpreter, not 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?, and integer?. It is also ok to use any car/cdr variant such as cadadr. You should not use any other built-in function.
3. Make sure your code is purely function: do not use imperative features such as set!.
Project Submission
On or before 11:59 pm July 23rd, you should submit a single file called “myfns.ss” containing all the definitions of all your functions, including the main function myinterpreter. 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 come 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 July 24th 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.
Grading
Your project 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.
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 http://oaa.osu.edu/coamresources.html). If you have any questions about university policies or what constitutes academic misconduct in this course, please contact me immediately.
3