Start time: _______________________________________________________________
End time: ________________________________________________________________
Honor code pledge:
This is a take-home exam. It is due Wednesday December 14, 5pm. Turn it in to Dr. Taha's office, DH 3103.
You are allowed 5 contiguous hours to work on the exam.
You may use your textbook, notes, and any material provided as part of this course, whether printed or online. You may use any Scheme syntax and functions that have been introduced in class, lab, or the sections of textbook covered so far.
You may not use the rest of the Web, other people, or any other materials. You may not use DrScheme while taking the exam.
Read all instructions and problems carefully. You need only present the parts of the design recipe that are specifically asked for. If you have any questions about what a question is asking, make reasonable assumptions and document them.
Print this exam out, do your work in the space provided, and turn this in. If you need additional space, use the backs of the exam pages or additional paper.
lastpos : [number] -> number or falsethat returns the last positive number before the first zero. If there is no such number, return
false. Do follow all steps of the design recipe that are relevant for defining such a function. Do not reverse the list or use side-effects, i.e., do not use
(lastpos (list 8 -1 2 -5 0 3 0))You need only show the recursive calls and final result.
lastposthat may be needed to compute a result?
; for : number number number (number -> X) -> void ; Evaluates (body low) ; (body (+ low incr)) ; (body (+ low incr incr)) ; … ; in that order, for each value of low+n*incr that is ; less than or equal to high. ; (define (for low high incr body) …)
forwithout using any side-effects.
forwith side-effects, i.e., changing a local variable to successively take on the values
(+ low incr), …
nincompoopia : natural -> naturalthat simulates a dungeon of n jail cells. At the end, return the number of prisoner who get to escape because they're cells are unlocked at the end. Use
forfrom the previous problem and vectors.
consstruct as having a single "link" to the next struct via the
restfield. In this problem, we will consider doubly-linked lists, where struct has a link to both the next AND the previous structs. For simplicitly, we will assume that the elements can only be 'Zero or 'One. We can use the following type definition to implement this idea:
(define-struct (cons+ left value right)) ; A doubly-linked list (dll) is one of ; - empty, or ; - (make-cons+ left value right), ; where value is either 'Zero or 'One ; and left,right are doubly-linked lists.A value
a-dllof this type should maintain the following invariants:
leftfield is empty, nothing is required. But if the
leftfield is not, then
(cons+-right (cons+-left a-dll))should be exactly the same as
a-dllis a globally-defined doubly-linked list. Write a function
; write! : ('Zero or 'One) -> void ; Changes the value of the current cell of a-dll.
a-dllis a globally-defined doubly-linked list. Write a function
; move-right! : void -> void ; Changes the global list a-dll to be one element ; to the "right". If there is no cell to the right, ; one is added with value
move-left!function that moves left (if it can, and stays in place otherwise).
'Green. As we said above, we will assume the only input it accepts are 'Zero and 'One. Then we need six rules that determine the next state based on the input and the current state. Note that we will also need the six rules to make sure the traffic light never stops!
; A machine is a list of states and a mutable global variable ; "current" which points to the current state. ; ; A state is ; - (make-state name ifZero ifOne) ; where name is a symbol, and ifZero and ifOne are either states or false.
make-statefor each state, define a global variable
machine, which contains the three states discussed above. Note that you will model the transition rules by picking the value for
ifOnein each state. If the input is 'Zero, the light should go to red, independent of the current state. If the input is 'One, the light should move to the next color in the normal cycle (red, green, yellow, red, etc.).
init_light : void -> voidthat initializes the global variable
currentto the safest initial state.
step : ('Zero or 'One) -> voidwhich takes the next input and makes one transition. This function should use only the global variable
currentand the current input. It should also work for any machine that we define, not just the traffic light.
easy-machine : [symbol] -> [state]that takes a list of symbols and creates an FSM where each given symbol names a state. All transitions in this machine are false. You should change the global variable
currentto be the initial state -- the first state in the list.
any-machine : [symbol] [[symbol]] -> [state]that takes takes a list of state names and a list of 3-element-lists and creates a FSM. Each 3-element list is a transition. The first element is a name for a state that should be in the machine, the second element is the name of an input (either 'Zero or 'One), and the third element is the name of the next state. For example, your function should be able to automatically produce the same result as you did by hand if you give it the list
(list 'Red 'Yellow 'Green)and the following transitions:
(list (list 'Red 'Zero 'Red) (list 'Red 'One 'Green) (list 'Yellow 'Zero 'Red) (list 'Yellow 'One 'Red) (list 'Green 'Zero 'Red) (list 'Green 'One 'Yellow))Make sure that the resulting machine will work properly with the
stepfunction from part (c).
'Rightand output can be either
'One. Now, each transition also produces an action and an output.
machine, and write a revised function
step : ('Zero or 'One) -> actionwhich returns the action associated with the transition.
step-from-dll : void -> action or falsewhich reads the input from
a-dlland steps the EFSM using this input. The function returns false if there is no transition from the current state with the current input.
step-with-dll : void -> boolwhich reads the input from the
a-dlland steps the EFSM using this input. It should return true if and only if the machine was able to make a move. If the resulting move is
'Left, the move the
a-dllleft. Similarly for
'Right. The output should be written to
a-dllbefore the move is made.
a-dllcontainin a series of
'Ones, we end with a dll that has been extended with one
'Zeroand the same number of
'Ones. For example, if we start with
'One 'One 'Oneon the dll, we can keep steping the machine until it stops. When it stops, we should have
'One 'One 'One 'Zero 'One 'One 'Oneon
a-dll. Your machine should use no more than ten states, but must still work for any series of
'Onesof any length. The machine must stop after it has finished this task.
lambda) is enough to encode a lot of the types that we know. For example, Alonzo Church noticed that we can encode each natural number N with a function:
c_N : (X->X) -> (X->X) c_0 = (lambda (f) (lambda (x) x) c_1 = (lambda (f) (lambda (x) (f x)) c_2 = (lambda (f) (lambda (x) (f (f x))) …
ChNu = (X->X)->(X->X). Define the function
add : ChNu ChNu -> ChNuwhich takes encodings of m and n and returns an encoding of m+n.
ChLiNufor representing a list of numbers, and show how it can be used to define the
mapfunction on lists.