llrl programming language

llrl is an experimental Lisp-like programming language.

How I created a self-hosting compiler with Rust + LLVM (Japanese)

Features

llrl mainly borrows its design from OCaml, Rust, Haskell, and Scheme.

Statically-typed
- Hindley-Milner based type system
- Supports type classes
Lisp-like syntax + macros
- Uses S-expressions to write programs
- Macros are compiled and executed at compile-time (JIT)
Self-hosting AOT compiler implementation
- There are Rust implementation (llrl0) and llrl implementation (llrl1)
Multiple backends
- llvm backend (works with The LLVM Compiler Infrastructure)
- chibi backend (works with xten; xten is a low-level x86_64 library including assembler and JIT linker, made for llrl)

llrl supports several well-known high-level language features:

Modules
Closures
Algebraic data types
Pattern matching
...

History, Goals, and Non-goals

llrl was originally started by learning LLVM Kaleidoscope Tutorial in Rust. This tutorial is great for learning LLVM frontend basics, but as the tutorial conclusion suggests, there are a lot of things to do to make our compiler more practical.

The first goal of llrl was not to create a modern, feature-rich practical programming language. Instead, llrl focuses to make a compiler self-hosted. To achieve this with LLVM-C API, we need to implement more language features like strings, pointers, etc. On the other hand, Implementing self-hosting compiler does not require a rich runtime system including garbage collections, exception handling, etc. llrl also uses Boehm garbage collector and does not support any exception mechanism to simplify the implementation. Error handling is mainly done with the Result type. This goal has been achieved and can be tested by make self-hosting1lll in llrl1/.

After achieving self-hosting, I set my next goal to remove the LLVM dependency from llrl implementation. With this goal, I sought to gain a better understanding of how the compiler backend does its job. Since llrl has Lisp-like macros as a language feature, I made my own assembler xten (which can be used in Rust code) and used it to implement a code generator targeting x86_64. The design of the code generator implementation is based on the pattern used in chibicc and An Incremental Approach to Compiler Construction.

Roadmap

[x] Language Design
[x] llrl0: llrl compiler by Rust
- [x] S-expression parser
- [x] Syntax analysis
- [x] Loading mechanism for a set of source codes
- [x] Semantic analysis
  - [x] Import/export resolution
  - [x] Design and construction of ASTs
  - [x] Name resolution
  - [x] Kind and type inference and unification algorithm
  - [x] Pattern matching analysis
- [x] Code generation
  - [x] Monomorphization
  - [x] Closure conversion
  - [x] Pattern matching expansion
  - [x] A very simple heap2stack
  - [x] LLVM backend
  - [x] Macro expansion
- [x] Driver
[x] llstd: llrl standard library
- [x] Macro helpers (gensym, quasiquote, s/match)
- [x] S-expression
- [x] Common macros (let*, let1, ...)
- [x] Common type classes (Default, Eq, Ord, Hash, Display, Conv, ...)
- [x] Common data types (Bool, Integers, Floating-point numbers, Ptr, Option, Result, Char, String, Tuples, ...)
- [x] Aggregate data types
  - [x] Array
  - [x] Vector
  - [x] Ordered map (B-tree)
  - [x] Ordered set
  - [x] Hash map
  - [x] Hash set
  - [x] Persistent ordered map (Red-black tree)
  - [ ] ~Persistent ordered set~
  - [x] Persistent hash map (HAMT)
  - [ ] ~Persistent hash set~
  - [ ] ~Persistent sequence (rrb-vector)~
- [x] Arithmetic operations
- [x] Bit operations
- [x] xxHash
- [x] Iterators
- [x] Derive macro
- [x] I/O
  - [x] Path
  - [x] File
  - [x] Directory
- [x] System
  - [x] Command line arguments
  - [x] Process
[x] llrl1: llrl compiler by llrl
- [x] LLVM-C API porting
- [x] S-expression parser
- [x] Syntax analysis
- [x] Loading mechanism for a set of source codes
- [x] Semantic analysis
- [x] Code generation
- [x] Driver
- [x] Self-hosting
- [x] chibi backend
[x] xten0: JIT/AOT compilation tools for llrl0
- [x] Assembler
- [x] ELF executable producer
- [x] JIT linker
[x] xten1: re-implementation of xten0 for llrl
[x] chibi backend (x86_64 targeting backend with xten)
- [x] for llrl0
- [x] for llrl1

