20장: 데이터 표현과 런타임

새 파일

• 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

변경된 파일

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

동기

지금까지 우리 인터프리터는 쓸모 있는 호사를 누려 왔습니다. Rust 열거형이 값을 기술하고, Rust가 그 저장 공간 관리를 돕습니다. 이제 우리가 생성할 기계어 코드에는 그런 열거형이 없습니다. 정수, 리스트 노드, 클로저가 메모리에서 정확히 어떤 모습인지 우리가 정해야 합니다.

다형성 때문에 이 질문은 특히 흥미로워집니다. 컴파일된 id 함수 하나가 정수, 문자열, 트리를 모두 받을 수 있어야 합니다. 우리는 이 모든 값을 같은 호출 규약으로 전달하고 싶습니다. 균일한 기계어 워드를 쓰면 그런 공통 표현을 얻을 수 있고, 약간의 태깅으로 즉칫값과 포인터를 구별할 수 있습니다.

LLVM을 연결하기 전에 런타임부터 만들겠습니다. 이렇게 하면 메모리 레이아웃과 적용 프로토콜을 따로 떼어 살펴볼 수 있습니다. 인터프리터들도 런타임의 기본 연산을 재사용할 것입니다. 부동소수점 수를 출력하는 방법에 대해 조금씩 다른 생각을 세 가지나 둘 필요는 없을 것입니다.

현재의 언어

여기서 우리가 작성하는 프로그램은 바뀌지 않습니다. 새 표현도 여전히 래핑되는 63비트 정수, 유니코드 문자, UTF-8 문자열, 엄격한 생성자 필드를 제공해야 합니다. 값이 메모리에 들어가는 방식을 바꾸더라도 Fun 프로그램이 관찰할 수 있는 것이 바뀌어서는 안 됩니다.

이 상속된 프로그램으로 NaN, 무한대, 부호 있는 0의 부동소수점 표시를 연습 문제처럼 시험해 봅니다:

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

main = print _old

런타임은 fun-rt-20으로 제공되며, 컴파일러를 위한 rlib와 외부 링크를 위한 staticlib 두 가지 형태로 모두 빌드됩니다. 이 장의 컴파일러는 여전히 Core, ANF, Flat을 실행합니다. 런타임을 C 테스트에 링크한다고 해서 아직 fun build가 생기는 것은 아닙니다. LLVM 오브젝트 생성은 다음 장에서 할 일입니다.

이론

값은 64비트 워드입니다. 즉치값(immediate)은 최하위 비트가 1입니다. 정렬된 포인터는 최하위 비트가 0입니다. 정수를 인코딩할 때는 왼쪽으로 1비트 시프트한 뒤 태그를 설정하므로, 부호 있는 63비트가 남습니다. 디코딩에는 산술 시프트를 사용합니다. 같은 즉칫값 인코딩으로 문자 스칼라 값과 인자 없는 생성자 태그도 담습니다.

#![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
}
}

워드 1에 관해 이상한 점이 하나 있습니다. 이 워드는 유닛, False, 빈 리스트, Nothing 중 무엇이든 나타낼 수 있습니다. 이는 런타임이 해소해야 하는 모호함이 아닙니다. 프로그램이 어떤 해석을 사용할 수 있는지는 타입 검사기가 이미 확정했습니다. 우리는 리스트를 불리언인 것처럼 검사하지 않습니다.

바로 이 점이 균일한 표현을 유용하게 만듭니다. 다형 함수는 인스턴스화마다 다른 메모리 레이아웃을 필요로 하지 않고도 워드를 주고받을 수 있습니다. 태깅과 박싱은 엄격한 함수형 언어 구현이 이를 실현할 수 있는 실용적인 방법을 제공합니다(Leroy 1990).

힙 객체는 헤더로 시작합니다. 헤더의 하위 8비트는 객체 종류를 식별하고, 그다음 24비트는 생성자 태그를 담으며, 상위 32비트는 페이로드 워드 수를 셉니다. 생성자 태그는 데이터 타입마다 따로 매겨지며 선언 순서를 따릅니다. Prelude의 고정 태그 덕분에 런타임이 만든 리스트와 옵션 값이 컴파일러가 만든 것과 호환됩니다.

