From 1+1 to a Functional Programming Language in C
What starts as a seemingly simple data structures assignment to evaluate '1+1+1' using a binary tree can unexpectedly blossom into the creation of a full-fledged functional programming language. This article details the surprising path from that initial problem to implementing features like closures, garbage collection, and custom memory allocators in C.

The Genesis: Evaluating '1+1+1'
The journey began with a standard data structures assignment: represent and evaluate the arithmetic expression '1+1+1' using a binary tree. The core idea was to construct a tree where operators serve as nodes, with their operands as children. Evaluating this tree involves a recursive process: first, evaluate the operands, and then apply the operator. For '1+1+1', this would translate to building a tree with a '+' at the root, its left child another '+' node (with children '1' and '1'), and its right child a '1' node. The evaluator would then need to resolve the inner '+' before summing with the outer '1'.
This straightforward evaluation revealed an interesting insight into how evaluators process operations. Initially, one might represent different arithmetic operations (Add, Sub, Mul, Div) as distinct cases within an expression type. However, upon closer inspection, the core logic of the evaluator doesn't necessarily need to distinguish between 'Add' and 'Sub' beyond their application. Both operations take two expressions and produce a single expression. This observation led to a more generalized representation: an expression is either a value or a function applied to two other expressions.
Introducing Variables and the Need for Hash Tables
The abstraction of expressions to 'Func Expr Expr | Val' proved elegant, but the introduction of variables presented a new challenge. Variables, in essence, are lookups within an environment that yield an expression. This immediately suggested the need for a data structure capable of efficient key-value lookups – a hash table. The realization that C, the chosen implementation language, lacks built-in hash tables meant that this fundamental data structure had to be implemented from scratch. This 'small change' initiated a cascade of further requirements and implementations.
Implementing a hash table in C, even for basic functionality, involves understanding hashing algorithms, collision resolution strategies (like chaining or open addressing), and managing memory for keys and values. The initial thought of a 'tiny addition' quickly ballooned as the implications of supporting dynamic variable environments became apparent. This groundwork laid the foundation for handling more complex language constructs beyond simple arithmetic.
The Memory Footprint of Expressions: Nodes and Allocations
Representing expressions as tree nodes in C, particularly using a tagged union approach with malloc-allocated memory, quickly exposed performance bottlenecks. Each node, composed of pointers for children, data storage (literal, variable name, or function identifier), and a type tag, consumed a significant amount of memory. On a 64-bit system, a node itself might be 32 bytes, but the malloc overhead (e.g., 16 bytes) pushed this to 48 bytes per node. Evaluating a simple expression like '1+1' required three nodes, leading to 144 bytes for just that operation. This overhead becomes prohibitive when dealing with many small, individual allocations for intermediate expressions.
The sheer number of small allocations for nodes suggested a need for more efficient memory management. The standard malloc and free pattern, with its per-allocation overhead and potential for fragmentation, was clearly inadequate. This realization pointed towards a custom memory allocation strategy that could better handle the pattern of creating many short-lived objects, such as expression tree nodes.
Arena Allocation: A Strategy for Node Management
To address the memory allocation overhead, an arena allocator was implemented. The core concept of an arena allocator is to pre-allocate a large contiguous block of memory (the arena) and then dole out chunks from it as needed. Instead of individual malloc calls for each node, a single, large allocation is made at the start. Memory is then managed by a simple pointer that tracks the next available byte within the arena. When the program finishes, or when the arena is no longer needed, the entire block can be freed in a single operation, significantly reducing overhead and eliminating fragmentation within that block.
The implementation involved defining a fixed-size array of nodes to serve as the arena and an index (top) to manage the allocation pointer. A function like allocNode() would simply return a pointer to arena[top++]. This approach dramatically cut down the per-allocation cost and simplified memory management, proving crucial for building and evaluating complex expression trees efficiently.
From C Pointers to First-Class Closures
The journey from evaluating arithmetic to supporting functions and variables naturally led to the concept of closures. Initially, one might consider representing functions as direct pointers to native C functions. However, this approach creates a significant impedance mismatch. User-defined functions, represented as Abstract Syntax Trees (ASTs) within the language, cannot be directly translated into opaque C function pointers. Furthermore, if a function can return another function, that returned function needs to be represented as a structure that the evaluator can understand and later execute, not as an opaque pointer.
This led to the crucial realization that functions must be first-class citizens within the language's representation. A closure, therefore, is not merely a pointer but a data structure that encapsulates both the function's code (as an AST) and its environment. In the context of the expression tree, a closure node would hold its parameter on one side and its body (another expression tree) on the other. This allows functions to be stored, passed around, and evaluated dynamically by the language's own evaluator, rather than being delegated to the host C environment.
Building a REPL and FFI
A key component for any interactive programming language is a Read-Eval-Print Loop (REPL). This allows users to type expressions, have them evaluated, and see the results printed immediately. Implementing a REPL involves parsing user input, feeding it to the evaluator, and then formatting the output. This provides a direct interface for users to interact with the newly created language.
Furthermore, to make the language more practical and extensible, a Foreign Function Interface (FFI) was introduced. An FFI allows code written in the new language to call functions written in another language (in this case, C) and vice versa. This is critical for leveraging existing libraries, performing system-level operations, or integrating with the host environment. Implementing an FFI requires careful management of type conversions and calling conventions between the two languages.
Garbage Collection and Memory Management
With the introduction of closures and dynamically allocated nodes, manual memory management in C becomes a significant burden. Accidental memory leaks or dangling pointers can quickly destabilize the program. To mitigate this, a garbage collector becomes a necessity. For a language built upon expression trees and closures, a tracing garbage collector (like a mark-and-sweep algorithm) is a common choice. The collector periodically traverses the graph of active objects, marking those that are reachable from the program's root set.
The arena allocator, while efficient for certain allocation patterns, doesn't solve the problem of reclaiming memory occupied by objects that are no longer referenced. A garbage collector complements the arena allocator by identifying and reclaiming this garbage, ensuring that the program's memory footprint remains manageable over time, even with complex function structures and recursive data. This requires careful tracking of all live objects and their references.
Where This Approach Does Not Fit
While building a functional programming language from such humble beginnings is a testament to the power of abstraction and incremental development, this approach has limitations. The C implementation, particularly with manual memory management and custom allocators, can be complex and error-prone. The performance of the custom-built garbage collector and allocator might not match highly optimized native solutions for very large-scale applications. Furthermore, the initial motivation was an arithmetic evaluator; extending it to a full-featured general-purpose language involves significant design choices regarding syntax, type systems, error handling, and concurrency.
The focus on expression trees and closures is characteristic of functional languages and interpreters. For applications demanding raw computational speed and minimal abstraction, a compiled language like C or C++ without the overhead of an interpreter and dynamic memory management might be a more appropriate choice. The flexibility gained through closures and dynamic evaluation comes at the cost of predictability and potentially raw performance compared to statically compiled, imperative code. The complexity of the implementation in C also means that the learning curve for developers new to systems programming or language implementation might be steep.
- #C
- #Programming
- #compiler
- #data structures
- #functional programming
- #interpreter



Comments