In Relation To

Back to home

Introduction to Ceylon Part 8

Posted by    |      

This is the eighth installment in a series of articles introducing the Ceylon language. Note that some features of the language may change before the final release.

This article was updated on 31/5/2011 to add information about partial application of methods.

First class and higher order functions

Ceylon isn't a functional language: it has variable attributes and so methods can have side effects. But Ceylon does let you use functions as values, which in some people's eyes makes the language a kind of hybrid. I'm not so sure about that. There's actually nothing at all new about having functions-as-values in an object oriented language — for example, Smalltalk, one of the first and still one of the cleanest object oriented languages, was built around this idea. (To my eyes, true functional programming is more about what you can't do — mutate values — than what you can do.) Anyway, Ceylon, like Smalltalk and a number of other object oriented languages, lets you treat a function as an object and pass it around the system.

In this installment, we're going to discuss Ceylon's support for first class and higher order functions. First class function support means the ability to treat a function as a value. A higher order function is a function that accepts other functions as arguments, or returns another function. It's clear that these two ideas go hand-in-hand, so I'll just talk about higher order function support from now on.

A quick disclaimer: none of the things in this installment have actually been implemented in the compiler yet.

Representing the type of a function

Ceylon is a (very) statically typed language. So if we're going to treat a function as a value, the very first question that arises is: what is the type of the function? We need a way to encode the return type and parameter types of a function into the type system. Remember that Ceylon doesn't have primitive types. A strong design principle is that every type should be representable within the type system as a class or interface declaration.

I suppose Ceylon could have gone down the road of some functional languages, and represented all functions with multiple parameters in curried form. So 

Natural sum(Natural x, Natural y) { ... }

would just be an abbreviation of 

Natural sum(Natural x)(Natural y) { ... }

i.e. a function with one parameter that returns another function with one parameter. Then we could have represented the type of the function like this: 

Function<Natural,Function<Natural,Natural>>

But we've decided not to go down this path.

Some other languages have chosen to have a separate type for each function arity. So there's F0<R>, F1<R,P1>, F2<R,P1,P2>, F3<R,P1,P2,P3>, etc. But this solution feels kinda .... lame. Worse, it doesn't allow us to abstract over all function types, building up abstractions like Method and Class, etc. We're going to need to be able to do that kind of thing when we get to discussing the typesafe metamodel.

In Ceylon, a single type Callable abstracts all functions. It's declaration is the following: 

shared interface Callable<out Result, Argument...> {}

The syntax P... is called a sequenced type parameter. By analogy with a sequenced parameter, which accepts zero or more values as arguments, a sequenced type parameter accepts zero or more types as arguments. The type parameter Result represents the return type of the function. The sequenced type parameter Argument... represents the parameter types of the function.

So the type of sum in Ceylon is: 

Callable<Natural, Natural, Natural>

What about void functions? Well, remember that way back in Part 1 we said that the return type of a void function is Void. So the type of a function like print() is: 

Callable<Void,String>

Representing the type of a method

Here we've been discussing first class functions. But in Ceylon all named declarations are first class. That is to say, they all have a reified metamodel representable within the type system. For example, we could represent the type of a method like this: 

shared interface Method<out Result, in Instance, Argument...>
    satisfies Callable<Callable<Result,Argument...>, Instance> {}

Where Instance is the type that declares the method. So the type of the method iterator() of Iterable<String> would be: 

Method<Iterator<String>, Iterable<String>>

And the type of the method compare() of Comparable<Natural> would be: 

Method<Comparison,Comparable<Natural>,Natural>

Notice that we've declared a method to be a function that accepts a receiver object and returns a function. As a consequence of this, an alternative method invocation protocol is the following: 

Iterable<String>.iterator(strings)();
Comparable<Natural>.compare(0)(num);

Don't worry if you can't make sense of that right now. And actually I'm skipping over some details here, that's not quite exactly how Method is defined. But we'll come back to this in a future installment. Let's get back to today's topic.

Defining higher order functions

We now have enough machinery to be able to write higher order functions. For example, we could create a repeat() function that repeatedly executes a function. 

void repeat(Natural times, Callable<Void,Natural> perform) {
    for (Natural i in 1..times) {
        perform(i);
    }
}

And call it like this: 

void print(Natural n) { writeLine(n); }
repeat(10, print);

Which would print the numbers 1 to 10 to the console.

There's one problem with this. In Ceylon, as we'll see later, we often call functions using named arguments, but the Callable type does not encode the names of the function parameters. So Ceylon has an alternative, more elegant, syntax for declaring a parameter of type Callable: 

void repeat(Natural times, void perform(Natural n)) {
    for (Natural i in 1..times) {
        perform(i);
    }
}

I find this version also slightly more readable and more regular. This is the preferred syntax for defining higher-order functions.

Function references

When a name of a function appears without any arguments, like print does above, it's called a function reference. A function reference is the thing that really has the type Callable. In this case, print has the type Callable<Void,Natural>.

Now, remember how we said that Void is both the return type of a void method, and also the logical root of the type hierarchy? Well that's useful here, since it means that we can assign a function with a non-Void return type to any parameter which expects a void method: 

Boolean attemptPrint(Natural n) { 
    try {
        writeLine(n);
        return true;
    }
    catch (Exception e) {
        return false;
    }
}
repeat(10, attemptPrint);

Another way we can produce a function reference is by partially applying a method to a receiver expression. For example, we could write the following: 

class Hello(String name) {
    shared void say(Natural n) {
        writeLine("Hello, " name ", for the " n "th time!");
    }
}

repeat(10, Hello("Gavin").say);

Here the expression Hello("Gavin").say has the same type as print above. It is a Callable<Void,Natural>.

More about higher-order functions

Let's see a more practical example, which mixes both ways of representing a function type. Suppose we have some kind of user interface component which can be observed by other objects in the system. We could use something like Java's Observer/Observable pattern: 

shared interface Observer { 
    shared formal void observe(Event event);
}
shared abstract class Component() {
    
    OpenList<Observer> observers = OpenList<Observer>();
    
    shared void addObserver(Observer o) { 
        observers.append(o); 
    }
    
    shared void fire(Event event) { 
        for (Observer o in observers) { 
            o.observe(event);
        } 
    }

}

But now all event observers have to implement the interface Observer, which has just one method. Why don't we cut out the interface, and let event observers just register a function object as their event listener? In the following code, we define the addObserver() method to accept a function as a parameter. 

shared abstract class Component() {
    
    OpenList<Callable<Void,Event>> observers = OpenList<Callable<Void,Event>>();
    
    shared void addObserver(void observe(Event event)) { 
        observers.append(observe); 
    }
    
    shared void fire(Event event) { 
        for (void observe(Event event) in observers) { 
            observe(event);
        } 
    }

}

Here we see the difference between the two ways of specifying a function type:

  • void observe(Event event) is more readable in parameter lists, where observe is the name of the parameter, but
  • Callable<Void,Event> is useful as a generic type argument.

Now, any event observer can just pass a reference to one of its own methods to addObserver(): 

shared class Listener(Component component) {

    void onEvent(Event e) { 
        //respond to the event 
        ...
    } 
    
    component.addObserver(onEvent); 
    
    ...

}

When the name of a method appears in an expression without a list of arguments after it, it is a reference to the method, not an invocation of the method. Here, the expression onEvent is an expression of type Callable<Void,Event> that refers to the method onEvent().

If onEvent() were shared, we could even wire together the Component and Listener from some other code, to eliminate the dependency of Listener on Component: 

shared class Listener() {

    shared void onEvent(Event e) { 
        //respond to the event 
        ...
    } 
    
    ...

}
void listen(Component component, Listener listener) {
    component.addObserver(listener.onEvent);
}

Here, the syntax listener.onEvent is a kind of partial application of the method onEvent(). It doesn't cause the onEvent() method to be executed (because we haven't supplied all the parameters yet). Rather, it results in a function that packages together the method reference onEvent and the method receiver listener.

