CS3342 – Assignment 3
due Mar. 27, 2024
2-day no-penalty extension until: Mar. 29, 11:59pm
!!! Submit all your responses for Q1 – Q3 as a single pdf file to Assignment 3 Q1-Q3 and
your Q4 Scheme code as alcs.rktfile to Assignment 3 Q4 (Scheme code).
1. (10pt) Using the numbers defined on slide 23, chap 11.1, and exponentiation operator defined on
slide 25, prove that 2
3
= 8 using:
(a) applicative order,
(b) normal order.
You can use online lambda calculators but do not post screen shots.
2. (20pt) Give an example of aλ-expression such that anα-conversion is needed during the applicative
order reduction, but noα-conversion is necessary during the normal-order reduction. Show both
reductions.
3. (20pt) Prove that the grammar forλ-expressions with minimum parentheses on the bottom of slide
5, chap.11.1, is unambiguous.
4. (50pt) Write a Scheme program,lcs.rkt, that computesalongest common subsequence of two
lists:
> (lcs ’() ’(a b))
’()
> (lcs ’(b a) ’(a b))
’(b)
> (lcs ’(a b c b d a b) ’(b d c a b a))
’(b d a b)
You are required to provide a pure functional implementation from scratch, that does not employ
advanced functions or imperative features. Therefore, besides basic arithmetic operations and
number comparisons, you are allowed to useonlythe following basic Scheme functional constructs:
– function creation:lambda
– binding:define,let,let*,letrec
– booleans:not,and,or
– conditionals:if,cond
– list operations:car,cdr,cons,list,append,null?,member
– comparison:eq?,eqv?,equal?
– mapping:map,apply
Notes: Online tools:You are allowed to use online tools such as JFLAP, LLMs (ChatGPT et al.), online
lambda calculators, etc., to help you solve the assignment. You still need to explain clearly your
solution. Also, make sure you understand what the tools do. No tool will be available during exams!
L
A
T
E
X:For those interested, the best program for scientific writing is L
A
T
E
X. It is far superior to
all the other programs, it is free, and you can start using it in minutes; here is an introduction:
https://tobi.oetiker.ch/lshort/lshort.pdf. It is also available online at https://www.overleaf.com/.
1
