Introduction to data modeling

# Introduction to data modeling

[Nicolas Rinaudo] • [@NicolasRinaudo@functional.cafe]

---

# A simple DSL

---

## Addition

```scala
1 + 2
```

???

The simplest expression we want to support: addition.

---

## Addition

```scala
1 `+` 2
```

---

## Addition

```scala
`1` + `2`
```

---

## Addition

```scala
1 `+` 2
```
---

## Addition

```scala
1 `+` 2
```

---

## Addition

```scala
`1` + 2
```

---

## Addition

```scala
1 + `2`
```

---

## Addition

```scala
1 + 2
```

---

## Addition

```scala
1 + 2
```

*`new `Add(1, 2)
```
]

---

## Addition

```scala
1 + 2
```

```scala
class Add(lhs: Int, rhs: Int)

Add(1, 2)
```

---

## Addition

```scala
1 + (2 + 3)
```

```scala
class Add(lhs: Int, rhs: Int)
```

---

## Addition

```scala
1 `+` (2 + 3)
```

---

## Addition

```scala
`1` + (2 + 3)
```

*Add(`???`, ???)
```
]

---

## Addition

```scala
`1` + (2 + 3)
```

*Add(`1`, ???)
```
]

---

## Addition

```scala
1 + `(2 + 3)`
```

*Add(1, `???`)
```
]

---

## Addition

```scala
1 + `(2 + 3)`
```

*Add(1, `Add(2, 3)`)
```
]

---

## Addition

```scala
1 + (2 + 3)
```

```scala
class Add(lhs: Int, rhs: Int)

Add(1, `Add(2, 3)`)
```

---

## Addition

```scala
1 + (2 + 3)
```

```scala
class Add(lhs: Int, `rhs: Int`)

Add(1, Add(2, 3))
```

---

## Addition

```scala
1 + (2 + 3)
```

```scala
class Add(lhs: Int, rhs: Int)

Add(1, Add(2, 3))
// ⛔ Found:    Add
//   Required: Int
```

---

## Subtyping

---

## Subtyping

```scala
def foo(a: `A`) = ???

foo(`new A`)
```

---

## Subtyping

```scala
def foo(a: A) = ???

foo(new A)
```

---

## Subtyping

```scala
def foo(a: A) = ???

foo(new A)
```

---

## Subtyping

*foo(new `A`)
```
]

---

## Subtyping

*foo(new `B`)
```
]

---

## Subtyping

```scala
def foo(a: `A`) = ???

foo(new B)
```
---

## Subtyping

```scala
def foo(a: A) = ???

foo(new B)
```

---

## Subtyping

```scala
def foo(a: A) = ???

foo(new B)
```

---

## Subtyping

foo(new B)
*`foo(new C)`
```
]

---

## Subtyping

```scala
def foo(a: A) = ???

foo(new `B`)
foo(new `C`)
```

---

## Subtyping

```scala
def foo(a: `A`) = ???

foo(new B)
foo(new C)
```

---

## Subtyping

*foo(new `B`)
foo(new C)
```
]

---

## Subtyping

*foo(new `Add`)
foo(new C)
```
]

---

## Subtyping

foo(new Add)
*foo(new `C`)
```
]

---

## Subtyping

foo(new Add)
*foo(new `Int`)
```
]

---

## Subtyping

```scala
class Add(lhs: `Int`, rhs: `Int`)
```

---

## Subtyping

```scala
class Add(lhs: Int, rhs: Int)
```

---

## Subtyping

---

## Subtyping

---

## Subtyping

```scala
class Exp
class Add(lhs: Int, rhs: Int) extends Exp
```

---

## Subtyping

.diff-add[
```scala
class Exp
class Add(lhs: Int, rhs: Int) extends Exp
*`class Num(value: Int) extends Exp`
```
]

---

## Subtyping

.diff-rm[
```scala
class Exp
*class Add(lhs: `Int`, rhs: `Int`) extends Exp
class Num(value: Int) extends Exp
```
]

---

## Subtyping

.diff-add[
```scala
class Exp
*class Add(lhs: `Exp`, rhs: `Exp`) extends Exp
class Num(value: Int) extends Exp
```
]

---

## Subtyping

```scala
1 + (2 + 3)
```

```scala
Add(1, Add(2, 3))
```

---

## Subtyping

```scala
1 + (2 + 3)
```

---

## Subtyping

```scala
1 + (2 + 3)
```

---

## Equality

```scala
1 = 2
```

---

## Equality

```scala
1 `=` 2
```

---

## Equality

```scala
`1` = `2`
```

---

## Equality

```scala
1 `=` 2
```

---

## Equality

```scala
1 `=` 2
```

---

## Equality

