Re:Land of Lisp is finally out...and has a music video.
by mahmud on Wednesday October 27, 2010 @09:37PM
(#1841304)
I think it was Appel who had a funny proof for the non-existence of the Perfect Compiler, it can be applied to Lisp quite easily.
FWIW, the proof used the halting problem and went like this. Assume there is a an unoptimized program that, when ran, would go through a series of motions but ultimately halt without any useful output or side-effect. Assume there existed a perfect compiler, PC; that compiler would need to be sufficiently smart enough to translate the problem to a single HALT instruction (or "Label X: goto X".) But since the halting of programs can not be proven analytically, it stands to reason that PC does not exist.
FWIW, the proof used the halting problem and went like this. Assume there is a an unoptimized program that, when ran, would go through a series of motions but ultimately halt without any useful output or side-effect. Assume there existed a perfect compiler, PC; that compiler would need to be sufficiently smart enough to translate the problem to a single HALT instruction (or "Label X: goto X".) But since the halting of programs can not be proven analytically, it stands to reason that PC does not exist.