这篇也算是抄的OLEKSANDR MANZYUK的博客,最近写个玩具的时候,发现在实现tagless-final的时候,Scala的一些不太方便的地方(existential types?),这些问题感觉DOT之前是很难解决了,不过索性还有其他的解决方案。

Expression problem

为了解决Expression problem是一切的开始。这里是一个例子,我们要在语言里面实现一个DSL,实现加法,用haskell的话就是

1
2
data Exp = Lit Int
| Add Exp Exp

然后一个式子就可以是

1
2
e1 = Add (Lit 1)
(Add (Lit 2) (Lit 3))

然后利用模式匹配写eval

1
2
3
eval :: Exp -> Int
eval (Lit n) = n
eval (Add x y) = eval x + eval y

接下来,我们就面临了扩展的问题。首先我们需要加入一种新的interpreter,把表达式转化成文本。我们可以很直接的

1
2
3
view :: Exp -> String
view (Lit n) = show
view (Add x y) = "(" ++ view x

这个时候如果我们想要加一个乘法操作的话,就可能比较麻烦了,我们需要打开Exp的定义,然后加入Mul Exp Exp,然后重新编译。

对于另外一些语言,常见的OO语言,并没有algebraic data types,面对这种问题就不太一样。

这里用scala为例子(这种写法并不scala,只是为了举个栗子,反正用java写也差不多)。

1
2
3
4
5
6
7
8
9
10
11
trait Exp {
def eval: Int
}
case class Lit(n: Int) extends Exp {
def eval: Int = n
}
case class Add(x: Exp, y: Exp) extends Exp {
def eval: Int = x.eval + y.eval
}

这样,我们加入Mul只需要加入一个新的case class

1
2
3
case class Mul(x: Exp, y: Exp) extends Exp {
def eval: Int = x.eval * y.eval
}

这样,我们不用去触碰之前的代码就能加入新的功能。然而这种方法在实现一个新的interpreter的时候缺不方便,我们需要打开Exp,然后加入更多的东西。然后修改每一个子类。

这两种方法提供了两个不同角度扩展的自由度。用个经典的图就是

第一种方法提供了纵向扩展的自由度,而第二种方法提供了横向扩展的自由度。

Object Algebras

Object Algebras是这篇论文里面提出的。我们继续实现一遍之前的需求。

1
2
3
4
trait ExpAlg[T] {
def lit(n: Int): T
def add(x: T, y: T): T
}

这样,我们只能把值表达成函数,因为我们没办法填充具体的类型。

1
2
f e1[T](f: ExpAlg[T]): T =
f.add(f.lit(1), f.add(f.lit(2), f.lit(3)))

接下来,我们实现一个具体的Eval

1
2
3
4
5
6
7
8
9
10
11
12
trait Eval {
def eval: Int
}
class EvalExp extends ExpAlg[Eval] {
override def lit(n: Int): Eval = new Eval {
override def eval: Int = n
}
override def add(x: Eval, y: Eval): Eval = new Eval {
override def eval: Int = x.eval + y.eval
}
}

然后使用的时候只要

1
e1(new EvalExp).eval

当我们需要加入一个新的操作的时候,只要继承ExpAlg,然后加入新的操作就行了。

1
2
3
trait MulAlg[T] extends ExpAlg[T] {
def mul(x: T, y: T): T
}

然后重新实现一个Eval

1
2
3
4
5
class EvalMul extends EvalExp with MulAlg[Eval] {
override def mul(x: Eval, y: Eval): Eval = new Eval {
override def eval: Int = x.eval * y.eval
}
}

这样在不触碰过去的代码的情况下,就可以加入新的功能。同样,我们可以接着实现view的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
trait View {
def view: String
}
class ViewExp extends ExpAlg[View] {
override def lit(n: Int): View = new View {
override def view = n.toString
}
override def add(x: View, y: View): View = new View {
override def view = s"(${x.view} + ${y.view})"
}
}
class ViewMul extends ViewExp with MulAlg[View] {
override def mul(x: View, y: View): View = new View {
override def view = s"(${x.view} * ${y.view})"
}
}

最后,试验一下

1
e1(new ViewMul).vie // res0: String = (1 + (2 + 3))

