Course: Functional Programming

« Back
Course title Functional Programming
Course code KMI/PGSFP
Organizational form of instruction Lecture
Level of course Doctoral
Year of study not specified
Semester Winter and summer
Number of ECTS credits 12
Language of instruction Czech, English
Status of course unspecified
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
  • Vychodil Vilém, doc. RNDr. Ph.D.
Course content
Functional programming and lambda calculus: Syntax of lambda expressions and their evaluation. Function applications and currying. Lambda abstractions. Operational semantics of lambda calculus: bound and free variables, beta-conversion, alpha-conversion, interconvertibility. Rewriting systems, termination, confluence, Church-Rosser property, normal forms. Connection to the pure lambda calculus and related problems. Representation of boolean formulas, natural numbers, tuples. Computable functions: total recursive, partial recursive. Fixed point theorems, undecidable properties. Recursive functions, Y combinator as a lambda abstraction. Denotational semantics of lambda calculus. Translation of higher order functional languages into lambda calculus: let-expressions, letrec-expressions, hierarchical data types, and pattern matching. Functional programming and ordered algebras: Specification of abstract data types: heterogeneous (many-sorted) algebras, their subalgebras, morphisms, and products; principle of the finitary algebraic recursion; equational theories, many-sorted equational logic; equational specification; initial semantics and operational semantics. Ordered algebras, their morphisms and products. Varieties of ordered algebras and their characterization of free ordered algebras. Inequational logic. Strict ordered algebras, omega-ordered algebras. Recursive programming schemes and their semantics, computed values, symbolic solutions, semantic equivalence. Stack model of evaluation of symbolic expressions: Functional programs as sequences of symbolic expressions. Stack model of evaluation. Semantic language elements: primitive procedures, definable procedures, special forms (operators), macros, environments, pairs. Extensions of the evaluation process: lexical and dynamic scoping, lazy evaluation, cached evaluation, imperative features in programming, escaping functions, current continuations, indeterminism, and parallelism. Interpreters and compilers of functional programming languages and their implementation methods.

Learning activities and teaching methods
Lecture, Demonstration
  • Preparation for the Exam - 120 hours per semester
Learning outcomes
The students become familiar with basic concepts of functional programming.
1. Knowledge Describe and understand comprehensively principles and methods of functional programming.

Assessment methods and criteria
Oral exam, Written exam

Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam.
Recommended literature
  • Barendregt H. P. (1997). The Lambda Calculus: its Syntax and Semantics. 2nd reprint. Elsevier, Amsterdam.
  • Bird R., Wadler P. (1988). Introduction to Functional Programming. Prentice Hall, Englewood Cliffs, New Jersey.
  • H. Abelson, G. J. Sussman. (1985). Structure and Interpretation of Computer Programs (SICP). MIT Press.
  • Church A. (1941). The Calculi of Lambda Conversion. Princeton University Press, Princeton, NJ.
  • Leeuwen, J. van (ed.). (1994). Handbook Of Theoretical Computer Science: Formal Models and Semantics. Volume B, Elsevier.
  • Manis V. S., Little J. J. (1995). The Schematics of Computation. Prentice Hall, Englewood Cliffs, New Jersey.
  • Peyton Jones S. L. (1987). The Implementation of Functional Programming Languages. Prentice Hall.
  • Wechler W. (1992). Universal Algebra for Computer Scientists. Springer-Verlag Berlin Heidelberg.
  • Zlatuška J. (1993). Lambda-kalkul. Vydavatelství MU, Brno.

Study plans that include the course
Faculty Study plan (Version) Branch of study Category Recommended year of study Recommended semester