Introduction

    The history of Object-Oriented and Functional programming shows that they came from two different branches of the programming language tree. Functional is its own main branch with a venerable history going back to lisp and the lambda calculus. On the other hand OO is apparently and offshoot of procedural programming. I believe the second is a coincidence of history and the development of ideas. Today we see the beginnings of a growing together of Functional and OO programming. Here I will explore some of the connections to gain a better understand of where these paradigms are headed and what they really mean and say.


Patterns vs. Higher Order Functions


Higher Order Functions & Their Use

    A function is something that can be invoked or, to use the terminology of the lambda calculus, can be applied to arguments. A higher order function is one that may take functions as arguments or return functions and does some operation with them, either manipulating them or applying them. Examples include a sort function which takes a comparison function or a function which takes two functions and returns a function which invokes both.


Command, Strategy, Decorator, Composite Patterns

    Each of these patterns uses an object to encapsulate behavior. The command pattern represents some behavior which you know needs done but you may have no idea what it does. The strategy is a behavior you need and you have some abstract idea what it does. It often operates in a context or returns something to the user. The decorator allows the addition of behavior to an object which already exists. The composite pattern combines multiple objects, which it is abstractly equivalent to, into one, in some ways composing their behavior. In each case there is a single or multiple ways to invoke or apply the object. The command and strategy patterns often have only one way, while the others usually have more then one way. In these cases objects are being used as functions. Indeed they are equivalent to functions. Each pattern includes some context which makes use of these objects by taking, returning or manipulating them.

    Some examples may be helpful. Consider again the idea of sorting, in Scheme and other languages which support function passing it would be standard to pass a function representing the comparison to be used. This allows the sorter to sort any type of thing according to any criteria. In an object oriented system a strategy is passed in to represent this. And it again allows any type of object to be sorted according to any criteria.

    Parallels of the command pattern are less frequently found in functional languages because commands often involve causing side effects on some part of the system. Consider a possible implementation of a network library. Packets could come in at any time. Rather than polling to see if one has arrived, a command could be given to the network layer which it would invoke when a packet arrived. This would be implemented almost identically in a functional language like Scheme and an object-oriented language like Java.

    For an example of a decorator, consider again the idea of a sorter that takes a comparison strategy. It might be very reasonable to want the same algorithm to be able to sort in reverse order without modifying the sorter or the comparison strategies that had already been written. A good way to do this would be to write a function or object which held another comparison strategy and passed to it the two things to be compared in reverse order. Thus reversing the comparison. This would be a decorator.

    The composite pattern can be seen in the simple example of the mathematical composition of two functions. An example one might actually see in a program is again tied to the example of sorting strategies. Imagine that a sort strategy was able to return both that something was less than another entity and also that the two things were equal. If we are sorting an address book we may have sorting strategies to sort by both first and last name. Imagine that we would like to sort by last name and then first name if two people have the same last name. A composite could hold both sorting strategies and when the first returned equal check the second. An important thing to note is that it is abstractly equivalent to a sorting strategy. That is, it can be used anywhere a sorting strategy is expected.


Anonymous Inner Classes & Anonymous Lambdas

    In Scheme it is very common to create an unnamed function inside another, in this case the function is scoped to the enclosing function. This is very close to Java's anonymous inner classes since, as has been seen, objects can be equivalent to functions. This extends the power of higher order functions and design patterns. The connection is visible in the requirement in Java that variables accessible in the enclosing scope be final if they are to be accessed from within the class. It is important to note that this ability is not new to OO with Java. It has always been possible but would have required declaring a new class and passing in all the parts of the context which are needed. In C++ this would be aided by the friend keyword but that is not required. However, just as not many people will discusses a concept for which they have no word. Not may programmers will code a structure for which they have no syntax. That is why Java is the first wide spread use of the Swing style listener event model, because it is the first language to provide a good syntax for it.


Comparison: Object-Oriented & Functional Booleans


Boolean Object Design (Demo Applet)

    First let us consider the design of objects to represent boolean values according to the Object Oriented paradigm. The test of the code designed herein can be seen in the Demo Applet.


Abstract Boolean Superclass

    Since we are modeling a system of true and false we should represent the ways in which they are abstractly equivalent in an abstract super class we will call ABool. We could add many boolean operations such as and, or and not. However, we would like to make our interface minimally complete. Otherwise we would have to set about adding every possible logical operation. We will see in a later section that only one operation is require for this. Till then we will leave the ABool class empty.


Singleton Pattern & Immutability

    Since the objects will represent the abstract concepts of true and false they will be immutable. That is, true is always true and does not change, likewise with false. Since there is only one unchanging truth value we will use the Singleton pattern and insure that none of the methods of true mutate it. The classic singleton pattern would create a private static instance and then provide a public static accessor to it. However in this case we would like to hide that from the users. To our users there is only ABool which has two values true and false. For that reason we make both the True and False classes package and provide static instances of them in the ABool class like so:

public static final ABool TRUE = True.Singleton();
public static final ABool FALSE = False.Singleton();

    This hides the fact that both True and False are singletons and doesn't expose the fact that they are implemented as two different classes. To the user there is only two ABool objects which are distinguished by behavior.


