Assignment 2: Functional Programming in Python
CSE 341: Programming Languages
The University of Washington, Seattle, Winter 2012
Reading: The reading for this assignment is Chapters 5-11, except 10. in Python as a Second Language.
Purposes: The purposes of this assignment are to deepen your experience with Python and to advance your understanding and fluency in functional programming.
Due: Saturday, January 21 (changed from Friday, January 20 on account of the weather), at 5:00 PM via Catalyst CollectIt.
Teamwork Allowed.
This is a partnership assignment, you are encouraged to work in pairs. You may choose to divide up the problems and share their solutions within your team, or you may choose to work together on each problem. Alternatively, you can combine dividing up and working together. Each team should turn in only one set of files. The turn-in must be performed by the "representative partner". The representative partner is the one whose last name comes first in the alphabet. The non-representative partner should simply turn in a text file that says, for example, "See my partner's submissions, under Smith, John." Partnerships are not required, but there will be no grading advantage to working alone and turning in solutions all by oneself.
What to Turn In: You should turn in the following files: (if you opt to do Problem 7)
Each file should begin with a multiline string that serves as a comment and that gives the name of the file, a program name (that is more descriptive and English-like than the filename), the author (your) name(s), followed by a brief description (2-5 lines) of what the program does.

The file readme.txt should contain the answer to the following questions. How did your team divide up the work? What did each partner contribute to the solutions? (150-word limit).
Each Python file that you turn in for this assignment should contain function definitions and possibly variable assignments, but should not contain any calls to the print function except in Problems 5d and 5g, except in case of program exceptions and invalid input to your functions. Thus, when your program is imported as a module, it should not cause anything to be printed. This will facilitate grading of your work by allowing grading scripts to control the execution of your functions.

You are encouraged to include testing functions that show the correctness of of your solutions. These functions should be named testP1(), testP2(), ..., testP7(), with each one performing a test for the corresponding problem solution. These functions are optional for Problems 1, 2, 4, and 5, but required in Problems 3 and 6 and required in Problem 7 if you opt to do Problem 7. Generally, the graders might or might not choose to use these testing functions, but they will probably help you develop your solutions in any case. If you include them, they should typically show sample input and output for some straightforward cases of calling each of your assigned functions. Calls to print in these functions is fine. For example, your testP4() should first announce that it is calling makeArithGenerator with, say, k=5, and then it should announce that it is making 3 calls to the function that was returned and print the returned values; next it should do something similar for makeGeomGenerator, etc., so that each required function is demonstrated in a way that shows that your solutions are good. Your code should not automatically call any of these testing functions when the program is imported as a module.

