Haskell debugs arbitrary lambda expression

Question

I have a set of lambda expressions that I pass to other lambdas. All lambdas rely only on their arguments; they do not call any external functions. Of course, sometimes this gets quite confusing, and I will pass the function with the wrong number of arguments to another, throwing a GHCi exception.

I want to make a debugging function that takes an arbitrary lambda expression (with an unknown number of arguments) and returns a string based on the structure and function of the lambda.

For example, let's say I have the following lambda expressions:

i = \x -> x k = \xy -> x s = \xyz -> xz (yz) 

debug (sk) should return "\ab -> b"

debug (ssk) should return "\ab -> aba" (if I simplified this)

debug s should return "\abc -> ac (bc)"

What would be a good way to do this?

Answer 1

I think a way to do this would be to define a small lambda calculus of DSL in Haskell (or use an existing implementation). Thus, instead of using the native Haskell wording, you should 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 . Then you have to write / use a rating function so you can write

 debug e = eval e debug (App sk) 

which will provide you with the final form in your own syntax. Also, to convert your DSL syntax to Haskell, you'll need a kind of interpreter so that you can actually use the functions in your code.

Implementing this seems like a pretty complicated job, and it's probably not exactly what you had in mind (especially if you need an assessment for typed syntax), but I'm sure it will be a great learning experience. A good reference would be chapter 6, "Write to you Haskell . " Using an existing implementation would be a lot easier (but less fun :)).

If this is just for debugging purposes, it might be useful for you to look at the syntax of the main ghc syntax. See Haskell chapter 25 of the real world , the ghc flag to use is -ddump-simple. But that would mean looking for the generated code, not creating a view inside your program. I'm also not sure how easily you could identify certain functions in the base code (I have no experience with this, so YMMV).

Of course, it would be great if the show on functions function would give the kind of output you are describing, but there are probably very good reasons that the functions are not an instance of Show (I could not tell you).

Answer 2

In fact, you can achieve this using the beautiful print from Template Haskell that comes with the GHC out of the box.

Firstly, the formatting function must be defined in a separate module (this is 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 the full names:

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

A few words about what is happening. showDef is a macro function that confirms the definition of a name from the environment and pretty prints it in a string literal. To use it, you need to specify the lambda name (using ' ) and splicing the result (which is the quoted string expression) into some expression (using $(...) ).