... abandon all type information

Introduction

(Note: links here point either off-site or into the pure fun API documentation)

Pure Fun is a free and simple, but history conscious exploration of functional programming concepts implemented in fairly plain old Java.

It is free in that it falls under an MIT style license.

It is simple in that its core contribution is a Function class that provides an apply method and allows derived classes to implement specific functions by redefining a single method.

An effort has been made to make using functions in your code simple, too. Therefore much of the remaining code is concerned with passing arguments to functions in a simple and readable manner (see the examples below)

The static members of the PF class provide a core set of higher order functions to combine functions in the declarative style, that is typical for functional programming.

Pure Fun is history conscious in that it provides many functional programming examples from the classic literature in the included unit tests. It also provides an (incomplete, as of yet) implementation of the FP system proposed in John Backus' Touring Award lecture "Can Programming be liberated from the Von Neumann Style"

In addition, there are LP utilities for dealing with lists in a LISP like fashion (with cons, car and cdr) where these lists also implement the java.util.Collection interface to allow for easy mixing of programming styles, where this might be desirable.

There is likewise a collection of LZ tools in support of lazy evaluation (based on force and delay) with a stream implementation providing for infinite lists implementing the java.util.Iterable interface.

Based on these tools I hope to be able one day to finish the implementation of the Dice Of Doom game as described in the book Land Of Lisp by Conrad Barski.

There's also some NUM tools for number crunching and some half baked experiments with continuations, thus the following warning might be in order:

This product may contain trace amounts of Lisp

Why Java?

Java has two features that make the task of providing functional programming concepts considerably easier: There is an ongoing discussion of providing a construct called closure to a future version of JAVA (some details), but I am not sure if that is what I have in mind here. Four the purpose at hand the environment that is captured by an inner class definition is sufficient.

Why Functional Programming?

Best answer is probably still given here.

More generally speaking, when programming, the best recipe in dealing with complexity is modularization. However that's only half the story; once we have the modules we have to put them together to create a solution that can deal with the complexity of the original problem. Regardless of the simple elegance of the individual parts, it is very likely that the complexity of the full solution will be in the same league as that of the original problem.

So one thing you need in programming is the means to combine the pieces of your solution into a working whole. Functional Programming gives you many of those to begin with and you can create your own by manipulating functions as first class data.

Functions in Java

A function takes some arguments (from its domain) and produces a result (in its range).

Let's call it f, then a somewhat more formal way to say this as follows

f is applied to the arguments (a[1], ... , a[n]) to produce a result r

Let's assume for a minute that we have a Java class named Function with a method to apply the function to an argument, say the integer 1:

	Function f = new Function();
	Object r = f.apply(new Integer(1));
	
Put this code in the main of a test class - surrounded by try { } catch(Exception e) { }, I'm afraid - and it will actually compile when you import the Function class as implemented in de.cm.frw.core.fun.impl The function f as defined above takes one argument (i.e. it is an unary function) and just returns the given argument as its result, so it is an unary identity function. Java being Java, we lost some type information here: f returns the integer 1 as an object. However, somehow Java still knows what it was, 'cause when you compare the result to a fresh integer 1, as in
 
 	r.equals(new Integer(1))
 
the result will be true. Yet, this does not help much, when you want to use r as an integer you have to cast it. This is true for all other types as well.

As a matter of fact f can be applied to any Java class (as long as it is derived from Object), e.g. a string:

 	"Cool".equals(f.apply("Cool"))
 
This last line of code will result in true.

So how do we get f to actually do something? For that you have to overwrite its operate method:

 	f = new Function() {
		public Object operate(Object[] operands)
				throws InvalidArgumentsException {
			return "Super " + ((String) operands[0]);
		}
	}; 
 
Then the following will evaluate to true:

	"Super Cool".equals(f.apply("Cool"))

The implementation of operate above makes some assumptions about the arguments given to f, namely that there is at least one argument and that it is a string. To make these assumptions more explicit it is probably a good idea to make them clear on a separate line:
 
 	f = new Function() {
		public Object operate(Object[] operands)
				throws InvalidArgumentsException {
			String s = (String) operands[0];
			return "Super " + s;
		}
	}; 
 
