Languages are defined inductively. Example: combinatory logic. K is a combinator. It represents the function \x y -> x S is a combinator. It represents the function \x y z -> (y x)(z x) (MN) is a combinator if and only if M and N are combinators It represents the function that results when you apply the function M represents to the function N represents. This is all the ways there are to build a combinator. We can have abbreviations, like I = SKK represents the identity function See http://en.wikipedia.org/wiki/Combinatory_logic We can map this directly onto SML: datatype combinator = K | S | APP of (combinator * combinator); or Haskell: data Combinator = K | S | App Combinator Combinator We can map it less directly to Java: abstract class Combinator {} class K extends Combinator {} class S extends Combinator {} class App extends Combinator { Combinator lhs, rhs; ... } This is the Composite pattern. A definition like this gives us an induction scheme for proving properties of combinators To prove (for all combinators x) p(x) prove p(K) prove p(S) prove ((for all combinators m, n) p(m) & p(n)) => p(APP (m,n)) and a primitive recursion scheme for defining functions of combinators: f(K) = ck f(S) = cs f(App x y) = ca x (f x) y (f y) where ck and cs are constants and ca is some function (which might well ignore some of its arguments). It is easy to write definitions like this in functional languages (see "value" in arith.hs), but the cases have to be scattered across many classes in OO languages, unless you use the Visitor pattern. With immutable data structures, "hash consing" can pay off. In the Java version of my model answer for the assignment, And and Or have a static field HashMap> and the "smart constructor" for And does (simplifying a bit): private And(Formula l, Formula r) { lhs = l; rhs = r; cache.get(lhs).put(rhs, this); } public static Formula of(Formula l, Formula r) { if (l == r) return l; HashMap h = cache.get(l); if (h == null) { h = new HashMap(); cache.put(l, h); } Formula a = h.get(r); return a == null ? new And(l, r) : a; } This means, for example, that once we have constructed a Formula object for (X&(Y|Z)) we never do so a second time. But we would for (X&(Z|Y)) or ((Y|Z)&X). We can cache function results in hash cons nodes.