Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Chapter 20: Data Representation and the Runtime

New files

  • rt/src/layout.rs
  • rt/src/abi.rs
  • rt/src/heap.rs
  • rt/src/apply.rs
  • rt/src/primitives.rs
  • rt/build.rs
  • rt/src/lib.rs

Changed files

  • src/primitives.rs
  • src/lib.rs
  • src/main.rs

Motivation

Our interpreters have enjoyed a useful luxury. Rust enums describe their values, and Rust helps manage their storage. The machine code we’re about to generate won’t have those enums. We need to decide exactly what an integer, a list node, or a closure looks like in memory.

Polymorphism makes the question especially interesting. One compiled id function should accept an integer, a string, or a tree. We’d like to pass all of them through the same calling convention. A uniform machine word gives us that common representation, with a little tagging to distinguish immediate values from pointers.

We’ll build the runtime before connecting LLVM. This lets us inspect the memory layout and application protocol on their own. The interpreters will also reuse its primitive operations. We shouldn’t need three slightly different ideas of how to print a floating-point number.

The Language, Now

The programs we write don’t change here. Our new representation must still give us wrapping 63-bit integers, Unicode characters, UTF-8 strings, and strict constructor fields. Changing how a value fits in memory shouldn’t change what a Fun program can observe.

This inherited program exercises floating display for NaN, infinity, and signed zero:

_old = (0.0/0.0,1.0/0.0,-0.0)

main = print _old

The runtime is available as fun-rt-20, built both as an rlib for the compiler and a staticlib for external linking. The chapter compiler still runs Core, ANF, or Flat. Linking the runtime into a C test does not yet provide fun build. LLVM object generation is the next chapter’s task.

Theory

A value is a 64-bit word. An immediate has low bit one. An aligned pointer has low bit zero. Encoding an integer shifts it left one bit and sets the tag, leaving 63 signed bits. Decoding uses an arithmetic shift. The same immediate encoding holds character scalar values and nullary constructor tags.

#![allow(unused)]
fn main() {
pub type Word = u64;
pub const WORD_BYTES: usize = 8;
pub const INT_MIN: i64 = -(1_i64 << 62);
pub const INT_MAX: i64 = (1_i64 << 62) - 1;
pub const CON: u8 = 0;
pub const CLOSURE: u8 = 1;
pub const PAP: u8 = 2;
pub const DOUBLE: u8 = 3;
pub const STRING: u8 = 4;
pub const FORWARD: u8 = 5;
pub const FALSE: Word = immediate(0);
pub const TRUE: Word = immediate(1);
pub const NIL: Word = immediate(0);
pub const UNIT: Word = immediate(0);
pub const NOTHING: Word = immediate(0);
pub const LT: Word = immediate(0);
pub const EQ: Word = immediate(1);
pub const GT: Word = immediate(2);
pub const CONS_TAG: u32 = 1;
pub const JUST_TAG: u32 = 1;
pub const CLOSURE_CODE: usize = 0;
pub const CLOSURE_ARITY: usize = 1;
pub const CLOSURE_CAPTURES: usize = 2;
pub const PAP_CLOSURE: usize = 0;
pub const PAP_COUNT: usize = 1;
pub const PAP_ARGS: usize = 2;
pub const fn normalize(n: i64) -> i64 {
    (n << 1) >> 1
}
pub const fn signed(w: Word) -> i64 {
    (w as i64) >> 1
}
pub const fn immediate(tag: u32) -> Word {
    ((tag as Word) << 1) | 1
}
pub const fn is_immediate(w: Word) -> bool {
    w & 1 != 0
}
/// Bits 0..8: kind, 8..32: tag, 32..64: payload word count.
pub const fn header(kind: u8, tag: u32, size: u32) -> Word {
    assert!(tag <= 0x00ff_ffff);
    kind as Word | ((tag as Word) << 8) | ((size as Word) << 32)
}
pub const fn kind(h: Word) -> u8 {
    h as u8
}
pub const fn tag(h: Word) -> u32 {
    ((h >> 8) & 0x00ff_ffff) as u32
}
pub const fn size(h: Word) -> usize {
    (h >> 32) as usize
}
pub const fn integer(n: i64) -> Word {
    ((n as u64) << 1) | 1
}
pub type Word = u64;
pub const WORD_BYTES: usize = 8;
pub const INT_MIN: i64 = -(1_i64 << 62);
pub const INT_MAX: i64 = (1_i64 << 62) - 1;
pub const CON: u8 = 0;
pub const CLOSURE: u8 = 1;
pub const PAP: u8 = 2;
pub const DOUBLE: u8 = 3;
pub const STRING: u8 = 4;
pub const FORWARD: u8 = 5;
pub const FALSE: Word = immediate(0);
pub const TRUE: Word = immediate(1);
pub const NIL: Word = immediate(0);
pub const UNIT: Word = immediate(0);
pub const NOTHING: Word = immediate(0);
pub const LT: Word = immediate(0);
pub const EQ: Word = immediate(1);
pub const GT: Word = immediate(2);
pub const CONS_TAG: u32 = 1;
pub const JUST_TAG: u32 = 1;
pub const CLOSURE_CODE: usize = 0;
pub const CLOSURE_ARITY: usize = 1;
pub const CLOSURE_CAPTURES: usize = 2;
pub const PAP_CLOSURE: usize = 0;
pub const PAP_COUNT: usize = 1;
pub const PAP_ARGS: usize = 2;
pub const fn normalize(n: i64) -> i64 {
    (n << 1) >> 1
}
pub const fn integer(n: i64) -> Word {
    ((n as u64) << 1) | 1
}
pub const fn immediate(tag: u32) -> Word {
    ((tag as Word) << 1) | 1
}
pub const fn is_immediate(w: Word) -> bool {
    w & 1 != 0
}
/// Bits 0..8: kind, 8..32: tag, 32..64: payload word count.
pub const fn header(kind: u8, tag: u32, size: u32) -> Word {
    assert!(tag <= 0x00ff_ffff);
    kind as Word | ((tag as Word) << 8) | ((size as Word) << 32)
}
pub const fn kind(h: Word) -> u8 {
    h as u8
}
pub const fn tag(h: Word) -> u32 {
    ((h >> 8) & 0x00ff_ffff) as u32
}
pub const fn size(h: Word) -> usize {
    (h >> 32) as usize
}
pub const fn signed(w: Word) -> i64 {
    (w as i64) >> 1
}
}