The implementation of apply will verify that there are at least as many arguments as are required by the function (1 for an unary function). It is also possible to verify the type and other conditions for the arguments by overwriting the method checkArguments:
 
 	f = new Function() {
		public void checkArguments(Collection args)
				throws InvalidArgumentsException {
			Object s = args.iterator().next();
			if(!(s instanceof String))
				throw new InvalidArgumentsException(
					"argument must be a string");
		}

		public Object operate(Object[] operands)
				throws InvalidArgumentsException {
			String s = (String) operands[0];
			return "Super " + s;
		}
		
	};

Functions with more than one Argument

Functions can be defined to require more than one argument. The number of required arguments are given as a parameter for the constructor, e.g. here is a function to add two Numbers:

	Function add = new Function(2) {

		public void checkArguments(Collection args)
				throws InvalidArgumentsException {
			Object a = args.iterator().next();
			Object b = args.iterator().next();
			if(!(a instanceof Number))
				throw new InvalidArgumentsException("first argument must be a Number");
			if(!(b instanceof Number))
				throw new InvalidArgumentsException("second argument must be a Number");
		}

		public Object operate(Object[] operands)
				throws InvalidArgumentsException {
			Number a = (Number) operands[0];
			Number b = (Number) operands[1];
			return new Double(a.doubleValue() + b.doubleValue());
		}
		
	};

To apply this function to two arguments you have to provide the argumens inside a collection:

	Collection args = new LinkedList();
	args.add(new Integer(1));
	args.add(new Integer(1));
	if(((Integer)add.apply(args)).doubleValue() != 2.0)
		fail("Wrong value for add");

To simplify this a little bit the Bag class is provided. It has additional put methods that can be chained as follows:

	if(((Integer)add.apply(new Bag().put(new Integer(1)).put(new Integer(1)))).doubleValue() != 2.0)
		fail("Wrong value for add");

The Advantages of using Functions

Of course we can do all of the above without having explicit functions. Most of the examples are so simple you would not even factor them out into a separate method. Yet, the behavior of the examples may be simple, but by wrapping them in a a function object we turned them into first class data that can be manipulated in all the usual JAVA ways, i.e.:
  1. can be used as a method parameter
  2. can be returned as a method result
  3. can be stored in local variables or class and instance members
  4. can be collected in data structures like arrays and java.util Collections
These features allow to combine the behavior implemented in functions in many ways, that are not available with behavior implemented in class methods. Consider an example for applying behavior to all the members of an array, e.g. iterate over an integer array and create an array containing its members squared. First the conventional solution:

	int[] values = { 1, 2, 3, 4 };
	int[] squares = new int[values.length];
	for(int p = 0; p < values.length; p++) {
		squares[p] = values[p]*values[p];
	}

Following the for-loop squares references an array of the squared members of values. A somewhat nicer approach would be:

static int[] squaredArray(int[] values) {
	int[] result = new int[values.length];
	for(int p = 0; p < values.length; p++) {
		result[p] = values[p]*values[p];
	}
	return result;
}

using this in your application:
	int[] values = { 1, 2, 3, 4 };
	int[] squares = squaredArray(values); // I'd prefer squaredArray({ 1, 2, 3, 4 }); 
but of course in JAVA this requires you to put the static method into some class ...

Now, let's turn this into pure fun. First we need a square function:


	Function square = new Function(1) {
		public void checkArguments(Collection args) 
			throws InvalidArgumentsException {
			Object a = args.iterator().next();
			if(!(a instanceof Number))
				throw new InvalidArgumentsException("argument must be a Number");
		}
		public Object operate(Object[] operands)
			throws InvalidArgumentsException {
			Number a = (Number) operands[0];
			return new Double(a.doubleValue() * a.doubleValue());
		}
		
	};

This we could apply to the members of an array in a loop:

	int[] squares = new int[values.length];
	for(int p = 0; p < values.length; p++) {
		squares[p] = ((Integer) square.apply(new Integer(values[p]))).intValue();
	}

Here is becomes questionable if this can be called pure fun ... what with all the casting and unboxing. The example becomes more enlightening when we factor out the for loop into a static member, but with an additional parameter for the function:
	static int[] mapOverIntArray(int[] values, Function f)
		throws InvalidArgumentsException {
		int[] result = new int[values.length];
		for(int p = 0; p < values.length; p++) {
			result[p] = ((Number) f.apply(new Integer(values[p]))).intValue();
		}
		return result;
	}
