Jeremy G. Siek - Crash Course on Notation in Programming Language Theory (Part 1) - λC 2018

Jeremy G. Siek introduces the mathematical notation used in programming language theory, covering grammars, operational semantics, and type systems.

If you have ever tried to read a paper about programming languages from an ACM conference such as Principles of Programming Languages (POPL) or the International Conference on Functional Programming (ICFP), then you're familiar with the dizzying amount of strange notation that is used in those papers. This workshop is a crash course on the most common notation used in programming language theory and the underlying ideas. The workshop will assume that the attendees are experienced programmers but not mathematicians or PL theorists. We will start with the most basic definitions and build up from there. The workshop will cover how to work with sets, tuples, relations, and inductive definitions. It will then move on to specifying language syntax with grammars. The high-point of the workshop is an introduction to operational semantics. The workshop will conclude with a introduction to type systems and the notion of a type safe programming language.