News for hackers. Stuff that matters.
Re:The Magic of Partial Evaluation by measurablefunc on Wednesday November 18, 2026 @02:22PM (#50550795)
Combining this w/ a JIT gets you truffle/graal.
Re:The Magic of Partial Evaluation by grashalm on Wednesday November 18, 2026 @02:28PM (#50550882)
If you are curious how this works in Truffle. Here are some docs:

https://www.graalvm.org/latest/graalvm-as-a-platform/languag...

Re:The Magic of Partial Evaluation by arvyy on Wednesday November 18, 2026 @04:43PM (#50552542)
truffle is great, it's the most exciting tech in pldev domain to me. I'll just mention truffle has few other perks than just performance boost -- you get a debugger with a fairly small effort, and you get interop with other languages implemented using truffle (which does include fairly mainstream ones like python, js, and others).
Re:The Magic of Partial Evaluation by measurablefunc on Wednesday November 18, 2026 @05:48PM (#50553463)
I think they have a C interpreter as well so in theory that should allow running python modules that are wrappers for C libraries like sqlite.
Re:The Magic of Partial Evaluation by owlstuffing on Wednesday November 18, 2026 @03:09PM (#50551469)
This type of optimization is also known as compile-time constant expression folding.

The problem with expanding it to include function calls is that it compromises binary compatibility. A code change on a function that results in a different range or has different side effects, will not be realized unless the caller is recompiled.

Re:The Magic of Partial Evaluation by cogman10 on Wednesday November 18, 2026 @04:06PM (#50552110)
Which is why the second most important optimization of compilers is inlining. If the callee is small enough then hoisting it up into the caller can expose additional optimizations, including noticing that parameters in the caller to the callee are in fact constant.
Re:The Magic of Partial Evaluation by apignotti on Wednesday November 18, 2026 @03:17PM (#50551576)
We implemented a similar concept in our C++ -> JavaScript/WebAssembly compiler (Cheerp) several years ago. It was a nice challenge.

https://labs.leaningtech.com/blog/reducing-webassembly-size-...

Re:The Magic of Partial Evaluation by infogulch on Wednesday November 18, 2026 @03:31PM (#50551733)
Doesn't Zig have a pretty nice implementation of compile-time evaluation built in?
Re:The Magic of Partial Evaluation by jimmyhmiller on Wednesday November 18, 2026 @04:09PM (#50552150)
Comptime in zig is definitely quite cool, but not quite the same.

Consider this example. https://jimmyhmiller.com/split-shot/#/vm

Make the code a comptime argument in zig and you get "store to comptime variable depends on runtime condition".

Re:The Magic of Partial Evaluation by hansvm on Wednesday November 18, 2026 @04:45PM (#50552568)
Zig isn't perfect, but I've definitely done this futamura stuff before. It's one of my favourite ways to implement a Forth in Zig (which, incidentally, is the default way that I introduce a backprop library or other DSL as I'm prototyping an idea). Interpreters are dead-simple to write, and I just write an interpreter with a comptime code argument. It definitely works, and the codegen is reasoanble out of the box.
Re:The Magic of Partial Evaluation by speedster217 on Wednesday November 18, 2026 @06:02PM (#50553599)
Thanks for the input! I was thinking about trying this out in Zig. The whole article reminded me of why I was originally excited about comptime
Re:The Magic of Partial Evaluation by artrax on Wednesday November 18, 2026 @04:18PM (#50552243)
We build this as a c++ library, do to query-compilation for our stream processing engine.

https://github.com/nebulastream/nautilus

It allows us to implement operators or functions without having to write them in terms of LLVM IR DSL (or similar). Rather, you write your functions over a wrapper type (and returning one), for which there is an overload of anything which you can overload in c++.

You can instantiate a wrapper from some c++ value, in which case the wrapper will just forward everything to this value, which was nice for debugging in the preagentic era. But, you can also instantiate such a wrapper as a tracer, and the result of the functions evaluation will be a trace.

For controlflow, we record whenever a wrapper type is evaluated as a bool, first return true, and when we reach the end of one branch, throw an exception to get back to the beginning, and start all over again, but evaluate it to false.

The resulting trace we can turn into LLVM IR and compile, or run for example in wasm

Re:The Magic of Partial Evaluation by johntortugo on Wednesday November 18, 2026 @04:45PM (#50552579)
This seminar explains how GraalVM Truffle uses partial evaluation: https://youtu.be/pksRrON5XfU
Re:The Magic of Partial Evaluation by airtnp on Wednesday November 18, 2026 @04:50PM (#50552675)
I keep thinking the partial evaluator and Futamura projection application on LLM context.

Skill => Generic Program LLM skill optimizer => Partial evaluator Context => Env/Input Agent => Interpreter

First projection: mix(interpreter, program) => specialized skill AOT compiling => offline skill rewriting JIT compiling => runtime specializing, defer loading

Second projection: mix(mix, interpreter) => Agent/Model specific skill optimizer

Third projection: mix(mix, mix) => self-improvement skill optimizer

Whatever maybe I'm just thinking LLM as magic partial evaluator for any tasks

Re:The Magic of Partial Evaluation by iFreilicht on Wednesday November 18, 2026 @05:20PM (#50553079)
Very interesting concept! It reminds me of Hazel (https://hazel.org/) which takes the idea further and into the editor; any program written in it can be partially evaluated, even if variables or even part of the syntax are missing. Missing parts are called "holes", and those are preserved during evaluation so that something like

abs( + 2 * 3 - 10)

becomes

abs( - 4)

which is great fun. My first attempts using this showed me that if you're not used to this, it actually gets pretty confusing quite quickly, but I guess it can be learned.

Re:The Magic of Partial Evaluation by fmbb on Wednesday November 18, 2026 @05:30PM (#50553239)
Is that a unary minus denoting a negative number or a binary minus yielding a function with one hole?
Re:The Magic of Partial Evaluation by dullcrisp on Thursday November 19, 2026 @12:13AM (#50556312)
Does it matter?
Re:The Magic of Partial Evaluation by mrgriffin on Thursday November 19, 2026 @04:52AM (#50558057)
I'm guessing that HN has swallowed some underscores. I've written them as $0 in the below:

> abs($0 + 2 * 3 - 10)

> becomes

> abs($0 - 4)

Re:The Magic of Partial Evaluation by Izkata on Thursday November 19, 2026 @09:02AM (#50560247)
For both of you: two spaces of indentation does code formatting, for example:

  abs(_ + 2 * 3 - 10)
https://news.ycombinator.com/formatdoc

Underscores don't do that though, so I'm not sure that's what was intended.

Re:The Magic of Partial Evaluation by Jtsummers on Thursday November 19, 2026 @10:50AM (#50561680)
Underscores are not swallowed by HN, the only (visible) character that can get stripped out will be *, you need to explicitly escape them in regular paragraphs (in code no escaping is needed) using ** or \*. If it's a lone * surrounded by white space or the only * next to other visible characters, then it will also survive. Otherwise you get italics*.
Re:The Magic of Partial Evaluation by TuringTest on Wednesday November 18, 2026 @05:34PM (#50553286)
[delayed]
Re:The Magic of Partial Evaluation by packetlost on Wednesday November 18, 2026 @05:47PM (#50553456)
> Third one is when you learn that the behavior of any imperative language (down to the working of the microprocessor data paths) can be fully represented in a pure functional rewrite language (without destructive assignment / cell state changes).

Can you either expand on that one or link me to sources that do? I think I follow, but I'd like more info

Re:The Magic of Partial Evaluation by IsTom on Wednesday November 18, 2026 @06:14PM (#50553706)
I think OP might be talking about operational or denominational semantics or something isomorphic to them.
Re:The Magic of Partial Evaluation by TuringTest on Friday November 20, 2026 @02:54AM (#50571493)
[delayed]
Re:The Magic of Partial Evaluation by tpoacher on Wednesday November 18, 2026 @06:45PM (#50553971)
Not OP, and probably not what he meant, but for me the insight that any for loop can be expressed as a fully equivalent tail-recursive call and vice-versa is what I would describe as my No.3 moment.
Re:The Magic of Partial Evaluation by packetlost on Wednesday November 18, 2026 @07:01PM (#50554106)
I don't think that's what is being said. The statement is more like 'any imperative program can be represented by a purely functional representation', which goes beyond simply modeling loops with tail call elimination.
Re:The Magic of Partial Evaluation by bmacho on Wednesday November 18, 2026 @07:43PM (#50554500)
[delayed]
Re:The Magic of Partial Evaluation by deterministic on Wednesday November 18, 2026 @11:11PM (#50555987)
You can represent any imperative state as a pure value and then "run" an imperative program by doing:

(i1,s1) = step(i0,s0)

(i2,s2) = step(i1,s1)

...

(halt,sN) = step(i(N-1),s(N-1))

where i* is the instruction(s), s* is the state(s) and halt is the "program is done" instruction.

Think about it as a pure interpreter running an imperative program.

It is how imperative software is proven correct using pure languages like LEAN.

Re:The Magic of Partial Evaluation by krackers on Thursday November 19, 2026 @12:54AM (#50556520)
[delayed]
Re:The Magic of Partial Evaluation by Viliam1234 on Thursday November 19, 2026 @02:33PM (#50565073)
"The future state is a deterministic function of the present state" is how computation works in general, and its continuous version is how physics works.

To get a Turing machine, you need to add one more constraint, which is that things only happen at one place at a time... but that "cursor" itself can (and must, if we want to do something nontrivial) walk across the working memory.

Re:The Magic of Partial Evaluation by jjtheblunt on Thursday November 19, 2026 @10:48AM (#50561666)
perhaps the OP is alluding to continuation passing style conversion, q.v.,

https://en.wikipedia.org/wiki/Continuation-passing_style

Re:The Magic of Partial Evaluation by amw-zero on Wednesday November 18, 2026 @08:11PM (#50554746)
> Third one is when you learn that the behavior of any imperative language (down to the working of the microprocessor data paths) can be fully represented in a pure functional rewrite language (without destructive assignment / cell state changes).

What no one is ever able to explain is: why is this a good thing?

The underlying machine does destructive assignment. The whole thing is a big mutable array. Why should we represent it in another way?

Re:The Magic of Partial Evaluation by AlotOfReading on Wednesday November 18, 2026 @08:46PM (#50555054)
The difficulty of a given problem changes depending on the perspective you're looking at it from. That's why understanding different models helps.

Optimizing deeply enough will eventually make any abstraction leaky though, so you'll never fully escape mechanical sympathy.

Re:The Magic of Partial Evaluation by naasking on Thursday November 19, 2026 @12:31AM (#50556399)
> Why should we represent it in another way?

Because different representations have different properties which lets you perform different transformations. All compilers even for imperative languages use some variant of SSA in their intermediate languages, for example.

Re:The Magic of Partial Evaluation by seanhunter on Thursday November 19, 2026 @01:11AM (#50556626)
Well one place where I’ve found this useful practically is it makes debugging much easier because you can see the evaluation of values as you step through the program. It’s also afaics the insight behind static single assignment form and all the compiler optimisations that enables https://en.wikipedia.org/wiki/Static_single-assignment_form
Re:The Magic of Partial Evaluation by cowlevel on Thursday November 19, 2026 @05:04AM (#50558152)
The described path is useful for applying mathematical thinking to a program, or for exploring several execution paths at a time (like fuzzing) or executing with backtracking, or stuff like that.
Re:The Magic of Partial Evaluation by snackbroken on Thursday November 19, 2026 @12:18PM (#50562961)
Every tool we bring to bear in programming, from control flow structures to type checking comes down to grappling with the fact that global mutable state is hard to reason about.

Viewing the CPU as a pure function from "state of the universe before a given clock cycle" to "state of the universe after said clock cycle" is not particularly helpful on its own, because you still need to care about all the state in the universe. What this change in perspective does however, is that it becomes a relatively small change to say "actually this part of the program doesn't care about the whole universe, and doesn't affect the whole resulting universe, only that tiny bit over there matters and only this tiny bit over here changes."

The win is that the compiler can help keep you honest about handling every possible state you depend on as input and that when you call a function, it doesn't unexpectedly change some state your function depends on behind your back. All the state you ever have to care about when writing a pure function is "what are my arguments, and what are the return values of functions I call?"

Re:The Magic of Partial Evaluation by TuringTest on Friday November 20, 2026 @03:05AM (#50571576)
[delayed]
Re:The Magic of Partial Evaluation by cowlevel on Thursday November 19, 2026 @05:02AM (#50558139)
That's one path, but it's a path that leads away from the machine towards mathematical abstraction. You can also choose the path of mechanical sympathy and learn about things like self-modifying code.
Re:The Magic of Partial Evaluation by p1necone on Wednesday November 18, 2026 @06:01PM (#50553589)
All the examples in here look pretty clean, but doesn't partial application like this in practice on "average" codebases result in massive binary size explosion?
Re:The Magic of Partial Evaluation by fjfaase on Wednesday November 18, 2026 @06:21PM (#50553770)
I once tried this for an interpreting parser I wrote and it resulted in a very large program that took far longer to compile and was also slower than the original interpreter, probably due the code no longer fitting in the processor caches.
Re:The Magic of Partial Evaluation by inopinatus on Wednesday November 18, 2026 @07:20PM (#50554284)
Opening line

> "There are certain ideas in software that are simply beautiful"

Fifteen-ish paragraphs later

> "Here we have a brainfuck interpreter"