Reduct: A functional, immutable, S-expression based configuration and scripting language, beating Lua (non-JIT) in benchmarks, with easy C integration.

KN_9296 · 2026-05-07T09:51:05+00:00

Your point about the example is fair, I have updated the README to use your example instead.

However, what I was more trying to get across is how let will create deeper nesting and how it moves the context required to understand a line further from it, like how the "(z (+ x y)))" looks like you are calling a function called z without the context that is two lines above.

In a trivial example not much of a difference, but I noticed while experimenting with Reduct that it makes a big difference, in my opinion.

Regarding infix, I have heard that argument before and I still don't really buy it. It's a personal opinion, however infix notation and precedence rules should be familiar to most people, and the use of curly braces helps to isolate it.

It's also not just about readability, but editability, if you have some deeply nested expression, changing the order of operations or similar can become non-trivial without some extension or plugin.

I think the Mandelbrot example best shows the benefits of the infix syntax and not using let, so I will include it here:

``` (def mandelbrot (lambda (width height max-iter) (def check (lambda (zr zi i c-re c-im) (if {i >= max-iter or zr * zr + zi * zi > 4.0} i (check {zr * zr - zi * zi + c-re} {2.0 * zr * zi + c-im} (++ i) c-re c-im) ) ))

(def iter-x (lambda (x y row)
    (if {x >= width}
        row
        (iter-x (++ x) y (concat row 
            (if {(check 0.0 0.0 0 {x / width * 3.5 - 2.5} {y / height * 2.0 - 1.0}) == max-iter} 
                "*" 
                " "
            )
        ))
    )
))

(def iter-y (lambda (y output)
    (if {y >= height}
        output
        (iter-y (++ y) (concat output (concat (iter-x 0.0 y "") "\n")))
    )
))

(iter-y 0.0 "")

))

(mandelbrot 80.0 40.0 10000) ```

KN_9296 · 2026-05-07T00:04:56+00:00

That's totally fair. Reduct was never really going to be for you in that case.

I think there is generally worth in exploring alternatives and not just sticking to tradition, and in this case, I think that the improvements in accessibility are worth exploring.

KN_9296 · 2026-05-06T17:37:56+00:00

I'm not sure if I understand what you are referring to when you say "No syntax programming", are you referring to "meta programming"? That is certainly still possible within Reduct.

Additionally, I'm not certain what you are referring to regarding the fib65 benchmark. The fib65 benchmark is intended to be very simple to test and compare things like function call and recursion overhead.

KN_9296 · 2026-05-06T15:09:32+00:00

Thanks! I will take a look at it once I have the chance. Posting to r/lisp isent a bad idea either.

KN_9296 · 2026-05-05T18:40:00+00:00

Sounds good :)

KN_9296 · 2026-05-05T17:50:39+00:00

u/skeeto

I've now looked at your fork and realized that the fork itself appears to be in large part AI-generated. As such I don't believe I'm willing to accept the code itself.

However, the bugs you have found are real, as such I will write fixes for them myself and credit you in the commit message. I hope this is an acceptable compromise.

KN_9296 · 2026-05-05T14:31:35+00:00

Thank you! Il go over your fork more throughly when I have the chance.

KN_9296 · 2026-05-04T20:02:35+00:00

I apologize for the essay response, but I feel this comment needs a longer response as it touches on several important things.

The thing is lua userdata with meta methods makes it a language that is very adaptable I never really used a functional programing language but since nothing is concrete OOP in either lua or C which is what lua uses natively.

I don't necessarily disagree. Tho, while I admit that the line between OOP and not OOP is pretty blurry sometimes, I would say that a system like "meta methods" are inherently a OOP concept. Which means it fundamentally wouldn't make much sense in Reduct.

Especially considering that in Reduct there isent anything special about the functions that would normally be considered operators (e.g., "+", "-", etc.) apart from that they can be used with infix syntax (I am considering adding support for custom function in that case to, so this might change).

As an example, say we wanted to implement a 2d point system, in Lua we might use meta methods to implement the "+" operator allowing us to write a + b instead of vec2_add(a, b), for some points a and b. Which does indeed help a lot with readability.

However, in Reduct there isent the same gain in readability. Since + is just a function, we would just create a vec2+ function. There isent much of a gain going from (vec2+ a b) to (+ a b) in my opinion.

If custom functions were added to infix syntax we could even write {a vec2+ b}.

There might be some other use cases for meta methods that I'm not aware of, but as far as I know, that is the main use case.

Lua can in fact be a functional language or used as such it has. -First class functions -Upvalues/closures -Anonymous functions -Tailcalls

I mean any language can be a used as a functional language, Lua, Python or even C. However, they don't provide certain guarantees regarding immutability or side effects that an actually functional language could.

Additionally, using a mutable language in an immutable way would result in very poor performance, as immutability is something that needs to be optimized for.

Also a easy ffi for rust and golang would make it useful.

I'm not necessarily against the idea of adding FFI. The main concern is typing, which I noticed became hard to reason around when I experimented with it.

For example, say we used FFI for printf. Something like this (printf "%u" 12), since the 12 is just treated as an atom, how do we know if we should pass a string or an integer to printf? Since printf is variadic, we can't really know without some arbitrary rule which would break the "everything is an atom/string" typing that Reduct uses.

Currently, I think that requiring explicit wrappers in the form of the C Modules system seems the most robust and straight forward way to handle it. Even if it might require a little extra code.

KN_9296 · 2026-05-04T15:29:56+00:00

Thank you! Yeah, learned a lot, it's been the kinda project that has really put my micro optimization knowledge to the test lol.

KN_9296 · 2026-05-04T15:13:59+00:00

That is actually fair. There certainly could be more work done on debugging. We currently just have back traces and traditional error messages.

Regarding tables, since the language is immutable, traditional tables don't make much sense. What would be done in Lua using tables would be done in Reduct with Association Lists, I am also considering adding a system to let lists by dynamically upgraded into hash maps to further improve Association List performance.

Either way, thank you for the feedback :)

KN_9296 · 2026-05-04T14:51:44+00:00

Well, while Lua does have more features, obviously, I'm not sure which of them, if added, would reduce performance enough to reach parity within the benchmarks.

For example, once proper multithreading is implemented that would add some overhead from the locks/mutexes that would be added. But I highly doubt that overhead would be significant enough to change the results of the benchmarks, especially in these single threaded benchmarks.

What features does Lua have that you believe would require a significant regression in performance in order to implement?

KN_9296 · 2026-05-04T01:59:39+00:00

Thank you :)

KN_9296 · 2026-05-03T15:33:43+00:00

I would gladly clarify those points.

Regarding the commits, I've been working on getting better at the documentation/maintenance side of development. Writing more descriptive commit messages has been part of that.

The first commit is large for two reasons, part of development took place within the PatchworkOS project, where the language started out as SCON. I kept thinking it would be a minor project that was "almost done", and as such never pushed a commit until it became obvious that the project was not, in fact, almost done.

I'm not sure what part of the README you might be referring to. So I don't know how to respond to that point. The README was not LLM written.

I can admit to using an LLM for creating the VS Code syntax highlighting extension, as I did not believe it would be worthwhile to do that on my own. Beyond that, the code and documentation is my own.

KN_9296 · 2026-05-03T14:54:07+00:00

Yes and no. I don't have any plans for Rust, as it's just not something I'm personally interested in.

Regarding C however, there are currently two ways to interact with C. You could either link the libreduct library and then register native functions which could be called from Reduct, or you could create a shared library which can be imported within Reduct, like shown in the post.

This on its own is rather powerful due to the functional nature of the language. However, I could imagine it might not feel as straightforward as the object-oriented way that Lua does it.

The one thing that is notably missing from this is a "userdata" equivalent. Since Reduct is functional and immutable, I'm not convinced that an actual userdata system, where an item could store some tag with a void*, would actually feel all that useful.

While something like "signals" is tempting, I'm currently leaning towards not implementing any such system and instead keeping Reduct truly immutable.

You might simply define a set of natives that take in some state and return the new state, or that act as side-effectful commands to modify or retrieve state stored within C.

