Tag: cs 111

Guide to the Scheme Interpreter Project (BYU CS 111) Part 2
Part 1 if you missed it

In part 2 we will be implementing the code for procedures. By the end of this, you will be able to interpret user-defined functions, lambda functions, and something special called “Mu-procedures” that you will soon learn to dislike. This part will be handling problems 6-11. Good luck.

Problem 6: “Begin”

In Scheme, we have the ‘begin’ special form. This lets us evaluate through a series of expressions in scheme and return only the value of the last expression.

Excerpt from Berkeley CS61A Documentation

It is useful because it allows for side effects from the first expressions to take place while returning only the evaluated value of the last expression in the series. For examples, see the examples in the CS 111 instructions and for even more understanding, read the short documentation for MIT/GNU’s implementation of scheme. Note from the documentation, that writing begin is often pointless because many special forms already apply it implicitly.

What you need to do, is implement the eval_all() function in scheme_eval_apply.py. Eval_all() takes in two arguments: expressions and env.

Scheme

(1 2 3)

Python

expressions = Pair(1, Pair(2, Pair(3, nil)))

You should go through expressions recursively, evaluating each one using scheme_eval(). When you get to the last expression, evaluate it like the others, but also return its value.

For more help

Problem 7: Lambda Procedures

We need to implement the do_lambda_form() function in scheme_forms.py. This function takes in two arguments: expressions and env.

expressions is going to be objects of class Pair representing our formals (just operators for the lambda function) and the second part is the operations.

The variable formals is given to us: formals = expressions.first

Scheme ———————

(lambda (x y) (+x y))

Python ———————–

expressions = Pair(Pair(‘x’, Pair(‘y’, nil)), Pair(Pair(‘+’, Pair(‘x’, Pair(‘y’, nil))), nil))

formals = Pair(‘x’, Pair(‘y’, nil)) #These are the arguments/operators to the lambda func

expressions.rest = Pair(Pair(‘+’, Pair(‘x’, Pair(‘y’, nil))), nil) # the operations

What we need to do is take the given information and return a LambdaProcedure object. The LambdaProcedure class is defined in scheme_classes.py. It would be very helpful to review it because you need to initialize and return an object from it.

Hint: LambdaProcedure Class

The code you write for this problem should be a single line long

For more help

Problem 8: Making New Frames

In this problem we will be dealing with frames and the creation thereof. When we make a frame, we are initializing an object of class Frame. Each frame has bindings (a dict representing all the variables and values within a frame) and parent (the frame from which the new frame comes from).

In Problem 1 we made the define() method that allowed us to define variables by saving them into the instance variable bindings. ! Remember this !

For Problem 8, we are implementing the class method make_child_frame() which takes in two arguments: formals and vals.

formals is a list of the symbols (the variables to which we are assigning values)

vals is a list of the values we are assigning to the symbols in formals

Scheme

(define a 1)

(define b 2)

(define c 3)

Python

formals = Pair(‘a’, Pair(‘b’, Pair(‘c’, nil)))

vals = Pair(‘a’, Pair(‘b’, Pair(‘c’, nil)))

The CS 111 website gives four steps which are decently clear and pretty much make up the pseudo code for this problem:

Hint: Assigning the Values

You somehow need to iterate through each of the lists and get the values at each point to be bound to one another. Personally, I wrote a function that converted linked lists into simple python lists and then I iterated through the python lists because that was easiest to me. There are multiple and probably better ways to do this.

Hint: Raise Error Syntax

raise Error(“Custom Error Message”)

For more help

For even more help

And for even more, but less related help

Problem 9: Lambda meets Frame

This is another problem that should not require a lot of code, only two lines to be exact. In scheme_eval_apply.py we have the scheme_apply() function that applies procedures to arguments.

scheme_apply() takes in procedure, args, and env. procedure is going to be an object of class Procedure. It could be a BuiltinProcedure or a LambdaProcedure (MuProcedure or MacroProcedure later too).

procedure = LambdaProcedure(operators, operations, env)

LambdaProcedure(Pair(‘x’, nil), Pair(Pair(‘*’, Pair(‘x’, Pair(‘x’, nil))), nil), <Global Frame>)

args stores the values of the arguments that our procedure is going to be applied to. In the above box it would be the value that replaces the x’s in the LambdaProcedure.

Scheme

(define square (lambda (x) (* x x)))

(square 21)

Python

args = Pair(21, nil)

When we make a call to a lambda function, it opens a new frame in which the operators are defined and the operations take place. That means you need to make a new frame whose parent is the current frame. (First Line) Then you need to return an evaluation of all the body of the lambda function (the operations part) using eval_all(). (Second Line)

Hint: SchemeError: unknown identifier: y

Recall from the first box above in Problem 9, that an object of LambdaProcedure is initialized by taking in the current environment (env) and makes an instance variable: self.env. An unkown identifier error will occur if we are not creating the new frame based off the current frame self.env.

