函数错位的探索

# 把函数塞进不该出现的地方 来源：https://blog.veritates.love/functions-as-data 纯粹数据意味着什么？我们究竟该如何把函数塞进数据中？ 对我而言，*纯粹数据*指满足或可实现以下特性的类型： - `Show`，可序列化整个内部结构。 - `NFData`（https://hackage-content.haskell.org/package/deepseq-1.5.2.0/docs/Control-DeepSeq.html#t:NFData），确保结构被完全求值（强制求值所有惰性thunk）。关于函数的NFData注：曾有一些（https://github.com/haskell/deepseq/issues/16）争论（https://github.com/haskell/deepseq/issues/111），讨论是否应保留函数的浅层WHNF实例作为规避笨拙代码的变通方案。本文提供了潜在的解决方案！语义上你希望`NFData`能规范闭包，即帮助函数实现运作的所有残留数据。但闭包的部分作用正是隐藏这些数据——你根本不知道它包含什么类型！除非所有数据都可规范化，否则这些数据很可能无法归一化，而且……你可能不喜欢它带来的副作用。 - `Eq`，用于比较值。 - `Ord`，用于排序值——不必然具有语义相关性。语义通常更偏好偏序关系。可以简单理解为`Set`和`Map`用来维护键的类型类。实现了`Eq`却无法实现`Ord`的类型极为罕见：存在类型，或由运行时实现的类型（如指针相等性/引用同一性——参见`Eq (IORef t)`示例）。 - 或许还有`Read`，但后文将说明其为何与本故事关系不大。 遵循这些接口契约的类型不会隐藏任何意外。它完全可读、简单、扁平。无论是代数数据类型（ADT）、字节串还是任意大自然数——其表示形式都无关紧要。它就是纯粹的数据。 不幸的是，这也意味着它不够*有趣*。你可以为数据添加可扩展性，但可扩展的*行为*更难实现。你可以教导所有消费该数据的代码如何处理这些新数据形态，甚至可能提供行为查找注册表——只要它们存在于运行时。但你无法在数据中嵌入函数。理论上不行，实践中也不行。好吧，某些运行时（https://blog.veritates.love/pickling.html#functions-builtins-bootstrapping）可以将函数序列化为字节码或语法树，但这在Haskell中不可行，且最好避免使用。 但真的做不到吗？ ### 起源故事：玩具WASM后端 我一直在尝试制作一个编译为WASM的简单函数式编程语言，并使用垃圾回收类型。（WASM GC提供了带垃圾回收引用的结构体和数组，通过`externref`与宿主运行时集成实现跨边界引用。虽然我将来也可能尝试自制GC，但特别对于原型开发，值得体验WASM GC。） 我*极其*希望语言中的类型能自由选择其在类型层面和代码层面的编码方式。例如，表面语言提供了数组、文本和ADT的基本语法，但我们应能将枚举编码为`i8`或`i31`（`i31`比`i32`节省一个比特，可与GC指针同域存储）。或许我们还想将位数组智能地编码为字节数组`\(array i8\)`。 我不想维护自定义类型的注册表。我不希望代码生成被特化类型和编译知识污染。基础代码生成应保持简洁纯粹。 但同时我也不想放弃表达式作为纯粹数据的特性——我希望能检查、比较AST（抽象语法树），或将它们用于属性测试等场景。 我该怎么办？ ### 存在类型模式 让我们通过去函数化（defunctionalization）形式，将函数“走私”到原本纯粹的数据中！ 类型类的魔力在于它们提供全局且*一致*的字典，以类型为键。由于全局且一致，字典本身不包含数据：理论上，你只需知道其类型即可。 而最棒的是？类型类字典天生就包含函数。 `NFData`对类型类字典不成问题：全局类型类字典中不会有意外的thunk或bottom值。`Eq`甚至`Ord`已为`TypeRep`（https://hackage-content.haskell.org/package/base-4.22.0.0/docs/Data-Typeable.html#t:TypeRep）提供——即`Typeable`类型的运行时表示（自动派生）。`Show`也不成问题（但`Read`会是问题）。 首先我们创建一个类型类同义名，捆绑所需的优秀特性。 ``` -- 为存在类型隐藏数据准备的良好属性 type Existentiable hidden = (Typeable hidden, NFData hidden, Ord hidden, Show hidden) ``` 接下来我们创建一个类型类，其中包含要“走私”的函数。比如这个用于注入任意外部语义的类： ``` class Existentiable sem => Semantics sem where semTyp :: sem -> STyp semCode :: sem -> WASM semEval :: sem -> [Expr] -> Map Name Expr -> Maybe Expr semExprs :: sem -> [Expr] semEffects :: sem -> Effects ``` 语义类型可以是捕获我们所需行为的任何数据类型。一旦获得该数据，我们就能投影出关心的行为：它的类型、某种代码生成方式、可能的求值模拟，以及用于静态分析的副作用说明。 这些本质上是编译器的钩子，是我们可扩展注入任意新行为的位置。 然后我们创建一个存在类型，将任意此类数据及其对应的类型类字典（包括`Typeable`、`Eq`等）包装起来，直到实际需要的`Semantics`。 ``` data ForeignSemantics = forall sem. Semantics sem => ForeignSemantics sem ``` 注意所有类型类方法都是投影式的（接收`sem`但不生成它），因此我们也能为这个抽象的`ForeignSemantics`存在类型实现`Semantics`： ``` instance Semantics ForeignSemantics where semTyp (ForeignSemantics sem) = semTyp sem semCode (ForeignSemantics sem) = semCode sem semEval (ForeignSemantics sem) = semEval sem semExprs (ForeignSemantics sem) = semExprs sem semEffects (ForeignSemantics sem) = semEffects sem ``` 为此，我们需要实现`Existentiable`的组成部分。 `Show`很简单，解包后应用`show`。`NFData`同样直接转发给包装类型的`NFData`——字典虽包含函数，但如前所述无需归一化：它只是全局类型类字典。 `Eq`和`Ord`需要比较两个值中`Typeable sem`打包的运行时类型反射。当然，`Typeable ForeignSemantics`自动派生——感谢GHC的神奇仙尘。 ``` instance Show ForeignSemantics where show (ForeignSemantics spec) = show spec instance NFData ForeignSemantics where rnf (ForeignSemantics spec) = rnf spec instance Eq ForeignSemantics where ForeignSemantics spec0 == ForeignSemantics spec2 | Just spec1 <- Typeable.cast spec0 = spec1 == spec2 | otherwise = False instance Ord ForeignSemantics where ForeignSemantics spec0 `compare` ForeignSemantics spec2 | Just spec1 <- Typeable.cast spec0 = spec1 `compare` spec2 | otherwise = Typeable.typeOf spec0 `compare` Typeable.typeOf spec2 ``` 现在我们可以在表达式主AST或任何有用的地方使用`ForeignSemantics`，而不会破坏`Show`、`NFData`、`Eq`或`Ord`的派生。 ``` -- 表达式AST data Expr -- 字面量 = EF64 !Double | EF32 !Float | EU64 !Word64 | EU32 !Word32 | ES64 !Int64 | ES32 !Int32 | ETxt !Text -- let表达式：按顺序绑定多个名称（非递归let） | ELet [(Expr, Bind)] Expr -- 变量引用 | EVar STyp !Name -- n元lambda表达式 | EFun STyp [Bind] Expr -- 函数应用（n元） | EApp Expr [Expr] . . . -- 外部代码 | EForeign ForeignSemantics deriving stock (Generic, Show, Eq, Ord) deriving anyclass (NFData) ``` 最后我们可以提供便捷的模式同义词。由于我们将`Typeable`与该存在类型捆绑，可以将其与特定类型比较，使用`Typeable\.cast`（https://hackage-content.haskell.org/package/base-4.22.0.0/docs/Data-Typeable.html#v:cast）检查是否为该类型。（这需要视图模式，虽非我所喜，但在此场景极为方便。）该模式同义词现可用于解构具体类型。 为方便起见，我们也可为AST类型重复该模式。由于每个`Expr`构造子都以`E`开头，可命名为`ESem`。 ``` pattern Sem :: Semantics sem => Semantics sem => sem -> ForeignSemantics pattern Sem sem <- ForeignSemantics (Typeable.cast -> Just (sem :: sem)) where Sem sem = ForeignSemantics sem pattern ESem :: Semantics sem => Semantics sem => sem -> Expr pattern ESem sem = EForeign (Sem sem) ``` 这很棒，库自身可以提供实例，需要时仍能具体匹配。例如，`STyp`是另一个合成类型的存在类型。 现在我们可以创建实例，它们会自动生效。外部调用的最小数据类型包含其类型、优化可能需要的副作用信息，以及要调用的WASM函数或导入名称。 ``` data ForeignCall = ForeignCall STyp Effects Name deriving stock (Eq, Ord, Show, Generic) deriving anyclass (NFData) instance Semantics ForeignCall where semTyp (ForeignCall t _ _) = t semCode (ForeignCall _ _ name) = tell $ SEXP "call" [ wasmID name ] semEval _ _ _ = Nothing semExprs _ = [] semEffects (ForeignCall _ ef _) = ef ``` 瞧，它自动接入编译器，我们可以通过魔法表达式`ESem \(ForeignCall \(itsType\) mempty "functionToCall"\)`召唤任何函数。 需特别注意，这是我们真正需要类型类约束存在类型的少数情况之一。通常你会说`data Showable = forall t. Show t => Showable t`等同于`String`（或其他类型），因为通过`show`转换为`String`是对存在类型`t`值能做的全部操作。但因为我们想在其中将函数作为数据，需要保持类型类字典抽象，并保留底层数据类型。 此外，你在此处从事实际工作。必须为每个类型类实例决定其行为背后数据的本质。你正在设计所需函数的闭包，并称其为`sem`类型。这本就是去函数化工作的核心部分。 但你无需担心去函数化的可扩展性问题；无需考虑作为库还是库消费者的立场。Haskell已处理好一切。这只是另一个类型类，而类型类机制无比强大。 你只是得不到实例的漂亮枚举列表，而实现`Read`那样的反序列化需要它。你受限于与此开放世界视图兼容的方法。但这对编译器钩子等场景来说恰到好处。 ### 结论 去函数化通常要么是经过深思熟虑的、极其显式的设计选择，要么在闭源代码库外部执行——那时所有函数都是已知的。 这种去函数化形式是可扩展的：你可以编写包含某些实例的Haskell库，用户可以带来自己的实例，无需任何协调。 你可以为代码或数据的任何部分添加可扩展行为，而不会过多损害数据的本质，无需维护扩展注册表，也无需预测用户（或未来的你）可能想用它做什么。 确定实例所需函数的核心数据需要付出努力，但希望这不会过于繁重，且能提供清晰性。这比其他方案更优。 遗憾的是，目前无法自动序列化和反序列化这些存在类型字典。我曾期望GHC\.Compact（https://hackage-content.haskell.org/package/ghc-compact-0.1.0.0/docs/GHC-Compact.html）能做到，但它未为类型类字典预留特殊处理。它确实说明： > 序列化数据只能由创建它的完全相同的二进制文件反序列化，但可以在反序列化前无限期存储。 理论上，如果你真想玩火，甚至可以包含函数和闭包。相同二进制，相同函数。更安全的做法是，二进制文件可嵌入规范的`TypeRep -> Dict`表（即字典组装器），以便反序列化时查找实例。但GHC运行时不支持此功能。