Notice something odd about word 1. It can represent unit, False, the empty list, or Nothing. That isn’t an ambiguity the runtime has to resolve. The type checker already established which interpretation the program can use. We don’t inspect a list as though it were a boolean.

This is what makes the uniform representation useful. A polymorphic function can pass words around without needing a different memory layout for every instantiation. Tagging and boxing give strict functional implementations a practical way to make that work (Leroy 1990).

Heap objects begin with a header. Its low eight bits identify the object kind, the next 24 bits carry a constructor tag, and the high 32 bits count payload words. Constructor tags are local to a datatype and follow declaration order. The fixed Prelude tags keep runtime-created lists and optional values compatible with compiler-created ones.

Boehm finds potential pointers by inspecting words in memory (Boehm and Weiser 1988). That saves us from describing every live pointer in the generated code. The tradeoff is that an unrelated bit pattern can look like an address and keep an otherwise dead object alive. The collector also can’t freely move an object when it doesn’t know which apparent pointers are real references to update.

A precise moving collector needs our help. We’ll build that cooperation in Chapter 24, using an explicit account of roots. Henderson and the GC handbook develop this distinction [Henderson (2002); Jones et al. (2023)].

Implementation

rt/src/layout.rs is the shared ABI definition, re-exported by the compiler as runtime_layout to avoid its existing offside-layout module. Header construction checks that the constructor tag fits:

