An example of Object Algebras in Felix

gistfile1.txt

// Title: An example of Object Algebras in Felix
// Author: Garrett Bluma
// Date: June 29, 2015

// Special thanks to Bruno Oliveira and William Cook
// http://i.cs.hku.hk/~bruno/oa/

// -----------------------------------------
// Object algebras use extension via type parameters and inheritance.  Given a
// type parameter and an extended algebra, we can calculate with a minimum of
// glue code. We can also extend an algebra via inheritance or type parameters
// without modifying previously written code.
//
//               | Lit   |  Add    | Sub (added later) 
// Basic         |       |         | 
// ExpAlg[Eval]  |  x    |   x     |  x 
// ExpAlg[Print] |  x    |   x     |  x        
// 
// -----------------------------------------


// Here we define our basic algebra, initially it is completely abstract.
class ExpAlg[E] {
    virtual fun Lit : int -> E;
    virtual fun Add : E -> E -> E;
}


// EVAL ------------------------------------
typedef Eval = 1 -> int;

// implement the algebra for evaluation for Lit and Add
instance ExpAlg[Eval] {
    fun Lit(x:int) => fun () => x;
    fun Add(e1:Eval) (e2:Eval) => fun () => e1() + e2();
}
open ExpAlg[Eval];

// extended the algebra with subtraction 
class SubExpAlg[E with ExpAlg[E]] {
    virtual fun Sub : E -> E -> E;
}

// implement the subtraction method for evaluation
instance SubExpAlg[Eval] {
    fun Sub(e1:Eval)(e2:Eval) => fun () => e1() - e2();
}
open SubExpAlg[Eval];


// PRINT -----------------------------------
typedef Print = 1 -> string;

// implement the algebra for printing for Lit and Add
instance ExpAlg[Print] {
    fun Lit(x:int) => fun () => str(x);
    fun Add(e1:Print)(e2:Print) => fun () => str(e1()) + " + " + str(e2());
}
open ExpAlg[Print];

// implement the subtraction method for printing
instance SubExpAlg[Print] {
    fun Sub(e1:Print)(e2:Print) => fun () => str(e1()) + " - " + str(e2());
}
open SubExpAlg[Print];


// DEMO -------------------

var v1 = ExpAlg[Eval]::Add (ExpAlg[Eval]::Lit 3) (ExpAlg[Eval]::Lit 4);
println$ v1(); // => 7

var v2 = ExpAlg[Print]::Add (ExpAlg[Print]::Lit 3) (ExpAlg[Print]::Lit 4);
println$ v2(); // => 3 + 4

// TODO: find out how to do this without all the explicit annotations