So far we haven’t used names that much for our λ calculus functions, mainly just with functions such as sqr. Recursion does require names, because we will call the functions multiple times. Here’s our function:
fact: (λn. (if (= n 1)
1
(* n (fact (- n 1))))
Let’s call (fact 3) and do a β reduction on 3:
(if (= 3 1) 1 (* 3 (fact (- 3 1)))
Clearly, (= 3 1) returns false, so we’re left with:
(* 3 (fact (- 3 1)))
Which becomes
(* 3 (fact 2))
Let’s do a β reduction on 2:
(* 3 (if (= 2 1) 1 (* 2 (fact (- 2 1))))
Okay, now this is starting to get complicated. It’s the same call we just had with (fact 3), but the expression is larger because we have the (* 3 … part too. Our test (= 2 1) returns false, so we just use the else part of the if to give us
(* 3 (* 2 (fact (- 2 1))))
We can reduce (- 2 1) to get
(* 3 (* 2 (fact 1)))
Now we do yet another β reduction to get:
(* 3 (* 2(if (= 1 1) 1 (* 1 (fact (- 1 1)))))
This time the if will return true, because (= 1 1) evaluates to true, so we have our simple case, which gives us:
(* 3 (* 2 1))
Suddenly this looks much simpler!
How about with ASTs?