Compiling a Functional Programming Language Using Combinators
Sumaia Aktar · Brock University Digital Repository (Brock University) · 2025
Our work explores functional programming (FP), a paradigm grounded in lambda calculus and term rewriting that emphasizes immutability and pure functions, ensuring consistent outputs without side effects. We design and implement a strongly typed functional language that leverages FP principles to create robust, reliable code with inherent type safety. Our approach involves translating functional programs into a combinator language that bypasses variables and substitution. The combinators serve as higher-order constructs, transforming lambda terms into variable-free expressions to streamline execution. Subsequently, we develop a custom abstract machine specifically designed to execute combinator instructions, implemented in both Java and x86 assembler to generate an executable version that can run on actual hardware. By bridging high-level functional constructs with low-level executable code, this thesis demonstrates a clear pathway from functional programming concepts to practical machine-level computation including lazy and eager evaluation of language constructs. It highlights the efficiency and reliability of FP principles while laying the groundwork for future advancements in functional programming-based processors.