从零开始的编译器前端之前置知识点

可能会是一个关于如何用monadic parsing来手写编译器的系列，来记录自己做实现的时候遇到的坑和一些经验。

第一篇文章会简单介绍一下一些基础设定。

首先是Monad。

众所周知，自函子范畴上的……（拖走暴打

好吧，这里不讨论学术上的定义，只试着以纯粹的使用者的角度从OO的视角出发去理解一下Monad，当然还有Functor，Applicative和Alternative这些typeclass到底是什么作用。

关于Typeclass

首先还得解释一下typeclass是什么……嗯，其实和OO里面的Interface是非常接近的概念，虽然说，还是有很多不同。

具体的说的话，OO的Interface构成的泛型是Parametric Polymorphism的重要组成，而typeclass则是基于Adhoc Polymorphism。

• Parametric Polymorphism的意思是，对于同一个函数，不去关心传入的参数是什么而把它用于所有传入的函数，例如

  fun <T> List<T>.boxsize(): Int {
      return this.size
  }

  这个函数对无论任何类型T构成的List都会使用同一个实现。

• Adhoc Polymorphism的意思是，根据传入的类型，决定使用的实现。因此，会有不同的可能的实现。比如说

  class Animal a where
      bark :: a -> String
      
  instance Animal Cat where
      bark = ...
      
  instance Animal Dog where
      bark = ...

  这里的每一个类型对应的实现都是不同的。看起来很像OO里面的继承但其实完全不是。准确的说，这里的Animal和Cat/Dog之类的类型之间唯一的关系就是Cat/Dog之类的类型有相似的行为（都有bark函数）所以它们聚集在Animal这个typeclass下。

typeclass的这一特征也使得它看起来非常像Interface（指只表现出相似的行为但没有继承关系这一性质）。

Functor

简单来说，就是满足fmap :: (a -> b) -> f a -> f b的数据结构，这里的f指的是一种满足这个约束的，由类型a组成的一种数据结构，例如[a]，其中a可以是Int、String……

对于一个List而言，fmap实际上就是map，因为map 满足(a -> b) -> [a] -> [b]这样的关系。换句话说，一个Functor是实现了一种行为的数据结构， 这种行为允许传入一个从A类型的参数算出B类型的结果的函数，把它应用到一个包含A类型的包装结构上，从而得到一个包含B类型的包装结构。

fmap的中缀形式是<$>。

虽然编译器不会做检查，但是一个Functor必须满足以下的条件：

• fmap id = id
• fmap (g . h) = fmap g . fmap h

Applicative

Functor抽象出了「把一个（具有一个参数的）函数map到一个数据结构上的每一个元素」这个性质。Applicative进一步推广出「把任意参数数量的函数map到一个数据结构上」这一概念。

可以注意到fmap的参数部分只能传入一个参数，如果想要对于任何数量的参数都实现这样的功能，该怎么办呢？

一个想法是给每个数量都特化一个单独的函数，比如说：

fmap0 :: a -> f a
fmap1 :: (a -> b) -> f a -> f b
fmap2 :: (a -> b -> c) -> f a -> f b -> f c
fmap3 :: (a -> b -> c -> d) -> f a -> f b -> f c -> f d
...

然后可以这样使用：

> fmap2 (+) (Just 1) (Just 2)
Just 3

不过这个想法显然是不能令人满意的，首先，要手动对于每一个参数的数量都实现一遍fmap是重复累赘的工作，而且因为函数可以有无限多的参数，所以需要手动去声明的fmap的数量也会非常的多。

实际上，如果注意到(a -> b) -> f a -> f b和函数的application（(a -> b) -> a -> b）之间有对应的关系，并且意识到函数的application和可莉化之间的关系的话，也可以意识到，其实并不需要对每个参数去做一个实现，而是可以利用可莉化来实现一个泛用的fmap函数：

首先通过pure :: a -> f a来「提升」一个A类型的值为一个关于A类型的F容器，

然后用<*> :: f (a -> b) -> f a -> f b来串接每一个被提升过的值。<*>就是对容器进行操作返回用容器装着的值的结合。