```scala
`1` = 2
```

```scala
class Eq()
```

---

## Equality

```scala
`1` = 2
```

---

## Equality

```scala
1 = `2`
```

```scala
class Eq(lhs: Exp)
```

---

## Equality

```scala
1 = `2`
```

---

## Equality

```scala
1 = 2
```

---

## Equality

```scala
(1 + 2) = (2 + 1)
```

---

## Equality

```scala
(1 + 2) `=` (2 + 1)
```

---

## Equality

```scala
`(1 + 2)` = (2 + 1)
```

---

## Equality

```scala
`(1 + 2)` = (2 + 1)
```

---

## Equality

```scala
(1 + 2) = `(2 + 1)`
```

---

## Equality

```scala
(1 + 2) = `(2 + 1)`
```

---

## Pretty printing

```scala
(1 + 2) = (2 + 1)
```

```scala
Eq(
  Add(Num(1), Num(2)),
  Add(Num(2), Num(1))
)
```

---

## Pretty printing

```scala
(1 + 2) = (2 + 1)
```

---

## Pretty printing

```scala
Eq(
  Add(Num(1), Num(2)),
  Add(Num(2), Num(1))
).toString
// val res2: String = Eq@79d4ff58
```

---

## Pretty printing

```scala
class Exp
```

---

## Pretty printing

---

## Pretty printing

---

## Pretty printing

```scala
class Num(value: Int) extends Exp

class Add(lhs: Exp, rhs: Exp) extends Exp

class Eq(lhs: Exp, rhs: Exp) extends Exp
```

---

## Pretty printing

*class Add(lhs: Exp, rhs: Exp) extends Exp`:`
* `override def toString = ???`

*class Eq(lhs: Exp, rhs: Exp) extends Exp`:`
* `override def toString = ???`
```
]

---

## Pretty printing

class Add(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = ???

class Eq(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = ???
```
]

---

## Pretty printing

class Add(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = ???

class Eq(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = ???
```
]

---

## Pretty printing

class Add(lhs: Exp, rhs: Exp) extends Exp:
* override def toString = `???`

class Eq(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = ???
```
]

---

## Pretty printing

class Add(lhs: Exp, rhs: Exp) extends Exp:
* override def toString = `s"($lhs + $rhs)"`

class Eq(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = ???
```
]

---

## Pretty printing

class Add(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs + $rhs)"

class Eq(lhs: Exp, rhs: Exp) extends Exp:
* override def toString = `???`
```
]

---

## Pretty printing

class Add(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs + $rhs)"

class Eq(lhs: Exp, rhs: Exp) extends Exp:
* override def toString = `s"($lhs = $rhs)"`
```
]

---

## Pretty printing

```scala
(1 + 2) = (2 + 1)
```

```scala
Eq(
  Add(Num(1), Num(2)),
  Add(Num(2), Num(1))
).toString
```

---

## Pretty printing

```scala
(1 + 2) = (2 + 1)
```

```scala
Eq(
  Add(Num(1), Num(2)),
  Add(Num(2), Num(1))
).toString
// val res3: String = ((1 + 2) = (2 + 1))
```

---

## Type checking

---

## Type checking

---

## Type checking

```scala
(1 = 2) + (2 + 1)
```

```scala
Add(
  Eq(Num(1), Num(2)),
  Add(Num(2), Num(1))
).toString
// val res4: String = ((1 = 2) + (2 + 1))
```

---

## Type checking

```scala
(1 = 2) + (2 + 1)
```

```scala
`Add`(
  Eq(Num(1), Num(2)),
  Add(Num(2), Num(1))
).toString
```

---

## Type checking

```scala
(1 = 2) + (2 + 1)
```

```scala
Add(
  `Eq`(Num(1), Num(2)),
  `Add`(Num(2), Num(1))
).toString
```

---

## Type checking

```scala
abstract class Exp:
  def toString: String

class Num(value: Int) extends Exp:
  override def toString = value.toString

class `Add`(`lhs: Exp`, `rhs: Exp`) extends Exp:
  override def toString = s"($lhs + $rhs)"

class Eq(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs = $rhs)"
```

---

## Type checking

```scala
abstract class Exp:
  def toString: String

class `Num`(value: Int) extends Exp:
  override def toString = value.toString

class Add(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs + $rhs)"

class Eq(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs = $rhs)"
```

---

## Type checking

```scala
abstract class Exp:
  def toString: String

class Num(value: Int) extends Exp:
  override def toString = value.toString

class Add(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs + $rhs)"

class `Eq`(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs = $rhs)"
```

---

## Type checking

class Num(value: Int) extends Exp:
  override def toString = value.toString

class Add(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs + $rhs)"

class Eq(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs = $rhs)"
```
]

