» CS 330: Lecture 10 – Conditionals and Loops

CS 330: Lecture 10 – Conditionals and Loops

February 19, 2018 by Chris Johnson. Filed under cs330, lectures, spring 2018.

Dear students,

The dream of every machine is to amplify human effort—turning a little force at the input end to a big effect at the output end. Our language is starting to have this quality. With just a few utterances we can draw a picture. But there are still two big things missing from it: loops and functions. Before diving into implementing these featuers, let’s start with an exercise for you and your neighbor:

Recall from last class that we modeled a while loop as a condition expression and a block of statements. How shall we model a function definition? What parts and pieces do we need to store in our AST? How shall we model a function call?

Here’s how I’d model these.

A function definition needs to know three things: the name of the function, the list of formal parameter names, and the block of statements that form the function’s body. A function call needs to know two things: the name of the function and the list of actual parameter values that will get passed to the function.

Let’s start by implementing a loop with this model:

function ExpressionWhile(condition, block) {
  this.evaluate = function(env) {
    while (condition.evaluate(env) != 0) {
      block.evaluate(env);
    }
  }
}

We don’t have booleans in our language. We’ll just say 0 is false and everything else is true.

Loops are statements in our language, so we add this to the statement rule of our parser:

else if (has(WHILE)) {
  return loop();
}

Handling loops is complicated enough that it deserves its own function:

function loop() {
  devour(); // eat while

  var condition = expression();

  var statements = [];
  while (i < tokens.length && !has(END)) {
    statements.push(statement());
  }

  if (!has(END)) {
    throw 'expected END';
  }
  devour(); // eat end

  var block = new Block(statements);

  return new ExpressionWhile(condition, block);
}

If this works, we can exert very little effort to produce some reasonably interesting output. Like this:

i = 0
while i < 25
  inset = i * 10
  radius = 250 - i * 10
  red = i * 10
  green = i * 10
  blue = i * 10
  rectangle inset inset (2 * radius) (2 * radius)
  i = i + 1
end

Conditional statements are very similar to loops, except they have two blocks and they choose which one to evaluate. Here’s our model:

function ExpressionIf(condition, thenBlock, elseBlock) {
  this.evaluate = function(env) {
    var value = condition.evaluate(env);
    if (value != 0) {
      thenBlock.evaluate(env);
    } else {
      elseBlock.evaluate(env);
    }
  }
}

And our new logic for the parser’s statement rule:

else if (has(IF)) {
  return conditional();
}

With the accompanying helper function:

function conditional() {
  devour(); // eat if

  var condition = expression();

  var thenStatements = [];
  while (i < tokens.length && !has(ELSE)) {
    thenStatements.push(statement());
  }

  if (!has(ELSE)) {
    throw 'expected ELSE';
  }

  devour(); // eat else
  var elseStatements = [];
  while (i < tokens.length && !has(END)) {
    elseStatements.push(statement());
  }

  if (!has(END)) {
    throw 'expected END';
  }
  devour(); // eat end

  var thenBlock = new Block(thenStatements);
  var elseBlock = new Block(elseStatements);

  return new ExpressionIf(condition, thenBlock, elseBlock);
}

The last big thing is to add functions. Suppose we want to draw a relocatable snowman. I propose this syntax:

to snowman(x y)
  circle x y 20
  circle x (y - 24) 15
  circle x (y - 43) 10
end

snowman(30 100)

As always, when we add new constructs to our language, we should start with the grammar. Here it is with function definitions and calls:

statement
  : RECTANGLE expr expr expr expr
  | CIRCLE expr expr expr
  | PRINT expr
  | IDENTIFIER ASSIGN expr 
  | IF expr statement* ELSE statement* END
  | WHILE expr statement* END
  | TO IDENTIFIER LEFT_PARENTHESIS IDENTIFIER* RIGHT_PARENTHESIS statement* END
  | IDENTIFIER LEFT_PARENTHESIS expr* RIGHT_PARENTHESIS

We model our function definition in the following way:

