無駄と文化

実用的ブログ

Haskellでλ計算のインタプリタを作っていこう ~ その2. パーザ

f:id:todays_mitsui:20171008025323p:plain


引き続き Mogul という名前のλ計算インタプリタを作っていこうと思います。
前回、λ式を表現するデータ型を定義したので、今回はパーザを書きます。ソースコードを読ませて抽象構文木を生成するところまでです。

ソースコード全体は GitHub に置いておきます。

github.com


Mogul の構文

パーザを書くにあたってまずは構文を決めなければいけません。
Mogul の構成要素で重要なのは 変数, 関数抽象, 関数適用 そして 関数定義 です。ぞれぞれ以下のような構文にしようと思います。


変数

変数の構成要素として許される文字は 英数字 + アンダースコア _ です。
ただし、英小文字は必ず1文字で一つの変数として解釈されます。英大文字, 数字, アンダースコアは複数連なっていればまとめて一つの変数だと解釈されます。


いくつかの例を挙げましょう、
axFOOFOO_2 は全て正しい変数名と解釈されます。

xy と書いた場合、これは二つの変数 xy が連続したものだと解釈されます。同様に Foo は三つの変数 F, o, o が連続したものだと解釈されます。

驚くべきことに(?)、_42 なども変数名として正しいと解釈されます。
常識的なプログラミング言語では 42 と書くと整数リテラルだと解釈されるでしょう。しかし幸か不幸かλ計算の世界に整数などというものは存在しません。なので 42 のように整数っぽく見えるものでも変数名として許してしまいます。


関数抽象

関数抽象は {\lambda x . M} をほぼそのまま書けるようにします。唯一の違いは λ の代わりに ^ を使うことです。

^x.M

と書くと、 {\lambda x . M} のことだと解釈されます。


また、λ計算の世界には1変数関数しか存在しないので、複数の引数をもとに計算を行いたい場合には、

{
  \lambda (x, y). M \Rightarrow \lambda x. ( \lambda y. M )
}

という感じで カリー化 を行います。
もちろん Mogul でも全ての関数は1変数関数として扱われますが、ネストした関数抽象のために以下のような糖衣構文を許すことにします。

^x y z.M

これは ^x.^y.^z.M と書いたのと同じように解釈されます。


関数適用

前回の記事でも宣言したとおり、関数適用には Unlambda 記法を採用します。
すなわち xy を適用するときは、バッククォート ` を使って

`xy

と書くことにします。


関数定義

関数定義の構文はこうです、

FLIP = ^f.^x.^y.``f y x

左辺に関数名、右辺に関数の本体を置き、左辺と右辺をイコール = でつなぎます。
また、左辺に 仮引数 を伴った書き方も許すことにします。

```FLIP f x y = ``f y x

または間を取った以下のような書き方も正しいです。

`FLIP f = ^x.^y.``f y x


実はこれら三つの書き方には別の意味を持たせようと思っています。前回の記事にも出た アリティ(項数) の概念です。
ひとまず今は 仮引数を左辺に置くか右辺に置くかによって別の構文木を生成させる ということだけ頭の片隅に置いてもらえれば大丈夫です。


コメント

ついでに、Mogul ではラインコメントを書けるようにします。
コメントとして扱われるのは # から行末までです。Python や Ruby と同じですね。

# 引数の適用順を入れ替える
`FLIP f = ^x.^y. ``f y x  # この部分はコメントです

ブロックコメント(複数行コメント)はありません。


BNF

というわけで、Mogul の構文を BNF で書き下すと、

# 識別子
<lower>            ::= "a" | ... | "z"
<upper>            ::= "A" | ... | "Z"
<digit>            ::= "0" | ... | "9"
<identifier>       ::= <lower> | (<upper> | <digit> | "_")+

# λ式
<var>              ::= <identifier>
<lambda>           ::= "^" (<identifier>)+ "." <expr>
<apply>            ::= "`" <expr> <expr>
<expr>             ::= <var> | <lambda> | <apply>

# 関数定義
<func_name>        ::= <identifier>
<param>            ::= <identifier>
<ident_and_params> ::= <func_name> | "`" <ident_and_params> <param>
<def>              ::= <ident_and_params> "=" <expr> EOL

# コンテキスト (関数定義の組)
<context>          ::= (<def>)*

このようになりますね。

これをもとにパーザを書いていきましょう。


使用するライブラリ

パーザコンビネータのライブラリとして、おなじみの parsec3 を使います。
Applicative スタイルで行を節約しながら書けるのがいい感じです。

