Concepts in Programming Languages
Handouts
- Lecture slides (as PDF, 1-up)
- Lecture slides (as PDF, 4-up)
- 2021/22 Revision Guide.
- Errata/Lacunae [last updated 23 May 2023]:
- Unfortunately the audio channel failed for lecture 2 (and the video is black and white).
The material presented is fortunately similar to that which was presented last year. See Lisp and Algol and the first 12m:35s of Object Oriented [Concepts].
Differences: this year's notes (and silent video) add more material on "Behavioural Subtyping" and remove the material on "Is ML an object-oriented language" (present in last year's video).
The slides above are definitive, not last year's videos. - Slide 60 uses the term "tag field" without explaining it. It should say that "k"
(of enumeration type "kind") appearing in the Pascal code on slide 59 is an example of
a tag field.
C union types are often referred to as "untagged unions", and any programmer-desired discriminator (or tag) needs to coded separately, e.g. as a separate member of any struct containing the union. - On slide 95, the "α ≈ β" is just syntax for a type constraint; such
constraints are emitted at each node of an expression's AST.
Slide 97 shows how, for a simple example, type constraints are emitted (top), collected (middle) and solved (bottom).
Logically ≈ means "demand these are equal types"; this can be achieved by Prolog-style unification. - Sadly, the audio channel failed again for lecture 8. The material is also covered
in last year's recordings.
Dependent types [start 12:23 into the video] and Rust and Koka.
The additional examples of Rust code lectured (in the soundless lecture) are available below under "several examples to illustrate memory-allocation control in Rust".
- Unfortunately the audio channel failed for lecture 2 (and the video is black and white).
Some additional background and code examples
- NEW May 2023: several examples to illustrate memory-allocation control in Rust ex1, ex1a, ex1b, ex2, ex2a, ex2b, ex5, ex5a.
- McCarthy's LISP-in-LISP interpreter explained.
- Tony Hoare's claim that his invention of NULL pointers was a "billion dollar mistake".
- A Java applet and HTML to invoke it (you may have to fight quite hard with your browser to allow this to execute; you can see the HTML with `view source' in your browser).
- JavaScript and the DOM (click the button to execute; see the HTML with `view source' in your browser)
- Mozilla article on JavaScript inheritance and the prototype chain.
- The w3schools tutorial on JavaScript and the DOM.
- Marcelo Fiore's coding of Objects in SML using ML modules.
- A blog entry giving a gentle explanation of the problem of Java covariant arrays and invariant generics.
- Chatley, Donaldson and Mycroft's 2019 paper "The next 7000 programming languages" [sic].
- Videos on Rust ownership/borrowing.
Core Exercises
The exercises have not changed in this version of the web page, but have been re-ordered.
- One-per-topic discussion questions
- 2021/22 Revision Guide.
- Past exam questions. 2015–2022 are most relevant.
Note there is an error in y2021p7q1(b); ask your supervisor after attempting it.
Note also that exam questions for 2020, 2021 and 2022 were "open book"; thus they may appear harder than questions intended for "in-person" exams. - Questions on variance:
- Why does this C++ code give exactly one type error? Why is this error message necessary for type safety?
- Why does this Java code raise an exception? What happens when the various commented-out code is uncommented?
There are also two sets of supervision exercises below; doing them all is perhaps overkeen, but supervisors should select from them.
Supervision exercises by Andrej Ivašković
Supervision question sets courtesy of Andrew Rice
(Note that topics VII, X and XI have been added/re-written since these questions were written.)
Slides by topic and pointers to further reading material
- Introduction and motivation.
Supplementary reading material: - The first procedural language: FORTRAN (1954-58).
Supplementary reading material: - The first declarative language: LISP (1958-62).
Supplementary reading material:- J. McCarthy.
Recursive functions of symbolic expressions and their computation by machine.
Communications of the ACM, 3(4):184-195, 1960.
- J. McCarthy.
Recursive functions of symbolic expressions and their computation by machine.
- Block-structured procedural languages: Algol (1958-68) and Pascal (1970).
Supplementary reading material:- D. E. Knuth.
The remaining trouble spots in ALGOL 60.
Communications of the ACM, Volume 10, Issue 10, pages 611-618, 1967. - B. Kerninghan.
Why Pascal is not my favorite programming language.
AT&T Bell Laboratories. Computing Science Technical Report No. 100, 1981.
- D. E. Knuth.
The remaining trouble spots in ALGOL 60.
- Object-oriented languages – Concepts and origins: SIMULA (1964-67) and Smalltalk (1971-80).
Programming language: Squeak.
Supplementary reading material:- A. C. Kay. The early history of Smalltalk.
ACM SIGPLAN Notices, Volume 28, No. 3, 1993. - P. Wegner. Concepts and Paradigms of Object-Oriented Programming
Expansion of OOPSLA-89 Keynote Talk. - B. Stroustrup. What is Object-Oriented Programming? (1991 revised version).
Proc. 1st European Software Festival. February, 1991.
- A. C. Kay. The early history of Smalltalk.
- Types in programming languages: ML (1973-1978).
Supplementary reading material:- A. Koenig. An anecdote about ML type inference.
USENIX Symp. on Very High Level Languages, 1994.
- A. Koenig. An anecdote about ML type inference.
- Scripting Languages and Dynamic Typing.
- Data abstraction and modularity: SML Modules (1984-97).
Supplementary reading material:- M. Tofte. Four Lectures on Standard ML.
LFCS Report Series ECS-LFCS-89-73, 1989.
- M. Tofte. Four Lectures on Standard ML.
- Languages for concurrency and parallelism
- Functional-style programming meets object-orientation
Programming language: Scala.
Supplementary reading material:- M. Odersky et al. An overview of the Scala programming language.
Technical Report LAMP-REPORT-2006-001, Second Edition, 2006. - M. Odersky et al. A Tour of the Scala Programming Language.
Programming Methods Laboratory, EPFL, 2007. - M. Odersky. Scala By Example.
Programming Methods Laboratory, EPFL, 2008.
- M. Odersky et al. An overview of the Scala programming language.
- Miscellaneous concepts.
Supplementary reading material:- P. Wadler. The essence of functional programming.
Proceedings POPL'92.
- P. Wadler. The essence of functional programming.
Books
- Main:
- M. Scott. Programming Language Pragmatics (2nd edition).
Morgan Kaufmann, 2006. - J.C. Mitchell. Concepts in programming languages.
Cambridge University Press, 2003. - T. W. Pratt and M.V.Zelkowitz. Programming Languages: Design and implementation (3rd edition).
Prentice Hall, 1999. -
R. Harper. Practical
Foundations for Programming Languages.
Cambridge University Press, 2013.
- M. Scott. Programming Language Pragmatics (2nd edition).
-
Other:
- R. L. Wexelblat (ed.). History of Programming Languages.
ACM Monograph Series, 1981. - N. Metropolis, J. Howlett, G.-C. Rota (eds.). A History of Computing in the Twentieth Century: A Collection of Essays.
Academic Press, 1980. - T.J. Bergin and R. G. Gibson (eds.). History of programming languages - II.
ACM Press, 1996.
- R. L. Wexelblat (ed.). History of Programming Languages.
Further reading material (due to Marcelo Fiore); not needed for examination purposes
- P.J.
Landin.
The next 700
programming languages.
Communications of the ACM, Volume 9, Issue 3, 1966. - D. D. Clark.
The
structuring of systems using upcalls.
Proceedings of the tenth ACM Symposium on Operating Systems Principles, pages 171-180, 1985. - L. Cardelli and
P. Wegner.
On
understanding types, data abstraction, and polymorphism.
Computing Surveys, Vol 17 n. 4, pages 471-522, 1985. - P. Canning,
W. Cook, W. Hill,
W. Olthoff,
J.C.
Mitchell.
F-bounded
polymorphism for object-oriented programming.
Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture, 1989. - R. P. Draves, B. N. Bershad, R. F. Rashid, and R. W. Dean.
Using
Continuations to Implement Thread Management and Communication in
Operating Systems.
Proceedings of the thirteenth ACM Symposium on Operating Systems Principles, pages 122-136, 1991. - M. P. Jones.
Using
Parameterized Signatures to Express Modular Structure.
In Proceedings of the Twenty Third Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1996. - M. Odersky,
C. Zenger, and
M. Zenger.
Colored
local type inference.
ACM SIGPLAN Notices archive. Volume 36, Issue 3, pages 41-53, 2001. - R. Garcia, J. Jarvi,
A. Lumsdaine,
J. G. Siek, and
J. Willcock.
A
comparative study of language support for generic programming.
ACM SIGPLAN Notices, Proceedings of the OOPSLA'03 Conference, 2003. - A. Kennedy and
C. Russo.
Generalized
Algebraic Datatypes and Object-Oriented Programming.
Conference on Object-Oriented Programming Systems, Languages, and Applications, 2005. - N. Wirth.
Good Ideas, Through the Looking Glass.
IEEE Computer, pages 56--68, 2006. - P. Hudak,
J. Hughes,
S. Peyton
Jones,
P. Wadler.
A
History of Haskell: being lazy with class.
The Third ACM SIGPLAN History of Programming Languages Conference (HOPL-III) San Diego, California, June 9-10, 2007. - A. Kennedy. Lecture slides on Java (1996) and C# (2000), 2007.