Add `entity` type, and identify entities by structural equality

[byorgey]

The problem

There are several open issues struggling with how to deal with entities when we need to be able to distinguish among entities that would otherwise be considered identical.

• Getting a reference to a specific entity #114 wonders about how to manage things like boxes with things put inside them: once we can start putting things in boxes, it matters a lot which box we are referring to. For example, we want to be able to say things like "take one of my 50 box entities, put a bunch of things in it, and now give that specific box to another robot".
• Use typewriter device for reifying values as entities #116 wonders about how to distinguish among different paper entities that have had values printed on them.

I'm sure other, similar situations will arise as we continue designing more interesting entities and commands.

In general, we have considered entities to be uniquely identified by their name. However, this causes a lot of problems.

• Entities aren't actually uniquely identified or stored by name, but rather by hash value. I think there are multiple places in the code where we look up an entity by name and just assume that we will get only one, even though in theory there could be multiple.
• Changing the name of an entity to make it unique is problematic. Consider the example of a box again. Getting a reference to a specific entity #114 suggests taking a box entity and changing its name to something unique (e.g. box1425) so that we can now refer to it uniquely. The problem is that we now no longer know that it is a box! As in, we might want to say something like "give every box in my inventory to base", but we can't: the box1425 is no longer a box, it is now a box1425.
• Moreover, representing entities as string values is error prone and not type-safe: e.g. give base "treee" only fails at runtime.

Proposed solution concept

The germ of this idea came from @noahyor . #393 noticed that principles of object-oriented programming were helpful in thinking about the way robots interact; the same thing is true here. The key components of the solution are:

• Make a new type entity representing descriptions of entities; entities can only be distinguished up to structural equality.
• Formally distinguish between the class of an entity (represented by a string such as box) and its identity (represented internally by its hash, and in the external language as a value of type entity).

For efficiency, we can still have multiple identical entities represented simply by a count (for example, if we have harvested 1257 trees, we do not need to give each one a separate, unique identity! --- we just have 1257 copies of the generic tree entity). But we can also have multiple entities with distinct identities but the same class. This makes the box and paper examples above work cleanly. For example, we can refer to a specific box by its unique identity, but it is still a box, so we can do things like "give all boxes" even if some of them have distinct identities.

Equivalence of entities and semantics of entity

In OOP terms, if we imagine each individual entity (e.g. every single individual tree) to be an object, there are three equivalence relations on entities we might potentially care about.

• Reference equality would distinguish entities up to some sort of unique id/reference/memory location. i.e. if you have 529 trees in your inventory, every single one would be not reference-equal to the others.
• Structural equality distinguishes entities only up to their contents/attributes. The 529 trees in your inventory are all structurally equal, but an empty box and a box containing a few other items would not be structurally equal.
• Class equality distinguishes entities only up to their class/name. For example, the two boxes in the previous example would be class-equal, but a box would never be class-equal to a tree.

In light of these categories, I propose:

• Values of type entity will represent entity descriptions, that is, equivalence classes of entities up to structural equality.
  • A value of type entity can therefore be represented internally by an entity hash value. (Yes, technically, this is not sound since there could be a hash collision for entities that are not structurally equal, but such a collision is extremely improbable.)
  • In particular a value of type entity does not represent a "reference" to a specific entity (unlike, say, values of type robot).
  • This is an important feature, not just an optimization, because it should be possible to talk about entities that you don't have. More examples of this later.
• Therefore, the language should not / cannot allow you to distinguish entities up to reference equality, only up to structural equality. Put another way, any two entities with exactly the same attributes are always completely interchangeable. Put yet another way, reference equality is not even a thing in Swarm. I only mentioned it above to have a reference point (haha) for discussion.

Proposed solution details

• Make a new opaque entity type, similar to what we did with robots in Use a new opaque type for robots instead of strings #303 .
  • Internally, an entity value can be stored as an Int, the entity hash value we already compute.
  • entity values must be immutable, since changing an attribute of an entity changes its hash value and thus its identity.
  • Some built-in functions will change type as well. For example, give : robot -> entity -> cmd (), place : entity -> cmd (), and grab : cmd entity.
  • make and create, on the other hand, should probably not change type; more on this below.
