SYLLABUS and READING MATERIAL

Il contenuto di questa pagina potra' venire modificato durante lo svolgimento del corso.
Potra' considerarsi definitivo solamente al termine del corso.

The list of the arguments of the course, together with the material to study.

• Overwiew of the main concepts related to Functional Programming  [PE] (You can skip 1.5, 1.6, 1.9) and [BGS] (Section 1)
• Lambda Calculus [BGS] (Sections 2 and 3)
• Typed Lambda Calculus 'a la Church and a' la Curry, Type Inference, extended lambda-calculi, reduction strategies, implicit polymorphism [BGS](Section 4),
• Syntax of Scheme  [Scheme] (purely functional fragment, main constructs)
• Recursion [B1]
• Data Types, Inductive data types, parametric data types, in Scheme and Haskell, Haskell Polymorphism and laziness [B2],[HASK],[B0]
• Higher order functions, Curryfication, Let constructs in Scheme [B3]
• Well-founded sets, Recursion and Induction, Induction Principles [B4], [B5], [VS](in [VS] you can skip 4.2, but not the exercises)
• Overview of tail recursion and call/cc [B7]
• Informal Operational Semantics of Scheme  [B6]
• Formal Structured Operational Semantics of Scheme [HPR]

A few of the following files are in .ps format. Windows users can view them using ghostscript and print them directly (programs like fineprint 2000 can be used to have two pages in a single page in order to save space). Both gostscript  and fineprint 2000 can be freely downloaded from several sites.

Some html files below are badly printed by some browsers. In this case it is advisable to download them and format them  before printing.

Thanks to Claudia and Tiziana Genovese for their writing the notes of the course which have been partly used as a basis for all the following Lecture Notes. Thanks to Felice S.  and Massimiliano Salfi for their collaboration  in some traslations.

Most of the Lecture Notes below have been revised and partly rewritten during my visit at the University of Reykjavik, whose support I gratefully acknowledge.

.

• [PE] R. Plasmeijer, M. van Eekelen, "Functional Programming and Parallel Graph Rewriting", Addison-Wesley, 1993. Cap. 1 (basic concepts) (file pdf)
• [BGS] Franco Barbanera, Claudia & Tiziana Genovese, Massimiliano Salfi Short Introduction to the Lambda Calculus (html file, aggiornato al 13 Novembre 08)
• [B1] Franco Barbanera Lectures Notes on Scheme and on Recursion using Scheme  (html file, aggiornato al 08 Dic 07)
• [B2] Franco Barbanera Lectures Notes on Data Types  (html file, aggiornato al 3 Dic 07)
• [B3] Franco Barbanera Notes on Let, Higher-order functions and Curryfication in Scheme (file html, aggiornato al 10 Dicembre 07)
• [B4] Franco Barbanera Notes on well founded sets (file html, aggiornato al 20 Nov 08)
• [B5] Franco Barbanera Lectures Notes on Recursion and Induction Principles (file html, aggiornato al 12 Dic 07)
• [VS] Vladimiro Sassone Induzione matematica e verifica di funzioni ricorsive (file ps). ( le soluzioni degli esercizi proposti).
• [B6] Franco Barbanera Lectures Notes on Scheme Operational Semantics (file html, aggiornato al 18 Dic 07)
• [B7] Franco Barbanera Lecture Notes on Tail Recursion and call/cc (file html, aggiornato al 19 Dic 07)
• [HPR] F. Honsell, A. Pravato, S. Ronchi della Rocca, "Structured Operational Semantics of a fragment of the language Scheme". file ps (31 pages). (Only the first 10 pages to be used; set! and begin expressions must be skipped)
• [HASK] Reading Material on Haskell
  • Haskell main concepts ( ps file, 21 pages). (it is the copy of this (file ps), but with the answers left blank.)
  • Notes on Haskell Laziness e Polymorphism ( ps file ), Inductive types in Haskell ( ps file ), Laziness ( ps file ), Haskell Type Inference ( ps file it is written that what it is shown is the type inference algorithm of Haskell, but what it is really shown is only the type unification algorithm.)
• [Scheme] For what concerns the language Scheme, any Scheme manual is ok. Among the many possibilities you can find those listed below.

Some Scheme manuals:

• AA.VV. "How to Design Programs, An Introduction to Programming and Computing", text on programming in SCHEME in electronic format, downloadable from How to Design Programs
• The Scheme programming language by Ken Dickey, introductory text available at text format
• Teach Yourself Scheme in Fixnum Days Another introductory textbook on Scheme.
• R. Kent Dybvig, The Scheme Programming Language, 3rd Edition. Online edition of a complete textbook. (The 2nd edition is available also in pdf format ; by C.Pistagna)

Scheme Interpreters

• A good Scheme  interpreter  (DrScheme) can be downloaded from  http://www.plt-scheme.org
   
• There exist many other interpreters for Scheme, for example the MITscheme, downloadable from  http://www.swiss.ai.mit.edu/projects/scheme/ together with links to other implementations (suggested by di C. Pistagna).

Optional Reading Material

• [CH] F. Cardone, R. Hindley, Storia del lambda-calcolo ( file .ps of a few introductory pages.)
• [AV] AA.VV., "Handbook of Theoretical Computer Science", Volume B, Formal Models and Semantics, Elsevier, 1990, Cap. 7 (Functional Programming and Lambda Calculus) by H.P. Barendregt.
• [H] P.Hudak, Two dozen Short Lessons on Haskell (file ps.gz version with blank answers(150 pag.), (file ps.gz version with answers, 150 pag.)
• [J] M.Jones, Introduction to Gofer (file ps.gz) (122 pag.).
• Short Introduction to Functional Programming using Scheme file html (based on part of the material of [PE] and the notes of the course)

A few Interesting Links

• The schemers homepage (recommended!)
• The Haskell Homepage
• Functional Programming in the real world
• Links about SCHEME
• Perche' studiare Scheme (By G. Patane')