Recursion and Arithmetic
ver. 1.0.0
This chapter explores how recursion is formulated in the lambda calculus and functional programming, introducing the Y combinator to construct recursive arithmetic operations.
Chapter 4, “Recursion and arithmetic,” explains how functional programming achieves repetition through recursion rather than mutable shared memory. It addresses the challenge of naive recursive definitions leading to infinite substitution sequences and demonstrates how to overcome this via function self-application and the paradoxical fixed-point combinator (\(Y\) combinator). This foundation is then used to construct fundamental arithmetic and comparison operations, including power, natural subtraction, equality, inequalities, and division.
Overview of Chapter 4: Recursion and Arithmetic
This chapter examines repetition in functional programming and lambda calculus, contrasting it with iterative constructs in imperative languages: - Repetition, Iteration, and Recursion: Bounded repetition (knowing the step count in advance) and unbounded iteration (running until a condition is met) are contrasted. In functional programming, repetition relies on recursion and structured nested function calls rather than shared state modifications. - The Definition Problem: Naive recursive definitions result in non-terminating substitution sequences during expansion because names must be fully replaced before evaluation. - Self-Application and Fixed-Point Combinators: - To delay recursive calls until needed, functions can abstract the recursive call point as a parameter and pass the function to itself (e.g., add2 add2). - This is generalized into a universal constructor known as the paradoxical combinator or fixed-point finder (\(Y\) combinator): recursive = λf.(λs.(f (s s)) λs.(f (s s))). - A special syntactic notation rec <name> = <expression> is introduced as shorthand for def <name> = recursive (λ<name>.<expression>). - Applicative Order β-Reduction: Introduces evaluation of function arguments prior to application, noting nuances regarding the evaluation of conditional branches. - Derived Arithmetic Operations: Using the recursion mechanism, several standard arithmetic operations and predicates are defined: - Power: Repeated multiplication (rec power x y). - Subtraction (Natural Subtraction): Decrementing both arguments until zero (rec sub x y), returning zero if \(y > x\). - Comparisons: Absolute difference (abs_diff), equality (rec equal x y), and inequality tests (greater, greater_or_equal). - Division: Repeated subtraction (rec div1 x y), defining division by zero safely as zero. - Exercises: Concludes with practice problems implementing recursive functions such as summation, factorial/product, and generalized functional summations over numerical ranges.
Materials
Source document
- An Introduction To Functional Programming Through Lambda Calculus, Greg Michaelson, Dover Publications, 1989, 2011 — Page 51-67