cs1120 Problem Set 7:
Charming Snakes with Mesmerizing Memoizers

Collaboration Policy - Read Carefully

For this assignment, you make work either alone or with a partner of your choice.

Remember to follow the pledge you read and signed at the beginning of the semester. For this assignment, you may consult any outside resources, including books, papers, web sites and people, you wish except for materials from previous cs1120, cs150, and cs200 courses. You may consult an outside person (e.g., another friend who is a CS major but is not in this class) who is not a member of the course staff, but that person cannot type anything in for you and all work must remain your own. That is, you can ask general questions such as "can you explain recursion to me?" or "how do lists work in Scheme?", but outside sources should never give you specific answers to problem set questions. If you use resources other than the class materials, lectures and course staff, explain what you used in your turn-in.

You are strongly encouraged to take advantage of the scheduled help hours and office hours for this course.

Purpose

• Understand how language interpreters work
• Understand the meta-circular evaluator
• Ruminate on the nature of univeral programming languages
• Learn how changing the evaluation rules changes programming

Background

Languages are powerful tools for thinking. One way to solve problems is to think of a language in which a solution to the problem can be easily expressed, and then to implement that language. This is the "great Hop forward" that Grace Hopper made in the 1950s: we can produce programs that implement languages. The input to the program is an expression specification in some language. If the program is an interpreter, the result is the value of that expression.

In this problem set, we provide a working interpreter for the Charme language, which is approximately a subset of Scheme. The interpreter implements the Scheme evaluation rules with state. Your assignment involves understanding the interpreter and making some additions and changes to it. If you are successful, you will produce an interpreter for the language Mesmerize in which the original Fibonacci procedure can be applied to 60 to produce the correct result in a reasonable amount of time.

Getting Started With Charme

In the charme.py window, select Run | Run Module (F5) to load the definitions into the interpreter. This file contains all the code from Chapter 11 of the course book.

It defines a procedure meval that takes two inputs: a list that represents a Charme expression and an environment. It outputs the value of the input expression. The initializeGlobalEnvironment() procedure initializes the global environment in the global variable globalEnvironment. We can use the as the second input to meval. You can try some evaluations using meval directly:

>>> initializeGlobalEnvironment()

>> meval('23', globalEnvironment)

23

>>> meval(['+', '1', '2'], globalEnvironment)

3

This is a bit awkward since the first input is not in the standard Charme notation, but the parsed structure.

The parse procedure takes a string representing one or more Charme expressions and produces as output a list containing each input expression as a structured list. For example:

>>> parse("23")

['23']

>>> parse("(+ 1 2 (* 3 4))")

[['+', '1', '2', ['*', '3', '4']]]

>>> parse("(define square (lambda (x) (* x x)))")

[['define', 'square', ['lambda', ['x'], ['*', 'x', 'x']]]]

Since parse takes one or more expressions and produces a list of expressions as its output, we cannot pass the result from parse direction to meval. If we just parse one expression, we just want to pass the first element of the parse output to meval:

>>> meval(parse("(+ 1 2 (* 3 4))")[0], globalEnvironment)

15

It is a bit awkward to remember the [0] and to pass in the globalEnvironment, so we have defined a procedure evalInGlobal(expr) that takes a string representing one Charme expression and evaluates it in the globalEnvironment:

def evalInGlobal(expr):
    return meval(parse(expr)[0], globalEnvironment)

For example:

>>> initializeGlobalEnvironment()

>>> evalInGlobal("(define square (lambda (x) (* x x)))")

>>> evalInGlobal("(square 4)")

16

>>> evalInGlobal("square")

<__main__.Procedure instance at 0x03C0BE18>

We have also provided the evalLoop() procedure that provides an interactions buffer for Charme.

From the perspective of our shiny new interpreter, a Charme program is really just a string that we parse and evaluate.

Adding Primitives

The set of primitives provided by our Charme interpreter is sufficient, in that it is enough to express every computation. However, it is not enough to express every computation in a convenient way. Our Charme interpreter does not provide any primitives for lists. As we saw in Chapter 5, it is possible to define cons, car and cdr using only the language already defined by Charme. However, it would be more convenient if some primitives for manipulating cons cells and lists are provided.

You should get the following interactions in the evalLoop():

Charme> (cons 1 2)

(1 . 2)

Charme> (car (cons 1 2))

1

Charme> (cdr (cons 1 2))

2

Charme> quit

Or the equivalent ones with evalInGlobal:

>> evalInGlobal("(cons 1 2)")

(1 . 2)

After finishing these questions, you should get the following interactions in the evalLoop():

Charme> (define a (list 1 2 3 4))

Charme> (car a)

1

Charme> (null? a)

False

Charme> (cdr (cdr a))

(3 4)

Note that this is the way Scheme prints out lists, and you are encouraged to make your Charme interpreter also print out lists this way. It is acceptable, though, to print out lists in a more straightforward way, so they would be displayed as normal cons pairs. Then, this would look like, (3 . (4 . None)), instead.

Charme> (null? (list ))

True

Special Forms

The provided Charme interpreter does not include the cond special form. Before attempting to answer the next question, we recommend carefully understanding the evaluation rule for the conditional expression (as described in Section 10.1.2 of the course book). After adding cond to your Charme interpreter, you should get the following interactions using evalLoop():

Charme> (cond)

None

Charme> (cond ((> 1 2) 2))

None

Charme> (cond ((> 1 2) 2) ((> 3 2) 3))

3

Charme> (define fibo (lambda (n) (cond ((= n 1) 1) ((= n 2) 1) (true (+ (fibo (- n 1)) (fibo (- n 2)))))))

None

Charme> (fibo 10)

55

Memoizing

Memoizing is a technique for improving efficiency by storing and reusing the results of previous procedure applications. If a procedure has no side effects and uses no global variables, everytime it is evaluated on the same operands it produces the same result.

To implement memoizing, we need to save the results of all procedure applications in a table. When a procedure application is evaluated, first, we lookup the application in the table to see if it has already been computed. If there is a known value, that is the result of the evaluation and no further computation need be done. If there is not, then the procedure application is evaluated, the result is stored in the table, and the result is returned as the value.

Once you have modified the interpreter, you should be able to evaluate (fibo 60) without changing the definition of fibo above. By changing the meaning of the application evaluation rule, a procedure that previously had running time exponential in the value of the input, now has running time that is linear in the value of the input!