---

## Type checking

*class Num(value: Int) extends Exp`[Int]`:
  override def toString = value.toString

class Add(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs + $rhs)"

class Eq(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs = $rhs)"
```
]

---

## Type checking

class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString

*class Add(lhs: Exp, rhs: Exp) extends Exp`[Int]`:
  override def toString = s"($lhs + $rhs)"

class Eq(lhs: Exp, rhs: Exp) extends Exp:
  override def toString = s"($lhs = $rhs)"
```
]

---

## Type checking

class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString

class Add(lhs: Exp, rhs: Exp) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"

*class Eq(lhs: Exp, rhs: Exp) extends Exp`[Boolean]`:
  override def toString = s"($lhs = $rhs)"
```
]

---

## Type checking

class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString

*class Add(lhs: Exp`[Int]`, rhs: Exp`[Int]`) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"

class Eq(lhs: Exp, rhs: Exp) extends Exp[Boolean]:
  override def toString = s"($lhs = $rhs)"
```
]

---

## Type checking

class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"

*class Eq(lhs: Exp`[Int]`, rhs: Exp`[Int]`) extends Exp[Boolean]:
  override def toString = s"($lhs = $rhs)"
```
]

---

## Type checking

```scala
(1 = 2) + (2 + 1)
```

```scala
Add(
  Eq(Num(1), Num(2)),
  Add(Num(2), Num(1))
).toString
```

---

## Type checking

```scala
`(1 = 2)` + (2 + 1)
```

```scala
Add(
  Eq(Num(1), Num(2)),
  Add(Num(2), Num(1))
).toString
// ⛔ Found:    Exp[Boolean]
//   Required: Exp[Int]
```

---

## Key takeaways

Feature              || OOP
---------------------||--------------------
 Terms               ||  
 Interpreters        ||  
 Illegal states      || .hidden[impossible]

---

## Key takeaways

Feature              || OOP
---------------------||--------------------
 Terms               || classes
 Interpreters        ||  
 Illegal states      || .hidden[impossible]

---

## Key takeaways

Feature              || OOP
---------------------||--------------------
 Terms               || classes
 Interpreters        || methods
 Illegal states      || .hidden[impossible]

---

## Key takeaways

Feature              || OOP
---------------------||--------------------
 Terms               || classes
 Interpreters        || methods
 Illegal states      || impossible

---

# Growing the language

---

## Adding terms: subtraction

```scala
2 - 1
```

---

## Adding terms: subtraction

```scala
2 `-` 1
```

---

## Adding terms: subtraction

```scala
`2` - `1`
```

---

## Adding terms: subtraction

```scala
2 `-` 1
```

---

## Adding terms: subtraction

```scala
2 `-` 1
```

---

## Adding terms: subtraction

```scala
`2` - 1
```

```scala
class Sub()
```

---

## Adding terms: subtraction

```scala
`2` - 1
```

---

## Adding terms: subtraction

```scala
2 - `1`
```

```scala
class Sub(lhs: Exp[Int])
```

---

## Adding terms: subtraction

```scala
2 - `1`
```

---

## Adding terms: subtraction

```scala
2 - 1
```

---

## Adding terms: subtraction

```scala
2 - 1
```

.diff-add[
```scala
class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
* `override def toString = s"($lhs - $rhs)"`
```
]

---

## Adding terms: subtraction

```scala
3 - (2 + 1)
```

---

## Adding terms: subtraction

```scala
3 `-` (2 + 1)
```

---

## Adding terms: subtraction

```scala
`3` - (2 + 1)
```

---

## Adding terms: subtraction

```scala
`3` - (2 + 1)
```

---

## Adding terms: subtraction

```scala
3 - `(2 + 1)`
```

---

## Adding terms: subtraction

```scala
3 - `(2 + 1)`
```

---

## Adding terms: subtraction

```scala
3 - (2 + 1)
```

---

## Adding terms: subtraction

```scala
3 - (2 + 1)
```

```scala
Sub(
  Num(3),
  Add(Num(2), Num(1))
).toString
// val res5: String = (3 - (2 + 1))
```

---

## Adding interpreters: evaluation

```scala
abstract class Exp[T]:
  def toString: String
```

---

## Adding interpreters: evaluation

---

## Adding interpreters: evaluation

```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
```

---

## Adding interpreters: evaluation

.diff-add[
```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
* `override def eval     = ???`

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
* `override def eval     = ???`

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
* `override def eval     = ???`
```
]

---

## Adding interpreters: evaluation

.diff-rm[
```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
* override def eval     = `???`

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
  override def eval     = ???

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
  override def eval     = ???
