iron-kaleidoscope

Status

Nothing works: Rust code completely outdated. Maybe one day I'll fix it.

State corresponds to the Chapter 7 of the original tutorial (i.e. mutable variables implemented).

TODO list.

LLVM tutorial in the Rust language.

This tutorial is a work in progress and at the moment I'm working on getting it fully working with the latest Rust and on improvinvg the way it uses LLVM.

Table of Contents

• Chapter 0. Introduction
  • Basic variant of the Kaleidoscope language
  • The project structure
  • The lexer
• Chapter 1. Parser and AST implementation
  • The grammar
  • The Abstract Syntax Tree (AST)
  • Parser implementation: introduction
  • Top level parse function
  • Helper macros for work with tokens
  • Parsing of statements and top level expressions
  • Parsing of primary expressions
  • Parsing of binary expressions
  • The driver
• Chapter 2. LLVM IR code generation
  • Code generation setup
  • Top level code generation
  • Expression code generation
• Chapter 3. Optimizer and JIT support
  • LLVM Optimization passes
  • MCJIT based JIT-compiler
  • Changes in the driver and 'built-in' functions
• Chapter 4. Extending Kaleidoscope: control flow
  • If/Then/Else
    • Lexer and parser changes for if/then/else
    • IR generation for if/then/else
  • 'For' loop
    • Lexer and parser changes for the 'for' loop
    • IR generation for the 'for' loop
• Chapter 5. Extending Kaleidoscope: user-defined operators
  • User-defined binary operators
  • User-defined unary operators
  • Painting the Mandelbrot set
• Chapter 6. Extending Kaleidoscope: mutable variables
  • Mutable variables in Kaleidoscope
  • Adjusting variables for mutation
  • Assignmnet operator
  • User-defined local variables

Chapter 0. Introduction

This tutorial shows how to implement a simple programming language using LLVM and Rust. Its first goal is to show how to use LLVM to create a simple REPL, so some knowledge of Rust is assumed. To be honest, author himself is a very beginner both in Rust and LLVM, so any feedback is highly appreciated.

The code in the repository corresponds to the state of your program at the end of the last chapter and serves as a starting point for further experiments.

If you want to look at code that corresponds to a given chapter, see chapters directory. Link to relevant code is attached to every chapter (work in progress).

To experiment with the code in this repo you need:

• the latest Rust compiler

• Cargo Rust package manager

• LLVM (I have used ver. 3.6)

To build the code just clone the repo and execute

cargo build

Then you will find an executable named iron-kaleidoscope in the target directory.

Basic variant of the Kaleidoscope language

In this tutorial we will use a simple functional language named Kaleidoscope. In this chapter its basic variant will be presented. New features will be added in the next chapters step by step.

The language has only one type: 64-bit floating point numbers (f64 in the Rust terminology).

The first variant of the language is very limited and even not Turing complete. It includes only function defenitions (or declarations) and function invocations together with some simple arithmetic operators. Examples follow.

Arithmetic expression:

1 + 2 * (3 - 4);

Function definition:

def plus(x, y)
    x + y

Function invocation:

plus(1 2)

Extern function declaration and invocation:

extern sin(x);

sin(1)

Every statement except of definitions and declarations in Kaleidoscope is an expression and has the corresponding value. Quite similar to Rust. Function body is just an expression, its value is returned. No explicit return operator is used.

To show the end of an expression or definition (declaration) we use ';' character. ',' character in function prototypes/calls is equivalent to the space character. Comments are started by '#' and last until the end of the line.

Names of variables start with an alphabetical character and contain any number of alphanumerical characters. Reserved words at the moment include def and extern. Any non-alphanumerical non-whitespace character different from '(', ')', ';' and ',' is treated as an operator.

A number literal is a nonempty sequence of decimal digits, possibly containing a decimal point character.

The project structure

To create a REPL we will need (corresponding source files are shown in parenthesis):

• the lexer (lexer.rs)

• the parser (parser.rs)

• the IR builder (builder.rs)

• the JIT compiler (jitter.rs)

• the driver (driver.rs)

We'll use Cargo as a build system for this project. All sources will live in the src directory. Project will have two crates: library and binary. All real functionality will be implemented in the library, and the binary will just parse command line arguments and invoke the driver.