The Function parameter f allows us to pass partial behavior into the mapping procedure:
	int[] squares = mapOverIntArray(values, square);
With a new twice Function:
	Function twice = new Function(1) {

		// checkArguments is not required; skipped for brevity here 

		public Object operate(Object[] operands)
			throws InvalidArgumentsException {
			Number a = (Number) operands[0];
			return new Double(a.doubleValue() + a.doubleValue());
		}
		
	};

we can reuse the loop to compute the obvious:

	int[] doubles = mapOverIntArray(values, twice);

We can even do this, creating the Function on the fly:
	int[] doubles = mapOverIntArray(
				values, 
				new Function(1) {
				  public Object operate(Object[] operands)
				  	throws InvalidArgumentsException 
				  {
				    Number a = (Number) operands[0];
				    return new Double(a.doubleValue() 
				    		+ a.doubleValue());
				  }});
To squeeze in a little functional programming terminology here: mapOverIntArray is a higher order function. When we pass in a Function on the fly, this would be called an anonymous function, or a lambda expression without a name. A named lambda expression would be created just the same, but stored in a variable for future reference, as we did with the functions twice and square. The variable becomes the name of the function.

Note: In the last examples we skipped the checkArguments method to make the examples more compact. This is OK for any throw away functions you may write (e.g. anonymous functions). However, if your function is for the keeping, checkArguments is a good place to document any constraints, that may apply to the arguments for the function. Those may be simple type constraints as stated before or even more complicated relationship requirements between individual arguments. Giving a good message when creating the InvalidArgumentException will improve documentation and usability of your function.

So the for loop inside the mapOverIntArray method became so much more versatile. It is now possible to customize its behavior on a per need as we code along.

Of course inside the mapOverIntArray method the function is available under its parameter name f (and even the functions square and twice are renamed for the occasion). However, an anonymous function can be applied directly, as in:

	int squareOf5 = ((Number)(new Function(1) {
		public Object operate(Object[] operands)
				throws InvalidArgumentsException {
			Number a = (Number) operands[0];
			return new Double(a.doubleValue() * a.doubleValue());
		}
	}).apply(new Integer(5))).intValue();

The mapOverIntArray method can be generalized further into a mapping over arrays of Objects, i.e. by giving up some type information for the first parameter. This allows to map all kinds of functions over arrays, provided those arrays contain Objects of suitable type.

	static int[] mapOverArray(Object[] values, Function f)
		throws InvalidArgumentsException {
		int[] result = new int[values.length];
		for(int p = 0; p < values.length; p++) {
			result[p] = ((Number) f.apply(values[p])).intValue();
		}
		return result;
	}
In the last example the function f still is required to produce a number. This restriction is implied by the mapOverArray method. Another restrictions are that it takes an array for its first argument and produces an array as result.

To turn this into a generic tool to map a given function over a collection of arbitrary objects resulting in a new collection of objects, we could make the following changes:

	static Collection map(Collection values, Function f)
		throws InvalidArgumentsException {
		Bag result = new Bag();
		Iterator i = values.iterator();
		while(i.hasNext()) 
			result.put(f.apply(i.next()));
		return result;
	}
So, it's obvious, once you let go of that precious type information, your code turns out so much simpler :)

At first glance the map method seems to require f to be an unary function, however f could require any number of arguments as long as the values collection contains collections of sufficient size as members.

Higher Order Functions

Since functions are first class objects, it is possible to write functions that take functions as arguments and produce a function as a result. For example here is a different solution to the generic function mapping problem:
	static Function map = new Function(1) {

		public Object operate(Object[] operands)
				throws InvalidArgumentsException {
			final Function f = (Function) operands[0];
			return new Function(1) {

				public Object operate(Object[] operands)
						throws InvalidArgumentsException {
					Collection values = (Collection) operands[0];
					Bag result = new Bag();
					Iterator i = values.iterator();
					while(i.hasNext()) 
						result.put(f.apply(i.next()));
					return result;
				}
			};
		}

	};

Here the function map takes a function f to produce a new function that takes a values collection as argument and applies f to its members to assemble the result. Here's how you would use it:
		Function mappedSquare = (Function) map.apply(square);
		Collection values = new Bag().put(new Integer(1)).
				put(new Integer(2)).
				put(new Integer(3)).
				put(new Integer(4));
		Collection squared =  (Collection) mappedSquare.apply(new Bag().put(values));
