Chapter 8 Mutable Variables and Loops
Where is this going: we want a looping construct, and if we add standard while loops we also need mutable variables.
We observe some awkwardness in the way loops are added: every expression is expected to return an integer result, but loops do not return values, they just modify state.
8.1 Recap
8.1.1 Current Grammar
<op> ::= '+' | '-' | '*' | '/'
<bop> ::= '==' | '!=' | '<' | '>' | '<=' | '>='
<atom> ::= <number>
| '('<simp>')'
| <ident>
| '{'<exp>'}'
<uatom> ::= [<op>]<atom>
<cond> ::= <simp><bop><simp>
<simp> ::= <uatom>[<op><uatom>]*
| 'if' '('<cond>')' <simp> 'else' <simp>
<exp> ::= <simp>
| 'val' <ident> '=' <simp>';' <exp>
8.1.2 Quiz
Are these syntactically valid programs?
if (3 == 5) {
2
} * 4 else 8
if (3 == 2)
val x = 3; x
else
5
Answer:
- Yes
- No: ‘val’ x = 3; x is not a simple expression
8.2 Mutable Variables
8.2.1 Syntax
<op> ::= '+' | '-' | '*' | '/'
<bop> ::= '==' | '!=' | '<' | '>' | '<=' | '>='
<atom> ::= <number>
| '('<simp>')'
| <ident>
| '{'<exp>'}'
<uatom> ::= [<op>]<atom>
<cond> ::= <simp><bop><simp>
<simp> ::= <uatom>[<op><uatom>]*
| 'if' '('<cond>')' <simp> 'else' <simp>
| <ident> '=' <simp>
<exp> ::= <simp>
| 'val' <ident> '=' <simp>';' <exp>
| 'var' <ident> '=' <simp>';' <exp>
8.2.2 AST
case class VarDec(name: String, value: Exp, body: Exp) extends Exp
case class VarAssign(name: String, value: Exp) extends Exp
8.2.3 Semantics
We can only assign to mutable variables, i.e. declared with ‘var’ (VarDec)
type Value = Int
def eval(exp: Exp)(env: ValueEnv): Val = exp match {
case VarDec(x, rhs, body) =>
eval(body)(env.withVar(x, eval(rhs)(env)))
case VarAssign(x, rhs) =>
env.updateVar(x, eval(rhs)(env)) // return the new value
}
8.3 Loops
8.3.1 Syntax
<op> ::= '+' | '-' | '*' | '/'
<bop> ::= '==' | '!=' | '<' | '>' | '<=' | '>='
<atom> ::= <number>
| '('<simp>')'
| <ident>
| '{'<exp>'}'
<uatom> ::= [<op>]<atom>
<cond> ::= <simp><bop><simp>
<simp> ::= <uatom>[<op><uatom>]*
| 'if' '('<cond>')' <simp> 'else' <simp>
| <ident> '=' <simp>
<exp> ::= <simp>
| 'val' <ident> '=' <simp>';' <exp>
| 'var' <ident> '=' <simp>';' <exp>
| 'while' '(' <cond> ')' <simp>; <exp>
8.3.2 AST
// Already defined
case class Cond(op: String, lop: Exp, rop: Exp)
case class While(cond: Cond, lbody: Exp, body: Exp) extends Exp
8.3.3 Semantics
type Value = Int
def eval(exp: Exp)(env: ValueEnv): Val = exp match {
case While(Cond(op, l, r), lbody, body) =>
while (evalCond(op)(eval(l)(env), eval(r)(env))) {
eval(lbody)(env)
}
eval(body)(env)
}
8.3.4 x86 Flags And Jump - Compile Loops
trans(While(Cond(op, l, r), lbody, body), 0)(Map())
In order to compile while statement, we are going to follow this idea:
jmp loop_cond
loop_body:
... # code for lbody
loop_cond:
... # code for l and r
cmpq <r>, <l>
j<op> loop_body # the jump operation depends on 'op'
... # code for body
How would we compile a do-while loop?
Answer: omit the unconditional jump
8.4 Parsing and Desugaring
8.4.1 We Can Write, Parse, and Compile Nice Code!!
var x = 2;
var y = 0;
while (y < 5) {
x = x * x;
y = y + 1
};
x
Can we really???
We need to modify our program slightly.
var x = 2;
var y = 0;
while (y < 5) {
val dummy = x = x * x;
y = y + 1
};
x
Let’s modify our grammar slightly instead!!
8.4.2 Grammar - Syntactic Sugar
<op> ::= '+' | '-' | '*' | '/'
<bop> ::= '==' | '!=' | '<' | '>' | '<=' | '>='
<atom> ::= <number>
| '('<simp>')'
| <ident>
| '{'<exp>'}'
<uatom> ::= [<op>]<atom>
<cond> ::= <simp><bop><simp>
<simp> ::= <uatom>[<op><uatom>]*
| 'if' '('<cond>')' <simp> ['else' <simp>]
| <ident> '=' <simp>
<exp> ::= <simp>[';'<exp>]
| 'val' <ident> '=' <simp>';'<exp>
| 'var' <ident> '=' <simp>';'<exp>
| 'while' '(' <cond> ')' <simp>';'<exp>
Syntax sugar constructs are constructs that can be syntactically translated to other existing constructs. Syntactic sugar does not offer additional expressive power to the programmer; only some syntactic convenience
x = x + 1;
y = y + 1
rather than
val dummy = x = x + 1;
y = y + 1
8.4.3 One-Sided Ifs
Similarly, we can support ifs without else clause:
if (x > 0)
x = x - 1;
val y = x * 5;
x
is now transformed into
val tmp = if (x > 0)
x = x - 1
else
0; // Won't be used
val y = x * 5;
y
8.4.4 AST Of Sugared Expressions
Example 1
x = x + 1;
y = y + 1
Let("tmp$1",
VarAssign("x", Prim("+", Ref("x"), Lit(1)))
VarAssign("y", Prim("+", Ref("y"), Lit(1)))
)
Example 2
if (x > 0)
x = x - 1;
val y = x * 5;
x
Let("tmp$1",
If(Cond(">", Ref("x"), Lit(0)),
VarAssign("x", Prim("-", Ref("x"), Lit(1))),
Lit(())),
Let("y", Prim("*", Ref("x"), Lit(5)), Ref("x"))
)
8.5 Where Are We?
We added variables, loops and some syntax sugar to our language.