今回は Text 型のストリームを読みながら抽象構文木に変換していくので、 Text.Parsec.Text をインポートします。


パーザを書く

書いていきましょう。


識別子

-- | 識別子
ident :: Parser Ident
ident = ident' <|> ident''

ident' :: Parser Ident
ident' = Ident . singleton <$> lower

ident'' :: Parser Ident
ident'' = Ident . pack <$> many1 (upper <|> digit <|> char '_')

途中に登場している singletonpack は、それぞれ Data.Text.singletonData.Text.pack です。


λ式

λ式は 変数, 関数抽象, 関数適用 の組み合わせで再帰的に定義されるので、それをそのままコードに落とし込みます。

-- | λ式
expr :: Parser Expr
expr = apply <|> lambda <|> var

-- | 変数
var :: Parser Expr
var = Var <$> ident

-- | 関数抽象
lambda :: Parser Expr
lambda = do
    token $ char '^'
    v  <- token ident
    vs <- many $ token ident
    token $ char '.'
    e  <- token expr
    return $ mkLambda (v:vs) e
  where
    mkLambda vs e = foldr (:^) e vs

-- | 関数適用
apply :: Parser Expr
apply = do
    token $ char '`'
    e  <- token expr
    e' <- token expr
    return $ e :$ e'

実はここでも Unlambda 記法を採用することのメリットが発揮されていて。Unlambda 記法だと varlambdaapply の動作が互いに排他になります。なので Text.Parsec.Prim.try を使う必要がなくなって、コードがシンプルになり、頭の中で動作も追いやすくなってます。


関数定義

このパートでは関数名(Ident)と無名関数(Func)のタプルを取り出すことがゴールです。

-- | 関数定義の左辺部 "```f x y z" の形だけを許す
defFunc :: Parser (Ident, [Ident])
defFunc = defFunc' <|> do
    funcName <- token ident
    return (funcName, [])

defFunc' :: Parser (Ident, [Ident])
defFunc' = do
    token $ char '`'
    (funcName, args) <- token defFunc
    arg <- token ident
    return (funcName, arg:args)

-- | 関数定義
def :: Parser (Ident, Func)
def = do
    (funcName, reversedArgs) <- token defFunc
    token $ char '='
    e <- token expr
    spaces'
    skipMany lineComment
    void endOfLine <|> eof
    return (funcName, Func (reverse reversedArgs) e)

def の do 構文の中でなんだか汚いことやってますね。
関数定義は複数行に渡ってもよくて、かつ、どこかの行末で終わるはずで、さらに、ここでついでにラインコメントを読み飛ばそうとしているのでめっちゃ汚くなってます。

この部分を見通しよくするには、まずソースコードを lexer に通してコメントを読み飛ばしながらトークン列に変換して、次の段階でトークン列を parser に通して抽象構文木に変換するような実装にすればいいはずです。
が、この部分以外は lexer と parser に分けるまでもないくらいにシンプルなので作り込むのが面倒なんですよね。

ま、ちゃんと動いてますよ。一応テストも書いているし。


コンテキスト

コンテキストとは複数の関数定義の集まりです。
実装上では関数名(Ident)と無名関数(Func)の Map になっています。

-- | コンテキスト (関数定義の組)
context :: Parser Context
context = Map.fromList <$> many1 def

def が関数名と無名関数のタプルを返すようにしたので、many1 で複数個取ってきてから Data.Map.fromList に食わせるだけですね。

ここで many ではなく many1 を使った理由としては、...不明です。
ここなんで敢えて many1 を使っているんだろう。これだと空の文字列を読ませたときにパースエラーになりますね。このコード書いたのがざっくり2年前なので意図を忘れました。ここは後々書き換えるかも知れません。


使ってみる

実際にパーザにコードを読ませて抽象構文木を作ってみましょう。

ghci> parse expr "" "``skk"
Right ((Var (Ident "s") :$ Var (Ident "k")) :$ Var (Ident "k"))

ghci> parse expr "" "^xy.`yx"
Right (Ident "x" :^ (Ident "y" :^ Var (Ident "y") :$ Var (Ident "x")))

ghci> parse expr "" "````s`k`sika^x.`xx"
Right ((((Var (Ident "s") :$ (Var (Ident "k") :$ (Var (Ident "s") :$ Var (Ident "i")))) :$ Var (Ident "k")) :$ Var (Ident "a")) :$ (Ident "x" :^ Var (Ident "x") :$ Var (Ident "x")))