• The entityMap (and entities.yaml) should now be thought of as storing a prototype Entity object corresponding to each entity class name.
• There should be a function like entity : string -> entity (alternative name: proto?) which does a lookup in the entity map, i.e. returns the prototype entity associated with a particular class name.
  • Presumably it throws an exception if there is no class with the given name.
  • So e.g. if we want to give the base one of our generic trees we can say give base (entity "tree").
    • This is slightly annoying but of course everyone is free to define their own def give' = \r. \c. give r (entity c) end.
    • Of course one can also thing <- grab; give base thing just like before.
  • But if we have a variable b : entity representing, say, a special, specific box with some things put in it, we can also say give base b.
• Note that we could still have make : string -> cmd () rather than make : entity -> cmd (), since it only ever makes sense for make to produce a prototype entity of a given class.
• There should also be a function class : entity -> string.
• If you have a specific e : entity and you want to make another one of it, you can of course say make (class e).
• Suppose you want to put a tree into a box and give it to base.
  • You can do that simply with a function insert : entity -> entity -> cmd entity, like so
    • treeBox <- insert (entity "tree") (entity "box"); give base treeBox.
    • This will actually remove tree and box entities from your inventory, add a new entity to your inventory representing the box with a tree in it, and return the hash value of that new entity. (The fact that it mutates your inventory is why it has to be in the cmd monad.)
    • If you execute insert (entity "tree") (entity "box") twice, you will now have two identical (i.e. structurally equal) entities in your inventory.
  • This is how we can solve the problems posed in Getting a reference to a specific entity #114 and Use typewriter device for reifying values as entities #116 .
  • A previous version of this description mentioned a function getUnique : string -> cmd entity which would take one of the prototype entities of the given class and make it into a new, unique entity. However, getUnique is not necessary; in retrospect I was confused about the semantics of entity and the difference between structural and reference equality.
  • Likewise, a previous version mentioned an inverse to getUnique like makeGeneric to turn an entity back into a prototype entity; this is also unnecessary. The example given previously was turning a unique box back into a generic box after removing some items from it. But after removing items from the box, it will now be structurally equal to a prototype box, hence nothing additional needs to be done.
• In addition to only producing prototype entities, make will also only use prototype entities for ingredients.
  • For example, if you put some items in a box, then make "drill" will never use that box to build the drill.
  • In other words, make will pick its ingredients up to structural equality with prototype entities, not up to class equality.
• As mentioned previously, the fact that entity values represent entity descriptions, not entity references, makes it possible to talk about entities you don't have in your inventory.
  • For example, imagine the operation of changing an entity's color.
  • There could be a function painted : color -> entity -> entity. This is a pure function that operates on entity descriptions. For example, painted blue (entity "tree") describes an entity which is the same as a generic prototype tree except that it is blue. It does not matter whether you have any trees or any blue trees in your inventory.
  • You can therefore say something like until (ishere (painted blue (entity "tree"))) { move }, to move until you encounter a blue tree.
  • But what if you have a tree in your inventory, and you actually want to paint it blue? There should be another built-in function like transform : entity -> (entity -> entity) -> cmd entity (or maybe apply, or applyTo?) for taking an entity transformation function and actually applying it to an entity in your inventory. In other words, transform e f will (1) look for an entity structurally equal to e in your inventory (and throw an exception if none is found), (2) remove one copy of that entity; (3) insert one copy of f e into your inventory; (4) return the value of f e.
  • Hmm, there is actually something strange going on here. If we have a pure function inserted : entity -> entity -> entity (as we should, in order to describe entities containing other entities), we could use that together with the proposed transform function to materialize entities out of thin air: transform (entity "box") (inserted (entity "tree")). So we will have to think more carefully about this. Maybe having a generic transform function is not really safe after all, and we just need two versions of each transformation, one pure and one that mutates the inventory (painted vs paint, inserted vs insert, etc.)?
  • Containers #115 (comment) suggests going the other way: provide only mutation operations (like paint, insert, etc.) in the cmd monad, but also provide a function hypothetical : cmd entity -> entity which performs a command in a hypothetical, infinite/creative inventory and returns a description of the resulting entity. So we could say let blueTree = hypothetical (paint blue (entity "tree")) in ...
