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<Formula, HashMap<Formula, Formula>>
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<Formula,Formula> h = cache.get(l);
        if (h == null) {
            h = new HashMap<Formula,Formula>();
            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.