What to Turn In:
You should turn in the following files:
functionFun.py
seqPredictor.py
sentenceGenerator.py
fibPoly.py (if you opt to do Problem 7)
readme.txt
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 functionFun.py that contains your function definitions
for Problems 1, 2, 3, and 4.
-
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]
-
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.
- 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().
- 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()
JohnScores()
1
JohnScores()
2
JohnScores()
3
MaryScores()
1
JohnScores()
4
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)
countBy7()
7
countBy7()
14
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)
scaleBy13()
13
scaleBy13()
169
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)
nextOdd()
1
nextOdd()
3
nextOdd()
5
d.
now modify your function for part b, creating
makeGeomGeneratorV2(k, start=1)
so that geometric sequences can start at any value.
- 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.
- 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))
6
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.
- 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
Note:
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 fibPoly.py, and you should include
the definition of a test function testP7() that shows
the above example involving f3.
|
