Scoping generic functions (by alaric)

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.

You see, another feature I like in programming languages is lexical scoping in module systems. That meaning, any given module in a program imports bindings from modules it lists as explicit imports, and only has lexical access to bindings it explicitly imports.

This means that any given piece of code in a module has access to:

1. Other things defined in the module, as long as the piece of code is lexically within that scope (other functions in the module are welcome to have their own local bindings)
2. Things exported by modules imported by this module.
3. Things made available to that code when it's invoked from outside the module at run time, through function arguments (or dynamically scoped parameters, but they can be modelled as implicit function arguments (especially if you consider them as being stored "inside" the function's continuation when it's applied)).
4. Things obtained by applying functions the code has access to, to other values the code has access to (for instance, the code might be passed an address book entry at run time, and apply a "give me a textual description" function it imports from a module, to get a string containing a mixture of properties of the address book entry and template text from the implementation of the "give me a textual description" function).

This clear-cut enforcement of what a piece of code has access to, lexically and dynamically, makes it easy to:

1. Perform separate compilation of that code, which is particularly useful if the same module is used in lots of different places in a system; it need only be compiled once, and its compiled code can be shared in memory.
2. Define the meaning of the code statically. Its lexical dependencies are easily identified as any binding not introduced via a lambda, and can be statically analysed to define its semantics in terms of unknown dynamic inputs.
3. Securely combine untrusted modules; a module cannot gain access to something it hasn't imported or been given at run time. So if you can whitelist/blacklist its imports and control what you pass it dynamically, you can control what it has access to (ok, when you apply untrusted functions you implicitly give it access to a memory allocator and a CPU (which can be thought of as implicit arguments to the function) which it can use to waste resources - unless your runtime allows passing in "restricted" memory allocators and CPUs that enforce resource limits - and you need to be careful about modules that allow access to other namespaces, such as the filesystem or network interfaces, but my solution to that is to disconnect such modules from such global namespaces and make them just define operations on a namespace, with the namespace values being given to the program itself at the top level - like Clean's World type - a model which also fits nicely with handling such external operations in a pure functional language...).

But generic functions can ride roughshod over all of that, unless I can think of a way around the problem!

An example of the scoping problem

Imagine we have the following modules:

• Module A defines a "describe" generic function that accepts a single argument and returns a string. Its documented purpose is to return a human-readable British English description of the argument, as a string.
• Module B defines a "Person" type that encapsulates a bunch of fields about a person: name, date of birth, favourite colour, that sort of thing.
• Module C imports modules A and B and defines an implementation of "describe" on the "Person" type, that does the obvious thing: looks at the fields of the Person instance and writes a description of them: "Arthur Scargill, a level-53 Death Mage, born on the third of August 530 BCE, whose favourite colour is pink."
• Module D imports module A and defines an implementation of "describe" on the "List of any value" type, that calls "describe" on all the elements of the list and combines the descriptions of the list elements into a nice description of the entire list ("A list with twelve elements, those being: Firstly, ...; and, finally, the twelfth element is ...")
• Module E imports modules A and B, and contains code which instantiates a number of Person objects, puts them in a list, and calls describe on them.

Our module E needs to import module A to get the "describe" GF, and needs to import module B to get the ability to instantiate Person objects. Neither modules A nor B import modules C or D, and yet somehow, methods defined in C or B need to be reachable in some manner by module E.

Somehow, the call to describe a list of people in module E needs to find the method of describe that handles lists in module D, which in turn must find the method of describe that handles people in module C, despite neither modules E nor D actually importing (or having any knowledge of) module C. A way of doing this must be found that either extends the normal notion of module importing, or somehow builds upon it.

