One of our goals in writing NML was to produce a system that would be very fast in execution speed. We settled on a non-interpretive approach.
NML actually compiles its source code at blazing fast speeds. But it does not produce native machine code. And it doesn’t produce pCode either -- something that would still require an interpreter of sorts -- the pMachine.
Instead, NML compiles its sources down to OCaml functional closures. If you have any familiarity with the ancient world of FORTH, then this is equivalent to Subroutine Threaded Code (STC). All of the code is compiled to executable functional closures that the OCaml compiler has already compiled to blazing fast native machine code for the host computer.
We took the easy way out here. We let OCaml do the bulk of the speed work for us.
But since we never compile all the way to native code, nor produce any kind of pCode, we cannot store the results of compilation to any kind of external object file. Instead, all code is compiled on the fly from NML sources, as needed.
NML is modular in the sense that separate source files define their own namespaces. References to other modules by way of dotted name notation, e.g., OtherModule.doit, causes the NML runtime system to automatically search for and load that other module on demand, if it is not already compiled into the current session.
The speed of compilation is so fast that this is hardly a concern.
For now, the compiler in NML is derived from a YACC-like production specification (OCamlYacc). But my experience over the past decades has shown that this is not always the best approach. I have been contemplating the creation of a recursive descent compiler where I might have more direct control over the actual parsing process.
But for now, that is a project on my back burner, and I limp along with the mess that ip_parser.mly has become.
The lexical scanning is accomplished by way of another specification in a LEX-like language (OCamlLex), and that isn’t so bad. I am inclined to leave that scanner alone if I ever decide to rewrite the parser.
In any case, whether I rewrite the parser in recursive descent fashion, or continue to use the YACC parser, the output of that parser consists of m-Trees -- a sort of intermediate code that can easily be displayed as Lisp S-expressions. The actual compiler accepts those m-Trees and produces the interlinked calls to previously compiled OCaml functional closures. You can see these m-Trees by asking NML to compile a fragment of code using ``test_parser’’:
# test_parser “let x = 15 in x + 3”;;
==> (Let (Binding (PatList (PatIdent x))
(List (Float 15.)))
(Apply + x (Float 3.)))
(In the above fragments, the sharp-sign # is the terminal input prompt. NML commands must be terminated by double-semicolon ``;;’’ in order to tell the terminal parser that the input is complete. That isn’t necessary in source files. The ``==>’’ is our way of indicating the output from NML)
The compiler itself is written in a kind of CPS (continuation passing style), but the resulting compiled NML code itself is not CPS driven. We tried an experiment years ago where we produced CPS compiled code for NML and found that the speed took about a 30% hit. That was an interesting and instructive exercise, but we decided to fall back to our non-CPS compiled form because speed was more important than other considerations.
Saturday, February 3, 2007
