TheSeamau5/makingElmDynamicSafely.md

## makingElmDynamicSafely.md

      
    Raw
  

              makingElmDynamicSafely.md
            
          
    Making Elm more Dynamic safely

The goal of this piece is to explore ways to give Elm some of the awesome features of dynamic languages while not sacrificing Elm's safety. The following ideas have come from exploring entity component systems/plugin architectures and noticing some of Elm's "limitations" to represent some of these ideas.
NOTE: I am by no means an expert in type systems, compiler, programming languages, or actually programming in general. These are simply ideas I have been playing around with in recent weeks and wished to share with the Elm community. The hope is not that my ideas be adopted or pushed for or whatever. The goal is simply to improve the Elm language/platform by exploring possibilities to enhance the language in such a way as to not break any of its current guarantees or void any of its current advantages. The following is an exploration on how to make Elm's type system more "dynamic" in the sense that the inputs may be of unknown type while keeping the static nature of the language and all the benefits and guarantees associated with strong static typing.
Example : Entity Component System

Entity Component System is an architectural pattern which is very common in game programming and can be useful in other settings. It is the pattern that enables plugins in almost anything (browsers, IDEs, etc..).
It is usually defined somewhat as follows:

An entity is an object with a list of components (and occasionally a unique identifier)
A component is a piece of raw data (position, velocity, mass, destructible, etc... are all examples of components)
The system applies actions on every single entity given that the action may be performed on an entity (actions in this case are just functions)

Example (in Elm-like pseudo-code) :
-- ENTITIES
-- Each entity has a number of (possibly different) components
mario = {
  position = {x = 0, y = 0},
  velocity = {x = 0, y = 0},
  mass = 20,
  life = True,
  controllability = True,
  groundedness = True
}

goomba = {
  position = {x = 20, y = 0},
  velocity = {x = -1, y = 0},
  mass = 20,
  life = True,
  groundedness = True
}

lakituCloud = {
  position = {x = 0, y = 100},
  velocity = {x = -2, y = 0},
  life = True,
  flying = True
}

block = {
  position = {x = 0, y = 0},
  destructibility = True
}

-- ACTIONS
move entity =
  { entity | position <- position + velocity }

applyGravity force entity =
  { entity | velocity <- velocity + force / mass }

update = move << applyGravity { x = 0, y = -9.81 }

-- SYSTEM

-- The list of all entities in the system
entities = [mario, goomba, lakituCloud, block]

-- The list of all entities after one update
-- mario and goomba have been affected by gravity
-- mario, goomba, and lakituCloud have moved
updatedEntities = map update entities

In this example, mario, goomba, lakituCloud, and block are all entities in the system and move and applyGravity are the actions in the system.
move and applyGravity are applied on every entity to return updated versions of those entities (or each entity at the next "timestep").
But note that not all entities are affected by the move or applyGravity actions.
The advantage of this architecture is that one can add arbitrarily many entities to the system with arbitrarily many and distinct components and the current system will not break and just take them into account. This architecture allows for lego-like modularity. The only requirement is that each action be applied only to entities that contain the required components. For example, move should not actually be applied to block as block does not have a velocity component.
From this example, we can see that in order to fully achieve this architecture, we need several abilities:


The ability to have a collection of entities of distinct type. While one can a-priori model all components currently in a system, it is necessary to have heterogeneous collections in order to allow the code to be easily extendable and take into account future components not currently modeled in the system.


The ability to "dynamically" conditionally apply an action based on the components of an entity.


The following is a set of features that may potentially solve these issues while not compromising the safety of Elm.
Meta Annotations

We are all probably familiar with type annotations to annotate functions and values:
pi : Float
addVectors : Vector -> Vector -> Vector
Now, what if you could annotate the type annotations?
require {x : Float, y : Float} from vector
addVectors : vector -> vector -> vector
In here, the require meta annotation would require the "loose" type vector to have an x and y field both Float
This would be exactly equivalent to the following statement:
addVectors : {a | x : Float, y : Float} -> {a | x : Float, y : Float} -> {a | x : Float, y : Float}
This sounds like a pretty useless feature to have. Sure, the syntax is a bit more compact but, really, what does this allow?
Well, it allows us to introduce different meta annotations.
Meet the optional meta annotation:
optional {z : Float} from vector
This meta annotation says that the "loose" type vector may optionally have a z field of type Float.
The optional meta annotation can allow us to define functions that are usable on
several types without having to introduce typeclasses or splitting the function
into multiple functions.
So, if we take our addVectors example:
optional {z : Float} from vector
required {x : Float, y : Float} from vector
addVectors : vector -> vector -> vector
This means that our addVectors function can work on 2D vectors as well as 3D vectors.
Now, how do we implement this function? We would need a way to check if the input
vectors actually have a z field...
To do so, meet the has function:
v = {x = 0, y = 0}

has {z : Float } v == False
has {x : Float } v == True
has {x : String} v == False
The has function is a special built-in magical function that takes a field-type as its
first argument and some object as the second argument and says if the object has the given
field.
One can imagine the type of has to be something like:
has : Type -> a -> Bool
Now, we have all the tools necessary to implement our addVectors function:
optional {z : Float} from vector
required {x : Float, y : Float} from vector
addVectors : vector -> vector -> vector
addVectors p q =
  if has {z : Float} p
  then
    { p | x <- p.x + q.x, y <- p.y + q.y, z <- p.z + q.z }
  else
    { p | x <- p.x + q.x, y <- p.y + q.y }
addVectors can now add 2d vectors or 3d vectors together
p2 = {x = 0, y = 1}
q2 = {x = 3, y = 4}

p3 = {x = 1, y = 2, z = 4}
q3 = {x = 2, y = 2, z = 1}

r2 = addVectors p2 q2 -- {x = 2, y = 5}
r3 = addVectors p3 q3 -- {x = 3, y = 4, z = 5}

bad = addVectors p2 q3 -- Compile-time error!
The reason that bad causes a compile-time error is due to the type annotation
addVectors : vector -> vector -> vector
As you can see, the type of both operands is assumed to be the same.
If you wish to add 2D and 3D vectors, you would need to change addVectors to
optional {z : Float} from vectorA, vectorB, vectorC
required {x : Float, y : Float} from vectorA, vectorB, vectorC
addVectors : vectorA -> vectorB -> vectorC
addVectors p q =
  case (has {z : Float} p, has {z : Float} q) of
    (True, True)   -> { p | x <- p.x + q.x, y <- p.y + q.y, z <- p.z + q.z }
    (True, False)  -> { p | x <- p.x + q.x, y <- p.y + q.y }
    (False, True)  -> { q | x <- p.x + q.x, y <- p.y + q.y }
    (False, False) -> { p | x <- p.x + q.x, y <- p.y + q.y }
In this case, the addVectors function will return a 3d vector if either vector is a 3d vector.
This is done by saying that vectorA, vectorB, vectorC are all distinct types, and that each may optionally have a {z : Float} field.
Furthermore, we may also imagine adding yet another meta annotation called prohibit.
prohibit does what you think it does:
prohibit {z : Float} from vector
addZ : vector -> vector3
addZ v = { v | z = 0 }
The addZ function in this case will add a {z : Float} field to its input. By adding
the meta-annotation, we have guaranteed that the input object does not contain a {z : Float} field. This slightly turns the traditional way of specifying types on its head by also specifying the type of values an input should NOT have.
Now that we have these meta annotations and the has function, how do we do heterogeneous collections?
Simple:
require {x : Float} from vector
list : List vector
list = [{x = 0}, {x = 1, y = 3}, {x = 9, z = 1}]
So, as you can see, the list contains objects of different type but the require meta annotation means that each element in list must have an {x : Float} field.
This means that the following would yield a compile-time error:
{z = 3} :: list -- compile-time error
So, we've gained flexibility and have conserved safety!
If you want a truly heterogeneous collection, you can do the following:
require {} from vector
list : List vector
list = [{x = 0}, {z = 1}, {x = 2, y = 3}]
This would make sure that nothing is required from the vector type.
Note: Currently, it is unclear how List would be implemented to fit heterogeneous list
or if List would need modifying in any way. This may be solved by introducing a forall statement.
Furthermore, note that the preceeding does not void the current semantics of Elm and is purely additive.
add p q = {p | x <- p.x + q.x, y <- p.y + q.y}
should continue to have type:
add : {a | x : Float, y : Float} -> {b | x : Float, y : Float} -> {a | x : Float, y : Float}
At worst, the compiler may conclude the following equivalent type:
require {x : Float, y : Float} from t1, t2
add : t1 -> t2 -> t1
So, now that we've introduced meta-annotations and the has function, how would our entity component system look like?
mario = {
  position = {x = 0, y = 0},
  velocity = {x = 0, y = 0},
  mass = 20,
  life = True,
  controllability = True,
  groundedness = True
}

goomba = {
  position = {x = 20, y = 0},
  velocity = {x = -1, y = 0},
  mass = 20,
  life = True,
  groundedness = True
}

lakituCloud = {
  position = {x = 0, y = 100},
  velocity = {x = -2, y = 0},
  life = True,
  flying = True
}

block = {
  position = {x = 0, y = 0},
  destructibility = True
}

optional {position: {x : Float, y : Float}, velocity : {x : Float, y : Float}} from entity
move : entity -> entity
move entity =
  if (has {position : {x : Float, y : Float}, velocity : {x : Float, y : Float}}) entity
  then
    { entity | position.x <- entity.position.x + entity.velocity.x,
               position.y <- entity.position.y + entity.velocity.y}
  else
    entity

