Question

Problem 5 [15pt] Using the pure A-calculus, we can encode a pair of A-terms as where a term PAIR takes three A-terms a, b, p and applies p to a and b. That is, we can define PAIR as a bp. pab). a) (5pt) Based on this definition, we can encode function RIGHT as RIGHT under such encoding, RIGHT (PAIR y evaluates to y. Ap. (p (ts. S)). Show that b) (5pt) Try to define a function LEFT in A-calculus so that given a pair, it returns the first term in the pair. For example, LEFT (PAIR ) should evaluate to x under your encoding. c) (5pt) Try to define a function FLIP in A-calculus so that given a pair, it returns a new pair where the elements are flipped. For example, FLIP (PAIR X y) should evaluate to (PAIR yr) (or some equivalent term under al 8-reduction)

Answer 1

* Solcetion : - Given that data using the pure x-calculs, we can encoded a pair of d- terms as where a term PAIR taky 3 - Terny a, b, p and applies p to a and b. # ie we can define PAIR as (da, b p. pab) isoj (a) cup - F encode Function RIGHT IS RIGHT* 1pCp Catf-t) RIGHT (PAER ay) → RIGHT A CPAIR ay). (PATR ay (Attf)) =RIGHT A Coxy.ay). (1 24. 24 (Attit)) (b) LEFT A CPARR «Y) (PATR ay Citf.f)) = LEFT & (rxy: xy) . (xxy. xy (Attt) FLIP CPAIR my) - (PADR Y«) [from asb From