Description
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).
Iwillprovideatestscriptwhichperformsminimaltestingofyourimplementation. Ifyourprogramdoesnotpasstheprovided 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. Tasks 1. Defineafunctionnamedlevel thatreturnsthestaticscopinglevelofagivenvariable. Ifthevariableislocal(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 ppTableuseful. Thevariablethispointstothecurrentenvironment/scope,whilethefunctionppTabledisplaysareadable 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) ( 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 compatiblefunctionsmake-agendaandpropagateforcreatingtheinitialagendaandrunningthesimulation,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 “nnassignment 3 loaded!nn”) 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
