Content deleted Content added
m Updated citation for Reynolds which is no longer at the CMU link. Explicitly credited Reynolds w/ discovery of EP. |
Added a concrete example that hopefully makes the problem clear. Also added one example solution based on the paper already cited in the article. |
||
Line 90:
Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages">{{cite journal|last1=Carette|first1=Jacques|last2=Kiselyov|first2=Oleg|last3=Chung-chieh|first3=Shan|title=Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages|journal=J. Funct. Program.|date=2009|url=http://okmij.org/ftp/tagless-final/JFP.pdf}}</ref> / Object algebras<ref name="Oliveira & Cook, Object Algebras">{{cite journal|last1=Oliveira|first1=Bruno C. d. S.|last2=Cook|first2=William R.|title=Extensibility for the Masses: Practical Extensibility with Object Algebras|journal=Ecoop '12|date=2012|url=http://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf}}</ref>
* Polymorphic Variants<ref name="Code Reuse Through Polymorphic Variants">{{cite journal|last1=Garrigue|first1=Jacques|title=Code Reuse Through Polymorphic Variants|citeseerx=10.1.1.128.7169|year=2000}}</ref>
== Example ==
=== Problem description ===
We can imagine we do not have the source code for the following library, written in [[C Sharp (programming language)|C#]], which we wish to extend:<syntaxhighlight lang="c#" line="1">
public interface IEvalExp
{
int Eval();
}
public class Lit : IEvalExp
{
public Lit(int n)
{
N = n;
}
public int N { get; }
public int Eval()
{
return N;
}
}
public class Add : IEvalExp
{
public Add(IEvalExp left, IEvalExp right)
{
Left = left;
Right = right;
}
public IEvalExp Left { get; }
public IEvalExp Right { get; }
public int Eval()
{
return Left.Eval() + Right.Eval();
}
}
public static class ExampleOne
{
public static IEvalExp AddOneAndTwo() => new Add(new Lit(1), new Lit(2));
public static int EvaluateTheSumOfOneAndTwo() => AddOneAndTwo().Eval();
}
</syntaxhighlight>Using this library we can express the arithmetic expression ''1 + 2'' as we did in ''ExampleOne.AddOneAndTwo()'' and can evaluate the expression by calling ''.Eval()''. Now imagine that we wish to extend this library, adding a new type is easy because we are working with an [[Object-oriented programming|Object Oriented Programming Language]]. For example, we might create the following class:<syntaxhighlight lang="c#" line="1">
public class Mult : IEvalExp
{
public Mult(IEvalExp left, IEvalExp right)
{
Left = left;
Right = right;
}
public IEvalExp Left { get; }
public IEvalExp Right { get; }
public int Eval()
{
return Left.Eval() * Right.Eval();
}
}
</syntaxhighlight>However, if we wish to add a new function over the type (a new method in C# terminology) we have to change the ''IEvalExp'' interface and then modify all the classes that implement the interface. Another possibility is to create a new interface that extends the ''IEvalExp'' interface and then create sub-types for ''Lit'', ''Add'' and ''Mult'' classes, but the expression returned in ''ExampleOne.AddOneAndTwo()'' has already been compiled so we will not be able to use the new function over the old type. The problem is reversed in functional programming languages like [[F Sharp (programming language)|F#]] where it is easy to add a function over a given type, but extending or adding types is difficult.
=== Problem Solution using Object Algebra ===
Let us redesign the original library with extensibility in mind using the ideas from the paper ''Extensibiltiy for the Masses.''<ref name="Oliveira & Cook, Object Algebras" /> <syntaxhighlight lang="c#" line="1">
public interface ExpAlgebra<T>
{
T Lit(int n);
T Add(T left, T right);
}
public class ExpFactory : ExpAlgebra<IEvalExp>
{
public IEvalExp Add(IEvalExp left, IEvalExp right)
{
return new Add(left, right);
}
public IEvalExp Lit(int n)
{
return new Lit(n);
}
}
public static class ExampleTwo<T>
{
public static T AddOneToTwo(ExpAlgebra<T> ae) => ae.Add(ae.Lit(1), ae.Lit(2));
}
</syntaxhighlight>We use the same implementation as in the first code example but now add a new interface containing the functions over the type as well as a factory for the algebra. Notice that we now generate the expression in ''ExampleTwo.AddOneToTwo()'' using the ''ExpAlgebra<T>'' interface instead of directly from the types. We can now add a function by extending the ''ExpAlgebra<T>'' interface, we will add functionality to print the expression:<syntaxhighlight lang="c#" line="1">
public interface IPrintExp : IEvalExp
{
string Print();
}
public class PrintableLit : Lit, IPrintExp
{
public PrintableLit(int n) : base(n)
{
N = n;
}
public int N { get; }
public string Print()
{
return N.ToString();
}
}
public class PrintableAdd : Add, IPrintExp
{
public PrintableAdd(IPrintExp left, IPrintExp right) : base(left, right)
{
Left = left;
Right = right;
}
public new IPrintExp Left { get; }
public new IPrintExp Right { get; }
public string Print()
{
return Left.Print() + " + " + Right.Print();
}
}
public class PrintFactory : ExpFactory, ExpAlgebra<IPrintExp>
{
public IPrintExp Add(IPrintExp left, IPrintExp right)
{
return new PrintableAdd(left, right);
}
public new IPrintExp Lit(int n)
{
return new PrintableLit(n);
}
}
public static class ExampleThree
{
public static int Evaluate() => ExampleTwo<IPrintExp>.AddOneToThree(new PrintFactory()).Eval();
public static string Print() => ExampleTwo<IPrintExp>.AddOneToThree(new PrintFactory()).Print();
}
</syntaxhighlight>Notice that in ''ExampleThree.Print()'' we are printing an expression that was already compiled in ''ExampleTwo'', we did not need to modify any existing code. Notice also that this is still strongly typed, we do not need reflection or casting. If we would replace the ''PrintFactory()'' with the ''ExpFactory()'' in the ''ExampleThree.Print()'' we would get a compilation error since the ''.Print()'' method does not exist in that context.
==See also==
| |||