simple-reflect

debug

• simple-reflect on Hackage

• twanvl/simple-reflect

• Simple reflection of expressions

特徴

• I will call this module SimpleReflect, since this is a poor mans form of reflection, converting code back to expressions at run time.

コードリーディング

class Show a where
 show x = shows x ""
  
shows :: (Show a) => a -> ShowS
shows = showsPrec 0

showString :: String -> ShowS
showString = (++)

Expr

-- | A reflected expression
data Expr = Expr
   { showExpr   :: Int -> ShowS  -- ^ Show with the given precedence level
   , intExpr    :: Maybe Integer -- ^ Integer value?
   , doubleExpr :: Maybe Double  -- ^ Floating value?
   , reduced    :: Maybe Expr    -- ^ Next reduction step
   }
   
emptyExpr :: Expr
emptyExpr = Expr
  { showExpr   = \_ -> showString ""
  , intExpr    = Nothing
  , doubleExpr = Nothing
  , reduced    = Nothing
  }

Show インスタンス

instance Show Expr where
  showsPrec p r = showExpr r p

var

var :: String -> Expr
var s = emptyExpr { showExpr = \_ -> showString s }

  var "x"
= emptyExpr { showExpr = \_ -> showString "x" }
= Expr
    { showExpr   = \_ -> showString "x"
    , intExpr    = Nothing
    , doubleExpr = Nothing
    , reduced    = Nothing
    }
    
-- この値を表示すると
= show (Expr { showExpr = \_ -> showString "x" })
= shows (Expr { showExpr = \_ -> showString "x" }) ""
= showsPrec 0 (Expr { showExpr = \_ -> showString "x" }) ""
= showExpr (Expr { showExpr = \_ -> showString "x" }) 0 ""
= (\_ -> showString "x") 0 ""
= showString "x" ""
= "x" ++ ""
= "x"

実行結果

*Debug.SimpleReflect> var "x"
x

lift

• var とほぼ同じだけど Show クラスのインスタンスである型を Expr に持ち上げれる

lift :: Show a => a -> Expr
lift x = emptyExpr { showExpr = \p -> showsPrec p x }

lift "x"
= emptyExpr { showExpr = \p -> showsPrec p x }
= Expr
    { showExpr   = \p -> showsPrec p "x"
    , intExpr    = Nothing
    , doubleExpr = Nothing
    , reduced    = Nothing
    }
    
-- この値を表示すると
= show (Expr { showExpr = \p -> showsPrec p "x" })
= shows (Expr { showExpr = \p -> showsPrec p "x" }) ""
= showsPrec 0 (Expr { showExpr = \p -> showsPrec p "x" }) ""
= showExpr (Expr { showExpr = \p -> showsPrec p "x" }) 0 ""
= (\p -> showsPrec p "x") 0 ""
= showsPrec 0 "x" ""  -- ここが var とは違って、文字列のShowインスタンスとなる
= "\"x\""

実行結果

*Debug.SimpleReflect> lift "x"
"x"

FromExpr

QuickCheck の Fun と同じような感じの定義

-- | Conversion from @Expr@ to other types
class FromExpr a where
  fromExpr :: Expr -> a

instance FromExpr Expr where
  fromExpr = id

instance (Show a, FromExpr b) => FromExpr (a -> b) where
  fromExpr f a = fromExpr $ op InfixL 10 " " f (lift a)

Expr は引数を取る場合があるため、3つ目のインスタンス宣言が必要

f0 :: Expr
f1 :: a1 -> Expr
f2 :: a1 -> a2 -> Expr
...
fn :: a1 -> a2 -> ... -> an -> Expr

もっと具体的に Int -> Expr で考えればこうなる

instance FromExpr (Int -> Expr) where
  fromExpr :: Expr -> (Int -> Expr)
  fromExpr expr arg1 = fromExpr $ op InfixL 10 " " expr (lift arg1)

• op InfixL 10 " " が関数適用を表している部分

• lift 関数によって Show クラスのインスタンスとなる型を Expr に持ち上げている

同様に2引数の関数の場合も考える Int -> String -> Expr

instance FromExpr (Int -> String -> Expr) where
  fromExpr :: Expr -> (Int -> (String -> Expr))
  fromExpr expr arg1 arg2
    = (fromExpr $ op InfixL 10 " " expr (lift arg1)) arg2
    -- expr2 = op InfixL 10 " " expr (lift arg1)
    = fromExpr expr2 arg2

fun

-- | A generic, overloaded, function variable
fun :: FromExpr a => String -> a
fun = fromExpr . var

使い方

*Debug.SimpleReflect> fun "x" :: Expr
x
*Debug.SimpleReflect> fun "x" 1 :: Expr
x 1
*Debug.SimpleReflect> fun "x" 1 "b" True :: Expr
x 1 "b" True

*Debug.SimpleReflect> foldr (fun "f") (var "x") [1..5]
f 1 (f 2 (f 3 (f 4 (f 5 x))))

foldr が良い感じに動く理由は Expr に飛ばした結果を良い感じに表示してるから

既に定義されているアルファベット

f,g,h は関数、それ以外のアルファベット一文字は変数としてライブラリ側で定義されている。

具体例

ghci

*Debug.SimpleReflect> foldr (+) x [0..10]
0 + (1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9 + (10 + x))))))))))

*Debug.SimpleReflect> foldr (+) (lift 0) [0..10]
0 + (1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9 + (10 + 0))))))))))

*Debug.SimpleReflect> sum [1..5] :: Expr
0 + 1 + 2 + 3 + 4 + 5

reduction 関数を使えば簡約列を全て表示することができる

ghci

*Debug.SimpleReflect> mapM_ print . reduction $ foldl (*) 1 [1..5]
1 * 1 * 2 * 3 * 4 * 5
1 * 2 * 3 * 4 * 5
2 * 3 * 4 * 5
6 * 4 * 5
24 * 5
120

*Debug.SimpleReflect> mapM_ print . reduction $ foldr (*) 1 [1..5]
1 * (2 * (3 * (4 * (5 * 1))))
1 * (2 * (3 * (4 * 5)))
1 * (2 * (3 * 20))
1 * (2 * 60)
1 * 120
120

問題点

遅延評価が上手く反映されない

ghci

# 短絡評価されるので値を返す
Prelude> foldr (||) True (repeat True)
True

# 止まらない
*Main> foldr (&&) False (repeat True)
...

リストは上手く処理できているので実装の問題かも。

ghci

Prelude> take 5 $ iterate f x
[x,f x,f (f x),f (f (f x)),f (f (f (f x)))]