Skip to main content

Theory of programming languages

2026/2027
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first
Kind:
optional
ECTS:
6
Language:
slovenian, english
Hours per week – 1. semester:
Lectures
3
Seminar
0
Tutorial
2
Lab
0
Prerequisites

There are no prerequisites.

Content (Syllabus outline)

The course covers the theory of programming languages with empahsis on mathematical methods for specification of programming languages and analysis of their properties. The following topics are covered:
- concrete and abstract syntax, lexical analysis and parsing as translation of concrete syntax to abstract syntax
- inductive definitions, definitions given in terms of judgements and rules of inference
- proofs by structural induction on abstract syntax and on the structure of a derivation
- inductive datatypes as an example of use of structural definitions and structural induction
- operational semantics as an inductively specified relation, small-step and big- step semantics
- functional programming languages: recursive definitions, eager and lazy languages, static analysis, type checking, safety as a consequence of progress and termination lemmas, significance of safety in practice
- polymorphism, parametric polymorphism and Hindley-Milner type inference
- imperative programming languages, specification and proofs of correctness
- denotational semantics: domains and continuous maps, existence of fixed points, denotational semantics of a functional language, interpretation of recursion as fixed points
- optional topics: object-oriented programming languages, parallel computing, logic programming.

Readings
  1. R. M. Amadio, P.-L. Curien: Domains and lambda-calculi Cambridge : Cambridge University Press, cop. 1998.
  2. B. C. Pierce: Types and programming languages, Cambridge (Mass.) : The MIT Press, cop. 200
  3. J. C. Reynolds: Theories of programming languages, Cambridge : Cambridge University Press, 1998.
Objectives and competences

The objective of the course is to present modern, mathematical approach to theory of programming languages. Students will attain the ability to analyze programming languages and the basic concepts related to them.

Intended learning outcomes

Knowledge and understanding:
Students learn how to design and analyze programming languages with formal mathematical methods.

Learning and teaching methods

lectures, tutorials, homeworks

Assessment

homework
project or written exam
5 - 10, a student passes the exam if he is graded from 6 to 10

Lecturer's references

Andrej Bauer:

– LUKŠIČ, Primož, HORVAT, Boris, BAUER, Andrej, PISANSKI, Tomaž. Practical E-Learning for the Faculty of Mathematics and Physics at the University of Ljubljana. Interdisciplinary journal of knowledge & learning objects, ISSN 1552-2210, 2007, vol. 3, str. 73-83 [COBISS-SI-ID 14269529]

– BAUER, Andrej, STONE, Christopher A. RZ: a tool for bringing constructive and computable mathematics closer to programming practice. V: Computation and logic in the real world : Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007 : proceedings, (Lecture notes in computer science, ISSN 0302-9743, 4497). Berlin, Heidelberg: Springer, cop. 2007, str. 28-42 [COBISS-SI-ID 14631769]

Matija Pretnar:

– PLOTKIN, Gordon, PRETNAR, Matija. Handling algebraic effects. Logical methods in computer science, ISSN 1860-5974, 2013, vol. 9, iss. 4, paper 23 (str. 1-36) [COBISS-SI-ID 16816729]

– PRETNAR, Matija. Inferring algebraic effects. Logical methods in computer science, ISSN 1860-5974, 2014, vol. 10, iss. 3, paper 21 (str. 1-43) [COBISS-SI-ID 17190745]

– BAUER, Andrej, PRETNAR, Matija. An effect system for algebraic effects and handlers. Logical methods in computer science, ISSN 1860-5974, 2014, vol. 10, iss. 4, paper 9 (str. 1-29). http://arxiv.org/pdf/1306.6316 [COBISS-SI-ID 17191001]

Alexander Keith Simpson:

– AWODEY, Steve, BUTZ, Carsten, SIMPSON, Alex, STREICHER, Thomas. Relating first-order set theories and elementary toposes. Bulletin of symbolic logic, ISSN 1079-8986, 2007, vol. 13, no. 3, str. 340-358 [COBISS-SI-ID 17096537]

– SIMPSON, Alex. Computational adequacy for recursive types in models of intuitionistic set theory. Annals of pure and applied Logic, ISSN 0168-0072. [Print ed.], 2004, vol. 130, iss. 1-3, str. 207-275 [COBISS-SI-ID 17117017]

– SIMPSON, Alex. A characterization of the least-fixed-point operator by dinaturality. Theoretical computer science, ISSN 0304-3975, 1993, vol. 118, iss. 2, str. 301-314 [COBISS-SI-ID 17181017]