1 of 18

Announcements

2 of 18

Project Overview

  • Parser (Formal Grammars and Parsing Theory)

​

  • Interpreter (Program Semantics)

​

  • Low-Level Virtual Machine (Syntax-Directed Translation)

​

  • Garbage Collector (Memory Management)

​

  • Code Generation and Optimization (Efficiency)

3 of 18

IMP: a simple imperative language

 

 

 

(assignment)

(if-then-else)

(sequential composition)

(loop)

The Formal Semantics of Programming Languages by Glynn Winskel

4 of 18

Recursive Interpreter

 

 

 

 

class Binop : public Expr {

enum BINOP { PLUS, SUB, MUL, DIV};

BINOP op;

Expr *left, *right;

};

​

int eval_expr(Frame* f, Expr *e) { ... }

​

int eval_binop(Frame *f, Binop *e) {

switch(e->op) {

case PLUS: return eval_plus(e);

case SUB : return eval_sub(e);

case MUL : return eval_mul(e);

case DIV : return eval_div(e);

}

}

int eval_plus(Frame *f, Binop *e) {

int n_1 = eval_expr(f, e->left);

int n_2 = eval_expr(f, e->right);

return n_1 + n_2;

}

...

5 of 18

Semantic Notation – Evaluation Relations

  • Define the semantics of each term in our language (E, B, and S) with an evaluation relation:

​

​

​

​

​

  • Meaning: given a frame, the term evaluates to a result

 

 

 

6 of 18

Variables and Frames

  •  

 

x = 1;

y = 2;

z = 3;

 

7 of 18

Evaluation Relations (Formal)

  •  

 

 

 

 

8 of 18

Evaluation Relations (Formal)

  •  

9 of 18

Expressions: Inference Rules

  •  

 

 

 

 

✓

𝘹

 

 

 

 

 

✓

𝘹

✓

𝘹

10 of 18

Expressions: Inference Rules

  •  

 

 

 

 

11 of 18

Errant Evaluations

  •  

12 of 18

Recursive Interpreter

 

 

 

 

class Binop : public Expr {

enum BINOP { PLUS, SUB, MUL, DIV};

BINOP op;

Expr *left, *right;

};

​

int eval_expr(Frame* f, Expr *e) { ... }

​

int eval_binop(Frame *f, Binop *e) {

switch(e->op) {

case PLUS: return eval_plus(e);

case SUB : return eval_sub(e);

case MUL : return eval_mul(e);

case DIV : return eval_div(e);

}

}

int eval_plus(Frame *f, Binop *e) {

int n_1 = eval_expr(f, e->left);

int n_2 = eval_expr(f, e->right);

return n_1 + n_2;

}

13 of 18

Recursive Interpreter

 

 

 

 

class Binop : public Expr {

enum BINOP { PLUS, SUB, MUL, DIV};

BINOP op;

Expr *left, *right;

};

​

int eval_expr(Frame* f, Expr *e) { ... }

​

int eval_binop(Frame *f, Binop *e) {

switch(e->op) {

case PLUS: return eval_plus(e);

case SUB : return eval_sub(e);

case MUL : return eval_mul(e);

case DIV : return eval_div(e);

}

}

int eval_plus(Frame *f, Binop *e) {

int n_1 = eval_expr(f, e->left);

int n_2 = eval_expr(f, e->right);

return n_1 + n_2;

}

14 of 18

Boolean Expressions: Inference Rules

  •  

 

 

 

 

 

 

 

15 of 18

Statements: Inference Rules

 

 

 

 

16 of 18

Statements: Inference Rules (cont.)

 

 

 

 

 

17 of 18

Example

if (x == 1)

{

y = 2;

}

 

 

 

 

 

 

 

 

 

 

18 of 18

Next Time

  • Heaps

​

  • Types