Principles of Programming Languages

Matteo Pradella, 2011-2012 (twitter @bzoto, tag #corsopl)

Notes

23/3: sono riuscito a spostare i primi due appelli: ora sono il 6 e il 23/7, entrambi alle 16.30

10/4: vi ricordo che la lezione di Giuseppe Maggiore su F# si terrà il 23 Maggio dalle 12.30 alle 16.30 in aula De Donato

4/5: Carmack on functional programming in C++

4/5: abbiamo deciso di non fare Erlang per motivi di tempo. Vedremo un po' di concetti collegati in C++ e Haskell

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

1. Motivations and Preliminaries

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

3. Main Programming Paradigms

   • Introduction: the procedural paradigm
   • The Object-oriented Paradigm
     • 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
   • The Functional Paradigm
     • History
     • Functional programming concepts: referential transparency, functions as a first-class entity, higher-order functions
     • Evaluation order and type systems
     • Purity and Monads
     • Continuations
   • The Logic Paradigm
     • History and motivation
     • Resolution and Unification
     • Control Flow management
     • Variants and usages

4. Concurrency and Parallelism

   • Background and motivation
   • Communication and Synchronization
   • Shared memory-based concurrency
   • Message passing-based concurrency

5. (Meta-)programming in the Real World

   • Multi-paradigm languages
   • Meta-programming facilities
   • Domain Specific Languages

Slides (still in progress)

1. Introduction and Scheme

2. Object Oriented programming

3. Hakell and functional programming

4. Haskell and parallelism

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.

1. Scheme

   • Standard R6RS
   • A good book on Scheme
   • For fans of macros (§)
   • Implementation: PLT Racket

2. Haskell

   • Standard ('98 + '10)
   • A gentle introduction to Haskell
   • Learn you a Haskell...
   • Real World Haskell
   • Implementation: The Glorious Glasgow Haskell Compiler

3. Prolog

   • A free Prolog course
   • A good book on Prolog (freely available online)
   • Implementation: SWI-Prolog

4. C++

   • Standard C++11 (it is actually the last draft, hence free)
   • The classic book on C++
   • Another book (freely available online)
   • Implementation: clang or the usual gcc

5. OO

   • D. Ungar and R. B. Smith, Self: the power of simplicity, Lisp and Symbolic Computation 4(3), June, 1991
   • W. Cook, On Understanding Data Abstraction, Revisited, 2009 (§)
   • Alan Kay, The Early History of Smalltalk, 1993 (§)
   • R. Gabriel, J. White, D. Boborow, CLOS: Integrating Object-Oriented and Functional Programming, CACM, 1991 (§)

6. Other interesting stuff (§)

   • Lisp history
   • Other historical Lisp stuff
   • A. Colmerauer, P. Roussel, The birth of Prolog, 1992
   • Oleg Kiselyov's web site
   • 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
   • E. W. Dijkstra, Go To Statement Considered Harmful, Comm. ACM 11(3): 147-148, 1968
   • D. Parnas, On the criteria to be used in decomposing systems into modules, CACM 15(12), 1053-1058, 1972

7. Fun stuff

   • Why I did not use Javascript or Ruby instead of Scheme

Exams and evaluation

There is a written traditional exam, where students may consult notes and books. During the course we will present small optional projects, that will be evaluated to increase final grades (around 2-3 points maximum, depending on the project).

Reception

Tuesday, at 4.30 PM

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

Teaching assistant

Ettore Speziale