Program penalties

When compiling an ambiguous MMX program, certain meanings may be preferred to others. For instance, given functions

forall (T: Class) {
  downgrade: Alias T -> T;
  postfix []: (Vector T, T, Int) -> T
  postfix []: (Alias Vector T, T, Int) -> Alias T
}

and the fragment of code

v: Vector String := [ "Hi", "there" ];
x: String == v[0];

the expression v[0] :> String has two possible meanings, depending on whether we used the read-only or read/write accessor for obtaining the first element of the array. Since we will never modify v[0] in this sample, read-only access should therefore be preferred.

The Mathemagix compiler implements a fine-grained mechanism for attaching penalties to the possible meanings of an ambiguous MMX program. These penalties form a partially ordered set and one meaning should be preferred over another if its attached penalty is strictly lower.

Internal representation of penalties

Internally, a penalty has type Penalty and is encoded by an expression tree of type GEN (which equals Generic), each subtree being either of type Literal or Compound. The private conversion routines between the types Penalty and GEN are postfix .v and penalty. The public routines for the syntactic manipulation of penalties are

penalty$literal: Literal -> Penalty

literal?: Penalty -> Boolean

convert: Penalty -> Literal

Creation of a leaf, testing whether a penalty is a leaf and converting a leaf to a literal.

$union: Tuple Literal -> Penalty

Conjunction of several literal penalties. To do: Tuple GEN or Tuple Literal?

postfix (): (Penalty, Tuple Penalty) -> Penalty

compound?: Penalty -> Boolean

prefix #: Penalty -> Int

postfix []: (Penalty, Int) -> Penalty

Creation of a compound tree, testing whether a penalty is a compound tree, obtaining the arity of a compound tree and accessing a child of a compound tree.

Standard built-in penalties

penalty$none: Penalty

No penalty.

penalty$automatic: Penalty

Low penalty for the convertion Alias T ~> T.

penalty$inclusion: Penalty

Penalty to be used for a type conversion T ~> U when T is mathematically included in U.

penalty$homomorphism: Penalty

Penalty for mathematical homomorphisms, such as .

penalty$cast: Penalty

Penalty for casts with loss of mathematical information, such as Floating -> Double.

penalty$access: Penalty

Penalty for write access.

penalty$from_literal: Penalty

Penalty for literal constants.

penalty$fall_back: Penalty

Penalty when no better idea is available.

penalty$panic: Penalty

To be used if all converters fail.

penalty$failed: Penalty

Infinite penalty for invalid conversions.

penalty$convert: Penalty

penalty$promote_generic: Penalty

Penalties for the interpreter, not currently used by the compiler.

Compound penalties

$strict_cross: Tuple Penalty -> Penalty

penalty$cross: Tuple Penalty -> Penalty

Given a tuple (p1, …, pn) of penalties, return the conjunct penalty with the property that (p1, …, pn) <= (q1, …, qn) if and only if pi <= qi for all i. In the case of penalty$cross, we return penalty$failed whenever one of the pi equals penalty$failed, and conjunctive penalties among the pi are expanded. For instance ((p1, p2), p3) is expanded into (p1, p2, p3).

$lex: (p1: Penalty, p2: Penalty) -> Penalty

Lexicographical penalty with $lex (p1, p2) <= $lex (q1, q2) if and only if p1 <= q1 and either !(q1 <= p1) or p2 <= q2.

$up: (p1: Penalty, p2: Penalty) -> Penalty

Penalty for upgraders: given an upgrader T2 -> T3 with penalty p1 and a converter T1 -> T2 with penalty p2, the penalty $up (p1, p2) corresponds to the penalty of the composed converter T1 -> T3. To do: ordering rules.

$down: (p1: Penalty, p2: Penalty) -> Penalty

Penalty for downgraders: given a downgrader T1 -> T2 with penalty p2 and a converter T2 -> T3 with penalty p1, the penalty $down (p1, p2) corresponds to the penalty of the composed converter T1 -> T3. To do: ordering rules.

$context: (ab: ABBR, p: Penalty) -> Penalty

To do: missing documentation.

$from_and: (ab: ABBR, p: Penalty) -> Penalty

To do: missing documentation.

$to_or: (ab: ABBR, p: Penalty) -> Penalty

To do: missing documentation.

Predicates

none?: Penalty -> Boolean

failed?: Penalty -> Boolean

Test whether a penalty is equal to penalty$none resp. penalty$failed.

union?: Penalty -> Boolean

Test whether a penalty is a conjunction of elementary penalties.

cross?: Penalty -> Boolean

lex?: Penalty -> Boolean

down?: Penalty -> Boolean

up?: Penalty -> Boolean

context?: Penalty -> Boolean

from_and?: Penalty -> Boolean

to_or?: Penalty -> Boolean

Predicates for the compound constructs $strict_cross, $lex, $down, $up, $context, $from_and and $to_or.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU General Public License. If you don't have this file, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.