Indice
Principi di Linguaggi di Programmazione
Module2: Programming Paradigms Teacher: Marco Bellia Laurea Magistrale**: Informatics.
| Schedule | ||
|---|---|---|
| Day | Hour | Room |
| Monday | 11-13 | C1, Polo Fibonacci |
| Wednesday | 9-11 | C2, Polo Fibonacci |
The course is a required course for the Laurea Magistrale in Informatica
Summary of Content
The course covers the main topics on the structure of programming languages, from the viewpoints of the runtime support of its abstract machine and of the programming methodologies of the supported linguistic constructs. It focuses on the study of three paradigms, the Object Oriented, the Functional, and the Logic Programming paradigms, and on their use in the various programming methodologies. The Programming methodologies considered in the course includes Decomposition Based, Fully Abstract Abstraction, Inductive Programming, Divide and Conquer, Functional Programming, Memoization, Tail Recursion, Polymorphic Programming, Higher Order Programming, Combinator Based, Deductive Programming, Object Oriented Programming lecture9-10fun.pdf principi_di_linguaggi.pdf
Lectures
| Date | Lecture | Notes | Reading |
|---|---|---|---|
| 18/2/2013 | Course Overview | lecture1e | Chapters 1-3 [GM] |
| 20/2/2013 | The Expected Characteristics of a Programming Language | lecture2e | |
| 27/2/2013 | The Procedural Machinery: Binding, Mutable and Immutable Values, Env, Store, AR, Block, Scope, S-Scope, D-Scope | lecture3-6e-part1 | Chapters 4 [GM] |
| 4/3/2013 | The Procedural Machinery: Different structures of AR, Le Blank-Cook Approach, Program Unit, Aliasing, Lambda Lifting and D-Scope | lecture3-6e-part2 | Chapters 5 [GM] |
| 6/3/2013 | The Procedural Machinery: Lambda Lifting and S-Scope, Closures, Formalizations of Env and Store, Stack and Heap. Mono-heap, Variable Heap, Best Fit, Buddy and Fibonacci based multiple Heap. | lecture3-6e-part3: Exercises to do for next monday in: slide 4 and 19 | Chapters 5 [GM] |
| 6/3/2013 | In-depth Knowledge of a Language: What and where to study a language, Formal tools for comparing languages, Preliminary Formalizations | lecture7-8: Exercises to do for next monday in: slide 4 | Ch. 1 [BM] |
| 11/3/2013 | Declarations: Formalization of the Scope Rules, Sequential, Parallel and Mixed Declarations | lecture7-8: Exercises in: slide 5, 6, 9, 10, 20, 23 | Ch. 2-3 [BM] |
| 11/3/2013 | Expressions: Referential Transparency and Side Effects; Strict and non-strict operators and functions; Lazy and eager evaluation; Finitely Approximated Infinite and Finitary Infinite values | lecture9-10: Exercises in: slide 10, 13, 14 | Ch. 4.1-4.3 [BM] |
| 13/3/2013 | Expressions: Val and Den interpretation and its formalization | see slides lecture9-10 | Ch. 4.3.2-3 [BM] |
| 13/3/2013 | OCaml: First Order Functional Programming plus Mutable Value | lecture9-10fun: Exercises in slide 8 | see refs in slide 3 |
| 18/3/2013 | Simple and Compound Commands; commands for structured programming; implementation; Control abstraction | lezione11-12: (in italian) Exercises in slide 11, 12, 13, 21 | ch. 6, 11.1-.3 [GM]; ch. 5 [BM] |
| 18/3/2013 | Parameter Passing: The 3 steps; By value, By name | Lecture13-14: Exercises in slide 11, 12, 13, 21 | ch. 7 [GM]; ch. 6 [BM] |
| 20/3/2013 | Parameter Passing: by need, by function/procedure, by reference, by constant, by result, by value-result | [Lecture13-14.pdf] : Exercise in the last slide | ch. 7 [GM]; ch. 6 [BM] |
| 25/3/2013 | Fully Abstract Abstractions, Decomposition based Programming, Deep e Shallow Bindings, Inductive Programming, Divide and Conquer Programming, Memoization and Tail Recursive Programming Techniques | lecture: Exercises in the last slide | ch. 7 [GM]; ch. 6 [BM] |
| 27/3/2013 | Data, Data types and Types: Type System, Type Safety, System F1, Equivalence, Coercion, Cast, Polymorphism | lecture18-19e: Exercises in the last slide | ch. 8 [GM]; |
| 8/4/2013 | Dynamic Allocation and Deallocation: Costructors and Deallocation Techniques; Decomposition Based, Inductive, Tail Recursion, Memoization Based and Divide and Conquer In Functional Languages; Higher Order Programming: Data Extensions and Control Extensions; Combinatory Programming | lecture20 -upgraded-: Exercises in the slides 5,6,9,11 | ch. 11.3, 11.5 [GM]; |
| 10/4/2013 | Functional Languages: Reduction, Reduction Stategies and Combinatory Programming. Deductive Programming in Problem Solving: The general Problem and an Example | Lecture21-21Part1.pdf, Exercises in the last slide of Lecture20.pdf; lecture21-22part1 | ch. 11.2, 11.6 [GM]; ch. 12.1 [GM]; |
| 15/4/2013 | Deductive Programming: First Order Logic, Prenex Clausal Form, Horn Clause, Minimal Freely Generated Model. The inference rules of Unification and LUSH Resolution, Resolvents | Lecture21-22.pdf; lecture21-22e | ch. 12.2-12.3 [GM]; |
| 17/4/2013 | Deductive Programming in Prolog. Syntax and Semantics. SLD resolution and its Search Space (or Resolvent Tree) | first 10 slides of Lecture23-25; lecture23-25e | ch. 12.4.1-2-3 [GM]; |
| 22/4/2013 | Deductive Programming. NonDeterminism, Invertibility, Relational Calculus. Additionals and Extensions in Prolog | Lecture23-25.pdf; lecture23-25e | ch. 12.4.4-5; 12.5; 12.6 [GM]; |
| 24/4/2013 | From Data Abstractiona to Abstract Data Types. Type Record:Definition, Allocation, Access, Environment, Dynamic Allocation. API and ADT: Syntax and Function Up and Down | Lecture26-27.pdf; | ch. 9.1-9.2-9.3 [GM] (for more insights ch.14 [TG]) |
| 29/4/2013 | Holliday | ||
| 01/05/2013 | National Holliday | ||
| 06/05/2013 | Abstract Data Types: Syntax, Semantics. API and ADT in Ocaml | Complete Lecture26-27e.pdf and the exercises in its slides lecture26-27, and the exercises in the slides lecture20hoppart1 | Complete ch. 9 [GM] (for more insights, ch.14 [TG]) |
| 08/05/2013 | Object Oriented Paradigm: Package, Class, Fields, Constructors, Methods | part1 of lecture with the exercise in the last slide of the part | ch. 10.1-10.2 [GM] |
| 13/05/2013 | Object Oriented Paradigm: The Inheritance and The self-reference. Additional Mechanisms: Generic and Sub-type Polymorphism; Interfaces and Anonymous Classes | part2 of lecture29-30: exercises in the last slides of the part | ch. 10.3-10.4 [GM] |
| 15/05/2013 | Object Oriented Paradigm: Methodologies for ADT and code reuse | lecture: exercises in the slides | |
| 20/05/2013 | Object Oriented Paradigm: ADT for Mutable and Immutable Values | lecture29-30withexercisesii: exercises in the slides | |
| 20/05/2013 | Code Extension and Reuse in Java; Programming in Prolog | lecture29-30withexercisesii, strandset: exercises in the slides | |
Exam
I recall that the final examination consists of two distinct written tests: The Preliminary Test (PE) and the Final Test (FE). The participation to the FE is conditioned to passing the PE. Finally, The FE of this module consists of 10 open answer questions to be answered in 2 hours. For other details see the notices provided at the beginning of the first module. Here is a specimen of the FE.
| Appello-Date | Results: Module1 | Text: Module1 | Results: Module2: | Text: Module2 | Final Grade |
|---|---|---|---|---|---|
| III: june 4th | text | Table | text | To be registered | |
| IV: june 25th | Table | text | Table | text | |
| V: july 15th | Table | Table | To be registered | ||
| VI: sept. 5th | Table | in italian | Table | in italian | To be registered |
Communications
18/07: The grade registration (either of the single module, or of the final grade) is tomorrow, friday 19th july, at 9:30 a.m., in my office.
16/07: The students that intend to participate to the final test of tomorrow afternoon, have to send an e-mail.
25/06: Students, that have obtained the final grade (both the module 1 and the module 2 have been passed), can be come for registering:
- today, from 15:30 pm to 16:30 pm in room A
- tomorrow, from 15:30 pm to 16:30 pm in room A
- next thursday, from 16:00 pm to 19:00 pm in my office
16/04: Lecture39-30.pdf has been upgraded and contains new exercises that will be discussed next monday
11/04: lecture20.pdf has been upgraded and contains new exercises in the last slide.
Material
- After each lecture, the relating slides will be available online from this page [SL]
- Lecture Notes on the formal aspects of the Programming Language Definition are (currently available only in italian [BM]) in preparation.
- Principi di Linguaggi: Semantica Denotazione e Concetti di Programmazione, Bellia, M., March 2012, principi_di_linguaggi [BM]
- Programming Languages: Principles and Paradigms, Gabbrielli, M., Martini, S, Springer, 2010, ISBN 978-1-84882-914-5. [GM]
Complementary Reading
- Programming Language Pragmatics, Scott, M.L., Elsevier-Morgan Faufmann Pub. Press, 2009 [SC]
- Design Concepts in Programming Languages, Turbak, F., Gifford, D., M.A. Sheldon, MIT Press, 2008 [TG]