[Haskell-cafe] Run-time compilation

[Martin Grabmueller]

Daniel Fischer wrote:
>
> So back to square one.
> What then _is_ run-time compilation?

In the virtual machine community, run-time compilation refers to the
translation of program code at run-time, for example the compilation of
Java byte code to machine code in a JIT (just-in-time) compiler.  Other
uses include binary dynamic translators (e.g. for running IA-32 binaries
on Alpha processors), binary dynamic optimizers or security monitors for
binary programs.

Actually, I work on dynamic analysis and transformation of functional
languages at the moment and was quite surprised how this term is used
in the Haskell Wiki.  I would rather call it pre-computing or something
(but maybe I misunderstood the RunTimeCompilation page on my first reading).

> 
> Bulat said that in
> 
> n <- readIO
> flip mapM [1 .. 100] $ \x -> print (x^n)
> 
> the programme could insert (if, e.g. the value read is 2) the concrete faster 
> algorithm for x^n. Isn't that some sort of run-time code generation?
> And a) how far might one expect that sort of thing done,

In a prototype implementation (or rather a proof-of-concept) I have done
exactly that: compile the code of a lambda-expression at the time the closure is
constructed and inline the values of all enclosing lexical variables.  Of course,
an optimizer is needed which uses the additional information about data values,
for example by constant-folding, performing strength-reduction, etc.  I have only
done very primitive optimizations so far.  The biggest problem is probably to
limit code generation to the cases where a performance gain is expected.

> b) how could one cajole the system to do that.

There are two options I can see:

- Operate on an intermediate representation of the program and interpret it, or
- compile the program to machine code.

The former method would probably loose most of the performance expected from
specialization, and the latter is difficult to integrate into existing systems
(the run-time system and especially the garbage collector will need to know
about dynamically generated code and how to properly handle them - you don't
want to throw code away to which a pointer still exists on the run-time stack,
for example :-)

> Last, reverting to the search/replace example, if I have the general algorithm 
> and also declare the function
> 
> work :: String -> String
> work = searchReplace "pattern" "substitution",
> 
> the compiler would produce specialised object code for that, or wouldn't it?

Yes, this is just a more complicated example of the code above, which could
specialize x^n.  The compiler would have to know how to work with strings, of
course.

If you're interested in that kind of stuff, you might want to read in the
direction of "virtual machines", "jit compilation", "partial evaluation" and
"meta programming".

Cheers,
  Martin