An important point is: defining a method on a generic function does not create a value that can simply be exported and then imported where it is needed. Generic functions, types, non-generic lambda functions, constants, and so on are all values which are exported by modules either as top-level named bindings, or as anonymous values that can be reached through chains of reference from those top-level named bindings (yes, you could have a module that exports a list of anonymous generic functions, they don't need to be individually named). But when a module implements a method, that method somehow flows "up" into the generic function that the method is on. The generic function can flow into the code that declares the method through any of the normal scoping mechanisms detailed above, but that method implementation then swims against the stream.

This poses two problems:

1. How the system finds modules C and D at all. Previously, any module could be statically analyzed with reference only to modules explicitly imported into it, as any module not imported by the module cannot affect the code in the module other than through known run-time dynamic inputs: function arguments (implicit or explicit). This meant that all the relevant modules could be found by recursively traversing the imports of modules. But if methods can extend generic functions in this manner, then the semantics of a module depend on the module and some notion of a set of modules whose methods can affect generic functions used by the module. How is this set defined? Suddenly we need a notion of a larger "system" that was previously missing from the language semantics, which provides a scope for generic functions and methods to find each other in, and some means of specifying what modules should be loaded into the "system".
2. How to maintain referential security. Code within the same "system" potentially has access to arbitrary methods within that "system", if it has access to the generic functions those methods extend and instances of the types.

To make a concrete example, imagine we have a situation where a method is defined on some type that has various subtypes, but the method does not need to be overridden for them; the supertype behaviour is perfectly fine. For instance, the supertype is "Array", the generic function returns the number of elements in a container type, and the subtypes of "Array" or specialised "LargeArray" and "SmallArray" which exist purely for the convenience of the garbage collector (LargeArray instances are stored in a separate memory pool so they don't need to be copied when the compacting GC runs, and have special reference counting instead, which is fine as they can't contain references to heap objects so there's no scope for circular reference). A module loaded as part of some less-trusted code has perfectly legitimate reasons to have access to the collections module that defines the number-of-elements generic function and the array library, but it happens to secretly take that opportunity to define a method of the number-of-elements GF on the LargeArray type that never terminates (and instead sits there allocating memory and retaining references to it). Trusted code elsewhere in the system (running without resource limits) then attempts to find the number of elements of an array that happens to be large, and boom, you have a denial of service.

Normally, if a module A imports a module B, it means that module A is making some decision to trust module B to some extent - which is a choice of the author of A and made clear in A's source code - while module B has no need to trust module A, nothing module A does can affect the functions of module B or other users of module B, and so on. But if we allow modules to define methods on generic functions exported by other modules, that protection no longer exists.

This implies that our notion of "system" that is used to control the scope of methods and generic functions should be used to isolate untrusted code, too, but then what happens when values are passed between trusted and untrusted code? When a generic function crosses into a "system" from "outside" should methods defined "outside" be automatically allowed in, but not the reverse? If an outer "system" that extends a standard module's "describe" generic function for some custom type, and passed an instance of that type into untrusted code in a "sub-system" that also imports the standard "describe" generic function, should methods that implement "describe" for that type be automatically available as it's a "sub-system" of the parent in which they are defined? It would perhaps be annoying if they require explicit whitelisting, as that would require the code that creates the sub-system for untrusted code to be explicitly made aware of the existence of that generic function and its method.

What options are there?

We could look at the different ways values are available to some code, as mentioned above, and see how they can be applied to this problem:

1. "Other things defined in the same module" aren't a problem, we can consider all generic functions and methods defined in the same module along with their uses in the module together within the same implied trust/configuration boundary.
2. Explicitly importing methods to the generic function call site won't do. Our "Display a list" code shouldn't need to know about importing the module that defines display on a Person.
3. Having some kind of "system" object passed around as a dynamically-scoped implicit parameter to all applications, and generic function applications look inside the "system" object to find available methods. This is probably the simplest, and most compatible with the notion of a constrained environment for untrusted code as it works entirely within the existing referential security model, but still requires some mechanism to define a "system" in terms of a set of modules methods available within it, and some thought would be required on how to implement those really fancy optimisations if we want shared separate compilation of modules.
4. Embedding references within other objects does allow one partial solution: Binding the "display a person" method inside instances of the "Person" type, as class-based languages do, looks initially promising but:
   1. This requires the constructor of the Person type to know about the "display" generic function and the "display a person" method, somehow, which has just sort of moved the problem.
   2. I don't know how to reconcile that with multiple dispatch. Which arguments to the application of a generic function do you "look inside" to find the appropriate method for that combination of arguments?

Existing Approaches

It's instructional to see how other systems avoid this.

1. Class-based systems have the methods defined inside the classes, and (effectively, if not actually) instances of the classes carry pointers to the implementations of all their methods. This means that a module importing a class type T can, from the static definition of the class type, know that a pointer to the "describe" method implementation can be found in a given position within any instance of T; a separate module defining a subtype S of T will do so by exporting a constructor for S that fills in a pointer to S's implementation of "describe" in that position in the object, so code that calls "describe" on any instance of T will be correctly routed to the appropriate implementation for any subtype. Subtypes can extend the memory images of instances so all the supertype-declared things are still at the same offsets and subtype-declared things come later, so code that handles values of types that can have subtypes need to expect, and not be fazed by, unknown extra data hanging off the end; and there's some exciting tricks that need to be done to make this work in the presence of multiple inheritance (ask me about those if you're interested!), but it all works out OK. At the cost of having to put up with single-dispatch methods-defined-inside-classes programming, euch.
2. Most existing generic function systems aren't purely functional (I've never met a purely functional language with generic functions, if anybody knows of one please tell me!). They usually have the notion that importing a module both exposes some bindings and executes some "module body code" purely for its side-effects. Generic functions are mutable objects, and defining a method on a generic function mutates the generic function to "insert" the method. The notion of "what is the scope of a method/generic function relationship" is thus turned into the issue of "what is the scope of a mutable variable contained inside a module", which is generally deferred to the platform-defined notion of a "process address space", and referential security is rarely given much thought. This also means that there are Complications around the state of the system when module bodies are running - as module bodies have to be executed in some sequence to correctly set up all the generic functions in the system to know about all their methods in the system, the state of the system while those module bodies are executing is partially-initialised in a way that depends on the other the system decided to execute those module bodies (which, even if defined in the language specification, then depends on what modules are imported by what in the system, which may be unknown by any one given module). This can lead to some obscure bugs if the module bodies use any generic functions.

The Core of the Problem

I want a pure functional language that (in order of descending priority):

1. Has generic functions with multiple dispatch.
2. Has a clearly defined notion of what methods are in scope for any given application of a generic function.
3. Is performant enough to do useful work.
4. Allows for referential security domains, which are as lightweight as possible. Ideally that would mean that a referential security domain would be a purely runtime thing, like a CPU/memory resource limit, and the same code can be used in different domains without recompilation and values can be passed between domains by sharing pointers to the same in-memory representations, so that these domains are quick to create, don't consume much storage, and are quick to pass values and the flow of control in and out of - but I suspect I'll need to make some compromises here.
5. Can also provide some form of "interactive environment", a lightweight (in the sense that values, including functions, can be shared between it and the parent domain) security domain that can be repeatedly extended with more generic functions / methods / module imports / etc (and overrides to existing methods) in order to support a REPL; performance need not be a major concern in this case, as long as the interactive environments can call code imported from the parent domain and have it run without any more than per-call time/memory costs due to the domain transition.

Actually, perhaps (3) and (4) can be traded off dynamically - with lightweight security domains implemented by passing around a dynamically scoped "system" for method lookups, that can inherit from a parent "system" so that values can be passed in and out (with methods available in the parent being automatically available in the child) AND heavyweight security domains implemented by creating an entirely isolated environment where code is compiled with static knowledge of all available types and all available methods of all available generic functions, which values can only be passed in and out of through I/O channels rather than as values. The fun part being that a heavyweight domain could create lightweight sub-domains that inherit methods from the heavyweight parent, so the systems need to be interoperable!

Such a heavyweight security domain, initialised with a set of known modules of code (and only extensible through lightweight security domains that are unable to extend the generic functions in the parent security domain) would offer a convenient boundary for whole-program optimisations other than optimising polymorphic generic function applications, too.

Well, that's my thoughts so far (and the above waffle pretty much encapsulates my thought processes taken to get here, if any students of software architecture want to see an example of how I do it), but I don't really love the solution I've come up with as it involves an unpleasant performance tradeoff (even the statically-compilable heavyweight domains trade better execution performance for worse setup/communication performance due to not being able to share things with the parent domain). If anybody knows of any pure functional languages with generic functions so I can see how they handle these issues, or knows of any better tricks, please tell me!

2 Comments

• 

  By Jeff, Sun 13th Dec 2020 @ 4:51 am

  Haskell's "type classes" and Rust's "traits" aren't usually described as generic functions, but a generic function is equivalent to a trait with just one method.

  I think you could get the lexical behavior you want in such a trait-based system. (Some languages might already work this way, maybe Idris? I'm not sure how it actually resolves instances.)

  • a "trait" is just a polymorphic record, that usually has functions for the values.

  • A "generic function" is just a trait with a single function in it.

  E.g.

  // Made-up language syntax. {} denotes type arguments. I'll try to be
  // mostly haskell-ish but details aren't important.
  
  // Trait for things that can be multiplied (e.g. "operator*").
  // We do not require the left and right types to be the same.
  struct Mul {L} {R} {
      O: Type
      mul: L -> R -> O
  }
  

  • In order to call mul a b, you need an instance of Mul A B. (This is is just a plain struct instance, and mul is just a struct member that happens to be a function.) You could do this explicitly:

    mul3 {T: Type} (m: Mul T T) (a: T) (b: T) (c: T) -> m.O = m.mul (m.mul a b) c

  Note that the output type here depends on the input argument m.

  • Then to make it ergonomic and avoid needing full dependent types, allow instances to be implicit, compile-time parameters like the type:

    mul3 {T: Type} {M: Mul T T} (a:T) (b:T) -> (c:M.O) = M.Mul (M.mul a b) c

  • At a call site, an implicit parameter will be filled in automatically if there is exactly one value of the required type in scope. If there is none, or more than one, the call is ambiguous. (This rule might be too simple; fancy it up to your taste.)

  • Implicit parameters can also be passed explicitly to disambiguate. E.g. using Idris's syntax to pass by name:

    let a: MyMatrix = ...; let b: MyMatrix = ...; let c: MyMatrix = mul {M=ElementwiseMul} a b; let d: MyMatrix = mul {M=MatrixMul} a b;

  ...

  I've been fiddling around with similar ideas, because I don't like the notion that the meaning of some piece of code depends on some ambient "main program" program in which the code is embedded. I want names to either be completely unambiguous (e.g. corresponding to a strong hash of some algorithm defined elsewhere) or explicitly parameterized.

  Unison (https://www.unisonweb.org/) is a language exploring similar ideas.

• 

  By andyjpb, Mon 11th Jan 2021 @ 5:01 pm

  Your mention of polymorphic inline caching lead me to an idea of option 3 throughout the article.

  The main problem I see is how to statically analyze and compile Module D (describe list). For a module that uses generic functions solely on values it creates itself you know which Generic Function Method to call at compile time. In Module D you don't know what will be in the list as it comes from the user at their compile time.

  ...so you're never doing whole-program optimization but rather compiling new things against exiting binary dependencies.

  In that case a "sufficiently smart compiler" can know at compile time whether or not it needs to generate code to do a dynamic dispatch for the method call. So there can be a trampoline like the polymorphic inline cache (although not a cache) that dispatches on type patterns it knows are possible and then defers to a dynamic environment for "else". i.e something like your idea of "system".

  This way it becomes Module E's job to import Module C and D. I'm not sure how else you'd do it explicitly because the author of Module E is best placed to decide which of many competing Cs or Ds they like best. ...but I suppose it could be an operator's policy decision (doesn't Java allow something like this with CLASS PATH overrides?)

  Anyway, when describe is called through E then the dynamic dispatch in C and D gets to see the imports that E has done. When describe is called in another context then there will be a different dynamic environment ("system") and something else might happen.

  I guess it's creeping towards the "Dependency Inversion" problem tho'. Things passed in to modules you depend on might cause problems but isn't this the same problem one always faces with any kind of callback or higher order programming? It's just a difference of whether the binding is coming from the static/lexical environment or the dynamic one?

  I think you're using Module A as a way to declare a symbol/name as a reference to Generic Function and therefore not a compiler error if it can't be found? It also seems to have some implicit security role as well? i.e. the same names for Generic Functions are different if they're imported from different Modules? i.e. a method for A::describe will never be used to implement a call to Z::describe?

  There's inherently some tension here between what can be done with a whole program compilation and separate module compilations, but I feel that both can have the same functional and security properties, even if the dynamic dispatch required in the latter case trades away some performance?

  So I guess I'm saying let symbols/names that are declared as Generic Functions but unimplemented draw from the dynamic environment and make a feature out of the fact that module author at any point in the call chain can make a decision on the implementation with an explicit import of a method with the correct signature?

Other Links to this Post

RSS feed for comments on this post.

Leave a comment

*Name

*Email (not published)

Website