Course pages 2015–16
Concepts in Programming Languages
Handouts
- Lecture slides (as PDF, 1-up)
- Lecture slides (as PDF, 4-up)
- 2014/15 Revision Guide
- One-per-topic sample questions (additional revision guide for 2015/16).
- Some additional exercises and information 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?
- This blog entry gives a gentle explanation of the problem of Java co-variant arrays and invariant generics.
- SML modules handout from lecture 6.
Handout meta-data and errata
- Note: the course has been updated for 2015/16. There is additional material -- particularly on monads (Topic X) and variance (Topic VI). Some previous material (e.g. Smalltalk) has been removed -- see the 2014/15 notes if you are interested -- and detailed knowledge of Scala (as opposed to programming concepts) has been downgraded. Note also that not every slide will be lectured, but they are left in place as useful revision background.
- Errata/Lacunae:
- Slide 83: the translation to ML is plausible but incorrect because the ML translation has no values of the type UBTree (as there are no non-recursive constructors). The Pascal is fine. The issue is that Pascal allows NULL pointers which are not modelled in the ML 'translation'. Readers might be interested (non-examinable) about Prof Sir Tony Hoare's view that his invention of NULL pointers was a "billion dollar mistake".
- Slide 93: "The object model in SIMULA was based on procedures activation records, with objects originally described as procedures that return a pointer to their own activation record". The word "objects" should be "classes".
- Slide 115 (Scripting Languages): perhaps I've dismissed these a little
too hastily. Advantages of dynamically typed languages include having,
as in LISP,
the availability of eval() and the ease of writing a meta-circular evaluator
(and interpreter for language L written in language L).
An interesting question to reflect on is "can eval() be implemented in a statically typed language and, if so, what is its type?". - Slides 133-134 (important) Sloppy use of cut-and-paste during slide writing has resulted in these slides declaring variables v as ArrayList (correct) but then using "v[i]" instead of "v.get" and "v.set" for access (sorry). Here are corrected versions of these slides. The exercise above also shows correct use.
Supervision question sets courtesy of Andrew Rice
Notes by topic
- 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).
Appendix: BCPL (1967) and C (1971-78)
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).
SML code: Objects in SML!?
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.
- 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
- A modern language design: Scala (2004-2006).
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.
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 Colletion 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
- 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.