6

Martin Odersky finished one online course on Scala with an unanswered question:

Can we implement one concept in terms of other ?

  • Objects in terms of higher order functions?
  • Higher order functions in terms of objects?

It is clear that high order functions can be implemented using objects but I am not sure if it works the other way round or at least while using static types.

Suppose that closure can contain encapsulated data as object does but it still has only one 'method' in its interface - applying itself. In dynamic languages (or in static ones if we use some broad type like Object or Any) we can pass and return anything from this function but is this really an object ?

8

With dynamic typing, it is fairly straightforward to implement an object-oriented system in terms of closures. I've written about this in my answer to “Modelling Objects as Functions” and expanded on that on my blog. There are some details about open recursion that are necessary to get certain OOP features such as subclassing right, but it's doable. In short, invoking the closure representing an object maps a method name to a method bound to that object, which can then be invoked as an ordinary function. Usage might look like result = object("methodName")(otherObject).

However, OOP and static typing are fundamentally at odds. There are various interpretations of OOP, such as OOP-as-message-passing or OOP-as-virtual-dispatch, but a central theme is that we do not statically know the exact runtime type of an expression such as x. However, many statically typed OOP languages do assign type bounds to an expression (such as x is a subtype of Iterable). When implementing objects in terms of closures in a statically typed language, we quickly run into the problem – when specifying the required method as an argument to the dispatch function, we can't statically know the required signature of the function. In the above example, how do I know that the result of object("methodName") should be a function accepting exactly one parameter?

The common solution when implementing objects is to make the object-system unityped (aka. untyped). That is, all method signatures would have the same type regardless of their arity (number of arguments) or of the types of arguments. This also requires that all our objects have the same type in the host language.

Some languages might be able to do better. E.g. in C++, we could pass the requested method type as a template parameter to the dispatch function: auto result = object<ResultType(ArgumentType)>("methodName")(otherObject). A clever implementation could then use different lookup tables to dispatch int() or int(int) method types etc. However, we cannot statically guarantee that the requested method exists since it is provided as a string. Another possibility would be to pass in a (visitor-like?) Message object rather than a string name to the dispatch function, which might allow more type safety in statically typed host languages, but I do not have sufficient experience with implementing OOP in static languages to describe this in more detail.

1

Effectively, yes. Closures and objects are equivalent. Higher order functions are a bit more debatable. Without closure over local variables (or if local variables are immutable in your language), there can be no mutable fields in the pseudo-object. If you can only get immutable sort-of objects, then it is more easily argued that they are not like objects.

But from a conceptual standpoint, you should generally think of closures and objects as similar beasties. In C# for example, closures are implemented via classes. I would expect Scala to do the same.

  • 2
    Objects and mutability are completely orthogonal. – Jörg W Mittag Dec 26 '15 at 15:42
  • @JörgWMittag - while I would tend to agree with you, not everyone does. – Telastyn Dec 26 '15 at 16:13
  • 2
    You, Alan Kay, William Cook, and Oleg Kiselyov agree, that's more than enough for me :-D – Jörg W Mittag Dec 26 '15 at 19:12
1

You can think of an object as a closure that closes over the member variables of the object and, each time it is invoked with a method name, it returns a method implementation. You can then apply the returned method implementation on the actual method arguments.

Since the result of this closure is a procedure / function (a method implementation), it is indeed a higher-order function: a higher-order function is a function that either takes functions as input arguments or returns a function as a result.

0

Looked from a functional programming perspective, "objects" look basically like this:

  1. Record types, with one field for each public method or field;
  2. The values of most of those fields are first class procedures;
  3. All the procedures in an object are closures that scope over the same private bindings.

So with that said, let's turn to your confusion:

Suppose that closure can contain encapsulated data as object does but it still has only one 'method' in its interface - applying itself.

The part that's missing here is my #1—the part about record types. I'd say that you ought to look at it in these terms: OOP languages are designed with a construct, the class, which amalgamates closures and record types. In functional languages these are generally treated as orthogonal features.

In dynamic languages (or in static ones if we use some broad type like Object or Any) we can pass and return anything from this function but is this really an object?

Sometimes people translate the (hopelessly vague) OOP idea of "message passing" into these terms:

  1. Messages then explicitly modeled as values. (Tagged union types/case classes are excellent for this.)
  2. An object, then, is a value whose principal operation is to accept messages and respond to them.

But I'd say that this, looked from a functional programming lens, is basically a degenerate version of the interpreter pattern.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.