slides.md

title	author	date	css
Compiling a simple functional language<br> with LLVM and Haskell	Andreas Herrmann<br> <a href="https://github.com/aherrmann/simply_llvm"> <i class="fa fa-github" aria-hidden="true"></i> github.com/aherrmann/simply_llvm </a>	November 24, 2016	https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css

What is LLVM

• Compiler toolchain

  • native code for multiple targets (x86, x86_64, ARM, and many more)

  • target independent optimizer

  • just in time (JIT) compiler

• Abstract assembly language

  • infinite virtual registers

  • static single assignment (SSA) form

Who uses LLVM

• Clang (part of LLVM)

• Rust

• Julia

• GHC

• many more

Demo LLVM IR

• 01_addmul.ll

• 02_factorial.ll

Today's language: "Simply"

• Simply-typed lambda calculus

• Base types: Int, Bool; and function types: a -> b

• Literals, Variables

• Branches

• Primitive operations: +, -, *, ==

• Lambda abstraction, and function application

• non-recursive let-bindings

• mutually recursive global bindings

• one main function

Today's language - Example

Calculate the factorial of the given number

globals

    factorial' (acc : Int) (n : Int) : Int =
        if n == 0 then
            acc
        else
            factorial' (acc * n) (n - 1)

    factorial (n : Int) : Int =
        factorial' 1 n

main (n : Int) =
    factorial n

Today's language - Supports

• higher order functions

• closures

• functions as values

globals

    apply (f : Int -> Int) (x : Int) : Int =
        f x

    mkAdder (a : Int) : Int -> Int =
        (+) a

main (n : Int) =
    let
        add3 = mkAdder 3
    in
        apply add3 n

Compiler Pipeline

• Parse to AST (not implemented)

• Type-check

• Convert to intermediate representation

• Convert to LLVM IR

• (Optimize)

• Generate native code

• Execute

Abstract Syntax Tree

• "Simply" AST

• Type Checker

• Examples

Motivate IR

Difference between "Simply" and LLVM:

• In LLVM everything is explicitly typed (annotated AST)

• LLVM distinguishes local and global variables explicitly

• LLVM only allows global function definitions

• LLVM has no closures

• In LLVM all function have to be fully applied

Intermediate Representation

• Intermediate representation AST

• Transform "Simply" to IR

  (Up to closures)

• Examples

Demo llvm-general-pure

• Manual.hs

Show Codegen.hs

• Codegen.hs

Transform to LLVM

• Transform IR to LLVM

  (Up to closures)

• JIT

• Examples

Closures on the Machine

• Closure captures environment and expects arguments

• Global function that takes environment and arguments

• Example in C

Closures in IR

• Intermediate representation AST

• Transform "Simply" to IR

• Examples

Closures in LLVM

• Transform IR to LLVM

• Examples

Where to go from here?

• Parsing, Pretty-Printing, Testing

  • Dave Laing

• Garbage Collection

  • LLVM documentation

• Polymorphism (Damas–Hindley–Milner)

  • Stephen Diehl
  • David Luposchainsky

• Dependent Types

  • Andres Löh, et al.

• Backend for Morte

  • Gabriel Gonzalez

Thanks for your attention

References

• Kaleidoscope in Haskell by Stephen Diehl

• Building Small Native Languages with Haskell by Stephen Diehl (code) (video)

• Closure Conversion by Jeremy Siek

• LLVM Bindings by Benjamin S. Scarlet

• LLVM Language Reference

• Types and Programming Languages by Benjamin C. Pierce

• Practical Foundations for Programming Languages by Robert Harper