```
]

---

## Adding interpreters: evaluation

.diff-add[
```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
* override def eval     = `value`

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
  override def eval     = ???

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
  override def eval     = ???
```
]

---

## Adding interpreters: evaluation

.diff-rm[
```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
  override def eval     = value

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
* override def eval     = `???`

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
  override def eval     = ???
```
]

---

## Adding interpreters: evaluation

.diff-add[
```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
  override def eval     = value

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
* override def eval     = `lhs.eval + rhs.eval`

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
  override def eval     = ???
```
]

---

## Adding interpreters: evaluation

.diff-rm[
```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
  override def eval     = value

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
  override def eval     = lhs.eval + rhs.eval

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
* override def eval     = `???`
```
]

---

## Adding interpreters: evaluation

.diff-add[
```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
  override def eval     = value

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
  override def eval     = lhs.eval + rhs.eval

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
* override def eval     = `lhs.eval - rhs.eval`
```
]

---

## Adding interpreters: evaluation

```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
  override def eval     = value

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
  override def eval     = lhs.eval + rhs.eval

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
  override def eval     = lhs.eval - rhs.eval

// ⛔ class Eq needs to be abstract, since
//   def eval: T in class Exp is not defined
```

---

## Adding interpreters: evaluation

.diff-add[
```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
  override def eval     = value

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
  override def eval     = lhs.eval + rhs.eval

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
  override def eval     = lhs.eval - rhs.eval
*
*`class Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]:`
* `override def toString = s"($lhs = $rhs)"`
```
]

---

## Adding interpreters: evaluation

.diff-add[
```scala
class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
  override def eval     = value

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
  override def eval     = lhs.eval + rhs.eval

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
  override def eval     = lhs.eval - rhs.eval

class Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]:
  override def toString = s"($lhs = $rhs)"
* `override def eval     = lhs.eval == rhs.eval`
```
]

---

## Adding interpreters: evaluation

```scala
(1 + 2) = (3 - 1)
```

---

## Adding interpreters: evaluation

```scala
(1 + 2) `=` (3 - 1)
```

---

## Adding interpreters: evaluation

```scala
`(1 + 2)` = (3 - 1)
```

---

## Adding interpreters: evaluation

```scala
`(1 + 2)` = (3 - 1)
```

---

## Adding interpreters: evaluation

```scala
(1 + 2) = `(3 - 1)`
```

---

## Adding interpreters: evaluation

```scala
(1 + 2) = `(3 - 1)`
```

---

## Adding interpreters: evaluation

```scala
(1 + 2) = (3 - 1)
```

---

## Adding interpreters: evaluation

```scala
(1 + 2) = (3 - 1)
```

```scala
Eq(
  Add(Num(1), Num(2)),
  Sub(Num(3), Num(1))
).eval
// val res7: Boolean = false
```

---

## Key takeaways

Feature              || OOP
---------------------||--------------------
 Term                || class
 Interpreter         || method
 Illegal states      || impossible
 Adding terms        ||  
 Adding interpreters ||

---

## Key takeaways

Feature              || OOP
---------------------||--------------------
 Term                || class
 Interpreter         || method
 Illegal states      || impossible
 Adding terms        || easy
 Adding interpreters ||

---

## Key takeaways

Feature              || OOP
---------------------||--------------------
 Term                || class
 Interpreter         || method
 Illegal states      || impossible
 Adding terms        || easy
 Adding interpreters || hard

---

# Decoupling data and behaviours

---

## "Dumb" data

```scala
abstract class Exp[T]:
  def toString: String
  def eval: T

class Num(value: Int) extends Exp[Int]:
  override def toString = value.toString
  override def eval     = value

class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs + $rhs)"
  override def eval     = lhs.eval + rhs.eval

class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]:
  override def toString = s"($lhs - $rhs)"
  override def eval     = lhs.eval - rhs.eval

class Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]:
  override def toString = s"($lhs = $rhs)"
  override def eval     = lhs.eval == rhs.eval
```

---

## "Dumb" data

*class Num(value: Int) extends Exp[Int]`:`
* `override def toString = value.toString`
* `override def eval     = value`
*
*class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]`:`
* `override def toString = s"($lhs + $rhs)"`
* `override def eval     = lhs.eval + rhs.eval`
*
*class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]`:`
* `override def toString = s"($lhs - $rhs)"`
* `override def eval     = lhs.eval - rhs.eval`
*
*class Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]`:`
* `override def toString = s"($lhs = $rhs)"`
* `override def eval     = lhs.eval == rhs.eval`
```
]

---

## "Dumb" data

```scala
abstract class Exp[T]

class Num(value: Int) extends Exp[Int]
class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
class Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]
```

---

## "Dumb" data

