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)