CIS 554 -- Final Exam Name __________________________________

Read each question carefully. Keep answers short and to the point. When asked for a "Short answer," please try to keep your answer to ten words or fewer. Do not provide any information that was not asked for; you may lose points that way. (106 points total.)

  1. (4 points) Rewrite each of the following as a clause, using logic (not Prolog) notation.

    1. a b

    2. a ∧ b ⇒ c

  2. (4 points each) Short answer:

    1. What does it mean to say that a logical system is monotonic?

    2. Why does Prolog use backward reasoning rather than forward reasoning?

    3. What, in the context of this course, is a paradigm?

  3. (8 points) For each of the following attempted unifications (=), if the unification succeeds, tell what is unified with each variable (it may be more than one thing), else write "fail." (Variables are denoted by capital letters.)

    1. [A, b, C] = [a, B, c]

    2. [E, f, g] = [g, E, F]

    3. foo(J, k, L) = foo(l, J, k)

    4. bar(M, N, O) = bar(N, O, [p])

  4. (4 points) Suppose member is defined as:

         member(H, [H | T]).
         member(H, [_ | T] :- member(H, T).

    1. Can member be used to check if a number is in a nonempty list of numbers?

    2. Can member be used to get a number from a nonempty list of numbers?

    3. Can member be used to construct a list containing a number?

    4. Can member called with a nonempty list as its second argument?

  5. (6 points) Resolve each of the following pairs of clauses, if possible, else write "fail."

    1. loves(john, mary) ∨ loves(mary, john)
      loves(bill, mary) ∨ loves(mary, john)

    2. loves(john, mary) ∨  loves(mary, john)
      loves(bill, mary) ∨ ¬loves(mary, john)

    3.  loves(john, mary) ∨  loves(mary, john)
      ¬loves(john, mary) ∨ ¬loves(mary, john)

  6. (3 points) You have a list of (name, occupation, phone number) tuples. You wish to find the names and phone numbers of all the plumbers. What higher-order methods would you apply, and in what order? (Briefly describe any intermediate values.)

  7. (3 points) Haskell and Scala each use a monad to avoid having to use a null value. In either language (not both), what is this monad called, and what are its possible values?
  8. (4 points) The following picture represents a sorted binary tree (treeA). We wish to construct a new sorted binary tree, treeB, that holds the same values as treeA, but also holds the value 18. If persistent storage is used, draw what must be added to treeA to produce treeB.

  9. (4 points each) Short answer:

    1. What is the primary difference between an actor (Erlang) and an agent (Clojure)?

    2. What determines the order in which an actor processes the messages in its mailbox?

    3. What does it mean to say that two Erlang processes are linked?

    4. With dynamic scoping, what is the scope of a variable?

    5. Under what circumstances does Software Transactional Memory run much faster than a similar program using shared storage?

    6. What is the distinction between parallelism and concurrency?

    7. What does it mean to lift a signal (Elm)"

    8. What did Tony Hoare refer to as his "billion-dollar mistake"?

    9. What does Scala use to replace Java's static?

    10. What does the zip function do?

  10. (2 points each) Very short answer, often just one word:

    1. What is it called when a function keeps a record of previously computed values, in case they are needed again?

    2. What does "Hindley-Milner" refer to in Haskell and Scala?

    3. In Haskell, we use an operator to take a “state of the world” resulting from one function, and pass it into the next function. What is this operator called?

    4. What commonly used higher-order function has the type (a → b) → [a] → [b] ?

    5. When data is immutable, the substitution rule applies: Any variable or function call may be replaced by its value. What is another term for this property?

    6. What language or languages have we covered that are homoiconic?

    7. What language or languages have we covered that execute on the JVM?

    8. When are calls to a macro evaluated?

    9. What do you call a data structure in which parts of it don't exist until they are accessed?

  11. (4 points) Using any convenient syntax, write a tail recursive version of the factorial function. You may use two parameters.