There are two kinds of function definitions. A function or procedure specified with the adjective virtual may have a specialisation provided in an instance declaration. Virtual functions may have definitions, in which case the definition is merely a default. It can be replaced in a specialising instance. However the definition should be taken as a semantic specification which the specialisation should adhere too.

The set of virtual functions of a polymorphic class is known as the basis of the class.

A non-virtual function can be defined in terms of virtual functions and other non-virtual functions. Non virtual functions cannot be specialised by the programmer. Instead, they are automatically specialised by the system for an instance.

A polymorphic class may also contain assertions. These are function like specifications which specify semantic constraints.

An axiom specifies a basic assertion, it specifies a class property in terms of relations between the class functions. Since Felix only supports first order assertional logic, higher order semantics must be specified in comments.

If a class contains virtual functions with definitions, the definition is also considered as axiomatic.

The set of all axioms, including those in comments, is known as the assertional basis or semantic specification of the class. Additionally some reductions may be or imply an extension of the semantic basis.

A lemma is an assertion which can be derived from the semantic specifications by logical reasoning. In particular, lemmas in principle should be self-evident, simple and useful and able to be deduced by an automatic theorm proving program.

A theorem is a more complicated derived assertion, which would be too hard to prove with an automatic theorem prover. Instead, it should be derivable with a proof assistant (such as Coq), given various unspecified strategies, tactics and hints.

This uses some advanced instantiation technology to allow you to define the cartesian product of a sequence of sets using the infix TeX operator \(\otimes\) which is spelled \otimes. There's also a left associative binary operator \(\times\) spelled \times.

share/lib/std/algebra/set.flx

  
  fun \(\times\)[U,V] (x:set_form[U],y:set_form[V]) => 
    { u,v : U * V | u \(\in\) x and v \(\in\) y }
  ;
  
  fun \(\otimes\)[U,V] (x:set_form[U],y:set_form[V]) => 
    { u,v : U * V | u \(\in\) x and v \(\in\) y }
  ;
  
  fun \(\otimes\)[U,V,W] (head:set_form[U], tail:set_form[V*W]) =>
    { u,v,w : U * V * W | u \(\in\) head and (v,w) \(\in\) tail }
  ;
  
  fun \(\otimes\)[NH,OH,OT] (head:set_form[NH], tail:set_form[OH**OT]) =>
    { h,,(oh,,ot) : NH ** (OH ** OT) | h \(\in\) head and (oh,,ot) \(\in\) tail }
  ;
  

An equivalence relation is a reflexive, symmetric, transitive relation. It is one of the most fundamental concepts in mathematics. One can show that for any set \(S\), for any element \(s \in S\), the subset \(\lbrack s\rbrack\) of \(S\) consisting of all elements equivalent to \(s\) are also equivalent to each other, and not equivalent to any other element outside that set.

Therefore, every equivalence relation on a set \(S\) specifies a partition of \(S\) which is a set of subsets of \(S\) known as equivalence classes, or just plain classes, such that no two classes have a common intersection, and the union of the classes spans the whole set.

In other words a partition consists of a disjoint union of subsets.

The most fundamential relation in computing which is required to be an equivalence relation is the equality operator. In particular, it allows us to have distinct encodings of a value, but still consider them equal semantically, and to provide an operational measure of that equivalence.

As a simple example, consider that the rational numbers \(1/2\) and \(2/4\) have distinct encodings but none-the-less are semantically equivalent.

An online reference on Wikibooks

share/lib/std/algebra/equiv.flx

  // equality: technically, equivalence relation
  class Eq[t] {
    virtual fun == : t * t -> bool;
    virtual fun != (x:t,y:t):bool => not (x == y);
  
    axiom reflex(x:t): x == x;
    axiom sym(x:t, y:t): (x == y) == (y == x);
    axiom trans(x:t, y:t, z:t): x == y and y == z implies x == z;
  
    fun eq(x:t, y:t)=> x == y;
    fun ne(x:t, y:t)=> x != y;
    fun \(\ne\)(x:t, y:t)=> x != y;
    fun \(\neq\)(x:t, y:t)=> x != y;
  }
  
  

A proper partial order \(\subset\) spelled \subset is a transitive, antisymmetric irreflexive relation.

We also provide an improper operator \(\subseteq\) spelled \subseteq which is transitive, antisymmetric, and reflexive, for which either the partial order or equivalence operator == applies.

The choice of operators is motivated by the canonical exemplar of subset containment relations.

share/lib/std/algebra/partialorder.flx

  // partial order
  class Pord[t]{
    inherit Eq[t];
    virtual fun \(\subset\): t * t -> bool;
    virtual fun \(\supset\)(x:t,y:t):bool =>y \(\subset\) x;
    virtual fun \(\subseteq\)(x:t,y:t):bool => x \(\subset\) y or x == y;
    virtual fun \(\supseteq\)(x:t,y:t):bool => x \(\supset\) y or x == y;
  
    fun \(\subseteqq\)(x:t,y:t):bool => x \(\subseteq\) y;
    fun \(\supseteqq\)(x:t,y:t):bool => x \(\supseteq\) y;
  
    fun \(\nsubseteq\)(x:t,y:t):bool => not (x \(\subseteq\) y);
    fun \(\nsupseteq\)(x:t,y:t):bool => not (x \(\supseteq\) y);
    fun \(\nsubseteqq\)(x:t,y:t):bool => not (x \(\subseteq\) y);
    fun \(\nsupseteqq\)(x:t,y:t):bool => not (x \(\supseteq\) y);
  
    fun \(\supsetneq\)(x:t,y:t):bool => x \(\supset\) y;
    fun \(\supsetneqq\)(x:t,y:t):bool => x \(\supset\) y;
    fun \(\supsetneq\)(x:t,y:t):bool => x \(\supset\) y;
    fun \(\supsetneqq\)(x:t,y:t):bool => x \(\supset\) y;
  
    axiom trans(x:t, y:t, z:t): \(\subset\)(x,y) and \(\subset\)(y,z) implies \(\subset\)(x,z);
    axiom antisym(x:t, y:t): \(\subset\)(x,y) or \(\subset\)(y,x) or x == y;
    axiom reflex(x:t, y:t): \(\subseteq\)(x,y) and \(\subseteq\)(y,x) implies x == y;
  }

A partial order may bave an upper or lower bound known as the supremum and infimum, respectively. If these values are in the type, they are called the maximum and minimum, respectively.

share/lib/std/algebra/partialorder.flx

  class UpperBoundPartialOrder[T] {
    inherit Pord[T];
    virtual fun upperbound: 1 -> T;
  }
  class LowerBoundPartialOrder[T] {
    inherit Pord[T];
    virtual fun lowerbound: 1 -> T;
  }
  class BoundPartialOrder[T] {
    inherit LowerBoundPartialOrder[T];
    inherit UpperBoundPartialOrder[T];
  }
  
  
  

A total order is a partial order with a totality law.

However we do not derive it from our partial order because we use different comparison operators. Here we use the standard ascii art comparison operators commonly found in programming languages along with the more beautiful TeX operators used in mathematical papers.

The spelling of the TeX operators can be found by holding the mouse over the symbol briefly.

