Check out my first novel, midnight's simulacra!

Programming Language Theory: Difference between revisions

From dankwiki
No edit summary
Line 12: Line 12:
* 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 [http://en.wikipedia.org/wiki/Church_encoding Church encoding] (n ≡ λf . λx . f<sup>n</sup>x)
* Numeric literals rather than [http://en.wikipedia.org/wiki/Church_encoding Church encoding] (<tt>n ≡ λf . λx . f<sup>n</sup>x</tt>)

Revision as of 05:42, 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)

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 (n ≡ λf . λx . fnx)