A Linearly Typed Assembly Language

Abstract

Today's type-safe low-level languages rely on garbage collection to recycle heap-allocated objects safely. We present LTAL, a safe, low-level, yet simple language that ``stands on its own'': it guarantees safe execution within a fixed memory space, without relying on external run-time support. We demonstrate the expressiveness of LTAL by giving a type-preserving compiler for the functional core of ML. But this independence comes at a steep price: LTAL's type system imposes a draconian discipline of linearity that ensures that memory can be reused safely, but prohibits any useful kind of sharing. We present the results of experiments with a prototype LTAL system that show just how high the price of linearity can be.