Functions

This is the eleventh part of the Tour of Ceylon. In the previous leg we looked at packages and modules. This leg covers first class and higher-order functions.

First class and higher order functions

Ceylon isn't a functional language: it has variable attributes and so methods can have side effects. But one thing Ceylon has in common with functional programming languages is that it lets you treat functions as values, which in some people's eyes makes the language a kind of hybrid. In truth, there's nothing remotely 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. 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. A little bit of PL jargon:

  • First class function support means the ability to treat a function as a value, assigning it to variables, and passing it as an argument.
  • 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 we'll just use the term "higher order functions" from now on.

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.

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

shared interface Callable<out Return, in Arguments> 
        given Arguments satisfies Anything[] {}

The type parameter Return represents the return type of the function. The sequenced type parameter Arguments, which must be a sequence type, represents the parameter types of the function. We can encode any parameter list as a tuple type. For example, the parameter list (String s, Float x) is encoded as the tuple type [String,Float].

So, take the following function:

function sum(Integer x, Integer y) => x+y;

The type of sum() is:

Callable<Integer,[Integer,Integer]>

What about void functions? Well, the return type of a void function is considered to be Anything. So the type of a function like print() is:

Callable<Anything,[Anything]>

Folks who have a background in languages like ML might have expected that void would be identified with some "unit" type, for example, Null, or perhaps []. But this approach would mean that a non-void method would not be able to refine a void method, and that a non-void function would not be able to be assigned to a void functional parameter. Therefore, perfectly reasonable code would be rejected by the compiler.

Note that a void function with a concrete implementation implicitly returns the value null. This is different to a function declared to return the type Anything, which may return any value at all, but must do it explicitly, via a return statement. The following functions have the same type, Anything(), but don't do exactly the same thing:

Anything hello() { 
    print("hello");
    return "hello";
}

void hello() { 
    print("hello");
    //implicitly returns null
}

You shouldn't rely upon a function that is declared void returning null, because it might be a method that is refined by a non-void method, or a reference to a non-void function.

We can abbreviate Callable types with a little syntax sugar:

  • Integer(Integer,Integer) means Callable<Integer,[Integer,Integer]>, and, likewise,
  • Anything(String) means Callable<Anything,[String]>.

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(Integer times, 
        Anything(Integer) perform) {
    for (i in 1..times) {
        perform(i);
    }
}

Let's try it:

void printNum(Integer n) => print(n);
repeat(10, printNum);

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(Integer times, 
        void perform(Integer n)) {
    for (i in 1..times) {
        perform { n=i; };
    }
}

This version is also slightly more readable, so it's the preferred syntax.

Function references

When a name of a function appears without any arguments, like printNum does above, it's called a function reference. A function reference is the thing that really has the type Callable. In this case, printNum has the type Callable<Anything,[Integer]>, or simply Anything(Integer).

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

Boolean attemptPrint(Integer n) {
    try {
        print(n);
        return true;
    }
    catch (Exception e) {
        return false;
    }
}

And call it like this

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(Integer n) {
        print("Hello, ``name``, for the ``n``th time!");
    }
}

And call it like this:

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

Here the expression Hello("Gavin").say has the same type as print above. It is of type Anything(Integer).

Static method and attribute references

A static method reference is a reference to a method, qualified by the type which declares the method.

value say = Hello.say;

In a static method reference, there's no receiving instance of the type! We have not provided any instance of Hello in this snippet. What we just wrote is quite different to this:

value say = Hello("Gavin").say;

So for a static method reference, to invoke the method, we must provide two items of information:

  • first, an instance of the type, and
  • then, the arguments of the function.

We provide these two items in distinct argument lists:

value say = Hello.say;
value sayHello = say(Hello("World"));
sayHello(3);

Or, simply:

value say = Hello.say;
say(Hello("World"))(3);

Let's fill in the types, to see what's really going on here:

Anything(Integer)(Hello) say = Hello.say;
Anything(Integer) sayHello = say(Hello("World"));
sayHello(3);

That is, a static function reference is a function that returns a function.

A static attribute reference is a reference to an attribute, qualified by the type which declares the attribute.

Polar coord = .... ;
value angle = Polar.angle;
value radius = Polar.angle;
Float a = angle(coord);
Float radius = radius(coord);

Just to be sure, let's fill in the types:

Polar coord = .... ;
Float(Polar) angle = Polar.angle;
Float(Polar) radius = Polar.angle;
Float a = angle(coord);
Float radius = radius(coord);

Static attribute references work especially well with the map() method of Iterable:

{String*} names = people.map(Person.name); 

Curried functions

A method or function may be declared in curried form, allowing the method or function to be partially applied to its arguments. A curried function has multiple lists of parameters:

Float adder(Integer n)(Float x) => x+n;

The adder() function has type Float(Float)(Integer). We can invoke it with a single integer argument to get a reference to a function of type Float(Float), and store this reference as a function, like this:

Float addOne(Float x);
addOne = adder(1);

Or as a value, like this:

Float(Float) addOne = adder(1);

(There only real difference between these two approaches is that in the first case we get to assign a name to the parameter of addOne().)

When we subsequently invoke addOne(), the actual body of adder() is finally executed, producing a Float:

Float three = addOne(2.0);

Gotcha!

Did you notice that order of parameter lists is reversed in a type expression compared to a function declaration? Look again:

void printSum(String desc)(Float x, Float y) => print(desc + (x+y).string);
Anything(Float,Float)(String) printSumRef = printSum;

