> It is worth noting that eager, statically-typed languages like OCaml and F#
> are many times faster than the other languages at this task. This is
> precisely the forte of OCaml and F#, manipulating trees and graphs.
To be fair, it is also worth noting that both the OCaml and F#
implementations have code generators that are much more advanced than
the usual suspects in the Lisp world (save maybe for Allegro, with
which I have no experience). The OCaml code generator is reknowned for
producing good code. And of course, F# has the benefit of the CLR code
generator, which is state of the art.
I don't know why the ML-family language implementations tend to have
better code generators, but they do. SML/NJ's register allocator is an
iterated-coalescing implementation written by Appel himself.
Meanwhile, SBCL's allocator is a simple heuristic implementation,
which wouldn't have been state of the art even 25 years ago. MLton
does a full suite of SSA-based optimizations. SBCL's doesn't even do
peephole optimization. And of course the CLR does *everything* (with
Microsoft's $$$, there is no excuse for it not to).
PS) I don't mean to pick on SBCL here. I'm just using it as an example
because it's state of the art as far as free Lisp compilers go.