skip to primary navigationskip to content

Department of Computer Science and Technology

Part IB CST

 

Course pages 2023–24

Concepts in Programming Languages

Principal lecturer: Prof Anil Madhavapeddy
Taken by: Part IB CST
Term: Easter
Hours: 8
Format: In-person lectures
Suggested hours of supervisions: 2
Exam: Paper 4 Question 3
Past exam questions, Moodle, timetable

Aims

The general aim of this course is to provide an overview of the basic concepts that appear in modern programming languages, the principles that underlie the design of programming languages, and their interaction.

Lectures

  • Introduction, motivation, and overview. What is a programming language? Application domains in language design. Program execution models. Theoretical foundations. Language standardization. History.
  • The ancestors: Fortran, Lisp, Algol and Pascal. Key ideas: procedural (Fortran), declarative (Lisp), block structured (Algol and Pascal). Execution models (abstract machines), data types, control structures, storage, arrays and pointers, procedures and forms of parameter passing, scope, strict and lazy evaluation, garbage collection. Programs as data (Lisp).
  • Object-oriented languages -- Concepts and origins: Simula and Smalltalk. Dynamic lookup. Abstraction. Subtyping. Inheritance. JavaScript prototypal vs Java class-based inheritance.
  • Types. Types in programming languages. Type safety. Type systems--static vs. dynamic. Type checking and type inference. Polymorphism. Overloading. Type equivalence.
  • Data abstraction and modularity: ML-family Modules. Information hiding. Modularity. Signatures, structures, and functors. Sharing.
  • Languages for parallel processing. Shared-memory concurrency with spawn/sync (OpenMP, Cilk, X10). Distributed-memory models (the actor model, Erlang). External vs. internal iteration.
  • Combining functional and object-oriented features. Function types and lambdas in Java. Generic types and methods. Variance annotations. The expression problem. Value types and deep copy.
  • More-advanced concepts and idioms. Haskell monads, type classes. Continuation passing style and call/cc. Dependent types. Type-managed storage (Rust). Effect Handlers.

Objectives

At the end of the course students should

  • be familiar with several language paradigms and how they relate to different application domains;
  • understand the design space of programming languages, including concepts and constructs from past languages as well as those that may be used in the future;
  • develop a critical understanding of the programming languages that we use by being able to identify and compare the same concept as it appears in different languages.

Recommended reading

Books:
* Mitchell, J.C. (2003). Concepts in programming languages. Cambridge University Press.
* Scott, M.L. (2009). Programming language pragmatics. Morgan Kaufmann.
Odersky, M. (2008). Scala by example. Programming Methods Laboratory, EPFL.
Pratt, T.W. and Zelkowitz, M.V. (2001). Programming languages: design and implementation. Prentice Hall.

Papers:
Kay, A.C. (1993). The early history of Smalltalk. ACM SIGPLAN Notices, Vol. 28, No. 3.
Kernighan, B. (1981). Why Pascal is not my favorite programming language. ATandT Bell Laboratories. Computing Science Technical Report No. 100.
Koenig, A. (1994). An anecdote about ML type inference. USENIX Symposium on Very High Level Languages.
Landin, P.J. (1966). The next 700 programming languages. Communications of the ACM, Vol. 9, Issue 3.
Odersky, M. et al. (2006). An overview of the Scala programming language. Technical Report LAMP-REPORT-2006-001, Second Edition.
McCarthy, J. (1960). Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, 3(4):184-195.
Stroustrup, B. (1991). What is Object-Oriented Programming? (1991 revised version). Proceedings 1st European Software Festival.