*class Num(`val `value: Int) extends Exp[Int]
*class Add(`val `lhs: Exp[Int], `val `rhs: Exp[Int]) extends Exp[Int]
*class Sub(`val `lhs: Exp[Int], `val `rhs: Exp[Int]) extends Exp[Int]
*class Eq(`val `lhs: Exp[Int], `val `rhs: Exp[Int]) extends Exp[Boolean]
```
]

---

## Pretty printing

```scala
def print[T](exp: Exp[T]): String = ???
```

---

## Pretty printing

```scala
def print[T](`exp: Exp[T]`): String = ???
```

---

## Pretty printing

```scala
def print[T](exp: Exp[T]): `String` = ???
```

---

## Pretty printing

---

## Pretty printing

.diff-add[
```scala
*def print[T](exp: Exp[T]): String = `exp match`
* `case i: Num => ???`
* `case a: Add => ???`
* `case m: Sub => ???`
* `case e: Eq  => ???`
```
]

---

## Pretty printing

```scala
def print[T](exp: Exp[T]): String = exp match
  case i: `Num` => ???
  case a: `Add` => ???
  case m: `Sub` => ???
  case e: `Eq`  => ???
```

---

## Pretty printing

.diff-rm[
```scala
def print[T](exp: Exp[T]): String = exp match
* case i: Num => `???`
  case a: Add => ???
  case m: Sub => ???
  case e: Eq  => ???
```
]

---

## Pretty printing

.diff-add[
```scala
def print[T](exp: Exp[T]): String = exp match
* case i: Num => `i.value.toString`
  case a: Add => ???
  case m: Sub => ???
  case e: Eq  => ???
```
]

---

## Pretty printing

.diff-rm[
```scala
def print[T](exp: Exp[T]): String = exp match
  case i: Num => i.value.toString
* case a: Add => `???`
  case m: Sub => ???
  case e: Eq  => ???
```
]

---

## Pretty printing

.diff-add[
```scala
def print[T](exp: Exp[T]): String = exp match
  case i: Num => i.value.toString
* case a: Add => `s"(${print(a.lhs)} + ${print(a.rhs)})"`
  case m: Sub => ???
  case e: Eq  => ???
```
]

---

## Pretty printing

.diff-rm[
```scala
def print[T](exp: Exp[T]): String = exp match
  case i: Num => i.value.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
* case m: Sub => `???`
  case e: Eq  => ???
```
]

---

## Pretty printing

.diff-add[
```scala
def print[T](exp: Exp[T]): String = exp match
  case i: Num => i.value.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
* case m: Sub => `s"(${print(m.lhs)} - ${print(m.rhs)})"`
  case e: Eq  => ???
```
]

---

## Pretty printing

.diff-rm[
```scala
def print[T](exp: Exp[T]): String = exp match
  case i: Num => i.value.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
  case m: Sub => s"(${print(m.lhs)} - ${print(m.rhs)})"
* case e: Eq  => `???`
```
]

---

## Pretty printing

.diff-add[
```scala
def print[T](exp: Exp[T]): String = exp match
  case i: Num => i.value.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
  case m: Sub => s"(${print(m.lhs)} - ${print(m.rhs)})"
* case e: Eq  => `s"(${print(e.lhs)} = ${print(e.rhs)})"`
```
]

---

## Pretty printing

```scala
def print[T](exp: Exp[T]): String = exp match
  case `i: Num` => i.value.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
  case m: Sub => s"(${print(m.lhs)} - ${print(m.rhs)})"
  case e: Eq  => s"(${print(e.lhs)} = ${print(e.rhs)})"
```

---

## Pretty printing

```scala
def print[T](exp: Exp[T]): String = exp match
  case i: Num => `i.value`.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
  case m: Sub => s"(${print(m.lhs)} - ${print(m.rhs)})"
  case e: Eq  => s"(${print(e.lhs)} = ${print(e.rhs)})"
```

---

## Pretty printing

```scala
def print[T](exp: Exp[T]): String = exp match
  case i: Num => i.value.toString
  case `a: Add` => s"(${print(`a.lhs`)} + ${print(`a.rhs`)})"
  case m: Sub => s"(${print(m.lhs)} - ${print(m.rhs)})"
  case e: Eq  => s"(${print(e.lhs)} = ${print(e.rhs)})"
```

---

## Product types

```scala
abstract class Exp[T]

