同态静态分析

# 同态静态分析 来源：http://marcosh.github.io/post/2026/05/21/homomorphic-static-analysis.html 在 Haskell 社区中，几乎是一个共识：应用函子（Applicative）允许进行静态分析，而单子（Monad）则不能。但这在实践中意味着什么？又指的是哪种静态分析？ 我能在网上找到的最佳答案是这个 StackOverflow 上的回答。在这篇文章中，我想对其进行一些扩展，并进一步深入探讨这个概念[^1]。 ## 上下文接口 考虑一个依赖于通用上下文 `m` 的示例接口，它被实现为一个函数记录（record of functions）： ```haskell data Interface m = Interface { foo :: FooInput -> m FooOutput , bar :: BarInput -> m BarOutput , baz :: BazInput -> m BazOutput } ``` 这是在纯函数式语言中定义接口的一种方法，已经被多次讨论和提出[^2]，并且效果相当不错。它定义了一组在相同上下文中工作的操作，这些操作可以用来定义更复杂的程序[^2]。 ```haskell myProgram :: Interface m -> Input -> m Output myProgram interface input = ... ``` `myProgram` 会使用 `Interface m` 定义的基本操作，但这些操作如何组合，则由 `m` 决定。如果 `m` 是 `Functor` 的实例，我们就可以执行其某个操作，然后使用纯函数映射结果。如果 `m` 是 `Applicative` 的实例，我们就可以独立执行 `Interface m` 中的操作，然后组合它们的结果。如果 `m` 是 `Monad` 的实例，我们就可以顺序组合 `Interface m` 中的操作，根据前一个操作的结果来决定是否执行下一个操作。 ## 在不执行代码的情况下解释代码 在生产代码中，`myProgram` 会在某个效应上下文 `m` 中被解释，并执行所有所需的效应。例如，`m` 可以是一个具体的单子（concrete monad）、一个单子变换器（monad transformer）栈，或者来自你最喜欢的效应系统的 `Eff` 单子。 尽管如此，我们可能还想收集一些关于代码的信息，而不执行任何具体的效应；例如，分析某些代码度量、计算依赖项列表，或者创建代码流程的图形表示。 实现这一点的一种方法是在另一个上下文 `m'` 中解释 `myProgram`，这个上下文不执行任何效应，而仅仅用于收集信息。一旦我们有了这个，就可以编写另一个可执行程序，在 `m'` 中解释 `myProgram`，并在不执行任何效应的情况下检索我们感兴趣的信息。这可以在不运行我们的应用程序的情况下完成，这也是为什么它被称为静态分析，尽管它仍然需要运行一些代码。 ## 在数据无关上下文中的解释 定义像上一节最后一段描述的 `m'` 上下文的一种方法是使其与数据无关。我的意思是像这样的数据结构： ```haskell newtype StaticInterpreter a = StaticInterpreter StaticDatum ``` `StaticInterpreter` 的关键之处在于 `a` 是一个幻影类型（phantom type），这意味着它出现在类型中，但在值层面没有任何该类型的值。 这样做的好处是，我们可以组合带有不同类型标记的 `StaticInterpreter` 值。例如，假设 `StaticDatum = Int`，那么我们可以组合 `StaticInterpreter i1 :: StaticInterpreter a1` 和 `StaticInterpreter i2 :: StaticInterpreter a2`，得到 `StaticInterpreter (i1 + i2) :: StaticInterpreter a`。 ## 约束上下文即约束静态数据 现在让我们看看，当我们开始对 `myProgram` 中的 `m` 施加约束时，`StaticDatum` 会发生什么。 如果需要 `m` 是一个 `Functor`，那么 `StaticInterpreter` 也应该具有 `Functor` 实例： ```haskell instance Functor StaticInterpreter where fmap :: (a -> b) -> StaticInterpreter a -> StaticInterpreter b fmap f (StaticInterpreter datum) = StaticInterpreter datum ``` 要实现它，我们对 `StaticDatum` 没有任何约束要求。这意味着，如果我们只需要 `m` 是一个 `Functor`，我们就可以对 `myProgram` 进行静态分析，并用任何可能的类型来解释它。 不过，通常我们的程序需要的不仅仅是 `Functor`。下一步是要求 `m` 具有 `Applicative` 实例。让我们看看一旦这样做，`StaticDatum` 会发生什么。 ```haskell instance Applicative StaticInterpreter where pure :: a -> StaticInterpreter a pure a = StaticInterpreter _ (<*>) :: StaticInterpreter (a -> b) -> StaticInterpreter a -> StaticInterpreter b (<*>) (StaticInterpreter sd1) (StaticInterpreter sd2) = StaticInterpreter _ ``` 我们基本上需要一种从无到有创建 `StaticDatum` 的方法，以及一种将两个 `StaticDatum` 值组合成一个新 `StaticDatum` 值的方法。换句话说，我们需要： ```haskell _outOfNothing :: StaticDatum _combineTwo :: StaticDatum -> StaticDatum -> StaticDatum ``` 而这正是 `StaticDatum` 上 `Monoid` 实例所提供的！ 这意味着，我们可以使用任何具有 `Monoid` 实例的类型，来静态分析受 `Applicative` 约束的程序。例如，`StaticDatum` 可以是一个值的列表，在 `StaticInterpreter` 中解释 `myProgram` 就会收集并连接所有元素[^3]。 现在让我们看看，如果要求 `StaticInterpreter` 具有 `Monad` 实例会发生什么。 ```haskell instance Monad StaticInterpreter where (>>=) :: StaticInterpreter a -> (a -> StaticInterpreter b) -> StaticInterpreter b (>>=) (StaticInterpreter sd) f = _ ``` 如果我们想要一个非平凡的 `>>=` 实现（即不是每次都返回 `StaticInterpreter mempty`），就需要使用 `f` 来获取一个 `StaticInterpreter b` 类型的值。但为了调用 `f`，我们需要一个 `a` 类型的值，而我们无法从 `StaticInterpreter a` 中提取它，因为 `a` 实际上是一个幻影类型，里面没有 `a` 类型的值。我们无法实现 `>>=` 的事实，就是为什么我们常说 `Monad` 不允许静态分析[^4]。 ## 用范畴玩同样的游戏 在上一节中，我们研究了在给定上下文 `m` 中编写的程序可以进行哪种静态分析。我们得出结论：如果只需要 `m` 具有 `Applicative` 实例，我们可以用任何幺半群（monoid）来静态分析程序；而如果要求 `Monad` 实例，我们基本上就丧失了静态反思代码的能力。 现在有趣的是（对我来说是这样！）尝试将相同的推理应用于范畴（categories）而不是函子/应用函子/单子。这意味着考虑 `Type -> Type -> Type` 的种类，而不是 `Type -> Type`。例子可以很简单地是 `(->)` 或 `Kleisli m`[^5]。 让我们像之前一样，考虑一个带有幻影类型的数据类型： ```haskell newtype CatStaticInterpreter a b = CatStaticInterpreter StaticDatum ``` 然后看看当我们尝试实现几个类型类的实例时会发生什么。让我们从 `Profunctor` 类型类开始。 ```haskell instance Profunctor CatStaticInterpreter where dimap :: (a -> b) -> (c -> d) -> CatStaticInterpreter b c -> CatStaticInterpreter a d dimap f g (CatStaticInterpreter sd) = CatStaticInterpreter sd ``` 就像我们之前对 `Functor` 所做的那样，我们忽略 `f` 和 `g` 函数，保持相同的 `StaticDatum` 值。 接下来我们可以探究 `Category` 类型类的情况： ```haskell instance Category CatStaticInterpreter where id :: CatStaticInterpreter a a id = _ (.) :: CatStaticInterpreter b c -> CatStaticInterpreter a b -> CatStaticInterpreter a c (.) (CatStaticInterpreter sd1) (CatStaticInterpreter sd2) = _ ``` 类似于上一节中 `Applicative` 类型类的情况，我们可以注意到，如果 `StaticDatum` 具有 `Monoid` 实例，我们就可以为 `CatStaticInterpreter` 实现 `Category` 实例。在这种情况下，我们可以定义： ```haskell id = CatStaticInterpreter mempty (.) (CatStaticInterpreter sd1) (CatStaticInterpreter sd2) = CatStaticInterpreter (sd1 <> sd2) ``` 请注意，虽然从计算角度来看 `Monad` 和 `Category` 同样强大，但前者不允许任何静态分析，而后者却可以。 ## `Strong` 和 `Choice` 的示例 当我们开始添加诸如 `Strong` 或 `Choice` 等约束时，事情变得更加有趣。对于这些类型类中的每一个，我们需要在 `StaticDatum` 上分别有一个二元操作，对应于 `(***)` 和 `(+++)`。 对于这个用例，让我们将 `StaticDatum` 定义为： ```haskell data StaticDatum = Unit Text | Compose StaticDatum StaticDatum | Alternative StaticDatum StaticDatum | Parallel StaticDatum StaticDatum ``` 有了这个定义，我们就可以为 `CatStaticInterpreter` 定义 `Category`、`Strong` 和 `Choice` 的实例。 ```haskell instance Category CatStaticInterpreter where id = CatStaticInterpreter Unit (.) (CatStaticInterpreter sd1) (CatStaticInterpreter sd2) = CatStaticInterpreter (Compose sd1 sd2) instance Strong CatStaticInterpreter where first' :: CatStaticInterpreter a b -> CatStaticInterpreter (a, c) (b, c) first' (CatStaticInterpreter sd) = CatStaticInterpreter (Parallel sd (Unit "id")) second' :: CatStaticInterpreter a b -> CatStaticInterpreter (c, a) (c, b) second' (CatStaticInterpreter sd) = CatStaticInterpreter (Parallel (Unit "id") sd) instance Choice CatStaticInterpreter where left' :: CatStaticInterpreter a b -> CatStaticInterpreter (Either a c) (Either b c) left' (CatStaticInterpreter sd) = CatStaticInterpreter (Alternative sd (Unit "id")) right' :: CatStaticInterpreter a b -> CatStaticInterpreter (Either c a) (Either c b) right' (CatStaticInterpreter sd) = CatStaticInterpreter (Alternative (Unit "id") sd) ``` 现在，让我们定义一个依赖于范畴 `p` 的接口： ```haskell data Interface p a b c d e f g h = Interface { foo1 :: p a b , foo2 :: p a c , foo3 :: p a (Either a a) , foo4 :: p a d , foo5 :: p a e , foo6 :: p (b, c) f , foo7 :: p (Either d e) g , foo8 :: p (f, g) h } ``` 有了它，我们可以定义一个使用该接口的示例函数 `foo`： ```haskell foo :: (Category p, Strong p, Choice p) => Interface p a b c d e f g h -> p a h foo Interface {..} = foo8 . ((foo6 . (foo1 &&& foo2)) &&& (foo7 . (foo4 +++ foo5) . foo3)) ``` 使用我们的 `CatStaticInterpreter`，现在可以为 `Interface CatStaticInterpreter` 定义一个实现： ```haskell implementation :: Interface CatStaticInterpreter a b c d e f g h implementation = Interface { foo1 = CatStaticInterpreter (Unit "foo1") , foo2 = CatStaticInterpreter (Unit "foo2") , foo3 = CatStaticInterpreter (Unit "foo3") , foo4 = CatStaticInterpreter (Unit "foo4") , foo5 = CatStaticInterpreter (Unit "foo5") , foo6 = CatStaticInterpreter (Unit "foo6") , foo7 = CatStaticInterpreter (Unit "foo7") , foo8 = CatStaticInterpreter (Unit "foo8") } ``` 最终，我们可以通过求值 `foo implementation` 来使用 `CatStaticInterpreter` 静态分析 `foo`： ``` >>> foo implementation Compose (Unit "foo8") (Compose (Parallel (Compose (Unit "foo6") (Compose (Parallel (Unit "foo1") (Unit "id")) (Parallel (Unit "id") (Unit "foo2")) ) ) (Unit "id") ) (Parallel (Unit "id") (Compose (Unit "foo7") (Compose (Compose (Alternative (Unit "foo4") (Unit "id")) (Alternative (Unit "id") (Unit "foo5")) ) (Unit "foo3") ) ) ) ) ``` 例如，通过这种树状表示，遍历并检查是否使用了特定模式（仅仅单个函数，还是更复杂的组合），甚至优化和重构树，都不困难。例如，任何 `Compose (Parallel (Unit "foo1") (Unit "id")) (Parallel (Unit "id") (Unit "foo2"))` 可能都可以重新解释为 `Parallel (Unit "foo1") (Unit "foo2")`。 另一种可能性是打印出结果树的图形表示，以记录我们程序的流程。对于 `foo`，它可能看起来像： Pro函子流程 ## 结论 回顾我们在这篇文章中所经历的，我们看到，我们可以用任何幺半群对在 `Applicative` 上下文中工作的任何代码进行静态分析；另一方面，单子不允许非平凡的静态分析。 转向范畴化领域，它在计算能力上与单子一样强大，但我们发现实际上可以进行静态分析，而且添加更多约束还可以让我们对代码结构有更深入的理解。在我们的示例中，我们看到了使用 `Strong` 和 `Choice` 可以做什么。同样的技巧还可以用于 `Closed`（处理函数）、`CoStrong`（处理递归）或 `CoChoice`。 --- [^1]: 原文链接：http://marcosh.github.io/post/2026/05/21/homomorphic-static-analysis.html [^2]: 指多次讨论和提出的方法。 [^3]: 指将所有元素收集并连接。 [^4]: 原因正如上文所述，无法实现 `>>=`。 [^5]: `Kleisli m` 是 `Control-Arrow` 模块中的一个类型。