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.
Interested in doing research on programming systems?
We have funding available for PhD and post-doc positions a range of topics related to programming languages and systems starting in 2024. If you are interested in joining us in Prague, please send an informal inquiry to Tomas Petricek (email@example.com).
If you are a Matyfz student already and are thinking about staying for a PhD or doing a research-oriented Master’s project focused on programming languages, email Tomas Petricek (firstname.lastname@example.org) to arrange a meeting or stop by after a lab!
Welcome lecture: Write your own tiny programming system(s)!
Lab - TinyBASIC: Tiny imperative interactive programming system
Lab - TinyProlog: Tiny declarative logic programming language
Lab - TinySelf: Tiny prototype-based object-oriented programming system
Watch before: 11 December, 12:20 (S9)
Slides: Coming soon
Code: Coming soon!
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 email@example.com! 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.
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:
- Emulating prehistoric computer system (EDSAC)
- Programming with GOTO, PEEK and POKE (BASIC)
- Implementing a small LISP interpreter (LISP)
- Different ways of interpreting functional languages (ML)
- Writing a Hindley-Milner type inference algorithm (ML)
- Writing a minimal pure object-oriented system (Smalltalk)
- Adding reflective programming capabilities (Smalltalk)
- Class-based vs. prototype-based OO programming
Other programming techniques
- Implementing a unification algorithm (Prolog)
- Spreadsheet implementation techniques (Excel)
- Functional reactive programming techniques (Elm)
- Syme, D., Granicz, A., Cisternino, A. (2012). Expert F# 3.0. Apress.
- Nystrom, R. (2021). Crafting Interpreters. Genever Benning.
- Sestoft, P. (2014). Spreadsheet Implementation Technology: Basics and Extensions. MIT Press.
- Goldberg, A., & Robson, D. (1983). Smalltalk-80: The Language and its Implementation. Addison-Wesley
- Abelson, H., Sussman, G. J. (1996). Structure and Interpretation of Computer Programs. MIT Press.
- Appel, A. W. (2004). Modern Compiler Implementation in C. Cambridge University Press.
- Abadi, M., & Cardelli, L. (2012). A theory of objects. Springer Science & Business Media.