# teaching machines

## CS 330 Lecture 12 – Storing a Program

February 20, 2015 by . Filed under cs330, lectures, spring 2015.

### Agenda

• what ?s
• storing program structures in Basecalc

### TODO

• Suppose we add a ternary operator to our Basecalc language. What happens when we execute the following expression?
a := (5 > 0) ? (b := 2) : (c := 3)
• Suppose we add loops to our language. What happens when we execute the following expression?
repeat 3
$a =$a + 5
end
• Suppose we want $diameter to always be 2 *$radius. If $radius changes, we want the next $diameter reference to automatically evaluate to 2 * $radius—without having to reassign $diameter = 2 * $radius. For example: $radius := 3 -- yields 3
$diameter :=$radius * 2 -- yields 6
$radius := 10 -- yields 10$diameter -- yields 20

### Code

#### Basecalc.g

grammar Basecalc;

line
: expr # DecimalOutput
| expr CAST DIGITS # BaseOutput
;

expr
: LEFT_PARENTHESIS expr RIGHT_PARENTHESIS # Grouped
| NOT expr # Negate
| expr POWER expr # Power
| expr MULTIPLICATIVE_OPERATOR expr # Multiply
| expr SHIFT expr # Shift
| expr AND expr # And
| expr XOR expr # Xor
| expr OR expr # Or
| IDENTIFIER ASSIGNMENT expr # Assignment
| IDENTIFIER '=' expr # LazyAssignment
| DIGITS # Literal
| n=DIGITS LESS base=DIGITS GREATER # LiteralWithBase
| IDENTIFIER # Identifier
;

LEFT_PARENTHESIS: '(';
RIGHT_PARENTHESIS: ')';
POWER: '^^';
MULTIPLICATIVE_OPERATOR: [*/%];
NOT: '~';
SHIFT: '<<' | '>>';
AND: '&';
XOR: '^';
OR: '|';
ASSIGNMENT: ':=';
CAST: '->';
LESS: '<';
GREATER: '>';
IDENTIFIER: '\$' [a-z]+ [a-z_]*;
DIGITS: [0-9a-zA-Z]+;

WHITESPACE: [ \n\r\t]+ -> skip;

#### Interpreter.java

import java.util.HashMap;
import java.util.Stack;

public class Interpreter extends BasecalcBaseListener {
private Stack<Expr> operands;
private HashMap<String, Expr> variables;

public Interpreter() {
operands = new Stack<>();
variables = new HashMap<>();
}

@Override
public void exitDecimalOutput(BasecalcParser.DecimalOutputContext ctx) {
System.out.println(operands.pop().evaluate(variables));
}

@Override
public void exitBaseOutput(BasecalcParser.BaseOutputContext ctx) {
String baseAsString = ctx.DIGITS().getText();
int base = Integer.parseInt(baseAsString);

System.out.println(Integer.toString(operands.pop().evaluate(variables), base) + "<" + base + ">");
}

@Override
public void exitLiteral(BasecalcParser.LiteralContext ctx) {
String digitsAsString = ctx.DIGITS().getText();
int digits = Integer.parseInt(digitsAsString);
operands.push(new ExprInteger(digits));
}

@Override
public void exitLiteralWithBase(BasecalcParser.LiteralWithBaseContext ctx) {
String digitsAsString = ctx.n.getText();
String baseAsString = ctx.base.getText();
int base = Integer.parseInt(baseAsString);
int digits = Integer.parseInt(digitsAsString, base);
operands.push(new ExprInteger(digits));
}

@Override
Expr b = operands.pop();
Expr a = operands.pop();
} else {
operands.push(new ExprSubtract(a, b));
}
}

@Override
public void exitPower(BasecalcParser.PowerContext ctx) {
Expr b = operands.pop();
Expr a = operands.pop();
operands.push(new ExprPower(a, b));
}

@Override
public void exitNegate(BasecalcParser.NegateContext ctx) {
Expr a = operands.pop();
operands.push(new ExprNegate(a));
}

@Override
public void exitXor(BasecalcParser.XorContext ctx) {
Expr b = operands.pop();
Expr a = operands.pop();
operands.push(new ExprXor(a, b));
}

@Override
public void exitMultiply(BasecalcParser.MultiplyContext ctx) {
Expr b = operands.pop();
Expr a = operands.pop();
if (ctx.MULTIPLICATIVE_OPERATOR().getText().equals("*")) {
operands.push(new ExprMultiply(a, b));
} else if (ctx.MULTIPLICATIVE_OPERATOR().getText().equals("/")) {
operands.push(new ExprDivide(a, b));
} else {
operands.push(new ExprRemainder(a, b));
}
}

