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 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 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.
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 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 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 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 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 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 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 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 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.
https://www.graalvm.org/latest/graalvm-as-a-platform/languag...
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.
https://labs.leaningtech.com/blog/reducing-webassembly-size-...
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".
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
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
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.
> abs($0 + 2 * 3 - 10)
> becomes
> abs($0 - 4)
Underscores don't do that though, so I'm not sure that's what was intended.
Can you either expand on that one or link me to sources that do? I think I follow, but I'd like more info
(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.
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.
https://en.wikipedia.org/wiki/Continuation-passing_style
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?
Optimizing deeply enough will eventually make any abstraction leaky though, so you'll never fully escape mechanical sympathy.
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.
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?"
> "There are certain ideas in software that are simply beautiful"
Fifteen-ish paragraphs later
> "Here we have a brainfuck interpreter"