Help

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.

26 comments:
 
02. May 2011, 10:54 CET | Link
Georg Ragaller
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.

So both ways can be used interchangeably? So that

OpenList<Callable<Void,Event>> observers = OpenList<Callable<Void,Event>>();

can also be written as

OpenList<void observe(Event event)> observers = OpenList<void observe(Event event)>();

And is there a way to use the function style declaration without the name(s)? I.e. is something like

OpenList<void (Event)> observers = OpenList<void (Event )>();

valid?

ReplyQuote
 
02. May 2011, 13:34 CET | Link
OpenList<Callable<Void,Event>> observers = OpenList<Callable<Void,Event>>();
can also be written as
OpenList<void observe(Event event)> observers = OpenList<void observe(Event event)>();

No, a declaration can't appear as a type argument. So a little asymmetry there.

And is there a way to use the function style declaration without the name(s)? I.e. is something like
OpenList<void (Event)> observers = OpenList<void (Event )>();
valid?

No. we actually explored a number of variations on this kind of syntax, but they all turned out either verbose or impossible to parse.

 
02. May 2011, 19:23 CET | Link

Hi Gavin! First off, thanks for those nice introductions. I haven't been reading much else and tried to get my head around your work. Personally, I have the impression that Ceylon is much more accessible compared to Scala (which I have attempted to like, but failed miserably). Anyway, I am excited about Ceylon, but I am not sure, I have digested everything. For example, the following code looks wrong to me:

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

Shouldn't his be:

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

Or did I miss something???

Thanks, -Norbert

 
02. May 2011, 19:24 CET | Link

(Oops. Sorry for the mangled code.)

 
02. May 2011, 20:20 CET | Link

Hi Norbert,

you probably missed the second pair of parentheses of the method addObserver (I did the same at first :-)

So addObserver(void observer(Event event)) has the return type void ...() (where the ... stands for addObserver(void observer(Event event))) which is a function.

This works just like the inline definition of the cancel function. Instead of cancel = ... you have void cancel() { ... } and instead of Callable<Void> addObserver(void observer(Event event)) { ... } (in this case there would be no second pair of parentheses) you surround addObserver(...) with void ...()

-Thorsten

 
02. May 2011, 22:28 CET | Link

Right. The following two declarations are approximately equivalent:

Callable<Void,Event> addObserver(void observer(Event event)) { ... }
void addObserver(void observer(Event event))() { .... }

This is all very consistent, since if you supply two lists of arguments to addObserver(), you get a void, not a Callable<Void,Event>. It's also very consistent with the traditional C style of declaration for things like pointers and arrays. In traditional C, you declare an array like int counts[] to reflect the fact that you get an int out after supplying an index. I've always found this actually much more elegant than Java's int[] counts declaration. (Huh? Why am I supplying an index to the type int?) But I know that other people find it quote confusing an unintuitive.

 
02. May 2011, 22:30 CET | Link
Thorsten wrote on May 02, 2011 14:20:
Hi Norbert, you probably missed the second pair of parentheses of the method addObserver (I did the same at first :-)

I probably should have used an example more like:

Float log(Float base)(Float x) { ... }

With the example usage:

Float ln(Float x) = log(e);

Does that make more sense?

 
03. May 2011, 07:50 CET | Link
Thorsten
Gavin King wrote on May 02, 2011 16:30:
I probably should have used an example more like:
Float log(Float base)(Float x) { ... }
[...] Does that make more sense?

Acutally both make sense (being the same construction after all) but it is easier to read because the second pair of parentheses is not empty and therefore not likely to be overlooked. And I do think that you did use an example like that before. But the example with the void () function is fine as well.

 
03. May 2011, 09:46 CET | Link
Norbert

Thanks.

I did indeed miss the second pair of parenthesis. ;) But seriously, this is rather hard to read, don't you think? The example where the Subscription object is returned explicitly is much easier to read and understand, while the second example is probably what a seasoned Ceylon developer would write. I might get used to this, but honestly it feels Perlish at first glance: easy to write, hard to read.

I'll keep pondering this, though. :)