• Note that give base (entity "box") will only ever give prototype boxes. So how can we do something like "give the base all the entities with class box"? A few thoughts:
  • The simplest idea is to have a function like getAny : string -> cmd entity which returns a reference to any entity of the given class in your inventory, as opposed to entity which specifically only returns a prototype entity.
  • Likewise there should probably be has : entity -> cmd bool vs hasAny : string -> cmd bool and count : entity -> cmd bool vs countAny : string -> cmd bool.
    • Very open to bikeshedding on these and other names. 😄
  • Hence we could write something like

    while (hasAny "box") { e <- getAny "box"; give base e }
    

  • I am leaving the above since getAny etc. are definitely useful. However, getAny doesn't really solve the problem. It only works in the above example since we immediately get rid of each item returned by getAny. But in general, what if you want to do something with each box but not get rid of them? What if you want to give only some of them to the base (e.g. non-empty ones)?
  • What we really want is something like withAll : string -> (entity -> int -> b -> Cmd b) -> b -> Cmd b which will fold over all entities of the given class.
    • It must be in the Cmd monad since which entities get folded over depends on the state of your inventory at a specific time.
  • Note how we can use withAll to implement hasAny and countAny.

Remaining questions

• How does this interact with the inventory list in the UI?
  • For example, if we have 50 boxes and then insert a tree into one of them, should the inventory list still simply display 50 boxes? Or should it now show 49 boxes and one of something else?
  • In other words, does the inventory list entities up to class equality or structural equality?
  • Perhaps we could have the best of both worlds: by default it lists things up to class equality, but there is a way to e.g. "expand" an entry to show all the unique entity values of that class?
  • Relatedly, the UI should be able to show more information about an entity than just its description and display, e.g. its inventory.
• If another robot gives you an entity, especially a non-prototype one, how do you find out about it? How do you get an entity value corresponding to the thing you just got?
  • One thing I could imagine is a function receive : cmd entity which you have to execute in order to "give permission" to another robot to give you something, which would also give you a corresponding entity value.
    • This might be super annoying, especially if it is blocking. You'd like to be able to go about some other business while also being given items. Even if we made it non-blocking somehow (but then it would have to have a type like cmd (() + entity)?) it would still be annoying. e.g. imagine if the base had to execute receive every time it sent a robot out to fetch something.
  • Another idea might be to have some sort of "receive queue", where entities you are given go into the queue, and executing something like receive gives you the next thing from the queue. This at least makes give non-blocking, and means you could simply never execute receive if you didn't care. But there is still the issue of whether receive itself should be blocking or not.
  • A simpler idea might just be to do nothing, i.e. let players use various other mechanisms to program their own solutions to the problem.
    • If you are expecting the entity given to you, then of course you can just refer to it yourself.
    • The robot giving the entity could communicate its description to you in some other way (Inter-robot communication #94).
    • Or you could iterate over your entire inventory and look for things you don't recognize.
• Relatedly, how are non-prototype entities displayed in the inventory list, and how can you refer to them, especially if you did not explicitly create them in such a way that you got an entity value corresponding to them (or if you just forgot to bind the result to a variable)?
  • Related: "Robot registry" allowing access to built/known robots by index #462

[xsebek]

I like the detailed proposal 👍

Would it be possible to have automatic conversion like Haskell fromIntegral that would convert string to entity where necessary?
Not sure if we want that, but it would be less to write.

I like the expandable item idea. Grouping items sounds useful on its own, so I may write an Issue for it. 😁

[byorgey]

Would it be possible to have automatic conversion like Haskell fromIntegral that would convert string to entity where necessary?

Short answer: no!

Long answer: great question! There are two ways I can think to achieve that, but both would be a big change to the type system:

• We could add subtyping, i.e. string could be a subtype of entity, so you can use a string value anywhere an entity value is expected. This would be sensible and convenient. However, from a theoretical and practical point of view, adding subtyping always makes type systems much more complicated.
• The way Haskell achieves it is with qualified polymorphism (i.e. type classes), so in particular e.g. a literal string value would not have type string but something like Stringy a => a.

Either of these by themselves wouldn't be too bad --- I have implemented type systems with both features before. However, the thing is that in #231 we are already contemplating a pretty complex effect typing system to handle capabilities properly. If we're going to make the type system more complex, I think capabilities are the more important and relevant thing to handle. And if we tried to combine the system being contemplated in #231 with either subtyping or qualified polymorphism, I think my brain would simply explode. 🤯