Layer 4 – Bootstrapping

[Mathnerd314]

Desired function
Provide a principled, library-level API for producing compilers, residual programs, generating extensions, compiler generators, runners, and bundled executables from within the language. arxiv

Futamura role
Implements the full Futamura stack around (i), (s), (c).

Inputs

• Interpreter program (i).
• Specializer (s) (2.2).
• Compiler pipeline (c) (2.3+2.4+2.5+2.6).
• User programs (p).

Processing

• Define:
  • (p_x = \mathrm{run}(s,(p,x))).
  • (g_p): (\mathrm{run}(g_p,x) = p_x).
  • (n): (\mathrm{run}(\mathrm{run}(\mathrm{run}(n,p),x),y) = \mathrm{run}(p,(x,y))). ecommons.udayton
  • Runner (r): (\mathrm{run}(\mathrm{run}(r,c),(p,x)) = \mathrm{run}(\mathrm{run}(c,p),x)).
  • Bundler (b): (\mathrm{run}(b(c,p),x) = \mathrm{run}(\mathrm{run}(c,p),x)).
• Expose them as library APIs.

Outputs

• Library functions for:
  • Compiling programs.
  • Specializing programs.
  • Generating compilers and generators.
  • Creating bundled executables.

Key references

• Diagrammatic and practical presentations of Futamura projections. blog.sigfpe

Let ( \mathrm{run} : \text{Program} \times \text{Data} \to \text{Result} ) be the master evaluator.

Classic Futamura artifacts (concrete semantics): ecommons.udayton

• Interpreter (i): program implementing run such that (\mathrm{run}(i,(p,d)) = \mathrm{run}(p,d)).
• Specializer (s): partial evaluator: (\mathrm{run}(\mathrm{run}(s,(p,x)),y) = \mathrm{run}(p,(x,y))).
• Compiler (c): specialization of (i) w.r.t. programs: (\mathrm{run}(\mathrm{run}(c,p),d) = \mathrm{run}(p,d)). ar5iv.labs.arxiv
• Residual program (p_x): (\mathrm{run}(p_x,y)=\mathrm{run}(p,(x,y))).
• Generating extension (g_p): (\mathrm{run}(g_p,x)=p_x). arxiv
• GNG (n): (\mathrm{run}(\mathrm{run}(\mathrm{run}(n,p),x),y) = \mathrm{run}(p,(x,y))). ecommons.udayton

Your runner and bundler are packaging around (c) (and (p)), not new projections; they’re included as higher-level artifacts.

On the verification side, there is an abstract interpreter (\mathrm{run}^\sharp) for properties, which fits the same pattern at the abstract level. pcousot.github

The toolchain bootstraps itself in stages:

4.1 Python Interpreter + P-Code Machine (Stage 0 Seed)

Function: The Stroscot interpreter written in Python combined with the P-code machine interprets the host-based compilation system, producing a slow but usable compilation and partial evaluation system.

---

4.2 Self-Applied Partial Evaluator (Stage 1)

Function: The interpreter-based PE system is applied to itself, producing an optimized PE system targeted for the host. Implements the second Futamura projection applied to the seed.

---

4.3 Generating Extension Generator (Stage 2)

Function: The optimized PE system is used as a generating extension generator and applied to a Stroscot interpreter written in Stroscot as the source program, generating the final host-system toolchain supporting all language features.