Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save dsferruzza/f53134b075d374a504f9 to your computer and use it in GitHub Desktop.
Save dsferruzza/f53134b075d374a504f9 to your computer and use it in GitHub Desktop.
Type-checking modular transformations of complex states

Type-checking modular transformations of complex states

Problem

Let's say we have a state, which can be represented as a kind of case class. So this state has named and typed properties:

case class State(prop1: String, prop2: Int)
```

Now we have an ordered list of functions from `State` to `State`, and we want to apply them on the initial state to get the final state.
Something like this:

```scala
val initialState: State = ???
val f1: State => State = ???
val f2: State => State = ???
val f = Seq(f1, f2)

val finalState: State = f.foldLeft(initialState)((st, func) => func(st))
```

This is nice, because:

- transformation functions are given a case class (representing the state), so accessing its properties from their implementation is easy
- transformation functions are checked by the compiler to ensure that:
	- they only access state's properties that exist
	- they use them in a way that type-checks
	- they return a new state that is valid
- state can be composed by properties of different types

But this is not optimal at all!
We would like to:

- change the state structure during transformations (add properties, mainly)
- avoid having to write `case class` to describe every transitional state
- write every transformation function independently of the others (so we can re-use them, assembled in different sequences of treatments)

The last item implies that we need a way to tell for each transformation functions (probably in their types) which kind of state they depend on.
Also, **how** they will change that state (probably in their return type). 


## Examples

Let's define 2 transformation functions:

- `f1` needs a state with a property `p1: Int`
- `f1` adds a new property `p2: String` in that state

and:

- `f2` needs a state with a property `p2: String`
- `f2` adds a new property `p3: (String, String)` in that state

### Example 1

- initial state is like `(p1: Int)`
- transformations: `Seq(f1, f2)`

**This is valid**

Final state will be like `(p1: Int, p2: String, p3: (String, String))`.

`f2` does not depends on a state having `p1: Int`, so `f2` will not be able to access that property.
But this property has been defined earlier (it was already in the state before it gets transformed by `f2`), so it will be kept unchanged.

*This let us with the issue of adding `p1: Int` from `f2`, i.e. collisions, but let's not care for now...*

### Example 2

- initial state is like `(p1: Int)`
- transformations: `Seq(f2, f1)` *(order has changed)*

**This is _not_ valid**

`f2` is not given a state with `p2: String`.

### Example 3

- initial state is like `(p1: Int, p4: Long)`
- transformations: `Seq(f1, f2)`

**This is valid**

Final state will be like `(p1: Int, p2: String, p3: (String, String), p4: Long)`.


## Thoughts

*Records* seem to bring some of the features we want, but don't match exactly with what I described.

I tried:

- Shapeless records: https://github.com/milessabin/shapeless
- Compossible: https://github.com/cvogt/compossible/ (which seems very promising, according to https://cdn.parleys.com/p/551a7c1ce4b0758c17004f24/ScalaRecordsSLIDES.pdf)

Also, I'm not sure we can avoid using macros (directly or via a library that uses them).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment