COMP 105 Higher-Order Functions Homework

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

Dire Warnings

As a substitute for assignment, use let or let*. Also use let or letrec for ``helper'' functions. Except as noted below, do not define helper functions at top level. When you do define inner helper functions, avoid passing as parameters values that are already available in the environment.

Your solutions should be valid μScheme; in particular, they must pass the following test:

Overview, organization, and what to submit

Place your solutions to Exercises 9 (b-g,i), 10, 15, 22 and exercises A and S, as well as any extra credit that you choose to submit, in a file called solution.scm. (The solution to exercise T goes in its own file, solver-tests.scm.) Be sure to put the solutions in the order they are listed below and to precede each solution by a comment that looks like something like this:

Details of all the exercises

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 should 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 to help you develop a technique for eliminating such features. You'll use this technique again later on.

My estimate of difficulty: most students find this exercise hard (though there is very little code)

9, 10. Higher-order functions. Do Exercise 9 on page 168 of Ramsey, parts(b) to (g) and part (i). Do Exercise 10 on page 169. 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 in the initial basis, or insert, which is given, may use recursion.) For Exercise 9 only, you may define helper functions at top level.

For Exercise 10 you get full credit if your implementations return correct results. You get EXTRA CREDIT (EXACT-EXISTS) if you can duplicate 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.

My estimate of difficulty: medium to easy (the first one or two are medium difficulty, but because the problems are so similar, once you have any one or two, the rest are easy)

37. Operational semantics and language design. Do all parts of Exercise 37 on page 176 of Ramsey. Be sure your answer to part (b) compiles and runs under uscheme. Put your answers to all parts in file semantics.pdf.
My estimate of difficulty: easy (parts a and b) and medium (part c).

M. Reasoning about higher-order functions. Using the calculational techniques from Section 3.4.5, prove that

15. Functions as values. Do Exercise 15 on page 170 of Ramsey. When you code the third approach to polymorphism, please write a function mk-set-ops. This function should take one argument (the equality predicate) and should return a list of six values, in this order:

My estimate of difficulty: hard, because it requires a new way of thinking. Once you learn to think that way, the functions are easy.

S. Higher-order, polymorphic sorting. Using filter and curry, define a function qsort that, when passed a binary comparison function (like <), returns a Quicksort function. So, for example,

Your Quicksort should not use the append function in any of its disguises. In other words, don't copy cons cells unnecessarily. (If you can't figure this part out, go ahead and use append; you will get partial credit.) Hint #1: Use method of accumulating parameters covered in class when we discussed revapp. That is, think about writing a helper function that takes at least two arguments: a list l to be sorted and another list tail to be appended to the sorted list l.

Your code should use as few helper functions as possible. In particular, if you count up the number of occurrences of define and lambda, they should total at most three. (And if you give up and use append, that should save you a lambda.) If you need more lambda abstractions, you are doing something wrong. As usual, any helper functions should be defined internally using let or letrec, not at top level.

Remember to give a brief explanation of why your recursive sort routine terminates. If you write more than a dozen lines of code for this exercise, you're probably in trouble.

22. Continuation-passing style. Do Exercise 22 on page 173 of Ramsey. Don't overlook the possibility of deeply nested formulas with one kind of operator under another!
You must define a function make-formula-true which takes three parameters: a formula, a failure continuation, and a success continuation. The failure continuation should not accept any arguments, and the success continuation should accept two arguments: the first is the current (and perhaps partial) solution, and the second is a "resume" continuation.
My solution to this exercise is under 50 lines of μScheme.

T. Testing your solver. In file solver-tests.scm, submit three test cases that together exercise all the capabilities of your solver. These test cases should be in their own file, and they should contain two val bindings for each test case: f1 should be the formula input the the solver, and s1 should be either a satifying assignment, or if no satisfying assignment exists, then it should be the symbol no-solution. If, for example, I wanted to code the test case that appears on page 122 of the book, I might write

We hope to run every submitted solver on every test case. Your goal should be to design test cases that cause other solvers to fail.

Extra Credit

Consider the class of well-formed arithmetic computations using the numeral 5. These are expressions formed by taking the integer literal 5, the four arithmetic operators +, -, *, and /, and properly placed parentheses. Such expressions correspond to binary trees in which the internal nodes are operators and every leaf is a 5. Write a Scheme program to answer one or more of the following questions:

Avoid common mistakes

Another common mistake is passing unnecessary parameters to a nested helper function. Here's a silly example:

Another common mistake is to fail to redefine functions length and so on in Exercise 10. Yes, we really want you to provide new definitions that replace the existing functions, just as the exercise says.

Another common mistake is to put your answer to some part of 37 in your solution.scm. All parts of this answer, including Part B, go in semantics.pdf.

What to submit

If you wish, you may also turn in a file named transcript.txt that contains test cases for your solutions. You don't have to give us test cases; the test cases shown above are there to help you, not to make more work for you. If you do show test cases, please cut and paste a transcript of your interactions with the interpreters, just like the transcripts from the book, as in the following example:

When you are ready, run submit105-hofs to submit your work, which should include the following files:

How your work will be evaluated

Structure and organization criteria

There are a few new criteria around Quicksort and around the use of basis functions.

	Exemplary	Satisfactory	Must improve
Form	• Code is laid out in a way that makes good use of scarce vertical space. Blank lines are used judiciously to break large blocks of code into groups, each of which can be understood as a unit. • All code respects the offside rule • Indentation is consistent everywhere. • New: Indentation leaves most code in the left half or middle part of the line. • No code is commented out. • Solution file contains no distracting test cases or print statements.	• Code has a few too many blank lines. • Code needs a few more blank lines to break big blocks into smaller chunks that course staff can more easily understand. • The code contains one or two violations of the offside rule • In one or two places, code is not indented in the same way as structurally similar code elsewhere. • New: Indentation pushes significant amounts of code to the right margin. • Solution file may contain clearly marked test functions, but they are never executed. It's easy to read the code without having to look at the test functions.	• Code wastes scarce vertical space with too many blank lines, block or line comments, or syntactic markers carrying no information. • Code preserves vertical space too aggressively, using so few blank lines that a reader suffers from a "wall of text" effect. • Code preserves vertical space too aggressively by crowding multiple expressions onto a line using some kind of greedy algorithm, as opposed to a layout that communicates the syntactic structure of the code. • In some parts of code, every single line of code is separated form its neighbor by a blank line, throwing away half of the vertical space (serious fault). • The code contains three or more violations of the offside rule • The code is not indented consistently. • New: Indentation pushes significant amounts of code so far to the right margin that lots of extra line breaks are needed to stick within the 80-column limit. • Solution file contains code that has been commented out. • Solution file contains test cases that are run when loaded. • When loaded, solution file prints test results.
Naming	• Each function is named either with a noun describing the result it returns, or with a verb describing the action it does to its argument. (Or the function is a predicate and is named as suggested below.) • In a function definition, the name of each parameter is a noun saying what, in the world of ideas, the parameter represents. • Or the name of a parameter is the name of an entity in the problem statement, or a name from the underlying mathematics. • Or the name of a parameter is short and conventional. For example, a magnitude or count might be `n` or `m`. An index might be `i`, `j`, or `k`. A pointer might be `p`; a string might be `s`. A variable might be `x`; an expression might be `e`. A list might be `xs` or `ys`. • Names that are visible only in a very small scope are short and conventional.	• Functions' names contain appropriate nouns and verbs, but the names are more complex than needed to convey the function's meaning. • Functions' names contain some suitable nouns and verbs, but they don't convey enough information about what the function returns or does. • The name of a parameter is a noun phrase formed from multiple words. • Although the name of a parameter is not short and conventional, not an English noun, and not a name from the math or the problem, it is still recognizable---perhaps as an abbreviation or a compound of abbreviations. • Names that are visible only in a very small scope are reasonably short.	• Function's names include verbs that are too generic, like "calculate", "process", "get", "find", or "check" • Auxiliary functions are given names that don't state their contracts, but that instead indicate a vague relationship with another function. Often such names are formed by combining the name of the other function with a suffix such as `aux`, `helper`, `1`, or even `_`. • Course staff cannot identify the connection between a function's name and what it returns or what it does. • The name of a parameter is a compound phrase phrase which could be reduced to a single noun. • The name of some parameter is not recognizable---or at least, course staff cannot figure it out. • The name of a list parameter is neither a plural noun form nor a conventional name like `xs` or `ys`. • Long names are used in very small scopes (exception granted for some function parameters). • Very short names are used with global scope.
Documentation	• The contract of each function is clear from the function's name, the names of its parameters, and perhaps a one-line comment describing the result. • When names are not enough, each function is documented with a contract that explains what the function returns, in terms of the parameters, which are mentioned by name. • From the name of a function, the names of its parameters, and the accompanying documentation, it is easy to determine how each parameter affects the result. • Documentation appears consistent with the code being described. • As an alternative to internal documentation, a function's documentation may refer the reader to the problem specification where the function's contract is given.	• A function's contract omits some parameters. • A function's documentation mentions every parameter, but does not specify a contract. • A function's documentation includes information that is redundant with the code, e.g., "this function has two parameters." • A function's contract omits some constraints on parameters, e.g., forgetting to say that the contract requires nonnegative parameters.	• A function is not named after the thing it returns, and the function's documentation does not say what it returns. • A function's documentation includes a narrative description of what happens in the body of the function, instead of a contract that mentions only the parameters and result. • A function's documentation neither specifies a contract nor mentions every parameter. • There are multiple functions that are not part of the specification of the problem, and from looking just at the names of the functions and the names of their parameters, it's hard for us to figure out what the functions do. • Documentation appears inconsistent with the code being described.
Structure	• Short problems are solved using simple anonymous `lambda` expressions, not named helper functions. • New: Quicksort does not use `append` and is implemented using at most three `define` and `lambda`, in any combination. • New: Or, Quicksort uses `append` and is implemented using at most two `define` and `lambda`, in any combination. • New: Quicksort uses one `null?` test and one `if` • New: Quicksort has a very solid explanation for why it terminates. • New: Or, Quicksort has a believable explanation for why it terminates. • When possible, inner functions use the parameters and `let`-bound names of outer functions directly. • Helper functions are defined internally using `let`, `let`, or `letrec`. • The code of each function is so clear that, with the help of the function's contract, course staff can easily tell whether the code is correct or incorrect. • There's only as much code as is needed to do the job. • New:* The initial basis of μScheme is used effectively.	• Most short problems are solved using anonymous lambdas, but there are some named helper functions. • New: Quicksort is implemented using more than three `define` and `lambda`, in any combination. • New: Or, Quicksort uses `append` and is implemented using three `define` and `lambda`s, in any combination. • New: Quicksort uses up to two `null?` tests and up to two `if`s. • New: Quicksort mentions termination. • An inner function is passed, as a parameter, the value of a parameter or `let`-bound variable of an outer function, which it could have accessed directly. • Course staff have to work to tell whether the code is correct or incorrect. • There's somewhat more code than is needed to do the job. • New: Functions in the initial basis, when used, are used correctly.	• Most short problems are solved using named helper functions; there aren't enough anonymous `lambda` expressions. • New: Quicksort uses more than two `null?` tests or more than two `if`s. • New: Or, Quicksort does not use any `null?` tests or `if`s (serious fault). • New: Quicksort does not mention termination. • Helper functions are defined at top level. • From reading the code, course staff cannot tell whether it is correct or incorrect. • From reading the code, course staff cannot easily tell what it is doing. • There's about twice as much code as is needed to do the job. • New: Functions in the initial basis are redefined in the submission.
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.

Cost and correctness of your code

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.

• New: File solver-tests.scm contains exactly 6 val bindings and no other code.

• New: In file solver-tests.scm, values s1, s2, and s3 are either satisfying assignents or the symbol no-solution.

• New: In file solver-tests.scm, values f1, f2, and f3 represent valid formulas.

• 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 (serious fault).

• Code cannot be tested because of loading errors, or no solutions were submitted (No Credit).

• New: File solver-tests.scm contains other code besides the 6 val bindings requested.

• New: In file solver-tests.scm, value s1, s2, or s3 claims to be a satisfying assignment, but it isn't.

• New: Or, in file solver-tests.scm, value s1, s2, or s3 claims there is no solution, but the corresponding formula does have a solution.

• New: In file solver-tests.scm, values f1, f2, or f3 does not represent a valid formula.

COMP 105 Assignment: Higher-Order Functions

Preliminaries: Setup and Interpreter