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

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 [email protected]! 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.

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

• Emulating prehistoric computer system (EDSAC)
• Programming with GOTO, PEEK and POKE (BASIC)

Functional programming

• Implementing a small LISP interpreter (LISP)
• Different ways of interpreting functional languages (ML)
• Writing a Hindley-Milner type inference algorithm (ML)

Object-oriented programming

• 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)

References

• 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.