2 Interpreting Programs🔗

Last time we saw CalcLang, syntax trees, and an interpreter for a calculator program. In this lecture we will break these ideas down further and more methodically explore them.

2.1 Parsing and Grammars🔗

Recall our CalcLang abstract syntax datastructure from last lecture. For this class, we’ll add a few other operations: subtraction and multiplication.

> (define-type CalcLang     (numE [value : Number])     (addE [e1 : CalcLang] [e2 : CalcLang])     (mulE [e1 : CalcLang] [e2 : CalcLang])     (subtractE [e1 : CalcLang] [e2 : CalcLang]))

Elements of the AST that have children are called non-terminal; for example, addE, mulE, and subtractE are non-terminal. Conversely, elements of the AST that have no children are called terminal; numE is the only terminal. By convention, children of non-terminals are drawn left-to-right: so, the left child of the tree node for (addE (addE (numE 1) (numE 2)) (numE 3)) is the tree node for (addE (numE 1) (numE 2)) (numE 3).

2.1.1 Grammars🔗

Parsing translates surface syntax into abstract syntax.

Perhaps the easiest surface syntax to parse is s-expressions. For example, the surface syntax "(+ (+ 1 2) 3)" parses to the AST (addE (addE (numE 1) (numE 2)) (numE 3)).

There are other kinds of surface syntax one might want to use. The one you’re maybe most familiar with is infix surface syntax, which lets you write surface syntax that looks like this: "1 + 2 * 3". You learned in grade school that multiplications "happens before" addition. We will formalize this notion by saying that multiplication binds more tightly than addition, so that we would parse the above expression into the following parse tree:

Infix surface syntax has parenthesis that tell you explicitly which terms get bound where. For example, "1 * (2 + 3)" is parsed as:

Clearly as langauges get more complicated there will be lots of rules about how to translate various surface syntax into abstract syntax. These rules are summarized by a grammar. The following grammar gives the rules for parsing s-expressions into CalcLang:

	‹expr›	::=	‹number›
		|	( + ‹expr› ‹expr› )
		|	( - ‹expr› ‹expr› )
		|	( * ‹expr› ‹expr› )
	‹number›	::=	A number constant

Figure 1: S-expression CalcLang grammar.

The grammar defines the non-terminal ‹expr›, which is an expression in CalcLang. Each vertical bar denotes one possible way of forming expression; we call these production rules. A lexeme is a string from the surface syntax; the lexemes above are highlighted (for instance, the open paren "(" is a lexeme).

Now we can learn the algorithm for using grammars to parse strings by example.

Consider the following surface syntax string: "10". This only matches one production rule, the one for ‹number›, so this parses to (numE 10).

