> Try executing 1000000 + 1000000 in Church numeral representation. Will you get a stack overflow? The sum is just function composition, so not likely. In term

> Try executing 1000000 + 1000000 in Church numeral representation. Will you get a stack overflow? The sum is just function composition, so not likely. In terms of using the sum, it depends on the function being applied and whether the evaluation model is lazy or strict. (And your stack size, of course.) The isZero function I gave above, for example, only needs to process the outermost "succ" or "zero" and the rest is ignored, which is perfect for lazy evaluation: isZero zero = (λn. n (λx. false) true) (λf. λx. x) -- def. of isZero and zero = (λf. λx. x) (λx. false) true -- β-reduce n = (λx. x) true -- β-reduce f = true -- β-reduce x isZero (succ N) -- for any N = (λn. n (λx. false) true) ((λn. λf. λx. f (n f x)) N) -- def. of isZero and succ = (λn. λf. λx. f (n f x)) N (λx. false) true -- β-reduce n = (λf. λx. f (N f x)) (λx. false) true -- β-reduce n = (λx. false) (N (λx. false) true) -- β-reduce f = false -- β-reduce x Of course, you can use other, more efficient representations in place of Peano numbers, such as Church-encoded lists of bits. Peano numbers are better suited for demonstrating the concept due to their simplicity. Lambda calculus doesn't really have a concept of "stack overflow" in any case. The point was that you can express both loops and conditions as well as more general structures such as state machines and continuations through (recursive) function calls, but—at least so far as I am aware—there is no way to similarly model data and generalized control-flow (other than loops, obviously) purely in terms of iteration. This is precisely because iteration constructs are more structured than recursion, and consequently have a narrow range of applications.