Making Reduct (previously SCON), a language for scripting and configuration within PatchworkOS, and accidentally faster than Lua, now available as its own project.

[KaiNorberg]

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!

[twh270]

I have no opinion on most of this as I haven't looked in detail, though at first glance it looks reasonable. Handles and tries look good. (There might be an optimization opportunity for special-casing short lists, I dunno.) And kinda impressive to do all of it in a header library.

But... I don't get the infix syntax on Reduct. You're adding a completely new notation (infix) which means a new tokenizer/parser, you lose some of lisp's core features (homoiconicity, everything-is-a-list), it's additional syntax you have to maintain, and it's something extra for the user to have to learn. All to get rid of some parentheses aka deep nesting. (Which I acknowledge is a worthy goal.)

Admittedly I don't know the background reasoning for your decision, so I might well be missing something obvious. But, I'd like to offer a suggestion: let newlines be significant whitespace. I propose two possible syntaxes, both of which compile in my head (in other words, fair warning...):

Option A

Both bindings and expressions can be newline-delimited. Expressions must be enclosed by parens.

do
  x 10
  y 20
  z (+ x y)
  (* z 2)

An equivalent to the above:

do
  (x 10) (y 20) (z (+ x y))
  (* z 2)

Option B

Both bindings and expressions can be newline-delimited. Bindings use = operator, which means expressions and bindings have the same grammar.

do
  = x 10
  = y 20
  = z (+ x y)
  * z 2

An equivalent to the above:

do
  = x 10
  = y 20
  = z
    + x y
  * z 2

(BTW I have no idea what the do keyword does, it's in your example but I didn't see it in the grammar.)

Both of these styles still support parentheses so you can write e.g. (do (x 10) (y 20) (z (+ x y)) (* z 2)). This becomes valuable when reading/writing S-exp's as data. A programmer writing code will ensure the syntax of the code is valid either with or without using newlines as delimiters, but some external data might not use newlines at all. But as as long as each S-exp is enclosed by parentheses we're good.

You lose a lot of parens, keep the simplicity of the grammar, keep homoiconicity.

Any of this resonate with you?

[KaiNorberg]

Well, I have seen some others discuss the usage of significant whitespace for Lisp-like languages (Sweet Expressions being the big one), which seems to be the main thing you're suggesting?

It really is a matter of taste, but I am firmly on the "significant whitespace bad" side of that argument for the usual reasons.

Actually, one of the reasons I chose to implement infix notation is actually because of how simple it was to implement. It only takes around 100 lines of the parse_impl.h file to expand the infix notation into prefix notation. 

So it's not a maintenance burden, nor do we really lose any homoiconicity since internally, infix notation just becomes prefix notation. 

For some programs, the Mandelbrot benchmark being a good example, the infix notation makes a huge difference. 

[twh270]

Fair 'nough. I am normally against significant whitespace -- but IMO the worst problems are when spaces/tabs become significant. My suggestion to make only newlines significant is an attempt to mitigate that.

I should have realized you'd just transform the infix to prefix haha.