The Tart compiler generates a lot of synthetic data and code, compared to a language like C++. This includes reflection tables, stack maps for garbage collection, type adapters, and so on.
What I've been wondering is whether it would make sense to do this work in the linker rather than in the compiler. There's even a precedent for this: there's one data structure which is already generated at link time, which is the list of static roots - global data structures that need to be traced in the collector.
There's a variety of things that could be generated at link time, ranging from the "only slightly ambitious" such as interface dispatch methods, to the "wildly ambitious" such as generating DWARF debugging info or even instantiating templates.
In order to do any of this, the linker would need much more information about high-level data structures and types. Ironically, this information - basically a serialized form of the AST - is already generated by the compiler and stored in the module. This information isn't currently used by the linker - instead, it's used by the compiler to allow already-compiled module files to be imported, without having to have the original source files.
If we take this idea to it's logical extreme, what we end up with is something like a Java class file that's compiled ahead of time (AOT), instead of just in time (JIT). That is, you have a single, comprehensive encoding of all of the types and methods in the module, and this encoded information is then used to produce the reflection tables, tracing tables, dispatch tables, and DWARF debug info. (As opposed to what it does now, which is to generate all of these tables separately, at compile time, and then glue them together in the linker.)
This whole approach basically blurs the line between AOT and JIT compilation, in that the inputs to the linker look a lot like the inputs to a VM.
There's some problems to solve however.
1) One problem with using the serialized AST is that lacks a lot of information, since it hasn't been fully analyzed. Type names in the AST are just names - we don't know yet which type is the one being referred to. Similarly with methods and variables, all we know is the name at this point. The largest part of the compiler is the part that analyzes the AST and converts it into a CFG (Control flow graph) in which all types are resolved, template parameters expanded, and so on. We don't want all of this functionality to live in the linker - instead, we want the compiler to do the analysis and then pass to the linker the results of that analysis.
So the first problem to be solved is to come up with a way to serialize the CFG rather than an AST.
2) A second problem has to do with template instantiation. Currently templates are not analyzed until after they have been instantiated. The reason for this is that until they are analyzed, templates don't have enough information to be able to do a successful analysis.
As a simple example, take the max() function whose declaration is "def max[%T](a:T, b:T) -> T". This function requires that it's template parameter, T, have a less-than operator defined for it. If there's no less than operator, the template instantiation fails. Until we actually attempt to instantiate the template and bind some type to T, we don't know if there's a less than operator defined or not. That's why templates are written out as un-analyzed ASTs, rather than fully-analyzed CFGs.
To solve this problem, we would need to change the way template parameters work. In order to do any operation on a variable whose type is a template parameter, you would have to declare the template parameter as supporting that operation.
Say we have a template parameter T, and we have some value 'a' whose type is T. Now we want to call 'a.toString()'. In the current system, we don't know whether a has a toString() method or not, but if we attempt to instantiate the template with some type that doesn't have a toString() method, then an error will occur. In the new system, in order to call a.toString(), you would have to declare template parameter T as [%T <: HasToString], where 'HasToString' is a protocol type that includes a 'toString()' method. In other words, having a 'toString()' method is now an explicit requirement for parameter T, any attempt to instantiate the template with a type that doesn't have a toString() method will fail early.
(FYI - in the literature on type theory, what I have described corresponds to "parametric polymorphism" whereas the way things work now is "ad-hoc polymorphism".)
Unfortunately, Tart's protocol system only works on instance methods, not on regular functions. Right now there's no way to express the concept "match any type that has a less-than operator defined for it". In other words, what we would need is some way to say "given a type T, return true if there is a function 'def infixLessThan(:T, :T) -> bool' defined somewhere." At the moment, I can't even imagine what that syntax would look like. But for now, let's assume we come up with some way to do this.
By pre-declaring what methods we need, we can do the analysis passes on the template and create a CFG. This CFG won't actually be complete, because some types are still not known. But we can at least do enough analysis to be able to write the CFG out to a file.
3) Currently, you can link Tart programs in two ways: Either by using the Tart linker, 'tartln', or by using the standard LLVM tools (llvm-ld, opt, and llc). If using the latter, however, you need to load in the Tart-specific plugins for reflection and garbage collection.
In order to do the link-time code generation that I'm describing, we would need to put all of the code to do that into the shared library, so that it can be loaded as a plugin as well.
No comments:
Post a Comment