Excuse me sir, there is no curry in my Java

A while ago, I was given the following assignment for a computer vision class:

• Track the angle of a green square held by a person in front of a camera
• Use Processing and Java
• Use the algorithms taught in class (edge detection, pixel intensity clamping, hough, quad detection) and implement them yourself
• Follow the procedure given in the assignments

As for any assignment, you have to beware of the procedure given. Indeed, most assignments are optimised for how long it takes to design rather than how easy it is to learn from them. This is specially true for new courses that haven’t gone though many years of iteration, which was the case for this class.

Hence, after looking at the procedure I decided to ignore it and build my own architecture in order to solve the task at hand. This allowed me to discover very neat properties which helped me find this elegant solution.

Abstracting away operations

The task was to split into three different phases in the processing of a single frame:

• Filter pixels according to color, brightness, etc. and detect edges using convolutions and Sobel algorithm
• Detect lines and filter them using the Hough algorithm
• Detect the largest 4 sided shape and approximate its angle in 3D space using linear algebra and heuristics

Intuitively I thought of those operations as pure functions that take an image and either transform the image or extract a property of that image (lines, intersections, quads). Something along the lines of Operation :: img -> img or Operation :: img -> (img, data).

Moreover, the assignment asked to display on screen the result of some of those operations, intuitively those are functions that take the output of a previous image operation and perform a side effect (displaying). Because we want those functions to compose nicely with each other, drawing functions need to be an identity function with a side effect, something along the lines of Effect :: a -> IO a.

With those two primitive I can start implementing the task as a single sequence of discrete steps (represented by functions) interleaved with side effects in order to display intermediate results. Something like drawLines • hough • drawSobel • sobel • filter • drawImage. That way, the whole pipeline should be easy to debug, develop and understand.

Now things get hairy. Indeed, java has limited support for functions, but you can get by using java 8’s fancy new features. Here is how a function on an image is represented:

class ImageTransformation<Pixel, Transformed> implements Function<List<Pixel>, List<Transformed>>

Wow what’s all that stuff about? That looks super complex and all. But in reallity it is as simple asImageTransformation :: [Pixel] -> [Pixel] .

As for effects they are modeled as

public class EffectFunction<A> implements Function<A, A> {
    private final Consumer<A> effect;
    public A apply(A a) { effect.accept(a);return a; }
}

With the hope that the side effect isn’t too wild and just displays on screen instead of updating global mutable variables.

After declaring all that we can finally implement our first algorithm.

Example: Sobel

Disclaimer: If you’re not interested in boring implementation details skip this section.

Sobel’s algorithm uses matrix convolutions (also called kernels) to detect edges in an array of values (https://en.wikipedia.org/wiki/Sobel_operator)

In a typical functional language you would write something like this:

sobel :: [pixel] -> [pixel]
sobel image :: map distance $ zip (map horizontalConvolution image) (map verticalConvolution image)

Where vertical and horizontal convolutions are (curried) functions with type convolution :: Matrix -> [Pixel] -> [Pixel] with a matrix already provided.

Sobel is built as a function from List<Float> to List<Float> using two convolutions (It’s not an ImageTransformation and I don’t know why, maybe an historical oversight). Floats encode a pixel brightness value.

Convolutions are implemented as an ImageTransformation (that’s our function from List<P> to List<P>)

ImageTransformation<Float, Float> convolutionTransformation(int[][] matrix, int size, int w, int h) {
    return new ImageTransformation<>(new Convolution(matrix, size, 1).toGeneric(w, h));
}

Shat’s all that noise about?

Here is what’s happening: Image transformations has a constructor that takes a GenericTransformation which is a function of the type Integer -> Pixel -> [Pixel] -> Output . It is implemented like so:

@FunctionalInterface
public interface GenericTransformation<T, S> {
    S apply(int index, T pixel, List<T> image);
}

This allows us to define an image transformation pixel by pixel while keeping track of the whole image in it’s original state. This is extremely useful for convolution since, to compute any given pixel, the matrix of convolution needs to access the surrounding pixels.

For example, in order to compute the pixel at position (10,20) using a 3x3 matix, the algorithm needs to get the pixels coordinates (9,19), (9, 20), (9, 21), (10, 19), (10, 21), (11, 19), (11, 20), (11, 21) none which can be accessed using a naive map function.

Which brings us to the Convolution object. It takes a square matrix and the size of its border and has (basically) one method: toGeneric . It returns a function of the type GenericTransformation(In retrospect this method could have been avoided by having the class be a functional interface and putting the content of the toGeneric method in the apply method).

The returnedGenericTransformation does what you’d expect, that is

• For each pixel takes the convolution of the surrounding pixels using the matrix supplied as argument.
• Applies the weight computed to the resulting pixel (in order to stay within sane pixel brightness values)
• Returns the computed pixel.

The ImageTransformation function will take this pixel transformation and use it to compute every pixel in the image passed as argument.

Finally, we can implement Sobel as two convolutions of each pixel of the image and return for each pixel the distance between the two resulting convolutions.

mergeWith is a custom method on functions with this signature: [a] -> (a -> b) -> (a -> c) -> ((b, c) ->d) -> d

This code looks a bit arcane but it does the same thing as the first code snippet of this section.

How to compose our functions in a sensible way

Now that we have our functions, we would really like to do something like:

void computeImage(image) {
    (filter              // pure 
    .andThen(sobel)      // pure
    .andThen(drawSolbel) // effect
    .andThen(drawImage)  // effect
    .andThen(hough)      //pure
    .andThen(drawHough))(image) //effect
}

The catch preventing us from doing so is that functions like sobel or hough need more arguments to do their work. Indeed, we need to pass in things like the size of the image or, for hough, the number of iterations of the algorithm. Ideally we would like to partially apply those functions and return a curried function that expects the missing arguments.

Something like .andThen(hough(0.05f, 2.5f))

Currying attempt 1: Create functions from objects

My first attempt at making partially applied functions involved creating an object that extends function, give it immutable private parmeters through the constructor and implement the apply method.

The implementation of the Hough transformation uses this architecture which can be outlined as so:

public class PartiallyApplied extends Function<D, E> {
    private final A a;
    private final B b;
    private final C c;
public PartiallyApplied(A a, B b, C c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
public E apply(D d) {
        //make use of a, b , c return e
    }
}

But if you look at the actual implementation you will see much much more stuff that surrounds this class. And that’s because the whole idea is bad:

• It encourages mutable state. Indeed, parameters are mutable by default, forgetting to set them as final easily leads to mutable state.
• It encourages more co-effects. Since a, b and c are visible from all other methods in the class it is very easy to abuse this power and end up with an object that has many methods and does much more than what was intended.
• We can’t even use the lambda syntax or method references, you have to use new MyCurriedFunction(parameters) so what’s the point?

But it’s not all bad, in particular we found a very nice property of objects:

Objects are just partially applied functions

Well not really, but here is the trick: think of objects as a record of both values and functions.

data MyObject :: { value1 :: A
                 , value2 :: B
                 , f :: C -> D
                 , g :: H -> IO () }

Now assume that functions are already implemented and you only need to plug-in values. So that the type constructor would look like this:

myObject :: A -> B -> MyObject

Another assumption: those functions are implicitly co-effectful that is, they will make use of state outside of their scope, in this case value1 and value2. A property of co-effectful functions is that a co-effectful function f :: A -> Bcan be expressed as a pure function f’ :: E -> A -> B with E being the state needed to run the function. We conclude that every object can be defined like this:

data MyActualObject :: { f :: (A, B) -> C -> D
                       , g :: (A, B) -> H -> IO () }

Therefore, our original myObject is the same as MyActualObject except the functions f and g are partially applied.

This partial application property extends way beyond our simple currying use case and can help us understand everyday OOP code in a very useful way. Nowadays, more and more codebase rely objects using lots of immutable properties, making them akin to a bag of partially applied functions. Sometimes this representation is very useful to better unerstand the architecture of a project.

Currying attempt 2: Use static methods to return functions

Instanciating objects as functions wasn’t the most practical but there is another mechanism we haven’t yet abused. Static methods are basically free functions under a namespace. So can’t we create an empty object with a dead constructor and filled with static methods? That would solve our co-effect problem and our syntax issues.

Here is what I tried:

public class Namespace {
    public static Function<D, E>curriedFunction(A a, B b, C c) {
        return d -> {
            //use a b c and d to produce e
}}}

And that works great:

• No more bloated objects, just simple static functions with limited scope and effects.
• No more new keyword.
• You are not allowed to implement weird interfaces and methods in your function object.

Unfortunately the method reference syntax cannot be used because our methods take arguments (we can’t do Namespace::curried(a,b,c)).

Currying attempt 3: Actual currying

I haven’t done anything like that during this project but know that it is possible to have “actual for realz not a joke” currying with java. Look at this:

Function<B, Function<C, Function<D, E>>> curried(A a) {
    return b -> {
        return c -> {
            return d -> {
                return //use a, b, c and d
}}}}

It works exactly as real currying would! And that is fantastic. I do think this solution is mostly impractical for the purpose of my project because the pipeline I needed was purely linear and consumed a single argument.

Moreoever the implementation can be hard to parse visually and it may be inconvenient to code with many levels of indentation without even introducing any control statements (but again, Java makes you start with at least two levels by default so you might be used to it by now).

Which finally brings us to the answer the title never asked:

How to curry functions in Java

Either:

• You don’t (and end up with spaghetti code or a different language).
• You end up in function signature hell (Function<A, Function<B, Function<C, …>>> ) and your coworkers will hate you.
• Your use case is simple enough that you can just pipe through a single argument and make static methods that return function<A,B>.

Conclusion

In the end, the API of the architecture looked nice and was very practical, easy to debug and easy to tweak. The algorithms used rely heavily on user-defined parameters and heuristics making the development cycle extremly dependent on feedback. Run code, move a couple of sliders and manually test the visual output, update the code accordingly, rince and repeat. And for that purpose, the function composition approach was a great success. If a single step of the pipeline needed investigation, it was very easy to introduce a drawEffect function in between two phases and visualize what the algorithm is doing.

On the other hand…

The incredibely convoluted machinery to get there isn’t something I recommend you do.

Take this examp- literal horror:

As mentionned in the top comment, the type signature isn’t that complex but the syntax of the language paired with the lack of type inference makes this whole code snippet unreadable at best. And that is why and architecture based on function composition isn’t something I recommend doing at least not in java and not in production. The benefits are limited and the tradeoffs risky. If that’s something you want (or need) to do, pick a language that makes it simple and easy for you like Haskell, or Scala if you’re on the JVM.

All the code can be found here https://github.com/zhaar/visual-comp .