2 Interpreting with Scope and Substitution
2.1 Interpreting Programs
Accept the Classroom50 assignment from here and create a github repository with your in-class work.
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.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]) (subE [e1 : CalcLang] [e2 : CalcLang]))
Skill: be able to translate between syntax trees and abstract syntax datastructures.
+ |
/ \ |
+ 3 |
/ \ |
1 2 |
Elements of the AST that have children are called non-terminal; for example, addE, mulE, and subE 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)).
2.1.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:
+ |
/ \ |
1 * |
/ \ |
2 3 |
Infix surface syntax has parenthesis that tell you explicitly which terms get bound where. For example, "1 * (2 + 3)" is parsed as:
* |
/ \ |
1 + |
/ \ |
2 3 |
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
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.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
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:
+ |
/ \ |
1 + |
/ \ |
2 3 |
and
+ |
/ \ |
+ 3 |
/ \ |
1 2 |
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.1.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))] [(subE 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 (subE (addE (numE 1) (numE 2)) (numE 3))) 0)
- Void
good (interp-calc (subE (addE (numE 1) (numE 2)) (numE 3))) at line 5
expected: 0
given: 0
See Reynolds, J. C. (1972, August). Definitional interpreters for higher-order programming languages. In Proceedings of the ACM annual conference-Volume 2 (pp. 717-740).
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:
1 + ((2 * 3) + 7) |
--> 1 + (6 + 7) |
--> 1 + 13 |
--> 14 |
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)])] [(subE e1 e2) (type-case CalcLang e1 [(numE v1) (type-case CalcLang e2 [(numE v2) (numE (- v1 v2))] [else (subE (numE v1) (step e2))])] [else (subE (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 (subE (addE (numE 1) (numE 2)) (numE 3))) (numE 0))
- Void
good (step-interp (subE (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.1.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.
2.2 Scope and Substitution
We will continue to grow our small language. Previously we ended with the if-then-else language with numbers. Next we will add Booleans and local variables to this language.
2.3 IfLang with Booleans
Recall the IfLang interpreter. Let’s continue to grow this language by extending it with Booleans, and give the usual semantics for if with Booleans. Here is the abstract syntax:
> (define-type IfLang (numI [value : Number]) (boolI [value : Boolean]) (addI [e1 : IfLang] [e2 : IfLang]) (ifI [guard : IfLang] [thn : IfLang] [els : IfLang]))
Let’s give a semantics to this by a definitional interpreter. Definitional interpreters run programs to values. However, now we have two kinds of values – Booleans and numbers – instead of just one. So, let’s add a value datatype that captures the type of values that IfLang programs can run to:
> (define-type Value (numV [v : Number]) (boolV [v : Boolean]))
Then we can define an interpreter that runs programs to values. However, we have to be careful: there are now invalid operations that this program can perform, like adding a number and a Boolean. When these occur, our interpreter should raise a runtime error. Sometimes we will specify what kind of error should be raised; other times, we can rely on our metalanguage (Plait) to raise a runtime error. Here, we opt to let Plait raise a runtime error:
> (interp-ite : (IfLang -> Value))
> (define (interp-ite e) (type-case IfLang e [(numI n) (numV n)] [(boolI b) (boolV b)] [(addI e1 e2) (let ([v1 (numV-v (interp-ite e1))] [v2 (numV-v (interp-ite e2))]) (numV (+ v1 v2)))] [(ifI guard thn els) (if (boolV-v (interp-ite guard)) (interp-ite thn) (interp-ite els))]))
Notice how if we try to run ((addI (numI 10) (boolI 20))) we get a runtime error.
2.3.1 Let Bindings
Now let’s move onto adding local variables. Our goal is for local variables to behave somewhat like Plait’s local variables, so let’s see how they behave. In Plait, you can introduce a local variable using the let function, also called a let-binding:
> (let [(myvar 10)] (+ myvar 10)) - Number
20
First, some terminology. The first argument to let is a list of binding expressions that associates identifiers with values. The name of a variable is called an identifier; in the above, myvar is an identifier. We say the identifier myvar is bound to the value 10. The body is the second argument to the let function: in the above, (+ myvar 10) is the body.
What makes a local variable local is that it is not visible outside of the body of the let expression. For instance, the following proram will raise a runtime error if you try to run it:
(let [(myvar 10)] (+ myvar 10)) (+ myvar 20)
The scope of an identifier is the portion of the program where it is visible. In Plait, the scope of an identifier for a let binding is the body of the let expression.
2.3.1.1 Shadowing
What happens when you try to redefine a local variable that has already been defined? Let’s see:
> (let [(myvar 10)] (let [(myvar 20)] myvar)) - Number
20
What happpens is that the we prefer the inner-most binding in the abstract syntax tree: this is called lexical scope, since the scope of a name depends on its position in the abstract syntax tree. We say that the inner binding code{(myvar 20)} shadows the outer binding (myvar 10). Most (but not all!) languages you’ve used have lexical scope rules that determine the scope of an identifier.
2.3.2 Substitution
Now let’s move on to understanding how we might go about implementing local variables. First, let’s define an abstract syntax tree for LetLang, a small language with let expressions:
> (define-type LetExpr [numL (n : Number)] [addL (l : LetExpr) (r : LetExpr)] [varL (s : Symbol)] [letL (var : Symbol) (assignment : LetExpr) (body : LetExpr)])
Substitution replaces an identifier in one expression with another expresion; think of it like "find-and-replace". We will give an intuitive semantics for let that involves substituting an identifier for its assignment. Let’s step some LetExpr terms to see this. Assume that we are following the same rules for stepping addL that we saw last lecture, so we can focus on how to step letE.
First example:
(letL 'x (numL 10) (addL (varL 'x) (varL 'x))) -- substitute 'x with (numL 10) --> (addL (numL 10) (numL 10)) -- simplify addL --> 20
In the above, to simplify the let, we have substituted the identifier 'x for the expression (numL 10).
The choice of whether or not to simplify a let binding before substitution has to do with eager versus lazy evaluation. Most languages you use are eager, meaning that expressions are fully simplified to values before they are substituted. But, not all languages behave this way; for instance, Haskell is famously a call-by-need langauge that does not deploy eager evaluation before substitution. We will return to these alternative evaluation schemes in a few lectures.
(letL 'x (addL (numL 10) (numL 20)) (addL (varL 'x) (varL 'x))) --> (letL 'x (numL 30) (addL (varL 'x) (varL 'x))) --> (addL (numL 30) (numL 30)) --> 60
Next, we need to carefully consider how we step in the presence of shadowing so that our lexical scoping rules are respected by the runtime behavior of the program. Concretely, the following sequence of steps should occur:
(letL 'x (numL 10) (letL 'x (numL 20) (varL 'x))) --> (letL 'x (numL 20) (varL 'x)) --> 20
Notice that in the above, after the first step of simplification, we do not replace the innermost (varL 'x) with (numL 10). This is critical so that our LetLang programs follow the lexical scoping convention of referring to the inner-most binding.
2.3.2.1 Implementing Substitution
Now we are ready to implement a funtion called subst that performs substitution in a way that respects our scoping rules:
In class, we will spend quite a bit of time discussing the various design decisions in this function and how they affect the scoping rules of your program. You should make sure to understand how changing this function affects the scoping rules of your resulting interpreter.
> (subst : (Symbol LetExpr LetExpr -> LetExpr))
> (define (subst id assignment body) (type-case LetExpr body [(numL n) (numL n)] [(addL l r) (addL (subst id assignment l) (subst id assignment r))] [(varL s) (if (symbol=? s id) assignment (varL s))] [(letL innervar innerassignment innerbody) (letL innervar (subst id assignment innerassignment) (if (symbol=? innervar id) innerbody (subst id assignment innerbody)))]))
> (test (subst 'x (varL 'x) (numL 10)) (numL 10))
- Void
good (subst (quote x) (varL (quote x)) (numL 10)) at line 29
expected: (numL 10)
given: (numL 10)
> (test (subst 'x (numL 10) (addL (varL 'x) (varL 'x))) (addL (numL 10) (numL 10)))
- Void
good (subst (quote x) (numL 10) (addL (varL (quote x)) (varL (quote x)))) at line 30
expected: (addL (numL 10) (numL 10))
given: (addL (numL 10) (numL 10))
> (test (subst 'x (numL 10) (letL 'x (numL 10) (varL 'x))) (letL 'x (numL 10) (varL 'x)))
- Void
good (subst (quote x) (numL 10) (letL (quote x) (numL 10) (varL (quote x)))) at line 31
expected: (letL 'x (numL 10) (varL 'x))
given: (letL 'x (numL 10) (varL 'x))
2.4 A Definitional LetLang Interpreter
Now that we have implemented substitution it is straightforward to implementa definitional interpreter that runs LetLang programs to values (i.e., numbers):
> (interp-let : (LetExpr -> Number))
> (define (interp-let e) (type-case LetExpr e [(numL n) n] [(addL l r) (+ (interp-let l) (interp-let r))] [(varL s) (error 'runtime "uninitialized")] [(letL id assignment body) (interp-let (subst id (numL (interp-let assignment)) body))]))
2.4.1 Dynamic Scope
A key property of our scoping rules so far is that they are static, meaning that the scope of an identifier does not depend on the runtime behavior of a program. This might seem like an obvious requirement – most languages you have used satisfy this requirement – but there are examples of languages where which variables are in-scope can depend on the runtime behavior of a program (most shell languges, for instance). This is an actual common Lisp program that prints out 5 5:
(defvar x 100) |
|
(defmethod fun1 (x) |
(print x) |
(fun2)) |
|
(defmethod fun2 () |
(print x)) |
|
(fun1 5) |
What is happening!? The defvar function introduces a special global variable x. Then, when fun1 is called, it introduces a variable x into scope, and binds it to the value 5 Then, it prints x, which has value 5 so the first 5 gets printed and seems normal. This is where things get really weird. Next, fun2 is called, which takes no arguments. It also prints x, which outputs 5, but we surely expect 100 to be printed!
This is because the scoping rules in Common Lisp are dynamic: once introduced, a variable never leaves scope, and hence variables always refers to the most recently declared identifier encountered while running the program! (Note: Common Lisp also has a local-like facility that supports lexical scope) Dynamic scope is quite unintuitive and almost certainly a bad design choice