Scoping generic functions (by )

So, my favourite model of object-oriented programming is "Generic Functions".

The idea is that, rather than the more widespread notion of "class-based object orientation" where methods are defined "inside" a class, the definition of types and the definition of methods on those types are kept separate. In practice, this means three different kinds of definitions:

  1. Defining types, which may well be class-like "record types with inheritance" and rules about what fields can be read/written in what scopes and all that, but could be any kind of type system as long as it defines some sort of "Is this an instance of this type?" relationship, possibly allowing subtyping (an object may be an instance of more than one type, but there's a "subtype" relationship between types that forms a lattice where any graph of types joined by subtype relationships has a single member that is not a subtype of any other member").
  2. Defining generic functions, by providing the structure of the argument list (but not the types of the arguments, although in systems with subtyping, there may be requirements made that some arguments' types are subtypes of some parent type) and the type of the return value and binding that to a name.
  3. Defining methods on a generic function, which are a mapping from a set of actual argument types to an implementation of the function, for a given generic function.

Note that the method refers to the type and the generic function, and is the only thing that "binds them together". Unlike in class-based OO, the definition of the type does not need to list all the operations available on that type. For instance, one module might define a "display something on the screen" generic function taking a thing and a display context as arguments; this module might be part of a user interface toolkit library. Another module might define a type for an address book entry, with a person or organisation's name and contact details. And then a third module might provide an implementation of the display-on-screen generic function for those address book entries. All three modules might well be written by different people, and only the third module needs to be aware that both the other modules exist; their authors might never hear of each other.

This is good for programmers, in my opinion, as it makes it easier to build systems out of separately-designed parts; it exhibits what is sometimes called "loose coupling". In a class-based system, the author of the address book type would either need to be aware of the user-interface toolkit and make sure their address book entry class also implemented the "display on a screen" interface and declare an implementation of the UI logic (which might not be their interest, especially if there's a large number of UI toolkits to choose from), or users of the address book class in combination with that UI toolkit would need to do the tiresome work of writing "wrapper classes" that contain an address book entry as an instance member, and then implement the display on a screen interface, and have to wrap/unwrap address book entries as they move in and out of user-interfacing parts of the application.

"Ah, but what if the user inherits from the address book entry class and implements the display-on-screen interface in their subclass?", you might say, but that's only a partial solution: sure, it gives you objects that are address book entries AND can be displayed on screen, but only if you explicitly construct an instance of that class rather than the generic address-book entry class - and third party code (such as parts of the address book library itself) wouldn't know to do that. Working around this with dependency injection frameworks is tedious, and success relies on every third-party component author bothering to use a DI framework instead of just instantiating classes in the way the language encourages them to do. An ugly solution, when generic functions solve the problem elegantly.

It also provides a natural model for multiple dispatch. Class-based "methods within classes" mean that every method is owned by one class, and methods are invoked on one object. In our address book UI example, the generic function to display things on screens accepts two arguments - the thing to display and a display context. In a class-based system, this means that the display method defined on our address book entry is passed a display context argument and can invoke operations on it defined by the display context class/interface/type, and if it wants different behaviour for displaying on a colour versus monochrome screen (remember them?) it needs to make that a runtime decision. However, in a generic function system, there would be separate subtypes of "display context" for "monochrome" and "colour", each defining different interfaces for controlling colours. This means you can provide separate methods on the display GF for an address book entry in colour or monochrome or, if you didn't need to worry about colour as you just displayed text in the default style, have a single implementation in terms of the generic "display context" supertype.

This feature is particularly welcome for people writing arithmetic libraries, who want to define multiplication between scalar and matrix, matrix and scalar, matrix and vector, vector and matrix, vector and scalar, scalar and vector, etc.

You can use run-time type information to implement all of this in a single-dispatch system, but (a) it's tedious typing (in both sense of the word) for the programmer, (b) it is not extensible (if somebody writes a "multiply" method in the "Matrix" class that knows to look for its argument being a scalar, vector, or other matrix, what is the author of a third-party "Quaternion" class to do to allow a Matrix to be multipled by a Quaternion?), (c) this robs the compiler of the opportunity to do really fancy optimisations it can do when it knows that this is a polymorphic generic function dispatch.

However, generic functions present a big problem for me, as an aspiring functional programming language author: scoping.

Read more »

WordPress Themes

Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales
Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales