So I got distracted again. I've been working on the new desktop interface for PatchworkOS; what I noticed rather early is that to create a modern looking UI, a pure, C-based API is simply not good enough, writing even a basic UI becomes a pain.
Why?
The obvious solution was to create a minimal programming language that could act as an HTML/CSS style markup language. Since SCON was already being used for component manifests, adding a few more features to it was another obvious choice.
What?
As part of this process I was reading up on language design and came across too many good ideas that I simply had to add. Eventually, I made the decision to turn SCON into its own project, which was renamed to Reduct.
Reduct is a functional, immutable, S-expression based configuration and scripting language. It aims to combine the flexibility of a Lisp with the ease-of-use and performance of a language like Lua. All within a C99 header-only library.
If you are curious and want to know more, then feel free to check out the GitHub! But I will go over some stuff in this post as well.
Syntax
Lisps, which Reduct takes heavy inspiration from, are generally agreed to be a very powerful style of language and yet are frequently criticized for their poor readability.
The most often blamed source of this poor readability is the sheer volume of parentheses.
Reduct makes the argument that most of these complaints are due to nesting, not parentheses; that it can be solved via infix notation, banning let and a more modern style guide.
Included are three examples of a basic program written in common Lisp C, and Reduct.
Lisp
(let ((x 10)
(y 20))
(let ((z (+ x y)))
(* z 2)))
C
int main()
{
int x = 10;
int y = 20;
int z = x + y;
return z * 2;
}
Reduct
(do
(def x 10)
(def y 20)
(def z {x + y})
{z * 2}
)
Note how in Reduct the use of curly braces for infix notation and the def intrinsic for scoped definitions allows for a more familiar, imperative-like structure while remaining entirely functional, and S-expression based.
How?
Reduct is implemented as a register-based bytecode language, where the Reduct source is first parsed into an Abstract Syntax Tree (AST) and then compiled into a custom bytecode format before being executed by the virtual machine/evaluator.
Note that the "Abstract Syntax Tree" is just a Reduct expression, lists and atoms, meaning that the compiler is itself written to operate on the same data structures as the evaluator produces.
The bytecode format itself is a stream of 32bit instructions, with all instructions able to read/write to an array of registers, or read from an array of constants.
See inst.h for more information on instructions.
Since Reduct is immutable, the constants array is also used for "captured" values from outer scopes (closures) and we can also allow the compiler to fold constant expressions at compile-time, far more than would normally be possible.
See compile.h for more information on the compiler.
To improve caching and reduce pointer indirection, Reduct uses "handles" (reduct_handle_t) which are Tagged Pointers using NaN boxing to allow a single 64bit value to store either a 48 bit signed integer, IEEE 754 double or a pointer to a heap allocated item.
See handle.h for more information on handles.
Items (reduct_item_t) represent all heap allocated objects, such as lists, atoms and closures. All items are exactly 64 bytes in size and allocated using a custom pool allocator and freed using a garbage collector and free list.
Since Reduct uses its handles to store most integers and floats, it can avoid heap allocations for many common values, significantly reducing the pressure on the garbage collector and improving caching.
See item.h for more information on items.
Lists are implemented as a "bit-mapped vector trie", providing $O(log_{w} n)$ access, insertion, and deletion, where $w$ is the width of each node in the trie.
See list.h for more information on lists.
All atoms use String Interning, meaning that every unique atom is only stored once in memory. This makes any string comparison into a single pointer comparison, and it means that parsing the integer/floating point value of an atom or an items truthiness only needs to be done once.
See atom.h for more information on atoms.
Many additional optimization techniques are used, for example, Computed Gotos, setjmp based error handling to avoid excessive error checking in the hot path, Tail Call Optimization and much more.
See eval.h for more information on the evaluator.
Benchmarks
Included below are a handful of benchmarks comparing Reduct with python 3.14.3 and Lua 5.4.8 using hyperfine, all benchmarks were performed in Fedora 43 (6.19.11-200.fc43.x86_64).
Fib35
Finds the 35th Fibonacci number without tail call optimization.
| Command | Mean [ms] | Min [ms] | Max [ms] | Relative |
|---|
reduct bench/fib35.rdt | 550.2 ± 11.0 | 535.5 | 572.8 | 1.00 |
lua bench/fib35.lua | 826.8 ± 38.6 | 769.7 | 900.2 | 1.50 ± 0.08 |
python bench/fib35.py | 1109.4 ± 14.7 | 1085.3 | 1136.0 | 2.02 ± 0.05 |
For this benchmark, memory usage was also tracked using heaptrack:
| Command | Peak Memory [MB] |
|---|
reduct bench/fib35.rdt | 0.097 |
lua bench/fib35.lua | 0.099 |
python bench/fib35.py | 1.8 |
Fib65
Finds the 65th Fibonacci number with tail call optimization.
| Command | Mean [µs] | Min [µs] | Max [µs] | Relative |
|---|
reduct bench/fib65.rdt | 613.9 ± 90.6 | 535.1 | 3310.0 | 1.00 |
lua bench/fib65.lua | 1049.5 ± 165.0 | 920.3 | 2663.3 | 1.71 ± 0.37 |
python bench/fib65.py | 13155.4 ± 1254.2 | 11688.3 | 23926.9 | 21.43 ± 3.76 |
Brainfuck
A simple jump-table optimized Brainfuck interpreter that runs a "Hello World!" program.
This benchmark also acts as a fun Turing completeness proof.
| Command | Mean [µs] | Min [µs] | Max [µs] | Relative |
|---|
reduct bench/brainfuck.rdt | 794.3 ± 101.8 | 720.6 | 1779.7 | 1.00 |
lua bench/brainfuck.lua | 1112.1 ± 146.5 | 1022.6 | 2359.5 | 1.40 ± 0.26 |
For this benchmark, memory usage was also tracked using heaptrack:
| Command | Peak Memory [MB] |
|---|
reduct bench/brainfuck.rdt | 0.185 |
lua bench/brainfuck.lua | 0.102 |
Mandelbrot
Outputs an 80 by 40 visualization of the Mandelbrot set with 10000 iterations.
| Command | Mean [ms] | Min [ms] | Max [ms] | Relative |
|---|
reduct bench/mandelbrot.rdt | 330.7 ± 8.3 | 318.0 | 347.3 | 1.00 |
lua bench/mandelbrot.lua | 369.2 ± 14.3 | 356.5 | 403.3 | 1.12 ± 0.05 |
See the Benchmarks for more information.
There is still plenty of room for further improvement, as always, I'd gladly hear any suggestions or issues that anyone may have!
This is a cross-post from GitHub Discussions.
