The basics of the Expression Problem, from a "functions and types" perspective, boil down to the following:

  • Replacing types with a new type, not known at the time of interface definition - Replacing functions with new functions, not

The primary way I've been thinking about this is in terms of (multi-sorted) algebras:

Why? Well an algebra is a very simple concept: It's just a bag of operations (each of which takes a certain number of arguments), which compose together in an un-restricted way. (In general, algebras also embed equivalence classes via equations, but what we're talking about today is just a free algebra, with no equations at all).

To put it more simply, an algebra has a bag of operations and allows you to build an operation tree out of these

->

From this point of view, a "type" classically provides two things: - A layout/representation of some data - A set of operations that can operate on this data, with some (often implied) semantics

The Expression Problem is about allowing each of these to be extended

Zig doesn't realize it yet, but it's actually weakly object-oriented in style so far, so it allows the creation of new data variants easily (duck-typing makes this easy).

But what do I do if I'd like to define a new algebra (i.e. new set of operations for a type U)? Well, I can't, really. The original type T defined in a module M has a canonical set of operations which are closed. That is, the definition of T has to be modified in order to support extending it with new methods.

Newer languages have a partial solution for this problem:

C# allows extension methods, Rust has Traits, Swift has protocols, etc.

Each of these has some flaws associated with it, though:

  • C# extension methods are only one layer deep, so extending a Type with new operations for another module to use is not possible (AFAIK). Since scopes are not first-class objects, you can't using an extension method namespace in a foreign function
  • Rust traits are very expressive and algebraic. However, they are also canonical. That is, they enforce a single implementation of the algebra per-type. They also come with "orphan rules" to prevent conflicts, which essentially means that person A defines a type, person B defines a set of operations, a module C cannot implement B for A's type. To work around this, Rust supports "wrapping" A's type in a new type defined by C. This allows the user to opt-in to one implementation or another by switching types, but it requires a lot of boiler-plate, and it's noted to be quite brittle/inflexible by the community.
  • Swift's protocols make it easy to add new operations, but they can have conflicting requirements from the parent type (name collision), which can be resolved in surprising ways https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151207/001861.html I'm not sure what the latest status on this is, but it can be improved

There's another wrinkle for Zig: - Globally-resolved extensions/traits not only add complexity in terms of reasoning about where each operation was defined on, but they make operator-overloading completely inviable (since it's not explicit).

So let's take the best attributes from the systems we know so far: - Reference methods w.r.t. an interface definition (rather than duck-typing them) - Many issues of overloading, method conflicts, etc. are due to nominally typed methods. Referring to a definition of an interface allows for an implicit 

  One famous instance: a .map() function might be part of a functional map-reduce algebra
  for streams (like this one), or it might be a function in a GIS system to obtain a reference
  to the map object, or it might be part of a GPS module, or it could refer to an item in a
  video game.

  The brilliance of type classes is that they are _not_ nominally (duck) typed. You must specify
  _which_ algebra your function is being implemented for, not just what the name of each method
  should be. Further more, the classes themselves (trait, or algebras, whatever) are identified 
  as _objects_, not as names.

  So even though Module A and Module B independently define a "MapOperations" type-class, one might
  refer to the operations in a video game, and another in a GIS system. Neither of these definitions,
  or the implementations of the methods conflict, since they all refer to the definition, where the
  expectation of the _semantics_ of the functions is made explicit

- We'd like to support defining multiple interfaces/algebras/type classes/traits on a single object

- Finally, we'll do things in a proper Zig style: algebras will be _manually_ manipulated to allow for inheritance,
  generic implementation, multiple interpretation, etc.

  This completely removes the need for a trait solver of any kind, and provides maximal flexibility, at the cost of some
  extra management by the user.

- There are advantages and disadvantages to being _object-oriented_ (i.e. tying methods to an object). We'll
  do our best to cover both...

  	   There are two ways to do this:
   	- Either we define everything w.r.t. an object (and maybe allow splitting off the method defs)
	- or we define everything as a separate algebra, and then allow binding to objects

- Open: method schema are very similar to struct definitions, so how do we share these as much as possible?

- Now the question is: Why can't we do this in Zig today? Well, the answer is that we (kind of) can! But it's
  not been adopted by the standard library yet, which will seriously limit its adoption

  Object-oriented duck-typing is also a bad habit, so maybe needs some discouragement
   
   -> "Using the type namespace for what you shouldn't"
   		-> Is there a way to enforce not putting methods in the type namespace? I don't think so...
		-> Yes, probably - literally just don't let those methods be public?
			-> The problem is how you implement public traits then, vs. "client usage"
			-> So you need a concept of "implementing an interface"
				-> But this is algebraically inconsistent - when does an interface become "client" code?

	-> What if instead, we allow "bad usage" but make it fixable?
		-> This requires de-structuring and re-structuring

  Finally, programming in this style is too inconvenient without proper scope introduction

Hmm, what if we go whole hog on the "types are name spaces idea"? Then, a type doesn't just have a set of functions that are keyed by the trait. It even has a set of fields!!! Woah, weird thought. And then all the data access is kind of like a "default" trait specific to that object. -> And the reason we don't expose data very often is that it is rarely semantically invariant -> Meanwhile, methods are rarely type-specific (but the non-public ones usually fall into this category)function -> This also potentially suggests a rule for how invariants are implied/enforced/continuous with the given object??

But now we get back into our RTTI problem, which is that dynamically constructing and de-structuring objects is expensive (kind of) That said, it gives us a very natural rule for X ++ M <- this is allowed if M only includes comptime members, in which case it has no run-time cost

<- Hmm... M ++ M looks suspiciously like CSL...

So, the idea is that we want to allow "type schema", which is essentially just a guaranteed footprint for a type <-- This can be implemented in Zig already?? and we also want to allow liberal structuring and de-structuring of types, though probably only with comptime fields -> If we can merge this with the notion of tuple/tag/context, then that will be very helpful

So, in typical Zig style, is there a very explicit and flexible way to handle all of this?

Moreover, if we through out the complications of overloading, extensions, delegation, etc. - Can we boil down all of these to a small core calculus manipulating algebras? I believe the answer is yes, and here's why:

You can see here that the definition of an algebra depends on an open type parameter: fn MatrixAlgebra(T: type) { }

TODO: Does the object algebras paper