Java Specialization Classes Compiler notes. by Francois-Xavier Josset updated by Nic Volanschi 1) Path hierarchy of the JSCC 2) New abstract/technical features for JSCC Pre-processing Generalities Enclosing object Generic and specialized implementations Generic implementation Specialized implementations 3) Hypothesises for users 4) Possible improvements for the JSCC 5) Known bugs 6) Current state of the JSCC. Where to find the sources. ************************************************************************************* NOTE: this document is NOT a tutorial on specialization classes. The reader should be familiar with the specialization classes concepts and compilation scheme. For details on that, see the OOPSLA'97 paper "A Declarative Approach to Specialization in Object-Oriented Programs". 1) Path hierarchy of the JSCC SCC _______|_______ | | | | | | | | | comp ppro lib which contain, respectively: SCC/comp/*.class ( package SCC.comp ) - the compiler itself SCC/ppro/*.class ( package SCC.ppro ) - the preprocessor SCC/lib/*.class ( package SCC.lib ) - the runtime support library Using JSCC, step by step: # 0 : the current working directory must contain a subdirectory called 'results', which itself must contain a subdirectory called 'rppro'. These will be filled with the results of the compilation process, as follows: # 1 : Initial state ./X.java, ./Y.SC note : X.java is the source Java file to specialize. Y.SC contains all the specialization classes. # 2 : pre-processing > java SCC.ppro.SCprepro X.java # 3 : state after pre-processing ./results/rppro/X(p).java note : X(p).java is the result of the X.java pre-processing. Its real name is X.java too, but we note it like this to distinguish from X.java. # 4 : compiling > java SCC.comp.SC Y.SC results/rppro/X(p).java # 5 : state after compiling ./results/X(scc).java, XImpl.java, (YSpecImpl.java)+ note 1 : X(scc).java is what we call the enclosing object. Its real name is X.java too, but we note it like this to distinguish from X.java and X(p).java. note 2 : XImpl.java is the generic implementation. note 3 : the notation (YSpecImpl.java)+ means: for every specialization class YSpec found in Y.SC, JSCC creates a specialized implementation named YSpecImpl.java. # Script. There is a script called 'compile' in the Examples directory, which performs all the phases for you (preprocessing, compiling with JSCC and compiling with javac). ************************************************************************************* 2) New abstract/technical features for JSCC *** Pre-processing *** #1: #2: The pre-processing step aims at modifying in the class X, the "contracted" assignment rule (with operators like ++, +=, -=, *=, /= and so on...). The substitutions are as follows: x op= y --> x = x op y ++x --> x = x + 1 /* if occuring at the top level in a ExpressionStatement */ --> (x = x + 1) /* otherwise */ x++ --> x = x + 1 /* if occuring at the top level in a ExpressionStatement */ --> ((x = x + 1) - 1) /* otherwise */ Note: the case of being at top level in an ExpressionStatement must be treated as a special case because not every expression can be an expression statement in Java (e.g. "(x=x+1);" is not allowed). This preprocessing of contracted assignements simplifies the 'guarding' of the unstable variables in the constructor or in the non-specializable methods: substitution of the assignment of the unstable variable v with the expression e for "scImpl.scSet_v(e)". *** Generalities *** #3: The compiler can distinguish the class X from others writen in the X.java file. So, the specialization processing is made only in the class X. The other classes are parsed by the "normal" java grammar and rewritten such as they are. #4: If the source X.java file begins with "package p;", then this is added on the top of implementation files (it is left such as it is on the enclosing object) and the package name "p." is added before the file names in the scNotify and scIsA methods (in the arguments of scSwitchToImpl and forName called methods, respectively). #5: If the source X.java file contains "import" declarations, they are copied into the body of the implementation files. #6: "import SCC.lib.*;" string is added into the body of all generated files. #7: About the problems of visibility, every "private" string occuring in variable or method attributes is suppressed. The constructors in the implementation files, and all classes produced by the compiler are "public". The "final" attributes found in the specializable methods prototype are removed. Note that this has the unpleasant efect of changing a little bit the semantics of the initial program. #8: A new class, named SCC.lib.ArrayOfInt, consist of redefining the java int[] arrays for our JSCC. This ArrayOfInt accepts int values. Its main interest is to process arrays as an object we can guard if it is unstable, and to avoid arrays considered like lists of values we could guard each one. Actually, the ArrayOfInt object is a stable invariant: it is assigned in the constructor and nowhere else, and its values are only read. An ArrayOfInt object is processed like an object variable in the compiler, and it is compile-time. The syntax of the ArrayOfInt invariant specification in the specialization class is: tab == { int_const, int_const, ... }; where tab is an Array object declared in the X.java file. For example, to declare an array "tab" of integers { 2, 4, 6 } as invariant, you'll write: " tab == { 2, 4, 6 }; " The specialization state of the Array is named "SpecArrayOfInt". Next, in an implementation file, the JSCC writes, for the same Array tab, the method scSet (in the 'enabler' context for example) as follows: " Array scSet_tab(Array val) { int tmp[] = { 2, 4, 6 }; if (scEncl.tab != null) scEncl.tab.scDetach(scEncl); scEncl.tab = new ArrayOfInt (val, tmp); if (scEncl.tab != null) { scEncl.tab.scAttach(scEncl); if (scEncl.tab.scIsA("SpecArrayOfInt")) scNotify(scEncl); } } " #9: JSCC "pretty"-prints automatically the produced code. It is not perfect, but the files are much more readable than the JavaCC produced code... In contrast, the preprocessor doesn not attempt any pretty-printing at all. To pretty-print the code better, you'll find a real java pretty-printer (written by Sandy Anderson ) in the path ./Pretty/. Its use is very simple: java Pretty source.java [ target.java ] Actually, the 'compile' script in the Examples directory calls this pretty-printer after the preprocessing. note: if you don't give a target as output for the pretty-printed code, the Pretty compiler prints this new code to the screen. *** Enclosing object *** #10: The enclosing object implements the interface QInv, instead of the interface Mutable. #11: The constructor is modified: - at first, if there is no constructor in the class X, JSCC creates one by default without parameter, which only calls the method scInit. - if it already exists, a call to scInit is added just after the expression with "super" if there is one, otherwise in the beginning of the constructor. - the assignments are guarded for the unstable variables. So, the method scInit mustn't call the method scAttach, because it would duplicate it. #12: The finalizer method is rewriten, as it is specified in the algorithm. #13: For each specializable native method m, the word "native" is removed, and a body is created which calls "scImpl.m(...)". #14: If the return type of a specializable method m is not "void", then the substitution body is: "return scImpl.m(...)", else it is: "scImpl.m(...)". #15: Several details in methods about the mutable behaviour changed: - a boolean flag named alreadyCalled is created to avoid the method scInit to be called twice. It could happen in the case of a constructor which calls another one. - the method scSwitchToImpl is modified. Its new body is: " scImpl = (classXName+"Impl")Impl.newImpl(Impl.getImplClass(state)) .theSpec().spec(this,state); " where classXName is X (for a X.java file), newImpl, getImplClass and theSpec are methods of the class Impl (in the package SCC.lib), spec is a method of the class Specializer (in the same package), and state is a formal parameter. - scClients is a Vector. The methods scAttach and scDetach are modified in consequence: " public void scAttach(Mutable m) { scClients.addElement(m); } public void scDetach(Mutable m) { scClients.removeElement(m); } " - the method scIsA changed too. Its new body is: " try { return scImpl.isA(Class.forName(state+"Impl")); } catch (ClassNotFoundException e) { throw new Error("Bad implementation!"); } " where isA is a method of the class Impl and state is a formal parameter. - in the method scNotify, the modification has to be propagated for the scClients, as shows the following piece of algorithm: for each scClient c c.scNotify(); *** Generic and specialized implementations *** #16 : The SC algorithm is modified on section 3: "Construct the N+1 implementations for X". At first, for the construction of the generic implementation, the new algorithm to update methods definition is: for each unstable variable v if v occurs in a sub-class S of X then: make the 'enabler' processing otherwise: make the 'plain assignment' processing Next, for the construction of specialized implementations, there are 3 shifts: - on the 'disabler' processing, the test to filter the variable state (specialization or no) disappears. - if 2 unstable variables with the same name occur in 2 related specialization classes, there might cause a conflict. Consequently, the 'disabler' processing is made first, and the 'enabler' one next but only if the current unstable variable (from a specialization sub-class of the current specialization class) is not an invariant of the current specialization class. - another problem can happen: 2 specialization classes, sisters (i.e. which extend the same specialization class), can have the same invariant. Then, to avoid a new conflict, we consider that if the current specialization class has more than one "direct" specialization sub-class, the test on 'enabler' processing becomes no necessary. #17: In the methods scSet, the test before the call to scNotify is about the predicate refering to the unstable variable, not about the predicate "check" which is the conjunction of all the predicates refering to all the unstable variables in the current specialization class. #18: The guards are modified in the methods scSet, for the unstable variables v typed with an object or Array. Before a scDetach or a scAttach, a NullPointerException-like test is necessary: " if (scEncl.v != null) ... " In addition, it is the enclosing object that has to be pushed as effective paramater for these two methods scAttach and scDetach. So it gives: " scEncl.v.scAttach(scEncl) " and " scEncl.v.scDetach(scEncl) " *** Generic implementation *** #19: A method named setEncl is created. Its use is at run-time specialization. Its code is: " void setEncl (Mutable m) { if (scEncl != null) throw new Error("setEncl() called twice!"); scEncl = (classXName)m; } " #20: For each specializable method, the initial body (in the class X) is copied with the substitution of "this" for "scEncl", and the prefixing by "scEncl." of all the global and inherited variables (i.e. the variables that are neither local nor formal parameter), and of each call to a method. In fact, JSCC behaves as follows: - every occurrence of "this" are replaced by "scEncl", - every name is checked: if the name is not qualified (i.e. no '.' inside), and that field is not shadowed by a local variable or by a formal parameter, JSCC prefixes the current name with "scEncl.", because this must be a field name (either delclared or ingerited by the current class X). If the name is qualified, and the first identifier is a field declared in class X (either a variable or a method), then JSCC prefixes the current name with "scEncl.". Note that JSCC doesn't dispose of the source code of any parent or imported classes; therefore, it cannot distinguish between a qualified name starting with an inherited variable (e.g. "field.itsField") and a qualified name starting with a class name (e.g. "System.out"). So, it doesn't prefix any of these with 'scEncl'. In order to obtain a correct result, inherited variables must be prefixed by 'this' in the original program (see "Hypotheses for the user"), and then will be treated by the previous rule. # Guards are put on any assignment to an unstable variable (which is non-local and non-formal parameter), as follows: x = --> scImpl.scSet_x() .x = val --> .scImpl.scSet_x() where is any expression of Object type (including a qualified name, e.g. a.b.c). Note: the 2nd rule above assumes that x is a variable of class X, according to the encapsulation hypothesis (see Hypotheses for the user). *** Specialized implementations *** #21: A method scSetEncl is created in each specialized implementation. Its code is very similar to the generic implementation method setEncl: " void scSetEncl (Mutable m) { scEncl = (classXName)m; } " #22: For each specializable method occuring in the current specialization class, JSCC copies: - the prototype found in the specialization class and its body, if a body is found in the specialization class; - the prototype found in the class X, with the substitutions and prefixes like in the generic implementation (cf 2.20). It requires therefore that the prototype of a specializable method in the class X and that of specialization class to be similar (cf 4.40). #23: What follows is a table which shows the possibilities of the specializable methods gathering and processing. The entries are: - the time of the specialization class (compile-time / run-time) - the attributes type stem from the method prototype declared in the class X: native or not native - the block type of the method in the specialization class: ";" or "{ ... }" note 1: (scEncl){ ... } means: in the block, the substitutions and prefixes are made, as specified in 2.22 note 2: normal_prototype is the prototype without modification prototype_with_native is the prototype without modification, and including a "native" attribute prototype_without_native is the prototype which the attribute "native" is removed ----------------------------------------------------------------------------------- | | not native & ";" | not native & "{ ... }" | |-------------|-----------------------------------|---------------------------------| | | "native" + normal_prototype + ";" | normal_prototype | | compile-time| --> error: not implemented yet | + (scEncl){ ... } | | | need a compile-time specializer | | |-------------|-----------------------------------|---------------------------------| | | "native" + normal_prototype + ";" | normal_prototype | | run-time | --> error: not implemented yet | + (scEncl){ ... } | | | need a run-time specializer | | |-------------|-----------------------------------|---------------------------------| |-------------|-----------------------------------|---------------------------------| | | native & ";" | native & "{ ... }" | |-------------|-----------------------------------|---------------------------------| | | prototype_with_native + ";" | prototype_without_native | | compile-time| --> specialization with Tempo CT | + (scEncl){ ... } | | | | | |-------------|-----------------------------------|---------------------------------| | | | prototype_without_native | | run-time | --> error: not implemented yet | + (scEncl){ ... } | | | (specialization with Tempo RT) | | ----------------------------------------------------------------------------------- ************************************************************************************* 3) Hypothesises for users First of all, we suppose that the .java file is correct, i.e. compiles under javac with no errors. We use this hypothesis several times throughout the compilation process. #24: Specializable methods are not overloaded. That is, when testing if a method is specializable, only its name is considered, not its prototype. This current shorcoming will be removed in a future version. #25: Reading in .SC file: the declaration of an object invariant is accepted only if the specialization class refered by this object is declarated upper in the .SC file. Otherwise, a null pointer exception is raised (this should be fixed). #26: Variables inherited by the class X, must be prefixed with "this." in the methods of class X, when they are starting a qualified name. Also, variables of class X and inherited by X must be prefixed by "this." in the specialized methods bodies in the specialization classes (in the .SC file). The .SC case is a bit different because at the time the .SC is parsed, the class X was not parsed yet, so the variables declared by X are unknown. A future version will make an extra pass of class X before (eventually fusionned with the preprocessing). #27: Assigning unstable variables in specializable methods: it is strictly forbidden and this error is located and printed to the screen. The reason is that the validity of a specialized method depends on that invariant values; assigning them would cause the method to invalidate itself! #28: Expressions with "super" in specializable methods are forbidden too, because in the implementations, it would be not possible to do something like "scEncl.super. ..." (this is not legal Java syntax). #29: The native methods at run-time: our JSCC does not process this case and prints an error message if it happens. We think that native methods at run-time does not occur often enough to process this tricky case. #30: Cycles in specialization classes are forbidden. For example, consider this simple scheme: spec Spec1 extends Spec2 { ... } spec Spec2 extends Spec1 { ... } Spec2 is a scClient of Spec1 and Spec1 is a scClient of Spec2. When Spec1 calls scInit in its constructor, this scInit calls scNotify, which calls Spec2.scNotify. Next, Spec2.scNotify calls Spec1.scNotify and so on ... Of course, the same problem can happen with more than 2 specialization classes. On the other hand, a cycle can (incidentally) be created with object invariants. Note: thanks to the requirement of having any specialization class declared before it is used, JCSS will always reject cyclic definitions. #31: The consistence between the specialization classes and the java class is (loosely) checked: all unstable variables must be declared in the class X and must not inherit from a super-class, and all specializable methods in Y.SC have to be declared in the class X. #32: Array invariants: a new class ArrayOfInt is available to use arrays in invariants. So, don't use java arrays as unstable variables! # The encapsulation hypothesis: all the assignments to the fields of any class C are performed only in methods of class C. This assumption is done even for public variables! The assumption is necessary for class X (the class to be specialized) because we parse only its definition, and therefore we cannot place guards anywhere else. The assumption is necessary for other classes, too, because we guard assignments to ANY unstable variable, in the methods of class X. So, we suppose that no field with the same name but belonging to another class is assigned in class X. ********************************************************************************** 4) Possible improvements for the JSCC #33: About the "private" elimination: in the jdk 1.1 java grammar, encapsulated classes are allowed. So, the implantation classes could be declared in the enclosing object class, what would solve the problem of visibility. #34: #35: All the words beginning with "sc" could be reserved. So that to avoid the use of JSCC reserved words (scAttach, scDetach, scNotify, scSwitchToImpl, scIsA, scState, scInit and so on ...). #36: The Array class could contain methods for the assignment of its components. It would complicate the implementation of this class, but it is feasable. #37: Methods named "TempoInit()" could be generated automatically by JSCC to give the java context (invariants and specializable methods) to Harissa, which would produce C code specialized next by Tempo. There would be one method "TempoInit()" in the generic implementation, and one in each specialization implementation. The generic implementation one could be: " void TempoInit() { scEncl = new X(); // X is the class to specialize (in X.java file) scEncl.scImpl = this; } " Considering the invariants: "{ v == 1; w; Spec s; t == { 1, 2 }; } " the specialized implementation one would be: " void TempoInit() { super.TempoInit(); scEncl.v = 1; // nothing for run-time variable w: initialization not possible s = new SpecImpl(); s.TempoInit(); int tmp[] = { 1, 2 }; t = new ArrayOfInt(tmp); t.TempoInit() } " #38: About the native methods at run-time: we could process them, but we could not find an lightweight solution for runtime linking (defining and loading a new class on the fly seems very inefficient). #39: The guarded assignments could be improved with an inter-procedural and context-sensitive analysis. This would allow to factorize all the guards in a constructor. #40: The prototype of the specializable methods in the specialization classes is complete: the attributes, the return type, the name, the formal parameters. though, only the method name is used when searching for specializable functions. Taking all the prototype into account (except perhaps the parameter names) would remove the non-overloading restriction on specializable methods. # [Harissa-related] The implementation classes (with the exception of the generic one) are never referred to explicitly in the enclosing object. Therefore, a switch to a specialized implementation produces a dynamic class load. This is bad for efficiency, but also because you cannot use Harissa's "static" flag (which is important, e.g, for CHA). One solution is to refer all the implementation classes explicitly in the enclosing object, either in a static block or in scSwitchToImpl() method (via a case statement). BTW, this would an optimization of scSwitchToImpl() for a small number of specialized implementations, similar to what they're doing in OO dispatch optimization. ************************************************************************************* 5) Known bugs #41: # There is a problem when using class constants in the right side of a CT invariant. The predicate is used both in the enclosing object and in the implementation objects, so the substitution with scEncl is needed only in some cases. The problem can be circumvented if prefixing the class constants with the class name (e.g. Inode.R_BIT). # When finding an invariant on an Object type, where the SC has not been seen yet, it gives a NullPointerException, instead of a clear message. # Runtime invariants yield a 'scEncl.true' check, which raises a compile error. In general, runtime specialization is not at all tested, and perhaps buggy. *************************************************************************************