require {x : Float, y : Float} from force
optional {mass : Float, velocity : {x : Float, y : Float}} from entity
applyGravity : force -> entity -> entity
applyGravity force entity =
  if has {mass : Float, velocity : {x : Float, y : Float}} entity
  then
    { entity | velocity.x <- entity.velocity.x + force.x / entity.mass,
               velocity.y <- entity.velocity.y + force.y / entity.mass }
  else
    entity


update = move << applyGravity { x = 0, y = -9.81 }


require {} from entity
entities : List entity
entities = [mario, goomba, lakituCloud, block]

require {} from entity
updatedEntities : List entity
updatedEntities = map update entities
As you can see, the above code is almost the same than the earlier pseudo-code. The difference lies in the inclusion of meta-annotations and the inner checks. Without any annotations, this code becomes:
mario = {
  position = {x = 0, y = 0},
  velocity = {x = 0, y = 0},
  mass = 20,
  life = True,
  controllability = True,
  groundedness = True
}

goomba = {
  position = {x = 20, y = 0},
  velocity = {x = -1, y = 0},
  mass = 20,
  life = True,
  groundedness = True
}

lakituCloud = {
  position = {x = 0, y = 100},
  velocity = {x = -2, y = 0},
  life = True,
  flying = True
}

block = {
  position = {x = 0, y = 0},
  destructibility = True
}

move entity =
  if (has {position : {x : Float, y : Float}, velocity : {x : Float, y : Float}}) entity
  then
    { entity | position.x <- entity.position.x + entity.velocity.x,
               position.y <- entity.position.y + entity.velocity.y}
  else
    entity


applyGravity force entity =
  if has {mass : Float, velocity : {x : Float, y : Float}} entity
  then
    { entity | velocity.x <- entity.velocity.x + force.x / entity.mass,
               velocity.y <- entity.velocity.y + force.y / entity.mass }
  else
    entity


update = move << applyGravity { x = 0, y = -9.81 }

entities = [mario, goomba, lakituCloud, block]

updatedEntities = map update entities
Further explorations

Notice that in the objects, we have these flags that are set to True. These flags are redundant because we actually run code based on the presence or absence of these flags, not on whether or not they are True or False.
With heterogeneous collections and the has functions, it is possible to introduce to concept of one-time tags (or singleton data types, or symbols) and singleton fields in records.
The idea is simple and is best exemplified by rewriting the mario object:
mario = {
  position = {x = 0, y = 0},
  velocity = {x = 0, y = 0},
  mass = 20,
  Life,
  Groundedness,
  Controllability
}
In this, mario has 3 singleton fields: Life, Groundedness, and Controllability.
Each field is of its own type created on the spot. They are equivalent in type to the following types:
type Life = Life
type Groundedness = Groundedness
type Controllability = Controllability
But there is no need to actually write the following, the compiler/code generator/desugarer would do that automatically.
The singleton types may not be useful, but if we add the ability for singleton fields (fields who do not need to be explicitly set to some value), we get a concise way of adding and removing tags or flags to entities without having to awkwardly set it to some default dummy value or have to manually create dummy types.
Therefore, we can easily express the function to check if an entity is "alive":
isAlive entity =
  if has {Life} entity
  then True
  else False
or more compactly:
isAlive = has {Life}
This allows to follow simplify our example to :
mario = {
  position = {x = 0, y = 0},
  velocity = {x = 0, y = 0},
  mass = 20,
  Life,
  Controllability,
  Groundedness
}

goomba = {
  position = {x = 20, y = 0},
  velocity = {x = -1, y = 0},
  mass = 20,
  Life,
  Groundedness
}

lakituCloud = {
  position = {x = 0, y = 100},
  velocity = {x = -2, y = 0},
  Life,
  Flying
}

block = {
  position = {x = 0, y = 0},
  Destructibility
}

move entity =
  if (has {position : {x : Float, y : Float}, velocity : {x : Float, y : Float}}) entity
  then
    { entity | position.x <- entity.position.x + entity.velocity.x,
               position.y <- entity.position.y + entity.velocity.y}
  else
    entity


applyGravity force entity =
  if has {mass : Float, velocity : {x : Float, y : Float}} entity
  then
    { entity | velocity.x <- entity.velocity.x + force.x / entity.mass,
               velocity.y <- entity.velocity.y + force.y / entity.mass }
  else
    entity


update = move << applyGravity { x = 0, y = -9.81 }

entities = [mario, goomba, lakituCloud, block]

updatedEntities = map update entities
As you can see, this representation is very minimalistic and by adding very few features, it is possible to achieve a result that is more flexible while retaining safety.
Unfortunately, there are numerous kinds of systems that are very hard to represent with static typing and one must go through incredible hoops to satisfy the compiler. This leads to code that is difficult to maintain and difficult to extend. Hopefully, this proposal will open up further discussions and bring forth more ideas on how to add flexibility to Elm safely and simply.