-
Notifications
You must be signed in to change notification settings - Fork 0
/
part3.html
168 lines (137 loc) · 7.1 KB
/
part3.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
<html>
<head>
<title>EECS 345: Interpreter Project, Part 3</title>
</head>
<body>
<h2>EECS 345: Programming Language Concepts</h2>
<h2>Interpreter Project, Part 3</h2>
<h3>Due Wednesday, April 12</h3>
<p>In this homework, you will expand on the interpreter of part 2 adding function definitions.
We still assume all variables store integers and boolean.
Likewise, all functions will only return integers and boolean.</p>
<p>While normal C does not allow nested functions, the gcc compiler <em>does</em> allow nested functions as an extension to C, so let's implement them!</p>
<p><em>For those seeking a small extra challenge:</em> try implementing both the <em>call-by-reference</em> and the <em>call-by-value</em>
parameter passing styles.</p>
<p>An example program that computes the greatest common divisor of two numbers is as follows:</p>
<pre>
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);
}
</pre>
<p>Here is another example program that uses recursion:
<pre>
function factorial (x) {
if (x == 0)
return 1;
else
return x * factorial(x - 1);
}
function main () {
return factorial(6);
}
</pre>
Note that only assignment statements are allowed outside of functions. Functions do not have to
return a value. The parser will have the following additional constructs:
<pre>
function a(x, y) { => (function a (x y) ((return (+ x y)))
return x + y;
}
function main () { => (function main () ((var x 10) (var y 15) (return (funcall gcd x y))))
var x = 10;
var y = 15;
return gcd(x, y);
}
</pre>
The final value returned by your interpreter should be whatever is returned by <tt>main</tt>. </p>
<p>Nested functions can appear anywhere in the body of a function. Any name in scope in a function body will be in scope in a function defined inside that body.
<pre>
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;
}
</pre>
<p>We will use a similar style as C++ for call-by-reference:
<pre>
function swap(&x, &y) { => (function swap (& x & y) ((var temp x) (= x y) (= y temp)))
var temp = x;
x = y;
y = temp;
}
</pre></p>
<p>Function calls may appear on the right hand side of global variable declaration/initialization statements, but the function
(and any functions that function calls) must be defined before the variable declaration. Otherwise, functions that are used
inside other functions do not need to be defined before they are used.</p>
<p>It is an error to use call-by-reference on anything other than a variable. For example, if the program contains
<tt>swap(x, x + 10)</tt> with the above definition of <tt>swap</tt>, you should give an error because <tt>x + 10</tt> is not a variable.</p>
<p>You do not have to stick to strict functional programming style, but you should avoid
global variables because they will make your life harder. A new parser is provided
for you, <tt>functionParser.scm</tt>, that will parse code
containing functions/methods as in the above examples. To
use the parser, type the code into a file, and call <tt>(parser "<em>filename</em>")</tt> as before. To call the
parsers from your interpreter code, place the command <tt>(load "<em>parsename</em>")</tt> in the Scheme file.</p>
<h4>What your code should do</h4>
<p>You should write a function called <tt>interpret</tt> that takes a filename, calls <tt>parser</tt>
with the filename, evaluates the parse tree returned by <tt>parser</tt>, and returns the
proper value returned by <tt>main</tt>. You are to maintain
an environment/state for the variables and return an error message if the program attempts to use a variable before it is declared,
attempts to use a variable before it is initialized, or attempts to use a function that has not been defined.</p>
<h4>Some hints</h4>
<p><strong>Terminology</strong> In this interpreter, we will be talking about <em>environments</em> instead of <em>states</em>. The state consists of all
the active bindings of your program. The environment is all the active bindings that are in scope.</p>
<p>1. Note that the base layer of your state will now be the global variables and functions. You should create an outer "layer"
of your interpreter that just does M_state functions for variable declarations and function definitions.
The declarations and assignments should be similar to what you did in your part 2 interpreter. The functon definitions will need to bind the function closure to
the function name where the closure consists of the formal parameter list, the function body, and a function that creates the function environment from the current environment.</p>
<p>2. Once the "outer" layer of your interpreter completes, your interpreter should then look up the <tt>main</tt> function in the state and call that function. (See the next step
for how to call a function.</p>
<p>3. You need to create a M_value function to call a function. This function should do the following: (a) create a function environment using the closure function on the current environment,
(b) evaluate each actual parameter in the current environment and bind it to the formal parameter in the function environment, (c) interpret the body of the function with the function environment. Note
that interpreting the body of the function should be, with one change, <em>exactly</em> what you submitted for <em>Interpreter, Part 2</em>. 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 evaluating the function body and copy back the new values of the global variables to
the current environment/state.</p>
<p>4. Change the M_state and M_value functions for statements and expressions, respectively, to expect function calls.<p>
<p>5. Test the interpeter on functions without global variables,
and then test your functions using global variables.
One tricky part with the functions is that, unlike the other language
constructs we have created, function 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 function works.</p>
<p>6. Since exceptions can happen anywhere that a function call can occur, you may discover more places that need the throw continuation. If you used call/cc for throw, then you should not have to
modify anything else in your interpreter from part 2. If you used tail recursion for throw, you will need to make the M_value functions tail recursive for throw to work correctly.
</p>
</body>
</html>