[Haskell-cafe] Expanding do notation

[Daniel Fischer]

Am Samstag, 7. Januar 2006 23:56 schrieben Sie:
> Daniel, i also included you in crossposting because these letters can
> also help you understand how "run-time compilation" works. basically
> it's a very simple thing: when we can compute at compile time value of
> some computation, many compilers will do it and substitute expression
> with its final value.

Yes, I thought they did. It's a good and clever thing, but calling that 
RunTimeCompilation would be a misnomer, wouldn't it? That's rather 
CompileTimeEvaluation, isn't it?

> the same can be done at the run-time - as soon
> as we can compute value of some expression used in program or at least
> simplify it using our knowing of part of arguments, this can be used
> to reduce number of computations which program need to perform. say,
>
> n <- readIO
> print (factorial n)
> print (factorial n)
>
> here, "factorial n" can be computed just one time. it's obvious. in
> this case
>
> n <- readIO
> flip mapM [1..100] $ \x ->
>   print (x^n)
>
> it's not so obvious that when program read value of `n`, it can
> substitute instead of `x^n` the concrete, faster algorithm, say 'x*x'
> for n=2. Haskell's ideology of "graph reductions" makes such "run-time
> optimizations" automatically. it it the thing that called "run-time
> compilation" on those wiki page.

Cool. So let's see if I got it.
If I have

n <- readIO
     ...
mapM_ (func n) list
     ...

in my programme, the runtime system will/might build object code for
func n that is then used instead of using the general code for func and 
supplying both arguments to that?

That'd be wow, triple wow!
And run-time compilation is a fitting name for that.

> in KMP algorithm we compile string
> searched to algorithm that will do the search of this concrete string.
> another examples from my own practice is compilation of strings
> representing regular expressions to functions which tests compliance
> with these regexprs, and compiling list of sorting criterions to
> compare function (you can find last example at the end of
> RunTimeCompilation hawiki page)

Thanks. 
Unless I'm grossly mistaken, that made things much clearer.
Would somebody add an explanation along these lines to the HaWiki-page
(I'm pretty sure, I'm not the only one who didn't understand the wiki-page)?

Cheers,
Daniel