Cons, Lambda, and Unification

The Question: Cons Cells

Implement functional-programming style Cons cells in Java. Provide six implementations.The implementations should have the following properties:

1. Heterogenous, mutable cons cells.
2. Heterogenous, immutable cons cells.
3. Mutable cons cells that are homogenous under ad hoc polymorphism. If there is a car of the cdr (a cadr), then the car of this cons must be an instance of either the same class or a derived class.
4. Immutable cons cells that are homogenous under ad hoc polymorphism.
5. Mutable cons cells that are completely homogenous. The cadr (if it exists) must be the same type as the car.
6. Immutable cons cells that are completely homogenous.

All six implementations should implement the toString method of java.lang.Object as well as the following interface:

public interface Cons {
   Object car();
   Cons cdr();
};
      

Mutable interfaces should also implement the following interface:

public interface MutableCons extends Cons {
   void setCar(Object) throws ClassCastException;
   void setCdr(MutableCons) throws ClassCastException;
};
      

You will need to throw a new instance of ClassCastException if the types of arguments are inconsistent with the types of other parts of the Cons (depending on what kind of Cons cell you are implementing). You will also need to be familiar with the methods of java.lang.Class, to show cells and to implement type homogeneity constraints.

Immutable

A base class for immutable Cons cells. We add the type checking on top of this.

public class ICons implements Cons {
   private final Object item;
   private final IUCons rest;
   protected ICons(Object ncar, IUCons ncdr) { item=ncar; rest=ncdr; };
   public Object car() { return item; };
   public Cons   cdr() { return rest; };
};
	

Question to the audience: Why is the constructor protected?

Immutable, Untyped

Since the ICons base class doesn't do anything funny with types, the untyped class doesn't need to either.

public class IUCons extends ICons {
   public IUCons(Object ncar, IUCons ncdr) { super(ncar, ncdr); };
};
	

Immutable, Single-Type

public class ISCons extends ICons {
   public ISCons(Object ncar, IUCons ncdr) { 
      if (ncdr) {
         Class check = ncdr.car().getClass();
         if (check == ncar.getClass()) {
            super(ncar, ncdr);
          } else {
             throw new ClassCastException("Inconsistent type");
          }
      } else {
         super(ncar, ncdr);
      }
   };
};
	

Immutable, Narrowing Polymorphic Type

public class INPCons extends ICons {
   public INPCons(Object ncar, IPCons ncdr) { 
      if (ncdr) {
         Class check = ncdr.car().getClass();
         if (check.instanceOf(ncar)) {
            super(ncar, ncdr);
          } else {
             throw new ClassCastException("Inconsistent type");
          }
      } else {
         super(ncar, ncdr);
      }
   };
};
	

Immutable, Broad Polymorphic Type

public class IBPCons extends ICons {
   protected final Class kind;
   public IBPCons(Object ncar, IPCons ncdr) { 
      if (ncdr) {
         if (ncdr.kind.instanceOf(ncar)) {
            super(ncar, ncdr);
          } else {
             throw new ClassCastException("Inconsistent type");
          }
      } else {
         kind = ncar.getClass();
         super(ncar, ncdr);
      }
   };
};
	

Mutable

A base class for mutable Cons cells. We add the type checking on top of this.

public class MCons implements MutableCons {
   private  Object item;
   private  MCons rest;
   protected MCons(Object ncar, IUCons ncdr) { item=ncar; rest=ncdr; };
   public Object car() 
      { return item; };
   public Cons   cdr() 
      { return rest; };
   public void setCar(Object o) throws ClassCastException
      { item = o; };
   public void setCdr(MutableCons m) throws ClassCastException
      { rest=m; };
};
	

The Question: Lambda Expressions

Implement lambda expressions in Java. A lambda expression should conform to the following interface:

public interface Lambda {
   Lambda lambda(Lambda l);
   Lambda apply(Lambda l);
   Lambda beta(Lambda l);
   Lambda eta();
}
      

Beta reduction should implicitly perform alpha reduction if required in order to maintain consistent bindings. The class should also implement the method toString from java.lang.Object.

Class Hierarchy

public abstract class LambdaExpression implements Lambda { ..... };
public class Name        extends LambdaExpression { .... };
public class Abstraction extends LambdaExpression { .... };
public class Application extends LambdaExpression { .... };
public class Parentheses extends LambdaExpression { .... };
	

If you want to get fancy, you add Number, PrimOp.

Base Class

class Name;
public abstract class LambdaExpression implements Lambda { 
   protected abstract boolean isBound(Name n);
   protected abstract LambdaExpression replace(Name n, LambdaExpression);
};

Name Class

public class Name extends LambdaExpression {
   protected String name;
   private static int counter = 0;
   public Name() { s = "AName" + (String) counter; counter++; }
   public Name(String s) { name=s; };

   public Lambda lambda(Lambda l) {
      return new LambdaAbstraction(this, l);
   };

   public Lambda apply(Lambda l) {
      return new Application(this, l);
   };

   public Lambda beta(Lambda l) {
      return l;
   };

   public Lambda eta() {
      return this;
   };

   protected boolean isBound(Name n) {
      return (n.name==name);
   };
   protected LambdaExpression replace(Name n, LambdaExpression l) {
      if (n.name==name) {
         return l;
      } else {
         return this;
      }
   };
};

Lambda Abstraction

public class Abstraction extends LambdaExpression {
   protected Name name;
   protected LambdaExpression expr;

   public Lambda lambda(Lambda l) {
      return new Abstraction(new Name(), Application(this, l));
   };

   public Lambda apply(Lambda l) {
      return new Application(this, l);
   };

   public Lambda beta(Lambda l) {
      if (expr.isBound(name)) 
         return expr.replace(name, l);
      else return this;
   };

   public Lambda eta() {
      if (expr.isBound(name)) 
         return this;
      else return expr;
   };

   protected boolean isBound(Name n) {
      return expr.isBound(n);
   };
   protected LambdaExpression replace(Name n, LambdaExpression l) {
      return expr.replace(n, l);
   };

Application

public class Abstraction extends LambdaExpression {
   protected LambdaExpression f;
   protected LambdaExpression n;

   public Lambda lambda(Lambda l) {
      return new Abstraction(new Name(), Application(this, l));
   };

   public Lambda apply(Lambda l) {
      return new Application(this, l);
   };

   public Lambda beta(Lambda l) {
      return this; // beta only does something with abstraction
   };

   public Lambda eta() {
      return this;
   };

   protected boolean isBound(Name name) {
      return f.isBound(name) || n.isBound(name);
   };
   protected LambdaExpression replace(Name name, LambdaExpression l) {
      return new Application(f.replace(name, l), n.replace(name, l));
   };

A Horn Clause

• A constant.
• A structure.

A Structure

Has a name. This is also called the functor.

Has some number of arguments, each with a variable (a name)

The name and the arguments are the head or the consequent.

Has zero or more terms.

Each term identifies another clause.

Definition: Unification

• A constant unifies with itself.
• A structure unifies with another structure if they have the same name and the same number of arguments and the arguments all unify.
• A variable unifies with anything, assuming that thing's meaning.

Unification is commutative.