Advanced Topics in Functional Programming

Code:

CC4028

Acronym:

CC4028

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2019/2020 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pbv/aulas/tapf
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master in Computer Science

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M:CC	4	Study plan since 2014/2015	1	-	6	42	162
MI:ERS	3	Plano Oficial desde ano letivo 2014	4	-	6	42	162

Teaching language

Suitable for English-speaking students
Obs.: All course materials are in english. English exams will be provided if required.

Objectives

Stengthening functional programming skills with emphasis em advanced techniques for improving modularity e correctness in software construction.

Learning outcomes and competences

At the end of this unit students should be able to:

1. understand the concept of type class and its translation using dictionary-passing;


2. understand algorithmic properties and complexity for basic purely-funcitonal data structures (e.g. lists and search trees)


3. know fundamental algebraic structures used for structuring functional programs such as semigroups, monoids, monads, functors and applicative functors;


4. understand how to use and implement functional parsers using combinators;


5. understand the concept of property-based testing and be able to write properties and generators using the QuickCheck library;


6. understand the concept of an embedded domain-specific language (EDSL) and be able to implement simple EDSLs in Haskell (e.g. mathematical and geometric problems).

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Functional programming course (such as CC1005).

Program

Review of the Haskell language.

Purely-functional data structures; imutability and sharing of sub-structures. Operational view and asympotic cost of execution for purely-functional programs. Worst-case complexity for some familiar data structures (e.g. lists and binary search trees).

Parametric polymorphism and "ad-hoc" polymorphism. Type classes. Type checking and type inference.

Specific type classes for structuring functional programs: monads, functors and applicative functors.

Monadic programming: partiality, state, non-determinsm, readers and writers. Monadc parsing. Monad transformers. Functors and applicatives.

Some case studies of programming with monads and applicatives: defining functional parsers using combinatores. The Parsec library.  

Property-based testing. Specifying properties and generators using the QuickCheck library. Automatic simplification of counter-examples ("shrinking").

Design and implementation of domain-specific languages (DSELs). Shallow and deep embeddings.

Mandatory literature

Graham Hutton; Programming in Haskell. ISBN: 978-0-521-69269-4
Miran Lipovaca; Learn you a Haskell for Great Good!, 2011 (http://learnyouahaskell.com/)

Complementary Bibliography

Bryan O'Sullivan, John Goerzen, Don Stewart; Real World Haskell, O'Reilley, 2008 (http://book.realworldhaskell.org/read/)

Comments from the literature

References on specific topics will be given during the course as articles and lectures notes.

Teaching methods and learning activities

Lectures and demonstration classes combining concept exposure, interactive examples and supervision of practical assignments.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	60,00
Trabalho prático ou de projeto	40,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	84,00
Frequência das aulas	42,00
Trabalho laboratorial	36,00
Total:	162,00

Eligibility for exams

N/A

Calculation formula of final grade

The final grade for aproval is obtained as:

40% (Grade on practical assignments) + 60% (Written exam grade)

Futhermore, a minimum of 40% on the written exam is required for aproval.

The above formula holds for both aproval, appeal  and grade improvement and special epochs.

Special assessment (TE, DA, ...)

The final grade for aproval is obtained as:

40% (Grade on practical assignments) + 60% (Written exam grade)

Futhermore, a minimum of 40% on the written exam is required for aproval.

The above formula holds for both aproval, appeal  and grade improvement and special epochs.

Classification improvement

The final grade for aproval is obtained as:

40% (Grade on practical assignments) + 60% (Written exam grade)

Futhermore, a minimum of 40% on the written exam is required for aproval.

The above formula holds for both aproval, appeal  and grade improvement and special epochs.

Observations

Requires CC1005 "Programação Funcional" (or equivalent)