Problem Set 7 - Comments

1. Define a factorial procedure in Charme. (Note that Charme does not provide the if expression, so the standard Scheme definition will not work.)

(define factorial 
   (lambda (x) 
      (cond ((= x 0) 1) 
            (#t (* x (factorial (- x 1)))))))

2. 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.

Answer: To add the <= procedure we define primitiveLessThanEqual using the Python <= operator:

def primitiveLessThanOrEqualTo (operands):
    checkOperands (operands, 2, "<=")
    return operands[0] <= operands[1]

Then, we add it to the global environment:

def initializeGlobalEnvironment():
    global globalEnvironment
    globalEnvironment = Environment(None)
    globalEnvironment.addVariable('#t', True)
    globalEnvironment.addVariable('#f', False)
    globalEnvironment.addVariable('+', primitivePlus)
    globalEnvironment.addVariable('-', primitiveMinus)
    globalEnvironment.addVariable('*', primitiveTimes)
    globalEnvironment.addVariable('=', primitiveEquals)
    globalEnvironment.addVariable('zero?', primitiveZero)
    globalEnvironment.addVariable('>', primitiveGreater)
    globalEnvironment.addVariable('<', primitiveLessThan)
    globalEnvironment.addVariable('<=', primitiveLessThanOrEqualTo)

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

Answer: There are several reasonable ways to do this. We define a new class, Cons that represents a cons cell.

class Cons:
    def __init__(self, left, right):
        self._left = left
        self._right = right
    def __str__(self):
        return "(%s . %s)" % (str(self._left), str(self._right))
    def car(self):
        return self._left
    def cdr(self):
        return self._right

Then, we define the primitive procedures:

def primitiveCons (operands):
    checkOperands (operands, 2, "cons")
    res = Cons(operands[0], operands[1])
    return res

def primitiveCar(operands):
    checkOperands(operands, 1, "car")
    return operands[0].car();

def primitiveCdr(operands):
    checkOperands(operands, 1, "cdr")
    return operands[0].cdr();

We add these to the global environment, but adding these three lines to initializeGlobalEnvironment:

    globalEnvironment.addVariable('cons', primitiveCons)
    globalEnvironment.addVariable('car', primitiveCar)
    globalEnvironment.addVariable('cdr', primitiveCdr)

Since we used the special name __str__ for our procedure that produces a string representation of a cons, the cons pairs will display correctly in the evalLoop with,

if res != None:
    print str(res)

(note that the Procedure method toString should have also been named __str__ to make this work for procedures also).

4. 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?.)

Answer: We can use anything we want to represent null, as long as we define null? correspondingly. The most obvious thing to use is the Python value None:

def primitiveIsNull (operands):
    checkOperands(operands, 1, "null?")
    return operands[0] == None

(note that we cannot use ? in identifier names in Python, so need to use a different name).

To define null (which is not a procedure), we just add it to the global environment by adding these statements to initializeGlobalEnvironment:

    globalEnvironment.addVariable('null', None) 
    globalEnvironment.addVariable('null?', primitiveIsNull)

5. Extend the Charme interpreter by defining the list primitive prodcedure. 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.

Answer: To add the list primitive, we define primitiveList as:

def primitiveList (operands):
    if (len(operands) == 0):
        return None
    else:
        return Cons(operands[0], primitiveList(operands[1:]))

and add it to the global environment:

    globalEnvironment.addVariable('list', primitiveList)

With this definition, lists will just print out as nested cons pairs:

Charme> (list 1 2 3 4)
(1 . (2 . (3 . (4 . None))))

Then, we modify the Cons __str__ method (using the ned strAsList helper method:

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

7. Modify the Charme interpreter to support memoizing for all procedure applications. (Hint: the Python dictionary datatype will be very useful for this.)

Answer: We have to figure out where to store the memoized results and how to maintain them. Many answers attempted to store the results globally, with a global dictionary of <procedure(operands), value> pairs. This sort of works, except is assumes the same name always refers to the same procedure. This is not the case with the environment model of evaluation. We would need a dictionary associated with each environment instead of a global dictionary. An easier approach is to associate the dictionary with the procedure. This is better because it is simpler, but it also means we can memoize results for procedures that do not have names. The memoized results table is associated with the procedure itself (which was produces by a lambda expression). (The one drawback of this approach is it means we are not memoizing the results of primitive procedures. Since the provided primitives are all fast procedures, however, this is not a serious drawback.)

The modified Procedure class adds the _memos instance variable, initializes it to the empty dictionary, and defines the procedure hasResult, storResult, and getResult:

We modify mapply to check if an application has a stored result. If it has a stored result, we use that as the result. Otherwise, we compute the result as before, and store it in the memoized results table.

Here is a link to the final interpreter with all of our changes: memocharme.zip.