Skip to content

Equivalence Classes

Andrew Johnson edited this page Jan 16, 2025 · 21 revisions

Equivalence Classes are an important concept used throughout the compiler.

Operations on Classes

Set operations are used to manipulate objects and their classes. Some common operations include:

  • without-<class> remove information
  • with-<class> add information (strong)
  • guess-<class> add information (weak)
  • with-only-<class> add & normalize information (strong)
  • guess-only-<class> add & normalize information (weak)
  • has-<class> query whether information is present (strong)
  • is-<class> query whether conjugate satisfies a predicate (strong)

Type Classes

Some common type classes include:

  • representation
  • size
  • fields
  • fields-size
  • datatype-normal
  • datatype-tag
  • property
  • proposition

Type Slots

Type Slots are similar to classes but are much more specific. A Slot is a single Ground Type possibly with some parameters but nothing else.

  • with-slot add information
  • with-only-slot narrow information
  • without-slot remove information

Normalized / Denormalized

A type is said to be normalized when it contains only the minimal amount of information to uniquely identify itself.

A type is said to be denormalized when it contains the maximum amount of information that can be strongly inferred from its normal form.