CS3342 – Assignment 3
due Mar. 24, 2021; latest to submit: Mar. 26, 2021
Note: The two-day extension (with no penalty) already achieves the effect of an SRA.
SRAs cannot be used to extend the deadline past Mar. 26.
1. (20pt) We have modelled the non-negative integers and operations with λ-expressions:
n ≡ λfc. f(f . . . (f(f︸ ︷︷ ︸
nf ’s
c)) . . .)
+ ≡ λmnab.ma ((na) b)
× ≡ λmna.m (na)
(1) (10pt) Using the above, prove, using call-by-value reduction (leftmost-innermost applicable
abstraction), that:
(a) 2 + 3 =⇒∗β 5
(b) 2 ∗ 3 =⇒∗β 6
(2) (10pt) Define a new function, succ, that computes the successor, n + 1, of an integer n and
prove that:
succ n =⇒∗β n+ 1 .
2. (20pt) We modelled also boolean logic: T ≡ λxy.x, F ≡ λxy.y. Define a new operator, xor, that
computes the exclusive or of two boolean values. Prove, using call-by-name reduction (leftmost-
outermost applicable abstraction), that:
(a) xor T F =⇒∗β T
(b) xor F F =⇒∗β F
Q1,2 note: For all computations you perform, indicate clearly the reduction being being done by underlying
the abstraction used and the argument it is applied to: (λx.M)N . Do not use anything already
computed in the notes; compute everything from scratch.
3. (30pt) Write a purely functional Scheme function, my-filter, that returns a list containing all
elements of a given list that satisfy a given predicate. For example:
(my-filter (lambda (x) (< x 5)) ’(3 9 5 8 2 4 7)) =⇒ ’(3 2 4)
(my-filter char? ’(a #\a 1 ’b’ "a" #t #\b)) =⇒ ’(#\a #\b)
4. (30pt) Write a purely functional Scheme function, permutations, that returns a list of all permu-
tations of a given list. The functions should work like this:
(permutations ’()) =⇒ ’()
(permutations ’(1 2 3)) =⇒ ’((1 2 3) (2 1 3) (2 3 1) (1 3 2) (3 1 2) (3 2 1))
(permutations ’(a a)) =⇒ ’((a a) (a a))
Q3,4 note: You are required to provide real functional implementations, that do not employ advanced functions
(Scheme has a built-in filter function) or imperative features. Therefore, you are allowed to use
only the following basic Scheme functional constructs:
– function creation: lambda
– binding: define, let, let*, letrec
– conditionals: if, cond, not, and, or
– basic list operations: car, cdr, cons, list, append, null?
– mapping: map, for-each, apply
Submit your functions in a separate file a3.rkt.
1
READ ME! Submit all your answers as a single pdf file on OWL. Solutions should be typed but high quality
hand written solutions are acceptable. Source code, if required, is submitted separately.
The solutions should provide sufficient detail to support your claim. A simple yes/no answer without
any supporting arguments is not given any marks. Note also that understanding the questions is
part of solving the assignment. You are encouraged to ask questions when necessary, but try your
best first. It is much more important to learn than merely getting the assignment done.
2

欢迎咨询51作业君