联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2021-04-27 10:52

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


版权所有:编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。