I have been tasked with reducing the following lambda expression:
(λpq.pqp)(λab.a)(λab.b)
using call-by-name and call-by-value reduction strategies.
Call-by-name
strategy: Left-most, outermost redex first but no reduction under lambda.
Step 1) alpha-equivalence
(λpq.pqp)(λab.a)(λcd.d)
Step 2) Reduction - using the redex (λpq.pqp)(λab.a)
(λq.(λab.a)q(λab.a)(λcd.d)
Step 3) - substitute (λcd.d) for q
(λab.a)(λcd.d)(λab.a)
Step 4) - substitute (λcd.d) for a
(λb.(λcd.d))(λab.a)
Step 5) - substitute (λab.a) for b
(λcd.d) -> (λab.b)
Which gives the same result if you were to use normal order instead.
Call-by-value
strategy: Right-most, innermost redex first but no reduction under lambda
Step 1) alpha-equivalence
(λpq.pqp)(λab.a)(λcd.d)
Step 2) substitute (λab.a) for c
(λpq.pqp)(λd.d)
Step 3) substitute (λpq.pqp) for d
(λpq.pqp)