Implement flow control with breaks

pkg/kernel/lib/interpreter/interpreter.dart

Index: pkg/kernel/lib/interpreter/interpreter.dart
diff --git a/pkg/kernel/lib/interpreter/interpreter.dart b/pkg/kernel/lib/interpreter/interpreter.dart
index a64fe581f12f7be928f4f34308138c6a63545c48..84f86afd6736570296ac5e4f05e47ac6f83f25a1 100644
--- a/pkg/kernel/lib/interpreter/interpreter.dart
+++ b/pkg/kernel/lib/interpreter/interpreter.dart
@@ -17,7 +17,6 @@ class NotImplemented {
 class Interpreter {
   Program program;
   StatementExecuter visitor = new StatementExecuter();
-  Environment env = new Environment.empty();
 
   Interpreter(this.program);
 
@@ -25,19 +24,11 @@ class Interpreter {
     assert(program.libraries.isEmpty);
     Procedure mainMethod = program.mainMethod;
     Statement statementBlock = mainMethod.function.body;
-    visitor.exec(statementBlock, env);
+    Continuation cont = new Continuation(statementBlock, new State.empty());
+    visitor.trampolinedExecution(cont);
   }
 }
 
-class InvalidExpressionError {
-  InvalidExpression expression;
-
-  InvalidExpressionError(this.expression);
-
-  String toString() =>
-      'Invalid expression at ${expression.location.toString()}';
-}
-
 class Binding {
   final VariableDeclaration variable;
   Value value;
@@ -82,6 +73,7 @@ class Environment {
   }
 }
 
+/// Evaluate expressions.
 class Evaluator extends ExpressionVisitor1<Value> {
   Value eval(Expression expr, Environment env) => expr.accept1(this, env);
 
@@ -91,7 +83,7 @@ class Evaluator extends ExpressionVisitor1<Value> {
   }
 
   Value visitInvalidExpression1(InvalidExpression node, env) {
-    throw new InvalidExpressionError(node);
+    throw 'Invalid expression at ${node.location.toString()}';
   }
 
   Value visitVariableGet(VariableGet node, env) {
@@ -223,57 +215,164 @@ class Evaluator extends ExpressionVisitor1<Value> {
   }
 }
 
+/// Represents a state which consists of current environment, continuation to be
+/// applied and the current label.
+class State {
+  final Environment env;
+  final Continuation continuation;
+  Label label;

[Kevin Millikin (Google), 2017/04/05 08:21:47]

List these in the same order as the constructor arguments for uniformity.  I
think we should call env 'environmment' since we've spelled out continuation or
else we should call continuation 'cont'.

I prefer spelling fields out in full, but I'm happy to abbreviate parameter
names.

'label' could be 'labels' because I think of it as plural: it's a stack or
linked list of (statement, continuation) pairs.

[zhivkag, 2017/04/05 10:00:19]

Done.

+
+  State(this.env, this.label, this.continuation);
+  State.withEnvironment(Environment env, State s)

[Kevin Millikin (Google), 2017/04/05 08:21:47]

This is basically a static function that we have to invoke with new
State.withEnvironment.  Since it has a State argument already, I think it might
be nicer to have it be a method:

State withEnvironment(Environment env) {
  return new State(env, label, cont);
}

[zhivkag, 2017/04/05 10:00:19]

Done.

+      : this(env, s.label, s.continuation);
+
+  State.withContinuation(Continuation cont, State s)
+      : this(s.env, s.label, cont);
+
+  State.empty()

[Kevin Millikin (Google), 2017/04/05 08:21:48]

Empty state seems ambiguous.  Perhaps State.initial:

State.initial() : this(new Environment.empty(), null, new
Continuation.initial());

[zhivkag, 2017/04/05 10:00:20]

Done.

+      : this(new Environment.empty(), new Label.empty(),
+            const Continuation.empty());
+
+  void addLabel(Statement s) {
+    label = new Label(s, continuation, label);

[Kevin Millikin (Google), 2017/04/05 08:21:47]

Suggest to make label be final and use a constructor (or method as above):

State withBreak(Statement stmt) {
  return new State(env, new Label(stmt, cont, labels), cont);
}

[zhivkag, 2017/04/05 10:00:19]

Done.

+  }
+
+  Label lookupLabel(LabeledStatement s) {
+    return label.lookupLabel(s);
+  }
+}
+
+/// Represent the continuation for execution of statement.
+class Continuation {
+  final Statement statement;
+  final State state;
+
+  Continuation(this.statement, this.state);
+  const Continuation.empty()

[Kevin Millikin (Google), 2017/04/05 08:21:47]

This is the initial continuation, right?  I think we have the property that
bodies always have a return, in which case we do not expect to 'invoke' this
continuation (by ending up trying to evaluate the statement).  Perhaps it is
Continuation.error, in that case?

For now I think we could just use null.

[zhivkag, 2017/04/05 10:00:19]

Yes, we shouldn't apply this continuation. exec should return it only when the
entire program was executed. 
Using null for now and we can change it later to Continuation.error or something
else if needed. 

+      : statement = null,
+        state = null;
+}
+
+/// Represents a labeled statement, the corresponding continuation and the
+/// enclosing label.
+class Label {
+  final LabeledStatement statement;
+  final Continuation continuation;
+  final Label enclosingLabel;
+
+  Label(this.statement, this.continuation, this.enclosingLabel);
+  Label.empty()

[Kevin Millikin (Google), 2017/04/05 08:21:48]

Does it make sense to use null as the sentinel for the end of the list?  new
Label.empty().lookup(s) doesn't work for any s except null, which we shouldn't
ask.

It dodges the issue that we have the same continuation as the initial
continuation, which doesn't seem quite right.

[zhivkag, 2017/04/05 10:00:19]

Done.

+      : statement = null,
+        continuation = new Continuation.empty(),
+        enclosingLabel = null;
+
+  Label lookupLabel(LabeledStatement s) {
+    if (identical(s, statement)) return this;
+    return enclosingLabel.lookupLabel(s);

[Kevin Millikin (Google), 2017/04/05 08:21:47]

In a well-formed program we will not get that enclosingLabel is null, but maybe
we should assert it.

[zhivkag, 2017/04/05 10:00:19]

Done.

+  }
+}
+
 /// Executes statements.
-class StatementExecuter extends StatementVisitor1 {
+///
+/// Execution of a statement completes in one of the following ways:
+/// - it completes normally, in which case the execution proceeds to applying
+/// the next continuation
+/// - it breaks with a label, in which case the corresponding continuation is
+/// returned and applied
+/// - it returns with or without value, TBD
+/// - it throws, TBD
+class StatementExecuter extends StatementVisitor1<Continuation> {
   Evaluator evaluator = new Evaluator();
 
-  exec(Statement statement, env) => statement.accept1(this, env);
-  eval(Expression expression, env) => evaluator.eval(expression, env);
+  void trampolinedExecution(Continuation continuation) {
+    while (!identical(continuation, const Continuation.empty())) {
+      continuation = exec(continuation.statement, continuation.state);
+    }
+  }
 
-  defaultStatement(Statement node, env) {
+  Continuation exec(Statement statement, state) =>
+      statement.accept1(this, state);
+  Value eval(Expression expression, env) => evaluator.eval(expression, env);
+
+  Continuation defaultStatement(Statement node, state) {
     throw notImplemented(
         m: "Execution is not implemented for statement:\n$node ");
   }
 
-  visitInvalidStatement(InvalidStatement node, env) {
+  Continuation visitInvalidStatement(InvalidStatement node, state) {
     throw "Invalid statement at ${node.location}";
   }
 
-  visitExpressionStatement(ExpressionStatement node, env) {
-    return eval(node.expression, env);
+  Continuation visitExpressionStatement(ExpressionStatement node, state) {
+    eval(node.expression, state.env);
+    return state.continuation;
   }
 
-  visitBlock(Block node, env) {
-    Environment blockEnv = new Environment(env);
-    for (Statement s in node.statements) {
-      exec(s, blockEnv);
+  Continuation visitBlock(Block node, state) {
+    // Block statement introduces a new environment.
+    Environment blockEnv = new Environment(state.env);
+    State blockState = new State.withEnvironment(blockEnv, state);
+    Continuation cont;

[Kevin Millikin (Google), 2017/04/05 08:21:47]

Maybe it's a little hard to reason about this code because blockState is mutated
on each iteration.  All the states are the same except that they differ in the
continuation, so I think it's clearer to just change the continuation:

Continuation cont = state.continuation;
for (Statement stmt in node.statements.reversed) {
  cont = new Continuation(stmt, blockState.withContinuation(cont));
}
return cont;


We might also consider short-circuiting the transition

exec({s0, ...}, state) -> Continuation(s0, state') -> exec(s0, state')

which would look something like:

if (node.statements.isEmpty) return state.continuation;

State blockState =
    new State.withEnvironment(new Environment(state.environment));
// Construct the continuation of the first statement.
Continuation cont = state.continuation;
for (Statement stmt in node.statements.skip(1).reversed) {
    cont = new Continuation(stmt, blockState.withContinuation(cont));
}
return exec(node.statements.first, blockState.withContinuation(cont));

[zhivkag, 2017/04/05 10:00:19]

Done.
Acknowledged.

+    for (Statement s in node.statements.reversed) {
+      cont = new Continuation(s, blockState);
+      blockState = new State.withContinuation(cont, blockState);
     }
+    return cont != null ? cont : state.continuation;
   }
 
-  visitEmptyStatement(EmptyStatement node, env) {}
+  Continuation visitEmptyStatement(EmptyStatement node, state) {
+    return state.continuation;
+  }
 
-  visitIfStatement(IfStatement node, env) {
-    Value condition = eval(node.condition, env).toBoolean();
-    if (identical(Value.trueInstance, condition)) {
-      exec(node.then, env);
-    } else {
-      exec(node.otherwise, env);
+  Continuation visitIfStatement(IfStatement node, state) {
+    Value cond = eval(node.condition, state.env).toBoolean();
+    if (identical(Value.trueInstance, cond)) {
+      return new Continuation(node.then, state);

[Kevin Millikin (Google), 2017/04/05 08:21:47]

Here we can (should?) have:

return exec(node.then, state);

[zhivkag, 2017/04/05 10:00:19]

Acknowledged.

+    } else if (node.otherwise != null) {
+      return new Continuation(node.otherwise, state);
     }
+    return state.continuation;
+  }
+
+  Continuation visitLabeledStatement(LabeledStatement node, state) {
+    state.addLabel(node);
+    return new Continuation(node.body, state);
+  }
+
+  Continuation visitBreakStatement(BreakStatement node, state) {
+    return state.lookupLabel(node.target).continuation;
+  }
+
+  Continuation visitWhileStatement(WhileStatement node, state) {
+    Value cond = eval(node.condition, state.env).toBoolean();
+    if (identical(Value.trueInstance, cond)) {
+      // Add continuation for the While statement to the linked list.
+      Continuation c = new Continuation(node, state);
+      // Continuation for the body of the loop.
+      return new Continuation(node.body, new State.withContinuation(c, state));

[Kevin Millikin (Google), 2017/04/05 08:21:47]

return exec(node.body, state.withContinuation(c));

[zhivkag, 2017/04/05 10:00:19]

Acknowledged.

+    }
+    return state.continuation;
+  }
+
+  Continuation visitDoStatement(DoStatement node, state) {
+    WhileStatement whileStatement =
+        new WhileStatement(node.condition, node.body);
+    Continuation c = new Continuation(whileStatement, state);
+    return new Continuation(node.body, new State.withContinuation(c, state));
   }
 
-  visitVariableDeclaration(VariableDeclaration node, env) {
+  Continuation visitVariableDeclaration(VariableDeclaration node, state) {
     Value value = node.initializer != null
-        ? eval(node.initializer, env)
+        ? eval(node.initializer, state.env)
         : Value.nullInstance;
-    env.expand(node, value);
+    state.env.expand(node, value);
+    return state.continuation;
   }
 }
 
 typedef Value Getter(Value receiver);
 typedef void Setter(Value receiver, Value value);
 
-// TODO(zhivkag): Change misleading name.
-// This is representation of a class in the interpreter, not a declaration.
 class Class {
   static final Map<Reference, Class> _classes = <Reference, Class>{};