path: root/docs/tutorial/OCamlLangImpl5.rst

==================================================
Kaleidoscope: Extending the Language: Control Flow
==================================================

.. contents::
   :local:

Written by `Chris Lattner <mailto:sabre@nondot.org>`_ and `Erick
Tryzelaar <mailto:idadesub@users.sourceforge.net>`_

Chapter 5 Introduction
======================

Welcome to Chapter 5 of the "`Implementing a language with
LLVM <index.html>`_" tutorial. Parts 1-4 described the implementation of
the simple Kaleidoscope language and included support for generating
LLVM IR, followed by optimizations and a JIT compiler. Unfortunately, as
presented, Kaleidoscope is mostly useless: it has no control flow other
than call and return. This means that you can't have conditional
branches in the code, significantly limiting its power. In this episode
of "build that compiler", we'll extend Kaleidoscope to have an
if/then/else expression plus a simple 'for' loop.

If/Then/Else
============

Extending Kaleidoscope to support if/then/else is quite straightforward.
It basically requires adding lexer support for this "new" concept to the
lexer, parser, AST, and LLVM code emitter. This example is nice, because
it shows how easy it is to "grow" a language over time, incrementally
extending it as new ideas are discovered.

Before we get going on "how" we add this extension, lets talk about
"what" we want. The basic idea is that we want to be able to write this
sort of thing:

::

    def fib(x)
      if x < 3 then
        1
      else
        fib(x-1)+fib(x-2);

In Kaleidoscope, every construct is an expression: there are no
statements. As such, the if/then/else expression needs to return a value
like any other. Since we're using a mostly functional form, we'll have
it evaluate its conditional, then return the 'then' or 'else' value
based on how the condition was resolved. This is very similar to the C
"?:" expression.

The semantics of the if/then/else expression is that it evaluates the
condition to a boolean equality value: 0.0 is considered to be false and
everything else is considered to be true. If the condition is true, the
first subexpression is evaluated and returned, if the condition is
false, the second subexpression is evaluated and returned. Since
Kaleidoscope allows side-effects, this behavior is important to nail
down.

Now that we know what we "want", lets break this down into its
constituent pieces.

Lexer Extensions for If/Then/Else
---------------------------------

The lexer extensions are straightforward. First we add new variants for
the relevant tokens:

.. code-block:: ocaml

      (* control *)
      | If | Then | Else | For | In

Once we have that, we recognize the new keywords in the lexer. This is
pretty simple stuff:

.. code-block:: ocaml

          ...
          match Buffer.contents buffer with
          | "def" -> [< 'Token.Def; stream >]
          | "extern" -> [< 'Token.Extern; stream >]
          | "if" -> [< 'Token.If; stream >]
          | "then" -> [< 'Token.Then; stream >]
          | "else" -> [< 'Token.Else; stream >]
          | "for" -> [< 'Token.For; stream >]
          | "in" -> [< 'Token.In; stream >]
          | id -> [< 'Token.Ident id; stream >]

AST Extensions for If/Then/Else
-------------------------------

To represent the new expression we add a new AST variant for it:

.. code-block:: ocaml

    type expr =
      ...
      (* variant for if/then/else. *)
      | If of expr * expr * expr

The AST variant just has pointers to the various subexpressions.

Parser Extensions for If/Then/Else
----------------------------------

Now that we have the relevant tokens coming from the lexer and we have
the AST node to build, our parsing logic is relatively straightforward.
First we define a new parsing function:

.. code-block:: ocaml

    let rec parse_primary = parser
      ...
      (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
      | [< 'Token.If; c=parse_expr;
           'Token.Then ?? "expected 'then'"; t=parse_expr;
           'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
          Ast.If (c, t, e)

Next we