(1) Sort a list of distinct numbers in ascending order, using the following divideand- conquer strategy (Quicksort): divide the list of numbers into two lists: one that contains all items that are strictly smaller than the first item (often called the pivot), and another with all those items that are strictly larger than the first item. Then the two smaller lists are sorted using the same procedure. Once the two lists are sorted, the pieces are juxtaposed. For example, given (11 8 14 7) the pivot is 11. We make two lists, (8 7) and (14). The second is already sorted; sorting the first - pivot is 8 - yields (7 8). Putting the three pieces together: (7 8) 11 (14) ==> (7 8 11 14).
(2) Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g.
(define stack1 (make-stack))
(define stack2 (make-stack))
Write procedures to manipulate stacks, e.g.
(stack1 'empty?) ==> boolean
(stack1 'push! item) ==> pushes item on top of stack
(stack1 'top) ==> returns top element of stack,
leaves stack unchanged
(stack1 'pop!) ==> throws away top element of stack
(stack1 'print) ==> prints some representation of the stack from top to bottom, enclosed in brackets etc….
Your tests should include making several stacks, pushing on one what is popped from the other, attempts to pop from an empty stack etc.
Also write a procedure to reverse a list by using two stacks.
(3) Implement your own streams.
(a) Write (delay ) as a special form for (lambda () ) and (force ).
(b) Write (stream-cons x y) as a special form, as discussed in class.
(c) Write stream analogues of some familiar list processing functions, including: (stream-car str)
(stream-cdr str)
(stream-null? str)
(stream-ref str n) --- returns the nth
element in stream str
(stream-filter pred str) --- makes a new stream of
elements satisfying pred
(stream-for-each proc str) --- applies proc to each
element of str for side effect
(first n str) --- makes a stream of the
first n items in str
(list->stream lis) --- makes a stream from
list lis
(stream->list str) --- opposite coercion
For example, if you have defined a stream of even integers called evens, you can display the first 50 even integers as follows:
(stream-for-each (lambda (x) (display x)(display "
")) (first 50 evens)).
Test your functions convincingly!
(d) Now define a bunch of streams to test your functions:
(i) an infinite stream of 1's
(ii) an infinite stream of all even integers
(iii) an infinite stream of random numbers between 1 and 100
(iv) write a predicate (prime? n) that tests for primality and use it to create a stream of all primes
(4) (i) Add the special form let to the metacircular interpreter (see ch4- mceval.scm from SICP and the version on the course website).
Hint: remember let is just syntactic sugar for a lambda expression and so a rewrite to the lambda form is all that is required.
(ii) What changes are needed in the metacircular interpreter so that Scheme uses dynamic instead of lexical scoping?
Testing
As always, test thoroughly and present your test results clearly. Do not forget to demonstrate that your changes to the metacircular interpreter work in all cases!
Your assignment should include a README.TXT file that contains details of the testing you have performed and any special requirements that have for setup. All Scheme files should have the extension .rkt. All text files should have the extension .txt.