IA081 Lambda calculus

Faculty of Informatics
Spring 2009
Extent and Intensity
2/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Jiří Zlatuška, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Jiří Zlatuška, CSc.
Timetable
Mon 10:00–11:50 B411
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
there are 15 fields of study the course is directly associated with, display
Course objectives
This course contains basic techniques and results of the theory of sequential functions as described by the lambda-calculus and combibatoru logic. The course contains the typed and untyped version of the formalism, as well as basic results concerning models of lambda-calulus. Course objectives: Lambda-calculus is important for understanding recursive constructs used in programming as well in the corresponding semantics constructs, and it provides a reference formalism useful for variaous applications.
Syllabus
  • Pure lambda-calculus: lambda-terms, structure of terms, equational theories.
  • Reductions: one-way transformations, general reductions, beta-reduction.
  • Lambda-calculus and computations: coding, recursive definitions, lambda-computability, fixed-point combinators, undecidable properties.
  • Modification of the theory: combinatory logic, extensionality, eta-reduction.
  • Typed lambda-calculus: types and terms, normal forms, set models, strong normalization, types as formulae.
  • Domain models: complete partial orders, domains, least fixed points, partiality.
  • Domain construction: compound domains, recursive domain construction, limit domains.
Literature
  • ZLATUŠKA, Jiří. Lambda-kalkul. 1. vyd. Brno: Masarykova univerzita, 1993, 264 s. ISBN 8021008261. info
  • BARENDREGT, H. P. Lambda calculus : its syntax and semantics. Rev. ed. Amsterdam: Elsevier, 1998, xv, 621 s. ISBN 0-444-86748-1. info
  • HINDLEY, J. Roger and J. P. SELDIN. An Introduction to Combinators and the (lambda)-calculus. Cambridge: Cambridge University Press, 1986, 360 s. ISBN 0521318394. info
  • AMADIO, Roberto M. and Pierre-Louis CURIEN. Domains and Lambda calculi. Cambridge: Cambridge University Press, 1998, xvi, 484. ISBN 0521622778. info
Assessment methods
The course is based on the lectures and individual study of assigned literature. Exam: individual written essay, and a subsequent oral exam.
Language of instruction
English
Further comments (probably available only in Czech)
The course is taught once in two years.
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2008, Spring 2010, Spring 2012, Spring 2015, Spring 2017, Spring 2019, Spring 2020, Spring 2022, Spring 2024.
  • Enrolment Statistics (Spring 2009, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2009/IA081