CSE40431代写、代写Java，Python编程

日期：2022-10-11 09:07

CSE40431 Homework 2: Scheme and the untyped λ-calculus

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 ’th letter of the alphabet with the

(

+ 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 that takes no arguments. It should choose a random number k between 1 and 25 (inclusive) and return a pair

(

)

of functions, one which

caesar

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.

Lambda calculations

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

= t’t” t v * t” t’ v * t”

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 fllows:

●0=n.

●Ifa,iseven,on.1 = n/2.

●lfo,isodd,an+1= 3n+ 1.

The Collatz conjecture is that for alln > 0, the hailstone sequence starting with n eventually reaches 1. Write a λ-term that, given the Church numeral forn > 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 .