# Subject-Oriented Programming

The idea of subject-oriented ostensibly originated as a critique of
object-oriented programming. In most statically-typed class-based
OOP systems[^2] beginners are encouraged to lay out their inheritance
hierarchy by basing it
on an ontology of concepts, i.e. the classic `Cat`-inherits-from-`Animal`
model. In practice, as people become more and more fluent with writing code
in an OOP language, they tend towards using interfaces more and more and
inheritance less and less, so as to couple the components less tightly.

[^2]: Are there statically-typed prototype-based OOP systems?

As Borges notes in "The Analytical Language of John Wilkins", "...it is clear
that there is no classification of the Universe not being arbitrary and full
of conjectures. The reason for this is very simple: we do not know what thing
the universe is." Necessarily, then, every ontology a programmer creates is
going to be arbitrary. A simple example might be edible plants: one programmer
will choose to structure their inheritance hierarchy such that `Tomato`
inherits from `Fruit`, as it derives from the flowering tissues of plants,
whereas another will declare that `Tomato extends Vegetable` because they are
not particularly sweet when eaten—and anyway, the codebase already has
`Salad makeSalad(ArrayList<Vegetable> ingredients)`.

Consequently, one problem with the inheritance-hierarchy-as-ontology system is (as Ossher
and Harrison describe in their paper) that it only works if your program is
guaranteed to always need/use that _particular_ ontology. To use a
somewhat more practical video game
example, let's say that you have game units in some manner of strategy game,
and you decide to structure their class hierarchy as follows:

    - Unit
      - Mobile
        - Ally
        - Enemy
      - Stationary

This is fine... until you'd like to have a stationary enemy (e.g. some kind
of gun emplacement.) You could rearrange to the following:

    - Unit
      - Ally
        - MobileAlly
        - StationaryAlly
      - Enemy
        - MobileEnemy
        - StationaryEnemy

...but aside from the work of refactoring, this now requires a third subclass
of `Entity` to account for the neutral entities (like trees), and you can no
longer write functions that take _any_ `Mobile` unit. As indicated before,
seasoned OOP programmers might instead reach for interfaces (`implements
Mobile, Ally`), or you might avoid encoding this information in the type at
all (e.g. give each `Unit` instance variables corresponding to motility,
alignment, &c.)

Nevertheless, there are some advantages to static type hierarchies. Perhaps we would
like a hierarchy of mobility:

    - Unit
      - Immobile
      - Mobile
        - Walking
        - Flying
        - Swimming

At times, we would like to write methods in terms of anything that can move,
whereas at other times, we'd like to write methods solely in terms of swimming
units, and at other times, we'd like to write methods in terms of any unit at
all. This is one thing that Harrison and Ossher were attempting to preserve
when they described Subject-Oriented Programming, and is the salient way in which
it differs from Object-Oriented Programming: in an OOP system, an object `o`
_is_ an instantiation of a class `C`, whereas in a SOP system, an entity[^1] `e`
_can be seen as_ an activation of a subject `S`.

[^1]: Harrison and Ossher actually use the word _oid_, as short for _object
identifier_, but I prefer the term _entity_.

In a Subject-Oriented model, we could have several distinct class
hierarchies, e.g.

    - Unit              - Unit              - Unit
      - Immobile          - Allied            - NoAttack
      - Mobile              - PlayerOwned     - Attacking
        - Walking           - FriendlyNPC       - MeleeAttacking
        - Flying          - Enemy               - AreaAttacking
        - Swimming          - Wild              - RangeAttacking
                            - EnemyNPC

So if the player has an archer, it can be seen as a `Walking` unit, a
`PlayerOwned` unit, and a `RangeAttacking` unit. If we then write a method
that works with a `Mobile` unit, or an `Allied` unit, or an `Attacking`
unit, we can pass it the player's archer, despite the fact that these are
all distinct ontologies. I'm handwaving wildly over the implementation
details for the moment, and to some extent I'm diverging from the original
conception, but I'm trying to stay roughly faithful to the ideas as
presented.

Curiously, Subject-Oriented Programming has a large conceptual overlap with
an idea quite in vogue among game developers, that of Component-Entity
Systems. What Harrison and Ossher would call _subjects_ are there called
_components_, and many of the details as implemented are different, but the
critical idea—that of an `entity` which takes on various roles as needed—is
present in both systems.

# A Subject-Oriented λ-Calculus

What would a subject-oriented λ-calculus look like? I'm gonna come up with
something that _looks_ like subject-oriented programming if you squint, but
it's not going to be particularly faithful to the original formulation.

