1. Read Sections 2.1 and 2.2 (the first part of the second lesson) in
[*Seven Lessons in Program Design*](../design/lessons.pdf).
You are tasked with writing a function that consumes a list of
numbers:
(a) How many cases must you consider?
(b) To tell the cases apart, what condition or conditions will you
use in `if` expressions? (List one fewer condition than cases.)
You are tasked with writing a function that consumes an ordinary
S-expression.
(c) How many cases must you consider?
(d) To tell the cases apart, what condition or conditions will you
use in `if` expressions? (List one fewer condition than cases.)
_You are ready to write algebraic laws using Scheme data._
2. In the main textbook, review section 2.2 on
values, S-expressions, and primitives, and say what is the value
of each of the expressions below.
If a run-time error would occur, please say so.
(car '(a b 1 2))
(cdr '(a b 1 2))
(= 'a 'b)
Write your answers as S-expression literals, like `'(a b c)`,
`#t`, or `17`.
_You are on your way to being ready for exercise **F**._
3. In *Programming Languages: Build, Prove, and Compare*, review the
first few pages of section 2.3, through the end of
section 2.3.2, and also section 2.3.5,
which starts on page 103. Which of the
following expressions evaluates to `#t` for every *list of
ordinary S-expressions* `xs`?
(= (reverse (reverse xs)) xs)
(equal? (reverse (reverse xs)) xs)
(a) Only the first
(b) Only the second
(c) Both the first and the second
(d) None
4. Read about association lists in section 2.3.8, which starts on page 106.
Given the definition
(val mascots
'((Tufts Jumbo) (MIT Beaver) (Northeastern Husky) (BU Terrier)))
Say what is the value of each of these expressions:
(find 'Tufts mascots)
(find 'MIT mascots)
(find 'Harvard mascots)
(find 'MIT (bind 'MIT 'Engineer mascots))
5. Read section 2.3 (another part of the second lesson) in [*Seven
Lessons in Program Design*](../design/lessons.pdf), and also the
first part of section 2.4 in the main textbook, up to and
including section 2.4.4.
Now complete the following law, which should represent a true
*property* of the association-list functions `find` and `bind`:
(find x (bind ...)) = ...
You may use variables, and you may use forms of data made with
`'()` and with `cons`. You may not use any atomic literals.
Write your property in the style of section 2.4.4.
_You are now prepared for the algebraic laws in exercises **A**,
**B**, and **C**._
6. In *Programming Languages: Build, Prove, and Compare*, read the
two laws for `append` (which we will call "append-nil" and
"append-cons") on page 99, and then study the proof at the bottom
of page 111, which shows that `(append (cons x '()) ys)` equals
`(cons x ys)`.
Now answer this question: The proof on page 111 proceeds by
expanding the definition of `append`. Suppose that you simplify
the proof by instead applying the "append-cons" law to the very
first expression. How many steps in the original proof does this
one step replace? (Count one step for each = sign.)
> Your answer:
7. Read section 2.5, which explains `let`, `let*`, and `letrec`.
This question asks you to decide if any or all these forms can
appropriately express the following function (written in C):
bool parity(int m) {
int half_m = m / 2;
int other_half = m - half_m;
return half_m == other_half;
}
Scheme does not have local variables, so to translate this
function into $\mu$Scheme, you must use `let`, `let*`, or
`letrec`. For each of these syntactic forms, we ask you if a
translation sensibly and faithfully captures the intent and behavior of the
original C function.
;; Translation A
(define parity (m)
(let ([half_m (/ m 2)]
[other_half (- m half_m)])
(= half_m other_half)))
Is translation A sensible and faithful (yes or no)?
;; Translation B
(define parity (m)
(let* ([half_m (/ m 2)]
[other_half (- m half_m)])
(= half_m other_half)))
Is translation B sensible and faithful (yes or no)?
;; Translation C
(define parity (m)
(letrec ([half_m (/ m 2)]
[other_half (- m half_m)])
(= half_m other_half)))
Is translation C sensible and faithful (yes or no)?
_You are now ready to program using `let`, `let*`, and `letrec`._
8. Read section 2.16.6, which starts on page 194.
Imagine that $\mu$Scheme is given the following definition:
(record 3point (x y z))
This definition puts five functions into the environment ρ.
What are their names?
_You are now mostly ready for exercise **E**._
9. Read section 2.3 in the second [*Lesson in Program
Design*](../design/lessons.pdf)---in particular, the last part, on
understanding and using properties. Assuming that `x` is
different from `y`, complete the following property:
(member? x (add-element y xs)) == ...,
where x differs from y
_You are ready to use properties to test `split-list`._