Programming Language Theory: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
The Church-Turing Thesis equates a vaguely-defined set of "computable" functions with the [http://en.wikipedia.org/wiki/Computable_function partial recursive functions]. Several systems are only as powerful as the partial recursives (''Turing-complete''): Turing machines and the λ-calculus are two. Programming languages provide further syntaxes and semantics, but all you really need in life is combinatory logic. Peter J. Landin's 1965 ACM report, "A correspondence between ALGOL 60 and Church's Lambda-notation", jump-started most of this.<blockquote>''There may, indeed, be other applications of the system than its use as a logic.'' -- Alonzo Church, 1932</blockquote> | The Church-Turing Thesis equates a vaguely-defined set of "computable" functions with the [http://en.wikipedia.org/wiki/Computable_function partial recursive functions]. Several systems are only as powerful as the partial recursives (''Turing-complete''): Turing machines and the λ-calculus are two. Programming languages provide further syntaxes and semantics, but all you really need in life is combinatory logic. Peter J. Landin's 1965 ACM report, "A correspondence between ALGOL 60 and Church's Lambda-notation", jump-started most of this.<blockquote>''There may, indeed, be other applications of the system than its use as a logic.'' -- Alonzo Church, 1932</blockquote> | ||
== | ==Functions== | ||
Expressions compose functions | Expressions in functional programs compose functions (as opposed to "values"). Backus proposed three tiers of complexity in his Turing Award lecture: | ||
* Simply functional language (<tt>fp</tt>): No state, limited names, finitely many functional forms, simple substitution semantics, algebraic laws | * Simply functional language (<tt>fp</tt>): No state, limited names, finitely many functional forms, simple substitution semantics, algebraic laws | ||
* Formal functional system (<tt>ffp</tt>): Extensible functional forms, functions represented by objects, translation of object representation to applicable form, formal semantics | * Formal functional system (<tt>ffp</tt>): Extensible functional forms, functions represented by objects, translation of object representation to applicable form, formal semantics | ||