The objective of this course is to illustrate the basic principles, the techniques, and the tools for programming computer applications through the presentation of the concepts typical of declarative programming of logical nature and functional nature and their comparison with those of imperative programming.

01. Introduction to Programming Paradigms and Languages
  01.01 Basic Definitions for Paradigms and Languages
  01.02 Imperative Programming: Procedural and Object Oriented
  01.03 Declarative Programming: Functional and Logic
  01.04 Sequential and Concurrent Programming Languages
  01.05 Script, Query, Markup, Modeling Languages

02. Discrete Mathematics Background
  02.01 Elements of Set Theory
  02.02 Relations, Functions, Operations
  02.03 Induction Principle

03. Lambda Calculus
  03.01 Syntax of Lambda Calculus
  03.02 Semantics of Lambda Calculus and Combinatory Logic
  03.03 Recursion and Computability in Lambda Calculus
  03.04 Termination and Confluence in Lambda Calculus
  03.05 Lambda Calculus with Types

04. Functional Programming: The Language Haskell
  04.01 From Lambda Calculus to Functional Programming
  04.02 Haskell: Assembling Functional Characteristics
  04.03 Haskell: Expressions, Data Types, Type Classes
  04.04 Haskell: Functions, Guards, Pattern Matching
  04.05 Haskell: Polymorphic, Higher-Order, Anonymous Functions
  04.06 Haskell: Lazy Evaluation, Input/Output, Modules

05. Propositional Logic
  05.01 Syntax of Propositional Logic
  05.02 Semantics and Intractability of Propositional Logic
  05.03 Consequence and Equivalence in Propositional Logic
  05.04 Algebraic Properties of the Logical Connectives
  05.05 Deduction Systems for Propositional Logic

06. Predicate Logic
  06.01 Syntax of Predicate Logic
  06.02 Semantics and Undecidability of Predicate Logic
  06.03 Consequence and Equivalence in Predicate Logic
  06.04 Algebraic Properties of the Quantifiers
  06.05 Deduction Systems for Predicate Logic

07. Refutation of Logical Formulas
  07.01 Normal Forms for Propositional and Predicate Logic
  07.02 Unification of Predicate Logic Formulas
  07.03 Herbrand Theory and Refutation Algorithm
  07.04 Robinson Resolution and Refutation Algorithm

08. Logic Programming: The Language Prolog
  08.01 From Logic to Logic Programming
  08.02 Prolog: Horn Clauses and SLD Resolution Strategy
  08.03 Prolog: Syntax of Terms and Predefined Predicates
  08.04 Prolog: Negation, Cut, Input/Output, Advanced Predicates

09. Laboratory Activities in Linux
  09.01 The Compiler/Interpreter ghci
  09.02 Implementation and Modification of Haskell Programs
  09.03 The Compiler/Interpreter gprolog
  09.04 Implementation and Modification of Prolog Programs

There are no mandatory prerequisites. It is recommended to take the exam of Logic and Functional Programming after taking the exam of Logic, Algebra and Geometry, the exam of Procedural Programming, and the exam of Algorithms and Data Structures.

Knowledge and understanding
The student will complete the fundamental knowledge in the field of computer programming, acquired in the previous two years with respect to the imperative paradigm of procedural nature and object-oriented nature, with that related to the declarative paradigm of logical nature and functional nature exemplified through the languages Prolog and Haskell respectively. The student will first deepen the knowledge of propositional and predicate logic introduced in the first year and will learn about the basis of the lambda calculus as foundation of functional programming.

Applying knowledge and understanding
The student will be able to design and develop software systems by means of the application of a methodology introduced in the first year that covers problem analysis, algorithm design, and program implementation, testing, verification, and maintenance, where the implementation phase will be carried out through a declarative programming language of logical or functional nature.

Making judgements
The student will be able to evaluate and compare alternative designs of the same software system, as well as to analyze and contrast alternative implementations in an imperative or declarative language of the same software design.

Communication skills
The student will be able to appropriately use the terminology of declarative programming languages of logical nature and functional nature. Furthermore, the student will know how to illustrate the main characteristics of the design and the implementation in a declarative language of a software system, including the production of the software system documentation in terms of technical report, internal comments, and user manual.

Learning skills
The student will acquire the ability of learning the syntactical and semantical features of any declarative programming language of logical nature and functional nature.

The teaching material prepared by the lecturer in addition to recommended textbooks (such as for instance slides, lecture notes, exercises, bibliography) and communications from the lecturer specific to the course can be found inside the Moodle platform › blended.uniurb.it

Teaching

Theory lectures and laboratory exercises.

Attendance

Although strongly recommended, course attendance is not mandatory.

Course books

Barendregt, "The Lambda Calculus: Its Syntax and Semantics", North Holland, 2014.

Thompson, "Haskell: The Craft of Functional Programming", Addison-Wesley, 2011.

Schöning, "Logic for Computer Scientists", Birkhäuser, 2008
(Asperti, Ciabattoni, "Logica a Informatica", McGraw-Hill, 1997).

Sterling, Shapiro, "The Art of Prolog", MIT Press, 1997
(Console, Lamma, Mello, Milano, "Programmazione Logica e Prolog", UTET, 1997).

Gabbrielli, Martini, "Programming Languages: Principles and Paradigms", Springer, 2010
(Gabbrielli, Martini, "Linguaggi di Programmazione: Principi e Paradigmi", McGraw-Hill, 2011).

Assessment

Project, written exam, and oral exam.

The project, which has to be developed by groups composed of at most two students on a problem agreed upon with the lecturer, consists of implementing a Haskell program and a Prolog program for that problem by following the methodology for developing software "in the small" presented in the course of Procedural Programming. The project has to be submitted at least 10 days before the written exam; in case of late submission, a 3/30 penalty is applied for each day after the deadline. Should the project be resubmitted in a subsequent exam call, the mark of the previously submitted project is canceled; project resubmission in the same exam session can take place only once per session and in this case a 4/30 penalty is applied to the mark of the newly submitted project because the developers can benefit from the correction of the previously submitted project. The project is passed if the mark is at least 18/30; the mark is valid, even if the written or oral exam is taken but not passed, until the third exam session after the one in which the project is submitted.

The written exam, which changes at each exam call and can be taken only if the project has been passed, consists of 8 questions plus 2 exercises to carry out in 90 minutes. It is passed if the mark is at least 18/30; the mark is valid only for the exam call in which the written exam is taken.

The oral exam, which can be taken only if the project and the written exam have been passed, consists of a discussion of the project and of the written exam, plus further questions. If passed, it determines an adjustment between -5/30 and 5/30 of the average of the two previous marks, thus yielding the final mark.

For further information › www.sti.uniurb.it/bernardo/teaching/prog_logi_funz/

Disability and Specific Learning Disorders (SLD)

Students who have registered their disability certification or SLD certification with the Inclusion and Right to Study Office can request to use conceptual maps (for keywords) during exams.

To this end, it is necessary to send the maps, two weeks before the exam date, to the course instructor, who will verify their compliance with the university guidelines and may request modifications.