Boehm은 메모리의 워드를 조사하여 포인터일 가능성이 있는 값을 찾습니다 (Boehm and Weiser 1988). 덕분에 우리는 생성된 코드에서 살아 있는 포인터를 하나하나 기술하지 않아도 됩니다. 트레이드오프는 무관한 비트 패턴이 주소처럼 보여서, 원래는 죽은 객체를 살아 있게 붙잡아 둘 수 있다는 점입니다. 또한 수집기는 겉보기 포인터 중 어느 것이 갱신해야 할 실제 참조인지 모르기 때문에 객체를 자유롭게 옮길 수 없습니다.

정밀한 이동 수집기에는 우리의 도움이 필요합니다. 우리는 24장에서 루트를 명시적으로 관리하는 방식으로 그 협력을 구축할 것입니다. Henderson과 GC 핸드북에서 이 구분을 자세히 다룹니다 [Henderson (2002); Jones et al. (2023)].

구현

rt/src/layout.rs는 공유 ABI 정의이며, 컴파일러는 기존의 오프사이드 레이아웃 모듈과 겹치지 않도록 이를 runtime_layout이라는 이름으로 다시 내보냅니다. 헤더를 만들 때는 생성자 태그가 들어맞는지 검사합니다:

#![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)
}
}

페이로드 레이아웃은 일부러 단순하게 만들었습니다:

힙 읽기

변수에 담긴 워드에서 시작합시다. 이 워드의 최하위 비트를 보면 값이 그 워드 안에 들어가는지, 아니면 객체를 가리키는지 알 수 있습니다. 포인터는 첫 번째 필드가 아니라 헤더를 가리킵니다. 아래의 오프셋은 모두 바이트 단위이며, 각 행은 8바이트를 차지합니다.

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 |
+-----------------+--------------+--------------+

예를 들어 Just 42에는 페이로드 워드가 하나 필요합니다. 이 값의 생성자 태그는 1입니다. Double도 페이로드 워드가 하나 필요하지만, 그 워드에는 인코딩된 Fun 값이 아니라 부동소수점 비트가 들어 있습니다.

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

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

클로저는 코드와 그 코드가 캡처한 값들을 하나로 묶습니다. k = 10일 때 지역 함수 f x y = k + x + y를 생각해 봅시다. 이 함수의 항수는 2이고 환경에는 캡처가 하나 있습니다. f를 20 하나에만 적용하면 부분 적용(partial application), 즉 PAP가 만들어집니다. PAP는 원래 클로저를 가리키며 그 인자를 기억합니다.

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
          +----------------------------+

화살표는 클로저 객체 전체를 가리키는 포인터를 나타냅니다. 항수와 인자 개수는 태그가 붙은 정수가 아니라 원시 개수입니다. 캡처와 저장된 인자는 Fun 값 워드이므로, 그 자체가 다른 객체를 가리킬 수 있습니다. 느린 진입점(slow entry)은 코드 주소입니다. PAP를 22로 호출하면 저장된 20과 22를 합친 다음, 두 인자를 모두 가지고 클로저에 진입합니다. 클로저의 캡처는 여전히 10입니다.

문자열은 바이트 수를 저장하고, 그 뒤에 워드 단위로 패딩된 UTF-8 바이트를 저장합니다. "hi"의 경우 페이로드는 두 워드, 즉 바이트 수 한 워드와 바이트 저장용 한 워드로 이루어집니다. 패딩은 문자열의 일부가 아니며, 끝을 나타내는 0도 필요하지 않습니다.

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

