Preliminary information
This is your third Scam assignment.
At the top of your assignment, place a definition similar to the following:
(define (author)
(println "AUTHOR: Izzy Iterator iiter@crimson.ua.edu")
)
with the name and email replaced by your own name and email.
For each numbered task (unless otherwise directed),
you are to provide a
function with a name of the form
runN,
with the N corresponding to the task number
(as in run1,
run2,
etc.).
This
function is in addition to all other requested functions.
These run
functions will test your implementation and are to take
no arguments.
For example, if task 5 is:
5. Implement factorial so that it implements a recursive process.
Name your function fact.
you should provide a run function similar to:
(define (run5)
(print "The result of (fact 3) is " (fact 3))
(println "[it should be 6]")
...
)
Woe betide students who
provide insufficient testing should their implementations prove to be
incorrect!
If you do not complete an
exercise,
do not provide a run function for that
exercise.
If you omit the run function corresponding to
an exercise,
it will be assumed that you are skipping that
part
and you will receive no credit for that exercise.
When you have completed testing of your run functions, comment out
any calls to them (but do not comment out the definitions).
I will provide a test script which performs minimal testing of your
implementation.
If your program does not
pass the provided test script without failing,
I will not grade your exercise and you will receive zero credit for the
assignment.
You may use assignment and loops for this set of tasks, unless otherwise
directed.
You will also be graded on style, including, but not limited to,
the proper nesting of helper functions that are not expected to be
called directly.
Tasks

