public class Homomorphism extends ProtoExpression
hom[list,op,id](f) = if isEmpty(list)
then id
else op(f(head(list)),
hom[tail(list),op,id](f))
Clearly, this scheme extends a function f to a homomorphism of monoids, from the monoid of lists to the monoid defined by (op,id).
Thus, an object of this class denotes the result of applying such a homomorphic extension of a function (f) to an element of collection monoid (i.e., a data structure such as a set, a list, or a bag), the image monoid being implicitly defined by the binary operation (op) - also called the accumulation operation. It is made to work iteratively.
For technical reasons, we need to treat specially so-called collection homomorphisms; i.e., those whose accumulation operation constructs a collection, such as a set. Although a collection homomorphism can conceptualy be expressed with the general scheme, the function applied to an element of the collection will return a collection (i.e., a free monoid) element, and the result of the homomorphism is then the result of tallying the partial collections coming from applying the function to each element into a final "concatenation."
Other (non-collection) homomorphisms are called primitive homomorphisms. For those, the function applied to all elements of the collection will return a computed element that may be directly composed with the other results. Thus, the difference between the two kinds of (collection or primitive) homomorphisms will appear in the typing and the code generated (a collection homomorphism requiring an extra loop for tallying partial results into the final collection). It is easy to make the distinction between the two kinds of homomorphisms thanks to the type of the accumulation operation (see below).
Therefore, a collection homomorphism expression constructing a collection of type c2(B) consists of:
Even though the scheme of computation for homomorphisms described above is correct, it is not often used, especially when the function already encapsulates the accumulation operation, as is always the case when the homomorphism comes from the desugaring of a comprehension - see below). Then, such a homomorphism will directly side-effect the structure specified as the identity element with a function of the form λx.op(x,id) and dispense altogether with the need to accumulate intermediate results. We shall call those homomorphisms in-place homomorphisms. To distinguish them and enable the suprression of intermediate computations, a flag indicating that the homomorphism is to be computed in-place is provided. Both primitive and collection homomorphisms can be specified to be in-place. If nothing regarding in-place computation is specified for a homomorphism, the default behavior will depend on whether the homomorphism is collection (default is in-place), or primitive (default is not in-place). Methods to override the defaults are provided.
For an in-place homomorphism, the iterated function encapsulates the operation, which affects the identity element, which thus accumulates intermediate results and no further composition using the operation is needed. This is especially handy for collections that are often represented, for (space and time) efficiency reasons, by iteratable bulk structures constructed by allocating an empty structure that is filled in-place with elements using a built-in "add" method guaranteeing that the resulting data structure is canonical - i.e., that it abides by the algebraic properties of its type of collection (e.g., adding an element to a set will not create duplicates, etc.).
Although monoid homomorphisms are defined as expressions in the kernel, they are not meant to be represented directly in a surface syntax (although they could, but would lead to rather cumbersome and not very legible expressions). Rather, they are meant to be used for expressing higher-level expressions known as monoid comprehensions, which offer the advantage of the familar (set) comprehension notation used in mathematics, and can be translated into monoid homomorphisms to be type-checked and evaluated.
A monoid comprehension is an expression of the form:
[op,id] { e | q1, ..., qn }
where [op,id] define a monoid, e is an expression, and the
qi's are qualifiers. A qualifier is either a
boolean expression or a pair x <- e, where x is
a variable and e is an expression. The sequence of qualifiers may
also be empty. Such a monoid comprehension is just syntactic sugar that
can be expressed in terms of homomorphisms as follows:
[op,id]{e | } = op(e,id);
[op,id]{e | x <- e', Q} = hom(e', λx.[op,id]{e | Q}, op, id);
[op,id]{e | c, Q} = if c then [op,id]{e | Q} else id;
Thus, monoid comprehensions allow the formulation of "declarative iteration." Note the fact mentioned earlier that a homomorphism coming from the translation of a comprehension encapsulates the operation in its function. Thus, this is generally taken to advantage with operations that cause a side-effect on their second argument to enable an in-place homomorphism to dispense with unneeded intermediate computation.
Comprehensions are also interesting as they may be subject to transformations leading to more efficient evaluation than their simple "nested loops" operational semantics (by using "unnesting" techniques and using relational operations as implementation instructions). At any rate, homomorphisms are here treated "naively" and compiled as simple loops.
| Modifier and Type | Field and Description |
|---|---|
static byte |
DEFAULT_IN_PLACE |
static byte |
DISABLED_IN_PLACE |
static byte |
ENABLED_IN_PLACE |
VOID_ASSIGNMENTS| Constructor and Description |
|---|
Homomorphism(Expression collection,
Expression function,
Expression operation,
Expression identity) |
Homomorphism(Expression collection,
Expression function,
Expression operation,
Expression identity,
boolean inPlace) |
| Modifier and Type | Method and Description |
|---|---|
void |
compile(Compiler compiler)
This method compiles this expression in the context of the specified
Compiler.
|
Expression |
copy()
Returns a deep copy of this expression.
|
Homomorphism |
disableInPlace() |
Homomorphism |
enableInPlace() |
int |
numberOfSubexpressions()
Returns the number of subexpressions
|
void |
setCheckedType()
This method sets the final unambiguously checked type of this expression, possibly
along with other final information that may be needed by the compiler for
generating code.
|
void |
setSlicings(ArrayList slicings) |
void |
setSlicings(Expression[] slicings) |
Expression |
setSubexpression(int n,
Expression expression)
Returns this expression after setting its n-th subexpression to the specified
expression; if there is no subexpression at the given position, this throws a
NoSuchSubexpressionException
|
Expression |
subexpression(int n)
Returns the n-th subexpression of this expression; if there is no subexpression
at the given position, this throws a NoSuchSubexpressionException
|
java.lang.String |
toString() |
void |
typeCheck(TypeChecker typeChecker)
|
Expression |
typedCopy()
Returns a deep copy of this expression this and all its subexpressions share the
same type as their copy's counterparts.
|
checkedType, setCheckedType, setType, type, typeRefaddType, addTypes, boxSort, containsFreeName, enclosingScope, extent, getEnd, getStart, isConstant, isEquality, isFalse, isHiddenSlicing, isNull, isSelector, isSlicing, isTrue, isVoid, locationString, otherTypes, parameters, sanitizeNames, sanitizeSorts, setCheckedTypeLocked, setEnd, setExtent, setOtherTypes, setStart, shiftOffsets, shiftOffsets, sort, substitute, typeCheck, typeCheck, typeCheckLockedpublic static final byte DEFAULT_IN_PLACE
public static final byte ENABLED_IN_PLACE
public static final byte DISABLED_IN_PLACE
public Homomorphism(Expression collection, Expression function, Expression operation, Expression identity)
public Homomorphism(Expression collection, Expression function, Expression operation, Expression identity, boolean inPlace)
public Expression copy()
Expressioncopy in class Expressionpublic Expression typedCopy()
ExpressiontypedCopy in class Expressionpublic int numberOfSubexpressions()
numberOfSubexpressions in class Expressionpublic Expression subexpression(int n) throws NoSuchSubexpressionException
subexpression in class ExpressionNoSuchSubexpressionExceptionpublic Expression setSubexpression(int n, Expression expression) throws NoSuchSubexpressionException
ExpressionsetSubexpression in class ExpressionNoSuchSubexpressionExceptionpublic final void setSlicings(ArrayList slicings)
public final void setSlicings(Expression[] slicings)
public final Homomorphism enableInPlace()
public final Homomorphism disableInPlace()
public void setCheckedType()
ExpressionsetCheckedType in class Expressionpublic void typeCheck(TypeChecker typeChecker) throws TypingErrorException
Primitive: OR Collection:
_collection : from_collection(A) _collection : from_collection(A)
_function : A -> B _function : A -> to_collection(B)
_operation : B,B -> B _operation : B, to_collection(B) -> to_collection(B)
_identity : B _identity : to_collection(B)
this : B this : to_collection(B)
Also, if slicing expressions are present, they must be typed as booleans.
NB: In order to accommodate primitive homomorphisms whose monoid operation is not strictly-speaking internal but may involve subtyping, we use a work-around that consists of unifying the shadow types of the operation's arguments rather than the types themselves. The changes from the lines needed for typing such "loose" monoids are marked explicitly and the original lines they replace are commented out. Unifying shadow types is done using a special goal: a ShadowUnifyGoal.
typeCheck in class ExpressionTypingErrorExceptionpublic void compile(Compiler compiler)
Expressioncompile in class Expressionpublic java.lang.String toString()
toString in class java.lang.Object