Functional Languages

Prev: Data Abstraction and Object Orientation Next: Logic Languages

11.2-11.3 Check Your Understanding

1. What mathematical formalism underlies functional programming?
2. List several distinguishing characteristics of functional programming languages.
3. Briefly describe the behavior of the Lisp/Scheme read-eval-print loop.
4. What is a first-class value?
5. Explain the difference between let, let*, and letrec in Scheme.
6. Explain the difference between eq?, eqv?, and equal?.
7. Describe three ways in which Scheme programs can depart from a purely functional programming model.
8. What is an association list?
9. What does it mean for a language to be homoiconic?
10. What is an S-expression?
11. Outline the behavior of eval and apply.

11.4 Check Your Understanding

12. Why does OCaml provide separate arithmetic operators for integer and floating-point values?
13. Explain the difference between physical and structural equality of values in OCaml.
14. How do lists in OCaml differ from those of Lisp and Scheme?
15. Identify the values that OCaml treats as mutable.
16. List three contexts in which OCaml performs pattern matching.
17. Explain the difference between tuples and records in OCaml. How does an OCaml record differ from a record (structure) in languages like C or Pascal?
18. What are OCaml variants? What features do they subsume from imperative languages such as C and Pascal?

11.5-11.8 Check Your Understanding

19. What is the difference between normal-order and applicative-order evaluation? What is lazy evaluation?
20. What is the difference between a function and a special form in Scheme?
21. What does it mean for a function to be strict?
22. What is memoization?
23. How can one accommodate I/O in a purely functional programming model?
24. What is a higher-order function (also known as a functional form)? Give three examples.
25. What is currying? What purpose does it serve in practical programs?
26. What is the trivial update problem in functional programming?
27. Summarize the arguments for and against side-effect-free programming.
28. Why do functional languages make such heavy use of lists?

11.10 Exercises

1. Is the define primitive of Scheme an imperative language feature? Why or why not?
2. It is possible to write programs in a purely functional subset of an imperative language such as C, but certain limitations of the language quickly become apparent. What features would need to be added to your favorite imperative language to make it genuinely useful as a functional language? Hint: What does Scheme have that C lacks?
3. Explain the connection between short-circuit Boolean expressions and normal-order evaluation. Why is cond a special form in Scheme, rather than a function?
4. Write a program in your favorite imperative language that has the same input and output as the Scheme program of Figure 11.1. Can you make any general observations about the usefulness of Scheme for symbolic computation, based on your experience?
5. Suppose we wish to remove adjacent duplicate elements from a list (e.g., after sorting). The following Scheme function accomplishes this goal:

(define unique
  (lambda (L)
    (cond
      ((null? L) L)
      ((null? (cdr L)) L)
      ((eqv? (car L) (car (cdr L))) (unique (cdr L)))
      (else (cons (car L) (unique (cdr L)))))))

Write a similar function that uses the imperative features of Scheme to modify L “in place,” rather than building a new list. Compare your function to the code above in terms of brevity, conceptual clarity, and speed. 6. Write tail-recursive versions of the following:

;; (a) compute integer log, base 2
;; (number of bits in binary representation)
;; works only for positive integers
(define log2
  (lambda (n)
    (if (= n 1) 1 (+ 1 (log2 (quotient n 2))))))
 
;; (b) find minimum element in a list
(define min
  (lambda (l)
    (cond
      ((null? l) '())
      ((null? (cdr l)) (car l))
      (#t (let ((a (car l))
                (b (min (cdr l))))
            (if (< b a) b a))))))

7. Write purely functional Scheme functions to (a) return all rotations of a given list. For example, (rotate '(a b c d e)) should return ((a b c d e) (b c d e a) (c d e a b) (d e a b c) (e a b c d)) in some order. (b) return a list containing all elements of a given list that satisfy a given predicate. For example, (filter (lambda (x) (< x 5)) '(3 9 5 8 2 4 7)) should return (3 2 4).
8. Write a purely functional Scheme function that returns a list of all permutations of a given list. For example, given (a b c), it should return ((a b c) (b a c) (b c a) (a c b) (c a b) (c b a)) in some order.
9. Modify the Scheme program of Figure 11.1 or the OCaml program of Figure 11.3 to simulate an NFA (nondeterministic finite automaton), rather than a DFA. The distinction between these automata is described in Section 2.2.1. Since you cannot “guess” correctly in the face of a multivalued transition function, you will need either to use explicitly coded backtracking to search for an accepting series of moves (if there is one), or keep track of all possible states that the machine could be in at a given point in time.
10. Consider the problem of determining whether two trees have the same fringe: the same set of leaves in the same order, regardless of internal structure. An obvious way to solve this problem is to write a function flatten that takes a tree as argument and returns an ordered list of its leaves. Then we can say

(define same-fringe
  (lambda (T1 T2)
    (equal (flatten T1) (flatten T2))))

Write a straightforward version of flatten in Scheme. How efficient is same-fringe when the trees differ in their first few leaves? How would your answer differ in a language like Haskell, which uses lazy evaluation for all arguments? How hard is it to get Haskell’s behavior in Scheme, using delay and force? 11. In Example 11.59 we showed how to implement interactive I/O in terms of the lazy evaluation of streams. Unfortunately, our code would not work as written, because Scheme uses applicative-order evaluation. We can make it work, however, with calls to delay and force.

Suppose we define input to be a function that returns an “istream” a promise that when forced will yield a pair, the cdr of which is an istream:

(define input (lambda () (delay (cons (read) (input)))))

Now we can define the driver to expect an “ostream” an empty list or a pair, the cdr of which is an ostream:

(define driver
  (lambda (s)
    (if (null? s) '()
        (display (car s))
        (driver (force (cdr s))))))

Note the use of force.

Show how to write the function squares so that it takes an istream as argument and returns an ostream. You should then be able to type (driver (squares (input))) and see appropriate behavior. 12. Write new versions of cons, car, and cdr that operate on streams. Using them, rewrite the code of the previous exercise to eliminate the calls to delay and force. Note that the stream version of cons will need to avoid evaluating its second argument; you will need to learn how to define macros (derived special forms) in Scheme. 13. Write the standard quicksort algorithm in Scheme, without using any imperative language features. Be careful to avoid the trivial update problem; your code should run in expected time n log n.

Rewrite your code using arrays. You will probably need to consult a Scheme manual for further information. Compare the running time and space requirements of your two sorts. 14. Write insert and find routines that manipulate binary search trees in Scheme. Consult an algorithms text if you need more information. Explain why the trivial update problem does not impact the asymptotic performance of insert. 15. Write an LL(1) parser generator in purely functional Scheme. If you consult Figure 2.24, remember that you will need to use tail recursion in place of iteration. Assume that the input CFG consists of a list of lists, one per nonterminal in the grammar. The first element of each sublist should be the nonterminal; the remaining elements should be the right-hand sides of the productions for which that nonterminal is the left-hand side. You may assume that the sublist for the start symbol will be the first one in the list. If we use quoted strings to represent grammar symbols, the calculator grammar of Figure 2.16 would look like this:

'(("program" ("stmt_list" "$$"))
  ("stmt_list" ("stmt" "stmt_list") ())
  ("stmt" ("id" ":=" "expr") ("read" "id") ("write" "expr"))
  ("expr" ("term" "term_tail"))
  ("term" ("factor" "factor_tail"))
  ("term_tail" ("add_op" "term" "term_tail") ())
  ("factor_tail" ("mult_op" "factor" "factor_tail") ())
  ("add_op" ("+") ("-"))
  ("mult_op" ("*") ("/"))
  ("factor" ("id") ("number") ("(" "expr" ")")))

Your output should be a parse table that has this same format, except that every right-hand side is replaced by a pair (a 2-element list) whose first element is the predict set for the corresponding production, and whose second element is the right-hand side. For the calculator grammar, the table looks like this:

(("program" (("$$" "id" "read" "write") ("stmt_list" "$$")))
 ("stmt_list"
  (("id" "read" "write") ("stmt" "stmt_list"))
  (("$$") ()))
 ("stmt"
  (("id") ("id" ":=" "expr"))
  (("read") ("read" "id"))
  (("write") ("write" "expr")))
 ("expr" (("(" "id" "number") ("term" "term_tail")))
 ("term" (("(" "id" "number") ("factor" "factor_tail")))
 ("term_tail"
  (("+" "-") ("add_op" "term" "term_tail"))
  (("$$" ")" "id" "read" "write") ()))
 ("factor_tail"
  (("*" "/") ("mult_op" "factor" "factor_tail"))
  (("$$" ")" "+" "-" "id" "read" "write") ()))
 ("add_op" (("+") ("+")) (("-") ("-")))
 ("mult_op" (("*") ("*")) (("/") ("/")))
 ("factor"
  (("id") ("id"))
  (("number") ("number"))
  (("(") ("(" "expr" ")"))))

Hint: You may want to define a right_context function that takes a nonterminal B as argument and returns a list of all pairs (A, β), where A is a nonterminal and β is a list of symbols, such that for some potentially different list of symbols α, A -> α B β. This function is useful for computing FOLLOW sets. You may also want to build a tail-recursive function that recomputes FIRST and FOLLOW sets until they converge. You will find it easier if you do not include ε in either set, but rather keep a separate estimate, for each nonterminal, of whether it may generate ε. 16. Write an equality operator (call it =/) that works correctly on the yearday type of Example 11.38. You may need to look up the rules that govern the occurrence of leap years. 17. Create addition and subtraction functions for the celsius and fahrenheit temperature types introduced in Sidebar 11.3. To allow the two scales to be mixed, you should also define conversion functions ct_of_ft : fahrenheit_temp -> celsius_temp and ft_of_ct : celsius_temp -> fahrenheit_temp. Your conversions should round to the nearest degree; half degrees round up. 18. We can use encapsulation within functions to delay evaluation in OCaml:

type 'a delayed_list =
  Pair of 'a * 'a delayed_list
| Promise of (unit -> 'a * 'a delayed_list);;
 
let head = function
| Pair (h, r) -> h
| Promise (f) -> let (a, b) = f() in a;;
 
let rest = function
| Pair (h, r) -> r
| Promise (f) -> let (a, b) = f() in b;;

Now given

let rec next_int n = (n, Promise (fun() -> next_int (n + 1)));;
let naturals = Promise (fun() -> next_int (1));;

we have

head naturals;;                    (* => 1 *)
head (rest naturals);;             (* => 2 *)
head (rest (rest naturals));;      (* => 3 *)
...

The delayed list naturals is effectively of unlimited length. It will be computed out only as far as actually needed. If a value is needed more than once, however, it will be recomputed every time. Show how to use pointers and assignment (Example 8.42) to memoize the values of a delayed_list, so that elements are computed only once. 19. Write an OCaml version of Example 11.67. Alternatively, or in addition, solve Exercises 11.5, 11.7, 11.8, 11.10, 11.13, 11.14, or 11.15 in OCaml. 20. 11.20-11.23 In More Depth.