How can you call the make_child_frame() method from the LambdaProcedure‘s instance variable self.env instead of just from env? 🤷

Hint: Making New Frames

In problem 8 we implemented the method of class Frame make_child_frame(formals, vals)

Unfortunately there is no more help ):

Problem 10: Defining Func’s Shorthandedly

In Problem 10 we are going to edit the do_define_form() function that we wrote a part of in Problem 4. In Problem 4 we made it so that we could assign values to a variable name. Now we want to make it so we can assign functions to a variable name using the following syntax in Scheme:
scm> (define (square x) (* x x)) square scm> (square 2) 4
do_define_form() takes two arguments: expressions and env. expressions, as normal, is a list of objects from the class Pair. Consider the following example:

Scheme

(define (f x y) (+ x y))

Python

expressions =

Pair(Pair(‘f’, Pair(‘x’, Pair(‘y’, nil))), Pair(Pair(‘+’, Pair(‘x’, Pair(‘y’, nil))), nil))

You need to dissect expressions to get the function name, the operators, and the operations. Keep in mind we have the variable signature which is equal to the red highlighted portion of expressions above. To define the function we need to take the variable name and assign an object of class LambdaProcedure to it. To create this object we are going to use the function do_lambda_form() from Problem 7.

As a reminder, do_lambda_form() takes in two arguments: expressions and env. It returns an object of class LambdaProcedure. expressions must be a scheme list represented by Pair class objects that hold the operators and the operations. You must create this Pair object in which the first part is the operators and the rest is the operations.

Once you have the LambdaProcedure object, assign it to the variable name in the current frame.

For more help

Problem 11: The ‘Mu’

The first important thing is to understand the difference between lexical and dynamic scoping. Here is the explanation again from the CS 111 website:

CS 111 Website Description

First, implement do_mu_form() in scheme_forms.py so that it returns an object of class MuProcedure. This should probably only be one line long. If you need help just look at your code for Problem 7. We are essentially doing the same thing except we are ignoring env because when initializing a MuProcedure we ignore the current frame because of dynamic scoping.

Make sure to look at the __init__() for MuProcedure to see what it intakes as arguments:

The class MuProcedure

Here are what the arguments to the __init__() would look like if we were initializing a MuProcedure object based off of the given scheme expression:

Scheme

(define f (mu (x) (+ x y)))

Python

formals = Pair(‘x’, nil) #variable name

body = Pair(Pair(‘+’, Pair(‘x’, Pair(‘y’, nil))), nil) #operations

Second, you need to edit the scheme_apply() function in scheme_eval_apply.py for when the procedure is a MuProcedure. Return the evaluation of the body of the MuProcedure object, but remember you have to do that using the correct frame that results in dynamic scoping. So beforehand make a new frame based off of the current frame. Use this new frame when you evaluate the MuProcedure.

Hint: Evaluating a Procedure

In Problem 6 we implemented the eval_all() function which we have been using for evaluating procedures. It intakes expressions and env.

eval_all(expressions, env)

Hint: Creating a New Frame

Review Problem 8 in which we implemented the method make_child_frame() of class Frame

For more help

</end>

Hopefully this was a sufficient help. Please submit any corrections or questions in the comments below. I will try my best to answer and update the article accordingly.

Part 3
December 10, 2022
Guide to the Scheme Interpreter Project (BYU CS 111) Part 1

part 2

The Scheme Interpreter project is the most daunting and if you’re me, by far the longest assignment (14 hours) in CS 111. In the project, you program bits and pieces of an interpreter for scheme in python. The project details and files can be found on the CS 111 website. Before beginning the project, I recommend reading the following chapters from Composing Programs: 3.2: Functional Programming, 3.4: Interpreters for Languages with Combination, and 3.5: Interpreters for Languages with Abstraction. Berkeley’s CS61a Youtube channel also has videos with helpful hints for specific questions from the scheme project.

The project is divided into four parts: The Evaluator, Procedures, Special Forms, and Write Some Scheme. I will not be going over the last part, because I do not really like writing code in scheme.

Problem 1: Define and Lookup

The frame is the current environment of a program in which variables are defined. Calling a function creates a new child frame with its own variables and values. In this problem we will be creating the functions in python that will allow us to make variables and bind values to them.

Our scheme interpreter (all of the python files) has a class, Frame, which will be where we make frames and control what variables and values are stored in them.

The Frame class in scheme_classes.py

When we initialize a frame object (__init__(self, parent)), it creates two instance variables: parent and bindings. Parent lets us know from which frame the newly initialized frame is being made. The first frame is the global frame so its parent is None. This is taken care of by the function create_global_frame() in scheme.py so don’t worry about it.

bindings is a python dictionary that represents variables in scheme and their associated values.

Scheme

(define a 3)

To Python

self.bindings = {‘a’: 3}

When we initialize a frame object, Bindings is an empty dictionary. To populate it, we need to implement the method define(self, symbol, value). The argument symbol is simply the variable name and value is the value to which symbol is being bound.

