MotivationComputable functions are a fundamental concept within computer science and mathematics. The λ-calculus provides a simple semantics for computation, enabling properties of computation to be studied formally. The λ-calculus incorporates two simplifications that make this semantics simple. One first simplification is that the λ-calculus treats functions "anonymously", without giving them explicit names. For example, the function can be rewritten in anonymous form as (read as “the pair of can be rewritten in anonymous form as The second simplification is that the λ-calculus only uses functions
of a single input. An ordinary function that requires two inputs, for
instance the can be reworked into This method, known as currying, transforms a function that takes multiple arguments into a chain of functions each with a single argument. Function application of the
whereas evaluation of the curried version requires one more step to arrive at the same result. |