Skip to content

Instantly share code, notes, and snippets.

@norswap
Last active June 22, 2020 21:56
Show Gist options
  • Save norswap/9d4dd9ae5c0fd2ef652a1f41778467ea to your computer and use it in GitHub Desktop.
Save norswap/9d4dd9ae5c0fd2ef652a1f41778467ea to your computer and use it in GitHub Desktop.
Visitors Comparison
See https://norswap.com/expression-problem-java/
public final class CovariantEP
{
// ====================================================
// 0. Initial Setup (data: [Add, Lit], operations: Print)
interface Exp {
void print();
}
// ----------------------------------------------------
public static class Lit implements Exp
{
public final int value;
public Lit (int value) { this.value = value; }
public void print() {
System.out.print(value);
}
}
// ----------------------------------------------------
public static abstract class Add implements Exp
{
abstract Exp left();
abstract Exp right();
@Override public void print() {
left().print();
System.out.print('+');
right().print();
}
}
// ----------------------------------------------------
public static class AddF extends Add
{
public final Exp left, right;
public AddF (Exp left, Exp right) {
this.left = left;
this.right = right;
}
@Override Exp left () { return left; }
@Override Exp right () { return right; }
}
// ====================================================
// 1. Add an operation (Eval)
interface EvalExp extends Exp {
int eval();
}
// ----------------------------------------------------
public static class EvalLit extends Lit implements EvalExp
{
public EvalLit (int value) { super(value); }
@Override public int eval () {
return value;
}
}
// ----------------------------------------------------
public static abstract class EvalAdd extends Add implements EvalExp
{
@Override abstract EvalExp left();
@Override abstract EvalExp right();
@Override public int eval () {
return left().eval() + right().eval();
}
}
// ----------------------------------------------------
public static class EvalAddF extends EvalAdd
{
public final EvalExp left, right;
public EvalAddF (EvalExp left, EvalExp right) {
this.left = left;
this.right = right;
}
@Override EvalExp left () { return left; }
@Override EvalExp right () { return right; }
}
// ====================================================
// 2. Add a data class (Neg)
public static abstract class Neg implements EvalExp
{
abstract EvalExp operand();
@Override public void print () {
System.out.print("-(");
operand().print();
System.out.print(")");
}
@Override public int eval () {
return - operand().eval();
}
}
// ----------------------------------------------------
public static class NegF extends Neg
{
public final EvalExp operand;
public NegF (EvalExp operand) {
this.operand = operand;
}
@Override EvalExp operand() { return operand; }
}
// ====================================================
public static void main (String[] args)
{
// NOTE: Compared to TorgensenDataEP, we dispensed
// with the factories. Don't let this bias the comparison,
// they're as necessary in both approach.
// -1 + 2
EvalExp exp = new EvalAddF(new NegF(new EvalLit(1)), new EvalLit(2));
exp.print();
System.out.println();
System.out.println(exp.eval());
}
// ====================================================
}
public final class NorswapEP
{
// ====================================================
// 0. Initial Setup (data: [Add, Lit], operations: Print)
public interface Exp {
void accept (Visitor visitor);
}
// ----------------------------------------------------
public interface Visitor {
void visit (Lit expr);
void visit (Add expr);
}
// ----------------------------------------------------
public static final class Lit implements Exp
{
public final int value;
public Lit (int value) { this.value = value; }
@Override public void accept (Visitor visitor) {
visitor.visit(this);
}
}
// ----------------------------------------------------
public static final class Add implements Exp
{
public final Exp left, right;
public Add (Exp left, Exp right) {
this.left = left;
this.right = right;
}
@Override public void accept (Visitor visitor) {
visitor.visit(this);
}
}
// ----------------------------------------------------
public static class Print implements Visitor
{
public int result;
public final void print (Exp exp) {
exp.accept(this);
}
@Override public void visit (Lit lit) {
System.out.print(lit.value);
}
@Override public void visit (Add add) {
print(add.left);
System.out.print('+');
print(add.right);
}
}
// ====================================================
// 1. Add an operation (Eval)
public static class Eval implements Visitor
{
public int result;
public final int eval (Exp exp) {
exp.accept(this);
return result;
}
@Override public void visit (Lit lit) {
result = lit.value;
}
@Override public void visit (Add add) {
result = eval(add.left) + eval(add.right);
}
}
// ====================================================
// 2. Add a data class (Neg)
public interface NegVisitor extends Visitor {
void visit (Neg expr);
}
// ----------------------------------------------------
public static final class Neg implements Exp
{
public final Exp operand;
public Neg (Exp operand) { this.operand = operand; }
@Override public void accept (Visitor visitor) {
((NegVisitor) visitor).visit(this);
}
}
// ----------------------------------------------------
public static class NegEval extends Eval implements NegVisitor
{
@Override public void visit (Neg neg) {
result = - eval(neg.operand);
}
}
// ----------------------------------------------------
public static class NegPrint extends Print implements NegVisitor
{
@Override public void visit (Neg neg) {
System.out.print("-(");
print(neg.operand);
System.out.print(")");
}
}
// ====================================================
public static void main (String[] args)
{
// -1 + 2
Exp exp = new Add(new Neg(new Lit(1)), new Lit(2));
new NegPrint().print(exp);
System.out.println();
System.out.println(new NegEval().eval(exp));
}
// ====================================================
}
public final class ObjectAlgebraEP
{
// ====================================================
// 0. Initial Setup (data: [Add, Lit], operations: Print)
interface Algebra<E> {
E lit (int value);
E add (E left, E right);
}
// ----------------------------------------------------
@FunctionalInterface interface Print {
void print();
}
// ----------------------------------------------------
public static class PrintAlgebra implements Algebra<Print>
{
@Override public Print lit (int value) {
return () -> System.out.print(value);
}
@Override public Print add (Print left, Print right) {
return () -> {
left.print();
System.out.print("+");
right.print();
};
}
}
// ====================================================
// 1. Add an operation (Eval)
@FunctionalInterface interface Eval {
int eval();
}
// ----------------------------------------------------
public static class EvalAlgebra implements Algebra<Eval>
{
@Override public Eval lit (int value) {
return () -> value;
}
@Override public Eval add (Eval left, Eval right) {
return () -> left.eval() + right.eval();
}
}
// ====================================================
// 2. Add a data class (Neg)
interface NegAlgebra<E> extends Algebra<E> {
E neg (E operand);
}
// ----------------------------------------------------
public static class NegPrintAlgebra
extends PrintAlgebra implements NegAlgebra<Print>
{
@Override public Print neg (Print operand) {
return () -> {
System.out.print("-(");
operand.print();
System.out.print(")");
};
}
}
// ----------------------------------------------------
public static class NegEvalAlgebra
extends EvalAlgebra implements NegAlgebra<Eval>
{
@Override public Eval neg (Eval operand) {
return () -> - operand.eval();
}
}
// ====================================================
public static <E> E expression (NegAlgebra<E> a)
{
// -1 + 2
return a.add(a.neg(a.lit(1)), a.lit(2));
}
public static void main (String[] args)
{
expression(new NegPrintAlgebra()).print();
System.out.println();
System.out.println(expression(new NegEvalAlgebra()).eval());
}
// ====================================================
}
public final class TorgersenBetterHybridEP
{
// ====================================================
// 0. Initial Setup (data: [Add, Lit], operation: Print)
interface Exp {
void accept (Visitor v);
}
// ----------------------------------------------------
interface Visitor {
void visit (Exp exp);
void visit (Lit lit);
void visit (Add add);
}
// ----------------------------------------------------
public static final class Lit implements PrintExp
{
public final int value;
public Lit (int value) { this.value = value; }
@Override public void print (Print print) {
System.out.print(value);
}
@Override public void accept (Visitor v) {
v.visit(this);
}
}
// ----------------------------------------------------
public static final class Add implements PrintExp
{
public final Exp left, right;
public Add(Exp left, Exp right) {
this.left = left;
this.right = right;
}
@Override public void print (Print print) {
print.visit(left);
System.out.print('+');
print.visit(right);
}
@Override public void accept (Visitor v) {
v.visit(this);
}
}
// ----------------------------------------------------
interface PrintExp extends Exp {
void print (Print print);
}
// ----------------------------------------------------
public static class Print implements Visitor
{
public final void print (Exp exp) {
visit(exp);
}
@Override public void visit (Exp exp) {
if (exp instanceof PrintExp)
((PrintExp) exp).print(this);
else
exp.accept(this);
}
@Override public void visit (Lit lit) {
lit.print(this); // never actually called
}
@Override public void visit (Add add) {
add.print(this); // never actually called
}
}
// ====================================================
// 1. Add an operation (Eval)
interface EvalExp extends PrintExp {
int eval (Eval eval);
}
// ----------------------------------------------------
public static class Eval implements Visitor
{
private int result;
public final int eval (Exp exp) {
visit(exp);
return result;
}
@Override public void visit (Exp exp) {
if (exp instanceof EvalExp)
result = ((EvalExp) exp).eval(this);
else
exp.accept(this);
// throw new IllegalStateException("not an EvalExp: " + exp); // TODO
}
@Override public void visit (Lit lit) {
result = lit.value;
}
@Override public void visit (Add add) {
result = eval(add.left) + eval(add.right);
}
}
// ====================================================
// 2. Add a data class (Neg)
interface NegVisitor extends Visitor {
void visit (Neg neg);
}
// ----------------------------------------------------
public static final class Neg implements EvalExp
{
public final Exp operand;
public Neg (Exp operand) { this.operand = operand; }
@Override public void print (Print print) {
System.out.print("−(");
print.print(operand);
System.out.print(")");
}
@Override public int eval (Eval eval) {
return - eval.eval(operand);
}
@Override public void accept (Visitor v) {
if (v instanceof NegVisitor)
((NegVisitor) v).visit(this);
else
throw new IllegalStateException("not a NegVisitor: " + v);
}
}
// ====================================================
public static void main (String[] args)
{
// -1 + 2
Exp exp = new Add(new Neg(new Lit(1)), new Lit(2));
new Print().print(exp);
System.out.println();
System.out.println(new Eval().eval(exp));
}
// ====================================================
}
public final class TorgersenBetterOperationEP
{
// ====================================================
// 0. Initial Setup (data: [Add, Lit], operations: Print)
public interface Exp<V extends Visitor> {
void accept (V visitor);
}
// ----------------------------------------------------
public interface Visitor {
<V extends Visitor> void visit (V self, Lit<V> expr);
<V extends Visitor> void visit (V self, Add<V> expr);
}
// ----------------------------------------------------
public static final class Lit <V extends Visitor> implements Exp<V>
{
public final int value;
public Lit (int value) { this.value = value; }
@Override public void accept (V visitor) {
visitor.visit(visitor, this);
}
}
// ----------------------------------------------------
public static final class Add <V extends Visitor> implements Exp<V>
{
public final Exp<? super V> left, right;
public Add (Exp<? super V> left, Exp<? super V> right) {
this.left = left;
this.right = right;
}
@Override public void accept (V visitor) {
visitor.visit(visitor, this);
}
}
// ----------------------------------------------------
public static class Print implements Visitor
{
@Override public <V extends Visitor> void visit (V self, Lit<V> lit) {
System.out.print(lit.value);
}
@Override public <V extends Visitor> void visit (V self, Add<V> add) {
add.left.accept(self);
System.out.print('+');
add.right.accept(self);
}
}
// ====================================================
// 1. Add an operation (Eval)
public static class Eval implements Visitor
{
public int result;
@Override public <V extends Visitor> void visit (V self, Lit<V> lit) {
result = lit.value;
}
@Override public <V extends Visitor> void visit (V self, Add<V> add) {
add.left.accept(self);
int left = result;
add.right.accept(self);
int right = result;
result = left + right;
}
}
// ====================================================
// 2. Add a data class (Neg)
public interface NegVisitor extends Visitor {
<V extends NegVisitor> void visit (V self, Neg<V> neg);
}
// ----------------------------------------------------
public static final class Neg <V extends NegVisitor> implements Exp<V>
{
public final Exp<? super V> operand;
public Neg (Exp<? super V> operand) { this.operand = operand; }
@Override public void accept (V visitor) {
visitor.visit(visitor, this);
}
}
// ----------------------------------------------------
public static class NegPrint extends Print implements NegVisitor
{
@Override public <V extends NegVisitor> void visit (V self, Neg<V> neg) {
System.out.print("-(");
neg.operand.accept(self);
System.out.print(")");
}
}
// ----------------------------------------------------
public static class NegEval extends Eval implements NegVisitor
{
@Override public <V extends NegVisitor> void visit (V self, Neg<V> neg) {
neg.operand.accept(self);
result = - result;
}
}
// ====================================================
public static void main (String[] args)
{
// -1 + 2
Exp<Visitor> lit1 = new Lit<>(1), lit2 = new Lit<>(2);
Exp<NegVisitor> exp = new Add<>(new Neg<>(lit1), lit2);
exp.accept(new NegPrint());
System.out.println();
NegEval eval = new NegEval();
exp.accept(eval);
System.out.println(eval.result);
}
// ====================================================
}
public final class TorgersenDataEP
{
// ====================================================
// 0. Initial Setup (data: [Add, Lit], operations: Print)
interface Exp <C extends Exp<C>> {
void print();
}
// ----------------------------------------------------
public static abstract class Lit <C extends Exp<C>> implements Exp<C>
{
public final int value;
public Lit (int value) { this.value = value; }
public void print() {
System.out.print(value);
}
}
// ----------------------------------------------------
public static abstract class Add <C extends Exp<C>> implements Exp<C>
{
public final C left, right;
public Add (C left, C right) {
this.left = left;
this.right = right;
}
@Override public void print() {
left.print();
System.out.print('+');
right.print();
}
}
// ----------------------------------------------------
interface ExpF extends Exp<ExpF> {}
// ----------------------------------------------------
public static final class LitF extends Lit<ExpF> implements ExpF {
public LitF (int value) { super (value); }
}
// ----------------------------------------------------
public static final class AddF extends Add<ExpF> implements ExpF {
AddF (ExpF left, ExpF right) { super (left,right); }
}
// ----------------------------------------------------
interface Factory <C extends Exp<C>> {
C add (C left, C right);
C lit (int value);
}
// ----------------------------------------------------
public static class FactoryF implements Factory<ExpF>
{
@Override public ExpF add (ExpF left, ExpF right) {
return new AddF(left, right);
}
@Override public ExpF lit (int value) {
return new LitF(value);
}
}
// ====================================================
// 1. Add an operation (Eval)
interface EvalExp <C extends EvalExp<C>> extends Exp<C> {
int eval();
}
// ----------------------------------------------------
public static abstract class EvalLit <C extends EvalExp<C>>
extends Lit<C> implements EvalExp<C>
{
public EvalLit (int value) { super (value); }
@Override public int eval() {
return value;
}
}
// ----------------------------------------------------
public static abstract class EvalAdd <C extends EvalExp<C>>
extends Add<C> implements EvalExp<C>
{
public EvalAdd (C left, C right) { super (left,right); }
@Override public int eval() {
return left.eval() + right.eval();
}
}
// ----------------------------------------------------
public interface EvalExpF extends EvalExp<EvalExpF> {}
// ----------------------------------------------------
public static class EvalLitF extends EvalLit<EvalExpF> implements EvalExpF {
EvalLitF (int v) { super (v); }
}
// ----------------------------------------------------
public static class EvalAddF extends EvalAdd<EvalExpF> implements EvalExpF {
EvalAddF (EvalExpF l, EvalExpF r) { super (l,r); }
}
// ----------------------------------------------------
interface EvalFactory<C extends EvalExp<C>> extends Factory<C> {}
// ----------------------------------------------------
public static class EvalFactoryF implements EvalFactory<EvalExpF>
{
@Override public EvalExpF add (EvalExpF left, EvalExpF right) {
return new EvalAddF(left, right);
}
@Override public EvalExpF lit (int value) {
return new EvalLitF(value);
}
}
// ====================================================
// 2. Add a data class (Neg)
public static abstract class Neg <C extends EvalExp<C>> implements EvalExp<C>
{
public C operand;
public Neg (C operand) { this.operand = operand; }
@Override public void print() {
System.out.print("-(");
operand.print();
System.out.print(")");
}
@Override public int eval() {
return - operand.eval();
}
}
// ----------------------------------------------------
public static final class NegF extends Neg<EvalExpF> implements EvalExpF {
public NegF (EvalExpF operand) { super (operand); }
}
// ----------------------------------------------------
interface NegFactory<C extends EvalExp<C>> extends Factory<C> {
C neg (C operand);
}
// ----------------------------------------------------
public static class NegFactoryF extends EvalFactoryF implements NegFactory<EvalExpF>
{
@Override public EvalExpF neg (EvalExpF operand) {
return new NegF(operand);
}
}
// ====================================================
public static void main (String[] args)
{
// -1 + 2
NegFactoryF f = new NegFactoryF();
EvalExp exp = f.add(f.neg(f.lit(1)), f.lit(2));
exp.print();
System.out.println();
System.out.println(exp.eval());
}
// ====================================================
}
public final class TorgersenHybridEP
{
// ====================================================
// 0. Initial Setup (data: [Add, Lit], operation: Print)
interface Exp {
void handle (Visitor v);
}
// ----------------------------------------------------
interface Visitor {
void apply (Exp e);
void fallback (Exp e);
}
// ----------------------------------------------------
public static abstract class Node <V extends Visitor> implements Exp
{
@SuppressWarnings("unchecked")
@Override public final void handle (Visitor v) {
if (isV(v)) accept((V) v);
else v.fallback(this);
}
abstract void accept(V v);
abstract boolean isV (Visitor v);
}
// ----------------------------------------------------
public static abstract class Op <E extends Exp> implements Visitor
{
@SuppressWarnings("unchecked")
@Override public final void apply (Exp e) {
if (isE(e)) call((E) e);
else e.handle(this);
}
abstract void call(E e);
@Override public void fallback (Exp e) {
throw new IllegalStateException("Not the right kind of visitor");
}
abstract boolean isE (Exp e);
}
// ----------------------------------------------------
interface ExpVisitor extends Visitor {
void visit (Lit lit);
void visit (Add add);
}
// ----------------------------------------------------
public static final class Lit extends Node<ExpVisitor> implements PrintExp
{
public final int value;
public Lit (int v) { value = v; }
@Override public void print (Print print) {
System.out.print(value);
}
@Override void accept (ExpVisitor v) {
v.visit(this);
}
@Override boolean isV (Visitor v) {
return v instanceof ExpVisitor;
}
}
// ----------------------------------------------------
public static final class Add extends Node<ExpVisitor> implements PrintExp
{
public final Exp left, right;
public Add (Exp left, Exp right) {
this.left = left;
this.right = right;
}
@Override public void print (Print print) {
print.apply(left);
System.out.print('+');
print.apply(right);
}
@Override void accept(ExpVisitor v) {
v.visit(this);
}
@Override boolean isV (Visitor v) {
return v instanceof ExpVisitor;
}
}
// ----------------------------------------------------
interface PrintExp extends Exp {
void print (Print print);
}
// ----------------------------------------------------
public static class Print extends Op<PrintExp> implements Visitor
{
public final void print (Exp e) {
apply(e);
}
@Override void call (PrintExp e) {
e.print(this);
}
@Override boolean isE (Exp e) {
return e instanceof PrintExp;
}
}
// ====================================================
// 1. Add an operation (Eval)
public static class Eval extends Op<EvalExp> implements ExpVisitor
{
private int result;
public final int eval (Exp e) {
apply(e);
return result;
}
@Override void call (EvalExp e) {
result = e.eval(this);
}
@Override public void visit (Lit lit) {
result = lit.value;
}
@Override public void visit (Add add) {
result = eval(add.left) + eval(add.right);
}
@Override boolean isE (Exp e) {
return e instanceof EvalExp;
}
}
interface EvalExp extends PrintExp {
int eval (Eval eval);
}
// ====================================================
// 2. Add a data class (Neg)
interface NegVisitor extends ExpVisitor {
void visit (Neg neg);
}
// ----------------------------------------------------
public static final class Neg extends Node<NegVisitor> implements EvalExp
{
public final Exp operand;
public Neg (Exp operand) { this.operand = operand; }
@Override public void print (Print print) {
System.out.print("−(");
print.apply(operand);
System.out.print(")");
}
@Override public int eval (Eval eval) {
return - eval.eval(operand);
}
@Override void accept (NegVisitor v) {
v.visit(this);
}
@Override boolean isV (Visitor v) {
return v instanceof NegVisitor;
}
}
// ====================================================
public static void main (String[] args)
{
// -1 + 2
Exp exp = new Add(new Neg(new Lit(1)), new Lit(2));
new Print().print(exp);
System.out.println();
System.out.println(new Eval().eval(exp));
}
// ====================================================
}
public final class TorgersenOperationEP
{
// ====================================================
// 0. Initial Setup (data: [Add, Lit], operations: Print)
public interface Exp<V extends Visitor> {
void accept (V visitor);
}
// ----------------------------------------------------
public interface Visitor {
<V extends Visitor> void visit (V self, Lit<V> expr);
<V extends Visitor> void visit (V self, Add<V> expr);
}
// ----------------------------------------------------
public static final class Lit <V extends Visitor> implements Exp<V>
{
public final int value;
public Lit (int value) { this.value = value; }
@Override public void accept (V visitor) {
visitor.visit(visitor, this);
}
}
// ----------------------------------------------------
public static final class Add <V extends Visitor> implements Exp<V>
{
public final Exp<V> left, right;
public Add (Exp<V> left, Exp<V> right) {
this.left = left;
this.right = right;
}
@Override public void accept (V visitor) {
visitor.visit(visitor, this);
}
}
// ----------------------------------------------------
public static class Print implements Visitor
{
@Override public <V extends Visitor> void visit (V self, Lit<V> lit) {
System.out.print(lit.value);
}
@Override public <V extends Visitor> void visit (V self, Add<V> add) {
add.left.accept(self);
System.out.print('+');
add.right.accept(self);
}
}
// ====================================================
// 1. Add an operation (Eval)
public static class Eval implements Visitor
{
public int result;
@Override public <V extends Visitor> void visit (V self, Lit<V> lit) {
result = lit.value;
}
@Override public <V extends Visitor> void visit (V self, Add<V> add) {
add.left.accept(self);
int left = result;
add.right.accept(self);
int right = result;
result = left + right;
}
}
// ====================================================
// 2. Add a data class (Neg)
public interface NegVisitor extends Visitor {
<V extends NegVisitor> void visit (V self, Neg<V> neg);
}
// ----------------------------------------------------
public static final class Neg <V extends NegVisitor> implements Exp<V>
{
public final Exp<V> operand;
public Neg (Exp operand) { this.operand = operand; }
@Override public void accept (V visitor) {
visitor.visit(visitor, this);
}
}
// ----------------------------------------------------
public static class NegPrint extends Print implements NegVisitor
{
@Override public <V extends NegVisitor> void visit (V self, Neg<V> neg) {
System.out.print("-(");
neg.operand.accept(self);
System.out.print(")");
}
}
// ----------------------------------------------------
public static class NegEval extends Eval implements NegVisitor
{
@Override public <V extends NegVisitor> void visit (V self, Neg<V> neg) {
neg.operand.accept(self);
result = - result;
}
}
// ====================================================
public static void main (String[] args)
{
// -1 + 2
Exp<NegVisitor> exp = new Add<>(new Neg<>(new Lit<>(1)), new Lit<>(2));
exp.accept(new NegPrint());
System.out.println();
NegEval eval = new NegEval();
exp.accept(eval);
System.out.println(eval.result);
}
// ====================================================
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment