* *
* 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 lambda(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', lambda 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.
*/
public class Homomorphism extends ProtoExpression
{
/**
* This is the collection over which the iteration is performed.
*/
private Expression _collection;
/**
* This is the function applied to each element of the collection.
*/
private Expression _function;
/**
* This is the accumulation operation of the image monoid.
*/
private Expression _operation;
/**
* This is the identity element of the image monoid.
*/
private Expression _identity;
/**
* This flag indicates whteher this is an in-place homomorphism.
*/
private byte _inPlace = _DEFAULT_IN_PLACE;
private static final byte _DEFAULT_IN_PLACE = 0;
private static final byte _ENABLED_IN_PLACE = 1;
private static final byte _DISABLED_IN_PLACE = 2;
public Homomorphism (Expression collection, Expression function,
Expression operation, Expression identity)
{
_collection = collection;
_function = function;
_operation = operation;
_identity = identity;
}
public Homomorphism (Expression collection, Expression function,
Expression operation, Expression identity, boolean inPlace)
{
this(collection,function,operation,identity);
if (inPlace)
enableInPlace();
else
disableInPlace();
}
public final Homomorphism enableInPlace ()
{
_inPlace = _ENABLED_IN_PLACE;
return this;
}
public final Homomorphism disableInPlace ()
{
_inPlace = _DISABLED_IN_PLACE;
return this;
}
public final Expression sanitizeNames (ParameterStack parameters, ClassTypeHandle handle)
{
_collection = _collection.sanitizeNames(parameters, handle);
_function = _function.sanitizeNames(parameters, handle);
_operation = _operation.sanitizeNames(parameters, handle);
_identity = _identity.sanitizeNames(parameters, handle);
return this;
}
public final void sanitizeSorts (Enclosure enclosure)
{
_collection.sanitizeSorts(enclosure);
_function.sanitizeSorts(enclosure);
_operation.sanitizeSorts(enclosure);
_identity.sanitizeSorts(enclosure);
}
public final Expression shiftOffsets (int intShift, int realShift, int objectShift,
int intDepth, int realDepth, int objectDepth)
{
_collection = _collection.shiftOffsets(intShift,realShift,objectShift,
intDepth,realDepth,objectDepth);
_function = _function.shiftOffsets(intShift,realShift,objectShift,
intDepth,realDepth,objectDepth);
_operation = _operation.shiftOffsets(intShift,realShift,objectShift,
intDepth,realDepth,objectDepth);
_identity = _identity.shiftOffsets(intShift,realShift,objectShift,
intDepth,realDepth,objectDepth);
return this;
}
public final void setCheckedType ()
{
if (isSetCheckedType()) return;
_collection.setCheckedType();
_function.setCheckedType();
_operation.setCheckedType();
_identity.setCheckedType();
setCheckedType(type().copy());
}
/**
*
* Checking the type of a homomorphism depends on whether the homomorphism is...
*
*
* 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)
*
*
*
*
* 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. */ public final void typeCheck (TypeChecker typeChecker) throws TypingErrorException { if (typeCheckLocked()) return; Type elementType = new TypeParameter(); // type A in comment above Type imageType = new TypeParameter(); // type B in comment above // Global collection = Global.dummyCollection(); // collection.typeCheck(typeChecker); // _collection.typeCheck(collection.typeRef(),typeChecker); _collection.typeCheck(Global.dummyCollection(),typeChecker); _identity.typeCheck(_type,typeChecker); Type shadowType = new TypeParameter(); // shadow of _type /* workaround [1] */ typeChecker.prove(new BaseTypeGoal(_collection,elementType)); typeChecker.prove(new ShadowUnifyGoal(shadowType,_type)); /* workaround [1] */ //FunctionType opType = new FunctionType(imageType,_type,_type); /* original [1] */ FunctionType opType = new FunctionType(imageType,shadowType,_type); /* workaround [1] */ _operation.typeCheck(opType,typeChecker); FunctionType funType = new FunctionType(elementType,_type); _function.typeCheck(funType,typeChecker); if (type().rank() == imageType.value().rank()) // do this image type check only for a primitive homomorphism //typeChecker.typeCheck(new UnifyGoal(_type,imageType)); /* original [2] */ typeChecker.prove(new ShadowUnifyGoal(_type,imageType)); /* workaround [2] */ else // do this base type check only for a collection homomorphism typeChecker.prove(new BaseTypeGoal(this,imageType)); } /** * Return true iff this is a collection homomorphism - i.e., iff the * operation is not strictly speaking a monoid operation (i.e., taking two * arguments of a type and return a result of same type), but a collection-add * operation (whose first argument type is the base type of the collection type * of the second argument and the result). Thus, to determine that this is a * collection homomorphism, it is sufficient to check that the second domain * type's rank is equal to the first domain type's rank plus one. */ private final boolean _isCollection () { FunctionType otype = (FunctionType)_operation.checkedType(); return otype.domain(1).rank() == 1 + otype.domain(0).rank(); } /** * Return true iff this is an in-place homomorphism. */ private final boolean _isInPlace () { if (_inPlace == _DEFAULT_IN_PLACE) return _isCollection(); return _inPlace == _ENABLED_IN_PLACE; } /** * This fixes the boxing of the monoid operator and identity by systematically unboxing * all occurrenced of the collection element type. This is a necessary hack [:( sigh!] * because collection-building built-in dummy instructions like SET_ADD have a * needlessly polymorphic type that becomes instantiated only when it is applied. However, * a homomorphism construct compiles the operation as a non-applied closure. This fix * will avoid boxing the types corresponding to the collection's elements. */ private final void _fixTypeBoxing () { Type itype = _identity.checkedType(); FunctionType otype = (FunctionType)_operation.checkedType(); FunctionType ftype = (FunctionType)_function.checkedType(); if (itype.kind() == Type.BOXABLE) ((BoxableTypeConstant)itype).setBoxed(false); if (otype.domain(0).kind() == Type.BOXABLE) { ((BoxableTypeConstant)otype.domain(0)).setBoxed(false); otype.unsetDomainBox(0); if (otype.domain(0).isEqualTo(otype.domain(1))) // primitive homomorphism { ((BoxableTypeConstant)otype.domain(1)).setBoxed(false); otype.unsetDomainBox(1); ((BoxableTypeConstant)otype.range()).setBoxed(false); otype.unsetRangeBox(); } } if (ftype.domain(0).kind() == Type.BOXABLE) { ((BoxableTypeConstant)ftype.domain(0)).setBoxed(false); ftype.unsetDomainBox(0); } } public final void compile (Compiler compiler) { _fixTypeBoxing(); _identity.compile(compiler); if (!_isInPlace()) _operation.compile(compiler); _function.compile(compiler); _collection.compile(compiler); if (_isInPlace()) switch (((Collection)_collection.checkedType()).baseType().sort()) { case Type.INT_SORT: compiler.generate(_isCollection() ? Instruction.APPLY_IP_COLL_HOM_I : Instruction.APPLY_IP_HOM_I); break; case Type.REAL_SORT: compiler.generate(_isCollection() ? Instruction.APPLY_IP_COLL_HOM_R : Instruction.APPLY_IP_HOM_R); break; default: compiler.generate(_isCollection() ? Instruction.APPLY_IP_COLL_HOM_O : Instruction.APPLY_IP_HOM_O); } else switch (((Collection)_collection.checkedType()).baseType().sort()) { case Type.INT_SORT: compiler.generate(_isCollection() ? new ApplyIntCollectionHomomorphism(_tally()) : Instruction.APPLY_HOM_I); break; case Type.REAL_SORT: compiler.generate(_isCollection() ? new ApplyRealCollectionHomomorphism(_tally()) : Instruction.APPLY_HOM_R); break; default: compiler.generate(_isCollection() ? new ApplyObjectCollectionHomomorphism(_tally()) : Instruction.APPLY_HOM_O); } } private final Instruction _tally () { switch (((FunctionType)_operation.checkedType()).domain(0).sort()) { case Type.INT_SORT: return Instruction.APPLY_COLL_I; case Type.REAL_SORT: return Instruction.APPLY_COLL_R; } return Instruction.APPLY_COLL_O; } public final String toString () { return "hom("+_collection+","+_function+","+_operation+","+_identity+")"; } // Added by PV public final String toTypedString () { return typed("hom("+_collection.toTypedString()+"," +_function.toTypedString()+"," +_operation.toTypedString()+"," +_identity.toTypedString()+")"); } /** * Same as above, but may not be called until this homomomorphism has been fully * type-checked - otherwise, crashes on non-existing types. */ public final String typeCheckedToString () { return (_isCollection() ? "collection_" : "primitive_") + "hom("+ _collection + " : " + _collection.checkedType() + "," + _function + " : " + _function.checkedType() + "," + _operation + " : " + _operation.checkedType() + "," + _identity + " : " + _identity.checkedType() + "," + _inPlace + " : " + _inPlace() + ") : " + _checkedType; } private final String _inPlace () { switch (_inPlace) { case _ENABLED_IN_PLACE: return "enabled in place"; case _DISABLED_IN_PLACE: return "disabled in place"; } return "default: "+(_isInPlace()?"in ":"not in ")+"place"; } }