Extending behaviour of Janet objects with respect to standard library functions

[subsetpark]

There has been lots of interesting discussion in the chat and elsewhere about different approaches to extending Janet - protocols, multimethods, user-defined types, and other. It's useful to disambiguate between related problems. I'll try to summarize the discussion around one of them—one that is maybe the most-discussed—here.

Problem: extending the behaviour of primitive Janet functions over new terms

Many of the core behaviours in Janet are accomplished by providing a sensible, composable implementation of a standard library function for some data type. To give an example: to perform iteration, call next repeatedly on the term you want to iterate over. Thus, the many flavors of iteration are decomposed into the more tractable problem of defining a semantics of next for some type.

In general, we are talking about the expression problem. We would like the ability as Janet developers to introduce both new behaviours, such as iteration, and new data types. We would like the ability to implement new behaviours for existing data types as well as include new data types for existing behaviours.

Methods vs. Functions

There is a little bit of inconsistency in the overall standard lib in term of implementation details. Sometimes, the function needing to be implemented is "open", in the sense that it's a method that should be inserted into a table (eg., :close), and sometimes it's "closed" in the sense that the function needing to be implemented is a function, like next, which needs to have sensible semantics implemented at the language level.

Solutions

The above two existing approaches are individual examples of a spectrum of possible solutions to the expression problem. Here is a rough overview:

• Totally closed: the six primitive Janet types are privileged with respect to behaviours like iteration. The definition of any global function like next depends only on its definition in the Janet source.
• Closed functions, open methods: certain core, primitive behaviours are closed to extension, because they are implemented in terms of standard library functions. Other behaviours are open to extension, but only for the Table type, because they are implemented in terms of keyword-based methods. Users can extend these behaviours for any Table or prototype Table by binding a function to the associated keyword in the table.
• Pervasive single-namespace methods: all behaviours are implemented in terms of methods, and thus extensible for any Table. Iteration, for instance, should not be implemented with the next function, but instead always by calling :next.
• Magic single-namespace methods: Some behaviours are method (ie, keyword)-based, and some are function-based (a la next). However, any behaviour in either category depends on keyword methods. next, for instance, should call :next on its object if that method is available.
• Magic separate-namespace methods: Some behaviours are method (ie, keyword)-based, and some are function-based (a la next). However, any behaviour in either category depends on an independent methods namespace. Methods are added to any term, table or not, by special functions get-method and set-method. (:next my-object) would call the :next method on my-object, but not by getting the value at :next in my my-object. It would look for a value bound to :next in the special methods namespace and if that value is present, call it with my-object as the argument. The prototypes system would be extended to dispatch to a table's prototype in both get and get-method calls. The methods namespace covers at least abstract types, in addition to tables, so that methods could be set on non-tables.
• Protocols: stand-alone generic functions (or modules) are defined to encapsulate behaviours like iteration. A new protocol implementation is then written for any given datatype. When the generic function is called, it checks the type of its object and then invokes the proper protocol implementation. This could be implemented in terms of a more strongly reified class/record system, whereby a developer defines a record type and then defines implementations for it, or it could be implemented in terms of the existing prototype system, whereby a developer creates a prototype table and then defines implementations for the prototype, to be inherited by any child. In either case, it would additionally require implementation targets for the existing primitive types and for abstract types (see Protocol Targets, below)

Some Tradeoffs

Some discussion has taken place about the "magic methods" approach.

Single-namespace methods

Janet's current behaviour defines a method as a function that's accessible on a table by get. This has the advantages of keeping the semantics extremely simple and predictable; (:foo bar) is identical to ((bar :foo) bar). Similarly, to define a method for a table, simply put a function in it.

This has the drawbacks of a relatively high likelihood of collision. Because methods are values with normal names in tables, it is very straightforward to accidentally overwrite a table's method by binding a new value to that name in the table. There are methods to reduce, if not eliminate, this likelihood: Python uses the __foo__ convention for its magic methods, making it unlikely that a developer will unknowingly clobber one of those values. Using globally-unique values that are bound to global symbols (for instance, binding some unique value like (def methods/next @"") in the root env and then calling (get methods/next my-object) is another approach.

This has the more serious drawback of restricting extensibility to objects with table-like semantics; for instance, (put methods/to-msgpack @[] (fn ...)) doesn't make very much sense, since arrays can't associate names to values (only indices), so it they would be too semantically poor to support behavioural extension.

Separate-namespace methods

The two drawbacks of single-namespace methods, as described above, could be avoided by implementing an entirely new method semantics. Adding set-method and get-method to the language would ensure that no matter what values were associated in a table, they wouldn't overwrite methods. And since they didn't rely on the existing semantics of associative data structures, they could be meaningfully implemented for any data type, not just tables.

The main drawback here would be that same point: the introduction of an entirely new semantics/namespace into the language. Existing intuitions would not apply to the methods associated with objects and existing functions, for instance, pretty-printing in a REPL, would not "see" the methods in this namespace. This has the potential of adding a sizeable dimension to the language, or the risk of adding a difficult-to-see layer of behavior.

Protocol Targets

For a productive protocols system, we would need the ability to define protocol implementations for any term, not just tables. For instance, given an Iterable protocol, I would require the ability to implement Iterable/next for arrays and tuples, just as I'd require the ability to implement Iterable/next for my new Dog prototype table. However, given two invocations of the form

(Iterable/next @[:a] nil)

and

(Iterable/next (table/setproto Dog @{:name "Fido"}) nil)

The definition of next can be sufficiently sophisticated as to dispatch conditionally based on the type of the argument rather than always reduce to a method call. Therefore, an implementation definition like (defimpl Iterable/next Array [self] <function body>) can reduce to a function body to be evaluated if the object is an array, without having to define an Array prototype or involve tables in any way.