The order of parameter lists in the function declaration reflects the order in which we supply arguments when we invoke the function. But in a function type expression, the return type comes always comes before the parameter types, so therefore the parameters which must be supplied first come at the last in the function type.

Anonymous functions

The most famous higher-order functions are a trio of functions for tranforming, filtering, and summarizing sequences of values. In Ceylon, these three functions, map(), filter(), and fold() are methods of the interface Iterable. (They even have a fourth, slightly less glamorous friend called find(), also a method of Iterable.)

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. There's nothing wrong with passing a named function to map() or filter(), and indeed that is often useful:

Float max = measurements.fold(0.0, largest<Float>);

However, quite commonly, it's inconvenient to have to declare a whole named function just to pass it to map(), filter(), fold() or find(). Instead, we can declare an anonymous function inline, as part of the argument list:

Float max = measurements.fold(0.0, 
        (Float max, Float num) => 
                num>max then num else max);

An anonymous function has:

  • optionally, the keyword function or void, and then
  • a parameter list, enclosed in parentheses, followed by
  • a fat arrow, =>, with an expression, or
  • a block.

So we could rewrite the above using a block

Float max = measurements.fold(0.0, 
        (Float max, Float num) {
            return num>max then num else max;
        });

Note that it's quite difficult to come up with a good way to format anonymous functions with blocks, so it's usually better to just give the function a name and use it by reference.

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:

interface Observer {
    shared formal void observe(Event event);
}
abstract class Component() {

    variable {Observer*} observers = {};

    shared void addObserver(Observer observer) {
        observers = {observer, *observers};
    }

    shared void fire(Event event) {
        for (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.

abstract class Component() {

    variable {Anything(Event)*} observers = {};

    shared void addObserver(void observe(Event event)) {
        observers = {observe, *observers};
    }

    shared void fire(Event event) {
        for (observe 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
  • Anything(Event) is useful in container types such as iterables.

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

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 Anything(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:

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. Let's consider adding the ability to remove observers from a Component. We could use a Subscription interface:

interface Subscription {
    shared formal void cancel();
}
abstract class Component() {

    variable {Anything(Event)*} observers = {};

    shared Subscription addObserver(void observe(Event event)) {
        observers = {observe, *observers};
        object subscription satisfies Subscription {
            cancel() => observers = 
                    { for (o in observers) if (o!=observe) o };
        }
        return subscription;
    }

    shared void fire(Event event) {
        for (observe in observers) {
            observe(event);
        }
    }

}

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

abstract class Component() {

    variable {Anything(Event)*} observers = {};

    shared Anything() addObserver(void observe(Event event)) {
        observers = {observe, *observers};
        return void () => observers = 
                    { for (o in observers) if (o!=observe) o };
    }

    shared void fire(Event event) {
        for (observe in observers) {
            observe(event);
        }
    }

}

Here, we define an anonymous function inside the body of the addObserver() method, and return a reference to this function from the outer method. The reference to the anonymous function returned by addObserver() can be called by any code that obtains the reference.

In case you're wondering, the type of the function addObserver() is Anything()(Anything(Event)).

Notice that the anonymous function 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.

Anything() cancel = addObserver(onEvent);
// ...
cancel();

The first line demonstrates how a function reference can be stored. The second line of code simply invokes the returned reference to cancel().

Composition and curry

The function compose() performs function composition. For example, given the functions print() and plus() in ceylon.language, with the following signatures:

shared void print(Anything line) { ... }

shared Value plus<Value>(Value x, Value y)
    given Value satisfies Summable<Value> { ... }

We can see that the type of the function reference print is Anything(Anything), and that the type of the function reference plus<Float> is Float(Float,Float). Then we can write the following:

Anything(Float,Float) printSum = compose(print,plus<Float>);
printSum(2.0,2.0); //prints 4.0

The function curry() produces a function with multiple parameter lists, given a function with multiple parameters:

Anything(Float)(Float) printSumCurried = curry(printSum);
Anything(Float) printPlus2 = printSumCurried(2.0);
printPlus2(2.0); //prints 4.0

The function uncurry() does the opposite, giving us back our original uncurried signature:

Anything(Float,Float) printSumUncurried = uncurry(printSumCurried);

Note that compose(), curry(), and uncurry() are ordinary functions, written in Ceylon.

The spread operator

We've already seen a few examples of the spread operator. We've seen how to use it to instantiate an iterable:

{ "hello", *names }

Or a tuple:

[x, y, *labels]

We can also use it when calling a function. Consider the following function:

String formatDate(String format, 
                  Integer day, 
                  Integer|String month, 
                  Integer year) {
    ...
}

And suppose we have a tuple representing a date:

value date = [15, "January", 2010];

Then we can pass the date to our function like this:

formatDate("dd MMMMM yyyy", *date)

Notice that the type of the tuple ["dd MMMMM yyyy", *date] is:

[String,Integer,String,Integer] 

Now consider type of the function formatDate. It is:

String(String,Integer,Integer|String,Integer)

Or rather:

Callable<String,[String,Integer,Integer|String,Integer]>

Since the tuple type [String,Integer,String,Integer] is a subtype of [String,Integer,Integer|String,Integer], the invocation is well-typed. This demonstrates the relationship between tuples and function argument!

There's more...

You'll find a more detailed discussion of how Ceylon represents function types using tupes here, including an in-depth discussion of compose() and curry().

Now we're going to talk about Ceylon's syntax for named argument lists and for defining user interfaces and structured data.