#![allow(unused)]
fn main() {
pub type Word = u64;
pub const WORD_BYTES: usize = 8;
pub const INT_MIN: i64 = -(1_i64 << 62);
pub const INT_MAX: i64 = (1_i64 << 62) - 1;
pub const CON: u8 = 0;
pub const CLOSURE: u8 = 1;
pub const PAP: u8 = 2;
pub const DOUBLE: u8 = 3;
pub const STRING: u8 = 4;
pub const FORWARD: u8 = 5;
pub const FALSE: Word = immediate(0);
pub const TRUE: Word = immediate(1);
pub const NIL: Word = immediate(0);
pub const UNIT: Word = immediate(0);
pub const NOTHING: Word = immediate(0);
pub const LT: Word = immediate(0);
pub const EQ: Word = immediate(1);
pub const GT: Word = immediate(2);
pub const CONS_TAG: u32 = 1;
pub const JUST_TAG: u32 = 1;
pub const CLOSURE_CODE: usize = 0;
pub const CLOSURE_ARITY: usize = 1;
pub const CLOSURE_CAPTURES: usize = 2;
pub const PAP_CLOSURE: usize = 0;
pub const PAP_COUNT: usize = 1;
pub const PAP_ARGS: usize = 2;
pub const fn normalize(n: i64) -> i64 {
    (n << 1) >> 1
}
pub const fn integer(n: i64) -> Word {
    ((n as u64) << 1) | 1
}
pub const fn signed(w: Word) -> i64 {
    (w as i64) >> 1
}
pub const fn immediate(tag: u32) -> Word {
    ((tag as Word) << 1) | 1
}
pub const fn is_immediate(w: Word) -> bool {
    w & 1 != 0
}
pub const fn kind(h: Word) -> u8 {
    h as u8
}
pub const fn tag(h: Word) -> u32 {
    ((h >> 8) & 0x00ff_ffff) as u32
}
pub const fn size(h: Word) -> usize {
    (h >> 32) as usize
}
/// Bits 0..8: kind, 8..32: tag, 32..64: payload word count.
pub const fn header(kind: u8, tag: u32, size: u32) -> Word {
    assert!(tag <= 0x00ff_ffff);
    kind as Word | ((tag as Word) << 8) | ((size as Word) << 32)
}
}

The payload layouts are deliberately simple:

KindPayload after the header
CONConstructor fields, one word each
CLOSURESlow code address, arity, then captures
PAPClosure word, argument count, then supplied arguments
DOUBLEOne word containing binary64 bits
STRINGByte length, then padded UTF-8 bytes
FORWARDReserved for the later copying collector

Reading the Heap

Start with the word held in a variable. Its low bit tells us whether the value fits in that word or points to an object. A pointer addresses the header, not the first field. All offsets below are bytes, and every row occupies eight bytes.

Value word (64 bits)

Int 42:     [ 85 ]  low bit 1
Heap value: [ p  ]  low bit 0
              |
              v
+----------------------------+
| header                     | +0
| payload[0]                 | +8
| payload[1]                 | +16
| ...                        |
+----------------------------+

Header bits (most significant first)
 63             32 31           8 7            0
+-----------------+--------------+--------------+
| size: 32 bits   | tag: 24 bits | kind: 8 bits |
+-----------------+--------------+--------------+

For example, Just 42 needs one payload word. Its constructor tag is 1. A Double also needs one payload word, but that word contains floating-point bits rather than an encoded Fun value.

Just 42
+----------------------------+
| CON, tag=1, size=1         | +0
| 85 (tagged Int 42)         | +8
+----------------------------+

Double 3.0
+----------------------------+
| DOUBLE, tag=0, size=1      | +0
| 0x4008000000000000         | +8
+----------------------------+

A closure packages code with the values it captured. Imagine the local function f x y = k + x + y, with k = 10. Its arity is two and its environment has one capture. Applying f to just 20 creates a partial application, or PAP, which points back to the closure and remembers that argument.

PAP for f 20
+----------------------------+
| PAP, tag=0, size=3         | +0
| closure word               | +8 ----+
| argument count: 1          | +16    |
| 41 (tagged Int 20)         | +24    |
+----------------------------+        |
       +------------------------------+
       |
       |  Closure for f
       |  +----------------------------+
       +->| CLOSURE, tag=0, size=3     | +0
          | slow entry address         | +8
          | arity: 2                   | +16
          | capture k: 21 (Int 10)     | +24
          +----------------------------+

The arrow denotes a pointer to the whole closure object. Arity and argument count are raw counts, not tagged integers. Captures and saved arguments are Fun value words, so they may themselves point to other objects. The slow entry is a code address. Calling the PAP with 22 combines the saved 20 with 22, then enters the closure with both arguments. The closure’s capture remains 10.

A string stores a byte count followed by UTF-8 bytes padded to whole words. For "hi", the payload has two words: the count and one word of byte storage. The padding is not part of the string, and no terminating zero is required.

String "hi"
+----------------------------+
| STRING, tag=0, size=2      | +0
| byte length: 2             | +8
| 68 69 .. .. .. .. .. ..    | +16
+----------------------------+
Hex bytes; .. denotes padding.

