0.2 Graph-Based Optimal Reduction Engine and IR

[Mathnerd314]

Goal: Represent the program as a mathematical function over the P-code machine, serving as the concrete implementation of the semantic core of the Stroscot language interpreter. This defines the "specification" of behavior when combined with the P-code machine. All projections specialize/compile this semantics; they don’t replace it.

Implementation: Execute and transform programs represented as graphs with explicit sharing and duplication control (Lamping-style, linear logic). Supports sea-of-nodes, SSA, traced paths.

Inputs

• Graph IR: nodes as combinators/primitives; edges for data/control; labels and boxes for sharing/duplication.
  • Flexible/extensible IR: combination of sea-of-node, SSA, traced paths, etc. - lived observation is "IR's don't have to be clean, they can be as messy as you want. they just have to express everything you want to express"
• Reduction rules (beta-reduction, primitive operations, control constructs).
• Parsed AST with lexical scopes and imports, poset-style declaration constraints.
• Optional annotations for CPS/join points.

Processing

• Maintain bidirectional, locally-nameless graph with named “chunks” for modularity.
• Use label-based hash-consing to detect/share common subgraphs.
• Apply linear-logic-style rules (boxes, contraction/weakening) to control duplication and garbage.
• Support modes: “active” interpreter-style nodes vs. “frozen” compiled representation.
• Optionally perform local normalization/cleanup (e.g., trivial join simplification, small CSE).

Outputs

• Reduced graph (normal form or partially reduced with suspended redexes).
• fully resolved IR with symbol IDs
• diagnostics for unresolved names or incoherent poset constraints.
• Metrics: sharing statistics, duplication counts, reduction logs (for profiling).

Key references

• Optimal reduction & sharing (Lamping, etc.).
• GHC supercombinators (Peyton Jones)

[Mathnerd314]

From #7 - decided to use VEX-like IR as internal assembly representation.
So for inline assembly / FFI stubs, we need to:

• Decode/decompile using pyvex lifter
• Translate VEX IR to internal IR
• Code generation (3.3.3. Unison-Style Global Code Generator (Compiler Core) #29 fast path)
• Run using native runtime of 0.1 Native Dispatch Runtime #7

To clarify how the FFI bindings work, as previous reference to https://github.com/aguinet/dragonffi was unclear:

• we take the FFI call in Stroscot - angle_radians = DO_CPP_FFI { ${angle_degrees} * (std::numbers::pi_v<float> / 180.0f) } or whatever syntax
• we generate a C stub function using a known calling convention (e.g. pure-memory C structs in this example):

extern "C" {
StroscotResultXXX func(StroscotArgsXXX args) {
  // unpack args - automatically generated code
  float angle_degrees = args.arg0;

  // arbitrary C or C++ from FFI user code - can use full capabilities and syntax since it's compiled by gcc/clang
  float angle_radians = angle_degrees * (std::numbers::pi_v<float> / 180.0f)
  // ... could do more stuff here

  // pack up args - also automatically generated code
  StroscotResultXXX retval;
  retval.a = angle_radians;
  return retval;
}
}

• we compile the C stub file to assembly or machine code using gcc/clang
• we take the assembly / machine code and decompile it to Stroscot internal IR
• we optimize it - if we're lucky it optimizes away completely, like here we would probably just get some arithmetic operations

This is why assembly "importing" is an essential component of the IR. And it is this messy 3-way interaction:

• the native runtime must know about calling conventions and how to generate/use trampoline shims to fix calling convention mismatches
• the IR must encode de-compiled assembly and in particular calls to non-inlined object-level libraries
• the code generator must assign calling conventions to IR code, and know how to inline/optimize trampolines

[Mathnerd314]

Paper references from #3: https://github.com/cryptiumlabs/juvix/issues/296#issue-545367326

so there are two noteworthy things:

• linear logic structures do have a direct interpreter semantics / compilation to machine code, see paper The Machinery of Interaction, Accattoli et al link and earlier citations Mackie 1995, based on a token-passing semantics - we sort of walk around the tree and at each step decide what to do, and each decision can be written directly as a machine code basic block / interpreter case
• optimal reduction is about reducing proof nets, so it is about optimizing linear logic structures. In the best case we can reduce the structure to a single constant, but in practice this is unlikely - the general case of optimal reduction is actually a careful restructuring of the linear logic graph to share families of computations via boxes and only evaluate them once. So therefore, optimal reduction and sharing actually falls under 3.3 Optimizing Compiler #26. It is conceptually related to CSE optimization.

[Mathnerd314]

So this suggests revising the plan in #11 (comment), we will implement a direct interpreter in Python rather than the full code generator. This follows the approach in Simple, they have an interpreter ("evaluator") starting Chapter 10 whereas code generation (#29) is later, chapters 19-21.