Implement flow control with breaks

pkg/kernel/lib/interpreter/interpreter.dart

 // Copyright (c) 2017, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 library kernel.interpreter;
 
 import '../ast.dart';
 import '../ast.dart' as ast show Class;
 
 class NotImplemented {
   String message;
 
   NotImplemented(this.message);
 
   String toString() => message;
 }
 
 class Interpreter {
   Program program;
   StatementExecuter visitor = new StatementExecuter();
-  Environment env = new Environment.empty();
 
   Interpreter(this.program);
 
   void run() {
     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;
 
   Binding(this.variable, this.value);
 }
 
 class Environment {
   final List<Binding> bindings = <Binding>[];
   final Environment parent;
@@ skipping 24 matching lines @@
     assert(contains(variable));
     lookupBinding(variable).value = value;
   }
 
   void expand(VariableDeclaration variable, Value value) {
     assert(!contains(variable));
     bindings.add(new Binding(variable, value));
   }
 }
 
+/// Evaluate expressions.
 class Evaluator extends ExpressionVisitor1<Value> {
   Value eval(Expression expr, Environment env) => expr.accept1(this, env);
 
   Value defaultExpression(Expression node, env) {
     throw new NotImplemented('Evaluation for expressions of type '
         '${node.runtimeType} is not implemented.');
   }
 
   Value visitInvalidExpression1(InvalidExpression node, env) {
-    throw new InvalidExpressionError(node);
+    throw 'Invalid expression at ${node.location.toString()}';
   }
 
   Value visitVariableGet(VariableGet node, env) {
     return env.lookup(node.variable);
   }
 
   Value visitVariableSet(VariableSet node, env) {
     return env.assign(node.variable, eval(node.value, env));
   }
 
@@ skipping 111 matching lines @@
   Value visitNullLiteral(NullLiteral node, env) => Value.nullInstance;
 
   Value visitLet(Let node, env) {
     var value = eval(node.variable.initializer, env);
     var letEnv = new Environment(env);
     letEnv.expand(node.variable, value);
     return eval(node.body, letEnv);
   }
 }
 
+/// 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) {}
-
-  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 visitEmptyStatement(EmptyStatement node, state) {
+    return state.continuation;
   }
 
-  visitVariableDeclaration(VariableDeclaration node, 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));
+  }
+
+  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>{};
 
   Class superclass;
   List<Field> instanceFields = <Field>[];
   List<Field> staticFields = <Field>[];
   // Implicit getters and setters for instance Fields.
   Map<Name, Getter> getters = <Name, Getter>{};
   Map<Name, Setter> setters = <Name, Setter>{};
   // The initializers of static fields are evaluated the first time the field
@@ skipping 203 matching lines @@
 
 class NullValue extends LiteralValue {
   Object get value => null;
 
   const NullValue();
 }
 
 notImplemented({String m, Object obj}) {
   throw new NotImplemented(m ?? 'Evaluation for $obj is not implemented');
 }