Problem Set 7: Hints

sources = ["first source", "second source"]

If you can read these words, you are doing it correctly.

Question 1

def intsto(n):
  # put something here 

Hint 2 (more detailed outline):

def intsto(n):
  if n == 0:
    # put something here 
  else:
    # put something else here 

Hint 3 (appending to a list):

    # you may use code like this in the recursive case: 
    res = # ... recursive call
    res.append(n) 
    # ...

Hint 4 (full answer):

def intsto(n):
  if n == 0:
    return []
  else:
    res = intsto(n-1)
    res.append(n)
    return res

Question 2

The basic form of your answer should be:

charmeFactorialDefinition = '(define factorial ... write stuff here ...)'

Hint 2 (if-then-else):

You can convert (if (predicate) A B) into (cond ((predicate) A) (#t B)).

Question 3

There are two big steps. First, you'll have to add a variable to the globalEnvironment. Second, you'll have to write a Python procedure, such as primitiveLessThanOrEqualTo, that actually implements the <= functionality.

Hint 2 (global environment):

Find the definition of initializeGlobalEnvironment and copy the line with primitiveLessThan, changing it to refer to the '<=' symbol and primitiveLessThanOrEqualTo procedure (which you'll be definining).

Hint 3 (primitive definition):

Find and copy the definition of primitiveLessThan, changing < to <= in both places.

Question 4

There are three big steps. First, you'll have to add three variables to the globalEnvironment ('cons', 'car' and 'cdr'). Second, you'll have to write three Python procedures: primitiveCons, primitiveCar, and primitiveCdr. Third, you'll have to define a Cons class. The first two parts are largely the same as in Question 3.

Hint 2 (Cons class fields):

To make instance variables (or "fields") in a Python class, just make up names. You might call the parts of your Cons cell _left and _right, for example. If you do so, you can assign to them with statements like self._left = initial_left_value and read from them with self._left.

Hint 3 (Cons class):

Consider making __init__(self,left,right), car(self) and cdr(self) methods for your Cons class. They should each be one or two lines long.

Hint 4 (__str__):

The __str__ method, to pretty-print a Cons cell, is the most complicated part of the class. You'll return to it in Question 6 when you add support for Lists. For now, consider this example (which contains one bug):

  return "(%s . %s)" % (str(self._right), str(self._left))

Question 5

As usual, you'll want to add two variables to the globalEnvironment: this time they are 'null' and 'null?'. You might associate the former with None and the latter with primitiveIsNull, a Python procedure you write. To check if X is None, use X == None in Python.

Question 6

You'll want to add one variables to the globalEnvironment: 'list' which references primitiveList, a function that you write. Your primitiveList function will be a recursive Python procedure. If there are no operands (i.e., if the length of operands is 0), it should return None. Otherwise, use your own Cons class: if you say return Cons(X,Y) it will have the same effect as calling the __init__ procedure of your Cons class with X,Y as the second and third arguments.

Hint 2 (detecting lists):

I recommend writing an isList recursive Python procedure that determines if a Cons cell is a list. Recall the definition: None (or null) is a List. A Cons cell is a list if its Cdr is a list. Everything else is not a list.

Hint 3 (__str__):

Now that you can detect a list (see Hint 2), consider code like this:

    def __str__(self):
        if isList(self):
            return "(%s)" % self.strAsList()
        return # ... as before

Hint 4 (strAsList):

If self._right is None, just return str(self._left). Otherwise return A + " " + B where A corresponds to _left and B corresponds to a recursive call.

Question 7

Since if is a special form, you do not put it in the globalEnvironment. Go back to Exam 1 Question 2 to review the difference between a speical form and a function.

Instead, you'll want to change meval. Try putting a check for isIf(expr): after the one for isConditional(expr):. Make an evalIf(expr,env) Python procedure.

Hint 2 (evalIf)

As a sanity check, you should check that the length of your expression is 4. Call meval on your first argument (expr[1]). If it's not False, evaluate the second argument. Otherwise, evaluate the third argument.

Question 7

The basic idea here is to change mapply so that the Procedure case checks to see if we have a stored result for those operands. If so, return the stored result. If not, use the existing code to evaluate the procedure as normal, but then just before you would return, store the result so that we can reuse it later.

Hint 2 (memoization):

Add a _memos field to the Procedure class. Set it to { } in __init__. Add methods like hasResult(self, operands), storeResult(self, operands, result) and getResult(self, operands).

Go look up the Python dictionary datatype to see how to add things to a dictionary, etc. Hint: .has_key, [ ]. I recommend using str(operands) as the key.

[an error occurred while processing this directive]