class Num(val value: Int) extends Exp[Int]
class Add(val lhs: Exp[Int], val rhs: Exp[Int]) extends Exp[Int]
class Sub(val lhs: Exp[Int], val rhs: Exp[Int]) extends Exp[Int]
class Eq(val lhs: Exp[Int], val rhs: Exp[Int]) extends Exp[Boolean]
```

---

## Product types

*`case `class Num(val value: Int) extends Exp[Int]
*`case `class Add(val lhs: Exp[Int], val rhs: Exp[Int])
*`  `extends Exp[Int]
*`case `class Sub(val lhs: Exp[Int], val rhs: Exp[Int])
*`  `extends Exp[Int]
*`case `class Eq(val lhs: Exp[Int], val rhs: Exp[Int])
*`  `extends Exp[Boolean]
```
]

---

## Product types

*case class Num(`val `value: Int) extends Exp[Int]
*case class Add(`val `lhs: Exp[Int], `val `rhs: Exp[Int])
*`  `extends Exp[Int]
*case class Sub(`val `lhs: Exp[Int], `val `rhs: Exp[Int])
*`  `extends Exp[Int]
*case class Eq(`val `lhs: Exp[Int], `val `rhs: Exp[Int])
*`  `extends Exp[Boolean]
```
]

---

## Product types

```scala
abstract class Exp[T]

case class Num(value: Int) extends Exp[Int]
case class Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
case class Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
case class Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]

```

---

## Product types

.diff-rm[
```scala
def print[T](exp: Exp[T]): String = exp match
* case `i: Num` => i.value.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
  case m: Sub => s"(${print(m.lhs)} - ${print(m.rhs)})"
  case e: Eq  => s"(${print(e.lhs)} = ${print(e.rhs)})"
```
]

---

## Product types

.diff-add[
```scala
def print[T](exp: Exp[T]): String = exp match
* case `Num(i)` => i.value.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
  case m: Sub => s"(${print(m.lhs)} - ${print(m.rhs)})"
  case e: Eq  => s"(${print(e.lhs)} = ${print(e.rhs)})"
```
]

---

## Product types

.diff-rm[
```scala
def print[T](exp: Exp[T]): String = exp match
* case Num(i) => i`.value`.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
  case m: Sub => s"(${print(m.lhs)} - ${print(m.rhs)})"
  case e: Eq  => s"(${print(e.lhs)} = ${print(e.rhs)})"
```
]

---

## Product types

```scala
def print[T](exp: Exp[T]): String = exp match
  case Num(i) => i.toString
  case a: Add => s"(${print(a.lhs)} + ${print(a.rhs)})"
  case m: Sub => s"(${print(m.lhs)} - ${print(m.rhs)})"
  case e: Eq  => s"(${print(e.lhs)} = ${print(e.rhs)})"
```

---

## Product types

.diff-rm[
```scala
def print[T](exp: Exp[T]): String = exp match
  case Num(i) => i.toString
* case `a: Add` => s"(${print(`a.`lhs)} + ${print(`a.`rhs)})"
* case `m: Sub` => s"(${print(`m.`lhs)} - ${print(`m.`rhs)})"
* case `e: Eq`  => s"(${print(`e.`lhs)} = ${print(`e.`rhs)})"
```
]

---

## Product types

.diff-add[
```scala
def print[T](exp: Exp[T]): String = exp match
* case Num(i)`       ` => i.toString
* case `Add(lhs, rhs)` => s"(${print(lhs)} + ${print(rhs)})"
* case `Sub(lhs, rhs)` => s"(${print(lhs)} - ${print(rhs)})"
* case `Eq(lhs, rhs) ` => s"(${print(lhs)} = ${print(rhs)})"
```
]

---

## Product types

```scala
(1 + 2) = (3 - 1)
```

---

## Product types

---

## Product types

```scala
(1 + 2) = (3 - 1)
```

```scala
print(Eq(
  Add(Num(1), Num(2)),
  Sub(Num(3), Num(1))
))
// val res0: String = ((1 + 2) = (3 - 1))
```

---

## Exhaustivity

```scala
def eval[T](exp: Exp[T]): T = ???
```

---

## Exhaustivity

```scala
def eval[T](`exp: Exp[T]`): T = ???
```

---

## Exhaustivity

```scala
def eval[T](exp: Exp[T]): `T` = ???
```

---

## Exhaustivity

---

## Exhaustivity

.diff-add[
```scala
*def eval[T](exp: Exp[T]): T = `exp match`
* `case Num(i)        => ???`
* `case Add(lhs, rhs) => ???`
* `case Sub(lhs, rhs) => ???`
```
]

---

## Exhaustivity

.diff-rm[
```scala
def eval[T](exp: Exp[T]): T = exp match
* case Num(i)        => `???`
* case Add(lhs, rhs) => `???`
* case Sub(lhs, rhs) => `???`
```
]

---

## Exhaustivity

.diff-add[
```scala
def eval[T](exp: Exp[T]): T = exp match
* case Num(i)        => `i`
* case Add(lhs, rhs) => `eval(lhs) + eval(rhs)`
* case Sub(lhs, rhs) => `eval(lhs) - eval(rhs)`
```
]

---

## Exhaustivity

```scala
(1 + 2) = (3 - 1)
```

---

## Exhaustivity

```scala
(1 + 2) = (3 - 1)
```

---

## Exhaustivity

```scala
(1 + 2) = (3 - 1)
```

```scala
eval(Eq(
  Add(Num(1), Num(2)),
  Sub(Num(3), Num(1))
))
// 💥 scala.MatchError at...
```

---

## Exhaustivity

```scala
(1 + 2) = (3 - 1)
```

```scala
def eval[T](exp: Exp[T]): T = exp match
  case `Num(i)`        => i
  case `Add(lhs, rhs)` => eval(lhs) + eval(rhs)
  case `Sub(lhs, rhs)` => eval(lhs) - eval(rhs)
