Safari 浏览器
EECS 345 Assignments Interpreter, Part 3!
Total Points: 100.0
Interpreter, Part 3
Due Monday by 11:59pm Points 100
Submi!ng a file upload
Interpreter Part 3
Criteria Ra”ngs Pts
5.0 pts
15.0 pts
5.0 pts
25.0 pts
10.0 pts
15.0 pts
10.0 pts
5.0 pts
5.0 pts
5.0 pts
Submit Assignment
For this and all programming project’s, you are welcome to work in
groups of up to three. The names of all group members should
appear at the top of the file, and every member should submit the
project on blackboard. All team members are responsible for
understanding the code submi!ed in their name. You do notnot have to
keep the same group as the previous interpreter parts.
Solu!ons to Part 2
Here is solu!on code for the interpreter, part 2. These solu!ons
do not use boxes and do not support side effects. They are the
same except that one has the M_state func!ons tail recursive
(but not the M_value func!ons) and uses (lambda (v) v) type
con!nua!ons, and the other uses “normal” recursion and call/cc
for the con!nua!ons.
Both solu!ons are wri#en to work with R5RS scheme. If you are
using racket instead of scheme, you need to add #lang racket to
the top of the file and change the (load “simpleParser.scm”) to
(require “simpleParser”).
Solu!on 1: interpreter2-tail-recursion-no-boxes.scm
Solu!on 2: interpreter2-callcc-no-boxes.scm
A New Parser
This interpreter needs a new parser: func!onParser.scm
As with the previous parser, this one is wri#en for R5RS scheme,
and you will need to comment/uncomment some lines to use it
with racket.
The same lex.scm file will work with the new parser.
The Language
In this homework, you will expand on the interpreter of part 2
adding func!on defini!ons. We s!ll assume all variables store
integers and boolean. Likewise, all func!ons will only return
integers and boolean.
While normal C does not allow nested func!ons, the gcc
compiler does allow nested func!ons as an extension to C, so
let’s implement them!
For those seeking a small extra challenge: try implemen!ng both
the call-by-reference and the call-by-value parameter passing
styles.
An example program that computes the greatest common divisor
of two numbers is as follows:
var x = 14;
var y = 3 * x – 7;
function gcd(a,b) {
if (a < b) {
var temp = a;
a = b;
b = temp;
}
var r = a % b;
while (r != 0) {
a = b;
b = r;
r = a % b;
}
return b;
}
function main () {
return gcd(x,y);
}
Here is another example program that uses recursion:
function factorial (x) {
if (x == 0)
return 1;
else
return x * factorial(x - 1);
}
function main () {
return factorial(6);
}
Note that only assignment statements are allowed outside of
func!ons. Func!ons do not have to return a value. The parser
will have the following addi!onal constructs:
function a(x, y) { => (function a (x y) ((return
(+ x y)))
return x + y;
}
function main () { => (function main () ((var x 1
0) (var y 15) (return (funcall gcd x y))))
var x = 10;
var y = 15;
return gcd(x, y);
}
The final value returned by your interpreter should be whatever
is returned by main.
Nested func!ons can appear anywhere in the body of a func!on.
Any name in scope in a func!on body will be in scope in a
func!on defined inside that body.
function main() {
var result;
var base;
function getpow(a) {
var x;
function setanswer(n) {
result = n;
}
function recurse(m) {
if (m > 0) {
x = x * base;
recurse(m-1);
}
else
setanswer(x);
}
x = 1;
recurse(a);
}
base = 2;
getpow(6);
return result;
}
Func!on calls may appear on the right hand side of global
variable declara!on/ini!aliza!on statements, but the func!on
(and any func!ons that func!on calls) must be defined before
the variable declara!on. Otherwise, func!ons that are used
inside other func!ons do not need to be defined before they are
used.
If you want the addi!onal challenge, we will use a similar style as
C++ for call-by-reference:
function swap(&x, &y) { => (function swap (& x & y) ((v
ar temp x) (= x y) (= y temp)))
var temp = x;
x = y;
y = temp;
}
It is an error to use call-by-reference on anything other than a
variable. For example, if the program contains swap(x, x + 10)
with the above defini!on of swap, you should give an error
because x + 10 is not a variable.
Sample Programs
Here are some sample programs in this simple language that you
can use to test your interpreter. Please note that these programs
cover most of the basic situa!ons, but they are not sufficient to
completely test your interpreter. Be certain to write some of your
own to fully test your interpreter. In par”cular, there are no tests
here using boolean values. Make sure your func”ons can take
booleans as inputs and return booleans.
part3tests.html
What your code should do
You should write a func!on called interpret that takes a filename,
calls parser with the filename, evaluates the parse tree returned
by parser, and returns the proper value returned by main. You are
to maintain an environment/state for the variables and return an
error message if the program a#empts to use a variable before it
is declared, a#empts to use a variable before it is ini!alized, or
a#empts to use a func!on that has not been defined.
Some hints
Terminology In this interpreter, we will be talking about
environments instead of states. The state consists of all the ac!ve
bindings of your program. The environment is all the ac!ve
bindings that are in scope.
1. Note that the base layer of your state will now be the global
variables and func!ons. You should create an outer “layer” of
your interpreter that just does M_state func!ons for variable
declara!ons and func!on defini!ons. The declara!ons and
assignments should be similar to what you did in your part 2
interpreter. The functon defini!ons will need to bind the
func!on closure to the func!on name where the closure consists
of the formal parameter list, the func!on body, and a func!on
that creates the func!on environment from the current
environment.
2. Once the “outer” layer of your interpreter completes, your
interpreter should then look up the main func!on in the state
and call that func!on. (See the next step for how to call a
func!on).
3. You need to create a M_value func!on to call a func!on. This
func!on should do the following: (a) create a func!on
environment using the closure func!on on the current
environment, (b) evaluate each actual parameter in the current
environment and bind it to the formal parameter in the func!on
environment, (c) interpret the body of the func!on with the
func!on environment. Note that interpre!ng the body of the
func!on should be, with one change, exactly what you submi#ed
for Interpreter, Part 2. Also note that if you are using boxes, you
should not have to do anything special to deal with global
variable side effects. If you are not using boxes, you will need to
get the final environment from evalua!ng the func!on body and
copy back the new values of the global variables to the current
environment/state.
4. Change the M_state and M_value func!ons for statements
and expressions, respec!vely, to expect func!on calls.
5. Test the interpeter on func!ons without global variables, and
then test your func!ons using global variables. One tricky part
with the func!ons is that, unlike the other language constructs
we have created, func!on calls can be a statement (where the
return value is ignored), and an expression (where the return
value is used). You need to make sure both ways of calling a
func!on works.
6. Since excep!ons can happen anywhere that a func!on call can
occur, you may discover more places that need the throw
con!nua!on. If you used call/cc for throw, then you should only
need minimal modifica!ons from what you did in your
interpreter from part 2. If you used tail recursion for throw, you
will need to make the M_value func!ons tail recursive for throw
to work correctly.
Abstrac!on 5.0 pts
Good
Abstrac!on
Uses
abstrac”on
throughout.
4.0 pts
Good abstrac!on but
the ini!al state
Uses abstrac”on
throughout but
hardcodes ‘() or ‘(()()) for
the state instead of an
abstrac”on
2.0 pts
Missing some
abstrac!on
Accessing elements of
the statements uses cars
and cdrs instead of well-
named func”ons.
0.0 pts
Over use of
car/cdr/cons
Accessing the state in
the M_ func”ons uses
cars and cdrs instead of
good abstrac”on
Func!onal
Coding
15.0 pts
Excellent
func!onal
style
12.0 pts
Good
func!onal
style
Mostly
uses good
func”onal
style, but
overuses
let or
begin.
10.0 pts
Mostly func!onal
Uses the func”onal style, but
also has very non-func”onal
coding such as set!, global
variables, or define used other
than to name a func”on. (set-
box! is allowed for the state
values)
8.0 pts
Poor
func!onal
style
The code
uses an
itera”ve style
throughout
such as a list
of statements
executed
sequen”ally.
0.0 pts
Violates
func!onal
coding
Significant use of
set!, define inside
of func”ons,
global variables,
or anything else
that is grossly
non-func”onal.
Readibility 5.0 pts
Full Marks
Nicely readible code: good
indenta”on, well organized
func”ons, well named
func”ons and parameters,
clear comments.
3.0 pts
Reasonable
Reasonably readible code.
Except for a few places there
is good commen”ng,
organiza”on, indenta”on,
short lines, and good naming.
0.0 pts
No Marks
Hard to read and follow the code
due to poor organiza”on or
indenta”on, poorly named
func”ons or parameters, and/or
a lack of commen”ng.
M_value for
func!ons
25.0 pts
Full marks
(a) Correctly
creates new
environment for
the func”on that
implements sta”c
scoping. (b)
Correctly
evaluates and
binds the
parameters. (c)
Creates the
proper
con”nua”ons for
the func”on call.
(d) Evaluates the
func”on body,
and (d) handles
return correctly.
23.0 pts
Excellent
Has all
the
necessary
parts and
logic, but
a few
small
errors.
21.0 pts
Good
Has all the
necessary
parts, but there
is a significant
error with one
of the parts.
For example,
does not have
sta”c scoping,
evaluates the
parameters in
the wrong
environment, or
does not set up
the
con”nua”ons
correctly.
16.0 pts
Poor
Has most
of the
necessary
steps, but
has
significant
errors in
mul”ple
steps, or is
completely
missing
one of the
necessary
steps.
10.0 pts
Minimal
Some valid
logic
implemen”ng
a func”on
call, but none
of the
necessary
steps are
correct.
0.0 pts
No Marks
No
reasonable
a!empt at
crea”ng a
M_value
for
func”on
calls.
Func!ons in
expressions
and
statements
10.0 pts
Full Marks
Func”on
calls work
correctly as
both
statements
and as
expressions.
The
environment
is updated
correctly in
all cases.
9.0 pts
Very good
Func”on
calls are
implemented
for both
statements
and
expressions,
but the
interpreter is
missing a
place where
func”on
calls can
occur.
8.0 pts
Good
Func”on
calls are
implemented
for
statements
and
expressions,
but there is
a significant
error such as
the return
value not
being
ignored
when the
func”on call
is a
statement.
7.0 pts
Poor
Func”on
calls are
implemented
in only one
place.
3.0 pts
Minimal
Func”on
calls are
implemented,
but not at
the correct
place in the
code.
0.0 pts
No Marks
Does not
have
func”on calls
implemented.
Interpreter
“layers”
15.0 pts
Full Marks
The interpreter
has two “layers”
with the outer
layer reading in
global variables
and func”on
defini”ons, the
interpreter looks
up and executes
main, and
returns the
value. The “inner
layer” correctly
handles func”on
bodies including
nested
func”ons.
14.0 pts
Very
Good
The
interpreter
has
“layers”,
looks up
and runs
main a#er
running
the “outer
layer”,
deals with
nested
func”ons
in the
“inner
layer”, but
there are
small
errors.
12.0 pts
Good
The
interpreter
has layers
that
separate
handling
the global
variables
and
func”on
defini”ons
from
interpre”ng
the
func”on
bodies, but
there are
significant
errors.
10.0 pts
Poor
There is
some
a!empt at
dividing the
interpreter
into layers,
but there
are things
that should
be done in
one layer
that are
missing or
done in the
wrong layer
or done in
both layers.
5.0 pts
Minimal
The interpreter
does not have
layers. Instead
the same
M_state
recursion is
used for global
variables and
func”on
defini”ons as it
is for func”on
bodies. The
interpreter does
lookup and run
main, though it
may not run
main correctly.
0.0 pts
No Marks
The
interpreter
has only
one layer.
The
interpreter
does not
find and
run the
main
func”on.
M_state for
func!on
defini!ons
10.0 pts
Full Marks
The
func”on
name is
correctly
placed in
the state
with a
correct
closure.
9.0 pts
Excellent
The func”on name is
bound to a correct
closure in the state,
but the rou”ne has a
small error in the
M_state func”on.
7.0 pts
Okay
The func”on name is
bound to a func”on
closure in the state, but
the closure does not
correctly set the scope
for nested func”ons.
5.0 pts
Poor
The func”on
name is
bound to a
closure in the
state, but the
closure is not
correct.
0.0 pts
No
Marks
The
func”on
name is
not
bound to
a closure
in the
state.
Loops,
condi!onals,
etc.
5.0 pts
Full Marks
Loops,
condi”onals,
assignment
all s”ll work
correctly.
3.0 pts
Some mistakes
Separated the func”on code from the
interpreter part 2 code, but something
done broke a M_state or M_value from
part 2 of the interpreter.
0.0 pts
No Marks
Did not successfully separate the
func”on implementa”on from the
rest of the language features, and
now much is broken.
Global
variables
5.0 pts
Full Marks
Global variables are correctly
modified and updated when used
in a func”on.
3.0 pts
Uses but does not update globals
Global variables are used, but the
values are not correctly updated and
maintained.
0.0 pts
No Marks
The func”ons
cannot use global
variables.
Throw/catch 5.0 pts
Full Marks
Throw can
correctly
work across
func”ons.
3.0 pts
Good
Throw correctly exits
func”ons, but the
environment in the catch or
finally is not correct.
0.0 pts
No Marks
Throw does not leave the func”on (for example,
failed to pass the throw con”nua”on where
needed or failed to make M_value tail recursive).
Spring 2018
Home
Announcements
Syllabus
Modules
Assignments
Quizzes
Grades
People
Discussions
Account
Dashboard
Courses
Groups
Calendar
Inbox
Help
2018/3/29 01)57
第 1 ⻚页（共 1 ⻚页）