Haskell调试任意lambda表达式

Question

我有一组Lambda表达式，我正在将它们传递给其他Lambda表达式。所有Lambda表达式只依赖于它们的参数，它们不调用任何外部函数。当然，有时候会变得相当混乱，我会将一个带有不正确数量参数的函数传递给另一个函数，从而创建一个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)"

有什么好的方法可以做到这一点吗？

- crb233

---

并不是在Haskell中，这种信息会在编译时被擦除。你可以使用模板Haskell来实现它，但那并不简单。 - bheklilr

有很多关于实现λ演算的资源可供使用。TaPL是一个特别好的资源，其中包括了各种复杂程度的演算实现。此外，在Hackage上也似乎有一些小型的实现可以尝试。 - Daniel Wagner

Haskell是一种静态类型语言。实际上，它并不涉及深入的λ演算，除非λ恰好是编写笛卡尔闭范畴表达式的有用方式。但是，直接使用类型来了解函数的作用要比查看某个等效的λ表达式更有效率。对于您想要实现的内容，Scheme这样的语言更加适合。 - leftaroundabout

这个有帮助吗？链接 - effectfully

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"))))

同样地，对于和也是如此。然后您将编写/使用评估函数，以便可以编写以下内容。

debug e = eval e
debug (App s k)

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

实现这似乎需要相当多的（棘手的）工作，而且这可能不完全是您想要的（特别是如果您需要类型化语法的评估），但我相信这将是一个很好的学习经验。一个很好的参考资料是“编写Haskell”第6章。使用现有的实现会更容易（但不那么有趣 :))。

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

当然，如果在函数上使用show命令可以得到你描述的输出结果，那会很酷，但是函数不是Show的实例可能有非常好的理由（我无法告诉你）。

- Sam van Herwaarden

Answer 2

你可以通过利用 GHC 自带的 Template Haskell 中的漂亮打印功能来实现这一点。

首先，应该在单独的模块中定义格式化函数（这是 TH 的限制）：

module LambdaPrint where

import Control.Monad
import Language.Haskell.TH.Ppr
import Language.Haskell.TH.Syntax

showDef :: Name -> Q Exp
showDef = liftM (LitE . StringL . pprint) . reify

然后使用它：

{-# LANGUAGE TemplateHaskell #-}
import LambdaPrint

y :: a -> a
y = \a -> a
$(return []) --workaround for GHC 7.8+

test = $(showDef 'y)

结果基本可读，不包括完全限定名称：

*Main> test
"Main.y :: forall a_0 . a_0 -> a_0"

关于正在发生的事情，简要说明一下。 showDef 是一个宏函数，它将环境中某个名称的定义具象化，并在字符串文字表达式中进行漂亮的打印。要使用它，您需要引用lambda的名称（使用'），并将结果（即引用的字符串表达式）插入到某个表达式中（使用$(...)）。

- Yuuri

---

很抱歉，但我的解决方案似乎是错误的。reify变量声明实际上并不包含其定义，因此showDef仅显示类型。这就是有关主体的文档所说的：“目前，该值始终为Nothing：由于缺乏兴趣，尚未实现返回RHS。” - Yuuri