Programming Language Theory: Difference between revisions
| Line 8: | Line 8: | ||
''Higher-order functions'' map one or more functions to a function. First-order support of functions provides composition of functions at runtime. | ''Higher-order functions'' map one or more functions to a function. First-order support of functions provides composition of functions at runtime. | ||
===Combinatory Logic=== | ===Combinatory Logic=== | ||
Combinatory logic provides no ''abstraction'' mechanism, but is build from only variables, a set of primitive combinators (closed λ-expressions with their own reduction rules), and function application. A Turing-complete kernel of primitive combinators is ''complete''. The SKI calculus requires only the K and S combinators; Chris Barker's Iota and Jot require only one each. | |||
====SKI Calculus==== | ====SKI Calculus==== | ||
*<tt>I ≡ λx. x</tt> | *<tt>I ≡ λx. x</tt> (identity) | ||
*<tt>K ≡ λx, y. x</tt> | *<tt>K ≡ λx, y. x</tt> (generation of constant functions) | ||
*<tt>S ≡ λx, y, z. (x z (y z))</tt> | *<tt>S ≡ λx, y, z. (x z (y z))</tt> (generalized function application) | ||
====Fixed-Point Combinators==== | ====Fixed-Point Combinators==== | ||
For a function F, its set of ''fixed points'' are those inputs which map to themselves. The ''fixed-point combinators'' compute the fixed points of their inputs. Curry's ''Y-combinator'' was the first: | For a function F, its set of ''fixed points'' are those inputs which map to themselves. The ''fixed-point combinators'' compute the fixed points of their inputs. Curry's ''Y-combinator'' was the first: | ||