いい感じですね。

関数定義のほうも試してみます。

ghci> parse def "" "I = ^x.x"
Right ( Ident "I"
      , Func {
            args     = []
          , bareExpr = Ident "x" :^ Var (Ident "x")
      })

読みやすいように整形してみました。
ちゃんと 関数名 Ident "I" と 無名関数 Func {args = [], bareExpr = Ident "x" :^ Var (Ident "x")} のタプルが返ってきてますね。


仮引数を左辺に置くか右辺に置くかによって別の構文木を生成させる と云ってた件、試してみます。

ghci> parse def "" "FLIP = ^f.^x.^y.``f y x"
Right ( Ident "FLIP"
      , Func {
            args     = []
          , bareExpr = Ident "f" :^ (Ident "x" :^ (Ident "y" :^ (Var (Ident "f") :$ Var (Ident "y")) :$ Var (Ident "x")))
      })

ghci> parse def "" "```FLIP f x y = ``f y x"
Right ( Ident "FLIP"
      , Func {
            args     = [Ident "f",Ident "x",Ident "y"],
            bareExpr = (Var (Ident "f") :$ Var (Ident "y")) :$ Var (Ident "x")
      })

ghci> parse def "" "`FLIP f = ^x.^y.``f y x"
Right ( Ident "FLIP"
      , Func {
            args     = [Ident "f"]
          , bareExpr = Ident "x" :^ (Ident "y" :^ (Var (Ident "f") :$ Var (Ident "y")) :$ Var (Ident "x"))
      })

関数定義の左辺に置いた仮引数は Func 型の args フィールドの中で保持しています。
今のところの狙いは 左辺にいくつの仮引数が置かれていたかデータ型覚えておくこと です。


まとめ

Mogul の構文を整理しつつ、対応するパーザを書いてきました。
今回見せたパーザは何度も書き直しつつ洗練させてきたものなので少しは読みやすく書けてるんじゃないかと自負しております。

ソースコードを読んで抽象構文木を作れるようになったので、次回は プリティプリンタ を書いて抽象構文木をうまく印字できるようにします。


私からは以上です。

Haskell でλ計算のインタプリタを作っていこう ~ その1. データ型

f:id:todays_mitsui:20171008025323p:plain


Haskell ネタです。
先日の記事で宣言したとおり、λ計算のインタプリタを作っていこうと思います。

ソースコード全体は GitHub に置いておきます。

github.com

プロジェクト名は Mogul (モーグル) 。
なので作っていくインタプリタの名前も Mogul です。


全体的な注意

このシリーズではλ計算の理論を Haskell で実装していきます。ある程度 Haskell が読み書きでき、かつ、型無しλ計算にある程度親しんでいる人を読者として想定しています。


関数適用の記法には Unlambda記法 を採用しています。が、これはあまり一般的ではないため面食らうかも知れません。

Unlambda記法とは何でしょうか。
関数 f を 引数 x で呼び出すとき、C 言語などでは f(x) と書きます。Haskell では f x ですね。Unlambda 記法ではこれを `fx と書きます。関数適用のための ` という演算子を ポーランド記法 で書いていると思うと理解しやすいかも知れません。
Unlambda 記法には 括弧 () を使わずにあらゆる式が書ける というメリットがあります。が、今回の採用にあたっていちばんの決め手になったのは 筆者が書き慣れているから です。ご了承ください。

その他、解説に使う用語や記号はなるべくλ計算・計算論・関数型プログラミングの分野で一般的なものに統一していくつもりです。


一応以下に参考サイトと参考文献を挙げてみます。

では行ってみましょう。


データ構造

Haskell らしく最初はデータ型の定義から始めます。
今回 Mogul でやろうとしていることを簡単に云ってしまうと λ式を良い感じに β 簡約していく ってな感じなので、まず定義するべきはなんと云っても λ式 です。

結論から見せましょう、データ型の定義はこのようにしました。

import Data.Text

-- | 識別子
data Ident = Ident Text
  deriving (Eq, Ord, Show, Read)

-- | λ式
data Expr = Var Ident      -- 変数
          | Ident :^ Expr  -- 関数抽象
          | Expr  :$ Expr  -- 関数適用
  deriving (Eq, Show, Read)

infixl 9 :$
infixr 7 :^

解説を加えます。