Cheers, Norbert

 
03. May 2011, 14:21 CET | Link
Andrey
    shared void addObserver(void observe(Event event))() { 

This sort of syntax is known to be a terrible pain-point in C and C++ (function pointers).

 
03. May 2011, 14:31 CET | Link
Andrey wrote on May 03, 2011 08:21:
    shared void addObserver(void observe(Event event))() { 
This sort of syntax is known to be a terrible pain-point in C and C++ (function pointers).

I don't think this syntax is near as complicated as C function pointers! :-)

 
03. May 2011, 20:02 CET | Link
Andrey
Gavin King wrote on May 03, 2011 08:31:
I don't think this syntax is near as complicated as C function pointers! :-)

Let's compare:

C:

void (*addObserver(void (*observe)(Even event)))() {

Ceylon:

void addObserver(void observe(Event event))() {

Well, C is obviously worse: it requires an extra pair of parentheses... I actually like the asterisk in C, because I can see that my function returns a pointer by looking at where the return type is supposed to be...

My conclusion is that Ceylon goes the tough way here.

 
04. May 2011, 00:25 CET | Link

So I count six additional punctuation characters in the C version. That's a pretty big difference.

 
08. Jun 2011, 14:01 CET | Link

Sorry, I need to get back to this example.

You wrote that these two lines are approximately equivalent.

Callable<Void,Event> addObserver(void observer(Event event)) { ... }
void addObserver(void observer(Event event))() { .... }

But I still do not really see this, because the cancel() method which is returned has the type Callable<Void>, doesn't it?

(Actually, I was also thinking that it might be of type Callable<Void,Void> to reflect that it does not take any arguments, but taking no arguments and an argument of type Void should be different. Would a method void foo(Nothing x) be of this type? Or would it indeed be Callable<Void,Nothing>?)

Anyway, either the first line should be

Callable<Void> addObserver(void observer(Event event)) { ... }

or the second line should be

void addObserver(void observer(Event e1))(Event e2) { ... }

in order for your statement to be correct. Am I missing something again? And, oh, what do actually you mean by approximately? :)

 
08. Jun 2011, 19:04 CET | Link

Sorry, you're right, it should have been:

Callable<Void> addObserver(void observer(Event event)) { ... }

The method void foo(Void v) would have the type Callable<Void,Void> :-)

And, oh, what do actually you mean by approximately? :)

The approximately means that there is some information lost when you don't write the parameter list out explicitly (parameter names are the main thing). In this case, where there were no parameters, no information is lost.

 
19. Jun 2011, 16:09 CET | Link

And I suppose there can be more argument lists? E.g.

void weird()()() { ... }

Adam

 
21. Aug 2011, 17:35 CET | Link

I found interesting blog post with idea to generate collections on the fly. May be it would be interesting to prohibit to make new collection implementation traditionally and force users to use factory, described in this blog. First time this factory can return just traditional implementation of collections. Later some specific libraries implementations like GNU Trove or fastutil can be used. This approach can make Ceylon to be even faster than java. Collection generation

// Initialize the factory when the program is loaded.
// Then the bytecode gets generated just once.
static final Factory factory =
  new FactoryBuilder()
    .list()
    .elementType(Integer.TYPE)
    .modifiable(false)
    .factory();

int[] ints = {1000, 1001, 1002};
List<Integer> list = factory.createIntList(ints);

Also I propose not to convert every primitive to object. Instead, compile it to int primitive inside bytecode and convert only in case of specific object calls. So, all are object principle of language still exists.

 
06. Sep 2011, 11:43 CET | Link
Olivier Pernet

Why is

Callable
not contravariant in the argument type?

 
06. Sep 2011, 19:05 CET | Link
Olivier Pernet wrote on Sep 06, 2011 05:43:
Why is
Callable
not contravariant in the argument type?

For now the language spec says that methods in Ceylon are invariant in their argument types, just like in Java, though this is obviously conceptually wrong, and will probably change at some point in the future. For now it makes the mapping to the JVM slightly simpler.

 
06. Sep 2011, 21:17 CET | Link
Olivier Pernet

I see, I didn't realize Java had this restriction. I suspect you will bump into it when designing libraries.

Will there be any problem if a type instance uses different contravariant/covariant types as types arguments in a sequenced type argument position?

 
06. Sep 2011, 21:21 CET | Link
Olivier Pernet

Another, perhaps trivial comment: is it right that you reversed the order of type arguments to Callable because you wanted/needed the sequenced argument last? It is a little confusing when one is used to the lambda calculus/ML/Haskell/Scala... order.

 
08. Sep 2011, 00:16 CET | Link
Olivier Pernet wrote on Sep 06, 2011 15:17:
I see, I didn't realize Java had this restriction. I suspect you will bump into it when designing libraries.

When it becomes a problem, we'll look into changing it. It's obviously incorrect.

 
08. Sep 2011, 00:18 CET | Link
Another, perhaps trivial comment: is it right that you reversed the order of type arguments to Callable because you wanted/needed the sequenced argument last?

Yes, correct.

It is a little confusing when one is used to the lambda calculus/ML/Haskell/Scala... order.

Yeah, but it is the same order in which things appear in a C-style function declaration, so it's actually more natural for folks who aren't steeped in FP.

 
09. Sep 2011, 00:14 CET | Link
Olivier Pernet
Gavin King wrote on Sep 07, 2011 18:18:
Another, perhaps trivial comment: is it right that you reversed the order of type arguments to Callable because you wanted/needed the sequenced argument last? Yes, correct. It is a little confusing when one is used to the lambda calculus/ML/Haskell/Scala... order. Yeah, but it is the same order in which things appear in a C-style function declaration, so it's actually more natural for folks who aren't steeped in FP.

I don't know, I consider myself steeped in both, but I find the lambda calculus order more readable when things get complicated. For example, I had to read this several times before understanding - because the eye needs to go back and forth to follow the arguments passed in:

the type of the method addObserver() is
Callable<Callable<Void>,Component,Callable<Void,Event>>

I think

Callable<Component, Callable<Void,Event>, Callable<Void>>
would be much easier to read: one left-to-right scan.

 
01. Jun 2012, 10:47 CET | Link
Get in my belly | jdpatterson(AT)gmail.com
There's no non-fragile way to define the ordering in which supertype initializers are executed in a multiple-inheritance model. This is the basic reason why interfaces are stateless in Ceylon.

Could simple attributes be allowed in an interface if they were initialised in a way that guaranteed no side effects?

 
23. Dec 2013, 09:17 CET | Link

Due to the extreme amount of garbage, many residents work as Trash Pickers--searching for anything they can find to cheap chanel replica bags sell to make a living. But besides from making a living, the people creatively use what they chanel outlet online store find to fashion instruments for the local music school. Environmental technician Favio Chavez came up with the idea after visiting and seeing children playing on the garbage heap. Seeing the children sparked his idea to build a music school where the children are able to bring music to life with instruments crafted from the garbage found.

Post Comment