Optimization in a Combinator-Based Compiler for a Functional Programming Language
Antwi Kwaku Robert · Brock University Digital Repository (Brock University) · 2026
Functional programming (FP), rooted in the lambda calculus, enables concise, modu- lar, and declarative programs through immutable data, pure functions, and referential transparency. These properties support clearer reasoning, improved testability, and stronger correctness guarantees. Yet a persistent implementation challenge remains: high-level lambda abstractions are elegant, but not directly suited to efficient low-level execution. Our work investigates combinator-based compilation as a practical route from typed functional source programs to native code. The central idea is to eliminate variables by translating source terms into combinator expressions. A variable-free target simplifies execution by avoiding the management of environments and substi- tution at runtime. However, a naive combinator translation based only on the classical SKI basis can expand terms dramatically and introduce redundant computation. To study this problem concretely, we design and implement Kavah, a statically typed functional language supporting higher-order functions, algebraic data types, pattern matching, recursion, primitive arithmetic and boolean operations, and syn- tactic conveniences such as sections. We develop a Java compiler for Kavah that parses complete programs, checks them using a unification-based type system, and lowers them through Scott encoding and an intermediate representation into a combinator language. The translation uses bracket abstraction and an extended basis including B, C, W, Y, and C∗, together with source-level and combinator-level optimizations. One major contribution is the architecture that coordinates established optimiza- tion techniques across source-level, abstraction-elimination, and combinator-level rep- resentations. Before lambda elimination, the compiler performs common subexpres- sion elimination to preserve source-level sharing. After translation, it applies function inlining, algebraic simplification of combinator expressions, and partial evaluation of constant and pattern-driven computations. These passes reduce unnecessary combi- nator growth, expose opportunities for compile-time computation, and significantly improve the quality of the generated target terms. Finally, the optimized combinator program is lowered to a small abstract-machine style backend that emits x86 assembly and produces native executables. By con- necting a rich typed source language, an optimized combinator translation, and a concrete machine-code backend, our work demonstrates that combinator compila- tion can serve not merely as a theoretical curiosity, but as a viable and transparent compilation strategy for functional languages.