CS 131 Final Review Sheet

1. Standard ML
   • Variable bindings (vs. assignment)
   • Polymorphism
   • Exceptions
   • References
   • Module interfaces
   • Tail recursion
   • callcc
2. Operational Semantics
   • SOS (small-step) for NQSML
   • Natural semantics (big-step) for NQSML
   • Extensions for polymorphism and failure
   • Compared to denotational semantics
3. Type Systems
• Inference Rules for NQSML
• Type soundness
• Polymorphic types and (informal) parametricity
• Subtyping and the sumsumption rule
• Unification and monomorphic type inference
4. Abstract vs. concrete syntax
5. Static and dynamic scoping
6. Untyped lambda calculus
   • Beta-reduction and beta-conversion
   • Normal forms and Church-Rosser/confluence
   • Encodings (church numerals, booleans, etc.)
   • Using fixed points and the Y combinator
7. Curry-Howard isomorphism