Self-modifying code (and space/time complexity)

[Bjorn Lisper]

In article <1744 at vaxb.calgary.UUCP> radford at calgary.UUCP (Radford Neal) writes:
>
>There are interesting cases where on-the-fly generation of code seems
>to be essential to get good asymptotic space and/or time complexity.
>
>Consider the following code fragment (version A):
>
>     for (i = 0; i<L; i++)
>     { if (c1) p1();
>       if (c2) p2();
>       ...
>       if (cN) pN();
>     }
>
>The Boolean variables c1, c2, ... cN are assumed to be loop invariants.

(...version B deleted...)

>The following lets you get both (version C):
>
>     start generating code;
>     if (c1) generate instruction to call p1;
>     if (c2) generate instruction to call p2;
>     ...
>     if (cN) generate instruction to call pN;
>     for (i = 0; i<L; i++) execute generated instructions;

Interesting. This reminds a lot of the kind of compile-time manipulation
that optimizing compilers do. The loop

     for (i = 0; i<L; i++) execute generated instructions;

is an optimized version of A *when the ci are known*. If they were known at
compile-time an optimizing compiler could have generated the same code. The
only difference is that the self-modifying program does this *at runtime*,
when we are guaranteed to know the values of the ci's. Maybe we should call
this technique "run-time compilation"?

Bjorn Lisper