CSE40431辅导、辅导Java，Python编程
- 首页 >> OS编程 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 .
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 .