share/lib/std/algebra/totalorder.flx

  // total order
  class Tord[t]{
    inherit Eq[t];
    // defined in terms of <, argument order swap, and boolean negation
  
    // less
    virtual fun < : t * t -> bool;
    fun lt (x:t,y:t): bool=> x < y;
    fun \(\lt\) (x:t,y:t): bool=> x < y;
    fun \(\lneq\) (x:t,y:t): bool=> x < y;
    fun \(\lneqq\) (x:t,y:t): bool=> x < y;
  
  
    axiom trans(x:t, y:t, z:t): x < y and y < z implies x < z;
    axiom antisym(x:t, y:t): x < y or y < x or x == y;
    axiom reflex(x:t, y:t): x < y and y <= x implies x == y;
    axiom totality(x:t, y:t): x <= y or y <= x;
  
  
    // greater
    fun >(x:t,y:t):bool => y < x;
    fun gt(x:t,y:t):bool => y < x;
    fun \(\gt\)(x:t,y:t):bool => y < x;
    fun \(\gneq\)(x:t,y:t):bool => y < x;
    fun \(\gneqq\)(x:t,y:t):bool => y < x;
  
    // less equal
    fun <= (x:t,y:t):bool => not (y < x);
    fun le (x:t,y:t):bool => not (y < x);
    fun \(\le\) (x:t,y:t):bool => not (y < x);
    fun \(\leq\) (x:t,y:t):bool => not (y < x);
    fun \(\leqq\) (x:t,y:t):bool => not (y < x);
    fun \(\leqslant\) (x:t,y:t):bool => not (y < x);
  
  
    // greater equal
    fun >= (x:t,y:t):bool => not (x < y);
    fun ge (x:t,y:t):bool => not (x < y);
    fun \(\ge\) (x:t,y:t):bool => not (x < y);
    fun \(\geq\) (x:t,y:t):bool => not (x < y);
    fun \(\geqq\) (x:t,y:t):bool => not (x < y);
    fun \(\geqslant\) (x:t,y:t):bool => not (x < y);
  
    // negated, strike-through
    fun \(\ngtr\) (x:t,y:t):bool => not (x < y);
    fun \(\nless\) (x:t,y:t):bool => not (x < y);
  
    fun \(\ngeq\) (x:t,y:t):bool => x < y;
    fun \(\ngeqq\) (x:t,y:t):bool => x < y;
    fun \(\ngeqslant\) (x:t,y:t):bool => x < y;
  
    fun \(\nleq\) (x:t,y:t):bool => not (x <= y);
    fun \(\nleqq\) (x:t,y:t):bool => not (x <= y);
    fun \(\nleqslant\) (x:t,y:t):bool => not (x <= y);
    
  
    // maxima and minima
    fun max(x:t,y:t):t=> if x < y then y else x endif;
    fun \(\vee\)(x:t,y:t) => max (x,y);
  
    fun min(x:t,y:t):t => if x < y then x else y endif;
    fun \(\wedge\)(x:t,y:t):t => min (x,y);
  
  
  }

share/lib/std/algebra/totalorder.flx

  class UpperBoundTotalOrder[T] {
    inherit Tord[T];
    virtual fun maxval: 1 -> T = "::std::numeric_limits<?1>::max()";
  }
  class LowerBoundTotalOrder[T] {
    inherit Tord[T];
    virtual fun minval: 1 -> T = "::std::numeric_limits<?1>::min()";
  }
  class BoundTotalOrder[T] {
    inherit LowerBoundTotalOrder[T];
    inherit UpperBoundTotalOrder[T];
  }
  
  

Sequences are discrete total orders.

share/lib/std/algebra/sequence.flx

  
  // Forward iterable
  class ForwardSequence[T] {
    inherit Tord[T];
    virtual fun succ: T -> T;
    virtual proc pre_incr: &T;
    virtual proc post_incr: &T;
  }
  
  // Bidirectional
  class BidirectionalSequence[T] {
    inherit ForwardSequence[T];
    virtual fun pred: T -> T;
    virtual proc pre_decr: &T;
    virtual proc post_decr: &T;
  }
  
  // Bounded Random access totally ordered
  // int should be any integer type really .. fix later
  class RandomSequence[T] {
    inherit BidirectionalSequence[T];
    virtual fun advance : int * T -> T;
  }
  
  // Bounded totally ordered forward iterable
  class BoundForwardSequence[T] {
    inherit ForwardSequence[T];
    inherit UpperBoundTotalOrder[T];
  }
  
  // Bounded totally ordered bidirectional
  class BoundBidirectionalSequence[T] {
    inherit BidirectionalSequence[T];
    inherit BoundTotalOrder[T];
  }
  
  // Bounded Random access totally ordered
  class BoundRandomSequence[T] {
    inherit RandomSequence[T];
    inherit BoundBidirectionalSequence[T];
  }
  

