Mutable Variables

Now that we know the sort of problem we want to tackle, let’s see what this looks like in the context of our little Kaleidoscope language. We’re going to add two features:

  • The ability to mutate variables with the ‘=’ operator.
  • The ability to define new variables.

While the first item is really what this is about, we only have variables for incoming arguments as well as for induction variables, and redefining those only goes so far :). Also, the ability to define new variables is a useful thing regardless of whether we will be mutating them. Here’s a motivating example that shows how we could use these:

  1. # Define ':' for sequencing: as a low-precedence operator that ignores operands
  2. # and just returns the RHS.
  3. def binary : 1 (x y) y;
  5. # Recursive fib, we could do this before.
  6. def fib(x)
  7.   if (x < 3) then
  8.     1
  9.   else
  10.     fib(x-1)+fib(x-2);
  12. # Iterative fib.
  13. def fibi(x)
  14.   var a = 1, b = 1, c = 0 in
  15.   (for i = 3, i < x in
  16.      c = (a + b) :
  17.      a = b :
  18.      b = c) :
  19.   b;
  21. # Call it.
  22. fibi(10);

At this point in Kaleidoscope’s development, it only supports variables for two things: incoming arguments to functions and the induction variable of ‘for’ loops. For consistency, we’ll allow mutation of these variables in addition to other user-defined variables. This means that these will both need memory locations.

We introduce a new var syntax which behaves much like the let notation in Haskell. We will let the user define a sequence of new variable names and inject these new variables into the symbol table.

  1. data Expr
  2.   ...
  3.   | Let Name Expr Expr
  4.   deriving (Eq, Ord, Show)

The parser for it will allow for multiple declarations on a single line and right fold the AST node bodies, allowing us to use variables declared earlier in the list in subsequent declarations (i.e. var x = 3, y = x + 1).

  1. letins :: Parser Expr
  2. letins = do
  3.   reserved "var"
  4.   defs <- commaSep $ do
  5.     var <- identifier
  6.     reservedOp "="
  7.     val <- expr
  8.     return (var, val)
  9.   reserved "in"
  10.   body <- expr
  11.   return $ foldr (uncurry Let) body defs

The code generation for this new syntax is very straight forward, we simply allocate a new reference and assign it to the name given then return the assigned value.

  1. cgen (S.Let a b c) = do
  2.   i <- alloca double
  3.   val <- cgen b
  4.   store i val
  5.   assign a i
  6.   cgen c

We can test out this new functionality. Note that code below is unoptimized and involves several extranous instructions that would normally be optimized away by mem2reg.

  1. ready> def main(x) var y = x + 1 in y;
  2. ; ModuleID = 'my cool jit'
  4. define double @main(double %x) {
  5. entry:
  6.   %0 = alloca double
  7.   store double %x, double* %0
  8.   %1 = alloca double
  9.   %2 = load double* %0
  10.   %3 = fadd double %2, 1.000000e+00
  11.   store double %3, double* %1
  12.   %4 = load double* %1
  13.   ret double %4
  14. }
  16. Evaluated to: 1.0