PQIL revision 0.5.2 ------------------- A PQIL program (or IL program) is a join, which can be either a primitive join or a control structure. Each join has a set of parameters that designate variables that are read from or written to. The sketch below designates the relevant inheritance structure: + Join (Section 1) + Primitive join (Section 2) + Predicate (Section 2.1) + Non-Predicate (Section 2.2) + Control structure (Section 3) An IL program is represented as a `Join' in the IL implementation. 1. Joins ======== Each IL program has a name and a list of parameters. Control structures further have branches; these are detailed in Section 3. In this document, we write IL programs as follows: name ( ... parameters ... ) ... branches ... Some branches introduce special notation which will be discussed when they are encountered. The parameters to a given join are typed. PQIL 0.3 supports the following types: - int - long - double - Object Some joins have additional constraints on their types which will be discussed when encountered. In the following, we describe joins together with their signature, which is a list of types: NEQ_Int: int * int (A join over two ints) Some joins have a read-boundary marker: ADD_Int : int * int -> int In this join over three ints, the `->' separates between read-only arguments and proper arguments (Section 1.1). In some joins, all variables are proper arguments; we designate them with the following notation: Int: -> int 1.1 Variables ------------- Variables in IL programs are explicitly typed. If there is a type mismatch between type variable and type signature, then evaluation implicitly introduces the necessary coercions, following Java coercion rules. Coercion always happens _to_ the type of the designated signature. For example, consider EQ_Int : int -> int which compares two 32 bit integer values. Let variables L0, L1 be bound as follows: L0 = 0x1 L1 = 0x100000001 L1 truncated to 32 bit is 0x1. Thus, EQ_Int(L0, L1) finds that L0 and L1 are indeed equal (as integers); this is an example of a `successful join' (Section 1.3). Coercions include boxing and unboxing conversions. Variables may occur in a reading position or in a writing position. If they occur in a reading position, the join will only read from the variables (they must thus have been written to previously). If they occur in a writing position, the join will write to them. Variables may occur in a reading position anywhere, but they may only occur in a writing position in proper arguments. To make the above more understandable, we will denote variables in a read position by a preceding question mark (e.g., ?x), and variables in a write position by a preceding exclamation mark (e.g., !x). Consider the following: EQ_Int(?x, ?y) This is legal, if `x' and `y' have been bound previously: the join will compare the two variables. EQ_Int(?x, !y) This is also legal, if `x' has been bound previously: the join will copy the value of `x' to `y'. We can see that it is legal from the signature of EQ_Int, which is `int -> int': the final variable may thus occur in a writing position. EQ_Int(!x, !y) This is illegal. The first argument to EQ_Int is a read-only argument, so any variable occurring here must occur in a reading position. Sometimes we do not care about a particular variable; in that case, we may designate it as the wildcard `_'. The wildcard always the meaning of a fresh variable in a writing position. 1.2 Well-formedness ------------------- A join J is well-formed wrt to a set of parameters P iff the following holds: (a) the number of arguments to J matches J's signature (b) any read-only arguments to J occur in a read position (c) any read-only arguments to J are elements of P (d) any arguments to J that occur in a write position are not in P Note that IL programs need not make explicit whether variables occur in a read- or write-position, but it must be possible to infer the read/write property in such a way that the above holds (such an inferencer is part of the IL system). 1.3 Join semantics ------------------ Any join has one of the following two semantics: - a failure - a success, with a set of possible bindings for all variables occurring in a writing position The bindings in the success case may be trivial; e.g., EQ_Int(?x, ?y) if successful will not actually bind anything. Thus, the semantics of a join can be though of as a lifted set of all viable bindings. 2. Primitive joins ================== We now list all primitive joins, separated into predicates and non-predicates. Predicates are joins that, on success, produce at most a single binding. 2.1 Predicates -------------- >> TRUE: always succeed, without bindings. >> FALSE: always fail. >> ADD_Int: int * int -> int >> ADD_Long: long * long -> long >> ADD_Double: double * double -> double Addition >> SUB_Int: int * int -> int >> SUB_Long: long * long -> long >> SUB_Double: double * double -> double Subtraction >> MUL_Int: int * int -> int >> MUL_Long: long * long -> long >> MUL_Double: double * double -> double Multiplication >> DIV_Int: int * int -> int >> DIV_Long: long * long -> long >> DIV_Double: double * double -> double Division >> MOD_Int: int * int -> int >> MOD_Long: long * long -> long Modulo operation >> BITOR_Int: int * int -> int >> BITOR_Long: long * long -> long Bitwise-OR operation >> BITOR_Int: int * int -> int >> BITOR_Long: long * long -> long Bitwise-OR operation >> BITAND_Int: int * int -> int >> BITAND_Long: long * long -> long Bitwise-AND operation >> BITXOR_Int: int * int -> int >> BITXOR_Long: long * long -> long Bitwise-XOR operation >> BITSHL_Int: int * int -> int >> BITSHL_Long: long * int -> long Bitwise-shift-left operation >> BITSHR_Int: int * int -> int >> BITSHR_Long: long * int -> long Bitwise-shift-right operation with sign extend (>> in Java) >> BITSSHR_Int: int * int -> int >> BITSSHR_Long: long * int -> long Bitwise-shift-right operation (>>> in Java) >> NEG_Int: int -> int >> NEG_Long: long -> long >> NEG_Double: double -> double Negation: 0 becomes 1, all other values become 0 >> BITINV_Int: int -> int >> BITINV_Long: long -> long Bitwise inversion >> EQ_Int: int -> int >> EQ_Long: long -> long >> EQ_Double: double -> double >> EQ_Object: Object -> Object Equality comparison. For objects, this is an object identity test. >> EQ_String: Object -> Object String equality comparison, for two string objects. >> NEQ_Int: int * int >> NEQ_Long: long * long >> NEQ_Double: double * double >> NEQ_Object: Object * Object >> NEQ_String: Object * Object Inequality comparison. For objects, this is an object identity test. >> LT_Int: int * int >> LT_Long: long * long >> LT_Double: double * double Arithmetic less-than test >> LTE_Int: int * int >> LTE_Long: long * long >> LTE_Double: double * double Arithmetic less-than-or-equal test >> SET_SIZE : Object -> int Size of a java.util.Set object >> MAP_SIZE : Object -> int Size of a java.util.Map object >> INT_ARRAY_SIZE : Object -> int >> LONG_ARRAY_SIZE : Object -> int >> DOUBLE_ARRAY_SIZE : Object -> int >> OBJECT_ARRAY_SIZE : Object -> int >> BOOLEAN_ARRAY_SIZE : Object -> int >> SHORT_ARRAY_SIZE : Object -> int >> CHAR_ARRAY_SIZE : Object -> int >> FLOAT_ARRAY_SIZE : Object -> int >> BYTE_ARRAY_SIZE : Object -> int length of an int[], long[], double[], Object[], boolean[], short[], char[], float[], or byte[] (respectively) >> POLY_SIZE : Object -> int polymorphic (hence slightly slower) version of the above >> FIELD: Object -> Object Obtain field `f' from the lhs object. For example, if variable `o' is bound to object `obj', FIELD(?o, !v) obtains `obj.f' into `v'. >> INSTANTIATE: args... instantiates via constructor c, passing in all arguments args (this is a var-args operation). >> COERCE_Boolean : int -> int >> COERCE_Byte : int -> int >> COERCE_Short : int -> int >> COERCE_Char : int -> int >> COERCE_Float : double -> double Coerce value to smaller Java type. This provides the usual Java coercion rules. 2.2 Non-predicates ------------------ The following may all produce multiple bindings: >> CONTAINS: Object -> Object Contains-check for java.util.Set. `CONTAINS(?map, ?value)' produces all possible `value' bindings. >> INT_RANGE_CONTAINS: int * int -> int >> LONG_RANGE_CONTAINS: long * long -> long INT_RANGE_CONTAINS(?l, ?r, ?x) produces all bindings for `x' such that l <= x <= r. LONG_RANGE_CONTAINS does the same for long values. >> LOOKUP: Object -> Object * Object Map lookup for java.util.Map. `LOOKUP(?map, ?key, ?value)' produces all `key' and `value' bindings. Note that LOOKUP(?,?,!) is significantly more efficient than LOOKUP(?,!,?). >> ARRAY_LOOKUP_Int: Object -> int * int >> ARRAY_LOOKUP_Char: Object -> int * int >> ARRAY_LOOKUP_Boolean: Object -> int * int >> ARRAY_LOOKUP_Short: Object -> int * int >> ARRAY_LOOKUP_Byte: Object -> int * int >> ARRAY_LOOKUP_Long: Object -> int * long >> ARRAY_LOOKUP_Double: Object -> int * double >> ARRAY_LOOKUP_Float: Object -> int * double >> ARRAY_LOOKUP_Object: Object -> int * Object Analogous to LOOKUP, but for arrays. >> POLY_LOOKUP: Object -> Object * Object Lookup in maps or arrays, depending on the dynamic type of the first argument. More expensive than the other operations. >> JAVA_TYPE: -> Object Produces all objects for Java type T (only available with special VM support or if T is an Enum). >> INT: -> int >> LONG: -> long >> BOOLEAN: -> int >> CHAR: -> int >> BYTE: -> int >> SHORT: -> int Tests whether the value is part of the set defining that particular type, or generate all values of that type. For example, BYTE(?x) will bind `x' to 256 values from -128 to 127. 3. Control structures ===================== Control structure alter the ways in which success and failure work. 3.1 Block --------- A `block' is a list of branches that are joined in sequence. We denote blocks as curly braces: {a ; b} is a block with two joins, `a' and `b'. The following equivalences hold, giving the block monadic semantics: {} = TRUE {a} = a {a; X} = {a; {X}} (for any sequence X) It is thus easy to define block semantics: `{a; b}' succeeds iff `b' succeeds with any of the bindings generated by `a'. The bindings generated by `{a ; b}' are all the bindings that `b' can generate for all the bindings of `a'. For example, let `one' = 1, `three' = 3. Then {range(?one, ?three, !x); range(?one, ?three, !y)} succeeds with nine different bindings, for all possible combinations of { | x <- {1, 2, 3}, y <- {1, 2, 3} } 3.1 Disjunctive block --------------------- A disjunctive block is the disjunctive converse to the Block: [] = FALSE [a] = a [a | X] = [a | [X]] The semantics of [a | b] are to produce all possible joins for a followed by all possible joins for b. 3.2 Bool -------- >> Bool: int > branch This control structure always succeeds with one binding for its parameter: 1 if the branch succeeds, and 0 if the branch fails. This allows manifesting truth values from failures/successes. 3.3 NoFail -------- >> NoFail This control structure always succeeds. 3.4 Not ------- >> Not: > branch This control structure inverts the success/failure of the inner branch. It produces no bindings. 3.5 Reductions -------------- >> Reduction[reductor_0, ... reductor_k]: ... > body A reduction is a variable-signature operation whose precise semantics depend on its reductors (Section 4). The Reduce operation's semantics depend largely on the reductors used, and on the two branches: the `binder' and the `evaluator' branch, which are executed in sequence. The `Reduce' operator considers each possible binding of `{binder; evaluator}' and reports them to the reductor. It also reports any situation in which the binder succeeds but the evaluator fails to the reductor. Each reductor R is a function that maps two values of the same type t to that type, i.e., `R: t * t -> t'. Each R has a default value default(R) such that default(R) is a neutral element (`1') for R. R(default(R), x) = x. Each R is commutative and associative. In other words, each R is an Abelian semigroup. Implementation-wise, reductors take an arbitrary number of parameters that must be bound in the branches of `Reduce'. For reductors, we use notation Reductor: int * int => int (for example) to specify a reductor with two arguments that must be bound by the `Reduce' body and one argument that is written to after the reduction has completed. A Reduction succeeds (with exactly the one binding produced by all reductors) iff all reductors succeed. 4. Reductors ============ Below is a list of all built-in reductors. Note that reductors may take parameters from outside the reduction they are contained in; we use notation `T1 -> T2 => T3' to separate between such `inner' and `outer' parameters. For example, DEFAULT_MAP: Object -> Object * Object => Object is a reductor that takes an (outer) default value, and then (for each iteration) a key and value map. Consider the following program: Reduction[DEFAULT_MAP(?default)(?key, ?value) : !map]: { INT_RANGE_CONTAINS(?left, ?right, ?key); MUL_Int(?key, ?key, !value) } Now assume the following bindings: default = -1 left = 0 right = 10 Then the above will produce a binding for `map' such that all natural numbers from 0 to 10 are mapped to their squares, and all other numbers are mapped to -1, the `default'. This `default' is only read once and defined outside the Reduction; it is the `outer' parameter. 4.1: Nested reductors --------------------- Some reductors may be nested. We indicate this by placing a caret (`^') preceding the type into which the reductor may be nested. Reductor nesting means that the binding produced by one reductor will be used by another reductor; this can open new opportunities for parallel execution. For example, consider the following reductors: MAP: Object * ^Object => Object SET: Object => Object We can nest these as follows: Reduction[MAP(?key, SET(?value)) : !map] : ... which will compute a map of the set of all `value' bindings that match the given `key' binding. 4.2: List of reductors ---------------------- *> FORALL: int => int This reductor produces 1 iff its argument was consistently nonzero. *> SET: Object => Object This reductor produces a set of all bindings it observed. *> MAP: Object * ^Object => Object This reductor produces a Java Map that maps all keys (left argument) to values (centre argument) observed. Ambiguous mappings raise AmbiguousMapKeyException(k), where `k' is the ambiguous key. *> DEFAULT_MAP: Object -> Object * ^Object => Object This reductor is analogous to MAP, but takes in a "default value". Let `d' be this default value, and `m' the resultant map. Any lookup for a key `k' such that `k' was not bound to a value during the production of `m' will yield the result `d'. *> METHOD_ADAPTER: Object => Object Reduces all versions of its argument with the Java method `m'. `m' must take two objects, two ints, two longs, or two doubles as parameters, and return a value of the same type. If `m' takes ints, longs, or doubles, it must be annotated with one of @DefaultValueInt(default) (for ints) @DefaultValueDouble(default) (for doubles) @DefaultValueLong(default) (for longs) to produce the default value `default' for the reduction. If `m' takes two Objects, `null' is the default value. 5. Structural operations ======================== Often, efficient PQIL compilation depends on knowledge about data structure sizes and other information. For example, when joining two maps over their key, it is preferable to iterate over the smaller map in the outer loop and perform lookups on the bigger map. To defer such decisions to execution time, we use structural operations, indicated by a preceding `%' character in their name. All such operations belong to an evaluation phase that determines when they are executed. They are thus marked with an evaluation phase marker, separated by a colon; for example, the %SCHEDULE operation may be written as %A:SELECT_PATH to indicate that it belongs to evaluation phase A. Evaluation phases are marked similarly to blocks and must thus be properly nested; we identify them with the structural operation %SCHEDULE. A structural operation scheduled for any phase A must always be contained within a %SCHEDULE block for that phase. %> %SCHEDULE: > block Scheduling operation; explicitly schedules operations contained within with the information available at that time. %> %SELECT_PATH: > block Selects an access path from `block', by re-ordering the joins found in both blocks and setting read and write flags for parameters lacking those. %Add example %> %FUSE(indicators): > block Selects fusion opportunities from a set of reductions contained in `block' (at the top level, i.e., `block' must be a block of reductions). The indicators are a set of fusion opportunities that identify mergeable joins across the reductions, as in the following example: %FUSE(#1, #2, #3): *Reduce[FORALL] %SCHEDULE { {#1}ARRAY_LOOKUP_Integer(?a, _, a_x), {#2}ARRAY_LOOKUP_Integer(?b, _, b_y) ;; GT_Int(?a_x, ?b_y) } *Reduce[FORALL] %SCHEDULE { {#1}ARRAY_LOOKUP_Integer(?a, _, a_x), {#3}ARRAY_LOOKUP_Integer(?c, _, c_y) ;; GT_Int(?a_x, ?c_y) } *Reduce[FORALL] %SCHEDULE { {#2}ARRAY_LOOKUP_Integer(?b, _, b_x), {#3}ARRAY_LOOKUP_Integer(?c, _, c_y) ;; GT_Int(?b_x, ?c_y) } 6. Join attributes ================== Joins of all kinds (including reductions and structural operations) have a certain set of attributes that are used during access path selection and loop fusion. Some of these properties can only be determined if certain information is known about existing variable bindings. The relevant properties are the following: - accessPathSelected: Whether or not there is a %SCHEDULE block contained in one of the branches/blocks of the relevant join - size: The maximum number of bindings produced by this join - accessCost: The expected average number of uncached memory accesses for one binding (data cache misses only) - selectivity: The average probability (for each possible binding) that the binding is realised Thus, size * selectivity are the mean (expected) value of bindings for a given join, ignoring all other parameters, and size * accessCost is the expected total cost for iterating through all viable bindings (referred to as fullCost below). Note that most of the selectivities are guesses and could be refined through sampling etc. Heuristics: - likelihood of matching arbitrary int: 0.01 - likelihood of matching arbitrary long or object: 0.001 - likelihood of matching arbitrary floating point number: 0.0001 - likelihood of inequality succeeding: 0.5 - size of unknown container: 1000 size accessCost selectivity Join 1 0 1 TRUE 0 0 0 FALSE 1 0 read(c)? 0.01 : 1 {ADD,SUB,MUL,DIV,MOD,BITOR,BITAND,BITXOR,BITSHL,BITSHR,BITSSHR}_Int (a, b; c) 1 0 read(c)? 0.001 : 1 {ADD,SUB,MUL,DIV,MOD,BITOR,BITAND,BITXOR,BITSHL,BITSHR,BITSSHR}_Long (a, b; c) 1 0 read(c)? 0.00001 : 1 {ADD,SUB,MUL,DIV,MOD,BITOR,BITAND,BITXOR,BITSHL,BITSHR,BITSSHR}_Double (a, b; c) 1 0 read(c)? 0.01 : 1 {BITINV,EQ}_Int (a; c) 1 0 read(c)? 0.001 : 1 {BITINV,EQ}_Long (a; c) 1 0 read(c)? 0.00001 : 1 {EQ}_Double (a; c) 1 0 read(c)? 0.001 : 1 EQ_{String, Object} (a; c) 1 0 read(c)? 0.99 : 1 NEQ_Int (a, c) 1 0 read(c)? 0.999 : 1 NEQ_{Long, String, Object} (a, c) 1 0 read(c)? 0.99999 : 1 NEQ_Double (a, c) 1 0 r(b)? 0.5 : 1 NEG_{Int,Long,Double} (a; b) 1 0 0.5 {LT,LTE}_{Int,Long,Double} (a, b) 1 1 r(b)? 0.01 : 1 {SET,POLY}_SIZE (a; b) 1 1 r(b)? 0.01 : 1 MAP_SIZE (a; b) 1 1 r(b)? 0.01 : 1 {INT,LONG,DOUBLE,OBJECT,BOOLEAN,SHORT,CHAR,FLOAT,BYTE}_ARRAY_SIZE (a; b) 1 1 r(b)? 0.001 : 1 FIELD (a; b) 1 10 1 INSTANTIATE (...) 1 0 r(b)? 0.5 : 1 COERCE_Boolean (a; b) 1 0 r(b)? 1/256 : 1 COERCE_Byte (a; b) 1 0 r(b)? 1/65536 : 1 COERCE_{Short,Char} (a; b) 1 0 r(b)? 0.00001 : 1 COERCE_Float (a; b) r(b)? 1:size(a) 10 r(b)? 0.001 : 1 CONTAINS (?a; !b) r(c)? 1:b-a+1 0 r(c)? 0.01 : 1 INT_RANGE_CONTAINS (a, b; c) r(c)? 1:b-a+1 0 r(c)? 0.001 : 1 LONG_RANGE_CONTAINS (a, b; c) size(a) 1 1 (ARRAY_)?LOOKUP(.*) (a; !b, !c) 1 1 1 (ARRAY_)?LOOKUP(.*) (a; ?b, !c) size(a) 1 1 / size(a) (ARRAY_)?LOOKUP(.*) (a; !b, ?c) 1 1 0.001 (POLY_)?LOOKUP (a; ?b, ?c) 1 1 0.5 ARRAY_LOOKUP_Boolean (a; ?b, ?c) 1 1 1/256 ARRAY_LOOKUP_Byte (a; ?b, ?c) 1 1 1/65536 ARRAY_LOOKUP_{Char,Short} (a; ?b, ?c) 1 1 0.01 ARRAY_LOOKUP_Int (a; ?b, ?c) 1 1 0.001 ARRAY_LOOKUP_{Long, Object} (a; ?b, ?c) 1 1 0.0001 ARRAY_LOOKUP_{Double,Float} (a; ?b, ?c) 1000 10 1 JAVA_TYPE (!a) 1 1 0.1 JAVA_TYPE (?a) 2^32 0 1 INT (!a) 1 0 1 INT (?a) 2^64 0 1 LONG (!a) 1 0 1 LONG (?a) 2 0 1 BOOLEAN (!a) 1 0 0.0001 (1/2^31) BOOLEAN (?a) 65536 0 1 {CHAR,SHORT} (!a) 1 0 0.01 (1/65536) {CHAR,SHORT} (?a) 256 0 1 BYTE (!a) 1 0 0.001 (1/2^48) BYTE (?a) size(a)*size(b) ac(a) + ac(b) slc(a) * slc(b) {a; b} size(a)+size(b) ac(a) ^ ac(b) slc(a) ^ slc(b) [a | b] 1 ac(block) 1 Bool(!a): block 1 ac(block) 0.5 Bool(?a): block 1 ac(block) 1 NoFail: block 1 ac(block) 1 - slc(block) Not: block 1 fullCost(body) 1 Reduction[reductor_0, ... reductor_k]: body where a^b means `weighted average of a and b' 6.1 Linearity ------------- A specific join instance is linear iff it can produce at most one binding. Linearity is useful for certain compiler optimisations. Below we detail under what conditions a join is linear. We mark `+' for zero or one, `1' for always one, `0' for always zero, and `-' for `not linear'. linear? Join 1 TRUE 0 FALSE + {ADD,SUB,MUL,DIV,MOD,BITOR,BITAND,BITXOR,BITSHL,BITSHR,BITSSHR}_{Int,Long,Double} (a, b; ?c) 1 {ADD,SUB,MUL,DIV,MOD,BITOR,BITAND,BITXOR,BITSHL,BITSHR,BITSSHR}_{Int,Long,Double} (a, b; !c) + {BITINV,EQ}_{Int,Long,Double,String} (a; ?c) 1 {BITINV,EQ}_{Int,Long,Double,String} (a; !c) + NEQ_{Int,String,Object,Double} (a, c) + NEG_{Int,Long,Double} (a; ?b) 1 NEG_{Int,Long,Double} (a; !b) + {LT,LTE}_{Int,Long,Double} (a, b) + {SET,POLY,MAP}_SIZE (a; ?b) 1 {SET,POLY,MAP}_SIZE (a; !b) + {INT,LONG,DOUBLE,OBJECT,BOOLEAN,SHORT,CHAR,FLOAT,BYTE}_ARRAY_SIZE (a; ?b) 1 {INT,LONG,DOUBLE,OBJECT,BOOLEAN,SHORT,CHAR,FLOAT,BYTE}_ARRAY_SIZE (a; !b) + FIELD (a; ?b) 1 FIELD (a; !b) 1 INSTANTIATE (...) + COERCE_{Boolean,Byte,Short,Char,Float} (a; ?b) 1 COERCE_{Boolean,Byte,Short,Char,Float} (a; !b) + CONTAINS (?a; ?b) - CONTAINS (?a; !b) + {INT,LONG}_RANGE_CONTAINS (a, b; ?c) - {INT,LONG}_RANGE_CONTAINS (a, b; !c) + {ARRAY_,POLY_}?LOOKUP(.*) (a; ?b, ?c) + {ARRAY_,POLY_}?LOOKUP(.*) (a; ?b, !c) - {ARRAY_,POLY_}?LOOKUP(.*) (a; !b, ?c) - {ARRAY_,POLY_}?LOOKUP(.*) (a; !b, !c) - JAVA_TYPE (!a) + JAVA_TYPE (?a) - {INT,LONG,BOOLEAN,CHAR,SHORT,BYTE} (!a) + {INT,LONG,BOOLEAN,CHAR,SHORT,BYTE} (?a) linear(a) | linear(b) {a; b} (where (|) symmetric, + | - = -; - | - = -; 1 | x = x; 0 | x = 0; + | + = +) - [a | b] 1 Bool(!a): block + Bool(?a): block 1 NoFail: block + Not: block + Reduction[reductor_0, ... reductor_k]: body 1 TRUE 0 FALSE + {ADD,SUB,MUL,DIV,MOD,BITOR,BITAND,BITXOR,BITSHL,BITSHR,BITSSHR}_{Int,Long,Double} (a, b; ?c) 1 {ADD,SUB,MUL,DIV,MOD,BITOR,BITAND,BITXOR,BITSHL,BITSHR,BITSSHR}_{Int,Long,Double} (a, b; !c) + {BITINV,EQ}_{Int,Long,Double,String} (a; ?c) 1 {BITINV,EQ}_{Int,Long,Double,String} (a; !c) + NEQ_{Int,String,Object,Double} (a, c) + NEG_{Int,Long,Double} (a; ?b) 1 NEG_{Int,Long,Double} (a; !b) + {LT,LTE}_{Int,Long,Double} (a, b) + {SET,POLY,MAP}_SIZE (a; ?b) 1 {SET,POLY,MAP}_SIZE (a; !b) + {INT,LONG,DOUBLE,OBJECT,BOOLEAN,SHORT,CHAR,FLOAT,BYTE}_ARRAY_SIZE (a; ?b) 1 {INT,LONG,DOUBLE,OBJECT,BOOLEAN,SHORT,CHAR,FLOAT,BYTE}_ARRAY_SIZE (a; !b) + FIELD (a; ?b) 1 FIELD (a; !b) 1 INSTANTIATE (...) + COERCE_{Boolean,Byte,Short,Char,Float} (a; ?b) 1 COERCE_{Boolean,Byte,Short,Char,Float} (a; !b) + CONTAINS (?a; ?b) + {INT,LONG}_RANGE_CONTAINS (a, b; ?c) + {ARRAY_,POLY_}?LOOKUP(.*) (a; ?b, ?c) + {ARRAY_,POLY_}?LOOKUP(.*) (a; ?b, !c) + JAVA_TYPE (?a) + {INT,LONG,BOOLEAN,CHAR,SHORT,BYTE} (?a) 1 Bool(!a): block + Bool(?a): block 1 NoFail: block + Not: block + Reduction[reductor_0, ... reductor_k]: body 7. Implementation notes ======================= Allocation during evaluation can currently occur in the following situations: - any boxing coercion - any object-creating reduction (reset, eval) - reductor copying - Instantiation - `equals' checks during: - Reduction of MAP and DEFAULT_MAP - Reduction of SET - LOOKUP - CONTAINS 8. Critique =========== - tuple constructor and deferred instantiation missing Implementation critique ----------------------- - pretty-printing doesn't use the variable notation from this document - %SCHEDULE missing - %SELECT_PATH missing - %FUSE missing 9. Changes ========== from 0.5.1 ---------- - added POLY_LOOKUP and POLY_SIZE - added Section 6.1 from 0.5 -------- - Added POLY_LOOKUP and POLY_SIZE from 0.4 -------- - %SELECT_PATH only has one parameter now - Removed IfThenElse control structure - Removed Exists reductor - Added disjunctive blocks: [ | ] - Updated access path selection from 0.3 -------- - Removed array creation reductors. May be re-introduced in the future. - Removed FORALL, EXISTS reductors - Renamed FORALL_Manifest and EXISTS_Manifest reductors to FORALL, EXISTS - Renamed Reduce `Reduction' - Removed unnecessary second branch to `Reduction' - Renamed Instantiation `Instantiate' - Added `NoFail' control structure - Added `NEQ_String' - Renamed RANGE_CONTAINS to `INT_RANGE_CONTAINS' - Added `LONG_RANGE_CONTAINS' - Renamed SetReductor to `SET' - Renamed MapReductor to `MAP' - Renamed MethodAdapterReductor to `METHOD_ADAPTER' - clarified requirements on for `METHOD_ADAPTER' - Added `DEFAULT_MAP' reductor - Mentioned that `equals' may be called and trigger allocation in some circumstances (Section 5) - Defined inner/outer parameters, added example (Section 4) - Defined nested reductors (Section 4.1) - Put list of reductors into new subsection, Section 4.2. - Added Section 5 - Added Section 6 Earlier changes --------------- (not recorded)