Write a program that contains your function definitions for Problems 1, 2, 3, and 4.

  1. A Function with a Loop:
    (10 points) Define a function tribonacci(n) that will compute the nth tribonacci number, t(n), where t(n) is defined by the recurrence:
    t(n) =
      1 if n = 0
      1 if n = 1
      1 if n = 2
      t(n-3) + t(n-2) + t(n-1) if n > 2
    Even though we typically express this definition in a recurrence (recursive equation), you should implement your function using a loop rather than recursion, in order to take advantage of "dynamic programming" (taking advantage of previously computed results to avoid an exponential growth in computing time and space). Here are the first 10 tribonacci numbers:
    [1, 1, 1, 3, 5, 9, 17, 31, 57, 105]

  2. Another Function Maker:
    (5 points) Define a function called makeParabolaEvaluator(a, b, c) that takes the three parameters of a quadratic function:
    y = a * x**2 + b * x + c
    and returns a function (let's assume it's f) That function f will accept one argument (for x) and will return the corresponding value of y.

  4. Making New Functions From Old:
    (20 points) Define a function makeSplicedFunction(functions, splicePoints) that turns a list of n functions and a list of n-1 floats into one new function that evaluates its argument x by comparing it with the floats (in left-to-right order) until it finds the last one it is greater than (or equal to). Say this is splicePoints[i]. It then applies functions[i+1] to x. If it is less than all the floats, functions[0] is applied.

    Next use a list comprehension and makeParabolaEvaluator to construct a list of 8 functions involving values of a, b, and c that are zero or one, in all combinations. The first function should evaluate y = 0 * x**2 + 0 * x + 0; the second should evaluate y = 0 * x**2 + 0 * x + 1; etc.

    Use these splicing points: SP = [4, 8, 12, 16, 20, 24, 28]
    Create a spliced function using the eight functions above and these seven splicing points. This function is a piecewise quadratic function. Then map the function onto range(0,32). You should get the following list:

    [0, 0, 0, 0, 1, 1, 1, 1,
     8, 9, 10, 11, 13, 14, 15, 16, 
     256, 289, 324, 361, 401, 442, 485, 530,
     600, 650, 702, 756, 813, 871, 931, 993]
    Encapsulate a presentation of this example in a test function, testP3().
  5. Working with Closures:
    (10 points) Here's a functional closure that can be used as a sequence generator for the natural number sequence.
    def makeCounter():
      n = [0]
      def count():
        n[0] += 1; return n[0]
      return count
    JohnScores = makeCounter()
    MaryScores = makeCounter()
    a. Using this function as a starting point, create a function makeArithGenerator(k) which returns closures that, instead of counting by 1, count by k. Here's an example of how it could be used:
    countBy7 = makeArithGenerator(7)

    b. Using this function as a starting point, create a function makeGeomGenerator(k) which returns closures that, instead of changing by a fixed increment, change by the factor k. Here's an example of how it could be used:
    scaleBy13 = makeGeomGenerator(13)

    c. Modify your function for part a, creating makeArithGeneratorV2(k, start=0) so that counting sequences can start at any value. (Note that the default start value will yield sequences a little different from those generated by makeArithGenerator in problem 4a.)
    nextOdd = makeArithGeneratorV2(2, 1)

    d. now modify your function for part b, creating makeGeomGeneratorV2(k, start=1) so that geometric sequences can start at any value.

  7. Sequence Analysis and Prediction:
    (30 points) a. Next, create a function tryArithSeq(list) that will determine whether list represents the beginning of an arithmetic sequence. If so, it will return a function of n that computes the nth term of the sequence. If not, it will return None.
    b. Now create a function tryGeomSeq(list) that will determine whether list represents the beginning of a geometic sequence. If so, it will return a function of n that computes the nth term of the sequence. If not, it will return None.
    c. Next create a function tryArithAndGeom(list) that will call tryArithSeq. If that succeeds, it will return the function. If that returns None, it will call tryGeomSeq and return its result.
    d. Create a read-eval-print loop that queries the user for a sequence of numbers and passes the sequence to tryArithAndGeom, and then uses the returned function to print out the next number in the sequence. The loop ends when the user types in 'bye'.
    e. Create a function makeInterleavedGenerator(f1, f2) where f1 and f2 are closures that generate their own sequences. The result of calling the new function should be a new closure that, each time it is called, calls one or the other of f1 and f2, alternating between them. For example, if f1 generates 0, -1, -2, -3, ... and f2 generates 2, 4, 8, 16, ... then the resulting new closure would generate 0, 2, -1, 4, -2, 8, -3, 16, ...
    f. Create a function analyzeAnySequence(list). This function should return the simplest function that generates the sequence whose prefix matches that in list. First it should try for an arithmetic sequence. Second it should try for a geometric sequence. Third, it should try for an interleaved sequence by splitting up list into two subsequences (the even-position terms in one and the odd-position terms in the other), and then it should (a) recursively call itself on each sublist to get a pair of functions that compute the nth elements of their respective sequences, and (b) create a new function that combines the two so that it can compute any element of the interleaved sequence.
    g. Modify your read-eval-print loop to use analyzeAnySequence.

  9. Sentence Generation:
    (25 points) Write a program that imports the CFG module (the starter code). In this program, define a subclass of Grammar called GrammarWithFunctions. Write a new method for this class that will produce functions Fp, one for each production rule p, that works as follows.
    Fp takes as its argument a sentential form Q. Assume that the production p is of the form A → x0 x1 ... xn-1. Fp scans Q looking for the first occurrence of A. If there is no occurrence of A, then Fp returns None. Otherwise, it computes a new sentential form Q' by replacing the first occurrence of A in Q by x0 x1 ... xn-1.

    Set up a dictionary whose keys are productions and whose values are the functions Fp.

    A leftmost derivation of a sentence using a context-free grammar is a derivation of a terminal string from the start symbol in which each application of a production involves replacing the leftmost nonterminal symbol in the current sentential form.

    Now write a sentence generator that generates a random leftmost derivation. Whenever it has a choice as to what production to apply, it should call the choice method of the random module to make the decision. Your sentence generator should be set up to handle calls of the form g.randomSentence(seed=0). If you define the method to have a default value of seed=-1, and that means "do not reset the random number generator", then you will be able to get new sentences each time the method is called. Otherwise, the random number generator should be initialized with the seed equal to the passed-in value. The random sentence should be returned as a string. You should also include a cutoff value so that attempts at infinite expansions due to left-recursive productions get cut off. The default cutoff should be 50, but it should be possible to override the default with a call such as this: g.randomSentence(cutoff=200).

    Here is some sample code that shows how to import the Random class of the random module, create an instance of it, seed it, and than invoke its choice method.

    >>> from random import Random
    >>> r = Random()
    >>> r.seed(0)
    >>> r.choice(range(10))
    Implement a test function testP6() that does the following. It should read in the given "Englishish.txt" grammar. A method in the starter code reads in the grammar. The sample grammar (the program's default) is available here.

    Then it should generate 10 random sentences and print them.

  10. Function Hierarchies
    (Optional, for 5 points of credit). Define a function makeFibonnaciPolynomialEvaluator(n) that will return a function that computes the Fn(x), where we define Fn(x) as follows:
    F0(x) = 0
    F1(x) = 1
    Fn(x) = x Fn-1(x) + Fn-2(x) for n > 1
    F2 is equivalent to x
    F3 is equivalent to x2 + 1
    Then try the following:
    f3 = makeFibonnaciPolynomialEvaluator(3)
    [f3(i) for i in range(10)]
    # or list(map(f3, range(10)))
    # You should get
    # [1, 2, 5, 10, 17, 26, 37, 50, 65, 82]
    There are two approaches to solving this problem. One is to use recursion. This is straightforward. The other is to use dynamic programming. If you use the latter, and your program generates a table of lambda functions in this approach, you may need to use extra keyword arguments in your lambda expressions in order to force evaluation and closure of the specific values of variables in the surrounding local context in order to avoid later runtime errors such as infinite recursion.

    Your solution to this problem should be coded in a file called, and you should include the definition of a test function testP7() that shows the above example involving f3.

Last updated: 19 January at 6:29 PM (moved the deadline to Saturday); 18 Jan. 7:25 PM (added "(or greater than)" in problem 3); 16 Jan. 4:10 PM (the function in 4c is renamed makeArithGeneratorV2 so it doesn't have to be consistent with that in 4a; similarly use makeGeomGeneratorV2 in 4d); 11:51 AM (the function testP3 is required, not testP5); 12 Jan. 8:00 PM (fixed spec. of P3, and added examples for P4a, b); 11 Jan. 3:20 PM (corrected spelling of tribonacci); 11 Jan. 1:52 AM.