cs150: Problem Set 7: Charming Snakes and Mesmeizing Memoizers

nking. 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 Python

First, try running the Charme interpreter. We recommend using IDLE, the Python interpreter and development environment provided in the ITC lab machines. IDLE provides an editor for Python code and an interpreter somewhat similar in style to DrScheme. To run Python in the ITC labs:

From the Start menu, select "SEAS -> Python 2.4 -> IDLE (Python GUI)"
Be patient (it takes about 10 seconds to start up)
Inside the Python shell, select "File -> Open" and select the charme.py file.

To run the Python module, select "Run -> Run Module" (or F5) in the editor window. This will return the focus to the Python shell with your module loaded.

Try evaluating mistake some Python statements in the interpreter window.

Question 1: To become familiar with Python, define an intsto method that takes a positive integer as its input and produces a list of the integers from 1 up to the input value. For example, intsto(5) should evaluate to [1, 2, 3, 4, 5]. Just add your new method at the bottom of charme.py.

Spoiler: The hints for this problem will walk you through one definition, but try it yourself first.

Getting Started With Charme

In the charme.py window, select Run | Run Module (F5) to load the definitions into the interpreter. You can try some evaluations using the procedure evalToplevelExp directly:

>>> evalToplevelExp([['+', '1', '2']])

3

>>> evalToplevelExp([['+', '1', '2', ['*', '3', '4']]])

15

There are two weaknesses with this approach. First, it does not make the global environment explicit. Second, and perhaps more importantly, it's obnoxiously difficult to use that [['+', '1', ... notation to enter Charme programs.

We'll deal with the parsing issue first. 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']]]]

You can pass the result of parse to evalToplevelExp if you like:

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

15

Under the hood, evalToplevelExp calls meval(exp,env) to evaluate the expression exp in the environment env. A special environment globalEnvironment exists. You'll learn more about environment manipulation as you complete this problem set.

Let's highlight the distinction between a Charme program and a Python program once again. From the perspective of our shiny new interpreter, a Charme program is really just a string that we parse and evaluate. Let's make a string called charmeAddTwoDefinition that is the source code for a Charme program that adds two to its argument:

>>> charmeAddTwoDefinition = "(define addTwo (lambda (x) (+ x 2)))"

>>> evalToplevelExp(parse(charmeAddTwoDefinition))

>>> evalToplevelExp(parse("(addTwo 5)"))

7

Question 2: Define a factorial procedure in Charme. Express your procedure as string in Python called charmeFactorialDefinition. When evaluated, it should define a Charme procedure called factorial. Your string should look like charmeAddTwoDefinition in line one of the example above. Note that Charme does not provide the if expression, so the standard Scheme definition will not work. When you've done it correctly, you should see output like this:

>>> evalToplevelExp(parse(charmeFactorialDefinition))