Usage

Since llrl0 is a standalone executable, you can simply install it with cargo install.

$ cargo install --path llrl0 --offline
$ llrl0 --help
$ llrl0 -O examples/fibonacci-numbers

# or

$ cargo run -- -O examples/fibonacci-numbers

Each backend is enabled by a feature flag and is enabled by default.

chibi-backend - Enables chibi backend, a x86_64 native backend
llvm-backend - Enables llvm backend, a backend built on top of LLVM

For example, to build llrl0 without LLVM, do the following:

$ cargo install --path llrl0 --offline \
    --no-default-features -F chibi-backend

Requirements

Linux x64
- llrl does not take into account support for other platforms
glibc
- Not tested other C libraries but llrl depends a few implementation-details of glibc (check at rt/rt.c)
clang
(optional) LLVM 11
- Enabled by default in llrl0 with llvm-backend feature
- I use llvmenv for building LLVM
Boehm GC 8
- On Arch Linux, you can install Boehm GC by simply running pacman -S gc

Editor support

VSCode language support is available at yubrot/llrl-vscode.

Language Overview

Syntax

The syntax of llrl is basically a subset of the Scheme syntax. There are several syntax sugar that are unique to this language.

| Syntax sugar | Desugared | Description | | ------------- | --------------------- | ---------------------------------------------------------------------------- | | ~expr | (load expr) | Call of the load function | | \expr | (capture expr) | Capture of the use (See Macros section) | | (...)? | (try? (...)) | Call of the try? macro (Early returns for Option) | | (...)! | (try! (...)) | Call of the try! macro (Early returns for Result) | | expr {...} | (annotate expr ...) | Type signatures (See Functions section) | | a... @ b... | a... (b...) | Used to reduce nesting of S-expressions |

The last syntax sugar allows nested S-expressions like (let1 foo 123 (let1 bar 456 (+ foo bar))) to be written as @let1 foo 123 @let1 bar 456 (+ foo bar).

Packages and Modules

Modules are identified by a string in the form of a path separated by a slash /. The first part of the path points to the name of the package, and the rest of the parts correspond to the file path on the package. If the file path on the package is omitted, it is treated as equivalent to <package-name>/prelude.

There are several predefined package names:

~: The special pakcage name that refers to the current package.
builtin: a set of language built-in definitions used directly by numeric literals, etc.
std: the llrl language standard library. std/prelude is implicitly imported in all modules (this behavior can be disabled with (no-implicit-std) declaration)

(import "std/hash-map" HashMap)

; Import all matching definitions by using `_` as a prefix or postfix
(import "std/hash-map" HashMap hash-map/_)

; Import everything
(import "std/hash-map" _)

; Export works as well
(export HashMap)

Functions

(function pi
  3.1415)

(function (square x)
  (* x x))

(function (squared-length a b)
  (+ (* a a) (* b b)))

pi                   ; => 3.1415
(square 10)          ; => 100
(squared-length 3 4) ; => 25

; With type signatures
(function pi {F64}
  3.1415)

(function (square x) {(-> I32 I32)}
  (* x x))

; Generalization
(function (identity x) {(forall A) (-> A A)}
  x)

; Generalization with constraints
(function (generic-square x) {(forall A) (-> A A) (where (Mul A))}
  (* x x))

Types

Primitive types are defined in builtin.llrl.

unit      ; Synonym for empty tuple (:)
Bool
I8
I16
I32
I64
U8
U16
U32
U64
F32
F64
String
Char

; Tuples
(: I32 I32)
(: String Char I32)

; Functions
(-> I32)
(-> I32 I32 I32)

; Option/Result
(Option I32)
(Result (Option I32) String)

Expressions

llrl does not have a main function, and the expressions written at the top level are executed in order.

; Literals
123
3.14
"Hello, World!\n"
#\a
#t
#f

; Function/macro application
(sqrt 2)
(+ 12 (* 34 56) 78)

; Conditional branching
(if #f
  (println! "then")
  (println! "else))

; Sequencing
(begin
  (println! "a")
  (println! "b")
  (println! "c"))

; Local variable binding
(let ([a 12]
      [b 34])
  (+ a b))

; Local function binding
(let ([(square x) (* x x)])
  (square 3))

; Loop
(let1 i (ref 0)
  (while (< ~i 5

Llrl

Install / Use

README