@Override
public void exitAnd(BasecalcParser.AndContext ctx) {
Expr b = operands.pop();
Expr a = operands.pop();
operands.push(new ExprAnd(a, b));
}

@Override
public void exitOr(BasecalcParser.OrContext ctx) {
Expr b = operands.pop();
Expr a = operands.pop();
operands.push(new ExprOr(a, b));
}

@Override
public void exitShift(BasecalcParser.ShiftContext ctx) {
Expr b = operands.pop();
Expr a = operands.pop();
if (ctx.SHIFT().getText().equals("<<")) {
operands.push(new ExprLeftShift(a, b));
} else {
operands.push(new ExprRightShift(a, b));
}
}

@Override
public void exitAssignment(BasecalcParser.AssignmentContext ctx) {
variables.put(ctx.IDENTIFIER().getText(), new ExprInteger(operands.peek().evaluate(variables)));
}

@Override
public void exitLazyAssignment(BasecalcParser.LazyAssignmentContext ctx) {
variables.put(ctx.IDENTIFIER().getText(), operands.peek());
}

@Override
public void exitIdentifier(BasecalcParser.IdentifierContext ctx) {
operands.push(new ExprIdentifier(ctx.IDENTIFIER().getText()));
}
}

#### Expr.java

import java.util.Map;

public abstract class Expr {
public abstract int evaluate(Map<String, Expr> env);
}

import java.util.Map;

public class ExprAdd extends Expr {
private Expr a;
private Expr b;

public ExprAdd(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) + b.evaluate(env);
}
}

#### ExprAnd.java

import java.util.Map;

public class ExprAnd extends Expr {
private Expr a;
private Expr b;

public ExprAnd(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) & b.evaluate(env);
}
}

#### ExprDivide.java

import java.util.Map;

public class ExprDivide extends Expr {
private Expr a;
private Expr b;

public ExprDivide(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) / b.evaluate(env);
}
}

#### ExprIdentifier.java

import java.util.Map;

public class ExprIdentifier extends Expr {
private String id;

public ExprIdentifier(String id) {
this.id = id;
}

public int evaluate(Map<String, Expr> env) {
return env.get(id).evaluate(env);
}
}

#### ExprInteger.java

import java.util.Map;

public class ExprInteger extends Expr {
public int i;

public ExprInteger(int i) {
this.i = i;
}

public int evaluate(Map<String, Expr> env) {
return i;
}
}

#### ExprLeftShift.java

import java.util.Map;

public class ExprLeftShift extends Expr {
private Expr a;
private Expr b;

public ExprLeftShift(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) << b.evaluate(env);
}
}

#### ExprMultiply.java

import java.util.Map;

public class ExprMultiply extends Expr {
private Expr a;
private Expr b;

public ExprMultiply(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) * b.evaluate(env);
}
}

#### ExprNegate.java

import java.util.Map;

public class ExprNegate extends Expr {
private Expr a;

public ExprNegate(Expr a) {
this.a = a;
}

public int evaluate(Map<String, Expr> env) {
return ~a.evaluate(env);
}
}

#### ExprOr.java

import java.util.Map;

public class ExprOr extends Expr {
private Expr a;
private Expr b;

public ExprOr(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) | b.evaluate(env);
}
}

#### ExprPower.java

import java.util.Map;

public class ExprPower extends Expr {
private Expr a;
private Expr b;

public ExprPower(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return (int) Math.pow(a.evaluate(env), b.evaluate(env));
}
}

#### ExprRemainder.java

import java.util.Map;

public class ExprRemainder extends Expr {
private Expr a;
private Expr b;

public ExprRemainder(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) % b.evaluate(env);
}
}

#### ExprRightShift.java

import java.util.Map;

public class ExprRightShift extends Expr {
private Expr a;
private Expr b;

public ExprRightShift(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) >> b.evaluate(env);
}
}

#### ExprSubtract.java

import java.util.Map;

public class ExprSubtract extends Expr {
private Expr a;
private Expr b;

public ExprSubtract(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) - b.evaluate(env);
}
}

#### ExprXor.java

import java.util.Map;

public class ExprXor extends Expr {
private Expr a;
private Expr b;

public ExprXor(Expr a, Expr b) {
this.a = a;
this.b = b;
}

public int evaluate(Map<String, Expr> env) {
return a.evaluate(env) ^ b.evaluate(env);
}
}

### Haiku

on the long term
The puppeteer died
His puppets lifeless, laughless