Check out my first novel, midnight's simulacra!
Programming Language Theory: Difference between revisions
From dankwiki
No edit summary |
No edit summary |
||
| Line 8: | Line 8: | ||
* Function definition: <tt>(λ''formalparam'' . body)</tt> | * Function definition: <tt>(λ''formalparam'' . body)</tt> | ||
* Function application: <tt>function(''actualparam'')</tt> | * Function application: <tt>function(''actualparam'')</tt> | ||
The integers (or any countably infinite set) can be represented via the [http://en.wikipedia.org/wiki/Church_encoding Church encoding]: | |||
* <tt>n ≡ λf . λx . f<sup>n</sup>x</tt> | |||
Common syntactic sugar: | Common syntactic sugar: | ||
* Left-associative application as implicit parentheses | * Left-associative application as implicit parentheses | ||
* Use of definitions (allowing identifiers to stand in as λ-expressions) | * Use of definitions (allowing identifiers to stand in as λ-expressions) | ||
* Currying: <tt>(λx, y . x + y)</tt> rather than <tt>(λx . (λy . x + y))</tt> | * Currying: <tt>(λx, y . x + y)</tt> rather than <tt>(λx . (λy . x + y))</tt> | ||
* Numeric literals rather than | * Numeric literals rather than Church encoding | ||
Revision as of 05:43, 7 December 2009
Applicative/Functional Programming
Expressions compose functions rather than values. Backus proposed three tiers of complexity in his Turing Award lecture:
- Simply functional language (fp): No state, limited names, finitely many functional forms, simple substitution semantics, algebraic laws
- Formal functional system (ffp): Extensible functional forms, functions represented by objects, translation of object representation to applicable form, formal semantics
- Applicative state transition system (ast): ffp plus mutable state and coarse-grained operations thereupon
Untyped λ-calculus
Two operators (function definition and application) upon one operand type (λ-expression).
- Function definition: (λformalparam . body)
- Function application: function(actualparam)
The integers (or any countably infinite set) can be represented via the Church encoding:
- n ≡ λf . λx . fnx
Common syntactic sugar:
- Left-associative application as implicit parentheses
- Use of definitions (allowing identifiers to stand in as λ-expressions)
- Currying: (λx, y . x + y) rather than (λx . (λy . x + y))
- Numeric literals rather than Church encoding
