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=== | ||
Built from only variables, a set of primitive combinators (closed λ-expressions with their own reduction rules), and function application, combinatory logic provides no ''abstraction'' mechanism. 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. | Built from only variables, a set of primitive combinators (closed λ-expressions with their own reduction rules), and function application, combinatory logic provides no ''abstraction'' mechanism. A Turing-complete kernel of primitive combinators is ''complete''. The SKI calculus requires only the K and S combinators; Chris Barker's [http://semarch.linguistics.fas.nyu.edu/barker/Iota/ Iota and Jot] require only one each. | ||
====SKI Calculus==== | ====SKI Calculus==== | ||
*<tt>I ≡ λx. x</tt> (identity) | *<tt>I ≡ λx. x</tt> (identity) | ||