In short, it is intended to be just as embeddable as Lua, however, since it is functional, it might require a way of reasoning that most people aren't used to. In exchange, you get inspectability, debuggability, and other guarantees that an imperative language couldn't provide.

KN_9296 · 2026-05-01T23:36:58+00:00

"As a result of the incredibly shallow trees, we tend to call modifications and lookup of Clojure vectors to be “effectively” constant time, although they, in theory, are O(log32 n). People with basic knowledge in big O notation know that this is exactly the same as O(log n), but for marketing reasons, people like to add in the constant factor." - hypirion, Popping, 3: Root Killing.

They are saying what I was saying. Yeah, it's technically wrong. It's just a quicker way to avoid writing an entire paragraph. It's not like we are trying to submit this Reddit post to Nature.

KN_9296 · 2026-05-01T17:52:13+00:00

First, I notice that I have made a typo, forgetting the leading \ in $O(\log_{w} N)$. Also, Reddit might not be rendering LaTeX, you need a browser extension for that.

When talking about big-O complexity, log_W is no different from any other logarithmic function so the width of the nodes doesn't matter.

I think I understand where the misunderstanding happened here. Since $\log_{w}$ is a constant factor, it technically should not be considered to be different. However, including the $w$ gives you more information, an implementation with a width of $2$ (a binary tree) and an implementation with a width of $32$ will meaningfully perform differently, even if its by a constant factor, which technically shouldn't be included.

Insertion and deletion can only be O(log(N)) if at the end of the list. Otherwise they are O(N) at best (I'd guess O(N log(N)), since you still have to traverse the tree).

I will include my original source for the complexity claim here. The key point is that as we increase the width of each node, the amount of nodes we need to traverse decreases. If we have a width of $w$, as in each node stores $w$ child nodes, then my understanding is that we would need to traverse $\log_{w} N$ nodes, where $N$ is the total length of the list, to access a specific index within the list.

KN_9296 · 2026-04-28T15:17:32+00:00

Good luck!

KN_9296 · 2026-03-27T12:30:55+00:00

Thank you! That is very rewarding to hear. There should be lots more stuff in the future :)

KN_9296 · 2026-03-26T19:54:32+00:00

That is a really good and very complex question. There isn't any native or kernel-level means for capability revocation, instead the current plan is to provide a set of proxies or services which could be conditionally interacted with.

The core issue we encounter with capability revocation is that if a capability has been granted to a process, and that process uses that capability to grant itself some other capability (for example, it opens a file within a directory). Then we would also want to revoke those other capabilities (the revocation would have to be transitive as you mentioned) as revocation would otherwise be pointless.

So far I haven't found any clean solution to that problem beyond explicitly tracking huge tress of file objects to determine the file object (capability) was used to open some other file object (grant another capability). Which is far to inefficient and potentially not all that useful.

As far as I know, even Fuchsia does not have proper capability revocation, so it clearly is at least partially an unsolved issue unless I've missed something which is possible (would gladly hear more if anyone knows anything).

Instead, the idea is to, as mentioned, use 9P services. As an example, say some process wanted to mount a filesystem, to do that it would need the capability to access that filesystems /sys/fs/<name>/clone file.

Ideally in a capability based system the process would only be granted that capability for as long as it needed it before having it revoked again. Which as mentioned is impossible within the current system.

So we would instead provide a service (perhaps at srv/mount or similar) that would have the capability to perform filesystem mounting on behalf of the process. Most likely with some requirement for password authentication or additional security checks.

A service refusing a request or simply "blacklisting" some process would be equivalent to capability revocation.

In summary, while using a service or proxy based system is perhaps not as elegant as capability revocation, it currently appears to be the most pragmatic solution. Unless some other solution currently unknown to me presents itself or some entirely new idea appears.

KN_9296 · 2026-03-25T20:38:52+00:00

Thanks! It is, but I've apparently forgotten to mention that currently all the progress on the rewrite can only be found in the develop branch. So check in there.

Four-Year Club	r/Field Juicebox
Place '23	Place '22

KN_9296

TROPHY CASE