Define a function named nonlocals, which returns a list of all
the nonlocal variables referenced in a function definition.
For example,
(define (square x) (* x x))
(inspect (nonlocals square))
should produce the following output:
(nonlocals square) is (begin *)
since
*
is the only nonlocal variable in the function body.
The symbol begin is also in the list because Scam wraps the body of
a function with a begin to make the function body appear to be a Scam
block.
Each nonlocal variable should appear exactly once in the resulting list.
Given a closure, one can retrieve the formal
parameters and body with:
(get 'parameters square)
(get 'code square)
respectively. Both the parameters and the function body are simple Scam lists
which can be manipulated with car, cdr, setcar!, and setcdr!.
Note: a symbol anywhere in the body represents a variable if it is not
wrapped in a call to quote.
You may assume that all local variables are defined before use.

Define a function named replace that replaces all occurrences of
a given symbol in a function definition
with a given value. You can obtain the body of a function definition as follows:
(define (square x) (* x x))
(define body (get 'code square))
(inspect body)
The inspection displays the list
(begin (* x x))
whose car is the symbol
begin
and
whose cadr is the list
(* x x)
.
You can update the body of the function as follows:
(set 'code '(begin (+ x x)) square)
(inspect (square 5))
The inspection should display the value 10. A call to replace
might look like:
(replace square '* +)
You can use the replace function to speed up the execution of
any function. Your run function should demonstrate such a speed up
with a recursive Fibonacci function.
Your replace function needs to work recursively. That is to say,
it needs to replace the symbol in any local function definitions,
including lambdas.
The function should only replace rvalue occurrences of the symbol.

Note: you may want to do this task last, as it is quite involved.
On the other hand, you need an AVL tree for your DPL and you should
be able to easily translate your Scam code to your language.
Define a binary search tree class named avl,
which implements a selfbalancing AVL tree.
Your class should support the following methods:
insert
find
size
statistics
The statistics method does a level order traversal,
printing out, in turn, each node value and the height of the left subtree minus
the
height of the right subtree.
The two values are to be
separated by a colon. The node outputs themselves are separated by spaces and
the entire output is terminated by a newline.
The other methods have their obvious meanings.
The size method should run in constant time.
The insert and find methods should run in
$\theta \left(\mathrm{log}n\right)$
time.
Examples:
(define t (avl))
((t 'insert) 3)
((t 'insert) 4)
((t 'insert) 5)
((t 'insert) 1)
((t 'insert) 0)
((t 'find) 5) ; should return #t
((t 'find) 7) ; should return #f
((t 'size)) ; should return 5
((t 'statistics)) ; should print 4:1 1:0 5:0 0:0 3:0
Assume your tree will be populated with unique values.
Do no error checking; assume good input.
You must use Scam's object system and you must base your
implementation on the pseudocode found at:
http://beastie.cs.ua.edu/avl/index.html.

Using the imperative style of the text,
implement a constraint network for the
formula for determining the gravitation
force between two objects:
$f=G\genfrac{}{}{0.1ex}{}{{m}_{1}{m}_{2}}{{r}^{2}}$
Name your
network constructor
gravity
.
Use a value of 0.00667300 for G. The function gravity should take
four connectors as arguments, corresponding to
the force (f),
the mass of object 1 (m1),
the mass of object 2 (m2), and
the distance between the two objects (r).
Provide the following accessor and mutator functions
getvalue, setvalue!, and forgetvalue!
as described on page 289 of the text.

Define a onetime synchronization barrier object using
using Scam's binary semaphore.
Name this function barrier.
You can use the gettid function to access the ID of the thread
asking for the mutex.
Example calls:
(define b (barrier))
((b'set 3)) ; set the barrier for three threads
...
((b'install)) ; the actual barrier
((b'remove)) ; remove the barrier
For this example, once three threads reach the installation point,
the barrier is removed and all threads can pass.
Your run function should test your barrier. The sleep function may be
useful for this purpose.

The big gulp stream is the
infinite stream of integers whose only prime factors are 7 and 11.
The first few elements of the stream are
[7,11,49,77,...]
.
Name the stream constructor biggulp and provide a streamdisplay
function:
(define bgs (biggulp))
(streamdisplay bgs 4) ;should print [7,11,49,77,...]

Given a stream that represents:
${x}^{2}+3x4$
show that
$\genfrac{}{}{0.1ex}{}{\mathrm{d}\phantom{\rule{0.278em}{0ex}}{\displaystyle \int}{x}^{2}+3x4\phantom{\rule{0.222em}{0ex}}\mathrm{d}x}{\mathrm{d}x}$
is equal to:
${x}^{2}+3x4$.
Show this by subtracting the integratedthendifferentiated stream from the
original stream and demonstrating that
the resulting stream is composed of zeros (or small numbers near zero).
Your run function should display a sufficient portion of
the original stream, the integrated stream, the derivative of the
integrated stream, and a stream representing the difference of the
original stream and the differentiated stream.
Name your streams poly, intPoly, and divIntPoly,
and difference,
respectively. The intPoly stream should be produced by passing
poly through an integrating function and the divIntPoly
strean should be produced by passing the resulting
stream through a differentiating function.
Name your integrating function integral,
your differentiating stream, differential,
and your stream difference function
subStreams.
To start, create the poly stream by making use of
the signal function:
(define (signal f x dx)
(consstream (f x) (signal f (+ x dx) dx))
)
Start your poly stream at zero.
Next integrate and differentiate
this stream using the integral and differential functions,
respectively:
(define (integral s dx)
...
)
(define (differential start s dx)
...
)
Note:
the integral stream should show the total area under the curve from the
starting value to the ${i}^{th}$ dx. For example, the stream:
[0 1 4 9 16 25 ...]
represents the $y={x}^{2}$ polynomial with a dx of 1. The integral of
this stream should be:
[0 1 5 14 30 55 ...]
using a crude rectangular approximation of the area under the curve between
two adjacent points. Also, you will need to use the same dx for the
signal, integral, and differential functions. Finally,
you will need to pass in the first value of the original
stream to the differential function so you can unwind the integral stream.
Extra credit for more sophisticated integral and differential functions.

Consider this series:
$1\genfrac{}{}{0.1ex}{}{{x}^{2}}{2!}+\genfrac{}{}{0.1ex}{}{{x}^{4}}{4!}\genfrac{}{}{0.1ex}{}{{x}^{6}}{6!}+\genfrac{}{}{0.1ex}{}{{x}^{8}}{8!}...$
Define a function named mystery that
returns the stream that holds the terms of the above series for a given x.
Define a function named psmystery that produces the
stream of partial sums of
(mystery x)
. Define a function named
accmystery that accelerates
(psmystery x)
using the Euler transform.
Define a function named supermystery that produces a super accelerated
stream using a tableau of everaccelerated partial sum streams. All of these
function takes x as their sole arguments.

Exercise 3.71 in the text. Define a function named ramanujan that
produces a stream of Ramanujan numbers. The function takes no arguments.