path: root/docs/tutorial/OCamlLangImpl6.rst

============================================================
Kaleidoscope: Extending the Language: User-defined Operators
============================================================

.. contents::
   :local:

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

Chapter 6 Introduction
======================

Welcome to Chapter 6 of the "`Implementing a language with
LLVM <index.html>`_" tutorial. At this point in our tutorial, we now
have a fully functional language that is fairly minimal, but also
useful. There is still one big problem with it, however. Our language
doesn't have many useful operators (like division, logical negation, or
even any comparisons besides less-than).

This chapter of the tutorial takes a wild digression into adding
user-defined operators to the simple and beautiful Kaleidoscope
language. This digression now gives us a simple and ugly language in
some ways, but also a powerful one at the same time. One of the great
things about creating your own language is that you get to decide what
is good or bad. In this tutorial we'll assume that it is okay to use
this as a way to show some interesting parsing techniques.

At the end of this tutorial, we'll run through an example Kaleidoscope
application that `renders the Mandelbrot set <#example>`_. This gives an
example of what you can build with Kaleidoscope and its feature set.

User-defined Operators: the Idea
================================

The "operator overloading" that we will add to Kaleidoscope is more
general than languages like C++. In C++, you are only allowed to
redefine existing operators: you can't programatically change the
grammar, introduce new operators, change precedence levels, etc. In this
chapter, we will add this capability to Kaleidoscope, which will let the
user round out the set of operators that are supported.

The point of going into user-defined operators in a tutorial like this
is to show the power and flexibility of using a hand-written parser.
Thus far, the parser we have been implementing uses recursive descent
for most parts of the grammar and operator precedence parsing for the
expressions. See `Chapter 2 <OCamlLangImpl2.html>`_ for details. Without
using operator precedence parsing, it would be very difficult to allow
the programmer to introduce new operators into the grammar: the grammar
is dynamically extensible as the JIT runs.

The two specific features we'll add are programmable unary operators
(right now, Kaleidoscope has no unary operators at all) as well as
binary operators. An example of this is:

::

    # Logical unary not.
    def unary!(v)
      if v then
        0
      else
        1;

    # Define > with the same precedence as <.
    def binary> 10 (LHS RHS)
      RHS < LHS;

    # Binary "logical or", (note that it does not "short circuit")
    def binary| 5 (LHS RHS)
      if LHS then
        1
      else if RHS then
        1
      else
        0;

    # Define = with slightly lower precedence than relationals.
    def binary= 9 (LHS RHS)
      !(LHS < RHS | LHS > RHS);

Many languages aspire to being able to implement their standard runtime
library in the language itself. In Kaleidoscope, we can implement
significant parts of the language in the library!

We will break down implementation of these features into two parts:
implementing support for user-defined binary operators and adding unary
operators.

User-defined Binary Operators
=============================

Adding support for user-defined binary operators is pretty simple with
our current framework. We'll first add support for the unary/binary
keywords:

.. code-block:: ocaml

    type token =
      ...
      (* operators *)
      | Binary