Hacker News Reader

I think Common Lisp, Scheme, and Clojure each have a lot to offer. I wish there was one perfect Lisp :)

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.

Actually, this could be done if the program didn't use any print or input commands. In general, it still cannot be done.

I said "without any useful output or side-effect". I/O falls under those categories.

Reply on news.ycombinator.com