This is a useful abstraction. We might be able to find more.

Reduce

Suppose you have a function add to add two numbers and you want to use it to compute the sum of all elements in a sequence. Here's one way to do just that:
		Collection values = new Bag().put(new Integer(1)).
				put(new Integer(2)).
				put(new Integer(3)).
				put(new Integer(4));
		int sumOfValues = 0;
		for(Iterator i = values.iterator(); i.hasNext(); )
			sumOfValues = ((Number) add.apply(new Bag().put(new Integer(sumOfValues))
					.put(i.next()))).intValue();
Another way so solve the problem would be to create a new function that computes the sum of the values, using a higher oder function:
		Collection values = new Bag().put(new Integer(1)).
				put(new Integer(2)).
				put(new Integer(3)).
				put(new Integer(4));
		Function sum = (Function) reduce.apply(new Bag().put(add)
				.put(new Integer(0)));
		int sumOfValues = ((Number) sum.apply(values)).intValue(); 
Here the higher order function reduce is responsible for constructing a new function given the function add and an initial value. The the resulting function sum can be used to reduce a sequence of numbers into a single value (the sum).

Here is the definition of the reduce function:


	public static final Function reduce = new Function(2) {

		public Object operate(Object[] operands)
				throws InvalidArgumentsException {
			/// create the list reduction function from the given function and initial value ...
			final Function f = (Function) operands[0];
			final Object init = operands[1];
			Function result = new Function(1) {

				public Object operate(Object[] operands)
						throws InvalidArgumentsException {
					// Recursion is replaced by iteration here ...
					Object result = init;
					Iterator i = ((Iterable) operands[0]).iterator();
					while(i.hasNext()) {
						result = f.apply(new Bag().put(i.next()).put(result));							
					}
					return result;
				}				
			};
			
			return result;
		}
	};

The result of the reduce function is a new function that takes as single argument the collection to be reduced into a single object. This new function uses the given function f (of two arguments) and an initial value.

Compose

