HigherOrderCO / HigherOrderCO/HVM4
JIT Compiler
- Dominant language
- C
- Stars
- 121
- Forks
- 28
- PR merge metrics
- No merged PRs in 30d
Description
Add a compiled mode that generates C code for defs, builds a single shared
library, loads it, and uses compiled defs when reducing `REF` in WNF.
Use the -c flag to indicate compiled mode. As in `hvm4 main.hvm4 -c".
The compiled C code should perform the WNF of applying the def to the arguments,
so its use in hvm4's WNF would be consistent with its lazy evaluation.
## 1) High-level Flow
1. Parse HVM4 file and build `BOOK` as usual.
2. Generate one C file containing:
- an ABI header
- one C function per def
- a registration function
3. Compile the C file to a `.so`.
4. `dlopen` the `.so` and register compiled defs into a function table.
5. In WNF `REF`, if compiled def exists and its args are saturated (all present), call it;
otherwise fall back to the normal ALO path.
## 2) Runtime Integration Points (Where It Plugs In)
- **REF dispatch:** `clang/wnf/_.c` `case REF:` is the entry point.
- **Book defs:** still stored in `BOOK` for fallback ALO.
- **Runtime ABI:** expose the full surface needed by codegen (see section 6).
## 3) Compiled Def Interface (Draft)
```c
typedef Term (*DefFun)(Term *args, u32 argc);
static DefFun DEF_FUN[BOOK_CAP];
static u32 DEF_ARI[BOOK_CAP]; // number of leading LAMs
```
where:
- argc is the number of arguments in args.
- HVM4 does not encode arity in `REF`, this should be counted from the leading Lams in the definition body; arguments live in APP frames.
- `DEF_ARI[id]` = number of leading LAMs in the static book term for def `id`.
## 4) WNF REF Branch (Draft)
Pseudocode:
```
case REF:
fid = term_ext(next)
if (DEF_FUN[fid] exists) and (stack has >= DEF_ARI[fid] APP frames):
read args from APP frames (right-to-left)
pop frames
next = DEF_FUN[fid](args, argc)
goto enter
else:
current ALO fallback
```
This is a *saturation* check, not a “compiled vs interpreted” branch.
So, the fallback case lets the program continue when the function is
only partially applied (i.e. not all of its args are present).
Fallback: if not saturated or no compiled def, use the existing ALO path
unchanged (partial applications behave as today).
## 5) Generated C File Contents
Single translation unit containing:
- `typedef` for the ABI (see below)
- all compiled def functions `def_(...)`
- `void hvm4_register(const Hvm4Api *api, DefFun *out, u32 *ari)`
- stores `API` pointer
- installs function pointers and arities
- the compiled C functions call the hvm4 functions as `API->heap_alloc` etc
## 6) Runtime ABI (Full; for Compiled Reductions)
The ABI must expose *everything* codegen may call when it performs real
reductions. To avoid omissions, define the ABI as “all functions in these
runtime modules” (file path = function name):
- **Heap + substitution:** all functions in `clang/heap/*.c`
- includes `heap_alloc/read/set/take`, `heap_subst_var`, `heap_subst_cop`
- **Term core + constructors:** all functions in `clang/term/*.c` and
`clang/term/new/*.c`
- includes `term_new`, `term_tag/ext/val/arity`, `term_sub_get/set`,
and all `term_new_*` constructors
- **WNF entrypoints:** `wnf`, `wnf_pri`, `wnf_uns`
- **Interaction helpers:** all `wnf_*` helpers in `clang/wnf/*.c`
- by naming rule, each `clang/wnf/foo_bar.c` exports `wnf_foo_bar`
- **Counters/labels:** add exported helpers for interaction counting and
fresh dup labels (e.g., `itrs_add(n)`, `fresh()`)
- **Constants header:** tags/op codes/bit masks shared between runtime and
generated C
Implementation note: because compiled code is in a `.so`, it must operate on
the main runtime’s globals. That is why we export the runtime surface instead
of embedding `hvm4.c` in the `.so`.
Small ABI sample (bootstrap only; not enough for compiled reductions):
```c
typedef struct {
u64 (*heap_alloc)(u64 size);
Term (*heap_read)(u32 loc);
void (*heap_set)(u32 loc, Term t);
Term (*term_new)(u8 tag, u32 ext, u32 val);
Term (*term_new_num)(u32 n);
Term (*term_new_op2)(u32 opr, Term x, Term y);
u8 (*term_tag)(Term t);
u32 (*term_val)(Term t);
u32 (*term_ext)(Term t);
Term (*wnf)(Term t);
Term (*wnf_pri)(Term t);
Term (*wnf_uns)(Term t);
Term (*wnf_app_lam)(Term lam, Term arg);
} Hvm4Api;
```
## 7) Codegen Strategy (Initial)
Start small and correct:
- Emit C that constructs the def body with args substituted.
- Only a few core nodes at first (NUM, APP, LAM, OP2, REF, DUP, SUP).
- No “fast path” optimizations yet; ensure semantic parity.
- Compiled defs return **WNF**, not full normalization.
Example (compiled `@add = λa. λb. (a + b)`):
```c
Term add_f(Term *args, u32 argc) {
Term a = args[0];
Term b = args[1];
if (term_tag(a) == NUM && term_tag(b) == NUM) {
return term_new_num(term_val(a) + term_val(b));
}
return term_new_op2(OP_ADD, a, b);
}
```
Later:
- Inline numeric matches and OP2.
- Tail-call loops for self-recursive defs.
- Skip node construction when possible.
## 8) Build/Load Pipeline (Draft)
- Generate `.build/.c`.
- Compile: `cc -O2 -fPIC -shared .c -o .so`
- `dlopen` + `dlsym("hvm4_register")` + call it.
- Store `DEF_FUN`/`DEF_ARI` in runtime globals.
## 9) Higher-Order Functions (Current Approach)
Arity will be derived from *leading LAMs*. That means compiled defs only fire
when saturated. For higher-order results, we can manually structure code to
have the intended arity by using a let to return a lambda. Example:
```
@f = λa. !v = λb. c; v
```
This makes `@f` have arity 1 (one leading LAM), and the compiled def can return
the lambda as a normal term. Later, a small non-looping (non derefing) normalization before
codegen could eliminate the extra app/let overhead if we decide to go that far.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.