I was recently asked by my supervisor to have a look at the lambda abstractions library that is added to the new Java JDK (
Java 8). Then, we had the idea of implementing Church numerals using two different programming techniques. One is to implement it using the visitor design pattern, and the other is to use the new lambda abstractions in java 8.
Church numerals is a way of presenting natural numbers using lambda calculus. It uses the famous algebraic idea of presenting zero and then presenting the other natural numbers using the successor function. Church presented natural numbers using the following lambda expressions :
- λs. λz. z ------> representing zero.
- λs. λz. s z -------> representing successor of zero.
The idea here is that you get two input functions (s and z). If you applied only z, then you are presenting zero. If you applied s on z (once) you get the presentation of the number one. if you applied s twice on zero (
λs.
λz. s (s z) ) then its the presentation of the number 2, and so on..
To present Church numerals in Java using the visitor design pattern. I started with implementing the
Visitor interface, It will have two methods, one is to replicates the zero function and the other as the successor function.
1
2
3
4
5
6
7
| public interface Visitor {
public <T> T visitZero(Zero z);
public <T> T visitSucc(Successor s);
}
|
I presented the natural numbers with three classes, an abstract class (
NatNum) for all natural numbers, class Zero and the class Successor.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| abstract class NatNum {
public abstract <T> T visit(Visitor vis);
}
class Zero extends NatNum {
@Override
public <T> T visit(Visitor vis) {
return (T) vis.visitZero(this);
}
}
class Successor extends NatNum {
NatNum of;
public Successor(NatNum off) {
of = off;
}
@Override
public <T> T visit(Visitor vis) {
return (T) vis.visitSucc(this);
}
}
|
The classes have the to implement the method
visit(visitor vis) . The idea here is that visitZero is applied when the number zero visits the Visitor interface. The same applies for the Successor, but in that case visitSucc is used. I did that to differentiate
between the zero function and the successor function in the Church numerals. Now, by writing a class that implements the interface Visitor, we can define the behavior of the visitZero and visitSucc functions. I will show this in an example later.
To present Church numerals using the new lambda abstraction in Java 8 - I actually advice you to read the manual of lambda abstraction on Oracle website -, I made also three classes, however, instead of taking a Visitor class in the argument of the method, I take two functions ( fZero and fSucc)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| abstract class NatNum {
public abstract <T> T visit(Function<Zero, T> fZero,
Function<Successor, T> fSucc);
}
class Zero extends NatNum {
public <T> T visit(Function<Zero, T> fZero,Function<Successor, T> fSucc){
return fZero.apply(this);
}
}
class Successor extends NatNum {
NatNum of;
public Successor(NatNum off) {
of = off;
}
public <T> T visit(Function<Zero, T> fZero,Function<Successor, T> fSucc) {
return fSucc.apply(this);
}
}
|
The function
fZero takes a
Zero object and returns an object of generic type
T.
fSucc takes a
Successor object and returns also an object of type
T. In the visit function of the
Zero object, fZero is applied on the instance of the object. In contrary with the
Successor object as
fSucc is applied on the
Successor object.
The result here is almost the same when we apply an operation on the Church numerals, either with the visitor pattern or with the lambda abstraction. I worked on a small example that evaluates the given Church numeral and returns its value in integers. For example, if I have (
λs.
λz. z), it should return the number 0.
λs.
λz. s (s (s z)) should return 3.
For the visitor pattern, I implemented a class "EvalVisitor" that implements the Visitor interface,
1
2
3
4
5
6
7
8
9
10
| public class EvalVisitor implements Visitor {
Integer visitZero(Zero z) {
return 0;
}
public Integer visitSucc(Successor s) {
return Integer.valueOf(new Integer(1) + (Integer) (s.of).visit(this));
}
}
|
The basic idea of
EvalVisitor is that when the method
visit is applied on a
Zero object and is redirected to the method
visitZero, it will just return the result zero. If it is a
Successor object, then
visitSucc will be applied on the object by adding 1 to the recursive call (visit ) on the rest of the Church numeral.
For the lambda calculus, we can think of the problem in a completely functional way, for example we have the function eval that takes a Church numeral and returns an integer, it is defined as follows:
eval(Zero) = 0.
eval(Sucessor(x)) = 1 + eval(x).
In java, we create the method "
eval(NatNum x)" which is defined as follows:
1
2
3
| public static Integer eval(NatNum num1) {
return (Integer) num1.visit(n -> 0, n -> 1 + eval(n.of));
}
|
It uses the method
visit on the given
NatNum, providing two functions, one is a simple function returning 0, which is applied on the Zero objects and one that returns 1 and recursively call eval on the
of of the
Successor object.
My point of view is that the potential of lambda abstractions and functions in Java 8 will reduce the amount of code written making it easier to read and less buggy ! I will add more examples in another post in the following days !
PS, its my first technical post ever so I apologize if the writing technique is not that good !
