Past exam of the computer science course of the University of Oxford / 2015 / Lambda calculus and types / 1 / a / Solution

Choose all auxiliary bound variables fresh for the free variables of

p, q, r

; alpha equivalence permits this. The operation

∙

is composition of lambda terms, so expand its definition and use beta reduction:

(p ∙ q) ∙ r p ∙ (q ∙ r) \equiv λ x . (λ y . p (q y)) (r x) ⟶_{β} λ x . p (q (r x)), \equiv λ x . p ((λ y . q (ry)) x) ⟶_{β} λ x . p (q (r x)) .

The two lambda terms have the same reduct, up to alpha equivalence, hence they are related by beta equivalence:

(p ∙ q) ∙ r =_{β} p ∙ (q ∙ r) .

No eta conversion is needed for this associativity calculation.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version