Fast Lisp

Years ago, I ran across a paper that described starting a high level language, and using that to operate on the large scale attributes of an algorithm that have real impact on performance; by performing successively optimizations in the high level language, the program was eventually reduced to a form that could be translated directly into low-level C, where it out-performed almost every other algorithm in the class (it was a school project) With my education project, and general recent interest, I thought it was time to look this resource again.

It didn’t take too long to find The Role of the Study of Programming Languages in the Education of a Programmer by Daniel P. Friendman, in the ‘useful’ folder of my downloaded papers. The bit I was thinking of was actually a single, though large, anecdote in a larger work. (It’s near the end if you go to read it.) The technical points of the paper itself are still a bit much for me on a casual read; I’ll have revisit it in more detail sometime.

Of course it’s the anecdote that stayed with me. Consider this quote:

“One can follow a series of rewrite rules (just about blindly) to transform a program into another form with some desirable property.”

“Just about blindly” is roughly equivalent to “just about mechanically” – so way can’t the danged machine do it for me? This this may have been a major influence in my Program transformation rant (last section; hopefully if I wrote that now I’d have the sense to put an anchor there)

A related note is an e-book I’m reading, Partial Evaluation and Automatic Program Generation. The results of course aren’t as good as hand written code, but may offer enough improvement for many applications. One of their favorite tricks is producing a compiler by specializing an interpreter on the source program, and various higher-order versions of the same concept.

Back on the theme of fast Lisp, I’ve also run across Picolisp, which claims that a lean and mean interpreter outperforms compiled Common Lisp – even with CLs special cases for things like arrays, and hints to help the compiler out. And you don’t have to complicate your system with special cases or annotations.

Posted Sunday, March 18th, 2007 under Review.

Comments are closed.