Forth 情報

個人的 Forth 情報の更新版。

実装するための情報

講義録。詳しくてとてもよい。

Forth の有用/有名な文章

まとめ

処理系など

アセンブラ

関係代数(3)

Template Haskell でコード生成を行うようにしたので、関係演算の実装に戻る。

project 演算は、集合に対する演算と見なせば以下のように単純に実装できる。

project :: (Eq a, Eq b) => (a -> b) -> R a -> R b
project f (R s) = R (S.map f s)

実例は以下の通り。

>>> :t suppliers
suppliers :: R (T4 SNO NAME Integer [Char])
>>> project (\ (T4 x y _ _) -> T2 x y) suppliers
SNO:THRelational.SNO SNAME:THRelational.NAME
--------------------------------------------
S1 Smith
S2 Jones
S3 Blake
S4 Clark
S5 Adams

Tutorial D では、もっと簡潔に SUP { SNO, SNAME} と書ける。

Raspberry Pi

購入。

無線LAN

資料

Template Haskell の例

追記: さらに更新(6/23)。
追記: ちょっと更新。

Template Haskell を以下のように進めている。

  • 生成したいボイラープレートの一部を書き下し、コンパイルが通ることを確認する。
  • インデントによるレイアウト規則を使っている場合は、次に行う構文木の調査のために、波括弧とセミコロンで書き直しておく。
  • 生成したいコードを runQ に渡し、構文木を調べる。
  • 出力された構文木の構造を調べる。
  • 出力された構文木をそのまま返す関数を、サンプルとして書く。
  • コンパイルが通ることを確認したら、生成したいボイラープレートを意識しつつ、リファクタリングする。
  • ボイラープレートを無くす。

以下は実例。

  • 生成したいボイラープレートの一部を書き下し、コンパイルが通ることを確認する。
-- 例。この T1 以外に引数が 2つの T2 a b,3つの T3 a b cと多数の類似のコードがあり、TH で生成したい。
instance (Typeable a, Show a) => Tuple (T1 a)
    where 
      heading (T1 (A a _)) = [a]
      amap f (T1 (A a x)) = T1 (A (f a) x)
      tvalue (T1 (A _ x)) = [show x]
      degree _ = 1
      typeNames (T1 (A _ x)) = [typeOf x]
  • インデントによるレイアウト規則を使っている場合は、次に行う構文木の調査のために、波括弧とセミコロンで書き直しておく。
instance (Typeable a, Show a) => Tuple (T1 a) where { heading (T1 (A a _)) = [a] ; amap f (T1 (A a x)) = T1 (A (f a) x); tvalue (T1 (A _ x)) = [show x]; degree _ = 1; typeNames (T1 (A _ x)) = [typeOf x];}
  • 生成したいコードを runQ に渡し、構文木を調べる。この際、コードはオックスフォード角括弧と呼ばれるカッコで囲む。必要なコードの種別に応じたカッコを用いる必要があり、今回の場合はトップレベルの宣言なので d を使う。構文木は Q [Dec] 型となる。
>>> :t [d| instance (Typeable a, Show a) => Tuple (T1 a) where { heading (T1 (A a _)) = [a] ; amap f (T1 (A a x)) = T1 (A (f a) x); tvalue (T1 (A _ x)) = [show x]; degree _ = 1; typeNames (T1 (A _ x)) = [typeOf x];} |]
[d| instance (Typeable a, Show a) => Tuple (T1 a) where { heading (T1 (A a _)) = [a] ; amap f (T1 (A a x)) = T1 (A (f a) x); tvalue (T1 (A _ x)) = [show x]; degree _ = 1; typeNames (T1 (A _ x)) = [typeOf x];} |]
  :: Q [Dec]

