This assignment is all individual work. There is no pair programming.

Overview

Higher-order functions are a cornerstone of functional programming. They are found in all of the web/scripting languages, including JavaScript, Python, Perl, and Lua. This assignment will help you incorporate first-class and higher-order functions into your programming practice. You will use existing higher-order functions, define higher-order functions that consume functions, and define higher-order functions that return functions. The assignment builds on what you’ve already done, and it adds new ideas and techniques that are described in sections 2.7, 2.8, and 2.9 of Build, Prove, and Compare.

Setup

The executable μScheme interpreter is in /comp/105/bin/uscheme; if you are set up with use comp105, you should be able to run uscheme as a command. The interpreter accepts a -q (“quiet”) option, which turns off prompting. Your homework will be graded using uscheme. When using the interpreter interactively, you may find it helpful to use ledit, as in the command

  ledit uscheme

We don’t give you a template—by this time, you know how to identify solutions and where to put contracts, algebraic laws, and tests.

Dire Warnings

The μScheme programs you submit must not use any imperative features. Banish set, while, print, println, printu, and begin from your vocabulary! If you break this rule for any exercise, you get No Credit for that exercise. You may find it useful to use begin and println while debugging, but they must not appear in any code you submit. As a substitute for assignment, use let or let*.

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. (An example of what to avoid appears under “Avoid common mistakes” below.)

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. (You can still earn credit for structure and organization). If your file includes failing unit tests, you might possibly get some credit for functional correctness, but we cannot guarantee it.

Every function should be accompanied by a short contract and by unit tests. If the function does case analysis, it must also be accompanied by algebraic laws. Submissions without algebraic laws will earn No Credit.

We will evaluate functional correctness by testing your code extensively. Because this testing is automatic, each function must be named be exactly as described in each question. Misnamed functions earn No Credit.

Reading comprehension

Before starting the programming problems, answer the reading-comprehension questions for this module, which you will find online. It is also OK to alternate between reading-comprehension questions and related homework questions.

Programming and Proof

Overview

For this assignment, you will do Exercises 28 (b, e, f), 29 (a, c), 30, and 38, from pages 186 to 189 of Build, Prove, and Compare, plus the exercises F, M, O, and V below.

A summary of μScheme’s initial basis can be found on page 99. While you’re working on this homework, keep it handy.

Each top-level function you define must be accompanied by a contract and unit tests. 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.) Algebraic laws are required only where noted below; each problem is accompanied by a Laws section, which says what is needed in the way of algebraic laws.

Book problems

(check-assert (function? set-ops-from))
(check-assert (set-ops? (set-ops-from =)))

(val atom-set-ops     (set-ops-from =))
(val atom-emptyset    (set-ops-emptyset    atom-set-ops))
(val atom-member?     (set-ops-member?     atom-set-ops))
(val atom-add-element (set-ops-add-element atom-set-ops)) 
(val atom-union       (set-ops-union       atom-set-ops))
(val atom-inter       (set-ops-inter       atom-set-ops))
(val atom-diff        (set-ops-diff        atom-set-ops))

A function that returns a function

Calculational reasoning about functions

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

Ordered lists

-> ((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

A domain-specific language for input validation

In this part of the homework, you will use higher-order functions to develop an embedded domain-specific language for validating web-form submissions.⁴ For example, here is a version of the web form on the CS 105 regrades page (but this version is not connected to anything):

In a real form, clicking on the Submit button sends data to the server, and that data has to be validated. For example, if the form asks for a grade to be reviewed, it must specify an assignment. (To try our validator for yourself, go to the course regrade form at https://www.cs.tufts.edu/comp/105/regrade, and click the Submit button without filling in the form.) Our validator checks the form’s input using higher-order functions, and for problem V below, you will define similar functions.

Representation of form data and validation results

When form data reaches the server, it is turned into an association list, which we call a response. In the response, each key names a field of the form; the key is represented by a symbol. The key is bound to the value the user responded with. If the user did not supply a value, the key is bound to the value #f. Here’s an example response, representing a student who wants something regraded because they accidentally submitted the wrong PDF:

(val sample-response
  '([why badsubmit]
    [badsubmit_asst scheme]
    [info (I accidentally submitted the opsem PDF again.)]
    [badgrade_asst ...]
    [problem #f]))

But what if they say they submitted the wrong PDF, but they forgot to say what assignment? The validator needs to identify such faults. For our purposes, a fault is simply a μScheme symbol that identifies a bad input. And a validator is a function that takes a response and returns a list of faults (without duplicates):

A language of validators

The key idea behind the validator functions—what makes them a “domain-specific language” and not just another API—is composition: you define functions that build validators from other validators. The functions are specified using these metavariables:

• F, a fault (a symbol)
• k, a key (also a symbol)
• v, a value
• V₁ and V₂, validators
• t, a validator table, which is an association list that maps values to validators

Here are the specifications:

• (faults/none) returns a validator that takes a response and always returns the empty list of faults, no matter what is in the response.

  

• (faults/always F) returns a validator that takes a response and always returns a singleton list containing the fault F, no matter what is in the response.

  

• (faults/equal k v) returns a validator that takes a response and if k is bound to v in the response, returns a singleton list containing k. If k is not bound to v in the response, the validator returns the empty list of faults.

  

• (faults/both V₁ V₂) returns a new validator that combines checks from the two validators V₁ and V₂. The faults/both validator returns a single list of faults that is formed by taking the union of the faults from V₁ with the faults from V₂ (with no duplicates).

  

• (faults/switch k t) returns a validator that validates the response using a validator selected from validator table t: the value of k in the response is a key used to find a validator in t.

  

  The use case for faults/switch is to create a validator that uses some of the input data to figure out how to validate the rest, and the validator table is like the list of cases in a C switch statement: each case is labeled with a value, and the action to be performed in that case is itself a validator. There’s an example below.

  The contract of faults/switch is hard to write in informal English: “Key k determines which field of the response is used to make a decision. When the validator is given a response, the value v associated with key k in the response is looked up in the validator table, and the resulting validator is used to find faults in the response.” We’re actually better off documenting the function with an algebraic law. In a language like Lua, Python, or JavaScript, where table lookup is primitive, I might write the essential part of an algebraic law like this:

  faults_switch(k, t)(response) == t[response[k]](response)

  When you write your algebraic laws, you will notate a similar computation in μScheme.

An example validator

To illustrate the use of the validator functions, here is some code for the regrade validator. It will help to know that it uses these faults:

• nobutton if no radio button was selected
• problem if “review my grade” was selected but the “problem” field was blank
• badsubmit_asst if “I submitted the wrong PDF” was selected but the “assignment” dropdown was left at “...”
• recitation if “I attended this recitation” was selected but the date or leaders were left blank

If the regrade validator were written in μScheme, it might look like this:

(val regrade-validator  ;; example for the regrade form
  (faults/switch 'why
    (bind         'photo
                  (faults/none)
      (bind       'badsubmit
                   (faults/both (faults/equal 'badsubmit_asst '...)
                                (faults/equal 'info #f))
        (bind     'badgrade
                  (faults/both
                      (faults/equal 'badgrade_asst '...)
                      (faults/both
                         (faults/equal 'info #f)
                         (faults/equal 'problem #f)))
          (bind   'recitation
                  (faults/both
                      (faults/equal 'date #f)
                      (faults/equal 'leaders #f))

            (bind '#f
                  (faults/always 'nobutton)
                  '())))))))

For example, if I submit a photo for regrade, faults/switch figures out that no more validation is required. But if I select “review my grade” (badgrade), faults/switch figures out that we need an assignment (badgrade_asst), an explanation (info) and a problem number (problem). If I leave all these fields blank, the validator will return a fault list containing symbols problem, badgrade_asst, and info, like this one:

'(problem badgrade_asst info)

If I leave only one or two of these fields blank, the validator will return a fault list identifying those fields.

You can use this validator to test your functions with some integration tests.

At last, your assigned problem

(val the-fault list1) ; build a singleton fault set
(val no-faults ’())   ; an empty fault set

; ((faults/none) response) == no-faults
(define faults/none ()
    ...)

; ((faults/always f) response) == (the-fault f)
(define faults/always (f)
    ...)

; ... law or laws for faults/equal ...
(define faults/equal (key value)
    ...)

; ... law or laws for faults/both ...
(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))])
    ...))

; ... law or laws for faults/switch ...
(define faults/switch (key validators)
    ...)

Extra credit

What and how to submit

You must submit three files:

• A README file containing
  • The names of the people with whom you collaborated
  • A list identifying which problems you solved
  • A note identifying any extra-credit work you did (Please use the words “extra credit” somewhere in your README.)

• A PDF file semantics.pdf containing the solutions to Exercise M. If you already know LaTeX, by all means use it. Otherwise, write your solution by hand and scan it. Do check with someone else who can confirm that your work is legible—if we cannot read your work, we cannot grade it.

• A file solution.scm containing the solutions to Exercises 28 (b, e, f), 29 (a, c), 30, 38, F, O, and V

  Each solution must be preceded by a comment that looks like something like this:

      ;;
      ;; Problem 28
      ;;

If you complete the extra-credit exercise VX, you must submit it separately:

• Optionally, a PDF file extra.pdf containing solutions to extra credit exercise VX

As soon as you have the files listed above, run submit105-hofs to submit a preliminary version of your work. Keep submitting until your work is complete; we grade only the last submission.

Avoid common mistakes

Listed below are some common mistakes, which we encourage you to avoid.

    (define sum-upto (n)
      (letrec ([sigma (lambda (m n) ;;; UGLY CODE
                         (if (> m n) 0 (+ m (sigma (+ m 1) n))))])
         (sigma 1 n)))

    (define sum-upto (n)
      (letrec ([sum-from (lambda (m) ;;; BETTER CODE
                         (if (> m n) 0 (+ m (sum-from (+ m 1)))))])
         (sum-from 1)))

How your work will be evaluated

Structure and organization

The criteria in the general coding rubric apply. As always, we emphasize contracts and naming. In particular, unless the contract is obvious from the name and from the names of the parameters, an inner function defined with lambda and a let form needs a contract. (An anonymous lambda that is returned from a function like faults/both does not need a contract—the behavior of that lambda is part of the contract of the function that returns it.)

There are a few new criteria related to let, lambda, and the use of basis functions. The short version is use the functions in the initial basis; except when we specifically ask you to, don’t redefine initial-basis functions.

Functional correctness

In addition to the usual testing, we want appropriate list operations to take constant time.

Proofs and inference rules

For your calculational proof, use induction correctly and exploit the laws that are proved in the book.