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