Haskell esegue il debug di un'espressione lambda arbitraria

Question

Ho un set di espressioni lambda che sto passando ad altri lambda. Tutti i lambda fanno affidamento solo sui loro argomenti, non chiamano nessuna funzione esterna. Certo, a volte diventa abbastanza confuso e passerò una funzione con il numero errato di argomenti a un altro, creando un'eccezione GHCi.

Desidero eseguire una funzione di debug che esegua un'espressione lambda arbitraria (con un numero sconosciuto di argomenti) e restituisca una stringa in base alla struttura e alla funzione del lambda.

Per esempio, dire che ho le seguenti espressioni lambda:

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

debug (s k) dovrebbe restituire "\a b -> b"

debug (s s k) dovrebbe restituire "\a b -> a b a" (se ho semplificato che correttamente)

debug s dovrebbe restituire "\a b c -> a c (b c)"

Wha sarebbe un buon modo per farlo?

Answer 1

Penso che il modo per farlo sarebbe definire un piccolo lambda calcolo DSL in Haskell (o utilizzare un'implementazione esistente). In questo modo, invece di usare la formulazione originaria Haskell, si avrebbe scritto qualcosa di simile

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

e allo stesso modo per s e i. Si potrebbe quindi scrivere/utilizzare una funzione di valutazione in modo che si potrebbe scrivere

debug e = eval e 
debug (App s k) 

che darebbe la forma finale nella propria sintassi. Inoltre avresti bisogno di una sorta di interprete per convertire la sintassi DSL in Haskell, in modo che tu possa effettivamente utilizzare le funzioni nel tuo codice.

L'implementazione di questo sembra un lavoro molto complicato, e probabilmente non è esattamente quello che avevate in mente (specialmente se avete bisogno della valutazione per la sintassi digitata), ma sono sicuro che sarebbe un grande imparando esperienze. Un buon riferimento sarebbe chapter 6 of "Write you a Haskell". Usare un'implementazione esistente sarebbe molto più semplice (ma meno divertente :)).

Se questo è solo a scopo di debug, si potrebbe trarre beneficio dall'osservazione della sintassi di base ghc in. Vedi chapter 25 of Real world Haskell, il flag ghc da usare è -ddump-simpl. Ma questo significherebbe guardare il codice generato piuttosto che generare una rappresentazione all'interno del tuo programma. Inoltre, non sono sicuro di quanto sia in grado di identificare facilmente funzioni specifiche nel codice Core (non ho esperienza con questo in modo YMMV).

Ovviamente sarebbe bello se l'uso di show sulle funzioni fornisse il tipo di output che descrivi ma ci sono probabilmente ottime ragioni per cui le funzioni non sono un'istanza di Show (non sarei in grado di dirlo).

Answer 2

In realtà è possibile ottenere ciò utilizzando la stampa carina da Template Haskell, che viene fornito con GHC appena estratto dalla confezione.

primo luogo, la funzione di formattazione devono definire modulo separato (che è una limitazione 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 

Poi usarlo:

{-# LANGUAGE TemplateHaskell #-} 
import LambdaPrint 

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

test = $(showDef 'y) 

Il risultato è più o meno leggibile, senza contare nomi completi:

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

Poche parole su cosa sta succedendo. showDef è una funzione macro che reifica la definizione di un nome dall'ambiente e la stampa in modo corretto in un'espressione letterale stringa. Per usarlo, è necessario citare il nome del lambda (usando ') e unire il risultato (che è un'espressione di stringa tra virgolette) in qualche espressione (usando $(...)).