rt_alloc takes a total word count including the header. rt_alloc_atomic takes bytes and asks Boehm not to scan the contents. Doubles and strings use atomic allocation because their payload contains no value pointers. A string’s stored length counts bytes. The source string-length primitive counts Unicode scalars. Alignment is eight bytes throughout.

Allocation must protect input fields while the collector runs. A Rust Vec is allocated by Rust’s allocator, and Boehm does not automatically trace through that buffer. Roots owns a stable boxed word buffer and registers its interior range with the collector. Its destructor removes the range before freeing the buffer. Two unregistered guard words keep adjacent registrations distinct. Object construction uses this protection before allocating and copying fields:

#![allow(unused)]
fn main() {
use crate::layout::{self, Word};
use std::{ffi::c_void, ptr, sync::Once};
#[repr(C)]
struct StackBase {
    mem_base: *mut c_void,
}
unsafe extern "C" {
    fn GC_init();
    fn GC_allow_register_threads();
    fn GC_thread_is_registered() -> i32;
    fn GC_get_stack_base(base: *mut StackBase) -> i32;
    fn GC_register_my_thread(base: *const StackBase) -> i32;
    fn GC_unregister_my_thread() -> i32;
    fn GC_malloc(n: usize) -> *mut c_void;
    fn GC_malloc_atomic(n: usize) -> *mut c_void;
    fn GC_add_roots(start: *mut c_void, end: *mut c_void);
    fn GC_remove_roots(start: *mut c_void, end: *mut c_void);
    fn GC_gcollect();
}
static INIT: Once = Once::new();
struct Registration(bool);
impl Drop for Registration {
    fn drop(&mut self) {
        if self.0 {
            // SAFETY: only this thread's successful explicit registration is removed.
            unsafe {
                GC_unregister_my_thread();
            }
        }
    }
}
thread_local! {
    static THREAD: Registration = {
        // SAFETY: INIT completed first; StackBase matches gc.h on our supported targets.
        unsafe {
            if GC_thread_is_registered() != 0 { Registration(false) }
            else {
                let mut base = StackBase { mem_base: ptr::null_mut() };
                assert_eq!(GC_get_stack_base(&mut base), 0, "cannot find GC stack base");
                assert_eq!(GC_register_my_thread(&base), 0, "cannot register GC thread");
                Registration(true)
            }
        }
    };
}
/// Call on the main thread before starting runtime worker threads.
#[unsafe(no_mangle)]
pub extern "C" fn rt_init() {
    crate::primitives::init_io();
    INIT.call_once(|| {
        // SAFETY: initialization is serialized and precedes every heap operation.
        unsafe {
            GC_init();
            GC_allow_register_threads();
        }
    });
    THREAD.with(|_| {});
}
fn checked(p: *mut c_void) -> *mut c_void {
    if p.is_null() {
        eprintln!("fun: out of memory");
        std::process::abort();
    }
    assert_eq!(p as usize % layout::WORD_BYTES, 0);
    p
}
/// Allocate total words, including the header, with pointer scanning enabled.
#[unsafe(no_mangle)]
pub extern "C" fn rt_alloc(words: usize) -> *mut Word {
    rt_init();
    let bytes = words
        .checked_mul(layout::WORD_BYTES)
        .expect("allocation size overflow");
    // SAFETY: the initialized collector returns suitably aligned storage of this size.
    checked(unsafe { GC_malloc(bytes.max(8)) }).cast()
}
/// Allocate bytes for a pointer-free object; callers initialize its header and payload.
#[unsafe(no_mangle)]
pub extern "C" fn rt_alloc_atomic(bytes: usize) -> *mut u8 {
    rt_init();
    // SAFETY: the initialized collector returns aligned storage, never scanned as pointers.
    checked(unsafe { GC_malloc_atomic(bytes.max(8)) }).cast()
}
/// A registered, independently owned range. Rust's ordinary heap is not scanned by Boehm.
pub struct Roots {
    words: Box<[Word]>,
}
impl Roots {
    pub fn new(words: &[Word]) -> Self {
        // Unregistered guard words prevent Boehm merging adjacent root ranges.
        let mut storage = vec![0; words.len() + 2];
        storage[1..words.len() + 1].copy_from_slice(words);
        let words = storage.into_boxed_slice();
        rt_init();
        if words.len() > 2 {
            // SAFETY: this stable, exclusively owned allocation lasts until Drop removes it.
            unsafe {
                GC_add_roots(
                    words.as_ptr().add(1) as *mut c_void,
                    words.as_ptr().add(words.len() - 1) as *mut c_void,
                );
            }
        }
        Self { words }
    }
    pub fn as_slice(&self) -> &[Word] {
        &self.words[1..self.words.len() - 1]
    }
}
impl Drop for Roots {
    fn drop(&mut self) {
        if self.words.len() > 2 {
            // SAFETY: removes exactly the registered range, before its allocation is freed.
            unsafe {
                GC_remove_roots(
                    self.words.as_ptr().add(1) as *mut c_void,
                    self.words.as_ptr().add(self.words.len() - 1)
                        as *mut c_void,
                );
            }
        }
    }
}
/// Force a collection for ABI validation. Live words must be on registered stacks or roots.
pub fn collect() {
    rt_init();
    // SAFETY: the calling thread is registered and the collector owns its heap.
    unsafe {
        GC_gcollect();
    }
}
pub fn constructor(tag: u32, fields: &[Word]) -> Word {
    if fields.is_empty() {
        layout::immediate(tag)
    } else {
        object(layout::CON, tag, fields)
    }
}
pub fn double(n: f64) -> Word {
    let p = rt_alloc_atomic(16).cast::<Word>();
    // SAFETY: a DOUBLE consists of one header and one unscanned f64 word.
    unsafe {
        p.write(layout::header(layout::DOUBLE, 0, 1));
        p.add(1).write(n.to_bits());
    }
    p as Word
}
pub fn string(s: &str) -> Word {
    let payload = 1 + s.len().div_ceil(8);
    let size = u32::try_from(payload).expect("string too large");
    let bytes = (payload + 1).checked_mul(8).expect("string size overflow");
    let p = rt_alloc_atomic(bytes);
    // SAFETY: p contains header, byte length, then padded UTF-8 bytes; no pointers are stored.
    unsafe {
        p.write_bytes(0, bytes);
        p.cast::<Word>()
            .write(layout::header(layout::STRING, 0, size));
        p.cast::<Word>().add(1).write(s.len() as Word);
        ptr::copy_nonoverlapping(s.as_ptr(), p.add(16), s.len());
    }
    p as Word
}
/// # Safety
/// w must point to a live, aligned heap object with a valid header.
pub unsafe fn header(w: Word) -> Word {
    assert!(!layout::is_immediate(w) && w != 0);
    // SAFETY: required live object header is the first word.
    unsafe { (w as *const Word).read() }
}
/// # Safety
/// w must be a live object and index must name a payload word.
pub unsafe fn field(w: Word, index: usize) -> Word {
    // SAFETY: the caller guarantees a live object; bounds are checked before reading.
    unsafe {
        assert!(index < layout::size(header(w)));
        (w as *const Word).add(index + 1).read()
    }
}
/// # Safety
/// w must be a live DOUBLE object.
pub unsafe fn unbox_double(w: Word) -> f64 {
    // SAFETY: the object kind and its fixed-size payload are checked.
    unsafe {
        assert_eq!(layout::kind(header(w)), layout::DOUBLE);
        f64::from_bits(field(w, 0))
    }
}
/// # Safety
/// w must be a live STRING, kept rooted for the returned borrow's entire lifetime.
pub unsafe fn text<'a>(w: Word) -> &'a str {
    // SAFETY: caller maintains the object; header/length/UTF-8 are checked before borrowing.
    unsafe {
        let h = header(w);
        assert_eq!(layout::kind(h), layout::STRING);
        let len = field(w, 0) as usize;
        assert!(
            len <= layout::size(h)
                .checked_sub(1)
                .expect("string length word")
                * 8
        );
        std::str::from_utf8(std::slice::from_raw_parts(
            (w as *const u8).add(16),
            len,
        ))
        .expect("runtime UTF-8")
    }
}
/// Allocate a scanned object, protecting fields even when supplied in a Rust Vec.
pub fn object(kind: u8, tag: u32, fields: &[Word]) -> Word {
    let roots = Roots::new(fields);
    let size = u32::try_from(fields.len()).expect("object too large");
    let p = rt_alloc(fields.len() + 1);
    // SAFETY: p has header + fields words; protected input and destination do not overlap.
    unsafe {
        p.write(layout::header(kind, tag, size));
        ptr::copy_nonoverlapping(
            roots.as_slice().as_ptr(),
            p.add(1),
            fields.len(),
        );
    }
    p as Word
}
}