An approximate additive group is a type for which there is a symmetric binary addition operator, a zero element, and for which there is an additive inverse or negation operator.

It is basically an additive group without the associativity requirement, and is intended to apply to floating point numbers.

Note we use the inherit statement to include the functions from class Eq.

share/lib/std/algebra/group.flx

  Additive symmetric float-approximate group, symbol +.
  Note: associativity is not assumed.
  class FloatAddgrp[t] {
    inherit Eq[t];
    virtual fun zero: unit -> t;
    virtual fun + : t * t -> t;
    virtual fun neg : t -> t;
    virtual fun prefix_plus : t -> t = "$1";
    virtual fun - (x:t,y:t):t => x + -y;
    virtual proc += (px:&t,y:t) { px <- *px + y; }
    virtual proc -= (px:&t,y:t) { px <- *px - y; }
  
    axiom sym (x:t,y:t): x+y == y+x;
  /*
    reduce id (x:t): x+zero() => x;
    reduce id (x:t): zero()+x => x;
    reduce inv(x:t): x - x => zero();
    reduce inv(x:t): - (-x) => x;
  */
    fun add(x:t,y:t)=> x + y;
    fun plus(x:t)=> +x;
    fun sub(x:t,y:t)=> x - y;
    proc pluseq(px:&t, y:t) {  += (px,y); }
    proc  minuseq(px:&t, y:t) { -= (px,y); }
  }

A proper additive group is derived from FloatAddgrp with associativity added.

share/lib/std/algebra/group.flx

  Additive symmetric group, symbol +.
  class Addgrp[t] {
    inherit FloatAddgrp[t];
    axiom assoc (x:t,y:t,z:t): (x + y) + z == x + (y + z);
    //reduce inv(x:t,y:t): x + y - y => x;
  }
  

An approximate multiplicative semigroup is a set with a symmetric binary multiplication operator and a unit.

share/lib/std/algebra/group.flx

  Multiplicative symmetric float-approximate semi group with unit symbol *.
  Note: associativity is not assumed.
  class FloatMultSemi1[t] {
    inherit Eq[t];
    proc muleq(px:&t, y:t) { *= (px,y); }
    fun mul(x:t, y:t) => x * y;
    fun sqr(x:t) => x * x;
    fun cube(x:t) => x * x * x;
    virtual fun one: unit -> t;
    virtual fun * : t * t -> t;
    virtual proc *= (px:&t, y:t) { px <- *px * y; }
  /*
    reduce id (x:t): x*one() => x;
    reduce id (x:t): one()*x => x;
  */
  }
  

A multiplicative semigroup with unit is an approximate multiplicative semigroup with unit and associativity and satisfies the cancellation law.

share/lib/std/algebra/group.flx

  Multiplicative semi group with unit.
  class MultSemi1[t] {
    inherit FloatMultSemi1[t];
    axiom assoc (x:t,y:t,z:t): (x * y) * z == x * (y * z);
    //reduce cancel (x:t,y:t,z:t): x * z ==  y * z => x == y;
  }
  

An approximate ring is a set which has addition and multiplication satisfying the rules for approximate additive group and multiplicative semigroup respectively.

share/lib/std/algebra/ring.flx

  Float-approximate ring.
  class FloatRing[t] {
    inherit FloatAddgrp[t];
    inherit FloatMultSemi1[t];
  }
  

A ring is a type which is a both an additive group and multiplicative semigroup with unit, and which in addition satisfies the distributive law.

