News for hackers. Stuff that matters.
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.