The runtime initializes Boehm on the main thread. Foreign Rust worker threads register their stacks and unregister when they exit. Direct ABI tests force collection inside calls and while cyclic closure environments are live. Those cases would expose assumptions that work only when allocation happens not to collect.

A closure stores a C-convention slow entry and its syntactic arity. The entry receives the closure word and a pointer to exactly that arity’s arguments. Closure construction simply builds the corresponding object:

#![allow(unused)]
fn main() {
use crate::{
    heap::{self, Roots},
    layout::{self, Word},
};
/// The slow entry receives its closure word and exactly its syntactic arity of arguments.
pub type Slow = unsafe extern "C" fn(Word, *const Word) -> Word;
/// # Safety
/// Arguments must be valid live words of the callee's source types, rooted by the caller.
/// args must point to n readable words (or may be null when n is zero).
#[unsafe(no_mangle)]
pub unsafe extern "C" fn rt_make_pap(
    clo: Word,
    n: usize,
    args: *const Word,
) -> Word {
    // SAFETY: caller supplies a readable argument array and a live function value.
    unsafe {
        let args = arguments(n, args);
        let mut fields = vec![clo, n as Word];
        fields.extend_from_slice(args);
        heap::object(layout::PAP, 0, &fields)
    }
}
unsafe fn arguments<'a>(n: usize, args: *const Word) -> &'a [Word] {
    if n == 0 {
        &[]
    } else {
        // SAFETY: the enclosing ABI contract requires n initialized, aligned words.
        unsafe { std::slice::from_raw_parts(args, n) }
    }
}
/// # Safety
/// clo must be a live CLOSURE and index a capture slot; value must be live and well typed.
/// Patching is confined to unpublished letrec initialization; no concurrent readers exist.
#[unsafe(no_mangle)]
pub unsafe extern "C" fn rt_closure_set(
    clo: Word,
    index: usize,
    value: Word,
) {
    // SAFETY: caller guarantees exclusive initialization; checked index excludes code/arity.
    unsafe {
        let h = heap::header(clo);
        assert_eq!(layout::kind(h), layout::CLOSURE);
        let i = index
            .checked_add(layout::CLOSURE_CAPTURES)
            .expect("capture overflow");
        assert!(i < layout::size(h));
        (clo as *mut Word).add(i + 1).write(value);
    }
}
/// # Safety
/// clo is a live closure or PAP; args is n valid, rooted, correctly typed words.
/// Every slow entry must obey the runtime ABI and return a live word of its result type.
#[unsafe(no_mangle)]
pub unsafe extern "C" fn rt_apply(
    mut clo: Word,
    n: usize,
    args: *const Word,
) -> Word {
    // SAFETY: all raw accesses follow the caller's typed-object contract and checked headers.
    unsafe {
        let mut roots = Roots::new(arguments(n, args));
        loop {
            let h = heap::header(clo);
            match layout::kind(h) {
                layout::PAP => {
                    let count =
                        heap::field(clo, layout::PAP_COUNT) as usize;
                    assert_eq!(layout::size(h), count + layout::PAP_ARGS);
                    let mut all = (0..count)
                        .map(|i| heap::field(clo, layout::PAP_ARGS + i))
                        .collect::<Vec<_>>();
                    all.extend_from_slice(roots.as_slice());
                    roots = Roots::new(&all);
                    clo = heap::field(clo, layout::PAP_CLOSURE);
                }
                layout::CLOSURE => {
                    let arity =
                        heap::field(clo, layout::CLOSURE_ARITY) as usize;
                    assert!(arity > 0);
                    if roots.as_slice().len() < arity {
                        return rt_make_pap(
                            clo,
                            roots.as_slice().len(),
                            roots.as_slice().as_ptr(),
                        );
                    }
                    let address = heap::field(clo, layout::CLOSURE_CODE);
                    // SAFETY: closure construction stores a Slow address, validated by the ABI contract.
                    let code: Slow = std::mem::transmute::<usize, Slow>(
                        address as usize,
                    );
                    let result = code(clo, roots.as_slice().as_ptr());
                    if roots.as_slice().len() == arity {
                        return result;
                    }
                    roots = Roots::new(&roots.as_slice()[arity..]);
                    clo = result;
                }
                _ => panic!("runtime application of non-function"),
            }
        }
    }
}
macro_rules! apply_n { ($name:ident; $($arg:ident),+) => {
    /// Fixed-size apply entry point.
    /// # Safety
    /// The closure and argument words must satisfy rt_apply's typed, live-object contract.
    #[unsafe(no_mangle)]
    pub unsafe extern "C" fn $name(clo: Word, $($arg: Word),+) -> Word {
        let args = [$($arg),+];
        // SAFETY: the local array contains the caller's valid words for the duration of apply.
        unsafe { rt_apply(clo, args.len(), args.as_ptr()) }
    }
}; }
apply_n!(rt_apply1; a);
apply_n!(rt_apply2; a,b);
apply_n!(rt_apply3; a,b,c);
apply_n!(rt_apply4; a,b,c,d);
/// Store a code address, syntactic arity, then captured values.
pub fn closure(code: Slow, arity: usize, captures: &[Word]) -> Word {
    assert!(arity > 0);
    let mut fields = vec![code as usize as Word, arity as Word];
    fields.extend_from_slice(captures);
    heap::object(layout::CLOSURE, 0, &fields)
}
}