One way to combine two functions is to apply one function to the result of another one. In mathematics this is called the composition of the two functions, as in:
compose(f,g)(x1 ... xn) = f(g(x1 ... xn))
This requires f to be a unary function. The resulting function takes as many arguments as g, that is n. A compose function is easily defined:
	public static final Function compose = new Function(2) {
		
		public Object operate(Object[] operands)
				throws InvalidArgumentsException {
			final Function f = (Function) operands[0];
			final Function g = (Function) operands[1];

			return new Function(g.arity()) {   /// composed function takes 
			                                   /// as many arguments as g
	
				public Object operate(Object[] operands)
						throws InvalidArgumentsException {
					Object tmp = g.operate(operands);
					if(tmp instanceof Collection)
						return f.apply((Collection)tmp);
					else
						return f.apply(tmp);
				}
				
			};
		}
Note, how the arity of the resulting function is determined from the arity of g. Note also that the resulting function does not need its own checkArguments function since arguments will be checked first by g, and then by f (indirectly, by checking the result of g).

Bind

One possibility to turn a general function into a more specialized function is to bind one of its arguments to a constant value:
bind(f, i, x)(x1, ..., xn-1) = f(x1, .. xi-1, x, xi, .., xn-1)
For example it is possible to create a decrement function from a function from general subtraction by binding its second value to 1:
decr(7) = bind(subtract, 1, 1)(7) = subtract(7, 1) = 7 - 1 = 6
Here is the same definition in Java code:
	Function decrement = (Function) bind.apply(new Bag().
			put(subtract).          /// the subtraction function
			put(new Integer(1)).    /// the argument position to bind
			put(new Integer(1)));   /// the value to bind it to
	if(((Integer) decrement.apply(new Integer(7))).intValue() != 6)
		fail("Wrong value");
Here is the definition of the bind funciton:
	public static final Function bind= new Function(3) {
	
		public Object operate(Object[] operands)
				throws InvalidArgumentsException {
			final Function f = (Function) operands[0];
			final Integer i = (Integer) operands[1];
			final Object boundArg = operands[2];
			
			return new Function(f.arity() - 1) {
	
				public void checkArguments(Collection args)
						throws InvalidArgumentsException {
					Object[] fArgs = operandsWithBoundArg(args.toArray());
					f.checkArguments(new Bag(fArgs));
				}
	
				public Object operate(Object[] operands)
						throws InvalidArgumentsException {
					Object[] fArgs = operandsWithBoundArg(operands);
					return f.operate(fArgs);
				}
	
				private Object[] operandsWithBoundArg(Object[] operands) {
					Object[] fArgs = new Object[f.arity()];
					for(int p = 0; p < i.intValue(); p++)
						fArgs[p] = operands[p];
					fArgs[i.intValue()] = boundArg;
					for(int p = i.intValue(); p < operands.length; p++)
						fArgs[p+1] = operands[p];
					return fArgs;
				}
			};
		}
		
	};
Note that the arity of the new function is one less than that of the given function f. Checking the arguments as well as computing the result is delegated to f after combining the given arguments with the bound value.

Adapt

Another way to combine two functions is to apply an unary function g to one of the arguments of an n-ary function f:
adapt(f, i, g)(x1, ... , xn) = f(x1, .., g(xi),  .. , xn)
As an example consider a function percent(x, p) that computes a given percentage p of a given value x:
percent(100, 80) = adapt(multiply, 1, divBy100) (100, 80) = multiply(100, divBy100(80)) = multiply(100, 0.8) = 80
The divBy100 function can be created using bind:
divBy100(x) = bind(multiply,1, 0.01)
Substituting this in the definition of percent yields:
percent(100, 80) = adapt(multiply, 1, bind(multiply,1, 0.01)) (100, 80) 
                 = multiply(100, bind(multiply,1, 0.01)(80)) 
                 = multiply(100, multiply(80, 0.01)) 
                 = multiply(100, 0.8) 
                 = 80
Here is the definition of percent with a test in Java:
    Function percent = (Function) adapt.apply(new Bag().
            put(multiply).
            put(new Integer(1)).
            put((Function) bind.apply(new Bag().
                    put(multiply).
                    put(new Integer(1)).
                    put(new Double(0.01)))));

    if(((Number) percent.apply(new Bag().put(new Integer(100)).put(new Integer(80)))).intValue() != 80)
            fail("Wrong value");
The implementation of the higher order function adapt is fairly similar to the function bind:
	public static final Function adapt = new Function(3) {

		public Object operate(Object[] operands)
				throws InvalidArguments {
			final Function f = (Function) operands[0];
			final Integer i = (Integer) operands[1];
			final Function g = (Function) operands[2];
			
			return new Function(f.arity()) {
	
				public void checkArguments(Collection args)
						throws InvalidArguments {
					Object[] fArgs = operandsWithAdaptedArg(
							args.toArray());
					f.checkArguments(new Bag(fArgs));
				}
	
				public Object operate(Object[] operands)
						throws InvalidArguments {
					Object[] fArgs = operandsWithAdaptedArg(operands);
					return f.operate(fArgs);
				}
				
				private Object[] operandsWithAdaptedArg(
						Object[] operands) throws InvalidArguments {
					Object[] fArgs = new Object[f.arity()];
					for(int p = 0; p < i.intValue(); p++)
						fArgs[p] = operands[p];
					fArgs[i.intValue()] = g.apply(operands[i.intValue()]);
					for(int p = i.intValue()+1; p < operands.length; p++)
						fArgs[p] = operands[p];
					return fArgs;
				}
			};
		}		

	};

Unary

On way to specialize a given n-ary function f is to turn it into a unary function such that the single argument is used in all parameter positions of the original function f:
unary(f)(x) = f(x, x, ... , x) 
For example, it is possible to define the function square as the unary of multiply:
square(5) = unary(multiply)(5) = multiply(5, 5) = 25
Here's square in JAVA:
    Function square = (Function) unary.apply(multiply);
  
    if(((Number) square.apply(new Integer(5))).intValue() != 25)
            fail("Wrong value");

The definition for unary employs the techniques seen before with bind and adapt:
	public static final Function unary = new Function(1) {

		public Object operate(Object[] operands)
				throws InvalidArguments {
			final Function f = (Function) operands[0];
			return new Function(1) {

				public void checkArguments(Collection args)
						throws InvalidArguments {
					Object arg = args.iterator().next();
					Object[] newArgs = operandsFromSingleArg(arg);
					f.checkArguments(new Bag(newArgs));
				}

				private Object[] operandsFromSingleArg(Object arg) {
					Object[] result = new Object[f.arity()];
					for(int i = 0; i < f.arity(); i++)
						result[i] = arg;
					return result;
				}

				public Object operate(Object[] operands)
						throws InvalidArguments {
					Object arg = operands[0];
					Object[] newArgs = operandsFromSingleArg(arg);
					return f.operate(newArgs);
				}
				
			};
		}
		
	};

Functional Programming Examples

In this section some examples are given to show the functional programming tools introduced so far in action. These examples are mostly quoted from online resources on functional programming and LISP.

The examples will focus on how to solve a given problem using the functional programming tools, but will also provide tips for using the pure.fun library in a way to simplify rather than obfuscate the code.

The main contribution of the pure.fun library is the class Function itself. It allows to define functions and apply them consistently. In addition it provides tools for boxing and unboxing primitive JAVA types. These tools are public static members, hence accessible to any code with a Function prefix (API ref for the boxing tools). A first tip to simplify the code is to actually use these tools. A second tip would be write your blocks of functional code inside the operate method of an anonymous function of zero arguments and call apply on it. This makes the static tools available to your code without the Function prefix. However these tools are also available with the PF prefix (since the class PF extends Function). Alternatively the can be made available by renaming the Function class through empty extension, e.g:

    class F extends Function { } /// short form to make boxing tools available outside functions

In the library the higher oder functions from the previous section are provided as static members of the PF (pure fun) class which serves as a name space for these tools. It also provides some syntactic sugar in the form of static methods that simplify the use of the higher order functions, e.g. instead of

    Function decrement = (Function) PF.bind.apply(new Bag().
	   		put(subtract).
			put(new Integer(1)).
			put(new Integer(1)));  
it is possible to write
Function decrement = PF.bind(subtract, 1, new Integer(1));
with the same result. An even more convincing example would be the definition of the function percent seen earlier, where the PF utilities can be used as follows:
    Function percent = PF.adapt(multiply, 1, PF.bind(multiply,1,new Double(0.01)));

Mathematics

Square Roots by Newtons Method

This example is adapted from Scala By Example Section 4.4 (you will find the original example in Scheme notation here).

The example shows how to use plain methods to add internal definitions to a Function to structure the code in a readable fashion closely following the mathematical definition. It also illustrates how to use the tools for boxing and unboxing of primitive types.

    try {
        final Function square = PF.unary(multiply);        /// (1)

        Function sqrtIter = new Function(2) {              /// (2)

            public Object operate(Object[] operands)
                    throws InvalidArguments {
                double guess = val(operands[0]);           /// (3)
                double x = val(operands[1]);               /// (4)
                if(isGoodEnough(guess, x)) 
                    return box(guess);
                else 
                    return this.apply(new Bag().put(improve(guess, x)).put(box(x))); /// (7)
            }

            private Object improve(double guess, double x) {
                return new Double((guess +(x/guess))/2);
            }

            private boolean isGoodEnough(double guess, double x) throws InvalidArguments {
                return abs(val(square.apply(box(guess))) - x) < 0.001;
            }

            private double abs(double d) {
                return d<0?-1*d:d;
            }

        };

        Function sqrt = PF.bind(sqrtIter, 0, PF.box(1.0)); /// (5)
        System.out.println(sqrt.apply(new Float(2)));      /// (6)
    } catch (InvalidArguments e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
First the square function is defined as the unary of the function for multiplication (1). The iterative Newton method is implemented as a function of two arguments (2), where the arguments are:
  1. guess : the current best guess (3)
  2. x : the value for which the square root is to be computed (4)
The arguments are unboxed as early as possible (using Function's static val member) to allow for implementing the internal definitions in terms of the primitive type, which makes the code more readable and shorter.

The actual sqrt function is created by binding the first parameter of sqrtIter to 1.0 as a commonly used initial guess (5).

Finally the sqrt function is used compute the square root of 2.0 (6), which is given here as a Float instance to illustrate the fact that Function.val is implemented in terms of the type Number.

An obvious improvement would be to parameterize the sqrtIter function for the required accuracy, which is easily achieved by adding a third parameter, that would be bound to the desired accuracy in the definition of sqrt.

And, yes, another improvement (in performance) would be to replace the tail recursive call at (7) with a while loop ...

Finding Fixed Points of Functions

This example is adapted from here and is also covered in section 5.3 of the Scala Book mentioned above .

For a fixed point x for a given function f, the condition f(x) = x holds. If for an initial guess x1 the series x1, f(x1), f(f(x1)), ... converges to a fixed point of f, the following function can be used:

     final Function fixedPoint = new Function(2) {
        final double tolerance = 0.00001;
        private boolean closeEnough(double a, double b) {
            double diff = Math.abs(a - b);
            return diff < tolerance;
        }
        public Object operate(Object[] operands)
                throws InvalidArguments {
            Function f = (Function) operands[0];
            double thisGuess = val(operands[1]);
            double nextGuess = val(f.apply(box(thisGuess)));
            while(!closeEnough(thisGuess, nextGuess)) {
                thisGuess = nextGuess;
                nextGuess = val(f.apply(box(thisGuess)));;
            }
            return box(nextGuess);
        }
    }; 
For example, we can use this method to approximate the fixed point of the cosine function, starting with 1 as an initial approximation:
try {
    Function cosine = new Function(1) {
        public Object operate(Object[] operands) throws InvalidArguments {
            double x = val(operands[0]);
            return box(Math.cos(x));
        }
    };
    Collection args = new Bag().put(cosine).put(PF.box(1.0));
    double fp = PF.val(fixedPoint.apply(args));
    System.out.println("(fixed-point cos 1.0) = "+fp);
} catch (InvalidArguments e) {
    fail(e.getMessage());
}
Similarly, we can find a solution to the equation y = sin y + cos y. Wrapping static methods from the Math class into a F is a very common task, so there is an abstract inner class provided in the NUM class to help with it. Here is how to use it:
    Function sinePlusCosine = new NUM.Unary() {
        protected double calc(double x) {
            return Math.sin(x) + Math.cos(x);
        }
    };
    Collection args = new Bag().put(sinePlusCosine).put(1.0);
    try {
        double fp = PF.val(NUM.fixedPoint.apply(args));
        System.out.println("(fixed-point (lambda (y) (+ (sin y) (cos y))) 1.0) = "+fp);
    } catch (InvalidArguments e) {
        fail(e.getMessage());
    }
Note: There is also a NUM.Binary class for numerical functions of two arguments

The function for finding fixed points can also be used to approximate the square root of 2. For this we have to state the problem of finding x, with x*x = 2 as a fixed point problem:

x*x = 2  <=> x = 2/x  <=> x = f(x), with f(x) = 2/x
However, applying fixedPoint to this f(x) will not converge, as the successive f(x) values will oscillate between 1.0 and 2.0. This issue can be resolved by average damping, in which successive values of f(x) are averaged. This can be implemented as a higher oder function that takes a function f as argument and returns a new Function with average damping applied:
    static final Function avgDamp = new Function(1) {
        double average(double a, double b) {
            return (a + b) / 2.0;
        }

        public Object operate(Object[] operands)
                throws InvalidArguments {
            final Function f = (Function) operands[0];
            return new Function(1) {

                public Object operate(Object[] operands)
                        throws InvalidArguments {
                    double x = val(operands[0]);
                    double f_x = val(f.apply(x));
                    return box(average(x, f_x));
                }
                
            };
        }
        
    };
fixedPoint and avgDamp along with static member methods to simplify their use are part of the NUM class. With the avgDamp function the sqrt function can be formulated in terms fixed point finding:
       Function sqrt = new Function(1) {

           public Object operate(Object[] operands)
                   throws InvalidArguments {
               final double x = val(operands[0]);
               Function sqrtFP = new NUM.Unary() {
                   protected double calc(double y) {
                       return x/y;
                   }
               };
               return NUM.fixedPoint.apply(new Bag().put(NUM.avgDamp.apply(sqrtFP)).put(1.0)); 
           }
           
       };
   
   try {
       double fp = PF.val(sqrt.apply(2.0));
       System.out.println("sqrt(2.0) = "+fp);
   } catch (InvalidArguments e) {
       e.printStackTrace();
       fail(e.getMessage());
   }

Arguing along the same lines we can define a function to compute the cube root, realizing that:
x^3 = y  <=> x = y/(x*x)  <=> x = f(x), with f(x) = y/(x*x)
So using the static member methods of NUM to simplify the code even more, we get:
       Function cbrt = new Function(1) {

           public Object operate(Object[] operands)
                   throws InvalidArguments {
               final double x = val(operands[0]);
               Function cbrtFP = new NUM.Unary() {
                   protected double calc(double y) {
                       return x/(y*y);
                   }
               };
               return NUM.fixedPoint(NUM.avgDamp(cbrtFP), 1.0); 
           }
           
       };
       
       try {
           double fp = PF.val(cbrt.apply(27.0));
           System.out.println("cbrt(27.0) = "+fp);
       } catch (InvalidArguments e) {
           e.printStackTrace();
           fail(e.getMessage());
       }

Computing the Distance between Points

In this section we are going to develop a function that takes two points in the plane and computes the distance between them. We the use this function to construct a new function that can be applied to a list of points to compute the circumference of a corresponding two dimensional shape.

The two points are given as a pair of numbers (x, y) representing their carthesian coordinates. Their distance is then the square root of the squared differences of their x and y components, more formally:

   d = sqrt((x2-x1)^2 + (y2-y1)^2)
Pairs are represented as a cons cell, which are provided in the LP (list processing) class through the static member functions cons, car and cdr.
   car(cons(a,b)) = a
   cdr(cons(a,b)) = b
Note: The cons cells together with their defining functions are (of course) inspired by the corresponding LISP constructs.

So, the two points p1 and p2 are constructed as follows:

   p1 = cons(x1, y1)
   p2 = cons(x2, y2)
and the formula for the distance can be given as:
   d = sqrt(add(square(subtract(car(p2), car(p1))), 
                square(subtract(cdr(p2), cdr(p1)))))
Let's tackle this inside out, starting with:
   subtract(car(p2), car(p1))
This is a function of two arguments, p1 and p2, that first applies LP.car to each argument and then computes the difference:
   Function distx = PF.adapt(PF.adapt(NUM.subtract, 0, LP.car), 1, LP,car);
Similar for disty:
   Function disty = PF.adapt(PF.adapt(NUM.subtract, 0, LP.cdr), 1, LP,cdr);
These functions can be easily combined with NUM.square trough composition, i.e. PF.compose:
   Function squareDistx = PF.compose(NUM.square, distx);
   Function squareDisty = PF.compose(NUM.square, disty);

However, using these results to provide the arguments for NUM.add poses somewhat of a challenge, since none of the functional programming tools defined in PF, e.g. PF.adapt, is directly applicable.

Roughly speaking we want to combine squareDistx and squareDisty with add and what comes to mind first is to use adapt, somewhat like this:

   tmp = adapt(adapt(add, 0, squareDistx), 1, squareDisty)
However, each of the adapter functions acutally needs both arguments (i.e both points), so the two points need to be combined into a single argument. Why not use cons to create a pair? The single argument then needs to be passed into both parameter positions. This is exactly what unary does. So:
   tmp = compose(unary(adapt(adapt(add, 0, squareDistx), 1, squareDisty)), cons)
For this to actually work, distx and disty need to be tweaked a little bit more to take the pair apart:
   distx = adapt(adapt(distx, 0, car), 1 cdr)
   disty = adapt(adapt(disty, 0, car), 1 cdr)
To complete the computation of the distance the tmp function from above needs to be combined withsqrt.
   distance = compose(sqrt, tmp)
Here is the complete definition of the distance function (in the correct order) with an application example in JAVA:
   Function distx = PF.adapt(PF.adapt(NUM.subtract, 0, LP.car), 1, LP.car);
   Function disty = PF.adapt(PF.adapt(NUM.subtract, 0, LP.cdr), 1, LP.cdr);
   distx = PF.unary(PF.adapt(PF.adapt(distx, 0, LP.car), 1, LP.cdr));
   disty = PF.unary(PF.adapt(PF.adapt(disty, 0, LP.car), 1, LP.cdr));
   Function squareDistx = PF.compose(NUM.square, distx);
   Function squareDisty = PF.compose(NUM.square, disty);
   Function tmp = PF.compose(PF.unary(PF.adapt(PF.adapt(NUM.add, 0, squareDistx), 1, squareDisty)), LP.cons);
   Function distance = PF.compose(NUM.sqrt, tmp);

   // the two points in an argument array
   final Object[] args = { LP.cons(PF.box(1), PF.box(2)), LP.cons(PF.box(9), PF.box(6)) };            
   Number dst = (Number) distance.apply(args);
   System.out.println(dst.toString());
The task computing the circumference of a shape, given the vertex points of its border can be split into two tasks: First