Programming Languages
How programming languages are designed, defined and implemented: language families and design criteria, grammars, parsing and abstract syntax, operational and denotational semantics, names, scope, environments and closures, the lambda calculus, evaluation strategies, laziness and continuations, type systems, type soundness, polymorphism and Hindley-Milner type inference, data abstraction, objects and modules, garbage collection, ownership and virtual machines, logic programming with unification and resolution alongside constraint and concurrency paradigms, ending in a capstone that designs, implements and tests a small typed language.
CMPUT-325 Year 3 3 credits 12 lessons · 7 h 4 min
Offered by HSM University · Computing Science
What you'll learn
- Compare programming paradigms and language families, and evaluate languages by readability, writability, reliability and cost.
- Write context-free grammars in BNF, resolve ambiguity, precedence and associativity, and build recursive-descent parsers that produce abstract syntax trees.
- Define a language's meaning with small-step and big-step operational semantics and with denotational semantics, and relate the two.
- Explain names, bindings, static and dynamic scope, environments and closures, and trace how each language resolves a name.
- Reduce lambda-calculus terms, avoid variable capture, and encode data and recursion with Church encodings and fixed-point combinators.
- Compare call-by-value, call-by-name and call-by-need evaluation, parameter-passing modes, laziness and continuation-passing style.
- State typing rules and type soundness, distinguish static, dynamic, strong and weak typing, and read real type errors from Rust, mypy and TypeScript.
- Implement unification and Hindley–Milner type inference, and explain parametric, ad-hoc and subtype polymorphism and variance.
- Explain abstract data types, objects, dynamic dispatch, inheritance and its linearization, structural typing, prototypes and modules.
- Simulate mark-and-sweep, reference-counting and copying garbage collection, explain Rust ownership, and compile expressions to stack bytecode.
- Write and run logic programs with unification and SLD resolution, and compare constraint, Datalog and concurrency paradigms.
- Design, implement and test a small typed language end to end, from grammar and type checker to interpreter and soundness tests.
Course content
12 lessons · 7 h 4 min total · final exam
- 1 Why study programming languages 33 min · quiz
- 2 Syntax: grammars, parsing and abstract syntax 35 min · quiz
- 3 Semantics: operational and denotational 34 min · quiz
- 4 Names, bindings, scope and environments 35 min · quiz
- 5 The lambda calculus 35 min · quiz
- 6 Evaluation strategies, laziness and continuations 34 min · quiz
- 7 Types I: type systems and type checking 34 min · quiz
- 8 Types II: polymorphism and type inference 37 min · quiz
- 9 Data abstraction, objects and modules 36 min · quiz
- 10 Memory management and runtime systems 37 min · quiz
- 11 Logic programming and other paradigms 37 min · quiz
- 12 Capstone: designing and implementing a small language 37 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
How programming languages are designed, defined and implemented: language families and design criteria, grammars, parsing and abstract syntax, operational and denotational semantics, names, scope, environments and closures, the lambda calculus, evaluation strategies, laziness and continuations, type systems, type soundness, polymorphism and Hindley-Milner type inference, data abstraction, objects and modules, garbage collection, ownership and virtual machines, logic programming with unification and resolution alongside constraint and concurrency paradigms, ending in a capstone that designs, implements and tests a small typed language.
Part of the Science stream, typically taken in year 3.