share/lib/std/algebra/ring.flx

  Ring.
  class Ring[t] {
    inherit Addgrp[t];
    inherit MultSemi1[t];
    axiom distrib (x:t,y:t,z:t): x * ( y + z) == x * y + x * z;
  }

An approximate division ring is an approximate ring with unit with a division operator.

share/lib/std/algebra/ring.flx

  Float-approximate division ring.
  class FloatDring[t] {
    inherit FloatRing[t];
    virtual fun / : t * t -> t; // pre t != 0
    fun \(\over\) (x:t,y:t) => x / y;
  
    virtual proc /= : &t * t;
    virtual fun % : t * t -> t;
    virtual proc %= : &t * t;
  
    fun div(x:t, y:t) => x / y;
    fun mod(x:t, y:t) => x % y;
    fun \(\bmod\)(x:t, y:t) => x % y;
    fun recip (x:t) => #one / x;
  
    proc diveq(px:&t, y:t) { /= (px,y); }
    proc modeq(px:&t, y:t) { %= (px,y); }
  }
  

share/lib/std/algebra/ring.flx

  Division ring.
  class Dring[t] {
    inherit Ring[t];
    inherit FloatDring[t];
  }
  

share/lib/std/algebra/bits.flx

  
  Bitwise operators.
  class Bits[t] {
    virtual fun \^ : t * t -> t = "(?1)($1^$2)";
    virtual fun \| : t * t -> t = "$1|$2";
    virtual fun \& : t * t -> t = "$1&$2";
    virtual fun ~: t -> t = "(?1)(~$1)";
    virtual proc ^= : &t * t = "*$1^=$2;";
    virtual proc |= : &t * t = "*$1|=$2;";
    virtual proc &= : &t * t = "*$1&=$2;";
  
    fun bxor(x:t,y:t)=> x \^ y;
    fun bor(x:t,y:t)=> x \| y;
    fun band(x:t,y:t)=> x \& y;
    fun bnot(x:t)=> ~ x;
  
  }

share/lib/std/algebra/integer.flx

  
  Integers.
  class Integer[t] {
    inherit Tord[t];
    inherit Dring[t];
    inherit RandomSequence[t];
    virtual fun << : t * t -> t = "$1<<$2";
    virtual fun >> : t * t -> t = "$1>>$2";
    virtual proc <<= : &t * t = "*$1<<=$2;";
    virtual proc >>= : &t * t = "*$1>>=$2;";
  
    fun shl(x:t,y:t)=> x << y;
    fun shr(x:t,y:t)=> x >> y;
  }
  
  Signed Integers.
  class Signed_integer[t] {
    inherit Integer[t];
    virtual fun sgn: t -> int;
    virtual fun abs: t -> t;
  }
  
  Unsigned Integers.
  class Unsigned_integer[t] {
    inherit Integer[t];
    inherit Bits[t];
  }
  
  
  

Trigonometric functions are shared by real and complex numbers.

