teaching machines

CS 330 Lecture 20 – A Logo Compiler with Conditionals and Loops

March 8, 2013 by Chris Johnson. Filed under cs330, lectures, spring 2013.

Agenda

• what ?s
• interpreting vs. compiling
• modeling a program: follow the grammar
• what to do on undeclared variables?
• adding loops
• adding conditionals

TODO

• Write a Logo program and drop it in your submissions directory in W330. Name your file todo.logo. Be exactly exact. We will have a gallery showing on Monday.
• You are encouraged to test it and thereby get a working ANTLR installation. To install, download the ANTLR jar file and add it to your class path. A zip file of the code below will be dropped in W330. If you get this working on the thingies, I welcome your documentation on the process in the comments.

Code

makefile

Note to copy and pasters: makefile rules need to be indented with real tabs, not spaces.

ANTLR_JAR = $(HOME)/bin/antlr-4.0-complete.jar
ANTLR = java -jar $(ANTLR_JAR)
PIECES = $(wildcard *Expression.java *Command.java) LogoBlock.java LVM.java

all: CompilerLoogo.class LVM.class

CompilerLoogo.class: LoogoParser.class makefile CompilerLoogo.java $(PIECES)
  javac CompilerLoogo.java

LVM.class: $(PIECES)
  javac LVM.java

LoogoParser.class: Loogo.g4 makefile
  $(ANTLR) Loogo.g4
  javac Loogo*.java

clean:
  rm -f *.class *.tokens Logo*Listener.java Logo*Parser.java Logo*Lexer.java

AddExpression.java

public class AddExpression implements LogoExpression {
  private LogoExpression a;
  private LogoExpression b;

  public AddExpression(LogoExpression a, LogoExpression b) {
    this.a = a;
    this.b = b;
  }

  public double evaluate(Environment env) {
    return a.evaluate(env) + b.evaluate(env);
  }
}

AssignmentCommand.java

public class AssignmentCommand implements LogoCommand {
  private String id;
  private LogoExpression expr;

  public AssignmentCommand(String id, LogoExpression expr) {
    this.id = id;
    this.expr = expr;
  }

  public void execute(Environment env) {
    env.variables.put(id, expr.evaluate(env));
  }
}

CommandListener.java

public interface CommandListener {
  public void onPostCommand();
}

CompilerLoogo.java

import org.antlr.v4.runtime.*;
import java.io.FileOutputStream;
import java.io.ObjectOutputStream;
import java.util.Stack;
import java.util.List;
import java.util.ArrayList;
import java.io.IOException;
import org.antlr.v4.runtime.tree.*;

public class CompilerLoogo extends LoogoBaseListener {
  private Stack<LogoExpression> expressions = new Stack<LogoExpression>();
  private Stack<LogoBlock> blocks = new Stack<LogoBlock>();

  public void enterBlock(LoogoParser.BlockContext context) {
    blocks.push(new LogoBlock());
  }

  public void exitMove(LoogoParser.MoveContext context) {
    blocks.peek().append(new MoveCommand(expressions.pop()));
  }

  public void exitRepeat(LoogoParser.RepeatContext context) {
    int nIterations = Integer.parseInt(context.INT().getText());
    RepeatCommand loop = new RepeatCommand(nIterations, blocks.pop());
    blocks.peek().append(loop);
  }

  public void exitIf(LoogoParser.IfContext context) {
    LogoExpression condition = expressions.pop();
    LogoBlock elseBlock = blocks.pop();
    LogoBlock thenBlock = blocks.pop();
    blocks.peek().append(new IfCommand(condition, thenBlock, elseBlock));
  }

  public void exitTurn(LoogoParser.TurnContext context) {
    blocks.peek().append(new TurnCommand(expressions.pop()));
  }

  public void exitAssignment(LoogoParser.AssignmentContext context) {
    blocks.peek().append(new AssignmentCommand(context.ID().getText(), expressions.pop()));
  }