<*>是左结合的，意味着g <*> x <*> y <*> z = ((g <*> x) <*> y) <*> z。

通常会把pure和<*>以这样的方式使用：pure g <*> x1 <*> x2 ... <*> xn，也就是说先把函数g提升起来，然后依照顺序进行<*>结合。这种方式又被称为Applicative style，因为参数结合的顺序和函数的应用是一致的。不同的是，每个参数的类型不再是ai而是f ai，返回值也变成了f b而不是b。

借助Applicative操作符，可以很容易的实现前面提到的fmap0之类的函数：

fmap0 :: a -> f a
fmap0 = pure

fmap1 :: (a -> b) -> f a -> f b
fmap1 g x = pure g <*> x

fmap2 :: (a -> b -> c) -> f a -> f b -> f c
fmap2 g x y = pure g <*> x <*> y

fmap3 :: (a -> b -> c -> d) -> f a -> f b -> f c -> f d
fmap3 g x y z = pure g <*> x <*> y <*> z

虽然编译器不会做检查，但是一个Applicative必须满足以下的条件：

• pure id <*> x = x
• pure (g x) = pure g <*> pure x
• x <*> pure y = pure (\g -> g y) <*> x
• x <*> (y <*> z) = (pure (.) <*> x <*> y) <*> z

Monad

假设一个数据类型data Expr = Val Int | Div Expr Expr。现在要实现一个eval函数，可能会这样写：

eval :: Expr -> Int
eval (Val n) = n
eval (Div x y) = eval x `div` eval y

这样会出现一个问题：这个函数不会考虑除以零的情况，如果除数为0，会抛出一个运行时错误。

也可以这样实现：

safediv :: Int -> Int -> Maybe Int 
safediv _ 0 = Nothing
safediv n m = Just (n `div` m)

eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = case eval x of
    Nothing -> Nothing
    Just n -> case eval y of
        Nothing -> Nothing
        Just m -> safediv n m

但是这样一来eval的实现就会变得非常啰嗦。

如果注意到Maybe本身也是一个Applicative的话，按照Applicative style重写的话，会得到这样的函数：

eval :: Expr -> Maybe Int
eval (Val n) = pure n
eval (Div x y) = pure safediv <*> eval x <*> eval y

然而这个函数并不能通过编译，因为safediv的类型是Int -> Int -> Maybe Int而pure所要求的函数的类型应该是Int -> Int -> Int。可以注意到，Applicative style里面传入的值是「被包装的」，但是传入的函数必须是「纯函数」，但是这里eval要求的传入的函数却并不是一个纯函数。

从另一方面来说，如果观察到上面的eval函数本身嵌套了多层的对于Maybe模式匹配，这一模式是否可以被抽离出来呢？

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
mx >>= f = case mx of
    Nothing -> Nothing
    Just x -> f x

这个思路是，>>=本身接受一个可能会失败的参数，以及一个可能会失败的函数，返回另一个可能失败的结果。如果运算失败了（不论是参数或者函数），那么Nothing会被返回并且扩散到下一个运算，否则进行正常的运算。>>=通常又叫bind。

使用bind和lambda，可以很轻易的重写之前的eval函数：

eval :: Expr -> Maybe Int
eval (Val n) = pure n
eval (Div x y) = eval x >>= \n ->
                 eval y >>= \m ->
                     safediv n m

一般的，bind遵循以下的写法：

m1 >>= \x1 ->
m2 >>= \x2 ->
...
mn >>= \xn ->
    f x1 x2 ... xn

一些语言里有一个专门的语法糖来表示这样的结构：do { x1 <- m1; x2 <- m2; ... xn <- mn; f x1 x2 ... xn }。

许多常见的数据结构都是Monad，比如说Maybe、List或者Tree。在Haskell里面，所有的副作用都是通过IO来包装的，这个IO本身也是一种Monad。

在接下来的章节里要实现的编译器，也是基于Monad的。

---

参考书目：Programming in Haskell