We have seen that we can map the Lambda Calculus down into a combinatory algebra. How might we implement a combinatory algebra in the Java environment?
The carrier set of an algebra is the set of objects upon which the operation(s) of the algebra work. Clearly, the carrier set of our Algebra should be implemented as a set of Java objects.
One approach would be to treat our carrier set as a Java class P2KObj, which would thus be a subclass of the generic Java class Object. P2KObj in turn would have subclasses P2KNum and P2KFun, representing numbers and functions respectively. The snag about this approach is that it would not be so easy to use existing Java classes such as the BigInteger class.
So, it's probably better to treat the carrier set of our algebra as being simply the Java Object class, and to develop a P2KFun class, which we really need to implement functions.
Each distinct function in POP2000 will be implemented using a separate sub-class of P2KFun, essentially because only classes can actually contain code, and (in the un-optimised form) calling a function is achieved only by activating its apply-method. So the apply-methods of distinct functions have to be distinct, that is they must be defined for different classes. The actual function-object will be the sole instance of its associated class.
Clearly, some new type classes (such as Rational) would need to be developed; others, such as integers of arbitrary precision, could simply be Java's BigInteger class. All these might be sub-classes of Java's abstract Number. class (except that that class consists of a lot of "useful jars to put things in").
The list of types that are required for POP2000 is as follows:
Boolean,Char,Null,Number,Pair,
Procedure,String,Symbol,Vector,
Application, Abstraction, Theorem
Of these, all but Application, Abstraction, Theorem
are Scheme datatypes. They serve to support the representation of a
Lambda-Calculus based logic within POP2000. Note that we do not follow
the Lisp tradition and represent terms as list-structures built out
of the Pair datatype. Instead we have a separate
Application datatype, whose concrete representation is not
specified as part of the POP2000 specification to the extent it would be if
pairs were used.
" of the combinatory algebra is most
obviously rendered using an apply method, which is defined for
every object of the P2KFun class.
So, the combinatory
algebra expression f x is rendered in Java
as
f.apply(x)
where f is a procedure-object (of type P2KFun) and
x can be any object.
Now, certainly in the untyped Lambda Calculus (with constants) it is possible to apply a non-function. This will be manifest in the Java framework because we will have to cast an object of unknown type to have type P2KFun before we can apply it: casting a non-function down to that type will raise an exception, which we'll need to catch in a user friendly way.
Let's consider the hd function, which finds the first component of a pair (what's called car in LISP). This will be the sole member of the class Hd. The class definition for Hd is quite simple. It's [1] a direct sub-class of the P2KFun class. The apply-method [2] takes any object as an argument, but, to succeed, this object p must be of class Pair. We return [3] the hd field of the pair.
If a non-pair is given, the cast down the hierarchy to Pair will raise an exception. Note, that we will have to define an exception-handler for this class, so that the user is given the most useful possible information about what's amiss.
class Hd extends P2KFun /* [1] */
{
public Object apply (Object p) /* [2] apply method */
{return ((Pair)p).hd;} /* [3] get hd field - must be Pair */
}
Most unary functions will follow this simple pattern. The main practical
distinction will be between whether or not an internal method-invocation
is required to achieve the required computation. For hd, the
p.hd expression is (probably) a field-access. On the other hand,
if we want to negate a member of the P2KNumber class, then
a negate method-call will be required to do the right thing for
the particular kind of number we happen to have.
class Negate extends P2KFun /* [1] */
{
public Object apply (Object p) /* [2] apply method */
{return ((P2KNumber)p).negate;} /* [3] call the negate method */
}
Where non-unary functions are involved, if we follow the specification of the Lambda Calculus literally we will always have to curry. For example, in implementing ((plus 2) 3) we first create a (plus 2) function-object, and then apply this new object to 3. Various optimising schemes to avoid doing this unless strictly necessary are conceivable. For example we might have apply2, apply3... methods, so that the above might be translated as plus.apply2(Integer(2), Integer(3)) However we'll defer consideration of these.
Conceptually, the simplest approach to creating these curried functions might be to have a unique curried-class for each possible arity of call. So, for example, (plus 2) might be translated into a curried_plus object.
However it seems wasteful to have several distinct classes for just one operation. The code that accomplishes the currying ought to be generic and not specific.
One approach to making a generic apparatus for currying is shown below. In this case, we handle binary functions using a Curried2 object which represents a binary function with one of its arguments "partially applied".
Suppose plus is the (unique) member of class Plus [1] that implements the addition function. Then the apply method [2] for plus creates a new Curried2 object [4]. This embodies the argument x of the addition, and also the plus object itself.
The apply2 method [5] is activated when the second argument to plus is available. It takes as arguments [5] the two objects to which plus has been successively applied. These [6] are cast down the hierarchy as numbers, and the "plus" method of x is called to add them.
class Plus extends P2KFun // [1]
{
public Object apply (Object x) // [2]
{
P2KNumber nx = (P2KNumber) x; // [3]
return new Curried2(this, nx); // [4]
}
public Object apply2 (Object x, Object y) // [5]
{
return ((P2KNumber)x).plus((P2KNumber)y); // [6]
}
}
The Curried2 class provides generic support for the implementation of binary functions. It contains 2 fields. The f field [1] holds the function which has been curried, while the arg1 field [2] holds its first argument which has been given to the function. A member of the class (of which there can be arbitrarily many) is created [3] by passing it the function-object and its first argument (see [4] above). These arguments are simply stored in the fields.
When the curried function is applied to its argument, arg2, it calls the apply2 method of the original function-object (whatever it was) to finish "doing its thing".
class Curried2 extends P2KFun
{
private P2KFun f; // [1]
private Object arg1; // [2]
public Curried2(P2KFun f, Object arg1) // [3]
{this.f = f; this.arg1 = arg1;} // [4]
public apply(Object arg2) // [5]
{return f.apply2(arg1,arg2);} // [6]
}
For functions of more than two arguments, the above approach would get quite complicated, with the need to have curried classes for every possible adicity. An alternative approach is shown below. Here the Curried object contains an array which holds the arguments acquired so far. When this array contains the right number of arguments, the doit method of the original function is called.
The new Plus class is shown below. At [1] as before, we define the apply method, but when we make the Curried object [2], we pass an extra parameter specifying the reqired number of arguments. Addition is actually performed by the doit method [3], which takes as argument an array args containing the accumulated combinatory-algebra arguments. Having checked [4] that we have exactly 2 arguments, we cast them as numbers [5] and [6], and [7] call the plus method to do the actual computation.
class Plus extends P2KFun
{
public Object apply (Object x) // [1]
{
return new Curried(this, x, 2); // [2]
}
public Object doit(Object [] args) // [3]
{ if (args.length != 2) throw new Exception... // [4]
{ P2KNumber arg1 = (P2KNumber)args[0], // [5]
arg2 = (P2KNumber)args[1]; // [6]
return arg1.plus(arg2); // [7]
}
}
}
The new Curried class is shown below. Each object in the class
contains 3 fields. The f field [1] holds the function object which
has been curried, the args field [2] holds in an array the
arguments accumulated so far, while the depth field [3] holds the
total number of arguments to be accumulated before the computation to be
done by f can be performed.
There are two constructors. The first [4] is the one called by the function object to be curried. The function-object f is itself passed in, together with the first argument x, and depth which is the number of arguments f needs to accumulate to be activated. This constructor initalises [4-5] the f, depth fields from the arguments. The args field is initialised [7-8] with an array consisting of the one argument x already available.
Perusal of the apply method for Curried shows that it calls a constructor for Curried. This second constructor [9] takes an extra argument, which is an array of the arguments accumulated so far. The f, depth fields are initialised as before [10-11], but the args field [12] is initialised to an array large enough to hold the arguments now accumulated, including x. Arguments are copied from the old args array to the new [13-14]. As Mr Schwartz so perspicuously observes ("My vote went for allocation of new arrays; memory is cheaper these days than debugging time".) it's a good idea to make a new array - actually it's essential, because at any stage in the currying process, the same function-object may be curried to different objects. Finally [15] the new argument x is installed in args.
The apply method [16] is quite simple. If enough arguments [17] have been accumulated, the doit method of the original function is invoked. Otherwise [19] a new Curried object is created embodying the argument x just acquired.
class Curried
{
private P2KFun f; // [1]
private Object args[]; // [2]
private int depth; // [3]
public Object curried(P2KFun f, Object x, int depth) // [4]
{ this.f = f; // [5]
this.depth = depth; // [6]
this.args = new Object[1]; // [7]
args[0] = x; // [8]
}
public Object curried
(P2KFun f, Object[] args, Object x, int depth) // [9]
{ this.f = f; // [10]
this.depth = depth; // [11]
this.args = new Object[args.length+1]; // [12]
for(int i=0; i
Incidentally - we need not regard these two methods of implementing
currying as mutually exclusive - they are not. The first would prove
more efficient for binary functions, while the second would be used for
greater arities.
The K combinator can easily be implemented in this framework.
class K_combinator extends P2KFun // [1]
{
public Object apply (Object x) // [2]
{
return new Curried2(this, x); // [3]
}
public Object apply2 (Object x, Object y) // [4]
{
return x; // [5]
}
}
The S combinator is also easy.
class S_combinator extends P2KFun
{
public Object apply (Object f) // [1]
{
return new Curried(this, f, 3); // [2]
}
public Object doit(Object [] args) // [3]
{ if (args.length != 3) throw new Exception... // [4]
{ P2KNumber f = (P2KFunction)args[0], // [5]
g = (P2KFunction)args[1]; // [6]
x = args[2] // [7]
return (f.apply(x)).apply(g.apply(x))) // [8]
}
}
}