teaching machines

CS 330 Lecture 12 – Storing a Program

Agenda

  • what ?s
  • think about this
  • storing program structures in Basecalc

TODO

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…

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *