CSSE 304 Exam 2 Part 2a 10/18/2017 (day 26.5) Name______________________ Section: 01(9:00) 02 (9:55) 03 (10:50 TR)
Problem
Possible
Earned
Comments
C1
10
C2
15
C3
15
During the entire exam you may not use email, IM, cell phone, PDA, headphones, ear buds, or any other communication device or software that allows you to communicate with another person.
Part 2a programming on your computer. For this part, you may use a Scheme editing/programming environment, the textbooks from the course (including TSPL, of course), The Chez Scheme Users’ Guide, the PLC grading program, and any materials that I provided online for the course. You may not use any other web or network resources. You are also allowed to look at and copy any Scheme code that you (or you and your partner) wrote before the exam, but nothing else (except code in the resources listed above) that was written by others, including CSSE 304 students from previous terms.
For any code you are asked to write, you may assume that all input values will have correct types; you do not need to write code to check for illegal input data. Test your code off-line before you submit to the grading server (an attempt to reduce the load on the server).
Submit your code to the E2-201810-2a assignment on the PLC server.
When you have finished either of Part 2a or Part 2b, please go ahead and submit the paper for that part. Then we can go ahead and grade yours, increasing our chances of returning the exams in Thursday’s class.
C1. (10 points) No mutation is allowed in your code for this problem. Using the same grammar for LcExp that we developed in class and that we used for free-vars and bound-vars in Assignment 10, write (occurring-vars LcExp), which produces a list of all variables that occur in the lambda-calculus expression LcExp. Your code does not have to handle any of the grammar enhancements from A10, A11, and A13.
Examples:
> (occurring-vars ‘g)
(g)
(h g)
> (occurring-vars ‘(lambda (x) x))
(x)
> (occurring-vars ‘((lambda (y) (lambda (x) y)) z))
(y z)
> (occurring-vars ‘((lambda (y) (lambda (x) y)) (x (x (t x)))))
(y t x)
C2. (15 points) No mutation is allowed in your code for this problem. In class and in A9, we introduced list-recur, snlist-recur, and bt-recur, which create procedures that recur over the corresponding data structures. Here you will use a procedure that recurs over LcExps (based on the same grammar as in problem 1). To keep it short, we will call this recursion-maker procedure lamrec.
(define lamrec
(lambda (vf lf af)
(letrec ((helper
(lambda (exp)
(cond
[(symbol? exp) (vf exp)]
[(eq? (car exp) ‘lambda)
(lf (caadr exp) (helper (caddr exp)))]
[else (af (helper (car exp))
(helper (cadr exp)))]))))
helper)))
You are to rewrite occurs-free? (from the EoPL book) and free-vars (from A10) using lamrec. None of the three procedures that you pass to lamrec is allowed to recur over an LcExp; all of that recursion must be done in lamrec itself.
.
Examples:
> (occurs-free? ‘x ‘x)
#t
> (occurs-free? ‘y ‘x)
#f
> (occurs-free? ‘y ‘((lambda (x) (x y)) (z (lambda (y) (z y)))))
#t
> (occurs-free? ‘y ‘(x ((x x) x)))
#f
> (occurs-free? ‘x ‘((lambda (x) (x y)) (z (lambda (y) (z y)))))
#f
> (occurs-free? ‘x ‘(x ((x x) x)))
#t
> (free-vars ‘(x x))
(x)
> (free-vars ‘((lambda (x) (x y)) (z (lambda (y) (z y)))))
(y z)
> (free-vars ‘(lambda (x) y))
(y)
> (free-vars ‘((lambda (y)
(lambda (y) y))
(lambda (x) (lambda (x) x))))
()
C3. (15 points) Mutation is allowed in your code for this problem, especially since the code we gave you involves mutation. Below is an object-oriented style definition of a queue “class”. This queue uses two lists to internally store the queue elements. q-f stores the zero or more elements from the front of the queue, and q-r stores the rest of the queue’s elements in reverse order. This makes enqueueing an element cheap—it’s just a cons. Dequeueing is relatively efficient too. We can almost always use car and cdr to chop off the front. Occasionally, when the front becomes empty, we have to move the reversed rear into the front. The following piece of the code is the part that moves the reversed rear onto the front:
(if (null? q-f) (begin (set! q-f (reverse q-r))
(set! q-r ‘())))
In the given code, this logic shows up in multiple places throughout the implementation. You should instead create an object-level procedure internal to the implementation that accomplishes this transfer. Replace all occurrences of the above logic with calls to your new procedure rather than writing the details multiple times. Call your new queue-maker function make-queue2.
Note that the code we give you already passes the server tests. In order to get credit for this problem, you must write and call the required internal procedure, while still passing the test cases.
This definition is part of the starting code that we will give you:
(define make-queue
(lambda ()
(let ([q-f ‘()] [q-r ‘()])
(lambda (msg . args)
(case msg
[(empty?) (if (null? q-f) (begin (set! q-f (reverse q-r))
(set! q-r ‘())))
(null? q-f)]
[(enqueue) (set! q-r (cons (car args) q-r))]
[(dequeue) (if (null? q-f) (begin (set! q-f (reverse q-r))
(set! q-r ‘())))
(cond
[(null? q-f) (errorf ‘queue “attempt to dequeue from empty queue”)]
[else (let ((h (car q-f)))
(set! q-f (cdr q-f))
h)])]
[(peek)
(if (null? q-f) (begin (set! q-f (reverse q-r))
(set! q-r ‘())))
(cond
[(null? q-f) (errorf ‘queue “attempt to peek from empty queue”)]
[else (car q-f)])]
[else (errorf ‘queue “illegal message to queue object: ~a” msg)])))))
> (let ([q (make-queue2)]
[results ‘()])
(q ‘enqueue 2)
(q ‘enqueue 4)
(set! results (cons (q ‘dequeue) results))
(set! results (cons (q ‘dequeue) results))
(q ‘enqueue 3)
(q ‘enqueue 1)
(set! results (cons (q ‘dequeue) results))
(q ‘enqueue 5)
(cons (q ‘dequeue) results))
(1 3 4 2)
> (let ([q1 (make-queue2)]
[q2 (make-queue2)]
[results ‘()])
q1 ‘enqueue 2)
q1 ‘enqueue 4)
(set! results (cons (q1 ‘dequeue) results))
(set! results (cons (q1 ‘dequeue) results))
(q1 ‘enqueue 3)
(q2 ‘enqueue 1)
(set! results (cons (q2 ‘dequeue) results))
(q2 ‘enqueue 7)
(q2 ‘enqueue 8)
(q2 ‘enqueue 1)
(q1 ‘enqueue 5)
(set! results (cons (q2 ’empty?) results))
(set! results (cons (q2 ‘dequeue) results))
(set! results (cons (q1 ‘dequeue) results))
(set! results (cons (q1 ‘dequeue) results))
(cons (q1 ’empty?) results))
(#t 5 3 7 #f 1 4 2)