# A Case for a Native Runtime Compilation Language
### Making Runtime Function Definitions into Runtime Compilation Events
*-- by @bwasti*
Compiled programming languages often distinguish between two types of information:
1. **compile-time information** - *static types, hardcoded constants...*
2. **runtime information** - *sessions, connections, streaming data...*
Many compiled language implementations have a hidden third type of
information:
0. **target information** - *instruction latency, # of cores, vector register width...*
1. compile-time information - *static types, hardcoded constants...*
2. runtime information - *sessions, connections, streaming data...*
which consists of details about the hardware and
optimization techniques for it.
Often, programs are initialized on startup, so let's add that to the list:
0. target information - *instruction latency, # of cores, vector register width...*
1. compile-time information - *static types, hardcoded constants...*
2. **initialization information** - *command line flags, environment variables...*
3. runtime information - *sessions, connections, streaming data...*
And when performance really matters,
it makes sense to profile at runtime, so let's add that as well:
0. target information - *instruction latency, # of cores, vector register width...*
1. compile-time information - *static types, hardcoded constants...*
2. initialization information - *command line flags, environment variables...*
3. **profiling information** - *hot functions, latency, throughput, cache misses...*
4. runtime information - *sessions, connections, streaming data...*
### AOT Compilation
There are probably many more conceptual layers of information we could add to the
list between 2 and 4,
but consider what a typical ahead-of-time optimizing compiler has access to:
**0 and 1. That's it.**
And the compiler only gets *one shot* to do anything with
this information (barring [PGO](https://en.wikipedia.org/wiki/Profile-guided_optimization)).
This isn't great for a couple of reasons.
There's a large burden on the programmer to *guess what the runtime will look like* in
order to provide performance. As a result, a lot of compiled performance-oriented libraries
are loaded with hard-to-decipher heuristics that have been (theoretically) tuned over the years.
There's a natural *tradeoff between codesize and performance*, with larger
binaries being required to handle more performance edgecases.
This gets worse as the [modality](https://en.wikipedia.org/wiki/Multimodal_distribution)
of the usage patterns increases.
There's a burden on the languages themselves *to [increase compile-time expressivity](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.3670).*
This makes some codebases quite hard to understand.
### JIT Compilation
Luckily there are some popular programming languages that give their compiler
access to all 5 layers of information.
Unfortunately, this often means giving up almost all control of the runtime,
including when things are compiled and how much time is spent doing so.
That's the standard interface for JIT-compiled languages like Java and JavaScript.
If you care about the performance of your program,
that's scary.
The lack of predictability and fine-grained control, as well as the large
persistent runtime, make it hard to justify as a solution for workloads
that need to run as fast as possible.
### Dynamic Compilation
There *are* esoteric alternatives to handing your code over to an
omnipotent JIT runtime.
They are forms of "[dynamic compilation](https://en.wikipedia.org/wiki/Dynamic_compilation),"
which is a superset of JIT compilation and includes all runtime-available compilation.
UW's '99 [DyC](https://web.archive.org/web/20050305025824fw_/http://www.cs.washington.edu/research/dyncomp/Papers/tr-97-03-03.pdf)
extends C with annotations `make_static` and `make_dynamic`
that allow scoped regions of dynamic recompilation, effectively creating
runtime template parameters.
[Forth](https://en.wikipedia.org/wiki/Forth_(programming_language)#Mixing_states_of_compiling_and_interpreting)
allows seamless mixing of interpreted and compiled code,
giving the user freedom to specify which form of execution should be used.
Both of these languages are quite old and also difficult to use (to my naive C++/Python loving eye).
However, they both capture the concept of native support for interactions with the compiler.
Users who want to compile at runtime
are not passing strings (as one might with OpenCL) nor constructiong IR objects (like LLVM IR),
they are just using the language as it stands and specifying *when* compilation should happen.
### A Native Runtime Compilation Language
To capture the benefits of the above mentioned dynamically compiled languages,
I'd like to propose a single conceptual addition to modern AOT languages:
**make runtime function definitions into runtime compilation events.**
Consider the code below (and for the sake of example, assume Python is a compiled language)
```
def foo(a, xs):
def bar(b):
return b * a
res = 0
for x in xs:
res += bar(x)
return res
```
or in C++ (by runtime function definition I mean callable-object construction)
```
int foo(int a, std::vector<int> xs) {
auto bar = [a](const int& b) {
return b * a;
};
int res = 0;
for (const auto& x : xs) {
res += bar(x);
}
return res;
}
```
Right now, in both languages,
the definition of `bar` is effectively syntactic sugar for
a function that takes *two* values (`a` and `b`).
However, I'd like to make a case to allow the definition of `bar` to be
a **runtime compilation event**.
Why? Well, `a` is constant with respect to `bar` and we could certainly emit code that
leverages this fact. For example, if `a` is a power of two,
the compiler could emit a shift operation rather than a multiplication.
Generalized, you end up with a lot of the same optimization benefits of ahead-of-time
compiled languages as well as the theoretically realized benefits of JIT compiled languages.
### Benefits
For a fair number of usecases, this is a lot better than current JIT-compiled languages.
For one, *there's no ambiguity about when compilation occurs*.
When the function is defined, a compilation happens.
If compilation is too slow for you at that point in time, don't define the function there.
Elegantly, a definition that happens outside of any other function
can be compiled ahead-of-time, which is consistent with AOT compiled languages today.
Users gain *fine-grained control over what gets compiled and how*.
Since most programs only have a couple hot functions, users can specify that
many more optimizations are used in very specific parts of the program.
Similarly, they can define their own feedback loops to collect profiling information
and can seamlessly recompile by generating new functions that leverage this information.
All of this is user driven and doesn't require an omniscient profiling JIT runtime.
*Codesize can be drastically reduced*. The typical optimized C++ binary is
loaded with precompiled templates to handle every possible path of execution,
since the compiler only gets one shot to optimize things. By relaxing this
single-shot compilation, binaries can be shipped with far less code.
### Downsides
This doesn't come for free.
For one, the runtime of the language will now need to include a compiler.
It isn't all bad, because the optimizing compiler can be shared as a library across processes
and might even be a bit smaller if it isn't constrained to
being ahead-of-time [citation needed, I know].
Memory becomes a bit trickier to reason over. Compilation doesn't yield
obvious binary sizes, so programmers might need to build mental models
about codesize or even dynamically check memory usage to avoid OOM errors.
Safety is probably a nightmare. I'm not very security minded, but even writing this
I felt a pang of unease about the potential attack surface size.
### Making This Real
I'm not sure this idea could easily be shoe-horned into extent languages.
I think languages with C-ABI support and an advanced macro interface could probably
get something hacked together, but it wouldn't be pretty.
Both LLVM ([ORCv2](https://llvm.org/docs/ORCv2.html)) and GCC
([libgccjit.so](https://gcc.gnu.org/wiki/JIT)) groups
are rapidly adding features to their JIT libraries which makes it a lot
easier to build a language like this from scratch.
I'm pretty interested in starting here, as it seems like fun.
The hardest path would be to actually add something like this to real language specifications.
That'd certainly require the previous two paths to prove out the idea as useful.
I'm very curious what folks think, and posted this article for comment on HackerNews:
[https://news.ycombinator.com/item?id=26998125](https://news.ycombinator.com/item?id=26998125)