Programming Language Theory

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