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 c))…)
nf ’s
+ ≡ λmnab.m a ((n a) b)
× ≡ λmna.m (n a)
(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 .
(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 TF=⇒∗βT (b)xor FF=⇒∗βF
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.
(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)
(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))
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
2.
Q1,2 note:
3.
4.
Q3,4 note:
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