Comment by throwaway81523
1 day ago
From Februray 2025 fwiw. Same result there have been multiple articles here about. I wonder how it would work for Haskell programs (no mutable memory).
1 day ago
From Februray 2025 fwiw. Same result there have been multiple articles here about. I wonder how it would work for Haskell programs (no mutable memory).
I'd view "no mutable memory" as misleading, because immutable languages can still create a new variable and forget an old one which has the same memory footprint as mutating one variable.
Obvious example: the flickering stack frame of tail call elimination.
Haskell has genuine mutable memory, through State and IO.
But even without it, you can emulate mutation in a pure language by threading a "heap" parameter through everything.
There's only at most a log factor of extra space and time required in most computing models to "update" a persistent map (though I'm not sure the best way to encode persistent maps directly in Turing machine tapes, which is the model this result is specifically about)