[an error occurred while processing this directive]

Problem Set 7: Hints

[an error occurred while processing this directive]

Question 1

Hint 1 (getting started): 

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

Hint 1 (general hints, getting started):

The basic form of your answer should be: 

charmeFactorialDefinition = '(define factorial ... write stuff here ...)'
You will definitely want to use lambda (because factorial is a function). Since factorial is recursive, it has a base case and an inductive step. You'll need to be check the input to distinguish between those two cases. Unfortunately, Charme does not have an if expression, so you'll need to improvise. Consider using cond.







Hint 2 (if-then-else):

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







Question 3

Hint 1 (general hints, getting started):

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

Hint 1 (general hints, getting started):

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

Hint 1:

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

Hint 1 (general hints, getting started, primitiveList):

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
You just have to write the recursive strAsList method to the Cons class.







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

Hint 1 (general hints, getting started):

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

Hint 1 (general hints, getting started):

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]