Lecturer(s)


Bartl Eduard, RNDr. Ph.D.

Course content

Pure lambda calculus: lambdaterms, term structure, equivalence theory. Reduction: transformations, general reduction, betareduction. Functional programming and Common LISP, Haskell and ML programming languages. Pure lambda calculus: lambdacomputability, undecidable properties of lambda calculus. Pure lambda calculus and functional programming: arithmetic, logic functions, recursion, fixedpoint combinators. Modification of theory: combinatory logic, extensionality, etaconversion. Typed lambda calculus: types and terms, normal forms, set models, strong norability, types as formulae. Typed lambda calculus implementation.

Learning activities and teaching methods

Lecture, Demonstration

Learning outcomes

The students become familiar with basic concepts of lambda calculus and functional programming.
1. Knowledge Describe and understand principles of lambda calculus and functional programming.

Prerequisites

unspecified

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.

Graham, P. (1995). ANSI Common LISP. Prentice Hall.

Hansen, M. R, Rischel, H. (1999). Introduction to Programming using SML. AddisonWesley.

Hutton, G. (2007). Programming in Haskell. Cambridge University Press.

Leeuwen, J. van (ed.). (1994). Handbook Of Theoretical Computer Science: Formal Models and Semantics. Volume B, Elsevier.

Zlatuška J. (1993). Lambdakalkul. Vydavatelství MU, Brno.