rt_alloc은 헤더를 포함한 전체 워드 수를 받습니다. rt_alloc_atomic은 바이트 수를 받고, Boehm에게 내용을 스캔하지 말라고 요청합니다. 배정밀도 실수(double)와 문자열은 페이로드에 값 포인터가 없으므로 원자적(atomic) 할당을 사용합니다. 문자열에 저장된 길이는 바이트 수를 셉니다. 소스 언어의 문자열 길이 프리미티브는 유니코드 스칼라 값의 개수를 셉니다. 정렬은 전체적으로 8바이트입니다.

할당은 수집기가 실행되는 동안 입력 필드를 보호해야 합니다. Rust Vec은 Rust의 할당자로 할당되며, Boehm은 그 버퍼를 자동으로 추적하지 않습니다. Roots는 위치가 고정된 박스 워드 버퍼를 소유하고, 그 내부 범위를 수집기에 등록합니다. 소멸자는 버퍼를 해제하기 전에 그 범위를 등록 해제합니다. 등록되지 않은 가드 워드 두 개가 인접한 등록 범위들을 서로 구별되게 유지합니다. 객체 생성은 필드를 할당하고 복사하기 전에 이 보호 장치를 사용합니다:

#![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
}
}

런타임은 메인 스레드에서 Boehm을 초기화합니다. 외부 Rust 작업자 스레드는 자신의 스택을 등록하고, 종료할 때 등록을 해제합니다. 직접적인 ABI 테스트는 호출 내부에서, 그리고 순환하는 클로저 환경이 살아 있는 동안 수집을 강제로 일으킵니다. 이러한 경우들은 할당이 우연히 수집을 일으키지 않을 때만 동작하는 가정을 드러냅니다.

클로저는 C 호출 규약을 따르는 느린 진입점과 그 구문적 항수를 저장합니다. 이 진입점은 클로저 워드와, 정확히 그 항수만큼의 인자를 가리키는 포인터를 받습니다. 클로저 생성은 단순히 해당 객체를 만듭니다:

#![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는 인자 버퍼를 루트로 등록하고, 저장된 PAP 인자와 새 인자를 합친 뒤, 19장의 eval/apply 프로토콜을 반복합니다(Marlow and Peyton Jones 2004). 인자가 모자란 호출은 PAP를 할당하고, 정확한 호출은 코드로 진입하며, 과포화 호출은 반환된 클로저와 남은 인자로 계속 진행합니다. rt_apply1부터 rt_apply4까지는 같은 구현을 사용합니다. rt_closure_set은 아직 공개되지 않은 재귀 그룹의 초기화 중에만 캡처 슬롯을 검사하고 수정합니다.

apply의 루프는 C 느린 진입점을 거치는 네이티브 꼬리 호출 제거를 보장하지 않습니다. 진입점 자체가 다시 apply를 호출할 수 있기 때문입니다. 21장의 알려진 빠른 호출(known fast call)에는 별도의 LLVM 꼬리 호출 규약이 필요합니다. 반복적인 ANF 및 Flat 머신은 이미 재귀적인 호스트 호출을 피하지만, 이는 그 인터프리터들의 성질일 뿐 C ABI가 자동으로 갖는 성질이 아닙니다.

primitives.rs는 안전하고 타입이 있는 값 API를 abi.rs의 워드 ABI와 분리합니다. 세 인터프리터 모두 자신의 데이터 값을 그 안전한 API에 맞춰 변환합니다. 각 인터프리터는 자체 제어 흐름 엔진과 힙 모델을 그대로 유지합니다. 네이티브 쪽 익스포트는 검사된 소스 타입에 따라 워드를 디코딩하고, 공유 의미론을 호출한 뒤, 결과를 인코딩합니다. 안전하지 않은 접근은 런타임 안으로 한정되며, 타입이 지정된 살아 있는 객체에 대한 계약으로 문서화됩니다. extern "C" 진입점을 가로지르는 언와인딩은 중단(abort)됩니다. 반면 언어 차원의 실패는 명시적인 런타임 오류 경로와 종료 경로를 따릅니다.

