Lab 9: snek | 6.009 Spring 2021
The questions below are due on Friday April 30, 2021; 05:00:00 PM.
Table of Contents
1) Preparation
2) Introduction
2.1) LISP and Snek
3) Interpreter Design
4) Tokenizer
5) Parser
5.1) Examples
6) Evaluator
6.1) Evaluator 1: Calculator
6.1.1) Testing Your Code: REPL
6.2) Additional Operations
6.3) Adding Support for Variables
6.4) Environments
6.4.1) Environments: Example
6.4.2) Environments: Initial Structure
6.5) Evaluator Changes
6.5.1) Changes to evaluate
6.5.2) Changes to parse
6.5.3) Examples
6.6) Environments, Test Cases, and the REPL
6.6.1) REPL
6.7) Adding Support for Functions
6.7.1) Defining functions
6.7.2) Calling Functions
6.7.3) Examples
6.7.4) Changes to parse
6.7.5) Changes to evaluate
6.7.6) Easier Function Definitions
7) Endnotes
8) Code Submission
9) Checkoff
9.1) Grade
1) Preparation
This lab assumes you have Python 3.6 or later installed on your machine (3.9 recommended).
The following file contains code and other resources as a starting point for this lab: lab9.zip
Most of your changes should be made to lab.py, which you will submit at the end of this lab. Importantly, you should not add
any imports to the file.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 2/22
You can also see and participate in online discussion about this lab in the "Lab 9" Category in the forum.
This lab is worth a total of 4 points. Your score for the lab is based on:
correctly answering the questions throughout this page (0.5 points)
passing the test cases from test.py under the time limit (1 points), and
a brief "checkoff" conversation with a staff member to discuss your code (2.5 points).
All questions on this page (including your code submission) are due at 5pm Eastern on Friday, 30 April. However, you
are strongly encouraged to start this lab early.
Please Start Early
You are strongly encouraged to start this lab early if possible.
Note: Solutions
Note that because lab 10 builds on lab 9, solutions for lab 9 will not be published (though solutions for lab 10 will be
published after it has come due).
Reminder: Collaboration Policy
Please also review the collaboration policy before continuing. In particular, note that you are not allowed to use
any code other than that which you have written yourself, including code from online sources.
2) Introduction
Throughout 6.009, we have spent a lot of time discussing the behind-the-scenes operation of Python through environment
diagrams. But you may have wondered along the way: how does Python actually do those things? What is actually doing them?
It turns out that the thing doing that work is another program! In particular, a program called CPython, the Python interpreter,
is responsible for interpreting your programs' source code and actually implementing the corresponding behaviors.
In this lab, we'll explore this idea even further by implementing our own interpreter for a dialect of LISP, one of the earliest
high-level programming languages, and one with a strong historical connection to MIT (LISP was invented by John McCarthy at
MIT in 1958, and the Scheme dialect of LISP was used in MIT's introductory programming subject from ~1975-20071
!).
The LISP dialect we'll implement in this lab will be similar to Python in many ways, but in some ways it will be a bit smaller; so
we'll call it Snek.
Its syntax is simpler than Python's, and the complete interpreter will fit in a single Python file. However, despite its small size,
the language we will implement here will be powerful! We will end up implementing a large portion of the environment model
we have been discussing, and our little language will actually be Turing-complete, i.e., in theory, it will be able to solve any
possible computational problem (so it would be possible, for example, to use it to write implementations of any of the labs we
have done so far in 6.009!).
2.1) LISP and Snek
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 3/22
As with most LISP dialects, the syntax of Snek is far simpler than that of Python. All-in-all, we can define the syntax of Snek as
follows:
Numbers (e.g., 1) and symbols (things like variable names, e.g., x) are called atomic expressions; they cannot be broken
into pieces. These are similar to their Python counterparts, except that in Snek, operators such as + and > are symbols,
too, and are treated the same way as x and fib.
Everything else is an S-expression: an opening round bracket (, followed by one or more expressions, followed by a
closing round bracket ). The first subexpression determines what the S-expression means:
An S-expression starting with a keyword, e.g. (function ...), is a special form; the meaning depends on the
keyword. For this lab, we will only have two keywords: function (for creating function objects) and := (for defining
variables). In next week's lab, though, we will add more keywords and special forms.
An S-expression starting with a non-keyword, e.g. (fib ...), is a function call, where the first element in the
expression is the function to be called2
, and the remaining subexpressions represent the arguments to that function.
And that's it! The whole syntax is described by the two bullet points above. For example, consider the following definition of a
function that computes Fibonacci numbers in Python:
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
We could write an equivalent program in Snek:
(:= (fib n)
(if (<= n 1)
n
(+ (fib (- n 1)) (fib (- n 2)))
)
)
Here is a brief example of an interaction with a LISP interpreter that demonstrates a few more examples of the structure of the
language:
> (+ 3 2)
=> 5
> (:= (square x) (* x x))
=> (function (x) (* x x))
> (:= (fourthpower x) (square (square x)))
=> (function (x) (square (square x)))
> (fourthpower 1.1)
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 4/22
=> 1.4641000000000004
> (+ 3 (- 7 8))
=> 2
There are a couple of key syntactic differences from Python:
LISP consists only of expressions, with no statements. Every expression evaluates to a value.
LISP uses prefix notation, e.g., (+ 3 2) instead of 3 + 2.
LISP's syntax is simpler but consists of a lot more parentheses.
Using so many parentheses might take some getting used to, but it helps to keep the language simple and consistent. Some
people have joked that LISP stands for "Lots of Insipid and Silly Parentheses," though some might argue instead that it stands
for "LISP Is Syntactically Pure." :)
from XKCD
3) Interpreter Design
Despite its small size, the interpreter for Snek will still be rather complicated. To help manage this complexity, we'll start with a
very small language, and we'll gradually add functionality until we have a fully featured language. As with most interpreters, our
Snek interpreter will consist of three parts:
A tokenizer, which takes a string as input and produces a list of tokens, which represent meaningful units in the syntax of
the programming language.
A parser, which takes the output of the tokenizer as input and produces a structured representation of the program as its
output.
An evaluator, which takes the output of the parser as input and actually handles running the program.
4) Tokenizer
Our first job is tokenizing. In Snek, we'll have exactly three kinds of tokens: opening round brackets (, closing round brackets ),
and everything else. Each token is separated by whitespace (either spaces or the special "newline" character '\n'). Your first
task for the lab is to write a function called tokenize, which takes a single string representing a program as its input and
outputs a list of tokens. For example, calling tokenize("(foo (bar 3.14))") should give us the following result: ['(',
'foo', '(', 'bar', '3.14', ')', ')']. Note that at this point, all of our tokens should be strings.
Unlike in Python, indentation does not matter, so, for example, the tokenize function should produce exactly the same output
for both of the following programs:
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 5/22
(:= circle-area
(function (r)
(* 3.14 (* r r))
)
)
(:= circle-area (function (r) (* 3.14 (* r r))))
Your tokenize function should also handle comments. A comment in Snek is prefixed with a semicolon ( ;), instead of the
octothorpe ( #) used by Python. If a line contains a semicolon, the tokenize function should not consider that semicolon or the
characters that follow it on that line to be part of the input program3
.
What should be the result of tokenize("(cat (dog (tomato)))")?
['(', 'cat', '(', 'dog', '(', 'tomato', ')', ')', ')']
Submit
You have submitted this assignment 1 time.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
What should be the result of tokenizing the following expression?
;add the numbers 2 and 3
(+ ; this expression
2 ; spans multiple
3 ; lines
)
['(', '+', '2', '3', ')']
Submit
You have submitted this assignment 1 time.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
Check Yourself:
Note that this is similar in many ways to the tokenizer we wrote as part of lab 8. What are the key similarities and
key differences? How can we modify that tokenizer to work in this context?
Implement the tokenize function in lab.py. Note that, while doing so, you may find some of the methods of the built-in str
type useful.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 6/22
5) Parser
Our next job is parsing the list of tokens into an abstract syntax tree, a structured representation of the expression to be
evaluated. Implement the parse function in lab.py. parse should take a single input (a list of tokens as produced by
tokenize) and should output a representation of the expression, where:
A number is represented according to its Python type (i.e., integers as int and decimals as float).
A symbol is represented as a string.
An S-expression is represented as a list of its parsed subexpressions.
For example, the program above that defined circle-area should parse as follows:
[':=', 'circle-area', ['function', ['r'], ['*', 3.14, ['*', 'r', 'r']]]]
Note that the syntax of this language is similar to that of the little language we created for symbolic algebra in the previous lab,
and so it might be a good idea to structure your parser for this lab in a similar fashion. One key difference between the two
languages is that, while our symbolic algebra language always had exactly two subexpressions to parse inside of parentheses,
S-expressions can contain arbitrarily many subexpressions. Another is that we will handle malformed input graciously; in
particular, in the case that parentheses are mismatched in the input, the function should raise a SnekSyntaxError.
Your code in this lab (including parse) should not use Python's built-in eval or exec functions.
You may find the following questions helpful before jumping in to your implementation (and you may even with to encode
these, or similar examples, as doctests in your code).
5.1) Examples
What should be the result of calling parse on the output from the first concept question above?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
What should be the result of calling parse(['2'])?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 7/22
What should be the result of calling parse(['x'])?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
What should be the result of calling parse(['(', '+', '2', '(', '-', '5', '3', ')', '7', '8', ')'])?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
6) Evaluator
"How do you eat a big pizza? One little bite at at time..."
-Anonymous
After parsing, we have the program in a form that is (relatively) easy to work with, and we can move on to implementing the
evaluator, which will handle actually running the program. This part of the interpreter will get fairly complicated, so we will start
small and add in more pieces later. We will make several "false steps" along the way, where we'll need to make modifications to
pieces we had implemented earlier.
Because of this, it will be important to save backups of your lab.py file after every major modification (maybe every
time you get some new test cases to pass), so that if something goes wrong, you can revert to a working copy. You are
welcome to use a version control system like Mercurial or Git for this if you are familiar with those tools, but you are
not allowed to use a public code forge like GitHub or Gitlab for your backups.
6.1) Evaluator 1: Calculator
We'll hold off on implementing variables, lists, conditionals, and functions for a little while; for now, we'll start by implementing
a small calculator that can handle the + and - operations.
Note that we have provided a dictionary called snek_builtins in lab.py, which maps the names + and - to functions. Each
of these functions takes a list as an argument and returns the appropriate value. Look at the snek_builtins dictionary to get a
sense of the form of those functions.
Define a function evaluate, which takes as its sole input an expression of the same form as the parser's output. evaluate
should return the value of the expression:
If the expression is a symbol representing a name in snek_builtins, it should return the associated object.
If the expression is a number, it should return that number.
If the expression is a list (representing an S-expression), each of the elements in the list should be evaluated, and the
result of evaluating the first element (a function) should be called with the remaining elements passed in as arguments4
.
The overall result of evaluating such a function is the return value of that function call.
If the expression is a symbol that is not in snek_builtins, it should raise a SnekNameError. Or, if it is a list whose first
element is not a valid function, it should raise a SnekEvaluationError
5
.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 8/22
For example:
evaluate('+') should return the function object associated with addition.
evaluate(3.14) should return 3.14.
evaluate(['+', 3, 7, 2]), which corresponds to (+ 3 7 2), should return 12 (i.e., the result of calling the + function
on the given arguments).
Note that this should work for nested expressions as well. evaluate(['+', 3, ['-', 7, 5]]), which corresponds to (+ 3 (-
7 5)), should return 5.
Implement the evaluate function in lab.py according to the rules above.
6.1.1) Testing Your Code: REPL
It is kind of a pain to have to type out all of the arguments to evaluate each time we call it.
As such, we'll implement a REPL (a "Read, Evaluate, Print Loop") for Snek. A REPL has a simple job: it continually prompts the
user for input until they type QUIT. Until then, it:
accepts input from the user,
tokenizes and parses it,
evaluates it, and
prints the result.
If an error occurs during any of these steps, an error message should be displayed, and that expression may be ignored, but the
program should not exit.
To implement the REPL, we can make use of Python's built-in input function. input takes an argument representing a prompt
to be displayed to the user and returns the string that they type (it is returned when they hit enter). If an exception occurs
during that evaluation, you should report the error but your REPL should not stop (i.e., it should move on to asking for the next
expression to be evaluated rather than erroring out).
The following shows one possible interaction with a REPL, with a particular prompt and output formatting (you are welcome to
use whatever formatting you like!):
in> (+ 2 3)
out> 5
in> (+ 2 (- 3 4))
out> 1
in> (- 3.14 1.14 1)
out> 1.0000000000000004
in> (+ 2 (- 3 4 5))
out> -4
in> QUIT
Note that your REPL only needs to handle one-line inputs. You do not need to handle the case of a multiline expression being
entered through the REPL.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 9/22
Implement a REPL for Snek and use it to test your evaluator. The REPL can/should be one of your main means of testing
moving forward; feel free to try things out using the REPL as you work through the remainder of the lab. The functionality of
your REPL will not be tested automatically; rather, it will be tested during the checkoff. The REPL should only start when the lab
is run directly, not when lab.py is imported from another script.
6.2) Additional Operations
Implement two new operations: * and /:
* should take arbitrarily many arguments and should return the product of all its arguments.
/ should take arbitrarily many arguments. It should return the result of successively dividing the first argument by the
remaining arguments6
.
(Hint: where can you put these operations so that they are usable by the interpreter?)
After implementing the evaluator and the * and / operations, try them out in the REPL.
6.3) Adding Support for Variables
Next, we will implement our first special form: variable definition using the := keyword (you may wish to read this section and
section 6.4 in their entirety before implementing this behavior).
A variable definition has the following syntax: (:= NAME EXPR), where NAME is a symbol and EXPR is an arbitrary expression.
When Snek evaluates a := expression, it should associate the name NAME with the value that results from evaluating EXPR. In
addition, the := expression should evaluate to the result of evaluating EXPR
7
.
The following transcript shows an example interaction using the := keyword:
in> (:= pi 3.14)
out> 3.14
in> (:= radius 2)
out> 2
in> (* pi radius radius)
out> 12.56
in> QUIT
Note that := differs from the function calls we saw earlier. It is a special form that does not evaluate the name that follows it; it
only evaluates the expression that follows the name. As such, we will have to treat it differently from a normal function call.
In addition, in order to think about how to implement :=, we will need to talk about the notion of environments.
6.4) Environments
Admitting variable definition into our language means that we need to be, in some sense, more careful with the process by
which expressions are evaluated. We will handle the complexity associated with variable definition by maintaining structures
called environments. An environment consists of bindings from variable names to values, and possibly a parent environment,
from which other bindings are inherited. One can look up a name in an environment, and one can bind names to values in an
environment.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 10/22
The environment is crucial to the evaluation process, because it determines the context in which an expression should be
evaluated. Indeed, one could say that expressions in a programming language do not, in themselves, have any meaning. Rather,
an expression acquires a meaning only with respect to some environment in which it is evaluated. Even the interpretation of an
expression as straightforward as (+ 1 1) depends on an understanding that one is operating in a context in which + is the
symbol for addition. Thus, in our model of evaluation we will always speak of evaluating an expression with respect to some
environment.
To describe interactions with the interpreter, we will suppose that there is a "built-in" environment, consisting of bindings of the
names of built-in functions and constants to their associated values. For example, the idea that + is the symbol for addition is
captured by saying that the symbol + is bound in this environment to the primitive addition procedure we defined above. The
global environment will have this environment as its parent.
One necessary operation on environments is looking up the value to which a given name is bound. To do this, we can follow
these steps:
If the name has a binding in the environment, that value is returned.
If the name does not have a binding in the environment and the environment has a parent, we look up the name in the
parent environment (following these same steps).
If the name does not have a binding in the environment and the environment does not have a parent, a SnekNameError
is raised.
Note that looking up a name in an environment is similar to looking up a key in a dictionary, except that if the key is not found,
we continue looking in parent environments until we find the key or we run out of parents to look in.
In order to make variables work properly, you will need to implement the kind of lookup described above in Python. To this
end, you should create a class to represent environments.
Check Yourself:
What information should be stored as instance attributes of this class? What kind of methods should the class
support?
It is up to you to decide how exactly to implement environments and the associated lookups within this structure. Details of
your implementation will not be tested directly by the automatic checker; rather, your implementation will be tested by looking
at the end-to-end behavior of your evaluator. Regardless of the details of your implementation, you should make sure your
environment representation can handle variables with arbitrary names (i.e., any sequence of characters that doesn't
represent a number and that doesn't contain parentheses or spaces should be treated as a variable name), and you should be
prepared to discuss your implementation during the checkoff.
6.4.1) Environments: Example
The following shows an example of an environment structure, where arrows indicate each environment's parent, if any. Here we
have four environments (each of which might be an instance of the class you created to represent environments), labeled E1,
E2, E3, and E4. Both E2 and E3 have E1 as a parent environment, and E4 has E3 as a parent environment. E1 does not have a
parent environment.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 11/22
We say that the values x, y, and z are bound in E1. Note that x and y are bound in E2; x is bound in E3, and a is bound in
E4. Looking up a name, we work our way up the arrows until we find the name we are looking for. For example, looking up a in
E4 gives us the value 1, and looking up z in E4 gives us 5.
Notice that, as was mentioned above, the environment is crucial for determining the result of an expression.
What is the result of evaluating x in E1?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
What is the result of evaluating x in E2?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
What is the result of evaluating x in E3?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 12/22
What is the result of evaluating x in E4?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
Also note that the := keyword always operates directly on the environment in which it is evaluated. If we were to evaluate (:=
y 8) in E4, this would result in a new binding inside of E4 (without affecting the parent environments):
Answer the following questions about variable lookup in this updated environment:
What is the result of evaluating y in E1?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
What is the result of evaluating y in E2?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 13/22
What is the result of evaluating y in E3?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
What is the result of evaluating y in E4?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
6.4.2) Environments: Initial Structure
Running a program in this language typically involves evaluating multiple expressions, one after the other, in the same
environment, and so we will take a moment here to think about what the initial structure of these environments should look
like.
When we first start a new REPL, we will need to think about two main environments: an environment to hold the built-in values
(such as the + function) and a "global" environment where top-level definitions from users' programs will be bound. Then,
every expression we provide to the REPL should be evaluated in that global environment.
For example, running the code below from the REPL should result in the environment structure shown in the picture that
follows:
in> (:= x 3)
out> 3
in> (:= y 4)
out> 4
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 14/22
Note that when we look up any of the built-in variables from the global environment, we end up finding them in the built-ins
environment.
6.5) Evaluator Changes
Now, we'll need to add support for variable definition and lookup to our interpreter by implementing a Python structure for
representing an environment and modifying our interpreter so that it handles variables and the := keyword.
6.5.1) Changes to evaluate
Beyond implementing a representation for environments, we will need to make some modifications to our evaluate function.
We will need to:
modify evaluate so that it takes a second (optional) argument: the environment in which the expression should be
evaluated. If no environment is passed in, an empty environment should be used, whose parent is an environment
containing all the bindings from the snek_builtins dictionary.
make sure that evaluate handles the := keyword properly, evaluating the given expression and storing the result in the
environment that was passed to evaluate.
modify the way symbols are handled in evaluate, so that if the symbol exists as a key in the environment (or a parent
environment), evaluate returns the associated value.
6.5.2) Changes to parse
We will also want to adjust our parse function. Note that the form of := is well-defined: it should always have exactly three
elements (the := keyword, the name of a variable, and an expression). As such, trying to create a := expression that has more
(or fewer) elements should raise a SnekSyntaxError.
Check Yourself:
There are several interesting design decisions here, which are worth thinking about. For example:
Why should something like (:= 7 8) or (:= x) be a syntax error, rather than an evaluation error?
Why might we want to perform these checks while parsing, rather than simply performing them when we try
to evaluate a malformed expression?
6.5.3) Examples
Consider evaluating the following expressions in order from the same REPL (i.e., in the same environment). What is the result of
evaluating each of these expressions?
input: (+ 3 2 4 (- 2 7 8))
output:
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 15/22
input: (:= x (+ 2 3))
output:
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
input: (:= x2 (* x x))
output:
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
input: (+ x2 x)
output:
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
These can make for some nice test cases when you implement your code! You may also wish to test some other similar
examples in your REPL to make sure things are working as expected.
6.6) Environments, Test Cases, and the REPL
All of the tests from this point on involve using your interpreter to run small programs by evaluating multiple expressions one
after the other in the same environment.
To make this kind of automatic checking possible, you should define a function called result_and_env that takes the same
arguments as evaluate but returns a tuple with two elements: the result of the evaluation and the environment in which the
expression was evaluated. Your code will not pass the tests without this function. Note also that this function should always
return the environment in which the expression was actually evaluated, even if no environment was explicitly passed to it. Note
that the result_and_env function only exists to help us with testing; it should probably not be a very complicated function,
and we should be careful to avoid duplicating logic between evaluate and result_and_env.
All test cases moving forward will use this function to simulate, in some sense, starting up a brand-new REPL, and evaluating
multiple expressions at that REPL in order. We do this by:
Calling result_and_env with the first expression and no environment specified (so that you should create a brand-new
one), and then
Calling result_and_env for each subsequent expression, each time passing in the environment that resulted from the
previous call (so that they all work in the same environment, which was created in the first call to result_and_env).
In order for this to work, we need result_and_env to behave as described above:
If an environment is given, the expression should be evaluated in that environment.
If no environment is given, you should make a brand new environment and evaluate the expression in that environment.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 16/22
And in either case, we want to return the result, as well as the environment in which that result was ultimately evaluated (either
the value that was passed in, or a newly-created environment).
It's in this way that we simulate evaluating multiple expressions in the same environment. If result_and_env isn't returning the
right environments, we might evaluate later expressions in a different environment from the one in which we defined the
variables on which that expression depends.
Another thing to be careful of here is making sure that you're always making a brand-new, empty environment every time
result_and_env (or evaluate) is called with no second argument passed in, rather than sharing the same environment in those
cases.
Real Programs in the Test Cases!
Note also that we are working with authentic programs here; and for each test case moving forward, there is a
corresponding file in the snek_code directory in the code distribution; these files contain the expressions that are
evaluated in the associated test case, with one expression on each line. A good exercise if you are failing a test case
would be to figure out by hand what each expression should evaluate to and then try them by pasting one line at a
time into your REPL (note that you should be able to open these files in your normal text editor).
If you are having trouble opening these files, or trouble figuring out why a given expression evaluates the way it does,
please don't hesitate to ask for help in office hours or on the forum!
6.6.1) REPL
Note that your REPL should also evaluate all of the expressions provided to it in the same environment. That is, we should
create the kind of structure described above (with a "global" environment that has the built-ins as its parent) when the REPL
first starts, and then evaluate all given expressions in that environment.
There are multiple different ways we could implement this behavior; you could directly create such an environment, or you
could try using your result_and_env function to accomplish the same goal (mirroring the way the test cases are implemented)
6.7) Adding Support for Functions
So far, we have a pretty nice calculator, but there are a few things missing before we can really call it a programming language.
One of those things is user-defined functions.
Currently, the operations we can perform are limited to the functions in the snek_builtins dictionary. We can really empower
a user of the language by allowing them to define functions of their own. As we've seen throughout 6.009, the ability to define
our own functions is a really powerful means of abstraction, and so this step will add a lot of power to our little language.
6.7.1) Defining functions
In order to be able to make use of functions, we first need a way for a user to define a new function. We will accomplish this via
the function special form8
.
A function expression takes the following form: (function (PARAM1 PARAM2 ...) EXPR). The result of evaluating such an
expression should be an object representing that function (note that this expression represents a function definition, not a
function call). Importantly, there are a few things we need to keep track of with regard to functions. We need to store:
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 17/22
the code representing the body of the function (which, for now, is restricted to a single expression representing the return
value)
the names of the function's parameters
a pointer to the environment in which the function was defined
You should define a class to represent your user-defined functions. Once again, it is up to you to determine what exactly
how to represent things inside of these functions; but it is important that, however it is represented, it stores the information
above (and also that you are able to distinguish it from the other types of objects we have seen so far)9
.
Check Yourself:
What information should be stored as instance attributes of this class? What kind of methods should the class
support?
For example, the result of evaluating (function (x y) (+ x y)) in the global environment should be an object that stores
the following information:
the function's parameters, in order, are called x and y.
the function's body is the expression (+ x y).
the function was defined in the global environment.
6.7.2) Calling Functions
Defining functions is nice, but we also need a way to call these functions after we've defined them. When the first element in an
S-expression evaluates to a user-defined function, we will need to call the function by taking the following steps:
evaluate all of the arguments to the function in the current environment (from which the function is being called).
make a new environment whose parent is the environment in which the function was defined (this is called lexical
scoping).
in that new environment, bind the function's parameters to the arguments that are passed to it.
evaluate the body of the function in that new environment.
If we try to call something that is not a function, or if we try to call a function with the incorrect number of arguments passed in,
a SnekEvaluationError should be raised.
It is worth noting that these steps are very close, if not exactly the same, as the steps Python takes when it calls a function.
Several lectures and recitations contain examples of talking through this process; and the readings for 6.145 contain some
additional explanation and examples (see sections 4-8 of Functions and sections 1-2.5 of Functions 2).
6.7.3) Examples
Here are two examples of calling functions and using function. The first associates a name with the function and calls the
function using that name, whereas the second calls the function directly without first giving it a name.
in> (:= square (function (x) (* x x)))
out> function object
in> (square 2)
out> 4
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 18/22
in> ((function (x) (* x x)) 3)
out> 9
After evaluating the above code, what is the value of the variable x in the global environment?
--
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
Here is another example of a more-complicated function. Note that the result of calling (foo 3) below is a function, which is
then called with 2 as an argument. Note also that the value associated with the name x when we call (bar 2) is the 3 from
the environment in which that function was created, not the 7 from the environment in which it was called.
in> (:= x 7)
out> 7
in> (:= foo (function (x) (function (y) (+ x y))))
out> function object
in> (:= bar (foo 3))
out> function object
in> (bar 2)
What is the result when evaluating (bar 2) above?
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
After evaluating the above code, what is the value of the variable x in the global environment?
--
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 19/22
After evaluating the above code, what is the value of the variable y in the global environment?
--
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
Check Yourself:
Why does (bar 2) not evaluate to 9?
Show/Hide
It may also help to look at equivalent Python code:
x = 7
def foo(x):
return lambda y: x+y
bar = foo(3)
print(bar(2)) # this prints 5!
6.7.4) Changes to parse
function expressions have a well-defined form: one of them always consists of exactly three elements (the function keyword,
a list of parameters, and an expression representing the body of the function). In parse, if we attempt to create a function
expression that has more or fewer than those 3 elements, or whose second element is not a list of parameters (0 or more
strings representing parameter names), we should instead raise a SnekSyntaxError.
6.7.5) Changes to evaluate
We will also need to make sure that evaluate handles the function keyword properly, by creating a new function object that
stores the names of the parameters, the expression representing the body of the function, and the environment in which the
function was defined. We also need to modify evaluate to handle calling user-defined functions.
From a high-level perspective, your evaluator should now work in the following way, given an expression e:
If e represents a number, it should evaluate to that number.
If e represents a variable name, it should evaluate to the value associated with that variable in the given environment, or
it should raise an SnekNameError if a binding cannot be found according to the rules above.
If e represents a special form (such as :=), it should be evaluated according to the rules for that special form.
Otherwise, e is a compound expression representing a function call. Each of the subexpressions should be evaluated in
the given environment, and:
If the first subexpression is a built-in function, it should be called with the remaining subexpressions as arguments
(in order).
If the first subexpression is a user-defined function, it should be called according to the rules given above.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 20/22
If we try to call something that is not a function, or if we try to call a function with the incorrect number of arguments passed in,
a SnekEvaluationError should be raised.
Note
Note that in the case of an S-expression that isn't a special form, evaluating the first element in the S-expression gives
us the function that is to be called, regardless of how it is specified (so your evaluator code should not have
additional logic based on the syntactic form of that first element).
After you have made the changes above, try them out in the REPL using the examples from subsubsection 6.7.3. Once you are
reasonably certain that everything is working, try them with test.py.
Check Yourself:
How difficult was it to add the function special form? And how much did it complicate your code? Next week, we
will be adding several new special forms to the language, so it is worth thinking ahead to see if there are ways of
reorganizing your code to make adding new special forms easier.
6.7.6) Easier Function Definitions
Implementing user-defined functions has given a lot of power to our interpreter! But it is kind of a pain to type them out.
Implement a shorter syntax for function definitions, so that, if the NAME in a := expression is itself an S-expression, it is
implicitly translated to a function definition before binding. For example:
(:= (five) (+ 2 3)) should be equivalent to (:= five (function () (+ 2 3)))
(:= (square x) (* x x)) should be equivalent to (:= square (function (x) (* x x)))
(:= (add2 x y) (+ x y)) should be equivalent to (:= add2 (function (x y) (+ x y)))
This is nice not only because it is easier to type but also because it makes the definition of a function more closely mirror the
syntax we will use when calling the function.
Modify your evaluate function so that it handles this new form. After implementing this change, try it out in the REPL and then
in test.py. At this point, your code should pass all the tests in test.py.
Additionally, modify your parse function so that it raises a SnekSyntaxError in the case where the second element in a :=
statement is neither a name nor a list containing one or more parameters (strings representing paramater names).
7) Endnotes
At this point, we have a very nice start toward an interpreter for Snek. We have the ability to create variables and to define and
call functions. Note also that recursion and closures come about naturally as a result of the rules we have implemented for
calling functions (we don't have to do any additional work to get those features!). And hopefully implementing it has been an
illuminating experience implementing the various pieces of the environment model we've been discussing throughout the
semester!
However, we still have some work to do before our language is complete. In particular, next week, we will add support for
conditionals and lists, along with a few other niceties.
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 21/22
8) Code Submission
Select File No file selected
Submit
You have submitted this assignment 0 times.
This question is due on Friday April 30, 2021 at 05:00:00 PM Eastern time.
9) Checkoff
Once you are finished with the code, please come to office hours and add yourself to the queue asking for a checkoff. You
must be ready to discuss your code and test cases in detail before asking for a checkoff.
You should be prepared to demonstrate your code (which should be well-commented, should avoid repetition, and should
make good use of helper functions). In particular, be prepared to discuss:
your implementation of tokenize and parse
the structure of your class for representing environments
how your environment representation handles arbitrary variable names
how you set up and use environments in evaluate and result_and_env
the structure of your class for representing user-defined functions
how user-defined functions are called (including setting up the proper new environments)
a demonstration of your REPL (including shared environment, exiting on QUIT, staying alive after errors, and correctly
evaluating input expressions)
9.1) Grade
You have not yet received this checkoff. When you have completed this checkoff, you will see a grade here.
Footnotes
1 The book associated with this subject, Structure and Interpretation of Computer Programs, is considered by many to be one
of the best books ever written on the topic of programming.
2 Note that this first element can be an arbitrary expression. That is, it does not need to be a single name; it could be a more
complicated expression that evaluates to a function object.
3 Note that lines are separated by a special character '\n'.
4 Note that we pass these arguments to the function as a single list containing all arguments, rather than as separate
arguments
5 Note that when you raise an exception, you can include an error message with details about the specifics of that error with the
following syntax: raise SnekNameError("some error message here"). This can help greatly with debugging, as it can help
you locate the particular raise statement an error came from (and, ultimately, the cause of the exception).
4/24/2021 Lab 9: snek | 6.009 Spring 2021
https://py.mit.edu/spring21/labs/lab9 22/22
6
Although we will not be explicitly testing for them, there are a few "edge cases" to consider when implementing these
functions. For multiplication, if we take the product of some numbers and multiply it by the product of
some numbers , we should get the same result as if we multiplied
. This suggests:
Multiplication with 1 argument passed in should return that argument itself.
Multiplication with no arguments should return 1.
(In that same vein, note that (+) evaluates to 0, and (+ 2) evaluates to 2)
For division, it's not clear that such a relationship exists. But one set of rules that could make sense (and which is implemented
in the MIT/GNU Scheme dialect of LISP) is:
Division with no arguments should raise an exception.
Division with a single argument should return .
7 Note that the := keyword is equivalent to Python's "walrus operator", which was new in Python 3.8.
8 Many languages, including Python, will instead call this lambda because it is strongly rooted in Church's lambda calculus.
9
If you want to, you can implement the __call__ "dunder" method to make instances of your class be callable like regular
Python functions.
a0 × a1 × a2 × …
b0 × b1 × b2 × … a0 × a1 × a2 × … × b0 × b1 ×
b2 × …
x 1/x
版权所有：编程辅导网 2021 All Rights Reserved 联系方式：QQ:99515681 微信：codinghelp 电子信箱：99515681@qq.com
免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。
