CPSC 311 Definition of Programming Languages
Winter 2016 Term 1
| Course Goals | Syllabus | Notes | Assignments | Piazza |
|
University of British Columbia, Department of Computer Science CPSC 311 Definition of Programming Languages Winter 2016 Term 1
|
Lectures will involve a mix of coding from my laptop, the whiteboard or camera projector, and (occasionally) slides. Code and slides will be posted before, or shortly after, lectures. For whiteboard-based lectures, lecture notes will usually be posted later the same day. If I use the camera projector, scans will usually be posted later the same day.
Note: To "skim" means to go through once: "eyes meet the page". To "read" means to carefully inspect with a pen (or physical/digital equivalent) in hand; jot down, look up, and answer questions; work exercises; and generally interrogate the material.
| date | subject | materials | reading for next lecture | ||
|---|---|---|---|---|---|
|
Wednesday,
Sept. 7 |
Introduction:
Defining "Definition of Programming Languages" |
slides
"The C language does not exist" (accessible from UBC) |
Skim Intermezzo: BSL from HtDP. | ||
|
Friday,
Sept. 9 |
Racket |
lec2.rkt
(optional: PLAI 1st ed., Chapter 1) |
|||
|
Monday,
Sept. 12 |
Syntax; grammars |
lec-syntax.pdf; the Algol 60 report (accessible from UBC) |
|||
|
Monday–Tuesday,
Sept. 12–13 |
Racket; define-type |
tutorial-2016-09-12.rkt
tutorial-2016-09-13.rkt |
|||
|
Wednesday,
Sept. 14 |
Parsing; define-type; type-case |
scanned diagrams; lec3.rkt |
|||
| Part 1: Dynamic semantics | |||||
|
Friday,
Sept. 16 |
Evaluation semantics; rules and derivations; our first interpreter! |
lec-operational.pdf;
dynsem.rkt |
|||
|
Monday,
Sept. 19 |
Identifiers and substitution |
substitution.rkt;
substitution-middle.rkt (state at end of lecture) |
|||
|
Wednesday,
Sept. 21 |
'Let' expressions
Functions |
substitution-2.rkt
lec-functions.pdf |
Read lec-functions.pdf through at least 4.0 / Figure 1 | ||
|
Friday,
Sept. 23 |
Functions |
functions.rkt | |||
|
Monday,
Sept. 26 |
Expression strategy vs. value strategy; conditionals |
functions.rkt (updated!);
lec-functions.pdf lec-conditionals.pdf ifzero.rkt (not tested!) |
|||
|
Wednesday,
Sept. 28 |
conditionals; syntactic sugar |
lec-conditionals.pdf | |||
|
Friday,
Sept. 30 |
recursion; undefined behaviour |
lec-recursion.pdf | |||
|
Monday,
Oct. 3 |
Classifying languages | lec-taxonomy.pdf | |||
|
Wednesday,
Oct. 5 |
Review: Rules, derivations, adding strings |
2016-10-05-strings.pdf
a2+strings.rkt paircase: paircase.rkt |
|||
| Part 2: Static semantics | |||||
|
Friday,
Oct. 7 |
Types | lec-types.pdf |
Read Section 1, Cardelli, Type Systems |
||
|
Monday,
Oct. 10 |
Thanksgiving | (no class) | |||
|
Wednesday,
Oct. 12 |
Typing for Fun |
lec-typed-fun.pdf
typing-lam.rkt |
|||
|
Friday,
Oct. 14 |
modes; typing lam |
lec-typed-fun.pdf
typing-lam.rkt | |||
|
Monday,
Oct. 17 |
More on typing rules; typing for strings; type safety |
lec-safety.pdf;
scanned page; Mars Climate Orbiter paper |
|||
|
Wednesday,
Oct. 19 |
Subtyping | lec-subtyping.pdf | |||
|
Friday,
Oct. 21 |
Subtyping; review | list of review topics |
practice midterm:
practice-blank.pdf |
||
|
Monday,
Oct. 24 |
Review for midterm |
a3-q1-solution.pdf;
example derivations |
solution to practice midterm: practice-sol.pdf |
||
|
Wednesday,
Oct. 26 |
Review for evening midterm |
review-midterm.pdf | |||
| Part 3: That which remains | |||||
|
Friday,
Oct. 28 |
Small-step semantics |
lec-smallstep.pdf;
scan-2016-10-28.pdf |
lec-smallstep.pdf | ||
|
Monday,
Oct. 31 |
Small-step semantics: implementation |
scan-2016-10-31.pdf
smallstep.rkt lec-smallstep-2.pdf |
|||
|
tutorials,
Oct. 31 - Nov. 1 |
Small-step semantics; subtyping |
||||
|
Wednesday,
Nov. 2 |
Tour of a4;
Environment-based semantics |
a4.pdf
scan-2016-11-02.pdf lec-env.pdf env-let-broken.rkt |
Read lec-env.pdf | ||
|
Friday,
Nov. 4 |
Environment-based semantics:
closures |
lec-env.pdf
lec-closures.pdf env-let.rkt env-let-dynamic.rkt |
|||
|
Monday,
Nov. 7 |
Environment-based semantics: recursion |
lec-closures.pdf (revised)
scan-2016-11-07.pdf env-rec.rkt |
--> | ||
|
Wednesday,
Nov. 9 |
Environment-based semantics:
mutable state |
lec-state.pdf | |||
|
Friday,
Nov. 11 |
Remembrance Day | (no class) | |||
|
Monday,
Nov. 14 |
Environment-based semantics:
implementation of mutable state |
env-state.rkt (without using Racket boxes)
env-state-direct.rkt (using Racket boxes) |
Read lec-lazy.pdf | --> | |
|
Wednesday,
Nov. 16 |
Environment-based semantics: Expression strategy; Lazy evaluation; Subtyping for ref |
lec-lazy.pdf
env-lazy.rkt lec-subtyping-ref.pdf a5.rkt |
|||
|
Friday,
Nov. 18 |
Tour of a5; Records (subtyping); Downcasts |
scan-2016-11-18.pdf
lec-records.pdf |
|||
|
Monday,
Nov. 21 |
Bidirectional typing |
lec-bidir.pdf
bidir-1.rkt |
lec-bidir.pdf (updated)
bidir-1.rkt (updated) |
--> | |
|
Wednesday,
Nov. 23 |
Bidirectional typing; Polymorphism |
bidir-2.rkt
poly.sml lec-bidir-poly.pdf bidir-poly.rkt |
|||
|
Friday,
Nov. 25 |
Polymorphism |
lec-bidir-poly.pdf
scanned page |
|||
|
Monday,
Nov. 28 |
a6 tour: sum types, recursive types |
scanned notes | Review all the term's readings. | ||
|
Wednesday,
Nov. 30 |
Review |
scanned page: bidirectional typing with polymorphism |
Review all the term's readings. | ||
|
Friday,
Dec. 2 |
Review: small-step semantics, environments and closures |
scan-2016-12-02.pdf | Review all the term's readings. | ||
| Final Preparation | Practice Final—Episode One |
practicefinal-blank.pdf
practicefinal-sol.pdf practicefinal-sol-Q1a.pdf |
|||
|
Saturday, Dec. 17 |
Final exam (ANGU 098) | ||||