```

---

## Exhaustivity

```scala
(1 + 2) = (3 - 1)
```

```scala
def eval[T](exp: Exp[T]): T = exp match
  case Num(i)        => i
  case Add(lhs, rhs) => eval(lhs) + eval(rhs)
  case Sub(lhs, rhs) => eval(lhs) - eval(rhs)
```

---

## Exhaustivity

```scala
abstract class Exp[T]

---

## Exhaustivity

---

## Exhaustivity

```scala
def eval[T](exp: Exp[T]): T = exp match
  case Num(i)        => i
  case Add(lhs, rhs) => eval(lhs) + eval(rhs)
  case Sub(lhs, rhs) => eval(lhs) - eval(rhs)
```

---

## Exhaustivity

```scala
def eval[T](exp: Exp[T]): T = exp match
  case Num(i)        => i
  case Add(lhs, rhs) => eval(lhs) + eval(rhs)
  case Sub(lhs, rhs) => eval(lhs) - eval(rhs)
// ⛔ match may not be exhaustive.
//
//   It would fail on pattern case: Eq(_, _)
```

---

## Exhaustivity

.diff-add[
```scala
def eval[T](exp: Exp[T]): T = exp match
  case Num(i)        => i
  case Add(lhs, rhs) => eval(lhs) + eval(rhs)
  case Sub(lhs, rhs) => eval(lhs) - eval(rhs)
* `case Eq(lhs, rhs)  => eval(lhs) == eval(rhs)`
```
]

---

## Exhaustivity

```scala
(1 + 2) = (3 - 1)
```

```scala
eval(Eq(
  Add(Num(1), Num(2)),
  Sub(Num(3), Num(1))
))
```

---

## Exhaustivity

```scala
(1 + 2) = (3 - 1)
```

```scala
eval(Eq(
  Add(Num(1), Num(2)),
  Sub(Num(3), Num(1))
))
// val res1: Boolean = false
```

---

## ADTs

```scala
sealed abstract class Exp[T]

---

## ADTs

---

## ADTs

---

## ADTs

.diff-rm[
```scala
enum Exp[T]:
*
*case` class` Num(value: Int) extends Exp[Int]
*case` class` Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
*case` class` Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
*case` class` Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]
```
]

---

## ADTs

.diff-add[
```scala
enum Exp[T]:
*`  `case Num(value: Int) extends Exp[Int]
*`  `case Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
*`  `case Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
*`  `case Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]
```
]

---

## ADTs

```scala
enum Exp[T]:
  case Num(value: Int) `extends Exp[Int]`
  case Add(lhs: Exp[Int], rhs: Exp[Int]) `extends Exp[Int]`
  case Sub(lhs: Exp[Int], rhs: Exp[Int]) `extends Exp[Int]`
  case Eq(lhs: Exp[Int], rhs: Exp[Int]) `extends Exp[Boolean]`
```

???

Scala has syntax for this exact, enums, which are really sums of products.
It's a subset of Algebraic Data Types.

---

## Key takeaways

Feature              || OOP                 | Algebraic Data Types
---------------------||---------------------|---------------------
 Term                || class               |  
 Interpreter         || method              |  
 Illegal states      || impossible          |  
 Adding terms        || easy                |  
 Adding interpreters || hard                |

---

## Key takeaways

Feature              || OOP                 | Algebraic Data Types
---------------------||---------------------|---------------------
 Term                || class               | data type
 Interpreter         || method              |  
 Illegal states      || impossible          |  
 Adding terms        || easy                |  
 Adding interpreters || hard                |

---

## Key takeaways

Feature              || OOP                 | Algebraic Data Types
---------------------||---------------------|---------------------
 Term                || class               | data type
 Interpreter         || method              | function
 Illegal states      || impossible          |  
 Adding terms        || easy                |  
 Adding interpreters || hard                |

---

## Key takeaways

Feature              || OOP                 | Algebraic Data Types
---------------------||---------------------|---------------------
 Term                || class               | data type
 Interpreter         || method              | function
 Illegal states      || impossible          | impossible
 Adding terms        || easy                |  
 Adding interpreters || hard                |

---

# Growing the language, again

---

## Adding terms: multiplication

```scala
2 * 3
```

---

## Adding terms: multiplication

```scala
2 `*` 3
```

---

## Adding terms: multiplication

```scala
`2` * `3`
```

---

## Adding terms: multiplication

```scala
2 `*` 3
```

```scala
enum Exp[T]:
  case Num(value: Int) extends Exp[Int]
  case Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
  case Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
  case Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]
