Implement support for variables and evaluation of logic expressions

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 kernerl.interpreter;
 
-import 'dart:collection';
 import '../ast.dart';
 
 class NotImplemented {
   String message;
 
   NotImplemented(this.message);
 
   String toString() => message;
 }
 
 class Interpreter {
   Program program;
 
   Interpreter(this.program);
 
   void evalProgram() {

[Kevin Millikin (Google), 2017/03/15 10:01:23]

Program's don't produce values, and maybe we should reserve the term 'evaluate'
for finding something's value.  evalProgram ==> runProgram?

Perhaps program is implied (it's not an argument), so I'd actually just call
this 'run()'.

[zhivkag, 2017/03/15 11:48:52]

Done.

     assert(program.libraries.isEmpty);
     Procedure mainMethod = program.mainMethod;
     Statement statementBlock = mainMethod.function.body;
-    // Evaluate only statement with one expression, ExpressionStatement, which
-    // is StaticInvocation of the method print.
+    // Evaluates only ExpressionStatements and VariableDeclarations in the top

[Kevin Millikin (Google), 2017/03/15 10:01:23]

Evaluates ==> Executes.

[zhivkag, 2017/03/15 11:48:53]

Done.

+    // BlockStatement.
     if (statementBlock is Block) {
-      Statement statement = statementBlock.statements.first;
-      if (statement is ExpressionStatement) {
-        statement.expression.accept1(new ExpressionEval1(),
-            new ExpressionState(new HashMap<String, Object>()));
+      var exprEval = new ExpressionEval();

[Kevin Millikin (Google), 2017/03/15 10:01:24]

So far ExpressionEval doesn't have any state, so I think it would be more
obvious to make it a member of class Interpreter.

I think expression is implied by evaluator and I prefer to avoid abbreviations. 
exprEval -> evaluator.

[zhivkag, 2017/03/15 11:48:53]

Done.

+      var env = new Environment.empty();
+
+      for (Statement s in statementBlock.statements) {
+        if (s is ExpressionStatement) {
+          s.expression.accept1(exprEval, env);

[Kevin Millikin (Google), 2017/03/15 10:01:23]

It reads more nicely to have a method

Value eval(Expression expr, Environment env) => expr.accept1(this, env);

in class ExpressionEval, and not call accept1 directly.

[zhivkag, 2017/03/15 11:48:52]

Done.

+        } else if (s is VariableDeclaration) {
+          env.expand(s, s.initializer.accept1(exprEval, env));
+        } else {
+          throw new NotImplemented('Evaluation for statement type '
+              '${s.runtimeType} is not implemented.');
+        }
       }
     } else {
       throw new NotImplemented('Evaluation for statement type '
-          '${statementBlock.runtimeType} is not implemented');
+          '${statementBlock.runtimeType} is not implemented.');
     }
   }
 }
 
 class InvalidExpressionError {
   InvalidExpression expression;
 
   InvalidExpressionError(this.expression);
 
-  String toString() => 'Invalid expression at '
-      '${expression.location.toString()}';
+  String toString() =>
+      'Invalid expression at ${expression.location.toString()}';
 }
 
-class ExpressionState {
-  Map<String, Object> environment;
+class Binding {

[Kevin Millikin (Google), 2017/03/15 10:01:24]

Ultimately we should have really detailed comments for classes like this.  I
think it's fine to leave them until later because things will change, but we
should plan to spend some time just writing comments as documentation.

[zhivkag, 2017/03/15 11:48:53]

Acknowledged.

+  final VariableDeclaration variable;
+  Value value;
 
-  ExpressionState(this.environment);
+  Binding(this.variable, this.value);
 }
 
-class ExpressionEval1 extends ExpressionVisitor1<Object> {
-  @override
-  Object defaultExpression(Expression node, arg) {
+class Environment {
+  final List<Binding> bindings = <Binding>[];
+  Environment parent;

[Kevin Millikin (Google), 2017/03/15 10:01:24]

final Environment parent;

[zhivkag, 2017/03/15 11:48:52]

Done.

+
+  Environment.empty();
+  Environment(this.parent);
+
+  Binding lookupBinding(VariableDeclaration variable) {

[Kevin Millikin (Google), 2017/03/15 10:01:23]

I'd make this the recursive function (and never return null):

assert(contains(variable))
for (var b in bindings.reversed) {
  if (identical(b.variable, variable)) return b;
}
return parent.lookup(variable);

I'd also use identical here and in other places where we mean 'the same object'
to dodge any questions about Dart's overridable operator==.

[zhivkag, 2017/03/15 11:48:52]

Done.

+    for (Binding b in bindings) {
+      if (b.variable == variable) return b;
+    }
+    return null;
+  }
+
+  Value lookup(VariableDeclaration variable) {

[Kevin Millikin (Google), 2017/03/15 10:01:23]

Then this is:

return lookupBinding(variable).value;

[zhivkag, 2017/03/15 11:48:52]

Done.

+    return lookupBinding(variable)?.value ??
+        parent?.lookup(variable) ??
+        error(variable);
+  }
+
+  void assign(VariableDeclaration variable, Value value) {

[Kevin Millikin (Google), 2017/03/15 10:01:23]

And this is:

lookupBinding(variable).value = value;

[zhivkag, 2017/03/15 11:48:53]

Done.

+    var b = lookupBinding(variable);
+    if (b != null) {
+      b.value = value;
+    } else if (parent != null) {
+      parent.assign(variable, value);
+    } else {
+      error(variable);
+    }
+  }
+
+  void expand(VariableDeclaration variable, Value value) {
+    if (lookupBinding(variable) != null) {

[Kevin Millikin (Google), 2017/03/15 10:01:23]

Variable declarations should be unique.  We could just
assert(!contains(variable)), if we implemented contains.

[zhivkag, 2017/03/15 11:48:52]

Done.

+      error(variable);
+    }
+    bindings.add(new Binding(variable, value));
+  }
+}
+
+class ExpressionEval extends ExpressionVisitor1<Value> {

[Kevin Millikin (Google), 2017/03/15 10:01:24]

class Evaluator?

[zhivkag, 2017/03/15 11:48:52]

Done.

+  Value defaultExpression(Expression node, arg) {
     throw new NotImplemented('Evaluation for expressions of type '
         '${node.runtimeType} is not implemented.');
   }
 
-  Object visitInvalidExpression1(InvalidExpression node, arg) =>
-      throw new InvalidExpressionError(node);
+  Value visitInvalidExpression1(InvalidExpression node, arg) {
+    throw new InvalidExpressionError(node);
+  }
 
-  Object visitStaticInvocation(StaticInvocation node, arg) {
+  Value visitVariableGet(VariableGet node, arg) {

[Kevin Millikin (Google), 2017/03/15 10:01:24]

arg ==> env.

[zhivkag, 2017/03/15 11:48:53]

Done.

+    return arg.lookup(node.variable);
+  }
+
+  Value visitVariableSet(VariableSet node, arg) {
+    return arg.assign(node.variable, node.value.accept1(this, arg));
+  }
+
+  Value visitStaticInvocation(StaticInvocation node, arg) {
     if ('print' == node.name.toString()) {
       // Special evaluation of print.
       var res = node.arguments.positional[0].accept1(this, arg);
-      print(res);
+      print(res.value);
+      return null;

[Kevin Millikin (Google), 2017/03/15 10:01:23]

Not null, but new NullValue().

We should make canonical instances for null, true, and false.  One way to do
that is to have them as static fields in class Value so here it is:

return Value.nullInstance;

[zhivkag, 2017/03/15 11:48:52]

Acknowledged.

     } else {
       throw new NotImplemented('Support for statement type '
           '${node.runtimeType} is not implemented');
     }
   }
 
+  Value visitNot(Not node, arg) {
+    return new BoolValue(!node.operand.accept1(this, arg).asBool);

[Kevin Millikin (Google), 2017/03/15 10:01:23]

I think I'd do the boolean conversion a little differently.  It's hard for the
reader to look at all the asBool overrides to see exactly what function is being
implemented.  I would also make it return a Value, not a Dart bool.  I wouldn't
use the word 'as' in the name, because Dart's as throws if the operand doesn't
have the required type, and this is a total function.

Suggest, in class Value:

BoolValue toBoolean() {
  return identical(this, Value.trueInstance)
      ? Value.trueInstance
      : Value.falseInstance;
}

Here, maybe:

var operand = eval(node.operand, env).toBoolean();
return identical(operand, Value.trueInstance)
    ? Value.falseInstance
    : Value.trueInstance;

[zhivkag, 2017/03/15 11:48:53]

Acknowledged.

+  }
+
+  Value visitLogicalExpression(LogicalExpression node, arg) {
+    bool left = node.left.accept1(this, arg).asBool;
+
+    if ('||' == node.operator) {

[Kevin Millikin (Google), 2017/03/15 10:01:24]

We might want a more literal interpretation of the spec for expression
evaluation, which describes dispatching on the operator before evaluating the
left-hand side:

if (node.operator == '||') {
  var left = eval(node.left, env).toBoolean();
  if (identical(left, Value.trueInstance)) return Value.trueInstance;
  return eval(node.right, env).toBoolean();
}

[zhivkag, 2017/03/15 11:48:52]

Acknowledged.

+      return left
+          ? new BoolValue(true)
+          : new BoolValue(node.right.accept1(this, arg).asBool);
+    } else {
+      assert('&&' == node.operator);
+      return !left
+          ? new BoolValue(false)
+          : new BoolValue(node.right.accept1(this, arg).asBool);
+    }
+  }
+
+  Value visitConditionalExpression(ConditionalExpression node, arg) {
+    if (node.condition.accept1(this, arg).asBool) {
+      return node.then.accept1(this, arg);
+    } else {
+      return node.otherwise.accept1(this, arg);
+    }
+  }
+
+  Value visitStringConcatenation(StringConcatenation node, arg) {
+    StringBuffer res = new StringBuffer();
+    for (Expression e in node.expressions) {
+      res.write(e.accept1(this, arg).value);
+    }
+    return new StringValue(res.toString());
+  }
+
   // Evaluation of BasicLiterals.
-  Object visitStringLiteral(StringLiteral node, arg) => node.value;
-  Object visitIntLiteral(IntLiteral node, arg) => node.value;
-  Object visitDoubleLiteral(DoubleLiteral node, arg) => node.value;
-  Object visitBoolLiteral(BoolLiteral node, arg) => node.value;
-  Object visitNullLiteral(NullLiteral node, arg) => node.value;
+  Value visitStringLiteral(StringLiteral node, arg) =>
+      new StringValue(node.value);
+  Value visitIntLiteral(IntLiteral node, arg) => new IntValue(node.value);
+  Value visitDoubleLiteral(DoubleLiteral node, arg) =>
+      new DoubleValue(node.value);
+  Value visitBoolLiteral(BoolLiteral node, arg) => new BoolValue(node.value);
+  Value visitNullLiteral(NullLiteral node, arg) => new NullValue();
+
+  Value visitLet(Let node, arg) {
+    var letEnv = new Environment(arg);

[Kevin Millikin (Google), 2017/03/15 10:01:23]

It might be more clear to name the value instead of the new environment:

var value = eval(node.variable.initializer, env);
return eval(node.body, new Environment(env).expand(node.variable, value));

[zhivkag, 2017/03/15 11:48:52]

Acknowledged.

+    letEnv.expand(node.variable, node.variable.initializer.accept1(this, arg));
+    return node.body.accept1(this, letEnv);
+  }
 }
+
+abstract class Value {
+  Object get value;
+  bool get asBool;
+}
+
+class StringValue extends Value {
+  String value;
+
+  bool get asBool => false;
+
+  StringValue(this.value);
+}
+
+class IntValue extends Value {
+  int value;
+
+  bool get asBool => false;
+
+  IntValue(this.value);
+}
+
+class DoubleValue extends Value {
+  double value;
+
+  bool get asBool => false;
+
+  DoubleValue(this.value);
+}
+
+class BoolValue extends Value {
+  bool value;
+
+  bool get asBool => value;
+
+  BoolValue(this.value);
+}
+
+class NullValue extends Value {
+  Object get value => null;
+  bool get asBool => false;
+}
+
+Object error(obj) {
+  // TODO: Implement accordingly with support for error handling.
+  throw new ArgumentError(obj);
+}