Semester: winter 2023/24
Lectures: Monday 12:20-15:20 (every other week), S9 (Tomáš Petříček)
Page in SIS: NPRG077
Grading: Credit

The goal of this course is to teach how fundamental programming language techniques, algorithms and systems work by writing their miniature versions. The course covers multiple paradigms including functional, object-oriented, imperative and logic, as well as end-user programming environments like spreadsheets. Examples will be given using the F# programming language, which will be briefly introduced.

The course will be taught in alternating years with Programming language design (NPRG075). It will not run in 2024/25.

Video materials

Welcome lecture: Write your own tiny programming system(s)!

Lecture: 9 October, 12:20 (S5)
Slides: Web-based or PDF format
Code: Demos from the lecture

Lab - TinyML: Tiny functional programming language interpreter

Watch before: 16 October, 12:20 (S9)
Slides: Web-based or PDF format
Code: Demos and tasks for you!

Lab - TinyBASIC: Tiny imperative interactive programming system

Watch before: 30 October, 12:20 (S9)
Slides: Web-based or PDF format
Code: Demos and tasks for you!

Lab - TinyHM: Tiny Hindley-Milner type inference algorithm

Watch before: 13 November, 12:20 (S9)
Slides: Web-based or PDF format
Code: Demos and tasks for you!

Lab - TinyProlog: Tiny declarative logic programming language

Watch before: 27 November, 12:20 (S9)
Slides: Web-based or PDF format
Code: Demos and tasks for you!

Lab - TinySelf: Tiny prototype-based object-oriented programming system

Watch before: 11 December, 12:20 (S9)
Slides: Coming soon
Code: Coming soon!

Course format

Beware! The course is not a classic 1.5 hour lecture.

I want the course to be as hands-on and interactive as possible. Rather than doing classic 1.5 hour lectures, I want us to spend most of the time actually writing and discussing code. For this reason, the course will meet every other week for a longer 180 minute (2 * 90 minute) session.

Watch the pre-recorded lectures before the lab!

I will also give you a pre-recorded short lecture to watch before the lab. This will explain the concepts we will be implementing and the code we will be using as the starting point, so you need to watch this before coming to the lab. There is no pre-recorded lecture for the first meeting. We will start with a regular live in-person lecture.

Bring your own laptop with F# installed.

The course is scheduled in a lab (SW1), but I expect most attendees will want to bring their own laptops. To use your own machine, you will need to install F#. Follow the instructions from the F# Software Foundation page. Writing F# is much easier with a decent editor. Visual Studio Code with the Ionide extension is a good choice.

Use whatever programming language you want.

I will give you code samples in F#, because F# features like discriminated unions and pattern matching make writing tiny programming systems very easy (and I happen to like F#). I will briefly introduce F# in the first lab. You are welcome to use whatever language you like, but it may be more work - you will need to reimplement my F# starting point code. (But comparing how things look in different languages would definitely be fun!)

Do you need to attend remotely?

Please email me at! If there is interest, I may be able to offer remote consultations in addition to in-person labs. Those would be shorter and less interactive, so you would need to do more work on your own.

Lectures and labs

The first lecture will be a regular 90 minute lecture. For the rest of the course, I will ask you to have a look at a brief pre-recorded lecture (maybe 30 minutes) in advance. We will then work together in a lab on completing and adding features to the system implementation.

  • 9 October, 12:20-13:50 (room S5) - Welcome lecture
    Write your own tiny programming system(s)!

  • 16 October, 12:20-15:20 (room S9) - Hands-on lab
    TinyML: A tiny functional programming language interpreter

  • 30 October, 12:20-15:20 (room S9) - Hands-on lab
    TinyBASIC: Implementing a tiny Commodore 64 BASIC and dealing with GOTO

  • 13 November, 12:20-15:20 (room S9) - Hands-on lab
    TinyML: Writing the Hindley-Milner type inference algorithm

  • 27 November, 12:20-15:20 (room S9) - Hands-on lab
    TinyProlog: Tiny logic programming language with unification and resolution

  • 11 December, 12:20-15:20 (room TBC) - Hands-on lab
    TinySelf: Creating a small object-oriented programming system

  • Date TBC, 12:20-15:20 (room TBC) - Hands-on lab
    TinyExcel: Implementing reactive graph-based computations

Credit / zápočet

The credit (zápočet) will be awarded for active participation in the course. Students will complete a number of exercises throughout the course such as adding new features to the discussed miniature implementations.

Course outline

The course will cover a range of techniques, algorithms and systems relevant to imperative, functional, object-oriented as well as other programming paradigms. The content will be adapted based on the interests of the students. A typical syllabus would include topics such as the following:

Imperative programming

Functional programming

Object-oriented programming

Other programming techniques