Teaching (After 2018)

Below are materials of recent courses that I taught, for which I created materal that might be interesting to someone.

Programming Languages

• Introduction to Python, with an explanation where Python stands in the landscape of programming languages.
• Basics of Python.
• Iterators in Python.
• Matching in Python. Matching was added to Python in 2022. It is an essential language construct, used in functional languages, and perhaps it will be added to C++ some beautiful day.
• Object-Orientation in Python. These slides were used only partially, because I think that the object mechanism in Python is useless. At the end, they contain an explanation of type hints.

In addition to the slides, there were exercises and assignments which I am not publishing. If you wish to see those, send me mail. These are slides on the basics of Prolog. Since the course does not only teach concrete programming languages, but also principles of programming languages, there also is a discussion on programming paradigms.

Compiler Construction

• Explanation of tokenizing. The task of the tokenizer is to group the input (a sequence of characters) into separate blocks, and classify these blocks by their type. If a block represents something that is not a string, for example a number, this number is constructed by the tokenizer.

  Tokenizing is usually separated from parsing because it is computationally much easier, and has a few requirements that are hard to express in context-free grammars (that it always creates the longest possible token, ignores comments, possibly takes indentation into account). There are two ways of obtaining a tokenizer: A tokenizer can be written by hand, which seems easy at first but the pain will come later. It is better to use a tool, which means that one has to read a manual, and prepare some starting code. This creates some additional effort in the beginning, but much less in long term. Of course, I shamelessly promote my own great tool, and force students to use it in exercises.

• Explanation of parsing. The purpose of parsing is to transform the output of the tokenizer into a tree structure, which represents the structure of the program at hand. As with tokenizing, one can either write a parser by hand, or use a parser generator.

  Writing a parser by hand is doable if one knows how to do it, and may sometimes be the better option. In these slides I give a general approach: One needs to write a set of parse functions, one for each left hand side symbol, that recursively call each other. This approach is called recursive descent parsing. It is nearly always necessary to modify the grammar because when there rules with the same left hand side, whose right hand sides can start with overlapping terminal symbols, one does not know which rule to select. The easiest way to modify the grammar, is by allowing regular expressions in right hand sides of grammar rules. There is no general algorithm how to adapt the grammar, but I give examples. I also explain how I think that bottom-up parsing should be implemented.

  In most cases, using a parser generator is better than writing the parser by hand. The initial cost of reading documentation, and preparing some required code interface pays off in long term. Once it is set up, extending the grammar or making changes is easy. I explain theory and practice of bottom-up parsing, and promote Maphoon of course.

• After parsing comes the actual translation. I first explain how simple, untyped expressions are translated into a stack/register machine. Expressions are evaluated in registers (variables of simple types without address), while local variables are stored on the stack (more complex and having an address). This approach will later be generalized to the full C-language. Slides are here.
• The C-language has a couple of peculiar features, which I consider breakthroughs in programming language design: Arrays decay into pointers (so that size is no longer part of the type), assignability of an expression is determined by its type instead of its syntactic category, and the pointer arithmetic. All this features make type checking a bit harder. The slides explain the basics of type checking for the C-language. Type checking is always combined with overload resolution and insertion of implicit conversions.
• Once types have been determined and conversions insersted, expressions can be translated into intermediate representation. Before this can be done, the stack/register machine introduced earlier must be modified to support types. After that, translation is mostly an administrative task: These are the slides.
• One lecture is spent to LLVM. LLVM is an intermediate representation that is well-designed, well-documented, and frequently used. Here are slides. LLVM is quite close to the stack/register machine that I used in the course.
• I dedicate one lecture to basics of optimization, but I have no good slides for this part. I explain the basics of abstract interpretation.

Theory of Computation

1. First part covered the polynomial complexity classes P and NP, the notion of NP-completeness, NP-completeness of the SAT problem, polynomial reductions and some more examples of NP-complete problems. All of this is standard theory. Slides are based on the Garey and Johnson book.
2. In the second part, I covered lambda calculus. I explained untyped lambda calculus, the fact that lambdas are invisibly all around us, for example in integrals or differentials. Next I explained how to define recursive datatypes in lambda calculus, like natural numbers, lists, partial objects, and pairs. After that, I introduced typed lambda calculus and demonstrate the Hindley/Milner type algorithm. I believe most descriptions of the HM type checking algorithm on the internet are incomplete, but my description is correct.
3. Third part covered some data structures not covered in our regular courses on complexity theory: Priority queues and red-black trees. I explain that red-black trees are a clever way of implementing 234 trees, when nodes of variable length are implemented as linked lists.