Haskell debugging an arbitrary lambda expression

Question

I have a set of lambda expressions which I'm passing to other lambdas. All lambdas rely only on their arguments, they don't call any outside functions. Of course, sometimes it gets quite confusing and I'll pass an function with the incorrect number of arguments to another, creating a GHCi exception.

I want to make a debug function which will take an arbitrary lambda expression (with an unknown number of arguments) and return a string based on the structure and function of the lambda.

For example, say I have the following lambda expressions:

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

debug (s k) should return "\a b -> b"

debug (s s k) should return "\a b -> a b a" (if I simplified that correctly)

debug s should return "\a b c -> a c (b c)"

What would be a good way of doing this?

Answer 1

I think the way to do this would be to define a small lambda calculus DSL in Haskell (or use an existing implementation). This way, instead of using the native Haskell formulation, you would write something like

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

and similarly for s and i. You would then write/use an evaluation function so that you could write

debug e = eval e
debug (App s k)

which would give you the final form in your own syntax. Additionally you would need a sort of interpreter to convert your DSL syntax to Haskell, so that you can actually use the functions in your code.

Implementing this does seem like quite a lot of (tricky) work, and it's probably not exactly what you had in mind (especially if you need the evaluation for typed syntax), but I'm sure it would be a great learning experience. A good reference would be chapter 6 of "Write you a Haskell". Using an existing implementation would be a lot easier (but less fun :)).

If this is merely for debugging purposes you might benefit from looking at the core syntax ghc compiles to. See chapter 25 of Real world Haskell, the ghc flag to use is -ddump-simpl. But this would mean looking at generated code rather than generating a representation inside your program. I'm also not sure to what extent you would be able to identify specific functions in the Core code easily (I have no experience with this so YMMV).

It would of course be pretty cool if using show on functions would give the kind of output you describe but there are probably very good reasons functions are not an instance of Show (I wouldn't be able to tell you).

Answer 2

You can actually achieve that by utilising pretty-printing from Template Haskell, which comes with GHC out of the box.

First, the formatting function should be defined in separate module (that's a TH restriction):

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

Then use it:

{-# LANGUAGE TemplateHaskell #-}
import LambdaPrint

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

test = $(showDef 'y)

The result is more or less readable, not counting fully qualified names:

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

Few words about what's going on. showDef is a macro function which reifies the definition of some name from the environment and pretty-prints it in a string literal expression. To use it, you need to quote the name of the lambda (using ') and splice the result (which is a quoted string expression) into some expression (using $(...)).