Project 6: Charming Snakes with Mesmerizing Memoizers

Deliverables: For this assignment, there is no paper turn-in required for this problem set. All of your answers should be clearly marked in the charme.py file you modify and submit electronically by email to evans@virginia.edu. To be eligible for the first Red Belt test opportunity, you should complete Project 6 by Friday, 22 April.

Purpose

Understand how language interpreters work
Gain experience with a programming language quite different from Python.
Understand the meta-circular evaluator
Ruminate on the nature of universal programming languages
Learn how changing the evaluation rules changes programming and running time

Collaboration Policy

For this assignment, you may work alone or work with a partner.

If you work with a partner, you and your partner should submit a single assignment with both of your names and UVA ids on it. You and your partner should work on all the problems together, and both of you must completely understand everything you turn in. You should also take turns driving (typing) when you are at the computer.

Regardless of whether you work alone or with a partner, you may discuss the assignment with anyone you want and get help from others, so long as it is help in the spirit of learning how to do things yourself not getting answers you don't understand. You should understand everything you turn in for the assignment well enough to be able to produce it completely on your own.

Remember to follow the course 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 courses or direct solutions to the given problems. You may consult anyone you want, but that person cannot type anything in for you and all work must remain your own and 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, you should document this in your turn-in.

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

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. Scheme is a simple programming language (which you've encountered some in the coursebook) that is designed to support a functional style of programming where programs are built by composing functions.

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 that includes two recursive calls will have running time that is approximately linear in the value of its input (compared to the exponential time it would have with a normal Scheme interpreter), and the simple edit distance procedure from Project 2 runs fast enough for reasonably large inputs (analyzing its actual running time is left as a bonus problem).

Preparation

Read Chapter 11: Interpreters of the course book. The starting code for this project is explained in Chapter 11.

Project 6 Repository

Set up your project6 repository in the same way as you did for previous projects.

Fork Project 6. Visit https://bitbucket.org/cs1120/project6/fork. Make sure to check the "This is a private repository" box to make your forked repository private (only visible to yourself and people you authorize to access it). If you are working with a partner, just one of you should fork the repository. Then, add the other partner's bitbucket id to have access to it.
Clone to your machine. To have a working copy of the repository on your machine, clone the forked repository in SourceTree by selecting File | New/Clone and enter the URL of the cloned repository. You can copy this from the project page you see in bitbucket.org afer forking the provided Project 5 repository. It should be a URL like https://<your bitbucket id>@bitbucket.org/<your bitbucket id>/project6.git. If you are working with a partner, both partners should clone the forked repository, so you each have a local copy of it. (For this project, you should work together when you work on the code. In general, though, using git allows many people to work on the same code and share their changes, and handle conflicts when two people edit the same file.)

The project6 repository contains just one file: charme.py.

For the questions in this assignment, you will modify charme.py which you will submit electronically when you are finished. Please mark clearly (using comments) the changes you have made for Problems 3 - 8.

Getting Started With Charme

Open charme.py and 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, with some modifications to make it work in Python 3 (the code provided in the book is for Python 2).

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 is the data structure that results from parsing "(+ 1 2)".

The parse function takes a string representing one or more Charme expressions and returns 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 directly 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 function evalInGlobal(_expr_) that takes a string representing a single 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>

(Of course, the actual address in memory where your procedure is stored will vary).

We have also provided the evalLoop() function that provides an interactions buffer for Charme, similar to the Python shell.

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

Problem 1. Define a factorial procedure in Charme. Express your procedure as string in Python by defining a variable called charme_factorial. When you evaluate evalInGlobal(charme_factorial), it should define a Charme procedure called factorial.

When you've complete Problem 1 correctly, you should see output like this:

>>> initializeGlobalEnvironment()
>>> evalInGlobal(charme_factorial)
>>> evalInGlobal("(factorial 5)")
120

Adding Primitives

The set of primitives provided by our Charme interpreter is sufficient, in that it is enough to express every computation. (One way to prove this would be to implement a Turing Machine simulator in Charme.) However, it is not enough to express every computation in a convenient way.

Problem 2. Extend the Charme interpreter by adding a primitive procedure <= (less than or equal to) to the global environment. You will need to define a procedure that implements the primitive, and modify initializeGlobalEnvironment to install your primitive.

It should behave like this:

>>> initializeGlobalEnvironment()
>>> evalInGlobal("(<= 5 3)") 
False 
>>> evalInGlobal("(<= 3 7)") 
True

Our Charme interpreter does not provide any primitives for lists. As we saw in Class 11, it is possible to define everything you need to make pairs and then lists just using procedures that are already provided by Charme.

However, it would be more convenient if some primitives for manipulating pairs are provided.

Problem 3. Extend the Charme interpreter by adding primitive functions cons (this is the Scheme name for make_pair), car (the Scheme name for pair_first) and cdr (the Scheme name for pair_last) that behave similarly to the primitive Scheme procedures. (Read on for some hints.)

You should start by defining a class that represents a cons cell (a pair). For example, you might define a Pair class that has an __init__ method that takes two inputs (the first and second parts of the pair), and provides methods for get_first and get_last that retrieve the respective parts of the Pair object.

You must also define a __str__(self) method for your class so that evalLoop and evalToplevelExp will print out your Pair objects in a readable way.

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

Problem 4. Extend the Charme interpreter by defining the null and null? primitives. (Note that unlike in Charme, names in Python cannot include question marks, so you will have to use a different name for the Python procedure you use to implement null?.) (Hint: You could use Python's None value to represent null.)

Problem 5. Extend the Charme interpreter by defining the list primitive procedure. Like the Scheme list primitive procedure, it should take any number of operands and produce as output a list containing each operand as an element in order.

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> (null? (list ))
True
Charme> (cdr (cdr a))
(3 4)

Note that the last output is the way Scheme prints 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.

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 coursebook).

Problem 6. Extend the Charme interpreter to support the cond special form, with the same meaning as the Scheme cond expression. (Your Charme cond expression does not need to support the special else syntax supported by Scheme.)

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. You should remember memoizing from Project 2.

To implement memoizing, we need to save the results of all function applications in a table. When a function 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 function application is evaluated, the result is stored in the table, and the result is returned as the value.

Problem 7. Modify the Charme interpreter to support memoizing for all function applications. (Hint: Python dictionaries will be very useful for this!)

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!

Problem 8. (Bonus) [This question is a "bonus question". It is not necessary to answer this to pass Project 6, but an exemplary answer to this question, along with completion of Problems 1-8 from Project 5, will be justification for automatic promotion to Red Belt.]

a. Define a Charme procedure that implements the edit distance function from Project 2.

b. Analyze the running time of your procedure, using the memoized Charme interpreter.

c. Analyze the running time of your procedure, using the standard Charme interpreter (without memoization)

Deliverables

Reminder: For this assignment, there is no paper turn-in required for this problem set. All of your answers should be clearly marked in the charme.py file you modify and submit electronically by email to evans@virginia.edu. To be eligible for the first Red Belt test opportunity, you should complete Project 6 by Friday, 22 April.