rt_apply roots its argument buffer, combines saved PAP arguments with new ones, and repeats the eval/apply protocol from Chapter 19 (Marlow and Peyton Jones 2004). A short call allocates a PAP, an exact call enters code, and an oversaturated call continues with the returned closure and remaining arguments. rt_apply1 through rt_apply4 use the same implementation. rt_closure_set checks and patches capture slots only during unpublished recursive-group initialization.

The loop in apply does not guarantee native tail-call elimination through C slow entries: the entry itself may call apply again. Chapter 21’s known fast calls need their own LLVM tail-call convention. The iterative ANF and Flat machines already avoid recursive host calls, but that is a property of those interpreters, not an automatic property of the C ABI.

primitives.rs separates a safe, typed value API from the word ABI in abi.rs. All three interpreters adapt their data values to that safe API. They retain their own control-flow engines and heap models. Native-facing exports decode words according to their checked source types, call the shared semantics, and encode the result. Unsafe accesses are confined to the runtime and documented with typed, live-object contracts. Unwinding across an extern "C" entry aborts. Language failures instead follow the explicit runtime error and exit paths.

show_double starts with Rust’s shortest round-trip digits, then normalizes notation. Nonzero magnitudes from 1e-4 inclusive to 1e16 exclusive use positional notation. Other finite values use a signed exponent. Zero retains its sign, and special values spell NaN, Infinity, and -Infinity. We check boundary values through both the safe API and the word ABI, including whether finite values survive a print-and-read round trip with the same bits. readInt accepts optional surrounding whitespace and a decimal sign, then rejects values outside the signed 63-bit range. Floating round uses ties-to-even and saturates. NaN converts to zero.

