• Oct 6 - Adjusted description of faults/switch to be more clear. Clarified that faults/both returns the intersection.
• Oct 5 - Added missing '() in Part C example. Clarified that no laws are needed for problem 19. Clarified that you can assume ordered-by? is a total order.
• Oct 3 - Replaced faults-not-equal by faults/not-equal. Clarified that all faults/x methods return functions.

Higher-order functions are a cornerstone of functional programming. And they have migrated into all of the web/scripting languages, including JavaScript, Ruby, and Python. This assignment will help you incorporate first-class and higher-order functions into your programming practice.

This project uses the same μScheme interpreter as from Homework 3. There is no code skeleton for this project. By now, you should know where to put contracts, algebraic laws, and tests.

• Do not use any imperative features. Banish set, while, print, println, printu, and begin from your vocabulary!.
• Except for the one exception mentioned explicitly below, no code may compute the length of a list.
• Except as noted below, do not define helper functions at top level. Instead, use let or letrec to define helper functions. When you do use let to define inner helper functions, avoid passing as parameters values that are already available in the environment.
• Each named internal function written with lambda should be accompanied by a contract, but internal functions cannot be unit-tested. (Anonymous lambda functions need not have contracts.)
• Your solutions must be valid μScheme. In particular, they must pass the following test: /comp/105/bin/uscheme -q < myfilename > /dev/null without any error messages or unit-test failures. If your file produces error messages, we won’t test your solution and you will earn No Credit for functional correctness.
• As usual, every function should be accompanied by a short contract, unit tests, and, if it does case analysis, algebraic laws.

Answer these questions before starting the rest of the assignment.

1. Review Sections 2.7.2, 2.8.1, and 2.8.2. Now consider each of the following functions: map filter exists? all? curry uncurry foldl foldr. Put each function into exactly one of the following four categories:

   (B) Always returns a Boolean
   (F) Always returns a function
   (L) Always returns a list
   (A) Can return anything (including a Boolean, a function, or a list)

2. For the same functions as question 1, say which of the following five categories best describes it. Pick the most specific category (e.g., (S) is more specific than (L) or (M), and all of these are more specific than (?)).

   (S) Takes a list & a function; returns a list of exactly the same size
   (L) Takes a list & a function; returns a list of at least the same size
   (M) Takes a list & a function; returns a list of at most the same size
   (?) Might return a list
   (V) Never returns a list

3. For the same functions as question 1, put each function into exactly one of the following categories. Always pick the most specific category (e.g. (F2) is more specific than (F)).

   (F) Takes a single argument: a function
   (F2) Takes a single argument: a function that itself takes two arguments
   (+) Takes more than one argument

4. Review the difference between foldr and foldl in section 2.8.1. You may also find it helpful to look at their implementations in section 2.8.3, which starts on page 135; the implementations are at the end.

   1. Do you expect (foldl + 0 '(1 2 3)) and (foldr + 0 '(1 2 3)) to be the same or different?

   2. Do you expect (foldl cons '() '(1 2 3)) and (foldr cons '() '(1 2 3)) to be the same or different?

   3. Look at the initial basis, which is summarized on 161. Give one example of a function, other than + or cons, that can be passed as the first argument to foldl or foldr, such that foldl always returns exactly the same result as foldr.

   4. Give one example of a function, other than + or cons, that can be passed as the first argument to foldl or foldr, such that foldl may return a different result from foldr.

5. Review function composition and currying, as described in section 2.7.2, which starts on page 130. Then judge the proposed properties below, which propose equality of functions, according to these rules:

   • Assume that names curry, o, <, *, cons, even?, and odd? have the definitions you would expect, but that m may have any value.

   • Each property proposes to equate two functions. If the functions are equal—which is to say, when both sides are applied to an argument, they always produce the same result—then mark the property Good. But if there is any argument on which the left-hand side produces different results from the right, mark the property Bad.

   Mark each property Good or Bad:

   ((curry <) m)     == (lambda (n) (< m n))
   
   ((curry <) m)     == (lambda (n) (< n m))
   
   ((curry cons) 10) == (lambda (xs) (cons 10 xs))
   
   (o odd?  (lambda (n) (* 3 n))) == odd?
   
   (o even? (lambda (n) (* 4 n))) == even?

• Do problem 14(e) on page 195 of the textbook. For this problem and the remaining parts of problem 14 listed next, you must not use recursion, and you need not write algebraic laws.
• Do problem 14(b) on page 195 of the textbook.
• Do problem 14(h) on page 195 of the textbook.
• Do problem 14(j) on page 195 of the textbook.
• Use foldl or foldr to implement map and filter. It is OK if some of these functions do a bit more work than their official versions, as long as they produce the same answers. Call your versions my-map and my-filter. You need not write algebraic laws.
• Do problems 19(a)-(c) on page 198 of the textbook. In part (c), your add-element function must take two parameters: the element to be added as the first parameter and the set as the second parameter. When you code part (c), compare values for equality using the equal? function. To help you design part (c), put comments in your source code that complete the right-hand sides of the following properties:

  (member? x (add-element x s)) == ...
  (member? x (add-element y s)) == ..., where (not (equal? y x))
  (member? x (union s1 s2))     == ...
  (member? x (inter s1 s2))     == ...
  (member? x (diff  s1 s2))     == ...

  The properties are not quite algorithmic, but they should help anyway. You do not need to write laws for these problems; the comments with the properties are enough.

• Using the entire nine-step design process (including developing algebraic laws), Define a function (ordered-by? precedes?) that takes a comparison function precedes? and returns a function that, given a list, returns #t if the list is totally ordered by precedes?, and #f otherwise. Hint: Here is an inductive definition of a list that is ordered by precedes?:

  • The empty list is ordered by precedes?.
  • A singleton list (a list of length one) is ordered by precedes?.
  • (cons x (cons y zs)) is ordered by precedes? if (precedes? x y) and (cons y zs) is ordered by precedes?.
  Here are some examples:

    -> ((ordered-by? <) '(1 2 3))
    #t
    -> ((ordered-by? <=) '(1 2 3))
    #t
    -> ((ordered-by? <) '(3 2 1)) 
    #f
    -> ((ordered-by? >=) '(3 2 1))
    #t
    -> ((ordered-by? >=) '(3 3 3))
    #t
    -> ((ordered-by? =) '(3 3 3)) 
    #t

  More hints: For the code itself, you will need letrec. We recommend that your submission include the following unit tests, which help ensure that your function has the correct name and takes the expected number of parameters.

  (check-assert (procedure? ordered-by?))
  (check-assert (procedure? (ordered-by? <)))
  (check-error (ordered-by? < '(1 2 3)))

  You can assume that ordered-by? is a total order (reflexive, anti-symmetric, transitive, and defined on all pairs of elements).
• Using the calculational techniques from Section 2.4.7, which starts on page 115, prove that

      (o ((curry map) f) ((curry map) g)) == ((curry map) (o f g))

  To prove two functions equal, prove that when applied to equal arguments, they return equal results.

In this part of the homework, you will use higher-order functions to develop an embedded domain-specific language (EDSL) for validating submitted web forms. For example here is a (fake!) web form:

If this web form were real, then when you clicked on the Submit button, the data you filled in to the form would be sent to the web server. For this problem, we will assume that the web server is running µScheme, and that form values are translated into association lists (recall these are lists of key-value pairs), where the keys are the form fields and the values are those entered in the form. For example, for the above form, one such value might be:

(val sample-response
  '([purpose course]
    [building h]
    [room 209]
    [start-time 2000]
    [end-time 2030]
    [info (COMP 105 study group.)]))

The above value is sensible, but what if someone fills out the form incorrectly? For example, among other things, they might forget to select a purpose, they might enter a non-existent room number, or they might choose an end time that's before the start time. (Ignore the fact that the form doesn't specify a date!)

Thus, most web servers will validate form submissions before preceding further. Validation both checks that the submitted form fields are sensible and, if not, indicates the faults: which fields failed validation. The EDSL you develop will let you write validators like the following, which checks some of the key properties for our example:

(val reservation-checker
  (faults/switch 'building
    (bind #f (faults/always 'building)
       (bind 'h (faults/both
                    (faults/not-equal 'room 102)
                    (faults/not-equal 'room 209))
         (bind 'robn (faults/not-equal 'room 253) '())))))

Here, reservation-checker checks the following (in order from top to bottom). If building is empty (#f), validation always fails. If building is 'h, then validation fails if the 'room is neither 102 nor 209. If building is 'robn then validation fails if the 'room is not 253.

reservation-checker is itself a function that takes a response (like sample-response) and returns a list of faults, which are symbols that capture for the fields that failed validation. For example, if it returns '(building room) that indicates those two fields are bad, and if it returns '() that indicates the submitted form was valid.

Your job is to implement several functions that, together, form an EDSL for writing validators. Here are the functions you must write:

• (faults/none) returns a validator that takes a response and always returns the empty list of faults.
• (faults/always F) returns a validator that takes a response and always returns a singleton list of faults containing F (which you can assume is a symbol).
• (faults/equal k v) returns a validator that takes a response and returns a singleton list containing k if k is bound to v in the response. Otherwise, the validator returns the empty list of faults.
• (faults/not-equal k v) returns a validator that takes a response and returns a singleton list containing k if k is not bound to v in the response. Otherwise, the validator returns the empty list of faults.
• (faults/both v1 v2) takes two validators v1 and v2 and returns a new validator that checks for all the faults found by both v1 and v2 (i.e., the intersection of their faults), returning any such faults together in a single list.
• (faults/switch k table) takes a key k and a validator table table, which is an association list that maps values to validators. It returns a validator v that looks up k in the response and finds its corresponding value k'. It then looks up k' in the validator table and runs the corresponding validator, returning the list of faults found by that validator. If there is no such validator, then v returns the empty list. For example, reservation-checker uses faults-switch to create a validator that compares the 'building field to either #f, 'h, or 'robn and execute the corresponding validators. If passed 'brak (a building that's included in the form but is not checked in the validator), the validator always returns the empty list of faults.

Expectations for these functions:

• A fault list should not contain duplicates.
• Each function you write must be accompanied by algebraic laws and unit tests.

• Every analyzer must treat the response as an abstraction. An analyzer must never interrogate a response about its form of data; the analyzer should restrict itself to function find and possibly function bound-in?:

  (define bound-in? (key pairs)
    (if (null? pairs)
        #f
        (|| (= key (alist-first-key pairs))
            (bound-in? key (cdr pairs)))))

• To avoid conflicts with the set code in exercise 19, you are welcome to use the following template to define faults/both (though note faults/both should do intersection, not union):

  (val faults/both
     (let* ([member?  (lambda (x s) (exists? ((curry =) x) s))]
            [add-elem (lambda (x s) (if (member? x s) s (cons x s)))]
            [union    (lambda (faults1 faults2) (foldr add-elem faults2 faults1))])
        ...))

• A cqs.hofs.txt containing your answers to the reading-comprehension questions.
• A pdf file semantics.pdf containing your calculational proof (last problem of Part B).
• A file solution.scm containing your programming solutions.You must precede each solution by a comment that looks like something like this:

      ;;
      ;; Problem A
      ;;