Cargo.toml file is quite straightforward.

The lexer

To implement the lexer we'll use regular expressions. We have the next types of tokens (and corresponding regexes given in the notation used by the Rust regex library):

• def and extern keywords (def|extern)

• identifier (\p{Alphabetic}\w*)

• number literal (\d+\.?\d*)

• semicolon (;)

• opening and closing parenthesis (\(|\))

• comma (,)

• operator (\S)

The corresponding enumeration looks like this:

#[derive(PartialEq, Clone, Debug)]
pub enum Token {
    Def,
    Extern,
    Delimiter, //';' character
    OpeningParenthesis,
    ClosingParenthesis,
    Comma,
    Ident(String),
    Number(f64),
    Operator(String)
}

Note, that to use enumeration members without scopes as we later do, you need to add some uses at the beginning of your module (it is needed since changing enums to be scoped in Rust):

pub use self::Token::{
    Def,
    Extern,
    Delimiter,
    OpeningParenthesis,
    ClosingParenthesis,
    Comma,
    Ident,
    Number,
    Operator
};

We do not mention those uses explicitly in the following.

Our parser function will accept a string with input characters and produce a vector of tokens. It will look like this:

…

Quite simple function. About regex in Rust you can read here.

Some comments: we create regex with different groups matching to different types of tokens. Then we match it on the input string and iterate over captures, looking what token we have matched. Identifiers are matched in the same regex with keywords, as they have the same microsyntax. They are separated later with the additional match.

To experiment with this lexer you can create a simple main function that reads lines from the input one by one and shows the recognized tokens. Full code for this chapter is available, but is a little bit more complex then needed as it is autogenerated from the full code.

Chapter 1. AST and parser implementation

In this chapter we will build a parser for the Kaleidoscope language. First we need to define its grammar and how to represent the parsing results. Then we can use Recursive Descent Parsing and Operator-Precedence Parsing to produce the Abstract Syntax Tree from the stream of tokens recognized by the lexer.

The grammar

This grammar description uses the dialect of Extended Backus-Naur Form (EBNF) described in the Rust reference. Identifiers that start with the lowercase name non-terminals. Identifiers that start with the uppercase name terminals and correspond to the names in the Token enum defined in the lexer.

program          : [[statement | expression] Delimiter ? ]*;
statement        : [declaration | definition];
declaration      : Extern prototype;
definition       : Def prototype expression;
prototype        : Ident OpeningParenthesis [Ident Comma ?]* ClosingParenthesis;
expression       : [primary_expr (Op primary_expr)*];
primary_expr     : [Ident | Number | call_expr | parenthesis_expr];
call_expr        : Ident OpeningParenthesis [expression Comma ?]* ClosingParenthesis;
parenthesis_expr : OpeningParenthesis expression ClosingParenthesis;

The Abstract Syntax Tree (AST)

Now we'll create data types corresponding to every item in the Kaleidoscope grammar.

program          : [[statement | expression] Delimiter ? ]*;

Program is a sequence of statements and expressions. To make life easier in the future we will close every expression in an anonymous function (we'll use this during JIT compilation). So, there are two types of items in the program after such a closure: declarations and definitions. Declarations are just function prototypes, when definitions are function prototypes combined with a function body.

The data type corresponding to the programm will be:

Vec

where ASTNode is defined as

#[derive(PartialEq, Clone, Debug)]
pub enum ASTNode {
    ExternNode(Prototype),
    FunctionNode(Function)
}

ExternNode corresponds to the declaration item in the grammar and FunctionNode corresponds to the definition item.

We define Prototype and Function according to the grammar:

definition       : Def prototype expression;
prototype        : Ident OpeningParenthesis [Ident Comma ?]* ClosingParenthesis;

#[derive(PartialEq, Clone, Debug)]
pub struct Function {
    pub prototype: Prototype,
    pub body: Expression
}

#[derive(PartialEq, Clone, Debug)]
pub struct Prototype {
    pub name: String,
    pub args: Vec
}

Functions are typed only by the number of arguments, as the onliest type in the Kaleidoscope language is an f64 number.

The only thing left to define is the data type that corresponds to the expression item. This one is the most complicated and difficult to parse, as it includes binary expressions with operator precedence.

`