Developer builds functional programming language in C for data structures assignment

Origin of the Project

The project began as a data structures assignment requiring the conversion and evaluation of an arithmetic expression, such as '1 + 1 + 1', into a binary tree. The initial goal was to evaluate this tree to its numerical result.

Evolution of the Evaluator

The developer's approach to the assignment quickly expanded beyond a basic evaluator. Over several days, the project grew to include the implementation of closures, a garbage collector, a custom memory allocator, a Read-Eval-Print Loop (REPL), and a Foreign Function Interface (FFI), all written in C.

Rethinking Expression Representation

Initially, different arithmetic operations (Add, Sub, Mul, Div) were distinct cases within the expression type. The developer realized that the evaluator did not need to differentiate between these operations, only how to apply a function. This led to a simplified expression representation using 'Func Expr Expr' and 'Val'.

Adding Variables and Data Structures

The need for variables prompted the implementation of a hash table in C, as it lacked built-in support. This addition allowed for the inclusion of 'Var' in the expression type, enabling variables to be passed to functions once evaluated, similar to how numeric literals are handled.

Implementation Details in C

The core implementation in C utilized a tagged union to represent different expression types, such as LITERAL, VAR, and FUNC. This structure facilitated the development of the functional programming language's features.