Swedish web site
Functional and Logic programmingDF22100, 2010VT
|
|
Course plan
No of lectures
30 h
Recommended for
PdD students in computer science
The course was last given
a new course
Goals
Provide a solid introduction into the paradigms of logic programming and
functional programming.
The course presents two programming paradigms, which differ from that of
mainstream programming (i.e. procedural and object oriented). The latter can
be seen as still related to the architecture of computer hardware. Its main
concept - a mutable variable - is an abstraction of a RAM memory cell. In such
languages, roughly speaking, programs are descriptions of sequences of
computational steps. The role of the steps is to modify the state.
In contrast, programs in (pure) logic or functional programming describe the
tasks of the computations. There is no state and mutable data; this makes it
easy to reason about complex programs.
Logic programming (LP) employs (a subset of) the language of the standard first
order logic as a programming language. In principle, a program is a set of
axioms describing a problem to be solved; the computed results are logical
consequences of the program. In practice, programs also describe how the
results are computed; this can be modified by the programmer without changing
the logical meaning of the program.
Hence reasoning about the meaning of programs and their correctness
(declarative semantics) can be separated from that about program execution
(operational semantics). Efficient implementations of LP exist.
Functional programming (FP) is a programming paradigm where the central
abstraction mechanism is a function.
FP has solid mathematical foundations. Many elegant programming techniques are
specific for FP.
Compilers for modern functional languages, such as Haskell, OCaml and F#, can
today both generate highly efficient code and discover many programming errors
at compile time. FP has in the last decades mostly been used in academia, but
has lately gained an increasingly interest within industry (e.g. Erlang and
F#).
Prerequisites
Some mathematical maturity, for instance given by introductory courses on
discrete mathematics, formal languages and automata theory, and logic.
Some experience of programming; familiarity with some programming languages.
Organization
Lectures.
Exercises and project work.
Contents
[subject to modifications]
Logic Programming (LP)
- Definite clause logic programs, their declarative and operational semantics.
- Prolog as an implementation of LP.
- Programming examples, LP as a declarative programming paradigm.
- Negation in LP, including Answer Set Programming.
- Reasoning about logic programs (formal & practical).
- Extensions of "classical" LP. Constraint logic programming.
Functional Programming (FP)
Central concepts such as higher-order functions, pattern matching, dynamic vs.
static type checking, referential transparency, type inference, parametric
polymorphism, eager vs. lazy evaluation, tail-recursion, type classes, and
monads.
FP relation to lambda-calculus.
Focus on statically typed functional programming languages, e.g. OCaml and
Haskell.
Literature
Articles, handouts, book chapters.
U. Nilsson and J. Maluszynski. Logic, Programming and Prolog (2ed).
Lecturers
P. Fritzson
W. Drabent
Guest lectures and FP lab assistants:
David Broman (Strict FP, OCAML)
Henrik Nilsson (Lazy FP, Haskell)
Examiner
P. Fritzson (FP)
W. Drabent (LP)
Examination
Home assignments and a minor project.
Credit
5hp maximally for the Functional Programming part (spring).
5hp maximally for the Logic Programming part (autumn).
Comments
LADOK:
DF22100 Functional and Logic Programming, 10 hp
DF22101 Functional Programming, 5 hp
DF22102 Logic Programming, 5 hp
/Anne
Page responsible: Director of Graduate Studies