[subsetpark]

Actually, one thing I feel we should establish is:

@bakpakin , I've been assuming the answer to this, but do you currently feel that this is an area of the language worth extending? Currently, Janet stands at around the Closed functions, open methods stage: OO via tables with keyword methods is available and supported, but abstract types/non-table types are not extensible, and certain potentially generic behaviours like next and get don't dispatch based on those methods.

I personally feel like there are some changes that could be made which, even if they don't add a lot of new functionality, could consolidate some of the current differences in behaviour between tables/non-tables on one hand, and global functions/local methods on the other. But of course, I'd want to validate that feeling with you before we all spent a lot of time arguing about what those changes should be.

[bakpakin]

"Protocols" as you mention. would be better described my multi-methods - Clojure uses protocols because they map well to the JVM, but they are strictly less expressive. No support for protocols as you have presented will be added to Janet - in fact, 'protocols' already exist - they are called methods and look like (:my-method x), are single dispatch, and have simple semantics. They of course only work on tables and abstract types, and for abstract types you cannot extend them. This is not something I plan on changing for tables, and perhaps only slightly for abstract types.

So yes, I am committed to "Closed functions, open methods" because multi-methods can be implemented in terms of normal functions.
Something like

(def- my-dispatch-table
  @{'(:string :string :string) (fn [x y z] 1)
       '(:string :string nil) (fn [x y z] 2)
       ...})

(defn my-multimethod
  [a b c]
  ((in my-dispatch-table [(type a) (type b) (type c)]) a b c))

Is quite general, and obviously some macros could make it nicer to use. Of course, the (type x) function will always return :table for tables, which would make it a bit more complicated for custom types based on tables.

[subsetpark]

Ok, that's good to know. Then I think my main question is - how do you see questions like the discussions we've been having about next fitting into this? There's been a fair amount of back and forth - resulting in some changes in the stdlib - about the fact that iteration doesn't compose naturally for everything, because next isn't always defined or doesn't always exactly work for a different kind of thing. So given a function like next, which falls in the "Closed functions" side of that divide as is currently written - do you think it's a problem to be addressed, that if I do make a table with a prototype, I can't define next for it?

[bakpakin]

The main issue is that looking up methods is slow and we want to keep functions like next fast, even for iterating over tables. The code is easy to add, that is not my main issue with it.

[subsetpark]

Ok, got it. That's a useful distinction. I think, as these conversations keep coming up, it will be good to have an authoritative list of "these are the functions that could be generic, but are closed for performance reasons" and "these are the functions that you can extend with methods".

[bakpakin]

I think get-method and set-method have potential but could be refined. I think a key insight is that "multiple namespaces" can be implemented in terms of table prototypes, and set-method I think is superfluous.

get-method could be as defined very simply for tables and abstract types:

• for tables, same as get but skips the table itself and goes directly to the prototype (if it exists). This changes the semantics a bit but works well for the common case, and avoids the issue of making normal tables behave as special objects while still allowing arbitrary keys to be added. This would be a breaking change as method calls that used to work may break.
  It could be defined in janet like (defn get-method [obj method] (get (or (table/getproto obj) obj) method)), but the real implementation would be inlined into the interpreter in C.
• for abstract types, get-method would just look at a new function pointer that we add in C, perhaps defaulting to the current get function pointer.

For set-method, on the other hand, you need somewhere to store function pointers. For tables, I suppose you could store it in the prototype table if it existed, and for abstract types that could be yet another function pointer. However, I'm not sure that this would really even be needed.

[MikeBeller]

I like the idea of staying with closed function / open methods. That keeps things simple which is one of the main things I love about Janet. But @bakpakin -- what if in these core functions likenext, in the switch case for table type, you just did a check to see if there is a non-nil prototype. If the prototype is nil you continue with the same fast existing code for the function. If it is non-nil, then you have to check if the prototype has a :__next field, and run that. Could that be an acceptable amount of impact on performance? Basically, anyone who is using prototypes is probably doing something a bit "OO"-ey and may be willing to pay a bit of performance for flexibility. The coder who is not using prototypes, is sticking to the "best to use POD when possible" philosophy that you espouse in the manual, and gets the better performance. (Oh and thanks for writing up all these ideas @subsetpark )

[MikeBeller]

Closely related to this topic -- I have just implemented a Proof of Concept module called janet-abstract (https://github.com/MikeBeller/janet-abstract). It provides a new abstract type that lets you create tables in Janet which can hook the 'next', 'get', 'put', 'tostring', 'compare' functions in the JanetAbstract struct, and write the functions in Janet in the table's prototype. I think it's something @bakpakin referred to in the past as a Proxy.

I then used janet-abstract to upgrade my janet-set module (https://github.com/MikeBeller/janet-set) to have much better semantics for iteration, printing, and things like 'length'.

Check it out if you have a chance. I had one major learning -- because the "get" function in abstract types is shared between getting methods from the method table, and other uses, you can not easily create an abstract container type (whether in C or Janet) which supports keywords as a key type. Fuller discussion in the readme to janet-abstract.

[subsetpark]

Really nice @MikeBeller ! Does it also mean you can customize the value of (type)?

[MikeBeller]

Thanks @subsetpark --- as of yet you can't customize (type) -- it's always :abstract/new. I guess a more "full" implementation maybe would have a registry. You would register a prototype with a name (abstract/register :sometype ) , and then (abstract/new :sometype ) would set the prototype to the registered one associated with :sometype. Then (type ..) could return :sometype. Maybe I should add that? But I also kind of want to hear where this discussion goes with regard to retrieving the methods a type supports before going too deep with this module. If the core goes in some different direction this would be wasted effort.

[subsetpark]

This does seem like another good argument for a breaking change to get-method (attn @bakpakin )