COMP 210 Exam 3

Name: __________________________________________________________________

Start time: _______________________________________________________________

End time: ________________________________________________________________

Honor code pledge:

________________________________________________________________________

Scores (to be completed by course staff)
Problem							Extra credit
Problem	1	2	3	4	5	Total	6	7	Total
Score
Possible	20	10	15	15	30	90	10	10	20

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.

(20 points total)
1. (10 points) Develop a function
```
lastpos : [number] -> number or false
```
  that 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 set! or set-…!.
2. (5 points) Hand-evaluate the expression
```
(lastpos (list 8 -1 2 -5 0 3 0))
```
  You need only show the recursive calls and final result.
3. (5 points) Given a list of n numbers, what is the maximum number of recursive calls to lastpos that may be needed to compute a result?
(10 points total) The following function models a looping construct common to many programming languages.
```
; 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) …)
```
1. (5 points) Write for without using any side-effects.
2. (5 points) Write for with side-effects, i.e., changing a local variable to successively take on the values low, (+ low incr), …
(15 points) In the land of Nincompoopia, there is a castle with a magic dungeon and some strange jailers. For any given n you choose, the dungeon will have that many jail cells, each with a prisoner. Of course, all the cells are locked.

For the holidays, the jailers go through a strange ritual. First, they toggle every other cell lock, (counting from zero, the 0th, 2nd, 4th, …). I.e., if it's locked, they unlock it. If it's unlocked, they lock it. Next, they toggle every third cell lock (0th, 3rd, 6th, …). They continue in this fashion until they finally toggle every nth cell lock (just the 0th). After all that effort, the jailers go home for the holidays.

Write a function
```
nincompoopia : natural -> natural
```
that 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 for from the previous problem and vectors.
(15 points total) The purely functional lists that we have used for most of the course are sometimes described as singly-linked lists by imperative programmers. In particular, we can think of each cons struct as having a single "link" to the next struct via the rest field. 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-dll of this type should maintain the following invariants:
- If it is empty, nothing more is required.
- If the left field is empty, nothing is required. But if the left field is not, then (cons+-right (cons+-left a-dll)) should be exactly the same as a-dll.
- A similar condition holds for the right field.
With a singly-linked list, we need to know the first cell of the list. With a doubly-linked list, it's enough to have access to any cell, because we can move left and right along the list.

The goal of this exercise is to develop a mutable doubly-linked list that we can extend on the right (so we can always make it longer) and where we can change the value in the cell that we are currently at.
1. (5 points) Give code creating a doubly-linked list with one cell with value 'Zero. Give code creating a doubly-linked list with two cells, one with 'Zero, and one with 'One.
2. (5 points) Assume that a-dll is a globally-defined doubly-linked list. Write a function
```
; write! : ('Zero or 'One) -> void
; Changes the value of the current cell of a-dll.
```
3. (5 points) Assume that a-dll is 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 'Zero.
```
For the rest of the exam, you can assume that you are given a move-left! function that moves left (if it can, and stays in place otherwise).
(30 points) One of the simplest and most widely used models of computation is called a finite-state machine (FSM). We can think of an FSM as a function with memory: At any point in time, it can take one input (for simplicity, we'll say the input can only be 'Zero or 'One), and change state based on its input and the current state. An FSM can only have a finite number of different states. We can assume that each state has a unique name in the form of a symbol. At any time, the machine is said to be "in" one of these states. Whenever the machine is given one input, the machine can change from one state to another. Such a change in state is called a transition. Transition rules have the form "If you see the input n and you are in state Current, then go to state Next". If there is no transition defined, then the machine is considered to have stopped and terminated all its work.

A simple example of an FSM is the traffic light, which has states named 'Red, 'Yellow, and '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!

Other examples of FSMs include the controllers for the dishwasher, soft-drink machine, your digital alarm clock, and, in fact, most appliances that we use everyday. This problem will give you practice with this concept that you'll see everywhere from now on.

In this problem we will implement an FSM using the same ideas that we used to implement graphs with sharing. We will use the following type definitions:
```
; 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.
```
1. (10 points) Using exactly one make-state for each state, define a global variable traffic-light of type machine, which contains the three states discussed above. Note that you will model the transition rules by picking the value for ifZero and ifOne in 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.).
2. (5 points) Define a function
```
init_light : void -> void
```
  that initializes the global variable current to the safest initial state.
3. (5 points) Write a function
```
step : ('Zero or 'One) -> void
```
  which takes the next input and makes one transition. This function should use only the global variable current and the current input. It should also work for any machine that we define, not just the traffic light.
4. (5 points) Define a function
```
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 current to be the initial state -- the first state in the list.
5. (5 points) Define a function
```
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 step function from part (c).
(10 points -- extra credit) An extended finite state machine (EFSM) is an FSM with a notion of "action". An action is a value (make-action move output) where move is either 'Left or 'Right and output can be either 'Zero or 'One. Now, each transition also produces an action and an output.
1. (1 point) Write a revised definition of the type machine, and write a revised function
```
step : ('Zero or 'One) -> action
```
  which returns the action associated with the transition.
2. (1 point) Write a function
```
step-from-dll : void -> action or false
```
  which reads the input from a-dll and steps the EFSM using this input. The function returns false if there is no transition from the current state with the current input.
3. (1 point) Write a function
```
step-with-dll : void -> bool
```
  which reads the input from the a-dll and 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-dll left. Similarly for 'Right. The output should be written to a-dll before the move is made.
4. (7 points) Write the code for building an EFSM that achieves the following task: If we start with a-dll containin a series of 'Ones, we end with a dll that has been extended with one 'Zero and the same number of 'Ones. For example, if we start with 'One 'One 'One on the dll, we can keep steping the machine until it stops. When it stops, we should have 'One 'One 'One 'Zero 'One 'One 'One on a-dll. Your machine should use no more than ten states, but must still work for any series of 'Ones of any length. The machine must stop after it has finished this task.
(10 points -- extra credit) Throughout the course, we used compound values and self-reference to model intersting structures, starting from natural numbers and lists and going to complicated mutable data structures. As it turns out, with a little bit of work, the lambda-calculus (consisting of only application, variables, and 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)))
…
```
1. (1 point) Let the type ChNu = (X->X)->(X->X). Define the function
```
add : ChNu ChNu -> ChNu
```
  which takes encodings of m and n and returns an encoding of m+n.
2. (1 point) Define a similar function for multiplication.
3. (1 point) Define a similar function for exponentiation.
4. (7 points) Suggest a type ChLiNu for representing a list of numbers, and show how it can be used to define the map function on lists.