What operations are valid on a particular entity? Well, it depends on the
subjects that entity has associated. We have a set of them, and each one
has fields and methods associated. That suggests that perhaps an entity
should look sort of like a _record_ of sorts—in particular, a record in a
language with _row polymorphism_. I'm gonna come up with a code sample, and
then elaborate on which primitive operations we need:

    subject S of Int
    subject T of Bool

    f : {S,T,...} -> Int
    f e = get S i from e
              T b from e
          in if b then i else 0

    y : Int
    y = let x   = ε
            x'  = add S 3 to x
            x'' = add T True to x'
        in f x''

What's going on here? Well, we're declaring our _subjects_ up front, but
those are effectively labels for a record. We use those with the
`add ... to ...` operation, which acts like record update, and extract
them with `get ... from ... in ...`. I'm here using epsilon as the
_"empty" entity_ but that's more or less arbitrary.



XXX -- delete?

So let's start with the expression language. We'll start with a rough
simply-typed λ-calculus with products, sums, and a unit type, and then
add things one-by-one.

    e := (e, e) | inl e | inr e | unit | λx:t. e

So far, so good. The next thing we can do is create an _empty entity_,
which is an entity with no subjects associated with it.

    e := ... | ε

we can also _add a subject_ to an entity

    e := ... | add S e to e

and _access a subject's field_

    e := get S x from e in e

Instead of explaining what these operations do, I'll jump straight to a
chunk of code:

To begin with, we declare two different subjects, `S` (which requires an
argument of type `Int`) and `T` (which requires an argument of type
`Bool`). We then define a function `f`, which takes an entity, and
extracts from it the subject `S` with its associated value and the subject
`T` with its associated value, and then uses those values in rather
traditional functional code.

The definition of the value `y` is done by creating an intermediate
entity called `x`, then creating a new entity `x'` that is the same as
`x` but nevertheless able to be viewed as an `S` as well, and then
an entity `x''` which can be viewed as either an `S` or a `T`, and then
passes that to `f` (which requires an entity that can be seen as
both `S` and `T` simultaneously.) The final value of `y` is going to
be `3`.

This gives us a clue about how types will work in our calculus, as
well—an entity must have a type corresponding to the set of subjects it
implements. Consequently, we have the following types in the program:

    x   : {}
    x'  : {S}
    x'' : {S,T}
    y   : Int
    f   : {S,T} -> Int

This is of course a ridiculous toy program, but we can begin to see some
of the previous features of Subject-Oriented Programming peeking out at
us:

    subject HasPosition of Int * Int
    subject HasVelocity of Int * Int

    updateEntity : Ref {HasPosition,HasVelocity} -> ()
    updateEntity someRef =
      let e = !someRef in
        get HasPosition (x,y)   from e
            HasVelocity (dx,dy) from e in
          someRef := add HasPosition (x + dx, y + dy) to e

And so forth. A practical 


# The Mezzo Language

There's a functional language—an ML variant—being developed by Jonathan
Protzenko and François Pottier at INRIA. It's an interesting effort. You
can read about its motivations and capabilities elsewhere, but the most
interesting is the way it handles what it calls _permissions_. A _permission_
corresponds somewhat to what other languages call a _type_, but the semantics
are... different.

For example, in an ML-like language, I can write a function which takes a pair
of values of the same type and swaps them.

    fun swap r =
      let val (x, y) = !r in
        r := (y, x)
      end

This SML function has its type inferred as `('a * 'a) ref -> unit`, and after
it executes, whatever pair you've passed it will have had its elements
swapped. However, in SML, there is no way of doing this with pairs of type
`('a * 'b) ref`, because you can't _change_ the type of something that exists.
You would have to construct a new pair with a different type.

Mezzo is different. In Mezzo, you don't have types, you have _permissions_,
which you can understand as the permission to access a particular part of the
heap as a particular kind of data. As such, you are allowed to write a function

    val mswap: [a, b] (consumes x: mpair a b) -> (| x @ mpair b a)

This type is interpreted as _consuming_ the permission to access `x` as a mutable
pair of types `a` and `b`, and _producing_ the permission to access `x` as a mutable
pair of types `b` and `a`. To be concise, it swaps the elements of the mutable pair
_without allocating a new pair_ and _in a type-safe way_[^3]. There's a fair amount
of extra complexity I'm omitting, and I encourage the reader to read the relevant
blog posts, because there are a lot of interesting things going on there.

[^3]: Or a permission-safe way, anyway.