function StatementFunctionDefine(name, formals, body) {
  this.evaluate = function(env) {
    env[name] = {name: name, formals: formals, body: body};
  }
}

Defining a function isn’t all that magic. We just keep record of the code and what parameters it expects.

And let’s add a sloppy rule to our parser to construct one of these:

else if (has(TO)) {
  devour(); // eat TO
  var idToken = devour();
  devour(); // eat (

  var formals = [];
  while (has(IDENTIFIER)) {
    var formalToken = devour();
    formals.push(formalToken.source);
  }

  devour(); // eat )

  var statements = [];
  while (i < tokens.length && !has(END)) {
    statements.push(statement());
  }

  devour(); // eat END

  return new StatementFunctionDefine(idToken.source, formals, new Block(statements));
}

We really should assert that we actually do see the tokens we think we’re seeing.

What about a function call? This is the place that feels the most magical to me. We have attach give the formals the appropriate values, which come from the actual parameters. How can we make that happen? We can make a new environment, one which binds the actual parameters to the formals.

function StatementFunctionCall(name, actuals) {
  this.evaluate = function(env) {
    if (env.hasOwnProperty(name)) {
      var f = env[name];

      var innerScope = {};
      actuals.forEach((actual, i) => {
        var formal = f.formals[i];
        innerScope[formal] = actual.evaluate(env);
      });

      f.body.evaluate(innerScope);
    } else {
      throw 'no such function ' + name;
    }
  }
}

Our parser needs a new rule too. Since two statements start with an IDENTIFIER token, we need to look at the second token to determine if we’ve got a variable assignment or a function call. Here’s our new rule:

else if (has(IDENTIFIER)) {
  var idToken = devour();
  if (has(ASSIGN)) {
    devour();
    var rhs = expression();
    return new StatementAssignment(idToken.source, rhs);
  } else if (has(LEFT_PARENTHESIS)) {
    devour();
    var actuals = [];
    while (!has(RIGHT_PARENTHESIS)) {
      actuals.push(expression());
    }
    devour();
    return new StatementFunctionCall(idToken.source, actuals);
  } else if (!has(ASSIGN)) {
    throw 'Curses. ' + tokens[i];
  }
}

That rounds out our language. Let’s take it for a spin!

to snowman(x y)
  circle x y 20
  circle x (y - 24) 15
  circle x (y - 43) 10
end

j = 0
while j < 6
  i = 0
  while i < 14
    snowman((30 + i * 40) (100 + j * 90)) 
    i = i + 1
  end
  j = j + 1
end

Here’s your TODO list:

For next Monday, write an interesting program in our language. I’ve uploaded our interpreter. Share the code and a screenshot on Piazza under folder teip.
Fix any Regexercise issues by the end of the day.
Start the Terp homework. For this homework and this homework only, you may work with a partner. README.md, which contains a description and your grammar) is due before March 5. But the interpreter itself is due by the end of the semester.
We will not have class Wednesday or Friday. I am attending a conference to become a better teacher and human being. You can meet with your partner and write a programming language!

See you next time!

Sincerely,

P.S. Here’s a haiku just for you:

I love naming things
Things with names are important
They leave the foobag

P.P.S. Here’s the code we wrote together:

scanchuk.rb

#!/usr/bin/env ruby

sentence = %q{the quick brown fox jumped over the lazy dog}

# sentence.scan(/(\w+)/) do |matches|
  # puts matches[0].inspect
# end

sentence.scan(/the/) do
  puts "$`: #{$`}"
  puts "$&: #{$&}"
  puts "$': #{$'}"
  puts ""
end

lexer.js

