Homomorphism (API documentation of hlt.language packages)
Date: 2013-01-30

hlt.language.design.kernel

## Class Homomorphism

- java.lang.Object
- - hlt.language.design.kernel.Expression
  - - hlt.language.design.kernel.ProtoExpression
    - - hlt.language.design.kernel.Homomorphism

- All Implemented Interfaces:
    Locatable
  Direct Known Subclasses:
    FilterHomomorphism

      public class Homomorphism
      extends ProtoExpression

  This is the class of objects denoting (monoid) homomorphisms. Such an expression means to iterate through a collection, applying a function to each element, accumulating the results along the way with an operation, and returning the end result. More precisely, it is the built-in version of the general computation scheme whose instance is the following "hom" functional, which may be formulated recursively, for the case of a list collection, as:

            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:

  - the collection iterated over - of type `c1(A)`;
  - the iterated function applied to each element - of type `A -> c2(B)`; and,
  - the operation "adding" an element to a collection - of type `B,c2(B) -> c2(B)`.
  A primitive homomorphism computing a value of type `B` consists of:
  - the collection iterated over - of type `c1(A)`;
  - the iterated function applied to each element - of type `A -> B`; and,
  - the monoid operation - of type `B,B -> B`.

  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.

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `static byte` | `DEFAULT_IN_PLACE`
    `static byte` | `DISABLED_IN_PLACE`
    `static byte` | `ENABLED_IN_PLACE`

    - ### Fields inherited from class hlt.language.design.kernel.Expression

      `VOID_ASSIGNMENTS`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `Homomorphism(Expression collection, Expression function, Expression operation, Expression identity)`
    `Homomorphism(Expression collection, Expression function, Expression operation, Expression identity, boolean inPlace)`

  - ### Method Summary

    Methods
    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)` Checking the type of a homomorphism depends on whether the homomorphism is...
    `Expression` | `typedCopy()` Returns a deep copy of this expression this and all its subexpressions share the same type as their copy's counterparts.

    - ### Methods inherited from class hlt.language.design.kernel.ProtoExpression

      `checkedType, setCheckedType, setType, type, typeRef`

    - ### Methods inherited from class hlt.language.design.kernel.Expression

      `addType, 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, typeCheckLocked`

    - ### Methods inherited from class java.lang.Object

      `equals, getClass, hashCode, notify, notifyAll, wait, wait, wait`

- - ### Field Detail

    - #### DEFAULT_IN_PLACE

          public static final byte DEFAULT_IN_PLACE

      See Also:
        Constant Field Values

    - #### ENABLED_IN_PLACE

          public static final byte ENABLED_IN_PLACE

      See Also:
        Constant Field Values

    - #### DISABLED_IN_PLACE

          public static final byte DISABLED_IN_PLACE

      See Also:
        Constant Field Values

  - ### Constructor Detail

    - #### Homomorphism

          public Homomorphism(Expression collection,
                      Expression function,
                      Expression operation,
                      Expression identity)

    - #### Homomorphism

          public Homomorphism(Expression collection,
                      Expression function,
                      Expression operation,
                      Expression identity,
                      boolean inPlace)

  - ### Method Detail

    - #### copy

          public Expression copy()

      Description copied from class: `Expression`
      Returns a deep copy of this expression. The types are not not copied. NB: This is a convenience for building expressions that should be used exclusively before any processing (in particular sanitizing), is done on this expression.
      Specified by:
        `copy` in class `Expression`

    - #### typedCopy

          public Expression typedCopy()

      Description copied from class: `Expression`
      Returns a deep copy of this expression this and all its subexpressions share the same type as their copy's counterparts. NB: This is a convenience for building expressions that should be used exclusively before any processing (in particular sanitizing), is done on this expression.
      Specified by:
        `typedCopy` in class `Expression`

    - #### numberOfSubexpressions

          public int numberOfSubexpressions()

      Returns the number of subexpressions
      Overrides:
        `numberOfSubexpressions` in class `Expression`

    - #### subexpression

          public Expression subexpression(int n)
                                   throws NoSuchSubexpressionException

      Returns the n-th subexpression of this expression; if there is no subexpression at the given position, this throws a `NoSuchSubexpressionException`
      Overrides:
        `subexpression` in class `Expression`
      Throws:
        `NoSuchSubexpressionException`

    - #### setSubexpression

          public Expression setSubexpression(int n,
                                    Expression expression)
                                      throws NoSuchSubexpressionException

      Description copied from class: `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`
      Overrides:
        `setSubexpression` in class `Expression`
      Throws:
        `NoSuchSubexpressionException`

    - #### setSlicings

          public final void setSlicings(ArrayList slicings)

    - #### setSlicings

          public final void setSlicings(Expression[] slicings)

    - #### enableInPlace

          public final Homomorphism enableInPlace()

    - #### disableInPlace

          public final Homomorphism disableInPlace()

    - #### setCheckedType

          public void setCheckedType()

      Description copied from class: `Expression`
      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.
      Specified by:
        `setCheckedType` in class `Expression`

    - #### typeCheck

          public void typeCheck(TypeChecker typeChecker)
                         throws TypingErrorException

      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)

      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`.

      Specified by:
        `typeCheck` in class `Expression`
      Throws:
        `TypingErrorException`

    - #### compile

          public void compile(Compiler compiler)

      Description copied from class: `Expression`
      This method compiles this expression in the context of the specified `Compiler`.
      Specified by:
        `compile` in class `Expression`

    - #### toString

          public java.lang.String toString()

      Overrides:
        `toString` in class `java.lang.Object`