What Is Level-Shifting in the Maru Compiler? A Deep Dive into Self-Hosting Compilation

Level-shifting in the Maru compiler is the semantics-preserving transformation that translates high-level Maru code (S-expressions in the "upper" realm) into executable target code (machine code, LLVM bitcode, or C) in the "lower" realm.

In the attila-lendvai/maru repository, level-shifting represents the core compilation pipeline that enables Maru to bootstrap itself. Unlike traditional compilers that treat source and target as separate black boxes, Maru explicitly models the relationship between the host evaluator (upper realm) and the generated runtime (lower realm) as a bridge between two distinct execution levels.

Understanding the Upper and Lower Realms

Level-shifting operates on a fundamental dichotomy between two execution environments:

• The Upper Realm: The live Maru evaluator running in the host VM, where code exists as manipulable S-expressions and objects.
• The Lower Realm: The target execution environment (slave VM) that will run the compiled output, such as a bare-metal x86 system or an LLVM-backed runtime.

According to the glossary in doc/glossary.md, level-shifting is "aka compilation; a semantics-preserving 'level shift' operation turning s-expressions to machine code." This transformation ensures that every definition in the upper realm has an equivalent, executable representation in the lower realm.

The Two-Phase Pipeline Before Level-Shifting

Before the actual level-shift occurs, Maru processes source code through two distinct compile-time phases defined in doc/compiler.md:

The Expand Phase: Macro Expansion

The expand function performs macro-expansion on source forms, rewriting high-level syntactic sugar into core language constructs.

;; Upper-realm code with a macro
(define-macro inc (x) `(set! ,x (+ ,x 1)))

;; Expand phase rewrites the macro
(expand '(inc counter))
;; Result: (set! counter (+ counter 1))

This phase ensures that the compiler only needs to handle a minimal set of primitive forms when performing the level-shift.

The Encode Phase: Variable Resolution

The encode function resolves all variable references to concrete storage slots and binding environments.

;; Encode phase binds identifiers to locations
(encode '(set! counter (+ counter 1)))
;; Resolves `counter` to its concrete slot in the environment

After encoding, the code is ready for the final level-shift transformation.

How Level-Shifting Emits Target Code

The core of level-shifting is the compile-definition multimethod, declared in source/compiler/emit-early.l and implemented by each backend (x86, LLVM, C). This function translates encoded upper-realm objects into lower-realm artifacts.

Compiling Primitive Types

In source/compiler/emit-x86-late.l, the compile-definition method for <long> emits data labels containing literal values:

;; Upper realm definition
(define my-number <long> 42)

;; Level-shift compilation
(compile-definition <long> 'my-number -c-)
;; Emits: a data label and cell containing the 64-bit integer value
;; in the lower realm's data section

Compiling Functions and Entry Points

For <expr> (function) types, the level-shift generates code labels and export symbols:

;; Upper realm function
(define (main) (print "Hello, Maru!"))

;; Level-shift compilation
(compile-definition <expr> 'main -c-)
;; Generates:
;; - A code label for the function body (closure-code-label)
;; - An export of that label for the target linker
;; - Optional alias for _start or main entry points

The host VM (upper realm) thus generates a complete executable image for the slave VM (lower realm), preserving all semantics while changing the level of abstraction.

Key Source Files for Level-Shifting in Maru

File	Role in Level-Shifting
doc/glossary.md	Formal definition of level-shifting terminology
doc/compiler.md	High-level pipeline description (expand, encode, level-shift)
source/compiler/emit-early.l	Generic compile-definition selector declaration
source/compiler/emit-x86-late.l	x86 backend implementation of level-shifting
source/compiler/emit-llvm.l	LLVM backend implementation
source/types.l	Definitions of high-level types (<long>, <expr>, <array>) subjected to level-shifting

Summary

• Level-shifting is Maru's term for the compilation process that transforms high-level S-expressions (upper realm) into target machine code (lower realm).
• The transformation is semantics-preserving, ensuring equivalent behavior between the host evaluator and the generated runtime.
• The pipeline consists of expand (macro expansion), encode (variable resolution), and compile-definition (target emission).
• The compile-definition multimethod in source/compiler/emit-x86-late.l and related files handles the actual translation of Maru types into lower-realm artifacts.
• Level-shifting enables self-hosting by allowing the Maru compiler running in a host VM to generate standalone executables for a slave VM.

Frequently Asked Questions

What is the difference between level-shifting and traditional compilation?

Traditional compilation typically refers to translating source code to machine code without explicit modeling of the runtime relationship between the compiler and the output. Level-shifting specifically emphasizes the bridge between the upper realm (the live Maru evaluator compiling the code) and the lower realm (the target environment executing the code). It is semantics-preserving by design, ensuring that definitions in the host VM have exact equivalents in the slave VM.

How does Maru handle macro expansion during level-shifting?

Macro expansion occurs in the expand phase, which runs before the actual level-shift. During this phase, the compiler traverses S-expressions and rewrites macro invocations into primitive special forms. For example, a user-defined inc macro expands into a set! expression. This ensures that by the time compile-definition performs the level-shift, it only needs to handle core language constructs, not user-defined syntax.

What target architectures does Maru's level-shifting support?

According to the source code in source/compiler/, Maru implements level-shifting for multiple backends:

• x86/x86-64: Implemented in emit-x86-late.l and related files, generating native machine code.
• LLVM: Implemented in emit-llvm.l, producing LLVM bitcode that can be compiled to various architectures.
• C: A backend that emits C code as an intermediate representation for portability.

Each backend provides its own methods for compile-definition to handle the translation from Maru's upper-realm types to lower-realm artifacts specific to that target.

Why is level-shifting important for self-hosting compilers?

Level-shifting enables bootstrapping by allowing a Maru compiler running in a host environment (upper realm) to generate a complete, standalone executable that runs in a different target environment (lower realm). Without this explicit level distinction, the compiler would produce code that depends on the host's runtime. By level-shifting to a lower realm, Maru can create a slave VM that is independent of the host, allowing the compiler to compile itself and produce a new compiler binary, achieving true self-hosting.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}