Principles of Programming Languages

Matteo Pradella (twitter @bzoto, tag #corsopl)

Notes

Twitter, tag #corsopl

Here is Michele Chiari's GitHub repository

Text and solutions of the exam of 2020.01.15

Text and solutions of the exam of 2020.02.07

Text and solutions of the exam of 2020.06.29

Text and solutions of the exam of 2020.07.17

Text and solutions of the exam of 2020.09.03

Note: this page is now obsolete, please refer to BEEP for the current version.

Main Objectives

Programming languages are one of the most important and direct tools for the construction of a computer system: in a modern computer different languages are routinely used for different levels of abstraction. Aspects related to writing an operating system or a device driver are generally very different from those of writing high level applications. Moreover, in some typical complex applications, different levels (and thus languages) coexist and inter-operate, from the "core" logic written e.g. in C++ or Java, to the level of scripting, or to the level of "gluing" different applications, usually defined by an interpreted high level language (e.g. Python). Like natural languages, Programming languages are a fundamental means of expression. Algorithms implemented using different programming languages may exhibit very different characteristics, that can be of aesthetic character, as higher level languages can be very synthetic and are usually very expressive; or in terms of performance, as relatively lower level languages allow a more direct management of memory and in general of the performance of the generated code.

This course presents the salient features in the landscape of programming languages, by analyzing similarities and differences; traditional and recent approaches and paradigms. We will show significant fragments of some important programming languages, given as examples of those paradigms considered in class.

The course aims to provide the means to better understand the essence of defining concepts of programming languages, so to allow critical choice about the level of abstraction, and consequently the language necessary to implement a particular system. Also, the student must attain a good mental flexibility before of an aspect, i.e. the choice of a language, that is constantly changing in computer science and software. Last, we will provide those basis required from designing language constructs "in the small", going to entire languages (e.g. a Domain Specific Language).

Program

Motivations and Preliminaries
Basic Abstraction Mechanisms
- Variables, Binding, and Scoping
- Expressions and statements
- Procedures and recursion
- Macros
- Parameter Passing: call by value, by reference, and by name
- Types: basic data types; pointers; dynamic and static type checking; type inference; parametric polymorphism
- Exception Handling - issues and variants
Main Programming Paradigms
- Introduction: the Procedural Paradigm
- Functional Programming
  - History
  - Functional programming concepts: referential transparency, functions as a first-class entity, higher-order functions
  - Evaluation order and type systems
  - Purity and Monads
  - Continuations
- Object-Oriented Programming
  - History and variants
  - Main issues and relation with Abstract Data Types
  - Dynamic Method Binding and "ad hoc" polymorphism
  - Encapsulation and Inheritance
  - Class vs Prototype-based inheritance
- Concurrent Programming
  - History, background, and motivation
  - The Actor model
  - General issues on Communication and Synchronization
  - Variants and usages
- General Considerations and Other Paradigms
  - Multi-paradigm languages
  - Meta-programming facilities
  - Domain Specific Languages
  - Logic programming

Main class slides

Old slides

Code examples

Named-let semantics
some exercises on Scheme macros
Continuations in mainstream languages: JavaScript (Rhino) examples and Ruby examples
A for/break example
example: the State monad in Scheme
example: the State monad in JavaScript

Exercises and exams

Bibliography and references

Notes: advanced/optional papers are marked with (§). I advise to use as a reference at least one book for each language - most of them are freely available online.

Scheme
- Implementation and documentation: Racket
- A good book on Scheme
- Standards
- For fans of macros (§)
Haskell
- Learn you a Haskell...
- Real World Haskell
- Suggested implementation: The Glorious Glasgow Haskell Compiler
- Standard
- A gentle introduction to Haskell
- Haskell Cheatsheet
- All about monads (§)
Erlang
OO
JavaScript
- A re-introduction to JavaScript
Prolog
- A free Prolog course
- Logic, Programming and Prolog
- Prolog for Programmers
- The power of Prolog
- Suggested implementation: SWI-Prolog
- Logic programming in a few lines of Scheme: Sokuza-Kanren
Other interesting stuff (§)
- Lisp history
- Other historical Lisp stuff
- A. Colmerauer, P. Roussel, The birth of Prolog, 1992
- L. Cardelli, Type Systems, The Computer Science and Engineering Handbook. CRC Press, Chapter 103, 1997
- R. P. Gabriel, Patterns of Software, 1996, an inspiring book on Software, Design, Languages and Achitecture (both soft and hard!)
- P. Hudak, Conception, evolution, and application of functional programming languages, ACM Comput. Surv. 21, 3, 1989
- J. Backus, Can Programming be Liberated from the von Neumann style?, CACM 21(8): 613-641, 1978
- Fabrizio Ferrai's Haskell is mainstream
Fun stuff
- Why I did not use JavaScript or Ruby instead of Scheme for the basics.

Exams and evaluation

Classes are divided into 30 hrs for lessons, and 20 hrs of seminars and exercises.

The exam is written and "open book", i.e. students can consult their notes. The exam consists in solving small problems using the languages presented in class.

Reception

Tuesday, at 4.30 PM

Note: the schedule for reception is flexible, just send me an email or call for an appointment.

Teaching assistant

Michele Chiari