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 email@example.com.
To be eligible for the first Red Belt test opportunity, you should complete Project 6 by Friday, 22 April.
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
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.
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).
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/Cloneand 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:
Getting Started With Charme
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.
initializeGlobalEnvironment() procedure initializes the global
environment in the global variable
globalEnvironment. We can use the
as the second input to
You can try some evaluations using
>>> 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)".
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']]]]
parse takes one or more expressions and produces a list of
expressions as its output, we cannot pass the result from
meval. If we just parse one expression, we just want to
pass the first element of the
parse output to
>>> meval(parse("(+ 1 2 (* 3 4))"), globalEnvironment) 15
It is a bit awkward to remember the
 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
def evalInGlobal(expr): return meval(parse(expr), globalEnvironment)
>>> 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.
charme_factorial. When you evaluate
evalInGlobal(charme_factorial), it should define a Charme procedure called
When you've complete Problem 1 correctly, you should see output like this:
>>> initializeGlobalEnvironment() >>> evalInGlobal(charme_factorial) >>> evalInGlobal("(factorial 5)") 120
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.
<=(less than or equal to) to the global environment. You will need to define a procedure that implements the primitive, and modify
initializeGlobalEnvironmentto 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.
cons(this is the Scheme name for
car(the Scheme name for
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
retrieve the respective parts of the
You must also define a
__str__(self) method for your class so that
evalToplevelExp will print out your Pair objects in a readable way.
You should get the following interactions in the
Charme> (cons 1 2) (1 . 2) Charme> (car (cons 1 2)) 1 Charme> (cdr (cons 1 2)) 2 Charme> quit
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
Nonevalue to represent
listprimitive procedure. Like the Scheme
listprimitive 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
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)
(3 . (4 . None)), instead.
The provided Charme interpreter does not include the
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).
condspecial form, with the same meaning as the Scheme cond expression. (Your Charme cond expression does not need to support the special
elsesyntax supported by Scheme.)
cond to your Charme interpreter, you should get the
following interactions using
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 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.
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!
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)
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
firstname.lastname@example.org. To be eligible for the first Red Belt test
opportunity, you should complete Project 6 by Friday, 22 April.