User loginNavigation 
Type DifferentialsI've stumbled across something in my compiler work and wondered if anyone has run into anything similar, or knows of any existing literature about it. The problem I'm working on is dealing with the template bloat problem in an AOT language, without resorting to type erasure. I know that there are some compilers which, during the code generation phase, will merge functions and data structures which have identical machine representations, but I'm attempting to do this in a more formal and abstract way, and at an earlier stage of compilation. In mathematics, a differential is a description of how the output of a function varies with respect to a parameter. In my scheme, a "type differential" is a description of how the meaning, behavior, and machine representation of a function changes with respect to changes in a template parameter. An analysis of the expression tree for a function yields a set of these differentials. Once you know all of the differentials for a function, you can then easily compute whether any of the template arguments can be weakened, creating a more generalized version of the function that has the same meaning. A trivial example is the "CallingConvention" differential. Let's say we have a generic function F which has a generic type parameter T, and which takes a function argument also of type T. Different values of T will have different machine representations, which changes the function signature  however, many different types have identical machine representations, so the set of possible machine representations is much smaller. On the other hand, if we change the type of the parameter from T to ArrayList[T], things are a little different  since ArrayList is a reference type, it's always passed as a pointer, so the value of T no longer has any effect on the function signature at the machine level. So CallConv[List[T] == CallConv[Object]. Other examples of type differential objects include LocalVariable, InstanceOfTest, InstanceMethodCall, FieldOffset, and so on. In some cases, the presence of a differential can be used to decide whether the compiled code should contain a static reference to a type identifier, or whether the type identifier should be passed at runtime as a hidden field or parameter. Java's type erasure can be thought of as a system in which the set of type differentials for all functions is the empty set. Now, what's interesting about this is that I realized that there's a kind of algebra of differentials: There are operators that can be used to sum and compose them. For example, if I have a composition of two templates, it's possible to compute the differential of the result directly by composing the differentials of the individual pieces. Anyway, I'm sure that there's probably some preexisting term for this  which I'd be able to search for if I knew what to name it. By Talin at 20150419 21:18  LtU Forum  previous forum topic  next forum topic  other blogs  3114 reads

Browse archives
Active forum topicsNew forum topics 
Recent comments
1 week 2 days ago
1 week 4 days ago
1 week 4 days ago
1 week 5 days ago
1 week 6 days ago
1 week 6 days ago
1 week 6 days ago
1 week 6 days ago
1 week 6 days ago
3 weeks 1 day ago