CS3342 Organization of Programming Languages - Assignment 3: Operators and Functions
CS3342 – Assignment 3
(15pt) Consider the logical operators: ¬, ∧, ∨, →, ↔, ⊕. If all are implemented in a programming
language, explain how short-circuit evaluation would work for those operators for which it is suitable.
-
(15pt) Using the numbers defined on slide 23, chap 11.1, and operators defined on slide 25, prove that 22+1 = 8 using: (a) applicative order, (b) normal order.
-
(20pt) For a λ-expression which can reach a normal form through both applicative and normal order, give an example where the normal order uses n times fewer steps than the applicative order, for an arbitrarily given n ≥ 1.
-
(50pt) Write a Scheme program, partition.rkt, that implements a function, (partition pred lst), that divides a list lst into two sublists, according to the predicate pred:
> (partition even? ’(1 4 6 2 3 4 5)) ’((4 6 2 4) (1 3 5)) > (partition positive? ’(-2 0 -0.001 -1)) ’(() (-2 0 -0.001 -1)) > (partition (lambda (x) (zero? (modulo x 3))) ’(3 5 2 9 0)) ’((3 9 0) (5 2))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 use only the 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: !!! Submit two files: one pdf file with responses to Assignment 3 Q1-3 and one source code file, partition.rkt, with code as required above to Assignment 3 Q4 (code); anything else receives 0pt. Solutions should be typed but high-quality hand-written solutions are acceptable.
Tools: You are allowed to use JFLAP, LLMs (such as ChatGPT), and online Lambda calculators, to help you solve the assignments. You still need to explain clearly your solution. Also, make sure you understand the answers as these tools will not be available during exams!
LATEX: For those interested, the best program for scientific writing is LATEX. 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/.