Visitor to the Booleans

    The key to our implementation of object-oriented boolean values is, as eluded to before, the visitor design pattern. The visitor pattern allows one to add polymorphic behavior to classes . Almost as if one were adding a method. Suppose that the function foo was never implemented for our booleans. Of course foo depends on whether they are true or false. The classic solution would be to add a method foo to our boolean classes so that it would be polymorphic and we could write the necessary different behaviors for foo in the True and False classes. The alternative is to simply write a new visitor, not changing existing classes at all. In order to achieve this all one needs is an interface for the visitor.

public interface IBoolVisitor
{
    public Object visitTrue(Object param);

    public Object visitFalse(Object param);
}

    And then to implement the appropriate accept method as per the visitor design pattern in ones boolean classes.

In ABool:
    public abstract Object accept(IBoolVisitor visitor, Object param);
In True:
    public Object accept(IBoolVisitor visitor, Object param)
    {
        return visitor.visitTrue(param);
    }
In False:
    public Object accept(IBoolVisitor visitor, Object param)
    {
        return visitor.visitFalse(param);
    }

    Once the visitor hook is provided all operations can be defined using it. Note how simple the boolean classes are. They contain no other methods but accept, their constructors and singleton accessors. The interfaces of True and False are minimally complete. Any operation which might be desired can be defined on them but they contain no extra methods, ie. ones definable in terms of other available methods. Finally, note that true and false are distinguished only by their behavior in this system.


Functional Boolean Design

    The definition of boolean values in the lambda calculus was given by Church as (also shown in scheme):

 true = lx.ly.x  false = lx.ly.y 

(define true
   (lambda (x y)
        x))
 

(define false
   (lambda (x y)
        y))

    The two values true and false are in this system both functions. In this way they are abstractly equivalent to all the functions. However at another level they are abstractly equivalent to each other and not to the rest of the system in that we think of them as both being booleans. This equivalence is not expressed in the system except in the behavior of the two functions. They are black boxes and can't be seen into. Only their behavior in the system defines them.


Actual comparison

    In both object-oriented and functional styles the state of the boolean is defined by its behavior, there is no way to know the state beyond interacting with it and observing its behavior. True behaves in one way, false in another. Each has the behavior of selecting between two choices. OO bundles the two cases into the visitor object while the functional doesn't. However, it is possible to exactly mimic in objects the way functional programming does it. The boolean could take two objects and return one depending on its state. These object could either be values or they could be commands allowing us to simply execute the command returned. That reflects the idea that in the lambda calculus whatever is returned is a function that can be invoked. It is also possible to turn the picture around and replicate OO in the functional style by using message passing.

    Why go to the trouble of using visitors and not just stick yo OO programming? The point of the visitor is focused around mutability. If the boolean object were mutable then the visitor situation would provide us with a context in which to execute the visitor, allowing us to mutate that context. It can also be connected to the idea of mimicking lazy evaluation. That is, in a scheme expression like (#t (foo) (infinite-loop)), since it would return the result of the first call and calls aren't side effecting, the second call need not be evaluated. In this case avoiding entering the infinite loop. This second reason is a weaker, since we could just build lazy evaluation into our functional languages.

    There is an important difference between the act of deciding on something ie. an if statement and a boolean which embodies that state to allow multiple uses of that state, but booleans are defined in terms of their behavior. It would seem we should separate action and persistence. That is to say create a dumb (no behavior) boolean value and use an if statement to decide based on it. Why not do this? Two reasons are that we wouldn't get type discovery and we don't have the idea of working in a context.

    There is a question of whether a boolean should represent a mathematical object which is either true or false in which case it would be logical for it to be immutable. Alternatively maybe it simply represents an entity which is in one of two states in which case it make sense for it to be mutable. In this discussion I have focused on the immutable. I think the choice depends on purpose and it would be reasonable to have both in a system. The mutable ones could be implemented in terms of the immutable ones. An issue to be resolved would be that the visitors for immutable booleans should probably be allowed to visit the mutable booleans.


Amendment: Current Thoughts

    The above work reflects my thoughts on the situation in the Spring of 2001. Since that time I have spent much time and effort refining my understanding of the concepts involved. While I still believe that as the first section suggests objects can be used to simulate higher order functions, I now believe the connection is more fundamental. I now consider the concept of class and function to be synonymous. OO programming has traditionally lacked the power and flexibility provided by functional languages in relation to functions. However, these powers are not in conflict with OO and so there is no reason they shouldn't be added to the OO perspective. Indeed I believe they will be found to be complementary to the OO style.

    In addition to considering class and functions synonymous, I now see the concepts of environment/function invocation and object as synonymous. That is to say that an object is the environment resulting from the invocation of a function. From this perspective the OO paradigm as granted the greater power and flexibility. In contrast many functional languages like Scheme don't even have environments as values. OO should continue to provide the power and flexibility they have in this area.

    The above consideration of boolean values in both OO and functional is well balanced. If, however I were to do it again I would focus on the connection between the immutable and mutable aspects of the situation. Functional has traditionally handled immutable models while OO handles mutable ones. I believe they are complementary, that OO the correct way to incorporate mutability into to functional programming. And functional programming is the correct way to integrate immutability into OO programming. What remains is to discover the interconnections and interplay between these two concepts