程序代写代做代考 scheme Java DrRacket Excel interpreter 2018/2/18 Interpreter, Part 1

2018/2/18 Interpreter, Part 1

https://canvas.case.edu/courses/6937/assignments/75044 1/6

Interpreter, Part 1

Due  Monday by 11:59pm  Points  100  Submitting  a file upload

Submit Assignment

For this and all programming project’s, you are to work in groups of up to three students. The names of all
group members should appear at the top of the file, and every member should join the same group on Canvas.
All team members are expected to contribute to the project, and all students are responsible for understanding
the code submitted in their name.  If you insist on working alone, you must still join a group of size one.

The Language

In this homework, you are to create an interpreter for a very simple Java/C­ish language. The language has
variables, assignment statements, mathematical expressions, comparison operators, boolean operators, if
statements, while statements, and return statements.

An example program is as follows:

var x;
x = 10;
var y = 3 * x + 5;
while (y % x != 3)
y = y + 1;
if (x > y)
return x;
else if (x * x > y)
return x * x;
else if (x * (x + x) > y)
return x * (x + x);
else
return y – 1;

Note that braces, { and }, are not implemented.

The following mathematical operations are implemented : +, ­, *, /, % (including the unary ­), the following
comparison operators are implemented: ==, !=, <, >, <=. >=, and the following boolean operators: &&, ||, !.
Variables may store values of type int as well as true and false. You do not have to detect an error if a program
uses a type incorrectly (but it is not hard to add the error check). You do not have to implement short­circuit
evaluation of && or ||, but you are welcome to do so.

For those seeking an extra challenge: The parser supports nested assignment statements as well as
assignments inside expressions. Try writing your interpreter so that assignment operators return a value as
well as initialize a variable:

2018/2/18 Interpreter, Part 1

https://canvas.case.edu/courses/6937/assignments/75044 2/6

var x;
var y;
x = y = 10;
if ((x = x + 1) > y)
return x;
else
return y;

 

Sample Programs

Here are some more sample programs in this simple language that you can use to test your interpreter.  Please
note that these programs cover most of the basic situations, but they are not sufficient to completely test your
interpreter.  Be certain to write some of your own to fully tests your interpreter.

part1tests.html  

General guidelines

You are to write your interpreter in Scheme using the functional programming style. For full marks, you should
not use variables, only functions and parameters.

Your program should clearly distinguish, by naming convention and code organization, functions that are doing
the M_state operations from ones doing the M_value and M_boolean operations. You do not have to call them
M_, but your naming convention should be consistent.

You should use good style, indentation and proper commenting so that the code you submit is easy to read and
understand.

Using the Parser

A parser is provided for you called simpleParser.scm . You will also have to get the file lex.scm . You can
use the parser in your program by including the line (load “simpleParser.scm”) at the top of your homework file.
The command assumes simpleParser.scm is in the same directory as your homework file. If it is not, you will
have to include the path to the file in the load command.

If you are using racket instead of scheme, you should use (require “simpleParser.scm”) at the top of your file
instead of the load function, and you will need to uncomment some lines in the simpleParser.scm and lex.scm
files.

To parse a program in our simple language, type the program code into a file, and call (parser “filename”). The
parser will return the parse tree in list format. For example, the parse tree of the above code is:  
((var x) (= x 10) (var y (+ (* 3 x) 5)) (while (!= (% y x) 3) (= y (+ y 1))) (if (> x y) (return x) (if (> (* x x) y) (return (*
x x)) (if (> (* x (+ x x)) y) (return (* x (+ x x))) (return (­ y 1))))))

Formally, a parse tree is a list where each sublist corresponds to a statement. The different statements are:

https://canvas.case.edu/courses/6937/files/654958/download?verifier=N3VUqXYszXiBby9yHqo5dlnzpWTebplThFXi61Zm&wrap=1
https://canvas.case.edu/courses/6937/files/654958/download?verifier=N3VUqXYszXiBby9yHqo5dlnzpWTebplThFXi61Zm&wrap=1
https://canvas.case.edu/courses/6937/files/654930/download?verifier=gd0EorxMXMkOFGqxCqIzqC2durMM0OljdzxMBbdC&wrap=1
https://canvas.case.edu/courses/6937/files/654930/download?verifier=gd0EorxMXMkOFGqxCqIzqC2durMM0OljdzxMBbdC&wrap=1
https://canvas.case.edu/courses/6937/files/654933/download?verifier=XaWjy20pxUMw6AYjKGfV8sQv0vzTvRfLRWsWMaBs&wrap=1
https://canvas.case.edu/courses/6937/files/654933/download?verifier=XaWjy20pxUMw6AYjKGfV8sQv0vzTvRfLRWsWMaBs&wrap=1

2018/2/18 Interpreter, Part 1

https://canvas.case.edu/courses/6937/assignments/75044 3/6

variable declaration (var variable) or (var variable value)

assignment (= variable expression)

return (return expression)

if statement (if conditional then­statement optional­else­statement)

while statement (while conditional body­statement)

Your Interpreter Program

You should write a function called interpret that takes a filename, calls parser with the filename, evaluates the
parse tree returned by parser, and returns the proper value. You are to maintain a state for the variables and
return an error message if the user attempts to use a variable before it is declared. You can use the Scheme
function (error …) to return the error.

The State

Your state needs to store binding pairs, but the exact implementation is up to you. I recommend either a list of
binding pairs (for example: ((x 5) (y 12) …) ), or two lists, one with the variables and one with the values (for
example: ((x y …) (5 12 …))). The first option will be simpler to program, but the second will be more easily
adapted supporting objects at the end of the course. The exact way you decide to implement looking up a
binding, creating a new binding, or updating an existing binding is up to you. It is not essential that you be
efficient here, just do something that works. With such a simple language, an efficient state is unneeded.

What you do have to do is use abstraction to separate your state from the rest of your interpreter. As we
increase the number of language features we have in future parts of the project, we will need to change how
the state is implemented. If you correctly use abstraction, you will be able to redesign the state without
changing the implementation of your interpreter. In this case, that means that the interpreter does not know
about the structure of the state. Instead, you have generic functions that the interpreter can call to manipulate
the state.

Returning a Value

Your interpreter needs to return the proper value.  How you achieve this is up to you, and we will later learn the
proper way to handle the return.  A simple solution that is sufficient for this project is to have a special variable
called return in the state that you assign to the return value.  When you are done interpreting the program your
code can then lookup return in the state, get, and return that value.

Finally…

If you are using DrRacket, you will need to choose an appropriate language.  The parser will run in both R5RS
Scheme and PrettyBig.  If you are using racket, you will need to uncomment a few lines in both the
simpleParser.scm and lex.scm files.

2018/2/18 Interpreter, Part 1

https://canvas.case.edu/courses/6937/assignments/75044 4/6

Interpreter Part 1

Please save your interpreter as a Scheme file with either the .scm, .ss, or .rkt extension.

2018/2/18 Interpreter, Part 1

https://canvas.case.edu/courses/6937/assignments/75044 5/6

Criteria Ratings Pts

50.0 pts 

5.0 pts 

Performance 50.0 pts
Full Marks

Works on
all
operators
and
statements.
Clearly
delineates
state
functions,
“M_state”
functions,
and
“M_value”
functions.
The value
functions
correctly
return the
value of an
expression.
The state
functions
correctly
determine
the new
state. State
functions
correctly
insert,
update,
and lookup.

45.0 pts
Great

Same
as 50
with only
minor
errors.

40.0 pts
Good

Clearly
separated
state,
“M_state”,
and
“M_value”
functions
that
correctly
return
states and
values.
The
functions
either
have
minor
errors
throughout
or
significant
errors or
omissions
that only
hurt a few
cases.

30.0 pts
Okay

The code
shows some
understanding
of the
differences
between
state,
“M_state”,
and
“M_value”
functions but
there are
significant
errors that
cover many
cases.

20.0 pts
Poor

While there is
some
understanding
of interpreter
structure, the
interpreter is
mixing up
where a state
should be
returned and
where a value
should be
returned.
There are
significant
errors that
affect most
cases.

10.0 pts
Minimal

Does not
demonstrate
an
interpreter
structure but
has some
thing such
as a state or
basic
expressions
with no
variables

0.0 pts
No
Marks

Abstraction 5.0 pts
Good
Abstraction

Uses
abstraction
through
out.

4.0 pts
Good abstraction but the
initial state

Uses abstraction
throughout but hardcodes
‘() or ‘(()()) for the state
instead of an abstraction

2.0 pts
Missing some abstraction

Accessing elements of the
statements uses cars and
cdrs instead of well­named
functions.

0.0 pts
Over use of car/cdr/cons

Accessing the state in the
M_ functions uses cars
and cdrs instead of good
abstraction

2018/2/18 Interpreter, Part 1

https://canvas.case.edu/courses/6937/assignments/75044 6/6

Total Points: 100.0

Criteria Ratings Pts

30.0 pts 

10.0 pts 

5.0 pts 

Functional
Coding

30.0 pts
Excellent
functional
style

24.0 pts
Good functional style

Mostly uses good
functional style, but
occasionally does things
that are not purely
functional such as using
let or begin (except for
handling the side effect
challenge)

20.0 pts
Mostly functional

Uses the functional
style, but also has
very non­functional
coding such as set!,
global variables, or
define used other
than to name a
function.

15.0 pts
Poor
functional
style

The code
uses an
iterative style
throughout
such as a list
of statements
executed
sequentially.

0.0 pts
Violates
functional
coding

Significant use
of set!, define
inside of
functions, global
variables, or
anything else
that is grossly
non­functional.

Return
values

10.0 pts
Full Marks

Correctly
returns integers
or true and
false.

7.0 pts
Close

Returns values but either may return fractions or
floating point instead of integers or returns #t and
#f instead of true and false.

3.0 pts
Returns the
wrong thing

Returns a
state
instead of a
value

0.0 pts
No Marks

Does not
return a
value or a
state

Readibility 5.0 pts
Full Marks

Nicely readible code: good
indentation, well organized
functions, well named
functions and parameters,
clear comments.

3.0 pts
Reasonable

Reasonably readible code.
Except for a few places there is
good commenting, organization,
indentation, short lines, and
good naming.

0.0 pts
No Marks

Hard to read and follow the code
due to poor organization or
indentation, poorly named
functions or parameters, and/or a
lack of commenting.