Homework 2: Scheme and the untyped λ-calculus

Due: 09/16 at 11:59pm
Points: 30

Please prepare your solution to problem 1 as a .scm file, and your solutions to problems 2–3 as a PDF file (scanned handwriting is okay, but no .doc or .docx, please). Submit all files in Canvas.

1. Caesar ciphers

This exercise will give you some practice writing in Scheme, particularly in using higher-order functions and lexical scoping.

The Caesar cipher was used by Julius Caesar to encrypt his private letters (Suetonius Vita Divi Iulii 56.6). A Caesar cipher with a shift of k replaces the i’th letter of the alphabet with the (i + k)’th letter of the alphabet (mod 26). For example, a Caesar cipher with a shift of −3 would change ECCE to BZZB. In this problem, you’ll implement this cipher in Scheme.

Write a function called caesar that takes no arguments. It should choose a random number k between 1 and 25 (inclusive) and return a pair (cons) of functions, one which encodes strings with a shift of k and one which decodes strings with the same shift. Assume that strings use only uppercase letters. For example,
```
> (let ((encdec (caesar)))
    (let ((encode (car encdec))
          (decode (cdr encdec)))
      (encode "ECCE")))
"YWWY"
```
(but since the shift is random, you might get a different result). And encoding then decoding should yield the original string:
```
> (let ((encdec (caesar)))
    (let ((encode (car encdec))
          (decode (cdr encdec)))
      (decode (encode "ECCE"))))
"ECCE"
```
It should be possible to create multiple encoder/decoder pairs at the same time. (In other words, don’t store k in a global variable.)
Try to make your encoder and decoder run in O(1) space. It’s not a requirement, but it’s good functional programming practice.
The following Scheme functions should be handy:
- (random n) gives a random integer between 0 and n − 1 inclusive. (Other Schemes might be different.)
- (modulo n m) is the same as Python’s % operator. (It behaves differently from C/C++’s % for negative numbers.)
- string->list and list->string convert strings to lists of characters and vice versa.
- char->integer and integer->char convert characters to integers and vice versa. Note that the letter A converts to 65.

2. Lambda calculations

Prove each of the following statements. If the statement is of the form t ⟶* t', show each call-by-value β-reduction step with the redex underlined. If the statement is of the form t = t', find a third term t" such that t ⟶_v* t" and t' ⟶_v* t", and prove both, showing each βᵥ-reduction step with the redex underlined.

For example:

    (λx. x) (λy. y) (λz. z)
    ―――――――――――――――

⟶ (λy. y) (λz. z)
    ―――――――――――――――

⟶ (λz. z)

(λx. λx. x) (λy. λz. y) (λy. λz. z) ⟶* λy. λz. z
(λx. λy. y x) (y y) z ⟶* z (y y)
(λx. λy. λz. x z (y z)) (λx. λy. x) (λx. λy. x) = λz. z
(λm. λn. λs. λz. m s (n s z)) x (λs. λz. z) = (λm. λn. λs. λz. m s (n s z)) (λs. λz. z) x

3. Hailstone sequences

The hailstone sequence starting with n is defined as follows:

a₀ = n.
If a_n is even, a_n + 1 = a_n/2.
If a_n is odd, a_n + 1 = 3a_n + 1.

The Collatz conjecture is that for all n > 0, the hailstone sequence starting with n eventually reaches 1. Write a λ-term that, given the Church numeral for n > 0, returns tru if the hailstone sequence starting with n eventually reaches 1; otherwise, it diverges.

You may use any of the terms defined in the book: tru, fls, test, and, pair, fst, snd, scc, plus, times, iszro, prd, and fix.