show_double은 Rust의 최단 왕복(round-trip) 숫자열에서 시작한 뒤 표기법을 정규화합니다. 크기가 1e-4 이상 1e16 미만인 0이 아닌 값은 자릿값 표기법을 사용합니다. 그 밖의 유한한 값은 부호 있는 지수를 사용합니다. 0은 부호를 유지하며, 특수 값은 NaN, Infinity, -Infinity로 표기합니다. 우리는 경계값을 안전한 API와 워드 ABI 양쪽을 통해 검사하며, 유한한 값이 출력 후 다시 읽는 왕복을 거쳐도 같은 비트로 남는지도 확인합니다. readInt는 앞뒤의 선택적 공백과 십진 부호를 허용한 다음, 부호 있는 63비트 범위를 벗어나는 값을 거부합니다. 부동소수점 round는 동률일 때 짝수로 반올림(ties-to-even)하며 포화(saturate)됩니다. NaN은 0으로 변환됩니다.

실행해 보기

더 큰 double-specials 픽스처는 자릿값/과학적 표기법의 경계도 검사합니다:

$ 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 ()

저장소 루트에서 cargo test -p fun-rt-20을 실행하면 기본 연산의 의미와 독립 실행형 ABI 하네스를 연습 문제처럼 두루 시험합니다. python3 scripts/check_runtime_abi.py는 정적 런타임을 빌드하고, rustc에 호스트의 네이티브 정적 라이브러리를 물어본 다음, 시스템 컴파일러로 C 스모크 프로그램을 링크하고, 그 프로그램이 42를 출력하는지 확인합니다. just build 역시 워크스페이스보다 먼저 런타임을 명시적으로 빌드합니다. Linux에서는 libgc-dev가 필요합니다. MacOS에서는 Homebrew의 bdw-gc를 사용하며, 다른 설치 위치를 쓰려면 GC_LIB_DIR을 지정할 수 있습니다.

수집기 버그는 할당이 정확히 잘못된 순간에 일어날 때까지 숨어 있는 경우가 많습니다. 런타임 테스트는 재귀 클로저를 만드는 도중과 호출이 살아 있는 인자를 붙들고 있는 동안에 수집을 강제로 일으킵니다. 이 테스트들은 부분 호출과 과포화 호출, 유니코드 문자열, 오류 전 출력도 연습 문제처럼 두루 시험합니다. 이런 곳들이야말로 겉보기에 올바른 객체 레이아웃이 실행 중인 프로그램의 일부로서 제대로 동작해야 하는 지점입니다.

연습 문제

1. 기초. -1, 0, True, unit에 대한 인코딩된 워드를 계산하십시오. 같은 워드가 반드시 같은 소스 값을 나타내지는 않는 이유를 설명하십시오.
2. 중급. 필드가 두 개인 생성자와 인자가 하나인 PAP를 헤더와 페이로드 크기를 포함해 그려 보십시오.
3. 중급. 일반적인 Rust 벡터에만 저장된 살아 있는 포인터가 Boehm의 시야에서 사라질 수 있는 이유를 설명하십시오.
4. 고급. ABI 테스트에서 재귀 클로저 할당과 패치 사이에 강제 수집을 추가하되, 완성되지 않은 모든 객체가 루트로 유지되도록 하십시오.
5. 고급. 이동 수집기가 클로저 캡처, PAP 인자, 전역 변수, 살아 있는 지역 값을 갱신하려면 어떤 추가 메타데이터가 필요한지 밝히십시오.

더 읽을거리

• 컴파일러의 협조 없이 이루어지는 보수적 수집 (Boehm and Weiser 1988).
• 컴파일러의 협력을 통한 루트 탐색 (Henderson 2002).
• 엄격한 함수형 런타임에서의 표현 방식 선택 (Leroy 1990).
• Eval/apply와 부분 적용 (Marlow and Peyton Jones 2004).
• 수집 알고리즘과 구현상의 트레이드오프 (Jones et al. 2023).
• Takenobu Tani의 GHC (STG, Cmm, asm) Illustrated(pdf / github)는 GHC의 힙 객체, 스택 레이아웃, 호출 규약을 우리 것과 나란히 비교해 보기에 좋습니다.