share/lib/std/algebra/trig.flx

  
  Float-approximate trigonometric functions.
  class Trig[t] {
    inherit FloatDring[t];
  
    // NOTE: most of the axioms here WILL FAIL because they require
    // exact equality, but they're only going to succeed with approximate
    // equality, whatever that means. This needs to be fixed!
  
    // circular
    // ref http://en.wikipedia.org/wiki/Circular_functions 
  
    // core trig
    virtual fun sin: t -> t;
    fun \(\sin\) (x:t)=> sin x;
  
    virtual fun cos: t -> t;
    fun \(\cos\) (x:t)=> cos x;
  
    virtual fun tan (x:t)=> sin x / cos x;
    fun \(\tan\) (x:t)=> tan x;
  
    // reciprocals
    virtual fun sec (x:t)=> recip (cos x);
    fun \(\sec\) (x:t)=> sec x;
  
    virtual fun csc (x:t)=> recip (sin x);
    fun \(\csc\) (x:t)=> csc x;
  
    virtual fun cot (x:t)=> recip (tan x);
    fun \(\cot\) (x:t)=> cot x;
  
    // inverses
    virtual fun asin: t -> t;
    fun \(\arcsin\) (x:t) => asin x;
   
    virtual fun acos: t -> t;
    fun \(\arccos\) (x:t) => acos x;
  
    virtual fun atan: t -> t;
    fun \(\arctan\) (x:t) => atan x;
  
    virtual fun asec (x:t) => acos ( recip x);
    virtual fun acsc (x:t) => asin ( recip x);
    virtual fun acot (x:t) => atan ( recip x);
  
    // hyperbolic
    // ref http://en.wikipedia.org/wiki/Hyperbolic_functions
    virtual fun sinh: t -> t;
    fun \(\sinh\) (x:t) => sinh x;
  
    virtual fun cosh: t -> t;
    fun \(\cosh\) (x:t) => cosh x;
  
    virtual fun tanh (x:t) => sinh x / cosh x;
    fun \(\tanh\) (x:t) => tanh x;
  
    // reciprocals
    virtual fun sech (x:t) => recip (cosh x);
    fun \(\sech\) (x:t) => sech x;
  
    virtual fun csch (x:t) => recip (sinh x);
    fun \(\csch\) (x:t) => csch x;
  
    virtual fun coth (x:t) => recip (tanh x); 
    fun \(\coth\) (x:t) => coth x;
  
    // inverses
    virtual fun asinh: t -> t;
  
    virtual fun acosh: t -> t;
  
    virtual fun atanh: t -> t;
  
    virtual fun asech (x:t) => acosh ( recip x);
    virtual fun acsch (x:t) => asinh ( recip x );
    virtual fun acoth (x:t) => atanh ( recip x );
  
    // exponential
    virtual fun exp: t -> t;
    fun \(\exp\) (x:t) => exp x;
  
    // log
    virtual fun log: t -> t;
    fun \(\log\) (x:t) => log x;
    fun ln (x:t) => log x;
    fun \(\ln\) (x:t) => log x;
  
    // power
    virtual fun pow: t * t -> t;
    virtual fun pow (a:t, b:int) : t => pow (a, C_hack::cast[t] b);
    fun ^ (x:t,y:t) => pow (x,y);
    fun ^ (x:t,y:int) => pow (x,y);
  
  
  }
  
  Finance and Statistics.
  class Special[t] {
    virtual fun erf: t -> t;
    virtual fun erfc: t -> t;
  }
  

share/lib/std/algebra/real.flx

  Float-approximate real numbers.
  class Real[t] {
    inherit Tord[t];
    inherit Trig[t];
    inherit Special[t];
    virtual fun embed: int -> t;
  
    virtual fun log10: t -> t;
    virtual fun abs: t -> t;
   
    virtual fun sqrt: t -> t;
    fun \(\sqrt\) (x:t) => sqrt x;
    virtual fun ceil: t -> t;
      // tex \lceil \rceil defined in grammar
  
    virtual fun floor: t -> t;
      // tex \lfloor \rfloor defined in grammar
  
    virtual fun trunc: t -> t;
  
    // this trig function is included here because it
    // is not available for complex numbers
    virtual fun atan2: t * t -> t;
  
  }
  
  

share/lib/std/algebra/complex.flx

  Float-approximate Complex.
  class Complex[t,r] {
    inherit Eq[t];
    inherit Special[t];
    inherit Trig[t];
    virtual fun real: t -> r;
    virtual fun imag: t -> r;
    virtual fun abs: t -> r;
    virtual fun arg: t -> r;
    virtual fun sqrt: t -> r;
  
    virtual fun + : r * t -> t;
    virtual fun + : t * r -> t;
    virtual fun - : r * t -> t;
    virtual fun - : t * r -> t;
    virtual fun * : t * r -> t;
    virtual fun * : r * t -> t;
    virtual fun / : t * r -> t;
    virtual fun / : r * t -> t;
  }