var IDENTIFIER = 'IDENTIFIER';
var PLUS = 'PLUS';
var EOF = 'EOF';
var LEFT_PARENTHESIS = 'LEFT_PARENTHESIS';
var RECTANGLE = 'RECTANGLE';
var CIRCLE = 'CIRCLE';
var RIGHT_PARENTHESIS = 'RIGHT_PARENTHESIS';
var DIVIDE = 'DIVIDE';
var MINUS = 'MINUS';
var ASTERISK = 'ASTERISK';
var COMMA = 'COMMA';
var MOD = 'MOD';
var INTEGER = 'INTEGER';
var WHILE = 'WHILE';
var IF = 'IF';
var ELSE = 'ELSE';
var END = 'END';
var MORE_OR_EQUAL = 'MORE_OR_EQUAL';
var MORE = 'MORE';
var LESS_OR_EQUAL = 'LESS_OR_EQUAL';
var LESS = 'LESS';
var EQUAL = 'EQUAL';
var NOT_EQUAL = 'NOT_EQUAL';
var PRINT = 'PRINT';
var ASSIGN = 'ASSIGN';
var TO = 'TO';

function lex(source) {
  var tokens = [];
  var tokenSoFar = '';
  var i = 0;

  function has(regex) {
    return source.charAt(i).match(regex);
  }

  function devour() {
    tokenSoFar += source.charAt(i);
    i += 1;
  }

  function emit(type) {
    tokens.push({type: type, source: tokenSoFar});
    tokenSoFar = '';
  }

  while (i < source.length) {
    if (has(/\+/)) {
      devour();
      emit(PLUS);
    } else if (has(/%/)) {
      devour();
      emit(MOD);
    } else if (has(/!/)) {
      devour();
      if (has(/=/)) {
        devour();
        emit(NOT_EQUAL);
      } else {
        throw 'expected = after !';
      }
    } else if (has(/=/)) {
      devour();
      if (has(/=/)) {
        devour();
        emit(EQUAL);
      } else {
        emit(ASSIGN);
      }
    } else if (has(/</)) {
      devour();
      if (has(/=/)) {
        devour();
        emit(LESS_OR_EQUAL);
      } else {
        emit(LESS);
      }
    } else if (has(/>/)) {
      devour();
      if (has(/=/)) {
        devour();
        emit(MORE_OR_EQUAL);
      } else {
        emit(MORE);
      }
    } else if (has(/-/)) {
      devour();
      emit(MINUS);
    } else if (has(/\(/)) {
      devour();
      emit(LEFT_PARENTHESIS);
    } else if (has(/\)/)) {
      devour();
      emit(RIGHT_PARENTHESIS);
    } else if (has(/\*/)) {
      devour();
      emit(ASTERISK);
    } else if (has(/\//)) {
      devour();
      if (has(/\//)) {
        while (has(/[^\n]/)) {
          devour();
        }
        tokenSoFar = '';
      } else {
        emit(DIVIDE);
      }
    } else if (has(/\d/)) {
      while (has(/\d/)) {
        devour();
      }
      emit(INTEGER);
    } else if (has(/[a-zA-Z]/)) {
      while (has(/[a-zA-Z0-9]/)) {
        devour();
      }

      if (tokenSoFar == 'rectangle') {
        emit(RECTANGLE);
      } else if (tokenSoFar == 'circle') {
        emit(CIRCLE);
      } else if (tokenSoFar == 'while') {
        emit(WHILE);
      } else if (tokenSoFar == 'if') {
        emit(IF);
      } else if (tokenSoFar == 'else') {
        emit(ELSE);
      } else if (tokenSoFar == 'end') {
        emit(END);
      } else if (tokenSoFar == 'print') {
        emit(PRINT);
      } else if (tokenSoFar == 'to') {
        emit(TO);
      } else {
        emit(IDENTIFIER);
      }
    } else if (has(/\s/)) {
      devour();
      tokenSoFar = '';
    } else {
      throw 'ack! [' + tokenSoFar + ']';
    }
  }

  emit(EOF);

  return tokens;
}

ast.js

function Block(statements) {
  this.evaluate = function(env) {
    statements.forEach(statement => statement.evaluate(env));
  }
}

function StatementCircle(originXExpression, originYExpression, radiusExpression) {
  this.evaluate = function(env) {
    var originX = originXExpression.evaluate(env); 
    var originY = originYExpression.evaluate(env); 
    var radius = radiusExpression.evaluate(env); 
    context.fillStyle = 'rgb(' + env.red + ',' + env.green + ',' + env.blue + ')';
    context.beginPath();
    context.arc(originX, originY, radius, 0, 2 * Math.PI);
    context.fill();
  }
}

function StatementRectangle(leftExpression, topExpression, widthExpression, heightExpression) {
  this.evaluate = function(env) {
    var l = leftExpression.evaluate(env); 
    var t = topExpression.evaluate(env); 
    var w = widthExpression.evaluate(env); 
    var h = heightExpression.evaluate(env); 
    context.fillStyle = 'rgb(' + env.red + ',' + env.green + ',' + env.blue + ')';
    context.fillRect(l, t, w, h);
  }
}

function StatementPrint(messageExpression) {
  this.evaluate = function(env) {
    var message = messageExpression.evaluate(env); 
    console.log(message);
  }
}

function ExpressionIntegerLiteral(literal) {
  this.evaluate = function(env) {
    return literal;
  }
}

function ExpressionVariableReference(id) {
  this.evaluate = function(env) {
    return env[id];
  }
}

function StatementAssignment(id, rhsExpression) {
  this.evaluate = function(env) {
    env[id] = rhsExpression.evaluate(env);
  }
}

function ExpressionAdd(lExpression, rExpression) {
  this.evaluate = function(env) {
    return lExpression.evaluate(env) + rExpression.evaluate(env);
  }
}

function ExpressionSubtract(lExpression, rExpression) {
  this.evaluate = function(env) {
    return lExpression.evaluate(env) - rExpression.evaluate(env);
  }
}

function ExpressionMultiply(a, b) {
  this.evaluate = function(env) {
    var valueA = a.evaluate(env);
    var valueB = b.evaluate(env);
    return valueA * valueB;
  }
}

function ExpressionDivide(a, b) {
  this.evaluate = function(env) {
    var valueA = a.evaluate(env);
    var valueB = b.evaluate(env);
    return valueA / valueB;
  }
}

function ExpressionMod(a, b) {
  this.evaluate = function(env) {
    var valueA = a.evaluate(env);
    var valueB = b.evaluate(env);
    return valueA % valueB;
  }
}

function ExpressionMore(a, b) {
  this.evaluate = function(env) {
    var valueA = a.evaluate(env);
    var valueB = b.evaluate(env);
    return valueA > valueB;
  }
}

function ExpressionMoreOrEqual(a, b) {
  this.evaluate = function(env) {
    var valueA = a.evaluate(env);
    var valueB = b.evaluate(env);
    return valueA >= valueB;
  }
}

function ExpressionLess(a, b) {
  this.evaluate = function(env) {
    var valueA = a.evaluate(env);
    var valueB = b.evaluate(env);
    return valueA < valueB;
  }
}

function ExpressionLessOrEqual(a, b) {
  this.evaluate = function(env) {
    var valueA = a.evaluate(env);
    var valueB = b.evaluate(env);
    return valueA <= valueB;
  }
}

function ExpressionEqual(a, b) {
  this.evaluate = function(env) {
    var valueA = a.evaluate(env);
    var valueB = b.evaluate(env);
    return valueA == valueB;
  }
}

function ExpressionNotEqual(a, b) {
  this.evaluate = function(env) {
    var valueA = a.evaluate(env);
    var valueB = b.evaluate(env);
    return valueA != valueB;
  }
}

function StatementWhile(conditionExpression, block) {
  this.evaluate = function(env) {
    while (conditionExpression.evaluate(env) != 0) {
      block.evaluate(env);
    }
  }
}

function StatementFunctionDefine(name, formals, block) {
  this.evaluate = function(env) {
    env[name] = {name: name, formals: formals, block: block};
  }
}

function StatementFunctionCall(name, actuals) {
  this.evaluate = function(env) {
    var f = env[name];

    var innerScope = {};
    actuals.forEach((actual, i) => {
      var formal = f.formals[i];
      innerScope[formal] = actual.evaluate(env);
    });

    f.block.evaluate(innerScope);
  }
}

function ExpressionIf(condition, thenBlock, elseBlock) {
  this.evaluate = function(env) {
    var value = condition.evaluate(env);
    if (value != 0) {
      thenBlock.evaluate(env);
    } else {
      elseBlock.evaluate(env);
    }
  }
}

parser.js

function parse(tokens) {
  var i = 0;

  function has(tokenType) {
    return i < tokens.length && tokens[i].type == tokenType;
  }

  function devour() {
    var token = tokens[i];
    i++;
    return token;
  }

  function program() {
    var statements = [];
    while (!has(EOF)) {
      statements.push(statement());
    }
    return new Block(statements);
  }

  function conditional() {
    devour(); // eat if

    var condition = expression();

    var thenStatements = [];
    while (i < tokens.length && !has(ELSE)) {
      thenStatements.push(statement());
    }

    if (!has(ELSE)) {
      throw 'expected ELSE';
    }

    devour(); // eat else
    var elseStatements = [];
    while (i < tokens.length && !has(END)) {
      elseStatements.push(statement());
    }

    if (!has(END)) {
      throw 'expected END';
    }
    devour(); // eat end

    var thenBlock = new Block(thenStatements);
    var elseBlock = new Block(elseStatements);

    return new ExpressionIf(condition, thenBlock, elseBlock);
  }

  function loop() {
    devour();
    var condition = expression();
    var statements = [];
    while (!has(END)) {
      statements.push(statement());
    }
    devour();
    return new StatementWhile(condition, new Block(statements));
  }

  function define() {
    devour();
    var nameToken = devour(); // hey, later assert that token is an IDENTIFIER
    devour(); // eat (, hey, later assert that token is (
    var formals = [];
    while (!has(RIGHT_PARENTHESIS)) { // assert that we don't go off deep-end
      var formalToken = devour();
      formals.push(formalToken.source);
    }
    devour(); // eat ) ASSERT
    var statements = [];
    while (!has(END)) { // assert assert assert // assert assert assert // assert assert assert // assert assert assert // assert assert assert // assert assert assert // assert assert assert // assert assert assert // assert assert assert // assert assert assert // assert assert assert // assert assert assert
      statements.push(statement());
    }
    devour(); // assert
    return new StatementFunctionDefine(nameToken.source, formals, new Block(statements));
  }

  function statement() {
    if (has(RECTANGLE)) {
      devour();
      var leftExpression = expression();
      var topExpression = expression();
      var widthExpression = expression();
      var heightExpression = expression();
      return new StatementRectangle(leftExpression, topExpression, widthExpression, heightExpression);
    } else if (has(CIRCLE)) {
      devour();
      var originXExpression = expression();
      var originYExpression = expression();
      var radiusExpression = expression();
      return new StatementCircle(originXExpression, originYExpression, radiusExpression);
    } else if (has(TO)) {
      return define();
    } else if (has(IF)) {
      return conditional();
    } else if (has(WHILE)) {
      return loop();
    } else if (has(PRINT)) {
      devour();
      var message = expression();
      return new StatementPrint(message);
    } else if (has(IDENTIFIER)) {
      var idToken = devour();
      if (has(ASSIGN)) {
        devour();
        var rhs = expression();
        return new StatementAssignment(idToken.source, rhs);
      } else if (has(LEFT_PARENTHESIS)) {
        devour();
        var actuals = [];
        while (!has(RIGHT_PARENTHESIS)) {
          actuals.push(expression());
        }
        devour(); // eat )
        return new StatementFunctionCall(idToken.source, actuals);
      } else if (!has(ASSIGN)) {
        throw 'Curses. ' + tokens[i];
      }
    } else {
      throw 'You messed up big time, foobag. I don\'t know ' + tokens[i].source;
    }
  }

  function expression() {
    return relational();
  }

  function relational() {
    var a = additive();
    while (has(MORE_OR_EQUAL) || has(MORE) || has(LESS_OR_EQUAL) || has(LESS) || has(EQUAL) || has(NOT_EQUAL)) {
      var operator = tokens[i];
      devour(); // eat operator
      var b = additive();
      if (operator.type == MORE_OR_EQUAL) {
        a = new ExpressionMoreOrEqual(a, b);
      } else if (operator.type == MORE) {
        a = new ExpressionMore(a, b);
      } else if (operator.type == LESS_OR_EQUAL) {
        a = new ExpressionLessOrEqual(a, b);
      } else if (operator.type == LESS) {
        a = new ExpressionLess(a, b);
      } else if (operator.type == EQUAL) {
        a = new ExpressionEqual(a, b);
      } else {
        a = new ExpressionNotEqual(a, b);
      }
    }
    return a;
  }

  function additive() {
    var l = multiplicative();
    while (has(PLUS) || has(MINUS)) {
      var operatorToken = devour();
      var r = multiplicative();
      if (operatorToken.type == PLUS) {
        l = new ExpressionAdd(l, r);
      } else {
        l = new ExpressionSubtract(l, r);
      }
    }

    return l;
  }

  function multiplicative() {
    var a = atom();
    while (has(ASTERISK) || has(DIVIDE) || has(MOD)) {
      var operator = tokens[i];
      devour(); // eat operator
      var b = atom();
      if (operator.type == ASTERISK) {
        a = new ExpressionMultiply(a, b);
      } else if (operator.type == MOD) {
        a = new ExpressionMod(a, b);
      } else {
        a = new ExpressionDivide(a, b);
      }
    }
    return a;
  }

  function atom() {
    if (has(INTEGER)) {
      var token = devour();
      return new ExpressionIntegerLiteral(parseInt(token.source));
    } else if (has(IDENTIFIER)) {
      var token = devour();
      return new ExpressionVariableReference(token.source);
    } else if (has(LEFT_PARENTHESIS)) {
      devour();
      var e = expression();
      if (!has(RIGHT_PARENTHESIS)) {
        throw 'uz unbalanced';
      }
      devour();
      return e;
    } else {
      throw 'I expected an expression. That\'s NOT what I found. ' + tokens[i].source;
    }
  }

  return program();
}

index.html

<!DOCTYPE html>
<html>
<head>
  <title>...</title>
  <script src="lexer.js"></script>
  <script src="ast.js"></script>
  <script src="parser.js"></script>

  <style>
* {
  box-sizing: border-box;
}

#editor {
  padding: 5px;
  width: 30%;
  position: absolute;
  top: 0;
  left: 0;
  bottom: 30px;
}

#editor textarea {
  font-size: 18pt;
  width: 100%;
  height: 95%;
}

#tools {
  height: 5%;
  position: absolute;
  bottom: 0;
  right: 5px;
}

canvas {
  margin: 5px;
  margin-left: 0px;
  position: absolute;
  top: 0;
  left: 30%;
}
  </style>
</head>
<body>
  <div id="editor">
    <textarea id="ide" rows="8"></textarea>
    <div id="tools">
      <input type="range" id="slider" value="0" min="0" max="100">
      <input type="button" id="run" value="Run">
    </div>
  </div>
  <canvas id="canvas" width="600" height="600" style="background-color: lightgray;"></canvas><br>
  
  <script>
var ide = document.getElementById('ide');
var run = document.getElementById('run');
var slider = document.getElementById('slider');
var canvas = document.getElementById('canvas');
var context = canvas.getContext('2d');

function evaluate() {
  context.clearRect(0, 0, canvas.width, canvas.height);

  var source = ide.value;
  var tokens = lex(source);
  var ast = parse(tokens);

  var env = {t: slider.value, red: 255, green: 0, blue: 0};
  ast.evaluate(env);
}

run.onclick = evaluate;
slider.oninput = evaluate;

  </script>
</body>
</html>