Scheme

(define a 3)

symbol = ‘a’

To Python

define(‘a’, 3)

value = 3

To populate the dictionary, you could use the update({a: b}) method of python dictionaries.

Now we need to implement the method lookup(self, symbol) which searches the frame object in bindings to see if the variable (symbol) is in there. If it is, it will return the value that the variable is bound to. If it is not in there, then it does the same search process but in the parent frame. Once we are to the global frame, meaning env.parent = None, if the variable is not found, the interpreter raises an error.

Interpreter raises an error if variable is not found (scheme_classes.py)

You can get the value of a dictionary key using the built-in .get(key_name) method. You can use python’s in to see if a key is in a dictionary.

For more help

Problem 2: Procedures

This time we are going to be implementing a function in scheme_eval_apply.py called scheme_apply(). This function takes in a scheme list (args) and then applies the correct procedure (like addition or a lambda function) to args. The function returns a call to the correct procedure on args. Procedures are handled by the Procedure class in schemeclasses.py.

The Procedure class in scheme_classes.py

In Problem 2, we will be handling Built-in Procedures. Everytime a BuiltinProcedure is initialized, it creates three instance variables: name, py_func, and expect_env.

py_func is a function in python that will handle the operation/procedure needing to be done in Scheme

expect_env is a boolean (True or False) telling us if the built-in procedure needs the current environment information to run

In scheme_apply(), args is a scheme list, meaning it is represented by the Pair class which is basically just a linked list.

Scheme

(2 2)

In Python

args = Pair(2, Pair(2, nil))

The CS 111 site gives pretty much step-by-step instructions on implementing this function properly.

Hint: Scheme List to Python List

To convert the scheme list to a python list of arguments you could write a function that makes an empty list and then has a helper function inside recursively go through the linked-list (args) and append the first value to the python list. The needed values in Pair are accessed with .first and the rest of the list is gotten with .rest.

Hint: Try Except Syntax

For more help

Problem 3: scheme_eval()

In problem 3 we are going to evaluate the operator, then the operands (the arguments to the operator), and then apply the operator to all of the operands. This will be done in the function scheme_eval(expr). expr is a scheme expression represented by a Pair object.

From Scheme

(+ 2 2)

The operator is (+) addition

To Python

expr = Pair(‘+’, Pair(2, Pair(2, nil)))

The operands are 2 and 2

The scheme_eval() function takes in expr. Your job is to get the operator in expr and recursively evaluate it using scheme_eval(). Then recursively evaluate all of the operands (the rest of expr after the operator) using scheme_eval(). Scheme_eval() is pre-programmed to be able to handle the operators and individual operands.

The evaluation of the operator, will be a procedure. The final step is to apply the procedure on the operands using scheme_apply() from the last problem and return the result of that.

Hint: Evaluating the Operands Using map()

The Pair class has a method called map(). map(func) takes a function in and makes a new scheme list by applying func to all of the elements.

map() method from Pair class in pair.py

The challenge is that map() only takes in one argument, but we want to evaluate all of the operands using scheme_eval(), which takes two arguments: expr and env. So we need to make an equivalent version of scheme_eval() that takes only 1 argument. Hint: Lambda

Syntax of using a class method

For more help

Problem 4: Define Special Form

In Problem 4, we will be tackling the do_define_form() function. This function takes two arguments: expr and env. expr is a scheme expression represented by Pair class objects.

Scheme

(define size 2)

To Python

expr = Pair(‘size’, Pair(2, nil))

The first part of expr, ‘size‘, is the variable name. Whatever else that comes after is the expression or value to which the variable name will be bound. If it is an operation being defined, then the second part of expr, will start with an operator (like +).

Scheme

(define x (+ 2 3))

To Python

expr = Pair(‘x’, Pair(Pair(‘+’, Pair(2, Pair(3, nil))), nil))

The variable pre-defined for us, signature = expressions.first, is just the name of the variable in scheme that we want to bind to a value. (In the above example, ‘x’) Your job is to write the code that takes the rest of the Scheme list (the Pair objects) and evaluates it to a value in Python. Then assign that value to signature in the current environment. Finally remember to return signature.

Hint: Environment Class Method define()

define() method from Class Frame in scheme_classes.py

We created the method for variable creation in problem 1

For more help

Problem 5: quote

In problem 5 we are going to handle the quote feature of scheme. If we call quote on an operand in scheme, then the operand will be returned, unevaluated.

From the CS 111 Website Problem 5 Description

All you need to do is just return the unevaluated operand. All it takes is a very short line of code. Personally, I spent about half an hour on this before I realized it, but I was also tired.

If expressions = Pair(3, nil)

Then return 3

For more help

</end>

Hopefully this was a sufficient help. Please submit any corrections or questions in the comments below. I will try my best to answer and update the article accordingly.

on to part 2

December 4, 2022