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
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:
/comp/105/bin/uscheme -q < myfilename > /dev/nullwithout any error messages. 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 readability).
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:
;; ;; Problem A ;;Place your solutions to Exercises 37, G, and M in a file called semantics.pdf. You can create this file using LaTeX or Lyx another mathematical word processor, or you can write your solution by hand and scan it.
On this assignment, there is no pair programming.
A. Good functional style. The function
(define f-imperative (y) (x) ; x is a local variable (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 function f-functional that doesn't use the imperative features begin (sequencing), while (goto), and set (assignment).
Hint #1: If you have trouble getting started, rewrite while to use if and goto. Now, what is like a goto?
(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
Do all parts of Exercise 37 on page 176 of Ramsey.
Be sure your answer to part (b) compiles and runs under
Put your answers to all parts in file semantics.pdf.
My estimate of difficulty: easy (parts a and b) and medium (part c).
G. From operational semantics to algebraic laws
This problem has two parts.
(cdr (cons x xs)) == xs
(cdr (cons e1 e2)) == e2The conjecture says that two independent evaluations, starting from the same initial state, produce the same value as a result.
M. Reasoning about higher-order functions. Using the calculational techniques from Section 3.4.5, 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 laws as given:
((o f g) x) == (f (g x)) ; apply-compose law (((curry f) x) y) == (f x y) ; apply-curried lawUsing these laws should keep your proof relatively simple.
My estimate of difficulty: medium
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,
-> ((qsort <) '(6 9 1 7 4 14 8 10 3 5 11 15 2 13 12)) (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15) -> ((qsort >) '(6 9 1 7 4 14 8 10 3 5 11 15 2 13 12)) (15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)You will also find it helpful to use the function-composition function o.
If you are not familiar with Quicksort, we have prepared a short Quicksort handout online.
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.
Hint #2: What part of Quicksort could filter and o help with?
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.
(For the bloody-minded among you, the C standard library specifies a higher-order Quicksort routine. How short an implementation can you write in C? How many more bugs did you find in your C version than in your Scheme version? How much longer did it take you? Do you find the answers surprising when you compare your experience with C to your experience with Scheme? No credit is being offered for the answers to any of these C-related questions. I include them only so you can torture your friends who haven't had this course... In case you wanted to know, P. J. Plauger has written a pretty good Quicksort in about 65 lines of ANSI standard C. He is quite careful about efficiency issues, like bounding use of the call stack.)Here are some exacting test cases:
((qsort <) '(1 1 1)) ((qsort <=) '(1 1 1)) ((qsort <) '())You might also try using qsort to sort a list of lists by putting the shortest lists first.
My Quicksort is 11 lines of μScheme.
My estimate of difficulty: medium
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.
My estimate of difficulty: hard
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
(val f1 '(and (or x y z) (or (not x) (not y) (not z)) (or x y (not z)))) (val s1 '((x #t) (y #f)))As another test case, I might write
(val f2 '(and x (not x))) (val s2 'no-solution)Be sure to consider combinations of the various Boolean operators. Explain why these particular test cases are important—your test cases must not be too complicated to be explained.
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.
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:
Another common mistake is passing 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, but the only other things that are different is I've removed the formal parameter from the lambda and I've 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.
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.
Another common mistake is to forget to explain why qsort terminates.
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:
-> (count 'a '(1 b a (c a))) 1 -> (countall 'a '(1 b a (c a))) 2
When you are ready, run submit105-hofs to submit your work, which should include the following files:
letform needs a contract.
There are a few new criteria around Quicksort and around the use of basis functions.
• 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.
• 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
• 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
• 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
• Long names are used in very small scopes (exception granted for some function parameters).
• Very short names are used with global scope.
• 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.
• Short problems are solved using simple anonymous
• New: Quicksort does not use
• New: Or, Quicksort uses
• New: Quicksort uses one
• 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
• Helper functions are defined internally using
• 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
• New: Or, Quicksort uses
• New: Quicksort uses up to two
• New: Quicksort mentions termination.
• An inner function is passed, as a parameter, the value of a parameter or
• 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
• New: Quicksort uses more than two
• New: Or, Quicksort does not use any
• 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.
• 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.
• 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
• New: In file
• New: In file
• 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
• New: In file
• New: Or, in file
• New: In file
• New: Proofs that involve predefined functions appeal to their definitions or to laws that are proved in the book.
• New: Proofs that involve inductively defined structures, including lists and S-expressions, use structural induction exactly where needed.
• New: Proofs involve predefined functions but do not appeal to their definitions or to laws that are proved in the book.
• New: Proofs that involve inductively defined structures, including lists and S-expressions, use structural induction, even if it may not always be needed.
• New: A proof that involves an inductively defined structure, like a list or an S-expression, does not use structural induction, but structural induction is needed.