Description
Tasks
1. Define a function named level that returns the static scoping level of a given variable. If the variable is local (i.e., defined
in the same frame as the call to level, level should return 0. If the variable is found in the next outer scoping level, the
return value should 1, and so on. Here is an example call:
(define a 3)
(define (f x)
(inspect (level ‘a))
(* a x)
)
The level function should return the symbol UNDEFINED if the desired variable is not defined locally or in any enclosing
scope. You must decompose Scam environments (they are structured as lists) to do this task. That is, you may not
use the local? function or any similar functions. You may find the predefined variable this and the predefined function
ppTable useful. The variable this points to the current environment/scope, while the function ppTable displays a readable
rendering of an environment/scope. Example:
(ppTable this)
You can get the enclosing scope of an environment named e with the command:
(e’__context)
2. Define a function named cache that replaces all the non-local variables in a function body with the values found in the
definition environment. You may assume that local variables will be defined with the define function. You do not need
to process the bodies of nested functions.
You can retrieve the definition environment from a closure with:
(define denv (get ‘__context square))
You can retrieve the value of a symbol in a list of symbols with:
(define listOfSymbols ‘(+ – * /))
(get (car listOfSymbols) denv) ; get the closure bound to +
Example:
scam> (define m 2)
scam> (define (msquare x) (* m x x))
scam> (include “pretty.lib”)
scam> (pretty msquare)
(define (msquare x)
(* m x x)
)
scam> (cache msquare)
scam> (pretty msquare)
(define (msquare x)
( 2 x x)
)
3. Define a priority queue with the following interface:
(set! p (PRQ comparator)) ; constructor, returns a priority queue object
(p ‘insert item rank) ; insert item into p with priority rank
(p ‘remove) ; return the pending item (item is removed)
(p ‘item) ; return the pending item (item is not removed)
(p ‘rank) ; return the pending rank (item is not removed)
(p ‘size) ; returns the number of items in the queue
(p ’empty?) ; returns whether or not the queue is empty
A comparator is any ordering function that takes two items and returns true if the first item comes before the other in
that ordering. Ranks can be any value that is compatible with the comparator The priority queue is ordered according
to the comparator. For example, if the comparator is <, the item pending to be removed should have the lowest rank
among all ranks in the queue.
4. Define a function, named add4, that returns a simulator for a four-bit ripple carry adder. The adder should be built
from four daisy-chained single bit full adders. The single-bit adder, named add1, should be built from two-input ANDs
and ORs, plus NOTs.
An example call to add4 would be:
(add4
(list x3 x2 x1 x0)
(list y3 y2 y1 y0)
(list o3 o2 o1 o0)
cout
)
where the x’s, y’s, o’s and cout are instantiated wires and x3 and y3 represent the high-order bits input bits and o3
represents the high-order output bit. The wire cout is represents the carry-out bit. Your wire constructor, as well as the
wire accessors and mutators (get-signal and set-signal) should be compatible with that of the text. Provide textbook
compatible functions make-agenda and propagate for creating the initial agenda and running the simulation, respectively.
2
5. Define a n-ary mutex constructor using Scam’s binary semaphore. Name this function mmutex. You can use the gettid
function to access the ID of the thread asking for the mutex.
Example calls:
(define m (mmutex 3))
((m’p))
((m’v))
The function call ((m’p)) should return the symbol ACQUIRED. Your mutex should reject release calls if the process
performing the release is not one of the processes holding the mutex. Therefore, the call ((m’v)) should return the
symbol RELEASED or the symbol FORBIDDEN, as appropriate.
Your run function should test your mutex. The sleep function may be useful for this purpose.
6. Create an infinite stream of integers whose only prime factors are 3, 11, and 17. The first few elements of the stream
are [3,9,11,17,27,…]. Name the function that creates and returns this stream pf-3-11-17.
7. Define a function, named saverage, that averages an infinite stream. When given a numeric stream:
(a b c d …)
where a, b, c, d, etc. represent numbers, returns a new stream whose elements are:
(a (/ (+ a b) 2.0) (/ (+ a b c) 3.0) (/ (+ a b c d) 4.0) …)
8. Use an infinite stream to model the following summation: ∑n
j=1
1
j
where the digits of j do not contain a nine. Name this
stream mystery. The first terms of this stream are:
[1, 1
2
,
1
3
,
1
4
,
1
5
,
1
6
,
1
7
,
1
8
,
1
10 ,
1
11 , …]
Note the absence of 1
9
.
Now solve this summation by generating a partial summation of the stream, naming the result mystery1. Accelerate
the stream using an Euler transform, naming the result mystery2. Finally, use a tableau of Euler accelerations to superaccelerate the stream (as in page 337 of the text), naming the result mystery3. Full credit reserved for implementations
where the 140th element of the all the mystery streams (at least) can be explored without error.
Extra credit: have your run function indicate the result of the summation carried to an infinite number of terms (within
2 decimal places).
9. Exercise 3.71 in the text. Name the stream-creating function ramanujan. It should take no arguments. The stream
that ramanujan returns should be a stream of all the Ramanujan numbers in increasing order.
Assignment submission
Submitting the assignment The entire assignment should be contained in a single file named assign3.scm. Any explanatory
text should be in the form of Scam comments, which begin with a semicolon. The file should load into the Scam interpreter
cleanly. The last line of your file should be:
(display “\n\nassignment 3 loaded!\n\n”)
If you do not see the message ”assignment 3 loaded” when loading your file into the Scam interpreter, then there is an error
some where that needs to be fixed. If your file does not load properly (i.e. I do not see the message), you will receive no credit
for your work. To submit your assignment, delete extraneous files from your working directory. Then, while in your working
directory, type the command:
submit proglan lusth assign3
The submit program will bundle up all the files in your current directory and ship them to me. Thus it is very important that
no executable files be in your directory. This includes subdirectories as well because all the files in any subdirectories will also
be shipped to me. I will deduct points for extraneous files, so be careful. You may submit as many times as you want before
the deadline; new submissions replace old submissions.
3