```

---

## Adding terms: multiplication

```scala
2 `*` 3
```

.diff-add[
```scala
enum Exp[T]:
  case Num(value: Int) extends Exp[Int]
  case Add(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
  case Sub(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Int]
  case Eq(lhs: Exp[Int], rhs: Exp[Int]) extends Exp[Boolean]
* `case Mult()`
```
]

---

## Adding terms: multiplication

```scala
`2` * 3
```

---

## Adding terms: multiplication

```scala
`2` * 3
```

---

## Adding terms: multiplication

```scala
2 * `3`
```

---

## Adding terms: multiplication

```scala
2 * `3`
```

---

## Adding terms: multiplication

```scala
2 * 3
```

---

## Adding terms: multiplication

```scala
def print[T](exp: Exp[T]): String = exp match
  case Num(i)         => i.toString
  case Add(lhs, rhs)  => s"(${print(lhs)} + ${print(rhs)})"
  case Sub(lhs, rhs)  => s"(${print(lhs)} - ${print(rhs)})"
  case Eq(lhs, rhs)   => s"(${print(lhs)} = ${print(rhs)})"
// ⛔ match may not be exhaustive.
//   It would fail on pattern case: Exp.Mult(_, _)
```

---

## Adding terms: multiplication

.diff-add[
```scala
def print[T](exp: Exp[T]): String = exp match
  case Num(i)         => i.toString
  case Add(lhs, rhs)  => s"(${print(lhs)} + ${print(rhs)})"
  case Sub(lhs, rhs)  => s"(${print(lhs)} - ${print(rhs)})"
  case Eq(lhs, rhs)   => s"(${print(lhs)} = ${print(rhs)})"
* `case Mult(lhs, rhs) => s"(${print(lhs)} * ${print(rhs)})"`
```
]

---

## Adding terms: multiplication

```scala
(3 + 3) = (2 * 3)
```

---

## Adding terms: multiplication

```scala
(3 + 3) `=` (2 * 3)
```

---

## Adding terms: multiplication

```scala
`(3 + 3)` = (2 * 3)
```

---

## Adding terms: multiplication

```scala
`(3 + 3)` = (2 * 3)
```

---

## Adding terms: multiplication

```scala
(3 + 3) = `(2 * 3)`
```

---

## Adding terms: multiplication

```scala
(3 + 3) = `(2 * 3)`
```

---

## Adding terms: multiplication

```scala
(3 + 3) = (2 * 3)
```

---

## Adding terms: multiplication

```scala
(3 + 3) = (2 * 3)
```

```scala
print(Eq(
  Add(Num(3), Num(3)),
  Mult(Num(2), Num(3))
))
// val res3: String = ((3 + 3) = (2 * 3))
```

---

## Adding terms: multiplication

```scala
def eval[T](exp: Exp[T]): T = exp match
  case Num(i)         => i
  case Add(lhs, rhs)  => eval(lhs) + eval(rhs)
  case Sub(lhs, rhs)  => eval(lhs) - eval(rhs)
  case Eq(lhs, rhs)   => eval(lhs) == eval(rhs)
```

---

## Adding terms: multiplication

.diff-add[
```scala
def eval[T](exp: Exp[T]): T = exp match
  case Num(i)         => i
  case Add(lhs, rhs)  => eval(lhs) + eval(rhs)
  case Sub(lhs, rhs)  => eval(lhs) - eval(rhs)
  case Eq(lhs, rhs)   => eval(lhs) == eval(rhs)
* `case Mult(lhs, rhs) => eval(lhs) * eval(rhs)`
```
]

---

## Adding terms: multiplication

```scala
(3 + 3) = (2 * 3)
```

---

## Adding terms: multiplication

```scala
(3 + 3) = (2 * 3)
```

---

## Adding terms: multiplication

```scala
(3 + 3) = (2 * 3)
```

```scala
eval(Eq(
  Add(Num(3), Num(3)),
  Mult(Num(2), Num(3))
))
// val res4: Boolean = true
```

---