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

# Overview

Higher-order functions are a cornerstone of functional programming. And they have migrated into 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 set you up with 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*`

.**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.

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. Submission 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 (10 percent)

Answer these questions before starting the rest of the assignment. As usual, you can download the questions.

The first step in this assignment is to learn the standard higher-order functions on lists, which you will use a lot. Suppose you need a list, or a Boolean, or a function—what can you call?

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)After each function, write (B), (F), (L), or (A):

`map filter exists? all? curry uncurry foldl foldr`

Here are the same functions again:

`map filter exists? all? curry uncurry foldl foldr`

For each function, 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 listAfter each function, write (S), (L), (M), (?), or (V):

`map filter exists? all? curry uncurry foldl foldr`

Here are the same functions again:

`map filter exists? all? curry uncurry foldl foldr`

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 argumentAfter each function, write (F), (F2), or (+):

`map filter exists? all? curry uncurry foldl foldr`

*You are now ready to tackle most parts of exercise 14.*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 133; the implementations are at the end.Do you expect

`(foldl + 0 '(1 2 3))`

and`(foldr + 0 '(1 2 3))`

to be the same or different?Do you expect

`(foldl cons '() '(1 2 3))`

and`(foldr cons '() '(1 2 3))`

to be the same or different?Look at the initial basis, which is summarized on 159. 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`

.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`

.

*You are now ready to tackle all parts of exercises 14 and 15.*Review the handout “Program Design with Higher-Order Functions”. The handout mentions a higher-order function

`flip`

, which can convert`<`

into`>`

, among other tricks. Write as many algebraic laws as are needed to specify`flip`

:Review function composition and currying, as described in section 2.7.2, which starts on page 128. 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?`

*You are now ready to tackle the first three parts of exercise 19, as well as problem***M**below.

# Programming and Proof (90 percent)

## Overview

For this assignment, you will do Exercises **14 (b-f,h,j)**, **15**, and **19**, from pages 212 to 216 of *Build, Prove, and Compare*, plus the exercises **A**, **F**, **G1**, **G2**, **G3**, **M**, and **O** below.

A summary of the initial basis can be found on page 159. A copy was handed out in class—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

**14**. *Higher-order functions*. Do exercise 14 on page 212 of *Build, Prove, and Compare*, parts (b) to (f), part (h), and part (j). Note which functions accept only *nonempty* lists, and code accordingly. **You must not use recursion—solutions using recursion will receive No Credit.** This restriction applies only to code you write. For example,

`gcd`

, which is defined in the initial basis, may use recursion.Because you are not defining recursive functions, you need not write any algebraic laws.

For this problem only, you may define *one* helper function at top level.

**Related reading**: For material on higher order functions, see sections 2.8.1 and 2.8.2 starting on page 131. For material on `curry`

, see section 2.7.2, which starts on page 128.

**Laws**: These functions must not be recursive, should not do any case analysis,^{1} and do not return functions. Therefore, no algebraic laws are needed.

**15**. *Higher-order functions*. Do exercise 15 on page 214. **You must not use recursion—solutions using recursion will receive No Credit.** As above, this restriction applies only to code you write.

Because you are not defining recursive functions, you need not write any algebraic laws.

For this problem, you get full credit if your implementations return correct results. You get *extra* credit^{2} if you can duplicate the behavior of `exists?`

and `all?`

exactly. To earn the extra credit, it must be impossible for an adversary to write a *μ*Scheme program that produces different output with your version than with a standard version. However, the adversary is not permitted to change the names in the initial basis.

**Related reading**: Examples of `foldl`

and `foldr`

are in sections 2.8.1 and 2.8.2 starting on page 131. You may also find it helpful to study the implementations of `foldl`

and `foldr`

in section 2.8.3, which starts on page 133; the implementations are at the end. Information on `lambda`

can be found in section 2.7, on pages 121 to 124.

**Laws**: These functions must not be recursive, should not begin with case analysis, and do not return functions. Therefore, no algebraic laws are needed.

**19**. *Functions as values*. Do exercise 19 on page 216 of *Build, Prove, and Compare*. **You cannot represent these sets using lists.** If any part of your code to construct or to interrogate a set uses `cons`

, `car`

, `cdr`

, or `null?`

, you are doing the problem wrong.

Do all four parts:

Parts (a) and (b) require no special instructions.

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.

In part (d), when you code the third approach to polymorphism, write a function

`set-ops-from`

which places your set functions in a record. To define record functions, use the syntactic sugar described in the book in Section 2.16.6 on page 194. In particular, be sure your code includes this record definition:`(record set-ops (empty member? add-element union inter diff))`

Code your solution to part (d) as a function

`set-ops-from`

, which will accept one argument (an equality predicate) and will return a record created by calling`make-set-ops`

. Your function might look like this:`(define set-ops-from (eq?) (let ([empty ...] [member? ...] [add ...] [union ...] [inter ...] [diff ...]) (make-set-ops empty member? add union inter diff)))`

Fill in each

`...`

with your own implementations. Each implementation is like one you wrote in part (c), except instead of using the predefined`equal?`

, it uses the parameter`eq?`

—that is what is meant by “the third approach to polymorphism.”No additional laws are needed for part (d).

To help you get part (d) right, we recommend that you use these unit tests:

```
(check-assert (procedure? set-ops-from))
(check-assert (set-ops? (set-ops-from =)))
```

And to write your own unit tests for the functions in part (d), you may use these definitions:

```
(val atom-set-ops (set-ops-from =))
(val atom-emptyset (set-ops-empty 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))
```

**Hint:** The recitation for this unit includes an “arrays as functions” exercise. Revisit it.

**Related reading**: For functions as values, see the examples of `lambda`

in the first part of section 2.7 on page 121, and also the array exercise from recitation. For function composition and currying, see section 2.7.2. For polymorphism, see section 2.9, which starts on page 135.

**Laws**: Complete the right-hand sides of the properties listed above. These properties say what happens when `member?`

is applied to any set created with any of the other functions. No other laws are needed.

## Relating imperative code to functional code

**A**. *Good functional style*. The Impcore-with-locals function

```
(define f-imperative (y) (locals x)
(begin
(set x e)
(while (p? x y)
(set x (g x y)))
(h x y)))
```

is in a typical imperative style, with assignment and looping. Write an equivalent μScheme function `f-functional`

that doesn’t use the imperative features `begin`

(sequencing), `while`

(goto), and `set`

(assignment).

- Assume that
`p?`

,`g`

, and`h`

are free variables which refer to externally defined functions. - Assume that
`e`

is an arbitrary expression. - Use as many helper functions as you like, as long as they are defined using
`let`

or`letrec`

and not at top level. - You need not write any algebraic laws.

*Hint #1:* If you have trouble getting started, rewrite `while`

to use `if`

and `goto`

. Now, what is like a `goto`

?

*Hint #2:* `(set x e)`

binds the value of `e`

to the name `x`

. What other ways do you know of binding the value of an expression to a name?

Don’t be confused about the purpose of this exercise. The exercise is a *thought experiment.* We don’t want you to write and run code for some *particular* choice of `g`

, `h`

, `p?`

, `e`

, `x`

, and `y`

. Instead, we want you write a function that works the same as `f-imperative`

given *any* choice of `g`

, `h`

, `p?`

, `e`

, `x`

, and `y`

. So for example, if `f-imperative`

would loop forever on some inputs, your `f-functional`

must also loop forever on exactly the same inputs.

Once you get your mind twisted in the right way, this exercise should be easy. The point of the exercise is not only to show that you can program without imperative features, but also to help you develop a technique for eliminating such features.

**Related reading**: No part of the book bears directly on this question. You’re better off reviewing your experience with recursive functions and perhaps the solutions for the Scheme assignment.

**Laws**: This problem doesn’t need laws.

## A function that returns a function

**F**. The handout “Program Design with Higher-Order Functions” mentions a higher-order function `flip`

, which can convert `<`

into `>`

, among other tricks. Using your algebraic law or laws from the comprehension questions, define `flip`

. Don’t forget unit tests.

**Related reading**: “Program Design with Higher-Order Functions”.

**Laws**: Use your law or laws from the comprehension questions.

## Graph problems

From COMP 15, you should be familiar with graphs and graph algorithms. In the next few problems you will work with an immutable representation of *directed* graphs: a graph is represented by an association list in which each node is associated with a list of its immediate successors. This representation is called a *successors map*. (It is a close cousin to the widely used “adjacency list.”)

For example, the ASCII-art graph

```
A --> B --> C
| ^
| |
+-----------+
```

could be represented as a successors map by `'([A (B C)] [B (C)] [C ()])`

.

The successors map, while it is an association list, a list of ordinary S-expressions, and an association list, is best treated as its own form of data. When writing algebraic laws, treat every successors map as one of two cases:

The empty list

`'()`

is a successors map.If

`node`

is a node,`successors`

is a list of nodes, and`graph`

is a graph represented as a successors map, then`(bind node successors graph)`

is a successors map.

You can tell these two cases apart using `null?`

. When you have the second case, you can extract `node`

and `successors`

using predefined functions `alist-first-key`

and `alist-first-attribute`

, and you can extract `graph`

using `cdr`

.

**Note**: The graph problems below can be solved using only first-order functions. But you will find the problems much easier if you use `let`

, `lambda`

, and either of the fold functions.

**Related reading**: The previous assignment. The definitions of `equal?`

in section 2.3.1 (basic recursive functions on lists). Material on association lists in section 2.3.6.

**Laws**: In each of the graph problems, you must write algebraic laws for every function that does case analysis (and only for those functions). You must write such laws even for helper functions and for inner functions defined using `lambda`

. Put all laws, even laws for inner functions, in comments above the entire function definition.

When you define laws for graph functions, you must treat the successors map as one of the two forms of data listed above. Writing `cons`

in graph-function laws is not acceptable.

**G1**. *List of edges*. An *edge* is represented by a record

`(make-edge N1 N2)`

where `N1`

and `N2`

are nodes. Define `make-edge`

using the following `record`

definition:

`(record edge [from to])`

Function `edge-list`

consumes a graph represented as a successors map and returns a list of all the edges in the graph. Edges may be listed in any order. For example, here are acceptable responses for a list of the edges in the graph pictured above:

```
(list3 (make-edge A B) (make-edge B C) (make-edge A C))
(list3 (make-edge A B) (make-edge A C) (make-edge B C))
```

Define function `edge-list`

. Algebraic laws are optional, but unit tests are required.

**Hints:**

There are plenty of lists in this problem. You will have an easier time if you find a way to use the predefined list functions, together with something you define that can add an edge to a list of edges.

By 105 standards, the solution to this problem requires a lot of code. To keep it manageable, use

`let`

or`let*`

.

**G2**. *Graph-building: adding an edge*. Function `add-edge`

takes two arguments: an edge made with `make-edge`

and a graph that is represented as a successors map. It returns a new graph that is like the original, except that the new graph has had the given edge added to it. ~~Depending on whether the ~~ In the new graph, both the `from`

node already appears in the graph, it may have to be added. (Determine its appearance using `equal?`

.)`from`

and `to`

nodes should be associated with their successors, even if the list of successors is empty.

For any edge `e`

and graph `g`

, function `add-edge`

satisfies this algebraic law:

```
(permutation? (cons e (edge-list g))
(edge-list (add-edge e g)))
```

Implement `add-edge`

, and in addition, write the following:

- At least one unit test using
`check-assert`

and the law above - At least one unit test using
`check-expect`

with an empty graph - At least one unit test using
`check-expect`

with a nonempty graph

You may include the implementation of `permutation?`

from the solutions to the previous homework.

Here are our requirements for algebraic laws:

Each recursive function you define must be specified using algebraic laws.

If none of your functions are recursive, you need not write any algebraic laws.

**Hint**: We know of at least two entirely different ways of coding `add-edge`

:

The first way is to treat the association list (that is, the successors map) entirely as an abstraction. That is, use only

`find`

,`bind`

, and the “laws of association lists” shown in lecture—never look directly at the representation. To succeed in this way, you will have to understand what happens when you call`find`

on a key that is not there.The second way is to get down in the weeds with the representation of the association list. You will wind up using

`car`

and`cdr`

, and if you are smart you will also use`alist-first-key`

and`alist-first-attribute`

.

We recommend coding the first way, and we recommend avoiding recursion.

**G3**. *Graph update: removing a node*. Calling `(remove-node node graph)`

returns a new graph that is like `graph`

, but with all references to `node`

removed:

No value

`equal?`

to`node`

appears as a key in the representation.No value

`equal?`

to`node`

appears as the successor of any other node.

If the original graph does not mention `node`

, then `(remove-node node graph)`

returns a new graph that is `equal?`

to the original.

Implement `remove-node`

. For full credit, implement `remove-node`

without using any recursion. If you do choose to use recursion, specify each recursive function by giving algebraic laws.

## Calculational reasoning about functions

**M**. *Reasoning about higher-order functions*. Using the calculational techniques from Section 2.4.5, which starts on page 110, 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.

Take the following properties as given:

```
((o f g) x) == (f (g x)) ; apply-compose law
(((curry f) x) y) == (f x y) ; apply-curried law
```

Using these properties should keep your proof relatively simple.

**Related reading**: Section 2.4.5. The definitions of composition and currying in section 2.7.2. Example uses of `map`

in section 2.8.1. The definition of `map`

in section 2.8.3.

**Laws**: In this problem you don’t write new laws; you reuse existing ones. You may take as given any algebraic law in the textbook (they start on page 108), in recitation, or in the lecture notes. (If it simplifies your proof, you may also introduce new laws, provided that you prove each new law is valid.)

## Ordered lists

**O**. *Ordered lists*. Like natural numbers, the forms of a list can be viewed in different ways. In almost all functions, we examine just two ways a list can be formed: `'()`

and `cons`

. But in some functions, we need a more refined view. Here is a problem that requires us to divide a list of values into *three* forms.

**Define a function** `ordered-by?`

that takes one argument—a comparison function that represents a transitive relation—and returns a predicate that tells if a list of values is totally ordered by that relation. Assuming the comparison function is called `precedes?`

, here is an inductive definition of a list that is ordered by `precedes?`

:

The empty list of values is ordered by

`precedes?`

.A singleton list containing one value is ordered by

`precedes?`

.A list of values in the form

`(cons x (cons y zs))`

is ordered by`precedes?`

if the following properties hold:`x`

is related to`y`

, which is to say`(precedes? x y)`

.List

`(cons y zs)`

is ordered by`precedes?`

.

Here are some examples. Note the parentheses surrounding the calls to `ordered-by?`

.

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

*Hints*:

The entire 9-step software-design process applies here, and it starts with the

*three*forms of data in the definition of “list ordered by” above.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)))`

**Related reading**: Section 2.9, which starts on page 135. Especially the polymorphic sort in section 2.9.2—the `lt?`

parameter to that function is an example of a transitive relation. Section 2.7.2. Example uses of `map`

in section 2.8.1. The definition of `map`

in section 2.8.3.

**Laws**: Write algebraic laws for `ordered-by?`

, including at least one law for each of the *three* forms of data used in the definition of “list ordered by” above.

# What and how to submit

You must submit four 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

A

`cqs.hofs.txt`

containing the reading-comprehension questions with your answers edited inA PDF files

`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**14 (b–f,h,j)**,**15**,**19**,**A**,**F**,**G1**,**G2**,**G3**, and**O**. You must precede each solution by a comment that looks like something like this:`;; ;; Problem A ;;`

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.

*Passing unnecessary parameters*. In this assignment, a very common mistake is to pass unnecessary parameters to a nested helper function. Here’s a silly example:

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

The problem here is that **the n parameter to sigma never changes**, and it is already available in the environment. To eliminate this kind of problem, don’t pass the parameter:

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

I’ve changed the name of the internal function, but the only other things that are different is that I have removed the formal parameter from the `lambda`

and I have removed the second actual parameter from the call sites. I can still use `n`

in the body of `sum-from`

; it’s visible from the definition.

An especially good place to avoid this mistake is in your definition of `ordered-by?`

in problem **O**.

Another common mistake is to fail to redefine functions `length`

and so on in exercise 15. Yes, we really want you to provide new definitions that replace the existing functions, just as the exercise says.

# 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**.

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.**

Exemplary | Satisfactory | Must improve | |
---|---|---|---|

Structure |
• Short problems are solved using simple anonymous
• When possible, inner functions use the parameters and • The initial basis of μScheme is used effectively. |
• Most short problems are solved using anonymous lambdas, but there are some named helper functions.
• An inner function is passed, as a parameter, the value of a parameter or • Functions in the initial basis, when used, are used correctly. |
• Most short problems are solved using named helper functions; there aren’t enough anonymous • Functions in the initial basis are redefined in the submission. |

## Functional correctness

In addition to the usual testing, we’ll evaluate the correctness of your translation in problem **A**. We’ll also want appropriate list operations to take constant time.

Exemplary | Satisfactory | Must improve | |
---|---|---|---|

Correctness |
• The translation in problem A is correct. • Your code passes every one of our stringent tests. • Testing shows that your code is of high quality in all respects. |
• The translation in problem A is almost correct, but an easily identifiable part is missing. • Testing reveals that your code demonstrates quality and significant learning, but some significant parts of the specification may have been overlooked or implemented incorrectly. |
• The translation in problem A is obviously incorrect, • Or course staff cannot understand the translation in problem A. • Testing suggests evidence of effort, but the performance of your code under test falls short of what we believe is needed to foster success.
• Testing reveals your work to be substantially incomplete, or shows serious deficiencies in meeting the problem specifications (
• Code cannot be tested because of loading errors, or no solutions were submitted ( |

Performance |
• Empty lists are distinguished from non-empty lists in constant time. |
• Distinguishing an empty list from a non-empty list might take longer than constant time. |

## Proofs and inference rules

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

Exemplary | Satisfactory | Must improve | |
---|---|---|---|

Proofs |
• Proofs that involve predefined functions appeal to their definitions or to laws that are proved in the book. • Proofs that involve inductively defined structures, including lists and S-expressions, use structural induction exactly where needed. |
• Proofs involve predefined functions but do not appeal to their definitions or to laws that are proved in the book. • Proofs that involve inductively defined structures, including lists and S-expressions, use structural induction, even if it may not always be needed. |
• A proof that involves an inductively defined structure, like a list or an S-expression, does |