Haskell调试任意lambda表达式

Question

我有一组lambda表达式,我将其传递给其他lambda.所有的lambdas都只依赖于他们的论点,他们不会调用任何外部函数.当然,有时它会变得非常混乱,我会将一个参数数量不正确的函数传递给另一个函数,从而产生一个GHCi异常.

我想创建一个调试函数,它将采用任意lambda表达式(具有未知数量的参数)并根据lambda的结构和函数返回一个字符串.

例如,假设我有以下lambda表达式:

i = \x -> x
k = \x y -> x
s = \x y z -> x z (y z)

debug (s k) 应该回来 "\a b -> b"

debug (s s k)应该返回"\a b -> a b a"(如果我正确简化)

debug s 应该回来 "\a b c -> a c (b c)"

这样做的好方法是什么？

Answer 1

我认为做到这一点的方法是在 Haskell 中定义一个小的 lambda 演算 DSL（或使用现有的实现）。这样，您就可以编写类似的内容，而不是使用本机 Haskell 公式

k = Lam "x" (Lam "y" (App (Var "x") (Var "y")))
s = Lam "x" (Lam "y" (Lam "z" (App (App (Var "x") (Var "z")
                                   (App (Var "y") (Var "z"))))

对于s和 也类似i。然后，您将编写/使用评估函数，以便您可以编写

debug e = eval e
debug (App s k)

这将为您提供您自己语法的最终形式。此外，您还需要一种解释器来将 DSL 语法转换为 Haskell，以便您可以实际使用代码中的函数。

实现这一点似乎确实需要大量（棘手的）工作，而且可能并不完全是您想要的（特别是如果您需要对类型化语法进行评估），但我确信这将是一次很棒的学习体验。一个很好的参考是“Write you a Haskell”的第 6 章。使用现有的实现会容易得多（但不太有趣:)）。

如果这只是为了调试目的，您可能会受益于查看 ghc 编译的核心语法。请参阅Real world Haskell 第 25 章，使用的 ghc 标志是 -ddump-simpl。但这意味着查看生成的代码而不是在程序内生成表示。我也不确定您在多大程度上能够轻松识别核心代码中的特定函数（我对此没有经验，所以 YMMV）。

如果在函数上使用 show 会给出您所描述的输出类型，那当然会很酷，但可能有很好的理由函数不是 Show 的实例（我无法告诉您）。