Study Guide for Final Examination

Preliminaries

This is a study guide for the final examination. It gives you information on the structure of the final (which will be copied nearly verbatim) and questions that may appear on the final.

Questions on the final will be selected exclusively from the questions in this study guide. They will differ from the questions in this study guide in two ways: (a) I will add the multiple-choice options which you must choose between; (b) I may reword a few problems slightly.

There are slightly more than thirty questions in this study guide. There will be fifteen questions on the final. Although I have paired questions for each primary subject, I may select multiple questions for one subject and no questions from another.

Exam Format

This is an in-class examination. You will take it during the designated time and in the designated place.

This is a closed-book and closed-computer examination. You may, however, refer to one sheet of hand-written notes that you have brought to the exam.

This is a multiple-choice examination. That is, for each question, you must select one of the options given to you. If you would like, you may also add a short analysis of how you arrived at that answer. If you arrive at a different answer than I did, I will look at that short analysis and may give you partial or full credit.

There are fifteen questions on the exam. Each is worth seven points.

I expect that someone who has mastered the material and works at a moderate rate should have little trouble completing the exam in a reasonable amount of time. In particular, this exam is likely to take you about one hour, depending on how well you've learned the topics and how fast you work. You will, however, have the full three hours allocated ot the final to take the examination.

You will note that the study guide has more than fifteen questions. The fifteen questions on the examination will be selected from the study guide questions.

Academic Honesty

You may study for this examination with anyone you wish. That study may include the development and analysis of solutions to the sample examination problems. However, once you begin the exam, you may not collaborate with anyone else on the examination itself.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say This is among the hardest exams I have ever taken. If you don't start it early, you will have no chance of finishing the exam. You may also summarize these policies. You may not tell other students which problems you've finished. You may not tell other students how long you've spent on the exam.

You must include both of the following statements on the cover sheet of the examination.

1. I have neither received nor given inappropriate assistance on this examination.
2. I am not aware of any other students who have given or received inappropriate assistance on this examination.

Please sign and date each statement. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Rebelsky (that's me).

Problems

Ruby

R1. Consider the following sets of Ruby class definitions that include inheritance and mixins. For which set are the methods alpha, beta, and gamma defined for object obj?

R2. Which of the following is an appropriate instance in which to use mixins rather than inheritance?

Io

I1. Given these Io definitions, which expression has a value of 42?

Io> OperatorTable addOperator ("+", 5)
Io> OperatorTable addOperator ("x", 2)
Io> 5 - := method(i, i-3)

I2. Consider the following sets Io statements which define a hierarchy of objects. After which of set will we see the following output?

Io> whatever proto slotNames foreach(slotName, writeln(slotName))
type
alpha
beta
gamma

Prolog

P1. Which of the following is a correct implementation of permutation(L1,L2) in Prolog?

P2. Which of the following implementations of member(val,lst)

• works correctly if you give it an explicit value and an explicit list (e.g., member(a,[a,b,c])),
• will find sample lists given an explicit value and a variable for the list (e.g., member(a, L)),
• but will have errors (perhaps incorrect output, perhaps looping forever), when given an explicit list and a variable for the value (e.g., member(X,[a,b,c])).

Scala

S1. Consider the following Scala XML definition.

scala> val info =
     | <overview>
     |   <genres>
     |     <genre name="action">action</genre>
     |     <genre name="comedy">comedy</genre>
     |     <genre name="horror">horror</genre>
     |   <genres>
     |   <collections>
     |     <collection name="action">
     |       <movie genre="action">Jaws</movie>
     |       <movie genre="racing">The Fast and the Furious</movie>
     |       <movie genre="comedy">The Jewel of the Nile</movie>
     |     </collection>
     |     <collection name="sgafilms2011">
     |       <movie genre="action">Pirates of the Caribbean</movie>
     |       <movie genre="tithed">Titular Head</movie>
     |       <movie genre="comedy">CF presents CF</movie>
     |     </collection>
     |   </collections>
     | </overview>

Which of the following expressions will return the value action?

S2. Which of the following is a correct definition of map in Scala?

Erlang

E1. Which of the following statements about I/O in Erlang is correct?

E2. Each of the following programs creates a groups of communicating processes. Which program will terminate?

Clojure

Cl1. Which of the following macros is a correct definition of while, a function of two values, test ad body, which behaves like a standard while loop. That is, it repeatedly evaluates the test and, if the test holds, evaluates the body and then starts all over again. If the test does not hold, the loop returns false.

Cl2. Which of the following functions can be easily defined without macros?

Haskell

H1. Which of the following list comprehensions defines the list of primes?

H2. For which of the following type/expression combinations does the stated type fail to match the type of the expression?

C

C1. Which of the following C programs still has memory allocated in the heap at the marked point??

C2. For which definition of key are the three values below equal?

  sizeof (*key);
  sizeof (key);
  strlen (key);

Lisp Implementation

L1. McCarthy leaves the assoc procedure undefined. Which of the following might be an appropriate definition of assoc (which may be expressed in Lisp, C, or S-expressions, or M-expressions)?

L2. Consider the following simple LISP program.

((label fact 
   (lambda (x) 
     (cond 
       ((= x 0) 1)
       (T (* x (fact (- x 1)))))))
 3)

Which of the following association lists best represents the state of the environment (the second parameter to eval) at the point at which we reach the base case in the expression?

L3. For which of the following programs will we see different behavior in a statically scoped and dynamically scoped language?

The Call Stack

CS1. Consider the following C procedures. Which of the following might be the state of the call stack at the point that the program prints Hello, given an initial expression of alpha(2)?

int
alpha (int x)
{
  static int y = 1;
  y++;
  if (x == 0)
    {
      printf ("Hello\n");
      return y;
    }
  else
    return alpha (beta (x-1));
} // alpha

int
beta (int z)
{
  if (z == 0)
    return 0;
  else
    return alpha (z);
} // beta

CS2. Which of the following should not be on the call stack?

Parameter Passing

PP1. Which of the following programs will have different output for each of the main parameter-passing strategies (pass-by-value, pass-by-reference, pass-by-name, pass-by-value-return, and pass-by-text)?

PP2. Assume that we're using pass-by-name. Which code fragment has an output of 42?

Garbage Collection

GC1. You may recall that the root set gives you the things which must be maintained during garbage collection. Which of the following are not in the root set?

GC2. Which of the following garbage collection strategies is most likely to preserve locality (that is, that things that are created at similar times are at similar locations in memory)?

Software Transactional Memory

STM1. One of the advantages of STM is that it lets you compose atomic operations and make the composition atomic. Which of the following compositions of atomic functions need (or need not) naturally be considered as atomic?

STM2. Which of the following are appropriate criticisms of STM?

Continuations and CPS

CPS1. For which of the following programs does cont have a value that approximates

(lambda (x) (display (+ x 2)) (newline) (REPL))

CPS2. Consider the expression

> (/ (+ 3 x (* 4 y)) 7)

Which of the following might be an appropriate translation of that expression to continuation-passing-style?

Monads

M1. For which of the following applications is a monad most appropriate?

M2. Which of the following is an appropriate explanation of the role of return, fmap, and join in the creation of monads?

Languages for Novices

N1. As the presenters suggested, different novice languages have different audiences. Which of the following language/audiences pairs does not match?

N2. Which of the following statements about Alice is false?