Concepts in Programming Languages

Handouts

• Lecture slides v1.0 (as PDF, 1-up)
• 2023/24 Revision Guide to follow.

Core Exercises

The exercises have not changed in this version of the web page, but have been re-ordered.

• One-per-topic discussion questions
• 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ć

• ConceptsPL_AI_Exercises.pdf

Supervision question sets courtesy of Andrew Rice

(Note that topics VII, X and XI have been added/re-written since these questions were written.)

• Supervision 1
• Supervision 2 (note that the SML question should now be in OCaml instead)

---

Slides by topic and pointers to further reading material

1. Introduction and motivation.
   Supplementary reading material:
   • K. Zuse. Plankalkül.
2. The first procedural language: FORTRAN (1954-58).
   Supplementary reading material:
   • Fortran.
3. 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.
4. 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.
5. 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.
6. 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.
7. Scripting Languages and Dynamic Typing.
8. 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.
9. Languages for concurrency and parallelism
   
10. 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.
11. Miscellaneous concepts.
    Supplementary reading material:
    • P. Wadler. The essence of functional programming.
      Proceedings POPL'92.

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.
• 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.

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.