通过这种方式,解决了两种扩展的问题。

Final Tagless

换成Haskell也有特殊的解决方法。

先声明typeclass

1
2
3
class ExpAlg t where
lit :: Int -> t
add :: t -> t -> t

换成Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
trait ExpAlg[T] {
def lit(n: Int): T
def add(x: T, y: T): T
}
object ExpAlg {
implicit class ToIntExpOps[T](n: Int)(implicit m: ExpAlg[T]) {
def lit[T](implicit m: ExpAlg[T]): T = m.lit(n)
}
implicit class ToExpAlgTOps[T](n: T)(implicit m: ExpAlg[T]) {
def add(y: T): T = m.add(n, y)
def ++ = add _
}
}

然后这样我们只要定义T类型就好,而且碰巧的是,我们发现其实这个类型就是Int

1
newtype Eval = Eval { eval :: Int }
1
2
3
trait Eval {
def eval: Int
}

然后实现具体的实例

1
2
3
instance ExpAlg Eval where
lit n = Eval n
add x y = Eval $ eval x + eval y
1
2
3
4
5
6
7
8
val evalInstance: ExpAlg[Eval] = new ExpAlg[Eval] {
override def lit(n: Int) = new Eval {
override def eval = n
}
override def add(x: Eval, y: Eval) = new Eval {
override def eval = x.eval + y.eval
}
}

最后的执行换成

1
eval (e1 :: Eval)
1
e1[Eval](evalInstance).eval

我们试一下扩展。

1
2
class ExpAlg t => MulAlg t where
mul :: t -> t -> t
1
2
3
4
5
6
7
8
9
10
trait MulAlg[T] extends ExpAlg[T] {
def mul(x: T, y: T): T
}
object MulAlg {
implicit class toMulAlgOps[T](n: T)(implicit m: MulAlg[T]) extends ToExpAlgTOps[T](n)(m){
def mul(y: T): T = m.mul(n, y)
def ** = mul _
}
}

然后实现新的Eval

1
2
instance MulAlg Eval where
mul x y = Eval $ eval x * eval y
1
2
3
4
5
6
7
class MulInstance extends EvalInstance with MulAlg[Eval] {
override def mul(x: Eval, y: Eval): Eval = new Eval {
override def eval = x.eval * y.eval
}
}
val mulInstance = new MulInstance

可以跑一下试一试

1
2
3
4
5
6
7
8
9
10
11
12
def e1[T](implicit m: ExpAlg[T]) = {
(1.lit[T] ++ 2.lit[T]) ++ 2.lit[T]
}
def e2[T](implicit m: ExpAlg[T], m1: MulAlg[T]) = {
(1.lit[T] ++ 2.lit[T]) ** 3.lit[T]
}
import EvalInstance._
println(e1[Eval].eval) // 5
println(e2[Eval].eval) // 9

最后,实现下view

1
2
3
4
5
6
7
8
newtype View = View { view :: String }
instance ExpAlg View where
lit n = View $ show n
add x y = View $ "(" ++ view x ++ " + " ++ view y ++ ")"
instance MulAlg View where
mul x y = View $ "(" ++ view x ++ " * " ++ view y ++ ")"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
trait View {
def view: String
}
object ViewExp {
implicit val viewInstance = new ExpAlg[View] {
override def lit(n: Int): View = new View {
override def view = n.toString
}
override def add(x: View, y: View): View = new View {
override def view = s"(${x.view} + ${y.view})"
}
}
implicit val mulInstance = new MulAlg[View] {
override def mul(x: View, y: View): View = new View {
override def view = s"(${x.view} * ${y.view})"
}
}
}

这样两种方式就都实现了。后者在又被称为final tagless。之所以称之为final,因为我们能够发现在执行过程是在构件过程,你完全可以写一个AST结构的继承体系GADT那样子,然后在eval中做pattern match,这样有点像scala最初的那种解决方案。因为第一种方法对应F-algebra中的initial,所以这种对应的方法就称为final。这一部分完整的Scala代码可以看这里

不过,这种方法得到的是untyped的,如果我们里面有多个类型(这里只有Int),就需要其他的东西了。




X