Programming Language Theory: Difference between revisions

@@ Line 1: / Line 1: @@
-==Untyped λ-calculus==
+==Applicative/Functional Programming==
+Expressions compose functions rather than 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
+* Formal functional system (<tt>ffp</tt>): Extensible functional forms, functions represented by objects, translation of object representation to applicable form, formal semantics
+* Applicative state transition system (<tt>ast</tt>): <tt>ffp</tt> plus mutable state and coarse-grained operations thereupon
+===Untyped λ-calculus===
+* Only one type: the function.