docs/tutorial/LangImpl6.rst

   1 ============================================================
   2 Kaleidoscope: Extending the Language: User-defined Operators
   3 ============================================================
   4
   5 .. contents::
   6    :local:
   7
   8 Chapter 6 Introduction
   9 ======================
  10
  11 Welcome to Chapter 6 of the "`Implementing a language with
  12 LLVM <index.html>`_" tutorial. At this point in our tutorial, we now
  13 have a fully functional language that is fairly minimal, but also
  14 useful. There is still one big problem with it, however. Our language
  15 doesn't have many useful operators (like division, logical negation, or
  16 even any comparisons besides less-than).
  17
  18 This chapter of the tutorial takes a wild digression into adding
  19 user-defined operators to the simple and beautiful Kaleidoscope
  20 language. This digression now gives us a simple and ugly language in
  21 some ways, but also a powerful one at the same time. One of the great
  22 things about creating your own language is that you get to decide what
  23 is good or bad. In this tutorial we'll assume that it is okay to use
  24 this as a way to show some interesting parsing techniques.
  25
  26 At the end of this tutorial, we'll run through an example Kaleidoscope
  27 application that `renders the Mandelbrot set <#example>`_. This gives an
  28 example of what you can build with Kaleidoscope and its feature set.
  29
  30 User-defined Operators: the Idea
  31 ================================
  32
  33 The "operator overloading" that we will add to Kaleidoscope is more
  34 general than languages like C++. In C++, you are only allowed to
  35 redefine existing operators: you can't programatically change the
  36 grammar, introduce new operators, change precedence levels, etc. In this
  37 chapter, we will add this capability to Kaleidoscope, which will let the
  38 user round out the set of operators that are supported.
  39
  40 The point of going into user-defined operators in a tutorial like this
  41 is to show the power and flexibility of using a hand-written parser.
  42 Thus far, the parser we have been implementing uses recursive descent
  43 for most parts of the grammar and operator precedence parsing for the
  44 expressions. See `Chapter 2 <LangImpl2.html>`_ for details. Without
  45 using operator precedence parsing, it would be very difficult to allow
  46 the programmer to introduce new operators into the grammar: the grammar
  47 is dynamically extensible as the JIT runs.
  48
  49 The two specific features we'll add are programmable unary operators
  50 (right now, Kaleidoscope has no unary operators at all) as well as
  51 binary operators. An example of this is:
  52
  53 ::
  54
  55     # Logical unary not.
  56     def unary!(v)
  57       if v then
  58         0
  59       else
  60         1;
  61
  62     # Define > with the same precedence as <.
  63     def binary> 10 (LHS RHS)
  64       RHS < LHS;
  65
  66     # Binary "logical or", (note that it does not "short circuit")
  67     def binary| 5 (LHS RHS)
  68       if LHS then
  69         1
  70       else if RHS then
  71         1
  72       else
  73         0;
  74
  75     # Define = with slightly lower precedence than relationals.
  76     def binary= 9 (LHS RHS)
  77       !(LHS < RHS | LHS > RHS);
  78
  79 Many languages aspire to being able to implement their standard runtime
  80 library in the language itself. In Kaleidoscope, we can implement
  81 significant parts of the language in the library!
  82
  83 We will break down implementation of these features into two parts:
  84 implementing support for user-defined binary operators and adding unary
  85 operators.
  86
  87 User-defined Binary Operators
  88 =============================
  89
  90 Adding support for user-defined binary operators is pretty simple with
  91 our current framework. We'll first add support for the unary/binary
  92 keywords:
  93
  94 .. code-block:: c++
  95
  96     enum Token {
  97       ...
  98       // operators
  99       tok_binary = -11,
 100       tok_unary = -12
 101     };
 102     ...
 103     static int gettok() {
 104     ...
 105         if (IdentifierStr == "for")
 106           return tok_for;
 107         if (IdentifierStr == "in")
 108           return tok_in;
 109         if (IdentifierStr == "binary")
 110           return tok_binary;
 111         if (IdentifierStr == "unary")
 112           return tok_unary;
 113         return tok_identifier;
 114
 115 This just adds lexer support for the unary and binary keywords, like we
 116 did in `previous chapters <LangImpl5.html#iflexer>`_. One nice thing
 117 about our current AST, is that we represent binary operators with full
 118 generalisation by using their ASCII code as the opcode. For our extended
 119 operators, we'll use this same representation, so we don't need any new
 120 AST or parser support.
 121
 122 On the other hand, we have to be able to represent the definitions of
 123 these new operators, in the "def binary\| 5" part of the function
 124 definition. In our grammar so far, the "name" for the function
 125 definition is parsed as the "prototype" production and into the
 126 ``PrototypeAST`` AST node. To represent our new user-defined operators
 127 as prototypes, we have to extend the ``PrototypeAST`` AST node like
 128 this:
 129
 130 .. code-block:: c++
 131
 132     /// PrototypeAST - This class represents the "prototype" for a function,
 133     /// which captures its argument names as well as if it is an operator.
 134     class PrototypeAST {
 135       std::string Name;
 136       std::vector<std::string> Args;
 137       bool IsOperator;
 138       unsigned Precedence;  // Precedence if a binary op.
 139
 140     public:
 141       PrototypeAST(const std::string &name, std::vector<std::string> Args,
 142                    bool IsOperator = false, unsigned Prec = 0)
 143       : Name(name), Args(std::move(Args)), IsOperator(IsOperator),
 144         Precedence(Prec) {}
 145
 146       bool isUnaryOp() const { return IsOperator && Args.size() == 1; }
 147       bool isBinaryOp() const { return IsOperator && Args.size() == 2; }
 148
 149       char getOperatorName() const {
 150         assert(isUnaryOp() || isBinaryOp());
 151         return Name[Name.size()-1];
 152       }
 153
 154       unsigned getBinaryPrecedence() const { return Precedence; }
 155
 156       Function *codegen();
 157     };
 158
 159 Basically, in addition to knowing a name for the prototype, we now keep
 160 track of whether it was an operator, and if it was, what precedence
 161 level the operator is at. The precedence is only used for binary
 162 operators (as you'll see below, it just doesn't apply for unary
 163 operators). Now that we have a way to represent the prototype for a
 164 user-defined operator, we need to parse it:
 165
 166 .. code-block:: c++
 167
 168     /// prototype
 169     ///   ::= id '(' id* ')'
 170     ///   ::= binary LETTER number? (id, id)
 171     static std::unique_ptr<PrototypeAST> ParsePrototype() {
 172       std::string FnName;
 173
 174       unsigned Kind = 0;  // 0 = identifier, 1 = unary, 2 = binary.
 175       unsigned BinaryPrecedence = 30;
 176
 177       switch (CurTok) {
 178       default:
 179         return ErrorP("Expected function name in prototype");
 180       case tok_identifier:
 181         FnName = IdentifierStr;
 182         Kind = 0;
 183         getNextToken();
 184         break;
 185       case tok_binary:
 186         getNextToken();
 187         if (!isascii(CurTok))
 188           return ErrorP("Expected binary operator");
 189         FnName = "binary";
 190         FnName += (char)CurTok;
 191         Kind = 2;
 192         getNextToken();
 193
 194         // Read the precedence if present.
 195         if (CurTok == tok_number) {
 196           if (NumVal < 1 || NumVal > 100)
 197             return ErrorP("Invalid precedecnce: must be 1..100");
 198           BinaryPrecedence = (unsigned)NumVal;
 199           getNextToken();
 200         }
 201         break;
 202       }
 203
 204       if (CurTok != '(')
 205         return ErrorP("Expected '(' in prototype");
 206
 207       std::vector<std::string> ArgNames;
 208       while (getNextToken() == tok_identifier)
 209         ArgNames.push_back(IdentifierStr);
 210       if (CurTok != ')')
 211         return ErrorP("Expected ')' in prototype");
 212
 213       // success.
 214       getNextToken();  // eat ')'.
 215
 216       // Verify right number of names for operator.
 217       if (Kind && ArgNames.size() != Kind)
 218         return ErrorP("Invalid number of operands for operator");
 219
 220       return llvm::make_unique<PrototypeAST>(FnName, std::move(ArgNames), Kind != 0,
 221                                              BinaryPrecedence);
 222     }
 223
 224 This is all fairly straightforward parsing code, and we have already
 225 seen a lot of similar code in the past. One interesting part about the
 226 code above is the couple lines that set up ``FnName`` for binary
 227 operators. This builds names like "binary@" for a newly defined "@"
 228 operator. This then takes advantage of the fact that symbol names in the
 229 LLVM symbol table are allowed to have any character in them, including
 230 embedded nul characters.
 231
 232 The next interesting thing to add, is codegen support for these binary
 233 operators. Given our current structure, this is a simple addition of a
 234 default case for our existing binary operator node:
 235
 236 .. code-block:: c++
 237
 238     Value *BinaryExprAST::codegen() {
 239       Value *L = LHS->codegen();
 240       Value *R = RHS->codegen();
 241       if (!L || !R)
 242         return nullptr;
 243
 244       switch (Op) {
 245       case '+':
 246         return Builder.CreateFAdd(L, R, "addtmp");
 247       case '-':
 248         return Builder.CreateFSub(L, R, "subtmp");
 249       case '*':
 250         return Builder.CreateFMul(L, R, "multmp");
 251       case '<':
 252         L = Builder.CreateFCmpULT(L, R, "cmptmp");
 253         // Convert bool 0/1 to double 0.0 or 1.0
 254         return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
 255                                     "booltmp");
 256       default:
 257         break;
 258       }
 259
 260       // If it wasn't a builtin binary operator, it must be a user defined one. Emit
 261       // a call to it.
 262       Function *F = TheModule->getFunction(std::string("binary") + Op);
 263       assert(F && "binary operator not found!");
 264
 265       Value *Ops[2] = { L, R };
 266       return Builder.CreateCall(F, Ops, "binop");
 267     }
 268
 269 As you can see above, the new code is actually really simple. It just
 270 does a lookup for the appropriate operator in the symbol table and
 271 generates a function call to it. Since user-defined operators are just
 272 built as normal functions (because the "prototype" boils down to a
 273 function with the right name) everything falls into place.
 274
 275 The final piece of code we are missing, is a bit of top-level magic:
 276
 277 .. code-block:: c++
 278
 279     Function *FunctionAST::codegen() {
 280       NamedValues.clear();
 281
 282       Function *TheFunction = Proto->codegen();
 283       if (!TheFunction)
 284         return nullptr;
 285
 286       // If this is an operator, install it.
 287       if (Proto->isBinaryOp())
 288         BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
 289
 290       // Create a new basic block to start insertion into.
 291       BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
 292       Builder.SetInsertPoint(BB);
 293
 294       if (Value *RetVal = Body->codegen()) {
 295         ...
 296
 297 Basically, before codegening a function, if it is a user-defined
 298 operator, we register it in the precedence table. This allows the binary
 299 operator parsing logic we already have in place to handle it. Since we
 300 are working on a fully-general operator precedence parser, this is all
 301 we need to do to "extend the grammar".
 302
 303 Now we have useful user-defined binary operators. This builds a lot on
 304 the previous framework we built for other operators. Adding unary
 305 operators is a bit more challenging, because we don't have any framework
 306 for it yet - lets see what it takes.
 307
 308 User-defined Unary Operators
 309 ============================
 310
 311 Since we don't currently support unary operators in the Kaleidoscope
 312 language, we'll need to add everything to support them. Above, we added
 313 simple support for the 'unary' keyword to the lexer. In addition to
 314 that, we need an AST node:
 315
 316 .. code-block:: c++
 317
 318     /// UnaryExprAST - Expression class for a unary operator.
 319     class UnaryExprAST : public ExprAST {
 320       char Opcode;
 321       std::unique_ptr<ExprAST> Operand;
 322
 323     public:
 324       UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand)
 325         : Opcode(Opcode), Operand(std::move(Operand)) {}
 326       virtual Value *codegen();
 327     };
 328
 329 This AST node is very simple and obvious by now. It directly mirrors the
 330 binary operator AST node, except that it only has one child. With this,
 331 we need to add the parsing logic. Parsing a unary operator is pretty
 332 simple: we'll add a new function to do it:
 333
 334 .. code-block:: c++
 335
 336     /// unary
 337     ///   ::= primary
 338     ///   ::= '!' unary
 339     static std::unique_ptr<ExprAST> ParseUnary() {
 340       // If the current token is not an operator, it must be a primary expr.
 341       if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
 342         return ParsePrimary();
 343
 344       // If this is a unary operator, read it.
 345       int Opc = CurTok;
 346       getNextToken();
 347       if (auto Operand = ParseUnary())
 348         return llvm::unique_ptr<UnaryExprAST>(Opc, std::move(Operand));
 349       return nullptr;
 350     }
 351
 352 The grammar we add is pretty straightforward here. If we see a unary
 353 operator when parsing a primary operator, we eat the operator as a
 354 prefix and parse the remaining piece as another unary operator. This
 355 allows us to handle multiple unary operators (e.g. "!!x"). Note that
 356 unary operators can't have ambiguous parses like binary operators can,
 357 so there is no need for precedence information.
 358
 359 The problem with this function, is that we need to call ParseUnary from
 360 somewhere. To do this, we change previous callers of ParsePrimary to
 361 call ParseUnary instead:
 362
 363 .. code-block:: c++
 364
 365     /// binoprhs
 366     ///   ::= ('+' unary)*
 367     static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
 368                                                   std::unique_ptr<ExprAST> LHS) {
 369       ...
 370         // Parse the unary expression after the binary operator.
 371         auto RHS = ParseUnary();
 372         if (!RHS)
 373           return nullptr;
 374       ...
 375     }
 376     /// expression
 377     ///   ::= unary binoprhs
 378     ///
 379     static std::unique_ptr<ExprAST> ParseExpression() {
 380       auto LHS = ParseUnary();
 381       if (!LHS)
 382         return nullptr;
 383
 384       return ParseBinOpRHS(0, std::move(LHS));
 385     }
 386
 387 With these two simple changes, we are now able to parse unary operators
 388 and build the AST for them. Next up, we need to add parser support for
 389 prototypes, to parse the unary operator prototype. We extend the binary
 390 operator code above with:
 391
 392 .. code-block:: c++
 393
 394     /// prototype
 395     ///   ::= id '(' id* ')'
 396     ///   ::= binary LETTER number? (id, id)
 397     ///   ::= unary LETTER (id)
 398     static std::unique_ptr<PrototypeAST> ParsePrototype() {
 399       std::string FnName;
 400
 401       unsigned Kind = 0;  // 0 = identifier, 1 = unary, 2 = binary.
 402       unsigned BinaryPrecedence = 30;
 403
 404       switch (CurTok) {
 405       default:
 406         return ErrorP("Expected function name in prototype");
 407       case tok_identifier:
 408         FnName = IdentifierStr;
 409         Kind = 0;
 410         getNextToken();
 411         break;
 412       case tok_unary:
 413         getNextToken();
 414         if (!isascii(CurTok))
 415           return ErrorP("Expected unary operator");
 416         FnName = "unary";
 417         FnName += (char)CurTok;
 418         Kind = 1;
 419         getNextToken();
 420         break;
 421       case tok_binary:
 422         ...
 423
 424 As with binary operators, we name unary operators with a name that
 425 includes the operator character. This assists us at code generation
 426 time. Speaking of, the final piece we need to add is codegen support for
 427 unary operators. It looks like this:
 428
 429 .. code-block:: c++
 430
 431     Value *UnaryExprAST::codegen() {
 432       Value *OperandV = Operand->codegen();
 433       if (!OperandV)
 434         return nullptr;
 435
 436       Function *F = TheModule->getFunction(std::string("unary")+Opcode);
 437       if (!F)
 438         return ErrorV("Unknown unary operator");
 439
 440       return Builder.CreateCall(F, OperandV, "unop");
 441     }
 442
 443 This code is similar to, but simpler than, the code for binary
 444 operators. It is simpler primarily because it doesn't need to handle any
 445 predefined operators.
 446
 447 Kicking the Tires
 448 =================
 449
 450 It is somewhat hard to believe, but with a few simple extensions we've
 451 covered in the last chapters, we have grown a real-ish language. With
 452 this, we can do a lot of interesting things, including I/O, math, and a
 453 bunch of other things. For example, we can now add a nice sequencing
 454 operator (printd is defined to print out the specified value and a
 455 newline):
 456
 457 ::
 458
 459     ready> extern printd(x);
 460     Read extern:
 461     declare double @printd(double)
 462
 463     ready> def binary : 1 (x y) 0;  # Low-precedence operator that ignores operands.
 464     ..
 465     ready> printd(123) : printd(456) : printd(789);
 466     123.000000
 467     456.000000
 468     789.000000
 469     Evaluated to 0.000000
 470
 471 We can also define a bunch of other "primitive" operations, such as:
 472
 473 ::
 474
 475     # Logical unary not.
 476     def unary!(v)
 477       if v then
 478         0
 479       else
 480         1;
 481
 482     # Unary negate.
 483     def unary-(v)
 484       0-v;
 485
 486     # Define > with the same precedence as <.
 487     def binary> 10 (LHS RHS)
 488       RHS < LHS;
 489
 490     # Binary logical or, which does not short circuit.
 491     def binary| 5 (LHS RHS)
 492       if LHS then
 493         1
 494       else if RHS then
 495         1
 496       else
 497         0;
 498
 499     # Binary logical and, which does not short circuit.
 500     def binary& 6 (LHS RHS)
 501       if !LHS then
 502         0
 503       else
 504         !!RHS;
 505
 506     # Define = with slightly lower precedence than relationals.
 507     def binary = 9 (LHS RHS)
 508       !(LHS < RHS | LHS > RHS);
 509
 510     # Define ':' for sequencing: as a low-precedence operator that ignores operands
 511     # and just returns the RHS.
 512     def binary : 1 (x y) y;
 513
 514 Given the previous if/then/else support, we can also define interesting
 515 functions for I/O. For example, the following prints out a character
 516 whose "density" reflects the value passed in: the lower the value, the
 517 denser the character:
 518
 519 ::
 520
 521     ready>
 522
 523     extern putchard(char)
 524     def printdensity(d)
 525       if d > 8 then
 526         putchard(32)  # ' '
 527       else if d > 4 then
 528         putchard(46)  # '.'
 529       else if d > 2 then
 530         putchard(43)  # '+'
 531       else
 532         putchard(42); # '*'
 533     ...
 534     ready> printdensity(1): printdensity(2): printdensity(3):
 535            printdensity(4): printdensity(5): printdensity(9):
 536            putchard(10);
 537     **++.
 538     Evaluated to 0.000000
 539
 540 Based on these simple primitive operations, we can start to define more
 541 interesting things. For example, here's a little function that solves
 542 for the number of iterations it takes a function in the complex plane to
 543 converge:
 544
 545 ::
 546
 547     # Determine whether the specific location diverges.
 548     # Solve for z = z^2 + c in the complex plane.
 549     def mandleconverger(real imag iters creal cimag)
 550       if iters > 255 | (real*real + imag*imag > 4) then
 551         iters
 552       else
 553         mandleconverger(real*real - imag*imag + creal,
 554                         2*real*imag + cimag,
 555                         iters+1, creal, cimag);
 556
 557     # Return the number of iterations required for the iteration to escape
 558     def mandleconverge(real imag)
 559       mandleconverger(real, imag, 0, real, imag);
 560
 561 This "``z = z2 + c``" function is a beautiful little creature that is
 562 the basis for computation of the `Mandelbrot
 563 Set <http://en.wikipedia.org/wiki/Mandelbrot_set>`_. Our
 564 ``mandelconverge`` function returns the number of iterations that it
 565 takes for a complex orbit to escape, saturating to 255. This is not a
 566 very useful function by itself, but if you plot its value over a
 567 two-dimensional plane, you can see the Mandelbrot set. Given that we are
 568 limited to using putchard here, our amazing graphical output is limited,
 569 but we can whip together something using the density plotter above:
 570
 571 ::
 572
 573     # Compute and plot the mandlebrot set with the specified 2 dimensional range
 574     # info.
 575     def mandelhelp(xmin xmax xstep   ymin ymax ystep)
 576       for y = ymin, y < ymax, ystep in (
 577         (for x = xmin, x < xmax, xstep in
 578            printdensity(mandleconverge(x,y)))
 579         : putchard(10)
 580       )
 581
 582     # mandel - This is a convenient helper function for plotting the mandelbrot set
 583     # from the specified position with the specified Magnification.
 584     def mandel(realstart imagstart realmag imagmag)
 585       mandelhelp(realstart, realstart+realmag*78, realmag,
 586                  imagstart, imagstart+imagmag*40, imagmag);
 587
 588 Given this, we can try plotting out the mandlebrot set! Lets try it out:
 589
 590 ::
 591
 592     ready> mandel(-2.3, -1.3, 0.05, 0.07);
 593     *******************************+++++++++++*************************************
 594     *************************+++++++++++++++++++++++*******************************
 595     **********************+++++++++++++++++++++++++++++****************************
 596     *******************+++++++++++++++++++++.. ...++++++++*************************
 597     *****************++++++++++++++++++++++.... ...+++++++++***********************
 598     ***************+++++++++++++++++++++++.....   ...+++++++++*********************
 599     **************+++++++++++++++++++++++....     ....+++++++++********************
 600     *************++++++++++++++++++++++......      .....++++++++*******************
 601     ************+++++++++++++++++++++.......       .......+++++++******************
 602     ***********+++++++++++++++++++....                ... .+++++++*****************
 603     **********+++++++++++++++++.......                     .+++++++****************
 604     *********++++++++++++++...........                    ...+++++++***************
 605     ********++++++++++++............                      ...++++++++**************
 606     ********++++++++++... ..........                        .++++++++**************
 607     *******+++++++++.....                                   .+++++++++*************
 608     *******++++++++......                                  ..+++++++++*************
 609     *******++++++.......                                   ..+++++++++*************
 610     *******+++++......                                     ..+++++++++*************
 611     *******.... ....                                      ...+++++++++*************
 612     *******.... .                                         ...+++++++++*************
 613     *******+++++......                                    ...+++++++++*************
 614     *******++++++.......                                   ..+++++++++*************
 615     *******++++++++......                                   .+++++++++*************
 616     *******+++++++++.....                                  ..+++++++++*************
 617     ********++++++++++... ..........                        .++++++++**************
 618     ********++++++++++++............                      ...++++++++**************
 619     *********++++++++++++++..........                     ...+++++++***************
 620     **********++++++++++++++++........                     .+++++++****************
 621     **********++++++++++++++++++++....                ... ..+++++++****************
 622     ***********++++++++++++++++++++++.......       .......++++++++*****************
 623     ************+++++++++++++++++++++++......      ......++++++++******************
 624     **************+++++++++++++++++++++++....      ....++++++++********************
 625     ***************+++++++++++++++++++++++.....   ...+++++++++*********************
 626     *****************++++++++++++++++++++++....  ...++++++++***********************
 627     *******************+++++++++++++++++++++......++++++++*************************
 628     *********************++++++++++++++++++++++.++++++++***************************
 629     *************************+++++++++++++++++++++++*******************************
 630     ******************************+++++++++++++************************************
 631     *******************************************************************************
 632     *******************************************************************************
 633     *******************************************************************************
 634     Evaluated to 0.000000
 635     ready> mandel(-2, -1, 0.02, 0.04);
 636     **************************+++++++++++++++++++++++++++++++++++++++++++++++++++++
 637     ***********************++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 638     *********************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
 639     *******************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
 640     *****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.....
 641     ***************++++++++++++++++++++++++++++++++++++++++++++++++++++++++........
 642     **************++++++++++++++++++++++++++++++++++++++++++++++++++++++...........
 643     ************+++++++++++++++++++++++++++++++++++++++++++++++++++++..............
 644     ***********++++++++++++++++++++++++++++++++++++++++++++++++++........        .
 645     **********++++++++++++++++++++++++++++++++++++++++++++++.............
 646     ********+++++++++++++++++++++++++++++++++++++++++++..................
 647     *******+++++++++++++++++++++++++++++++++++++++.......................
 648     ******+++++++++++++++++++++++++++++++++++...........................
 649     *****++++++++++++++++++++++++++++++++............................
 650     *****++++++++++++++++++++++++++++...............................
 651     ****++++++++++++++++++++++++++......   .........................
 652     ***++++++++++++++++++++++++.........     ......    ...........
 653     ***++++++++++++++++++++++............
 654     **+++++++++++++++++++++..............
 655     **+++++++++++++++++++................
 656     *++++++++++++++++++.................
 657     *++++++++++++++++............ ...
 658     *++++++++++++++..............
 659     *+++....++++................
 660     *..........  ...........
 661     *
 662     *..........  ...........
 663     *+++....++++................
 664     *++++++++++++++..............
 665     *++++++++++++++++............ ...
 666     *++++++++++++++++++.................
 667     **+++++++++++++++++++................
 668     **+++++++++++++++++++++..............
 669     ***++++++++++++++++++++++............
 670     ***++++++++++++++++++++++++.........     ......    ...........
 671     ****++++++++++++++++++++++++++......   .........................
 672     *****++++++++++++++++++++++++++++...............................
 673     *****++++++++++++++++++++++++++++++++............................
 674     ******+++++++++++++++++++++++++++++++++++...........................
 675     *******+++++++++++++++++++++++++++++++++++++++.......................
 676     ********+++++++++++++++++++++++++++++++++++++++++++..................
 677     Evaluated to 0.000000
 678     ready> mandel(-0.9, -1.4, 0.02, 0.03);
 679     *******************************************************************************
 680     *******************************************************************************
 681     *******************************************************************************
 682     **********+++++++++++++++++++++************************************************
 683     *+++++++++++++++++++++++++++++++++++++++***************************************
 684     +++++++++++++++++++++++++++++++++++++++++++++**********************************
 685     ++++++++++++++++++++++++++++++++++++++++++++++++++*****************************
 686     ++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************
 687     +++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************
 688     +++++++++++++++++++++++++++++++++.........++++++++++++++++++*******************
 689     +++++++++++++++++++++++++++++++....   ......+++++++++++++++++++****************
 690     +++++++++++++++++++++++++++++.......  ........+++++++++++++++++++**************
 691     ++++++++++++++++++++++++++++........   ........++++++++++++++++++++************
 692     +++++++++++++++++++++++++++.........     ..  ...+++++++++++++++++++++**********
 693     ++++++++++++++++++++++++++...........        ....++++++++++++++++++++++********
 694     ++++++++++++++++++++++++.............       .......++++++++++++++++++++++******
 695     +++++++++++++++++++++++.............        ........+++++++++++++++++++++++****
 696     ++++++++++++++++++++++...........           ..........++++++++++++++++++++++***
 697     ++++++++++++++++++++...........                .........++++++++++++++++++++++*
 698     ++++++++++++++++++............                  ...........++++++++++++++++++++
 699     ++++++++++++++++...............                 .............++++++++++++++++++
 700     ++++++++++++++.................                 ...............++++++++++++++++
 701     ++++++++++++..................                  .................++++++++++++++
 702     +++++++++..................                      .................+++++++++++++
 703     ++++++........        .                               .........  ..++++++++++++
 704     ++............                                         ......    ....++++++++++
 705     ..............                                                    ...++++++++++
 706     ..............                                                    ....+++++++++
 707     ..............                                                    .....++++++++
 708     .............                                                    ......++++++++
 709     ...........                                                     .......++++++++
 710     .........                                                       ........+++++++
 711     .........                                                       ........+++++++
 712     .........                                                           ....+++++++
 713     ........                                                             ...+++++++
 714     .......                                                              ...+++++++
 715                                                                         ....+++++++
 716                                                                        .....+++++++
 717                                                                         ....+++++++
 718                                                                         ....+++++++
 719                                                                         ....+++++++
 720     Evaluated to 0.000000
 721     ready> ^D
 722
 723 At this point, you may be starting to realize that Kaleidoscope is a
 724 real and powerful language. It may not be self-similar :), but it can be
 725 used to plot things that are!
 726
 727 With this, we conclude the "adding user-defined operators" chapter of
 728 the tutorial. We have successfully augmented our language, adding the
 729 ability to extend the language in the library, and we have shown how
 730 this can be used to build a simple but interesting end-user application
 731 in Kaleidoscope. At this point, Kaleidoscope can build a variety of
 732 applications that are functional and can call functions with
 733 side-effects, but it can't actually define and mutate a variable itself.
 734
 735 Strikingly, variable mutation is an important feature of some languages,
 736 and it is not at all obvious how to `add support for mutable
 737 variables <LangImpl7.html>`_ without having to add an "SSA construction"
 738 phase to your front-end. In the next chapter, we will describe how you
 739 can add variable mutation without building SSA in your front-end.
 740
 741 Full Code Listing
 742 =================
 743
 744 Here is the complete code listing for our running example, enhanced with
 745 the if/then/else and for expressions.. To build this example, use:
 746
 747 .. code-block:: bash
 748
 749     # Compile
 750     clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core mcjit native` -O3 -o toy
 751     # Run
 752     ./toy
 753
 754 On some platforms, you will need to specify -rdynamic or
 755 -Wl,--export-dynamic when linking. This ensures that symbols defined in
 756 the main executable are exported to the dynamic linker and so are
 757 available for symbol resolution at run time. This is not needed if you
 758 compile your support code into a shared library, although doing that
 759 will cause problems on Windows.
 760
 761 Here is the code:
 762
 763 .. literalinclude:: ../../examples/Kaleidoscope/Chapter6/toy.cpp
 764    :language: c++
 765
 766 `Next: Extending the language: mutable variables / SSA
 767 construction <LangImpl7.html>`_
 768