Up – Spring-2025 » topicsThis is a (fairly) complete list of the topics we'll cover in this course. It's not guaranteed to be exhaustive, and it's subject to change, but we'll do our best to keep this list up to date.
Topics:
Describe what this course is about, how the course is structured, a rough outline of the topics Introduce OCaml, how to work with utop, how to write basic expressions Topics:
Look at basic constructs we need to start writing interesting OCaml programs Work through some example programs Start looking at typing rules and semantics rules of a fragment of OCaml Introduce the build tool dune Topics:
Look at how to organize data using simple variants, data-carrying variants, tuples, records Introduced the notion of a pattern (not the same thing as an expression) Topics:
Introduce lists, emphasizing that lists are immutable and not the same as arrays Talk about tail recursion, how to write tail recursive functions, why we might want to Topics:
Introduce algebraic data types (ADTs) as a way of defining recursive and parameterized data types. Cover many examples of ADTs Topics:
Take a moment to discuss polymorphism more formally, and how to use polymorphism to write more general programs Topics:
Introduce the notion of higher-order functions, i.e., functions which take other functions as arguments Cover the first two fundamental higher-order functions: map and filter Topics
Cover the last (and most complex) of the common higher-order functions: fold_left and fold_right Look at how higher-order functions can be useful for more than lists. Topics
Further discuss the use of Options and Results for error handling (Advanced) Briefly cover monadsCover how to raise and catch exceptions Talk a bit about OUnit and writing unit tests Topics:
Introduce modules as a way of organizing OCaml code. See at how modules can also be used to organize interfaces for data structures. Topics
Introduce the second half of the course, including the full interpretation pipeline Start at the beginning of the pipeline (i.e., parsing) with (E)BNF grammars Topics
Look more carefully at the difference between lexing and parsing Introduce he notion of grammatical ambiguity, and discuss how to avoid it Topics
See how to use ocamllex and menhir to generate lexers and parsers for a grammar In particular, show how to deal with ambiguity and precedence Topics
Introduce operational semantics (both small-step and big-step) as a way of formally specifying the behavior of executing a programming language Give some examples of derivations for various semantics Topics
Look the lambda calculus, its syntax and semantics Discuss capture-avoiding substitution and well-scoped expressions Topics
Discuss dynamic and lexical scoping, with an emphasis on how variable scoping is dealt with in OCaml We consider how this connects to call-by-value semantics and closures Topics
Further discuss closures as a way to better implement lexical scoping in functional programming languages Introduce the environment model as a more efficient alternative to the substitution model Topics
Add types to the lambda calculus Discuss more formally the anatomy of a typing judgment and a typing derivation Topics
Discuss why we do type checking Prove that well-typed programs are "good"Topics
Give a live coding demonstration of an implementation of the STLC Topics:
Introduce the system Hindley-Milner Light Discuss core concepts of this system, including type order, mono/polytypes Discuss let-polymorphism Topics
Discuss more generally the notion of unification Look at its connection to type inference Briefly see its connection to logic programming Topics
Define a syntax-directed type system which uses unification to do type inference Give examples derivations in this system Topics
Do a live-coding implementation of Hindley-Milner Light Topics
Discuss stack-oriented languages in general Introduce the syntax and semantics of a basic stack-oriented language with procedures Topics
Give a high-level introduction of compilation and its relation to interpretation Work through some simple examples Go through an example of building a simple byte-code interpreter