CIS 554 -- Final Exam Name __________________________________

Read each question carefully. Keep answers short and to the point. Do not provide any information that was not asked for; you may lose points that way.

  1. (50 points) Complete the following definitions as precisely as you can. Use one sentence, do not give examples.

    1.  In resolution theory, a clause is...

    2. A homoiconic language is...

    3. A language is Turing complete if...

    4. A persistent data structure is...

    5. A lazy data structure is...

    6. Metaprogramming is...

    7. A collection of values of type A is covariant if...

    8. Dynamic typing is...

    9. A closure is...

    10. An actor is...

  2. (5 points) What did Tony Hoare refer to as his "billion dollar mistake"?

  3. (5 points) Of the languages that we have studied,
    1. Which language had the simplest syntax?

    2. As briefly as possible, describe that syntax.

  4. (5 points) In symbols rather than words, what is the resolution principle?

  5. (5 points) Unification is an essential operation in Prolog. For each of the following, tell (1) whether the two expressions can be unified (answer "yes" or "no"), and (2) if "yes," what values are given to each of the variables. (Remember, variables begin with a capital letter.)
    1. mother(john, Dick) = mother(Jack, richard)
    2. mother(tom, Dick) = mother(Dick, harry)
    3. Me = grandpaw(Me, myself)

  6. (4 points) Here is some code from one of my REBOL programs:
         last-part:  last  split-path  pick  image-files  n  clear  find  last-part  #"."
    where last, split-path and clear are functions that take a single argument, pick and find are functions that take two arguments, and image-files and n are data values. Add parentheses to this line to make the structure explicit.

  7. (6 points)
    1. Give one reason for claiming that REBOL is a functional language.

    2. Give one reason for claiming that REBOL is not a functional language.

  8. (5 points) Give two examples of a monad in Scala.

  9. (2 points) We have studied two domain-specific languages. One of them was Graphviz. What was the other one?

  10. (3 points) Using an example, write a description of currying.

  11. (5 points) Suppose you have a program to evaluate a large variety of algebraic expressions. Because algebraic expressions can be nested, the methods that do the evaluations must be recursive.

    1. What would be the advantage of writing these methods to be tail recursive?

    2. In addition to being a little extra effort, what would be the disadvantage of writing them to be tail recursive?

    3. Should you write these methods in a tail-recursive fashion? Why or why not?

  12. (5 points) In any functional language, lists are much more important than arrays, and are used much more often. Why?