The idea is that to multiply $m$ by $n$, you "supply" $n$ as the successor function rather than the zero. Understanding what each variable means helps a lot.Īs an exercise, now try implementing multiplication. On a final note, I suspect that using meaningful names for your variables is half the battle here. So if you took, say, $S(S(0))$ and "replaced" the zero with $S(S(S(0)))$, you would be basically adding $2$ and $3$. What does it mean to "supply" a zero? Well, you can put anything you like there, even another number. The only difference between this and the recursive definition above is that a caller needs to supply the successor function and the zero. s(s(s(z)))$ is an "abstracted" version of $S(S(S(0)))$, using Church encoding. If $n$ is a natural number, then $S(n)$ is a natural number, where $S$ is the successor function.Natural numbers can be defined recursively: An abstraction consists of a head and a body, separated by the dot (.) symbol. ![]() We introduce new abstractions using the lambda symbol. I'm not going to completely answer your question by showing the adder to you in action, but here's some intuition as to why it works. Lambda calculus only defines univariate (single-variable) functions, but we can easily extend it to include multivariate functions too, as we’ll see later. Manufactures constant functions: ( K x) is the function which,įor all terms x and y.So. The simplest example of a combinator is I, the identityįor all terms x. It is in this way that primitive combinators behave as functions. Lambda calculus is concerned with objects called lambda-terms, which can be represented by Dana Scott in the 1960s and 1970s showed how to marry model theory and combinatory logic. Many early papers by Curry showed how to translate axiom sets for conventional logic into combinatory logic equations (Hindley and Meredith 1990). Although not a practical programming language, Unlambda is of some theoretical interest.Ĭombinatory logic can be given a variety of interpretations. The purest form of this view is the programming language Unlambda, whose sole primitives are the S and K combinators augmented with character input/output. Hence combinatory logic has been used to model some non-strict functional programming languages and hardware. It is easy to transform lambda expressions into combinator expressions, and combinator reduction is much simpler than lambda reduction. Despite its simplicity, combinatory logic captures many essential features of computation.Ĭombinatory logic can be viewed as a variant of the lambda calculus, in which lambda expressions (representing functional abstraction) are replaced by a limited set of combinators, primitive functions without free variables. In computer science, combinatory logic is used as a simplified model of computation, used in computability theory and proof theory. ![]() For a more modern treatment of combinatory logic and the lambda calculus together, see the book by Barendregt, which reviews the models Dana Scott devised for combinatory logic in the 1960s and 1970s. ![]() (1972) survey the early history of combinatory logic. The upshot of these historical contingencies was that until theoretical computer science began taking an interest in combinatory logic in the 1960s and 1970s, nearly all work on the subject was by Haskell Curry and his students, or by Robert Feys in Belgium. In the late 1930s, Alonzo Church and his students at Princeton invented a rival formalism for functional abstraction, the lambda calculus, which proved more popular than combinatory logic. Haskell Curry rediscovered the combinators while working as an instructor at Princeton University in late 1927. The original inventor of combinatory logic, Moses Schönfinkel, published nothing on combinatory logic after his original 1924 paper. While the expressive power of combinatory logic typically exceeds that of first-order logic, the expressive power of predicate functor logic is identical to that of first order logic ( Quine 1960, 1966, 1976). Another way of eliminating quantified variables is Quine's predicate functor logic. ![]() A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.Ĭombinatory logic was originally intended as a 'pre-logic' that would clarify the role of quantified variables in logic, essentially by eliminating them. It is based on combinators, which were introduced by Schönfinkel in 1920 with the idea of providing an analogous way to build up functions-and to remove any mention of variables-particularly in predicate logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages. Not to be confused with combinational logic, a topic in digital electronics.Ĭombinatory logic is a notation to eliminate the need for quantified variables in mathematical logic.
0 Comments
Leave a Reply. |