  public void exitSlime(LoogoParser.SlimeContext context) {
    blocks.peek().append(new SlimeCommand(context.ON() != null));
  }

  public void exitDouble(LoogoParser.DoubleContext context) {
    expressions.push(new DoubleExpression(Double.parseDouble(context.DOUBLE().getText())));
  }

  public void exitInt(LoogoParser.IntContext context) {
    expressions.push(new IntExpression(Integer.parseInt(context.INT().getText())));
  }

  public void exitID(LoogoParser.IDContext context) {
    expressions.push(new IdExpression(context.ID().getText()));
  }

  public void exitAddSubtract(LoogoParser.AddSubtractContext context) {
    LogoExpression b = expressions.pop();
    LogoExpression a = expressions.pop();

    if (context.ADDITIVE_OPERATOR().getText().equals("+")) {
      expressions.push(new AddExpression(a, b));
    } else {
      expressions.push(new SubtractExpression(a, b));
    }
  }

  public void exitMulDivMod(LoogoParser.MulDivModContext context) {
    LogoExpression b = expressions.pop();
    LogoExpression a = expressions.pop();

    if (context.MULTIPLICATIVE_OPERATOR().getText().equals("*")) {
      expressions.push(new MultiplyExpression(a, b));
    } else if (context.MULTIPLICATIVE_OPERATOR().getText().equals("/")) {
      expressions.push(new DivideExpression(a, b));
    } else {
      expressions.push(new ModExpression(a, b));
    }
  }

  public void exitProgram(LoogoParser.ProgramContext context) {
    try {
      ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream("logo.out"));
      out.writeObject(blocks.pop());
      out.close();
    } catch (IOException e) {
    }
  }

  public static void main(String[] args) throws IOException {
    CompilerLoogo compiler = new CompilerLoogo();

    ANTLRInputStream input = new ANTLRInputStream(System.in);
    LoogoLexer lexer = new LoogoLexer(input);
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    LoogoParser parser = new LoogoParser(tokens);
    ParseTree tree = parser.program();

    ParseTreeWalker walker = new ParseTreeWalker();
    walker.walk(compiler, tree);
  }
}

DivideExpression.java

public class DivideExpression implements LogoExpression {
  private LogoExpression a;
  private LogoExpression b;

  public DivideExpression(LogoExpression a, LogoExpression b) {
    this.a = a;
    this.b = b;
  }

  public double evaluate(Environment env) {
    return a.evaluate(env) / b.evaluate(env);
  }
}

DoubleExpression.java

public class DoubleExpression implements LogoExpression {
  private double value;

  public DoubleExpression(double value) {
    this.value = value;
  }

  public double evaluate(Environment env) {
    return value;
  }
}

Environment.java

import java.util.ArrayList;
import java.util.HashMap;
import java.awt.geom.Line2D;

public class Environment {
  public double x = 0.0;
  public double y = 0.0;
  public double theta = 0.0;
  public boolean isLeaking = true;
  public HashMap<String, Double> variables = new HashMap<String, Double>();
  public ArrayList<Line2D.Double> segments = new ArrayList<Line2D.Double>();
  public CommandListener listener = null;
}

IdExpression.java

public class IdExpression implements LogoExpression {
  private String id;

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

  public double evaluate(Environment env) {
    Double value = env.variables.get(id);
    if (value == null) {
      System.err.println("No such variable " + id + "!");
      System.exit(1);
    }
    return value;
  }
}

IfCommand.java

public class IfCommand implements LogoCommand {
  private LogoExpression condition;
  private LogoBlock thenBlock;
  private LogoBlock elseBlock;

  public IfCommand(LogoExpression condition, LogoBlock thenBlock, LogoBlock elseBlock) {
    this.condition = condition;
    this.thenBlock = thenBlock;
    this.elseBlock = elseBlock;
  }

  public void execute(Environment env) {
    if (condition.evaluate(env) > 0.0) {
      thenBlock.execute(env);
    } else {
      elseBlock.execute(env);
    }
  }
}

IntExpression.java