>>> runQ [d| instance (Typeable a, Show a) => Tuple (T1 a) where { heading (T1 (A a _)) = [a] ; amap f (T1 (A a x)) = T1 (A (f a) x); tvalue (T1 (A _ x)) = [show x]; degree _ = 1; typeNames (T1 (A _ x)) = [typeOf x];} |]
[InstanceD [ClassP Data.Typeable.Typeable [VarT a_0],ClassP GHC.Show.Show [VarT a_0]] (AppT (ConT RT.Tuple) (AppT (ConT RT.T1) (VarT a_0))) [FunD heading [Clause [ConP RT.T1 [ConP TH.A [VarP a_1,WildP]]] (NormalB (ListE [VarE a_1])) []],FunD amap [Clause [VarP f_2,ConP RT.T1 [ConP TH.A [VarP a_3,VarP x_4]]] (NormalB (AppE (ConE RT.T1) (AppE (AppE (ConE TH.A) (AppE (VarE f_2) (VarE a_3))) (VarE x_4)))) []],FunD tvalue [Clause [ConP RT.T1 [ConP TH.A [WildP,VarP x_5]]] (NormalB (ListE [AppE (VarE GHC.Show.show) (VarE x_5)])) []],FunD degree [Clause [WildP] (NormalB (LitE (IntegerL 1))) []],FunD typeNames [Clause [ConP RT.T1 [ConP TH.A [WildP,VarP x_6]]] (NormalB (ListE [AppE (VarE Data.Typeable.typeOf) (VarE x_6)])) []]]]
  • 出力された構文木をそのまま返す関数(ここでは仮に defT1Ex :: Q [Dec]とする)を、サンプルとして書く。GHC の制限で、トップレベルの宣言は import されなければならないので、構文木を返す関数は、利用するファイルとは別のファイルに書いておく。また、構文木に以下の修正を行なう。
    • a_0 や a_1, f_1 などの名前は mkName で作った Name データにおきかえる。※変数名のキャプチャに注意。newName を使う方法がより正しい。
    • ライブラリ関数や型名も mkName で作った Name データにおきかえる。ただし、mkName "GHC.Show.Show" ではうまくいかない。 mkName "Show" とする。
-- コード生成を定義しているファイル x.hs
defT1Ex :: Q [Dec]
defT1Ex = return defT1Ex'
defT1Ex' =
    [InstanceD
     [ClassP typeable [VarT a_0], ClassP showClass [VarT a_0]] -- Cxt
     (AppT (ConT tuple) (AppT (ConT t1) (VarT a_0))) -- Type
     [
      FunD (mkName "heading") [Clause [ConP t1 [ConP conA [VarP a_1, WildP]]] (NormalB (ListE [VarE a_1])) []],
      FunD (mkName "amap") [Clause [VarP f_2,ConP t1 [ConP conA [VarP a_3,VarP x_4]]] (NormalB (AppE (ConE t1) (AppE (AppE (ConE conA) (AppE (VarE f_2) (VarE a_3))) (VarE x_4)))) []],
      FunD (mkName "tvalue") [Clause [ConP t1 [ConP conA [WildP,VarP x_5]]] (NormalB (ListE [AppE (VarE showFunc) (VarE x_5)])) []],
      FunD (mkName "degree") [Clause [WildP] (NormalB (LitE (IntegerL 1))) []],
      FunD (mkName "typeNames") [Clause [ConP t1 [ConP conA [WildP,VarP x_6]]] (NormalB (ListE [AppE (VarE typeof) (VarE x_6)])) []]]
    ]
    where
      conA = mkName "A"
      showClass = mkName "Show"
      showFunc = mkName "show"
      typeable = mkName "Data.Typeable.Typeable"
      typeof = mkName "Data.Typeable.typeOf"
      tuple = mkName "Tuple"
      t1 = mkName "T1"
      a_0 = mkName "a_0"
      a_1 = mkName "a_1"
      a_2 = mkName "a_2"
      a_3 = mkName "a_3"
      f_1 = mkName "f_1"
      f_2 = mkName "f_2"
      x_4 = mkName "x_4"
      x_5 = mkName "x_5"
      x_6 = mkName "x_6"


-- コード生成を利用するファイル y.hs
...
$(defT1Ex)
-- トップレベル宣言は $() は省略可能で、 defT1Ex と書いてもよい。
...
    • ppr 関数を使うと、展開形を出力できるので適宜用いて確認する。
>>> ppr defT1Ex'
instance (Data.Typeable.Typeable a_0, Show a_0) => Tuple (T1 a_0)
    where heading (T1 (A a_1 _)) = [a_1]
          amap f_2 (T1 (A a_3 x_4)) = T1 (A (f_2 a_3) x_4)
          tvalue (T1 (A _ x_5)) = [show x_5]
          degree _ = 1
          typeNames (T1 (A _ x_6)) = [Data.Typeable.typeOf x_6]
    • ppr 関数は Q モナドに対してはそのままは使えない。runQ で実行したのち pprint する関数 expand を作っておくと簡単に展開形を確認できる。
expand x = runQ x >>= putStrLn . pprint
  • コンパイルが通ることを確認したら、生成したいボイラープレートを意識しつつ、リファクタリングする。どう生成したらいいか不明な場合は、サンプルを増やして確認する。複雑な構文木を作る場合は、単純化するために別の関数として切り出すと間違えにくい。
    • リファクタリング時には等価な、より生成しやすい単純な式に変形することを考える。
      • 引数が一つより多い場合の関数適用、たとえば f x0 x1 x2 は (((f x0) x1) x2) である。foldl を使うと簡単に作成できる。
>>> runQ [d| f x0 x1 x2 = (((f x0) x1) x2) |]
[FunD f [Clause [VarP x0_9,VarP x1_10,VarP x2_11] (NormalB (AppE (AppE (AppE (VarE f) (VarE x0_9)) (VarE x1_10)) (VarE x2_11))) []]]

>>> FunD (mkName "f") [Clause (map (\x -> VarP (mkName ("a" ++ show x))) [1..3]) (NormalB (foldl AppE (VarE (mkName "f")) (map (\x -> VarE (mkName ("a" ++ show x))) [1..3]))) []]
FunD f [Clause [VarP a1,VarP a2,VarP a3] (NormalB (AppE (AppE (AppE (VarE f) (VarE a1)) (VarE a2)) (VarE a3))) []]
>>> ppr it
f a1 a2 a3 = f a1 a2 a3
    • where 句を使うことで単純にできる場合がある。
  • ghci にオプション -ddump-splices を付けると、splice 時に展開結果を出力してくれる。
  • ボイラープレートを無くす。

ボイラープレートを生成する関数としてまとめ、不要となったボイラープレートを削除する。

参考資料

関係代数(2)

属性、タプル、リレーショナルを以下のように実装した。いまのところ、５つの属性からなるタプルまでしか実装していない。

type Attr = String
-- | Attribute
data A a = A Attr a deriving (Eq, Show)
-- | Tuple
data T1 a = T1 (A a) deriving (Eq, Show)
data T2 a b = T2 (A a) (A b) deriving (Eq, Show)
data T3 a b c = T3 (A a) (A b) (A c) deriving (Eq, Show)
data T4 a b c d = T4 (A a) (A b) (A c) (A d) deriving (Eq, Show)
data T5 a b c d e = T5 (A a) (A b) (A c) (A d) (A e) deriving (Eq, Show)
-- | Relational
data R a = R (Set a) deriving (Eq)

このデータ型に対する関係演算(restrict, join)は以下のように素直に定義できた。

restrict :: (a -> Bool) -> R a -> R a
restrict f (R s) = R (S.filter f s)
rJoin :: (Eq a, Eq b, Eq c) => (a -> b -> Maybe c) -> R a -> R b -> R c
rJoin f (R x) (R y) = R (S.fromList (catMaybes [f a b | a <- elems x, b <- elems y]))

