// File Nat.java /* Natural number example. H. Conrad Cunningham 17 January 2004 The cluster of classes consisting of base class Nat and its subclasses Zero, Err, and Succ defines a representation for the "natural numbers" with a hierarchical class structure inspired by Peano's Postulates. It does not use any builtin integer type. We consider 0 as being a natural number as is customary for many computer scientists. Mathematically, we can define the set Nat (of natural numbers) as follows: x in Nat if and only if (1) x = 0 -- zero or (2) (Exists y in Nat :: x = Succ(y)) -- successor function This design uses the Composite pattern to represent natural numbers. The abstract base class for the set is Nat. Subclass Zero is the leaf case of the Composite pattern; it represents 0. Subclass Succ is the composite case of the Composite pattern; it represents a successor of the single Nat it contains. In addition, we introduce a leaf case Err to represent errors. The design and implementations of Zero and Err also reflect the Singleton design pattern, which provides for exactly one instance to be created. Err also reflects the Null Object pattern, in that its instances are null or inert objects that can be safely returned by operations in error situations. This implementation essentially gives a a unary representation for the natural numbers -- one Succ object in a linear structure for each natural number value greater than 0. */ /* Class Nat is the base class of our Natural numbers. It specifies the operations that Nats must support. Additional operations should be included. */ abstract public class Nat { abstract public Nat add(Nat n); abstract public Nat sub(Nat n); abstract public boolean isLess(Nat n); } // File Zero.java /* Part of Natural number example. H. Conrad Cunningham 17 January 2004 Class Zero represents the natural number value zero. It is a leaf subclass in the Composite pattern and is designed and implemented with the Singleton pattern to ensure that exactly one instance is created. */ public class Zero extends Nat { private Zero() {} // private constructor for Singleton public Nat add(Nat n) { return n; } // 0 + n = n public Nat sub(Nat n) { if (n == this) { return this; } // 0 - 0 = 0 return Err.getErr(); // undefined } public boolean isLess(Nat n) { return (n != this); } // 0 < n public boolean equals(Object n) { return (n == this); } // exactly one value of Zero public String toString() // method from class Object { return "0"; } // Set up Singleton pattern for this type public static Zero getZero() { return theZero; } private static Zero theZero = new Zero(); } // File Succ.java /* File Succ.java Natural number example. H. Conrad Cunningham 17 January 2004 Class Succ represents the successor function in the natural number definition. It maps its argument (i.e., contained Nat value) to its successor (i.e., one larger value). It is a composite subclass in the Composite pattern. */ public class Succ extends Nat { public Succ(Nat n) { val = n; } public Nat pred() // operation of Succ, not Nat { return val; } public Nat add(Nat n) { return val.add(new Succ(n)); } // m + n = (m-1)+(n+1) public Nat sub(Nat n) { if (n == Zero.getZero()) { return this; } // m - 0 = m return val.sub(((Succ)n).pred()); // m - n = (m-1) - (n-1) } public boolean isLess(Nat n) { if (n == Zero.getZero()) { return false; } // m > 0 return val.isLess(((Succ)n).pred()); // m < n = (m-1)<(n-1) } public boolean equals(Object n) // method from class Object { if (!(n instanceof Succ)) { return false; } return val.equals(((Succ)n).pred()); // (m=n) = ((m-1)=(n-1)) } public String toString() // method from class Object { return ("1+" + val); } private Nat val; // predecessor value } // File Err.java /* Part of Natural number example. H. Conrad Cunningham 17 January 2004 Class Err represents an error condition. It is a leaf subclass in the Composite pattern and is designed and implemented with the Singleton pattern to ensure that exactly one instance is created. Perhaps in a more sophisticated version, Err would carry an indicator of what type of error is needed. In that case, a Singleton could not be used. */ public class Err extends Nat { private Err () { } // private constructor for Singleton public Nat add(Nat n) { return this; } // Err + n = Err public Nat sub(Nat n) { return this; } // Err - n = Err public boolean isLess(Nat n) { return false; } // Not comparable. Probably bad design. // This is tricky because of Err nesting down inside Succ // structures. public boolean equals(Object n) { if (n == this) { return true; } // Err = Err if (n == Zero.getZero()) { return false; } // Err != 0 if (!(n instanceof Nat)) { return false; } return (equals(((Succ)n).pred())); // Err = Succ(Err) } public String toString() // method from class Object { return "ERR"; } // Set up a Singleton for this type public static Err getErr() { return theErr; } private static Err theErr = new Err(); } // File TestNat.java /* Test driver for Natural number example. H. Conrad Cunningham 17 January 2004 This is a quick-and-dirty, partial test driver for the Nat cluster of classes. */ public class TestNat { public static void main(String[] arg) { Nat zero = Zero.getZero(); System.out.println("0 : " + zero); Nat three = new Succ(new Succ(new Succ(zero))) ; System.out.println("1+1+1+0 : " + three); Nat six = three.add(three); System.out.println("3+3 : " + six); System.out.println("3-3 : " + three.sub(three)); System.out.println("3-6 : " + three.sub(six)); System.out.println("3=3 : " + three.equals(three)); System.out.println("3=6 : " + three.equals(six)); System.out.println("0=6 : " + zero.equals(six)); System.out.println("0=0 : " + zero.equals(zero)); Nat err = Err.getErr(); System.out.println("Err = 1+1+Err : " + err.equals(new Succ(new Succ(err)))); System.out.println("3<3 : " + three.isLess(three)); System.out.println("3<6 : " + three.isLess(six)); System.out.println("0<6 : " + zero.isLess(six)); System.out.println("0<0 : " + zero.isLess(zero)); } }