public class IntExpression implements LogoExpression {
  private int value;

  public IntExpression(int value) {
    this.value = value;
  }

  public double evaluate(Environment env) {
    return value;
  }
}

LogoBlock.java

import java.io.Serializable;
import java.util.ArrayList;

public class LogoBlock implements Serializable {
  private ArrayList<LogoCommand> commands = new ArrayList<LogoCommand>();

  public LogoBlock() {
    commands = new ArrayList<LogoCommand>();
  }

  public void append(LogoCommand command) {
    commands.add(command);
  }

  public void execute(Environment env) {
    for (LogoCommand command : commands) {
      command.execute(env);
      if (env.listener != null) {
        env.listener.onPostCommand();
      }
    }
  }
}

LogoCommand.java

import java.io.Serializable;

public interface LogoCommand extends Serializable {
  public void execute(Environment env);
}

LogoExpression.java

import java.io.Serializable;

public interface LogoExpression extends Serializable {
  public double evaluate(Environment env);
}

LVM.java

import javax.swing.JFrame;
import java.io.ObjectInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import javax.swing.JFrame;
import javax.swing.JPanel;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Line2D;
import java.awt.geom.AffineTransform;
import java.util.HashMap;

public class LVM implements CommandListener {
  public static void main(String[] args) throws IOException, ClassNotFoundException {
    new LVM(args[0], Integer.parseInt(args[1]));
  }

  private JFrame display;
  private Environment env;
  private int delay;

  public LVM(String path, int delay) throws IOException, ClassNotFoundException {
    this.delay = delay;

    ObjectInputStream in = new ObjectInputStream(new FileInputStream(path));
    LogoBlock main = (LogoBlock) in.readObject();
    in.close();

    display = new JFrame("Loogo");

    Environment env = new Environment();
    env.listener = this;
    display.setContentPane(new LoogoDisplay(env));

    display.setSize(1200, 700);
    display.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    display.setVisible(true);

    main.execute(env);

    System.out.println("all done");
  }

  public void onPostCommand() {
    pause(delay);
    display.repaint();
  }

  private void pause(int delay) {
    try {
      Thread.sleep(delay);
    } catch (InterruptedException e) {
    }
  }

  class LoogoDisplay extends JPanel {
    private Line2D.Double arrowTop;
    private Line2D.Double arrowBottom;
    private Environment env;

    public LoogoDisplay(Environment env) {
      this.env = env;
      arrowTop = new Line2D.Double(-10.0f, -5.0f, 0.0f, 0.0f);
      arrowBottom = new Line2D.Double(-10.0f, 5.0f, 0.0f, 0.0f);
    }

    public void paintComponent(Graphics g) {
      super.paintComponent(g);

      Graphics2D g2 = (Graphics2D) g;
      AffineTransform xform = g2.getTransform(); 

      g2.translate(850, 150);

      synchronized (env.segments) {
        for (Line2D.Double segment : env.segments) {
          g2.draw(segment);
        }  
      }

      g2.translate(env.x, env.y);
      g2.rotate(env.theta);
      g2.draw(arrowTop);
      g2.draw(arrowBottom);
    }
  }
}

ModExpression.java

public class ModExpression implements LogoExpression {
  private LogoExpression a;
  private LogoExpression b;

  public ModExpression(LogoExpression a, LogoExpression b) {
    this.a = a;
    this.b = b;
  }

  public double evaluate(Environment env) {
    return a.evaluate(env) % b.evaluate(env);
  }
}

MoveCommand.java

import java.awt.geom.Line2D;

public class MoveCommand implements LogoCommand {
  private LogoExpression expr;

  public MoveCommand(LogoExpression expr) {
    this.expr = expr;
  }

  public void execute(Environment env) {
    double distance = expr.evaluate(env);

    double newX = env.x + Math.cos(env.theta) * distance;
    double newY = env.y + Math.sin(env.theta) * distance;

    if (env.isLeaking) {
      synchronized (env.segments) {
        env.segments.add(new Line2D.Double(env.x, env.y, newX, newY));
      }
    }

    env.x = newX;
    env.y = newY;
  }
}

MultiplyExpression.java

public class MultiplyExpression implements LogoExpression {
  private LogoExpression a;
  private LogoExpression b;

  public MultiplyExpression(LogoExpression a, LogoExpression b) {
    this.a = a;
    this.b = b;
  }

  public double evaluate(Environment env) {
    return a.evaluate(env) * b.evaluate(env);
  }
}

RepeatCommand.java

public class RepeatCommand implements LogoCommand {
  private int nIterations;
  private LogoBlock block;

  public RepeatCommand(int nIterations, LogoBlock block) {
    this.nIterations = nIterations;
    this.block = block;
  }

  public void execute(Environment env) {
    for (int i = 0; i < nIterations; ++i) {
      block.execute(env);
    }
  }
}

SlimeCommand.java

public class SlimeCommand implements LogoCommand {
  private boolean enable;

  public SlimeCommand(boolean enable) {
    this.enable = enable;
  }

  public void execute(Environment env) {
    env.isLeaking = enable;
  }
}

SubtractExpression.java

public class SubtractExpression implements LogoExpression {
  private LogoExpression a;
  private LogoExpression b;

  public SubtractExpression(LogoExpression a, LogoExpression b) {
    this.a = a;
    this.b = b;
  }

  public double evaluate(Environment env) {
    return a.evaluate(env) - b.evaluate(env);
  }
}

TurnCommand.java

public class TurnCommand implements LogoCommand {
  private LogoExpression expr;

  public TurnCommand(LogoExpression expr) {
    this.expr = expr;
  }

  public void execute(Environment env) {
    env.theta -= Math.toRadians(expr.evaluate(env));
  }
}

Loogo.g4

grammar Loogo;

program
  : block EOF
  ;

block
  : statement*
  ;

statement
  : command NEWLINE
  | NEWLINE
  ;

command
  : MOVE expression # Move
  | TURN expression # Turn
  | SLIME (ON | OFF) # Slime
  | ID IS expression # Assignment
  | REPEAT INT NEWLINE block END # Repeat
  | IF expression NEWLINE block ELSE NEWLINE block END # If
  ;

expression
  : DOUBLE # Double
  | INT # Int
  | ID # ID
  | '(' expression ')' # Parenthesized
  | expression MULTIPLICATIVE_OPERATOR expression # MulDivMod
  | expression ADDITIVE_OPERATOR expression # AddSubtract
  ;

MULTIPLICATIVE_OPERATOR : ('*'|'/'|'%');
ADDITIVE_OPERATOR : ('+'|'-');
IS : '<-';
INT : '-'? [0-9]+;
DOUBLE : '-'? [0-9]+ ('.' [0-9]+)?;
MOVE : 'move';
TURN : 'turn';
FUNCTION : 'function';
SLIME : 'slime';
ON : 'on';
OFF : 'off';
END : 'end';
REPEAT : 'repeat';
IF : 'if';
ELSE : 'else';
ID : [a-z]+;
NEWLINE : '\r'? '\n';

COMMENT : '#' .*? '\n' -> skip;
WHITESPACE : [ \t\r]+ -> skip;

amplisquare.logo

a <- 10
repeat 50
  move a
  turn 90
  move a
  turn 90
  move a
  turn 90
  move a
  a <- a + 4
end

cond.logo

a <- -100

if a
  turn 45
else
  turn -45
end

move 100

repeat_square.logo

d <- 100
a <- 90
repeat 4
  move d
  turn a
end

square.logo

d <- 100
a <- 90

repeat 10
  move d
  turn a
  move d
  turn a
  move d
  turn a
  move d

  d <- d + 1
  a <- a + 10
end

xgrid.logo

repeat 10
  repeat 10
    repeat 9
      move 10
      turn 40
    end
    slime off
    move 30
    slime on
  end
  turn 180
  slime off
  move 300
  turn 90
  move 30
  turn 90
  slime on
end

Haiku