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
      a ∨ ¬b

    2. a ∧ b ⇒ c
      ¬a ∨ ¬b ∨ c

  2. (4 points each) Short answer:

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

      Once a fact is proven true, it remains true forever

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

      Forward reasoning would lead to a combinatorial explosion of clauses

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

      A way of thinking about solving a problem

  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]
      A = a, B = b, C = 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])
      M = 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)

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

    3.  loves(john, mary) ∨  loves(mary, john)
      ¬loves(john, mary) ∨ ¬loves(mary, john)
          Any of:
              loves(john, mary) ∨ ¬loves(john, mary)
              loves(mary, john) ∨ ¬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.)

        Use filter to get a list of only those 3-tuples where the occupation is "plumber"
        then use map to convert the list into (name, phone number) 2-tuples

  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?
         Scala, Option with Some(value) or None; or
        Haskell, Maybe with Just(value) or Nothing
    (One point deducted if both were given)

  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)?

      Actors are send messages containing data; agents are sent functions to execute

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

      The order in which they are received

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

      If one process dies, the other is sent a "kill" message (and dies, unless it is a System process)

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

      Its lexical scope, plus any functions that are called (at any depth) from within the lexical scope

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

      When there is little contention for access to shared memory

    6. What is the distinction between parallelism and concurrency?

      Parallelism is a hardware term, meaning simultaneous execution
      Concurrency is a software term, meaning asynchronous (possibly simultaneous) execution

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

      The signal is automatically passed through a function, yielding a new signal

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

      The invention of the null reference
      (1 point deducted if you thought this was invented for Java)

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

      Companion objects

    10. What does the zip function do?

      Combines two lists into a list of two-tuples

  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?

      Type inferencing ("types" isn't enough)

    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?

      bind, or >>=

    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?

      referential transparency

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

      Prolog and Clojure

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

      Clojure and Scala

    8. When are calls to a macro evaluated?

      At compile time

    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.

    def factorial(n: Int, acc: Int = 1) = if (n == 1) 1 else factorial(n - 1, n * acc)