It's also possible to declare a method that returns a function. A method that returns a function has multiple parameter lists. Let's consider adding the ability to remove observers from a Component. We could use a Subscription interface: 

shared interface Subscription {
    shared void cancel();
}
shared abstract class Component() {
    
    ...
    
    shared Subscription addObserver(void observe(Event event)) { 
        observers.append(observe); 
        object subscription satisfies Subscription {
            shared actual void cancel() {
                observers.remove(observe);
            }
        }
        return subscription;
    }
    
    ...

}

But a simpler solution might be to just eliminate the interface and return the cancel() method directly: 

shared abstract class Component() {
    
    ...
    
    shared void addObserver(void observe(Event event))() { 
        observers.append(observe); 
        void cancel() {
            observers.remove(observe);
        }
        return cancel;
    }
    
    ...

}

Note the second parameter list of addObserver().

Here, we define a method cancel() inside the body of the addObserver() method, and return a reference to the inner method from the outer method. The inner method cancel() can't be called directly from outside the body of the addObserver() method, since it is a block local declaration. But the reference to cancel() returned by addObserver() can be called by any code that obtains the reference.

Oh, in case you're wondering, the type of the method addObserver() is Callable<Callable<Void>,Component,Callable<Void,Event>>.

Notice that cancel() is able to use the parameter observe of addObserver(). We say that the inner method receives a closure of the non-variable locals and parameters of the outer method — just like a method of a class receives a closure of the class initialization parameters and locals of the class initializer. In general, any inner class, method, or attribute declaration always receives the closure of the members of the class, method, or attribute declaration in which it is enclosed. This is an example of how regular the language is.

We could invoke our method like this: 

addObserver(onEvent)();

But if we were planning to use the method in this way, there would be no good reason for giving it two parameter lists. It's much more likely that we're planning to store or pass the reference to the inner method somewhere before invoking it. 

void cancel() = addObserver(onEvent);
...
cancel();

The first line demonstrates how a method can be defined using a = specification statement, just like a simple attribute definition. The second line of code simply invokes the returned reference to cancel().

We've already seen how an attribute can be defined using a block of code. Now we see that a method can be defined using a specifier. So, if you like, you can start thinking of a method as an attribute of type Callable — an attribute with parameters. Or if you prefer, you can think of an attribute as member with zero parameter lists, and of a method as a member with one or more parameter lists. Either kind of member can be defined by reference, using =, or directly, by specifying a block of code to be executed.

Cool, huh? That's more regularity.

There's more...

As you've probably noticed, all the functions we've defined so far have been declared with a name, using a traditional C-like syntax. We still need to see what Ceylon has instead of anonymous functions (sometimes called lambda expressions) for making it easy to take advantage of functions like repeat() which define specialized control structures. But I've hit my word limit already. Instead, you can find a discussion here.

If you're interested to know more about programming with higher-order functions, you can read more about currying, uncurrying, and function composition.

In Part 9, we're finally going to talk about Ceylon's syntax for named argument lists and for defining user interfaces and structured data.

Back to top