Now consider the string surface syntax "(+ (+ 1 2) 3)". We attempt to parse one lexeme at a time. The first lexeme is (, so this cannot be a number; it must be one of the other productions. So we move onto the next lexeme, which is +. This matches the production for addition. The rule for parsing addition tells us that we should try to parse two sub-expressions, so we recursively attempt to parse "(+ 1 2)" and "3" into expressions. So, we end up with the abstract syntax (addE (addE (numE 1) (numE 2)) (numE 3)) as the parsed expression.

2.1.2 Infix Grammar for CalcLang🔗

Now we can give the alternative infix grammar for how to parse calculator syntax into abstract syntax:

	‹expr›	::=	( ‹expr› )
		|	‹expr› * ‹expr›
		|	‹expr› + ‹expr›
		|	‹expr› - ‹expr›
		|	‹number›
	‹number›	::=	A number constant

Figure 2: S-expression CalcLang grammar.

By convention we assume rules are applied in the order that they appear in the grammar; this gives parenthesis and multiplication priority over addition and subtraction, which we expected from our PEMDAS rules. This grammar seems reasonable, but it is tricky: what does the surface syntax "1 + 2 + 3" parse to? This is an example of ambiguity. From the above grammar, there are two valid parse trees for this expresion:

and

To resolve this amibuity, we will specify the binding order of our operations. We say binary operations bind to the left, meaning that we prefer the second tree to the first. Sometimes it makes sense to bind to the right; then, we would prefer the first tree.

This complexity with binding order and ambiguity is a good reason to prefer s-expressions for programming language syntax.

In general there are many tools for generating parsers these days from specifications like the grammars we showed you here. We won’t spend much of this class focusing on the implementation of parsers themselves.

2.2 The Stepper: Simplifying Calculator Programs🔗

We saw last time how to give a semantics to calculator programs using Plait as a metalanguage. Let’s extend our interpreter from last time to handle the new operations:

> (define (interp-calc e)     (type-case CalcLang e                [(numE v) v]                [(addE e1 e2) (+ (interp-calc e1)                                 (interp-calc e2))]                [(subtractE e1 e2) (- (interp-calc e1)                                      (interp-calc e2))]                [(mulE e1 e2) (* (interp-calc e1)                                 (interp-calc e2))]))

> (test (interp-calc (addE (numE 1) (numE 2)))         3)

- Void good (interp-calc (addE (numE 1) (numE 2))) at line 4   expected: 3   given: 3

> (test (interp-calc (subtractE (addE (numE 1) (numE 2)) (numE 3)))         0)

- Void good (interp-calc (subtractE (addE (numE 1) (numE 2)) (numE 3))) at line 5   expected: 0   given: 0

One of the themes we’ll see in this class is that there are many ways to run programs that have uses in different contexts. Here we’ll see another way to interpret CalcLang programs that is more like how you learned to calculate in high school: by simplification.

If you are given a big expression like "1 + ((2 * 3) + 7)", the way that you usually approach solving it is by simplifying it in pieces, like:

Each line of the above computation is a step of simplification. We can design an alternative interpreter for CalcLang that works more like this style of reasoning that progressively simplifies programs until there is no work left to do.

Let’s start by making a simplify function that takes one step of simplification. There are of course many different orders in which simplification can occur; let’s pick one and see the consequences, focusing only on addition for now:

> (step : (CalcLang -> CalcLang))

> (define (step e)     (type-case CalcLang e                [(numE v)                 (numE v)]                [(addE e1 e2)                 (type-case CalcLang e1                            [(numE v1)                             (type-case CalcLang e2                                        [(numE v2)                                         (numE (+ v1 v2))]                                        [else (addE (numE v1) (step e2))])]                            [else (addE (step e1) e2)])]                   [(mulE e1 e2)                 (type-case CalcLang e1                            [(numE v1)                             (type-case CalcLang e2                                        [(numE v2)                                         (numE (* v1 v2))]                                        [else (mulE (numE v1) (step e2))])]                            [else (mulE (step e1) e2)])]                 [(subtractE e1 e2)                  (type-case CalcLang e1                             [(numE v1)                              (type-case CalcLang e2                                         [(numE v2)                                          (numE (- v1 v2))]                                         [else (subtractE (numE v1) (step e2))])]                             [else (subtractE (step e1) e2)])]))

Let’s step the program (+ (+ 1 2) (+ 3 4)) until it’s fully evaluated:

> (step (addE (addE (numE 1) (numE 2)) (addE (numE 3) (numE 4))))

- CalcLang

(addE (numE 3) (addE (numE 3) (numE 4)))

> (step (addE (numE 3) (addE (numE 3) (numE 4))))

- CalcLang

(addE (numE 3) (numE 7))

Notice how with each step a particular part of the program is simplified. We arbitrarily chose to simplify the left expression first, and then the right expression.

Now we can define a function run that steps a program until it reaches a fixed point (i.e., it does not change):

> (step-interp : (CalcLang -> CalcLang))

> (define (step-interp e)     (let [(stepped-e (step e))]       (if (equal? stepped-e e)           e           (step-interp stepped-e))))

> (test (step-interp (addE (numE 1) (numE 2))) (numE 3))

- Void good (step-interp (addE (numE 1) (numE 2))) at line 12   expected: (numE 3)   given: (numE 3)

> (test (step-interp (addE (addE (numE 1) (numE 2)) (numE 3))) (numE 6))

- Void good (step-interp (addE (addE (numE 1) (numE 2)) (numE 3))) at line 13   expected: (numE 6)   given: (numE 6)

> (test (step-interp (addE (addE (numE 1) (numE 2))                            (addE (numE 3) (numE 4)))) (numE 10))

- Void good (step-interp (addE (addE (numE 1) (numE 2)) (addE (numE 3) (numE 4)))) at line 14   expected: (numE 10)   given: (numE 10)

> (test (step-interp (subtractE (addE (numE 1) (numE 2)) (numE 3))) (numE 0))

- Void good (step-interp (subtractE (addE (numE 1) (numE 2)) (numE 3))) at line 15   expected: (numE 0)   given: (numE 0)

We call the above interpreter a small-step interpreter. The key is that the small-step and definitional interpreters always agree on the value that all programs run to. We will see more of the small step interpreter as we progress through the course, but for now, the key takeaway is that there is more than one way of evaluating a program. The small step interpreter makes each step of computation very explicit, and seems to correspond closely to how a computer might execute the above program. The definitional interpreter seems to be the most straightforward implementation strategy.

2.3 IfLang: Adding Conditionals🔗

Now, let’s grow our little language by adding conditionals; we will call this langauge IfLang. We will use the following abstract syntax:

> (define-type IfLang     (numI [value : Number])     (addI [e1 : IfLang] [e2 : IfLang])     (ifI [guard : IfLang] [thn : IfLang] [els : IfLang]))

Notice, IfLang does not have any Booleans. This doesn’t stop us from giving a semantics for ifE, though. Let’s choose a meaning: if guard evaluates to a non-zero value, then evaluate the then branch; otherwise, evaluate the else branch. We can implement this semantics in a definitional interpreter:

> (interp-if : (IfLang -> Number))

> (define (interp-if e)     (type-case IfLang e                [(numI v) v]                [(addI e1 e2) (+ (interp-if e1) (interp-if e2))]                [(ifI guard thn els)                 (if (not (equal? (interp-if guard) 0))                     (interp-if thn)                     (interp-if els))]))

> (test (interp-if (ifI (numI 0)                         (numI 10)                         (numI 20)))         20)

- Void good (interp-if (ifI (numI 0) (numI 10) (numI 20))) at line 19   expected: 20   given: 20

Notice here that our object language (IfLang) has a different semantics for conditionals than our last language (Plait), even though we make use of Plait’s if construct to give a semantics to IfLang’s. This is often the case when making interpreters, and we’ll see more examples of this.