Recommended Free Tools
iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
A binary-tree exercise meant to evaluate 1 + 1 + 1 became the starting point for graphLang, a C-based language runtime. The author’s account traces the scope change through a practical sequence: treat operations as functions, add environments for variables, represent user-defined functions as closures, then solve the memory pressure created by evaluation.
Why an arithmetic tree became a language project
The author introduces the project this way: “I was given a data structures problem of converting an arithmetic expression into a binary tree. Naturally, I decided to build an evaluator.” Rather than writing a special evaluator branch for each arithmetic operator, the author reframed operators as functions that accept expressions. That made function application the general mechanism for evaluation—and raised the question of how to support functions beyond built-in arithmetic.
The author characterizes the result as a “Graph Reduction engine.” That is the author’s description of the implementation, not an independent classification or audit of the project.
How the evaluator acquired language features
Operations became function application
In the original assignment, the input was an arithmetic expression represented as a binary tree. By treating operators as functions, the evaluator could apply a function to expression arguments instead of requiring a separate arithmetic-specific rule for every operator.
#1 Best Overall
Variables required an environment
Once expressions could refer to variables, the runtime needed a way to associate names with values. The article describes adding a hash-table environment for that purpose.
User-defined functions became closures
A user-defined function could not just be an opaque C function pointer if it needed to live in the language’s expression graph or be returned and evaluated later. The author therefore describes closures as graph nodes containing function parameters and bodies. This moved functions from being only runtime implementation details to values the language could represent.
Why memory management became part of the project
A fixed arena hit its limit
The first allocator used a fixed arena of 1,024 nodes. In the author’s fib(5) example, the evaluator reportedly generated 13,000 nodes, far beyond that capacity. The article estimates an expression node at 32 bytes on a 64-bit system, before allocator overhead, and says malloc() added 16 bytes on the author’s system. Both are implementation-specific estimates, not universal C or allocator guarantees.
Linked chunks avoided moving live nodes
One way to enlarge an arena is to grow its backing block, but reallocating can move memory and invalidate pointers into it. The author instead changed the allocator to linked chunks, allowing additional capacity without moving existing node targets. With chunk allocation, the author reports fib(5) used 1.32 MB and fib(10) used 40 MB before garbage collection.
Rank #3
Mark-and-sweep reclaimed unreachable nodes
The author reports that fib(40) used more than 12 GB before collection and ended in an out-of-memory crash. The article estimates about 1.3 billion nodes and 62.4 GB of cumulative node allocations at 48 bytes per node. After adding mark-and-sweep collection, the author reports about 1.7 MB for fib(40), with a runtime of six minutes. These figures are the author’s results; they are not independently replicated benchmarks, and they describe this implementation rather than a general performance expectation for graph reduction or garbage collection.
What the repository says graphLang can do
The public graphLang repository describes the project as a minimal, dynamically typed, functional-leaning Lisp dialect and VM. Its README claims a Lisp-style expression syntax, variables, first-class functions, closures, let, a REPL, native-function plugins, lexical scoping, and a tracing mark-and-sweep collector. Those are the project’s own documented claims; they are not an independent review or test of the code.
The README gives make as the build command and includes run examples. It is the best place to consult for the project’s current documented usage and syntax. The development article also mentions a lexer and parser, FFI, REPL, lambda functions, local variables, tail-call optimization, and a Cheney copying collector among future parts or plans. The later README documents some features, but the article alone does not establish which plans were completed at publication.
How to read the project’s claims
The story is useful as a compact example of scope expanding through implementation decisions: a generic function-application evaluator needs environments and first-class functions, while graph-based evaluation creates allocation pressure that eventually makes reclamation important. The memory figures and node counts should be read as the author’s own observations, not a formal performance report. The repository documents the project’s stated features, but these sources do not establish independent replication, broad adoption, or a complete language specification.
Quick Recap
Best Value
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
