# GPU Lambda Execution — Architecture Notes

## Path to Hyper-Lambdas

### Phase 1: Map/Reduce on GPU (immediate)
- `(map f list)` where f is pure → one CUDA thread per element
- `(fold-left + 0 list)` → tree-based parallel reduction in shared memory
- NaN-boxed values work natively as CUDA `uint64_t`
- Pre-allocate memory pools (no malloc in kernels)

### Phase 2: Trampolining for Recursive Lambdas
- Convert recursive calls to thunks (unevaluated computations)
- GPU kernel loops over thunks instead of recursing
- Eliminates stack overflow risk on GPU
- Each CUDA thread processes one thunk chain

### Phase 3: Interaction Combinators (Bend/HVM approach)
- Lambda terms → interaction net graphs
- Rewrite agents in parallel across CUDA cores
- 74,000 MIPS on RTX 4090 demonstrated by HVM2
- Requires compilation to intermediate representation

## Key Design Decisions
- Keep NaN-boxing (native CUDA uint64_t)
- Memory pools for cons cells (atomicDec on free list)
- Closures as flat struct: {code_id, env_ptr, env_size}
- Environments as flat arrays (better memory coalescing)
- Warp size 32, block size 256, grid = (N+255)/256

## References
- Bend/HVM: github.com/HigherOrderCO/Bend
- cl-cuda: github.com/takagi/cl-cuda
- Harlan (Scheme→OpenCL): github.com/eholk/harlan
- Futhark (functional GPU): futhark-lang.org
