• Stars
    star
    260
  • Rank 153,544 (Top 4 %)
  • Language Standard ML
  • License
    GNU General Publi...
  • Created about 6 years ago
  • Updated about 6 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Low-level Lisp with compile-time memory management

Interim

Build Status

Interim is a statically-typed, low-level dialect of Lisp featuring compile-time, GC-free memory management.

Interim is a technology demonstrator for compile-time memory management using regions. As of 2018, the only major language with compile-time memory management is Rust, which is notoriously tough to learn. Interim was built to prove that sound, GC-free, compile-time memory management can be both simple to implement and easy to learn and use.

Overview of Regions

Memory safety is achieved by preventing three classes of errors:

  • NULL pointers
  • Double free()
  • Use after free() (dangling pointers)

Preventing NULL pointers is easy: we use an option type (called Maybe in Haskell). In the case of Interim, we have a special pointer type called nullable which represents a pointer which is potentially NULL. The case construct can be used to extract a never-NULL pointer in a safe way.

Preventing double free() and use after free() errors is harder, and this is where regions come in.

Consider this code:

(letregion rho
  (let ((p (allocate rho 10)))
    (letregion rho'
      (let ((p' (allocate rho' 12)))
        nil))))

What we're doing here is:

  1. Defining a region rho. Regions are both lexical objects and run-time values.

  2. Defining a variable p, whose initial value is the result of allocating the number 10 in the region rho.

    An allocate call takes a value of type T and a region indentifier, allocates enough memory in the region to hold that value, and returns a pointer to it. The result pointer has the type (nullable T R), where T is the type of the value we're allocating and R is the region identifier.

  3. Defining a new region rho'.

  4. Defining a new variable p', whose initial value is (allocate rho' 12), that is, the result of allocating the value 12 in the region rho'.

  5. Finally, return nil.

Now notice what happens if we try to store p' in p:

(letregion rho
  (let ((p (allocate rho 10)))
    (letregion rho'
      (let ((p' (allocate rho' 12)))
        (<- p p')))))

The compiler will fail with

Cannot assign to variable 'p': the type of the variable is (nullable i32 rho),
while the type of the expression is (nullable i32 rho')

This is the key to preventing dangling pointer errors: pointers are tagged with the region they belong to. A pointer cannot escape its lifetime, to a higher-up region or to a global variable, because the types won't match.

Double free() errors are prevented through a straightforward feature of regions: there is no way to do a manual free(), and everything in a region is freed automatically when exiting the region's body.

Examples

For more examples, look in the examples/ directory.

Hello World

(defun main () i32
  (println "Hello, world!")
  0)

Fibonacci

(defun fib ((n i32)) i32
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

(defun main () i32
  (print "fib(30) = ")
  (println (fib 30))
  0)

Output:

fib(30) = 832040

Regions

(defun main () i32
  (letregion rho
    (let ((p (allocate rho 10)))
      (case p
        ((not-null p')
         (print "Allocated successfully! Value: ")
         (println (load p'))
         0)
        (null
         (println "Out of memory!")
         -1)))))

Output:

Allocated successfully! Value: 10

Building

You need MLton, git and make to build Interim. On Ubuntu:

$ sudo apt-get install mlton git make

Then:

$ make interim

After building, try

$ make examples

Dependencies

The only dependency is Parsimony, a parser combinator library.

Design

Being a technology demonstrator, Interim lacks many features of real languages: modules, macros, higher-order functions, and higher-order types are not implemented since the focus is on region-based memory management.

As the name implies, Interim is a stepping stone or proof of concept for a larger, more sophisticated language.

Bibliography

License

Copyright 2018 Fernando Borretti.

Licensed under the GPLv3 license. See the COPYING file for details.

More Repositories

1

cmacro

Lisp macros for C
Common Lisp
876
star
2

corvus

Low-level Lisp for LLVM
Common Lisp
503
star
3

magma

Extending C with cmacro
C
326
star
4

crane

An ORM for Common Lisp.
Common Lisp
197
star
5

lucerne

A web framework for Common Lisp, built on Clack
Common Lisp
142
star
6

cl-yaml

YAML parser for Common Lisp
Common Lisp
58
star
7

corona

Create and manage virtual machines from Common Lisp
Common Lisp
50
star
8

rock

Asset manager and compiler for Common Lisp web apps
Common Lisp
46
star
9

hermetic

Security for Clack-based Common Lisp web applications.
Common Lisp
43
star
10

trivial-ssh

An SSH client library for Common Lisp (Built on libssh2)
Common Lisp
40
star
11

docparser

Extract documentation from Common Lisp systems
Common Lisp
40
star
12

eco

Fast, flexible, designer-friendly templates for Common Lisp
Common Lisp
38
star
13

trivial-download

Download files from Common Lisp through Drakma.
Common Lisp
37
star
14

asdf-linguist

ASDF extensions.
Common Lisp
34
star
15

cl-pass

Password hashing and verification library
Common Lisp
30
star
16

swank-protocol

A low-level client for Swank
Common Lisp
29
star
17

spaced-repetition-tools

Scripts for generating flashcards.
Python
29
star
18

clack-errors

Error page middleware for Clack.
JavaScript
28
star
19

lime

A client for Swank
Common Lisp
25
star
20

dotfiles

Not guaranteed to work outside of My Machineβ„’
Emacs Lisp
20
star
21

find-port

Programmatically find open ports.
Common Lisp
19
star
22

trivial-open-browser

Open a browser window. From Common Lisp.
Common Lisp
18
star
23

parsing-menhir

Code for a tutorial on parsing with Menhir
OCaml
15
star
24

terminal-keypress

Read keyboard events in the terminal from Common Lisp
Common Lisp
14
star
25

eudoxia0.github.io

Personal website
HTML
14
star
26

lcm

Manage your system configuration in Common Lisp.
Common Lisp
12
star
27

astro-eog581

Astronomical calculations for The Epiphany of Gliese 581.
Common Lisp
10
star
28

terminal-size

Get the size of the terminal from Common Lisp
Common Lisp
10
star
29

parsimony

Parser combinators for Standard ML
Standard ML
9
star
30

clos-fixtures

CLOS fixtures.
Common Lisp
9
star
31

avatar-api

Get avatars from Gravatar and other services.
Common Lisp
9
star
32

postmaster

Email for humans
Common Lisp
8
star
33

arachne

A web crawling framework in Common Lisp.
Common Lisp
8
star
34

cl-virtualbox

Control VirtualBox from Common Lisp
Common Lisp
8
star
35

airloom

A reverse literate programming tool.
Haskell
7
star
36

cl-libyaml

libyaml bindings for Common Lisp
Common Lisp
6
star
37

concordia

A document preparation system
Standard ML
4
star
38

trivial-extract

Extract compressed files painlessly.
Common Lisp
4
star
39

cartesian

My personal exocortex
Python
3
star
40

l0

Linear Lisp
Standard ML
3
star
41

cl-base58

An implementation of base58 for Common Lisp
Common Lisp
3
star
42

parse-front-matter

A Jekyll-style front matter parser
Common Lisp
3
star
43

ctbnrle

Continuous Time Bayesian Network Reasoning and Learning Engine (CTBN-RLE)
C
3
star
44

which

The which command in Common Lisp
Common Lisp
2
star
45

clippings-parser

Export Kindle clippings to JSON, CSV, or Markdown.
Python
2
star
46

NeuriteTracer

An experiment in computer vision.
C++
2
star
47

lass-flexbox

Flexbox for Lass
Common Lisp
2
star
48

mlunit

A test framework for Standard ML
Standard ML
2
star
49

ocaml-nix-starter

OCaml starter project template using Nix for reproducibility.
Nix
2
star
50

git-file-history

View a file's git history, and individual commit info
Common Lisp
2
star
51

MNT

Molecular machinery built in NanoEngineer, in .mmp format.
1
star
52

sml-sqlite3

SQLite3 bindings for MLton
Standard ML
1
star
53

wax

TeX-like markup language experiment thing
Common Lisp
1
star
54

path-parse

Parse the PATH environment variable portably
Common Lisp
1
star
55

benchmarks

Common Lisp vs. the World
Common Lisp
1
star
56

texgen

Lisp DSL for generating TeX
Common Lisp
1
star
57

diy-clozemaster

Python
1
star