Running It

The larger double-specials fixture also checks the positional/scientific notation boundary:

$ cd crates/ch20_runtime
$ cargo run -q -- run tests/programs/runtime/double-specials.fun --lint
-0.0
NaN
Infinity
-Infinity
0.0001
1.0e+16
$ cargo run -q -- dump --pass=types tests/programs/runtime/double-specials.fun
main : IO ()

From the repository root, cargo test -p fun-rt-20 exercises primitive semantics and the standalone ABI harness. python3 scripts/check_runtime_abi.py builds the static runtime, asks rustc for the host’s native static libraries, links the C smoke program with the system compiler, and checks that it prints 42. just build also builds the runtime explicitly before the workspace. Linux requires libgc-dev. MacOS uses Homebrew’s bdw-gc, with GC_LIB_DIR available for another installation location.

A collector bug often hides until allocation happens at exactly the wrong moment. The runtime tests force collection while recursive closures are being built and while calls hold live arguments. They also exercise partial and oversaturated calls, Unicode strings, and output before errors. These are the places where a correct-looking object layout has to work as part of a running program.

Exercises

  1. Warm-up. Compute the encoded words for -1, 0, True, and unit. Explain why equal words need not represent equal source values.
  2. Intermediate. Draw a two-field constructor and a one-argument PAP, including their headers and payload sizes.
  3. Intermediate. Explain why a live pointer stored only in an ordinary Rust vector can disappear from Boehm’s view.
  4. Advanced. Add a forced collection between recursive closure allocation and patching in an ABI test, keeping every unfinished object rooted.
  5. Advanced. Identify what extra metadata a moving collector would need to update closure captures, PAP arguments, globals, and live local values.

Further Reading