例えば、(部署番号、部署名、予算) からなる関係 DEPTS と、(従業員番号、氏名、部署番号、給与）からなる関係 EMPS に対して、以下のような演算が行える。DNO は DNO String で定義されるデータ型であるため、単純に文字列との比較は出来ない点に注意。このような型に厳密な演算は、 Tutorial D では（煩雑、ではなく）長所と考えられているようだ。

*Relational> :t depts
depts :: R (T3 DNO NAME BUDGET)
*Relational> depts
DNO DNAME BUDGET
----------------
D1 Marketing 10M
D2 Development 12M
D3 Research 5M

-- SELECT * FROM DEPTS WHERE DNO = "D3" に相当

*Relational> restrict (\ (T3 dno _ _) -> dno == (A "DNO" (DNO "D3"))) depts
DNO DNAME BUDGET
----------------
D3 Research 5M

*Relational> emps
ENO ENAME DNO SALARY
--------------------
E1 Lopez D1 40K
E2 Cheng D1 42K
E3 Finzi D2 30K
E4 Saito D2 35K

-- SELECT D.DNAME, E.ENAME FROM DEPTS D, EMPS E WHERE D.DNO = E.DNO に相当
*Relational> rJoin deptJoin depts emps
DNAME ENAME
-----------
Marketing Lopez
Marketing Cheng
Development Finzi
Development Saito

ここで、deptJoin 関数は以下のように定義している。

deptJoin (T3 dno dname budget) (T4 eno ename dno' salary)
    | dno == dno' = Just (T2 dname ename)
    | otherwise = Nothing

TODO

  • Tutorial D では、ナチュラルジョインは属性名で自動的に行われるため、 EMPS JOIN DEPTS のような簡潔な表記ができる。
  • Tutorial D では、上記の実現のため、属性名を RENAME する機能を持つ。

関係代数(1)

Haskell の練習に関係代数を実装しよう。

関係代数は強い静的型ととても相性が良さそうだ。データ構造は色々な定義ができそうだけど、可能な限り、シンプルに行こう。
以下はまだ試行錯誤中のデータ構造。

-- 'Database in Depth', Chapter Two.
-- Suppliers
data SNO = SNO String deriving (Eq, Show, Ord)
theSNO (SNO x) = x
data NAME = NAME String deriving (Eq, Show, Ord)

type S = (SNO, NAME, Integer, String)

suppliers = 
    fromList [ ((SNO "S1"), (NAME "Smith"), 20, "London"),
               ((SNO "S2"), (NAME "Jones"), 10, "Paris"),
               ((SNO "S3"), (NAME "Blake"), 30, "Paris"),
               ((SNO "S4"), (NAME "Clark"), 20, "London"),
               ((SNO "S5"), (NAME "Adams"), 30, "Athens")
             ] :: Set S

参考

quickCheck 英文生成

英文生成

PAIP (Paradigms of Artificial Intelligence Programming) の第２章 「簡単な Lisp プログラムの例」では、ランダムな英文を生成するプログラムを取り上げています。勉強のため、この英文生成プログラムを Haskell で書いてみました。コードは以下に置きました。

正攻法

PAIP ではまず、Lisp の関数と（小さな）英文法を直接対応させた解が示されます。これを直接 Haskell に翻訳したのが simple.hs です。Haskell は純粋関数型言語のため、Lisp のように気軽にランダムな要素を返す関数は書けません。ここでは quickCheck の elements 関数を用い、Gen String 型の関数としました。実際にランダムな要素を生成するには sample または sample' 関数を用います。sample2.hs は同じ内容を liftM2 を使って書いたものです。

ルールベース

PAIP では次に、直接 Lisp 関数を書く自由度の低いやり方から、ルールベースのより柔軟性のあるやり方を示します。これはデータとして英文生成ルールを持たせ、プログラムはこのルールを参照して動作するやり方です。Lisp では、シンボルとリストで非常に分かりやすく、直接的にルールを表現することができます。
このルールベースの Haskell 版が rule.hs です。試行錯誤した結果のため、Lisp 版とだいぶ違っています。PAIP で示されている同じルールを用いて木を生成する例も含めています。