HackMD
(part of a course on programming languages)
A Calculator: Overview
"The form of syntax we shall now describe differs from the Backus normal form
in two ways. First, it is analytic rather than synthetic; it tells how to
take a program apart, rather than how to put it together. Second, it is abstract
in that it is independent of the notation used to represent, say sums,
but only affirms that they can be recognized and taken apart."
From the article Towards a Mathematical Science of Computation by McCarthy, which introduces the concept of abstract syntax. [1]
To understand how programming languages work, we start with a calculator. Let us really make it simple and only take addition and multiplication.
Thus, the programming language only has arithmetic expressions such as
Instead of evaluating (=interpreting) such expressions directly, we first translate them into an intermediary representation called abstract syntax. (The expression 5*((4+3)*2+1) itself is said to be in concrete syntax.) In abstract syntax we have:
Abstract syntax is meant to be processed by machines not by humans. But it becomes readable to us, if we write it as a tree.
Activity: Write Times (Num 5) (Plus (Times (Plus (Num 4) (Num 3)) (Num 2)) (Num 1)) as a tree, the so-called abstract syntax tree of the expression.
Activity: Evaluate the expression by recursion on the abstract syntax tree.
Stocktaking: At the hand of an example we have seen how to perform the following steps
Concrete Syntax ==> Abstract Syntax ==> Value
where the first step is called parsing and the second step is called evaluation or interpretation.
After doing the homework below, you should be able to do the parsing and interpretation of arithmetic expressions by hand. (Really, all we have done so far is taking a fresh look at high-school algebra.)
But how can we implement the steps above on a computer?
This is the topic of the following lectures.
We first build an interpreter that works by recursion on abstract syntax.
We then address the argument that the interpreter above translates something simple (arithmetic) into something more sophisticated (Haskell). We show how to, alternatively, build from scratch a virtual machine (VM) that can do arithmetic and then write another interpreter that evaluates abstract syntax in this VM. [2]
Finally, we learn how to write a context-free grammar for arithmetic expressions and how to use a parser generator to create a parser that translates concrete syntax into abstract syntax.
Homework (mandatory, not assessed): With pen and paper, translate the following expressions to abstract syntax and replay the two activities above.
1+2*3
(1+2)*3
(1+2)*(3+4)
((1+2*3)+4*5)*(3+4)
Today AI and Programming Languages are areas that are often thought to have little overlap. McCarthy is a founding father of both. For example, he coined both the term Artificial Intelligence and created LISP, one of the first functional programming languages. ↩︎
Granted, we run this VM also on Haskell. But this is only for convenience. The VM is defined by a set of rewrite rules that are entirely independent of Haskell. Indeed, the VM can easily be executed pen-and-paper. ↩︎
