» CS 330 Lecture 12 – Storing a Program

CS 330 Lecture 12 – Storing a Program

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

Agenda

what ?s
think about this
storing program structures in Basecalc

TODO

Watch two videos on optimization from Stanford professor Alex Aiken: https://www.youtube.com/watch?v=_8PEtL9AYmQ and https://www.youtube.com/watch?v=yRfh7hUx26k. Feel free to watch at double speed. Share 3-4 questions or observations on a 1/4 sheet.

Think About This

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 ADDITIVE_OPERATOR expr # Add
  | 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: [*/%];
ADDITIVE_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
  public void exitAdd(BasecalcParser.AddContext ctx) {
    Expr b = operands.pop();
    Expr a = operands.pop();
    if (ctx.ADDITIVE_OPERATOR().getText().equals("+")) {
      operands.push(new ExprAdd(a, b));
    } 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);
}

ExprAdd.java

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
If he’d had robots…