>>> evalToplevelExp(parse("(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. However, it is not enough to express every computation in a convenient way.

Question 3: Extend the Charme interpreter by adding a primitive procedure <= to the global environment. You will need to define a procedure that implements the primitive, and modify initializeGlobalEnvironment to install your primitive.

>>> evalToplevelExp(parse("(<= 5 3)"));

False

>>> evalToplevelExp(parse("(<= 3 7)"));

True

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.

Question 4: Extend the Charme interpreter by adding primitive procedures cons, car and cdr that behave similarly to the primitive Scheme procedures.

You should start by defining a class that represents a cons cell. For example, you might define a Cons class that has a constructor (__init__) that takes two inputs (the first and second parts of the pair), and provides methods for getFirst and getSecond that retrieve the respective parts of the pair.

You must also define a __str__(self): method for your class so that evalLoop and evalToplevelExp will print out Cons sells similarly to how they are displayed in Scheme.

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

Or the equivalent ones with evalToplevelExp:

>> evalToplevelExp(parse("(cons 1 2)"))

(1 . 2)

...

Question 5: Extend the Charme interpreter by defining the null and null? primitives. (Note that 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.

Question 6: 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.

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

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

Charme> (car a)

1

Charme> (null? a)

False

Charme> (cdr (cdr a))

(3 4)

Charme> (null? (list ))

True

Special Forms

Question 7: Extend the Charme interpreter to support the if expression special form, with the same meaning as the Scheme if expression.

After adding if to your Charme interpreter, you should get the following interactions (note: we recommend testing it with simpler tests before trying this):

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

Charme> (fibo 5)

5

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.

Question 8: Modify the Charme interpreter to support memoizing for all procedure applications.

Hint: the Python dictionary datatype will be very useful for this. See page 12-10 of Chapter 12 of the Course Book.

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!

Question 9: Define variables pleased and displeased that are strings completing these sentences:

pleased = """I am pleased that ..."""
displeased = """I am displeased that ..."""

As usual, we welcome your comments on any subject, but we particularly covet concrete suggestions for course improvement. You will receive full credit if each string exceeds twenty characters.

Automatic Adjudication: Submit a single Scheme Definition file that addresses all of the Questions until you are satisfied with your test results. Your scheme file should be a modification of the ps6.scm file. Each partner must submit the file separately.

Warning: Just running your Python code should not produce any output. If you are getting all of the questions wrong and if you have any calls to print or evalToplevelExp at the top level of your Python code, remove them so that the automatic adjudication service is not confused.

Extra Credit: Computer Fugues: Becoming A Java Junkie

Many of you may be interested in continuing on to CS 205, Engineering Software, especially if you are pursuing a Major or Minor in Computer Science.

The first assignment in CS 205 typically asks students to pick up a new language, Java, relatively rapidly, and to use that knowledge to modify a large existing program. This extra credit assignment is a copy of the first assignment from CS 205 — if you can complete it here, you have every reason to believe that you will have no trouble in CS 205 proper.

If you are considering taking CS 205, I highly recommend that you complete this extra credit assignment. It is due Monday, April 27 (yes, that far out), so you have plenty of time.

The assignment is to complete the Question 1 and Question 2 from the problem set below (taken verbatim from CS 205):

Completing the Questions will require you to download the source to jfugue and xom. I have provided local copies above. In addition, you get a chance to use Eclipse, a popular integrated development environment (somewhat like IDLE or DrScheme).

I recommend that you get started by reading the Schemer's Guide to Java for this class. You might follow that up by Googling for Java Tutorials, and then browse the jfugue book (link found inside handout). The course staff will be happy to answer questions about the Java programming language (in person, via email, or in office hours).

Successfully completing this extra credit assignment is worth 10% boost to your PS7 coding grade and a 10% boost to your PS8 grade.

Extra Credit Manual Adjudication: To submit the extra credit, you should email the answers (as required in the handout above) to cs150-staff@cs.virginia.edu with subject "Java Extra Credit". You must do so by Midnight, Monday, April 27th.

[an error occurred while processing this directive] cs150: Problem Set 7: Charming Snakes and Mesmeizing Memoizers

cs150 Spring 2009

classes book syllabus ps exams guides forum

cs150: Computer Science
from Ada and Euclid to Quantum Computing and the World Wide Web

Instructor
Westley Weimer

Teaching Assistants
Zak Fry
Paul DiOrio
Rachel Lathbury

Email Address
cs150-staff@cs.virginia.edu

Class Meetings
Mondays and Wednesdays, 3:30-4:45pm in MEC 341

Structured Lab Hours
Wednesdays, 7:00-8:00pm and 8:00-9:00pm in OLS 001

Staffed Lab Hours
(Small Hall Lab)
Monday 5:00-6:00 (Zak)
Tuesday 3:15-4:15 (Rachel)
Thursday 5:00-6:00 (Paul)
Sunday 3:00-4:00 (on request)

Office & Lab Hours
(Small Hall Lab)
Monday 2:00-3:00 (Rachel)
Tuesday 11:00-12:00 (Wes in Olsson 219)
Tuesday 3:00-4:00 (Zak)
Wednesday 1:00-2:00 (Paul)