『計算論 計算可能性とラムダ計算』 の第2章「λ計算の基礎」から引用すると、λ式は以下のように再帰的に定義される式です。

  1. 変数 {x_0, x_1, \cdots} はそれ単体でλ式である
  2. {M} がλ式で {x} が変数のとき {\lambda x . M} はλ式である (関数抽象)
  3. {M}{N} がλ式のとき {MN} はλ式である (関数適用)

これをそのまま Haskell のコードに落としていけば素朴なデータ型の定義ができそうです。幸いに Haskell の柔軟な表現力によって、定義式をそのままコードに落とすことができました。

ただし、しっかりと型推論の恩恵にあずかるために 識別子としての変数λ式の一部として現れる単体の変数 を別々の型として区別することにしました。前者は identifier (識別子) を略して Ident という型にしました。後者は variable を略した Var :: Ident -> Expr という値構築子で表現します。


λ計算に追加したいもの

ところで、Mogul ではλ計算の系にいくつかの要素を追加したいと考えています。その一つが 関数定義 です。
関数定義とは λ式に名前を付けて複数の場所で使い回してやろう というアイデアです。みなさんが親しんでいるどの言語にも当たり前にありますよね?

関数定義を許すのには二つの狙いがあります。一つは λ式に適当な名前を付けて参照することで可読性を上げられるであろうこと。もう一つは、 λ式に名前を付けたものでコンビネータを表現できるだろう というものです。

例えば S コンビネータ(『ものまね鳥をまねる』で云うところのホシムクドリ)は以下のように定義出来ますが、

```Sxyz = ``xz`yz

これはλ式 ^x.^y.^z.``xz`yzS という名前を付けることと同義です。

というわけで識別子とλ式を Map で紐付けるようなデータ型を定義します。

import Data.Map.Lazy

-- | 無名関数
data Func = Func
    { args     :: [Ident]
    , bareExpr :: Expr
    } deriving (Eq, Show, Read)

-- | 関数定義の集合
type Context = Map Ident Func

無名関数を表す Func 型を定義した上で、 Map Ident Func によって識別子と関数を対応付けています。
なぜ素朴に type Context = Map Ident Expr とせずに、わざわざ Func 型を定義するかというと、それは アリティ を考慮したいからなのですが。それは、まぁ、β簡約を実装するときにでもあらためて触れましょう。


λ式の同値性

話は少し戻りますが、 Expr の定義で deriving (Eq) として Eq クラスのインスタンスを自動導出していることに注目してください。
deriving 句は便利ですが、Eq クラスのインスタンス定義を自動導出してしまうと意味的には等しいはずの {\lambda x . x}{\lambda y . y}等しくない ということになってしまいます。

-- | ^x.x == ^y.y ?
Ident "x" :^ Var (Ident "x") == Ident "y" :^ Var (Ident "y")
  -- => False

ご存知の通り、α変換 のアイデアで云えば、上記の {\lambda x . x}{\lambda y . y} は同じ関数を表しているはずです。これらの式を比べたとき等しくなるようにするには (==) の定義にα変換のアイデアを持ち込まなければいけません。
これが結構厄介で、上手い実装はないかと長らく考えあぐねていたところに @dif_engine さまから「 ド・ブラン・インデックス を使わない手はないだろう」というアドバイス(空リプ)をいただきました。

ド・ブラン・インデックスを使うと束縛変数の名前( xy など)が表現から完全に消えてしまい、 {\lambda x . x}{\lambda y . y} も同じ {\lambda . 1} という表記で書けるようです。なるほどこれなら複雑なα変換のロジックを持ち出すまでもなく、より賢い (==) の定義が書けそうです。

というわけで、 Expr の定義を以下のように変更しようかと考えています。

type Index = Int

data Expr = Var (Maybe Index) Ident  -- 変数
          | Ident :^ Expr            -- 関数抽象
          | Expr  :$ Expr            -- 関数適用
  deriving (Eq, Show, Read)

Var (Maybe Index) Ident として各変数にインデックスを持たせています。
自由変数にはインデックスを振ることができないので Nothing を割り当てます。

たとえば {\lambda x . \lambda y . FOO \ y \ x} という式をデータに落とすと、

Ident "x" :^ Ident "y" :^ Var Nothing "Foo" :$ Var (Just 1) "y" :$ Var (Just 2) "x"

となります。
...という構想をしていますが、まだ実装してテストはしていません。これも追々で。


まとめ

というわけで初回はλ計算の世界を表現するデータ型についてつらつらと書いてきました。
次回は Mogul の文法を紹介しつつパーザ(parser)の実装を眺めていこうと思います。


私からは以上です。