heap.coffee

heap.coffee is a CoffeeScript dialect that has an optional C-like type system with manual memory management which compiles to use an explicit typed array as its "heap". This lets you write memory-efficient and GC pause-free code less painfully.

A word of warning: this is not a very good type system, or even does very much. It's basically a glorified preprocessor to help compute offsets for struct fields.

Original CoffeeScript

# A linked list type.
type node = struct
  val  :: int
  next :: *node

# Allocate 2 new nodes with new.
n, m :: *node
n = m = new node

# Dot-notation now also dereference struct pointers.
n.val = 0
n.next = m
m.val = 1
m.next = null

# Free heap-allocated nodes with delete.
delete n
delete m

Compiled JavaScript

// Generated by CoffeeScript 1.3.1
(function() {
  var free, m, malloc, n, _ref,
    _HEAP = require('heap/heap'),
    _I32 = _HEAP.I32,
    _U32 = _HEAP.U32;

  _ref = require('heap/malloc'), malloc = _ref.malloc, free = _ref.free;

  // type node = struct { [0] val :: i32, [4] next :: *node }

  // n :: *node
  // m :: *node
  n = m = malloc(8);

  _I32[n] = 0;
  _U32[n + 1] = m;
  _I32[m] = 1;
  _U32[m + 1] = 0;

  free(n);
  free(m);
}).call(this);

Components

To use heap.coffee, there are two components: the compiler and the runtime. The compiler is hooked into CoffeeScript internals and should just work. The runtime are found in `src/heap' and should be built using:

$ bin/cake build:heap

This builds heap.js, which is the module to be required to initialize the heap, and malloc.js, which is an implementation of K&R's naive malloc and free implementation.

Syntax

Type synonyms alias one type name to another. These may only appear at the toplevel.

type size_t = uint

Type declarations tell the compiler what variable is what type. Our type system is simple and C-like, so you must tell it the types of everything, it doesn't really do any inference.

# Type a simple identifier.
i :: int
# Type a destructuring array.
[ i, j ] :: [ int, int ]
# Type a destructuring object.
{ foo, bar } :: { foo: int, bar: int }

Allocate using new:

n :: *node
n = new node

Free using delete:

delete n

Dereferencing in expressions and taking the address of variables are just like in C:

v  = *n
np = &n

Use dot where you would use arrow in C. Dereferencing of the struct pointer is automatic.

n = n.next
n = (*n).next # semantically equivalent to above

Use := to assign to the memory location of a pointer type. Note that the C-like syntax *p = e is valid, but really means *(p = e).

i :: *int
i = new int
i := 42

Pointer arithmetic work as it does in C.

Types

heap.coffee includes any, {i,u}{8,16,32} and double, and the following aliases.

• byte = u8
• short = i16
• int = i32
• uint = u32
• num = double

Declaring a variable to be of type any is like not declaring its type.

Struct types are declared using type synonyms and share syntax with creating objects, except each property-value pair is a type declaration:

type point = struct
  x :: int
  y :: int

Pointer types are prefixed by *:

type intp = *int

Function types are composed using ->. Since functions are still JavaScript-native, pointers cannot be taken of functions.

type binop = (int, int) -> int

Normally, the user has to declare the types of parameters manually. There is a special sugar in place for when a variable is given a function type declaration and its value is found to be a syntactic function. When this holds, the compiler automatically inserts the declarations for the parameters.

f :: (int, int) -> int
f = (x, y) -> x * y

# The above is the same as:
f :: (int, int) -> int
f = (x, y) :: (int, int) ->
  x * y

Destructuring array or object types are allowed to more easily type destructuring assignments.

{ x, y } :: { x: int, y: int }
{ x, y } = { x: 0, y: 1 }

# The above is the same as
x :: int
y :: int
{ x, y } = { x: 0, y: 1 }

Note, however, that property accesses in general are untyped. Only statically determinable objects (literals) and statically determinable properties (dot notation or a constant index) are typed.

This is particularly helpful for typing parameters:

f :: ([int, int]) -> int
f = ([i, j]) -> i * j

If the left-hand side of an assignment is typed, the right-hand side must also be typed, and the two types must be unifiable.

n :: *node
n = new node

i :: int
i = n  # error: incompatible types `int' and `*node'
i = {} # error: cannot assign untyped to typed