Skip to content

Instantly share code, notes, and snippets.

@hodzanassredin
Created July 31, 2012 19:38
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hodzanassredin/3219856 to your computer and use it in GitHub Desktop.
Save hodzanassredin/3219856 to your computer and use it in GitHub Desktop.
Solutions to the Expression Problem Using Object Algebras
using System;
using System.Globalization;
namespace OASample
{
// Initial object algebra interface for expressions: integers and addition
interface IExpAlg<E>
{
E Lit(int x);
E Add(E e1, E e2);
}
// ----------------------------------------------------------------------
// An object algebra implementing that interface (evaluation)
// ----------------------------------------------------------------------
// The evaluation interface
public class Evaluator
{
Func<int> f;
public Evaluator(Func<int> f)
{
this.f = f;
}
public int Eval()
{
return f();
}
}
// The object algebra
class EvalExpAlg : IExpAlg<Evaluator>
{
public Evaluator Lit(int x)
{
Func<int> f = () => x;
return new Evaluator(f);
}
public Evaluator Add(Evaluator e1, Evaluator e2)
{
Func<int> f = () => e1.Eval() + e2.Eval();
return new Evaluator(f);
}
}
// ----------------------------------------------------------------------
// Evolution 1: Adding subtraction
// ----------------------------------------------------------------------
interface ISubExpAlg<E> : IExpAlg<E>
{
E Sub(E e1, E e2);
}
// Updating evaluation:
class EvalSubExpAlg : EvalExpAlg, ISubExpAlg<Evaluator>
{
public Evaluator Sub(Evaluator e1, Evaluator e2)
{
Func<int> f = () => e1.Eval() - e2.Eval();
return new Evaluator(f);
}
}
// ----------------------------------------------------------------------
// Evolution 2: Adding pretty printing
// ----------------------------------------------------------------------
public class IPPrint
{
Func<string> f;
public IPPrint (Func<string> f)
{
this.f = f;
}
public string Print ()
{
return f();
}
}
class PrintExpAlg : ISubExpAlg<IPPrint>
{
public IPPrint Lit(int x)
{
Func<string> f = () => x.ToString(CultureInfo.InvariantCulture);
return new IPPrint(f);
}
public IPPrint Add(IPPrint e1, IPPrint e2)
{
Func<string> f = () => e1.Print() + " + " + e2.Print();
return new IPPrint(f);
}
public IPPrint Sub(IPPrint e1, IPPrint e2)
{
Func<string> f = () => e1.Print() + " - " + e2.Print();
return new IPPrint(f);
}
}
// An alternative object algebra for pretty printing:
// Often, when precise control over the invocation of
// methods is not needed, we can simplify object algebras.
// For example, here's an alternative implementation
// of pretty printing that directly computes a string:
class PrintExpAlg2 : ISubExpAlg<string>
{
public string Lit(int x)
{
return x.ToString(CultureInfo.InvariantCulture);
}
public string Add(string e1, string e2)
{
return e1 + " + " + e2;
}
public string Sub(string e1, string e2)
{
return e1 + " - " + e2;
}
}
// ----------------------------------------------------------------------
// Testing
// ----------------------------------------------------------------------
class Program
{
// An expression using the basic ExpAlg
private static E Exp1<E>(IExpAlg<E> alg)
{
return alg.Add(alg.Lit(3), alg.Lit(4));
}
// An expression using subtraction too
private static E Exp2<E>(ISubExpAlg<E> alg)
{
return alg.Sub(Exp1(alg), alg.Lit(4));
}
private static void Main()
{
// Some object algebras:
var ea = new EvalExpAlg();
var esa = new EvalSubExpAlg();
var pa = new PrintExpAlg();
var pa2 = new PrintExpAlg2();
// We can call esa with Exp1
var ev = Exp1(esa);
// But calling ea with Exp2 is an error
// var ev_bad = Exp2(ea);
// Testing the actual algebras
Console.WriteLine("Evaluation of Exp1 '{0}' is: {1}", Exp1(pa).Print(), ev.Eval());
Console.WriteLine("Evaluation of Exp2 '{0}' is: {1}", Exp2(pa).Print(), Exp2(esa).Eval());
Console.WriteLine("The alternative pretty printer works nicely too!{0}Exp1: {1}{0}Exp2: {2}",
Environment.NewLine, Exp1(pa2), Exp2(pa2));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment