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:

1. Yes
2. 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.