I'm currently going through the paper Extensibility for the Masses. Practical Extensibility with Object Algebras by Bruno C. d. S. Oliveira and William R. Cook (available many places on the internet - for example here: https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf).
On page 10, they write:
Adding new data variants is easy. The first step is to create new classes
BoolandIffin the usual object-oriented style (likeLitandAdd):class Bool implements Exp {...} class Iff implements Exp {...}
The implementation of Exp is, it seems, left as an exercise to the reader. It's not clear to me, however, how Exp is defined in this part of the paper. My question is:
How should Bool and Iff be implemented?
Here's what I've tried:
ExpEarly in the paper, the Exp interface is defined like this:
interface Exp {
Value eval();
}
Here, Value is defined by another interface:
interface Value {
Integer getInt();
Boolean getBool();
}
The paper, however, quickly departs from this definition of Exp in favour of a Visitor-based definition.
BoolBased on that definition, how should one implement the Bool class?
Something like this seems like a start:
class Bool implements Exp {
boolean x;
public Bool(boolean x) { this.x = x; }
public Value eval() {
return new VBool(x);
}}
The question, however, becomes how to properly implement Value?
The paper only shows this:
class VBool implements Value {...}
The implementation doesn't seem total to me:
class VBool implements Value {
boolean x;
public VBool(boolean x) { this.x = x; }
public Boolean getBool() {
return new Boolean(x);
}
public Integer getInt() {
// What to return here?
}
}
As my above attempt shows, it's not clear what to return from getInt. I suppose I could return null or throw an exception, but that would imply that my implementation is partial.
In any case, this first definition of Exp seems only to exist as a motivating example in the paper, which then proceeds to define a better alternative.
ExpOn page 4 the paper redefines Exp as an Internal Visitor:
interface Exp {
<A> A accept(IntAlg<A> vis);
}
Where IntAlg<A> is another interface:
interface IntAlg<A> {
A lit(int x);
A add(A e1, A e2);
}
So far things seem clear, until we get to implementing Bool and Iff...
BoolHow should we implement the proposed Bool class based on this definition of Exp?
class Bool implements Exp {
boolean x;
public Bool(boolean x) { this.x = x; }
public <A> A accept(IntAlg<A> vis) {
// What to return here?
}}
There's no way to conjure an A value out of thin air, so one has to interact with vis in order to produce an A value. The vis parameter, however, only defines lit and add methods.
The lit method requires an int, which isn't available in Bool.
Likewise, add requires two A values, which are also unavailable. Again, I find myself at an impasse.
Exp?Then, on page 8, the paper shows this example:
int x = exp(base).eval();
Here, exp(base) returns Exp, but which definition of eval is this?
Apparently, Exp still (or again?) has an eval method, but now it returns int. Does it look like this?
interface Exp {
int eval();
}
The paper doesn't show this definition, so I may be misunderstanding something.
BoolCan we implement Bool and Iff with this definition of Exp?
class Bool implements Exp {
boolean x;
public Bool(boolean x) { this.x = x; }
public int eval() {
// What to return here?
}}
Again, it's not clear how to implement the interface. One could, of course, return 0 for false and 1 for true, but that's just an arbitrary decision. That doesn't seem appropriate.
Is there a fourth definition of Exp that I'm missing? Or is there some other information in the paper that's eluding me?
BTW, I apologise if I've made mistakes in my attempts. I don't normally write Java code.
@Mark. Let me try to clarify the confusion points that you have.
The definition of Exp that we are assumming in page 10 is:
interface Exp {
Value eval();
}
which is presented earlier in the paper in Figure 1. The alternative version of Exp with visitors can be ignored. We used it merely to talk about visitors and the relationship with Object Algebras, and it does not play a role in later parts of the paper.
Also, regarding the code in page 8, I think there is a typo in the paper. You are right: it seems that there we were assuming an eval method that returns int. When we were writing the paper we were using multiple versions of Exp, and probably we used the code for another version there by mistake. The code in page 8, adapted to the representation in the paper, should be:
int x = exp(base).eval().getInt();
The code that we intended to have for the implementation of the Value class uses exceptions, similarly to your own attempt, and it is indeed partial as presented in the paper. In the paper, the point that we were making is about the extensibility and type-safety with respect to the source expressions. For the values, all we wanted was that values were rich enough to support the source expressions, and the assumption was that the values themselves were not extensible (later in Section 7 we briefly discuss extensible values). The representation that we choose in the paper was aimed at keeping the code simple, and avoid some distractions with dealing with error management (which are orthogonal to extensibility).
Agreeably this is not a great representation but, at least with the Java version at the time, it seemed like a reasonable compromise. In modern Java, I think the way to go would be to have Value modelled as an algebraic datatype. Java 16 supports pattern matching and sealed types, which can be used to essentially model algebraic datatypes in functional programming. So you could model Value with something like:
sealed interface Value {}
record VInt(int x) implements Value {}
record VBool(boolean b) implements Value {}
In retrospect, to avoid confusions like the one you're having, I think it would have been better to have presented the paper simply using the interface:
interface Exp {
int eval();
}
and to use an if construct à la C, where integers play the role of booleans. This would have avoided distractions with the representation of Value in the first place.
In any case, getting back to the representation of the paper, and also to your point about partiality, I show a minimal, but complete implementation of the code next. For illustrating that partiality is not a fundamental issue, I also switch from using unchecked exceptions to checked exceptions.
First we can define values as follows:
interface Value {
// You can choose checked exceptions or unchecked exceptions.
// In the paper we opted for unchecked exceptions.
// But here, I show that you can also use checked exceptions,
// if you want to ensure that you deal with exception cases.
int intValue() throws Exception;
boolean boolValue() throws Exception;
}
class VInt implements Value {
int x;
public VInt(int x) {
this.x = x;
}
public int intValue() throws Exception {
return x;
}
public boolean boolValue() throws Exception {
throw new Exception();
}
public String toString() {
return Integer.valueOf(x).toString();
}
}
class VBool implements Value {
boolean b;
public VBool(boolean b) {
this.b = b;
}
public int intValue() throws Exception {
throw new Exception();
}
public boolean boolValue() throws Exception {
return b;
}
public String toString() {
return Boolean.valueOf(b).toString();
}
}
Then you can write the code with for Object Algebras as follows:
// Integer Expressions
interface IntAlg<Exp> {
Exp lit(int x);
Exp add(Exp e1, Exp e2);
}
interface Exp {
Value eval() throws Exception;
}
class IntEval implements IntAlg<Exp> {
public Exp lit(int x) {
return () -> new VInt(x);
}
public Exp add(Exp e1, Exp e2) {
return () -> new VInt(e1.eval().intValue() + e2.eval().intValue());
}
}
// Boolean Expressions
interface BoolAlg<Exp> extends IntAlg<Exp> {
Exp bool(boolean b);
Exp iff(Exp e1, Exp e2, Exp e3);
}
class BoolEval extends IntEval implements BoolAlg<Exp> {
public Exp bool(boolean b) {
return () -> new VBool(b);
}
public Exp iff(Exp e1, Exp e2, Exp e3) {
return () -> e1.eval().boolValue() ? e2.eval() : e3.eval();
}
}
public class Main {
public static <Exp> Exp m(IntAlg<Exp> alg) {
return alg.add(alg.lit(4),alg.lit(3));
}
public static <Exp> Exp m2(BoolAlg<Exp> alg) {
return alg.iff(alg.bool(false),m(alg),alg.bool(true));
}
public static void main(String[] args) {
Exp e = m(new IntEval());
try {
System.out.println(e.eval());
} catch (Exception exp) {
System.out.println("Ops! There is an error...");
}
Exp e2 = m2(new BoolEval());
try {
System.out.println(e2.eval());
} catch (Exception exp) {
System.out.println("Ops! There is an error...");
}
}
}
As you can see in the definition of the main, we need to eventually deal with the exceptions. As a matter of fact, if you wanted to deal more nicely with errors, you should change the code in the interpreter to catch the exceptions there, and then give error messages like "You cannot add a boolean to an integer..." and so on. That does involve extra code (which is not so related to the main point of the technique), but it can be easily done.
Also note that I'm using lambdas to avoid some boilerplate with anonymous classes. In Java anonymous classes with a single method implementation can be written as a lambda.
If you do not like code using exceptions, and you'd prefer a more functional-style approach, you could also use Java's Optional class to model failure (just as you'd do in a functional language like Haskell, say). In such case, you could have the following:
// Values
interface Value {
Optional<Integer> intValue();
Optional<Boolean> boolValue();
}
// The expression interface
interface Exp {
Optional<Value> eval();
}
Where we now use Optional instead of making the operations partial. The Java code (without pattern matching) with this option will not be so nice, but maybe with the new pattern matching features it won't be that bad.