rb.blog.pasberth.com

User
@pasberthのRuby系ブログ

文章にするのがめんどい気がするので結論から。

  1. 文字列を単純なトークンの集りに字句解析する
  2. 優先順位の高い演算子から順に 、中置トークンとそのひとつ前のトークン、そしてそのひとつ後ろのトークンを、ひとつのトークンにまとめあげる
    1. このとき、 左結合なら左のトークンから、右結合なら右のトークンから順に 解析する
  3. おわり

次のようなイメージである

文字列

a + b * c + d

トークンの列

a
+
b
*
c
+
d

優先順位の高い中置トークンとその前のトークンをひとつにまとめあげる

a
+
(* b c)
+
d

左結合なら左のトークンから

(+ a (* b c))
+
d

(+ (+ a (* b c)) d)

Clojure で実装するとこんな感じになる

優先順位の解決を、トークン同士の比較や、再帰でおこなうのではなくて、 優先順位の低いものは、優先順位の高いものよりも後に解析される というように考える。

ちなみにこの考えのもとで実装しているパーサが Parsef である

パーサの勉強のために、前回は infixing library を作りましたが、今回は型システムを作ってみます。 Lisp という言語はコード自体がデータとして扱えるので、このようなシステムを作るにはうってつけです。

型システム入門を読みつつ型システムを Lisp のコードに落とし込んでいきます。

今回作ったものは このコミット にあります。

とはいえなんというか、ブログにできることがそんなに多いわけではなく(実装の詳細を日本語にできない)。

まず、型の制約を表すデータを定義します。

(defrecord Constraint [expected actual])
(defrecord Forall [variables expression])
(defrecord Bound [variable])
(defrecord Pair [first second])
(defrecord Arrow [source target])

Forall は変数を導入するデータで、 Bound が束縛変数、 Arrow が関数に相当します。 (Forall. [:a] (Arrow. (Bound. :a) (Bound. :a))) のように使います。

Constraintexpected は期待する型で、 actual が実際の型です。これが同じじゃなかったら型エラーにするわけです。

それから、このデータはまだ人間が扱えるものではありませんから、もうすこし人間が読み書きできるようにマクロを定義してあげます (ここ重要) 。 このあたり に定義があります。

このマクロのおかげで (Forall. [:a] (Arrow. (Bound. :a) (Bound. :a)))(constraint :a -> :a) と書けるようになりました。やったね! (hold :a -> :a) と書くと、 (Constraint. (Forall. [:a] (Arrow. (Bound. :a) (Bound. :a))) (Forall. [:a] (Arrow. (Bound. :a) (Bound. :a)))) に展開してくれます。

そして { 'identity (hold :a -> :a) } のような単純な Map を型システムを表すデータとして扱い、このデータをインタプリトする感じにして型システムを構築します。

とりあえずザッと書いて動きを確かめてみます。

それからいろいろと必要な定義して、 infer-type' 関数で、型システムとコードからコードの型を得るようにします。 ただし、 infer-type' 関数はマクロ展開済みのコードを受け取る必要があります。

というわけで実際に動かしてみるとこんな感じです

うむ、なんかいい感じに推論できてるっぽいので、とりあえずこれでよしとしましょう。

とりあえず型システムを実装してみての雑感は、型システムを実装すると分岐の嵐になるってことです (特に型変数への代入とか)。 多態は分岐の汎用的な形なので、このあたりだと Clojure の Multimethods がわりと活かされてくる気もしました。

昨日、きつねさんでもわかる LLVM が届いたので、 LLVM の練習がてら 作ってみた。コードは以下。

最適化とかは考えていない。 Haskell にも LLVM のためのモジュールはあるけど、一度目だし感覚を掴むためにあまり抽象化されていない感じに作ってみた。

BrainfuckCompiler に Brainfuck のコードを与えて実行すると、 LLVM のインストラクションが書き出される。それを llc などでコンパイルすると実行可能ファイルができあがる。

いいね! こんなふうにいろいろとコンパイラが作れそうな気がしてきた。

体の各部の比率 (大雑把) なメモ

身長を 10 として、

  • 0.75
  • 手首から指先まで 1
  • 1.25
  • 二の腕 1.25
  • 肘から手首まで 1.25
  • 肘から指先まで 2.25
  • 太もも 2.25
  • ふくらはぎ 2.25
  • 胴体 3

  • 太もも + ふくらはぎで 5 (あとかかとの分もある、でもまだ、かかとはよくわからない)

  • 胴体 + 首 + 頭で 5 (足とほぼ同じ)
  • 手は身長の 1/10 くらい
  • 頭の大きさと、二の腕の長さと、肘から手首までの長さはだいたい等しい (身長の1/8くらい)
  • 肘から指先までと、太ももの長さと、ふくらはぎの長さはほぼ同じ (身長の1/5くらい)
  • 胴体はたぶん、手の3倍+αくらい大きい

人間を上下に等分割すると、ちょうど下腹部くらいが境目になる。

ウィトルウィウス的人体図 にはこのあたりの情報が異常に詳しく描かれているらしくとても参考になるっぽい。

tnoda-clojure:

私 Scala な人ですが,Clojure ガチ勢の召喚に期待して書いてみます.


その 1

user=> (def f1 (fn [& xs] (apply + xs)))
#'user/f1 user=> (f1 1 2 3...

GHC 7.6.3 を Mac にインストールしようとしたのだが、いろいろとはまった。 こんな感じ:

ぼくは Mac に Gentoo Prefix をインストールして使っているのだが、どうも libiconv がコンフリクトしているみたいなのだ。

/usr/lib にあるものと、 $EPREFIX/usr/lib にあるものが同名になっている。

ghc でコンパイルする時は、 -L オプションを指定すればうまく通った。 cabal の場合、 --ghc-options にライブラリのパスを指定してやれば解決した。 つまり

$ cabal install hoge

などとするときに

$ cabal install hoge --ghc-options=-L/usr/lib

などとする。

モナドといえば Haskell 。他の言語でもモナドライブラリはいろいろとあるのですが、イマイチ使いやすいと思えない。

これはやっぱり >>= を使って束縛するとネストしまくるのがアレだと思うのです。でも、これを、do記法なしでネストさせずに書くことができる事に気づきました。

あるモナド mk について、 中の値 x y を束縛しつつアレするのを 単純に書くとこのようになります:

(>>= m (fn [x]
  (>>= k (fn [y]
    do-something..))))

これはとても書きにくいし、構文にしろ、なにか違う書き方がしたいものです。

ここで product が使えます。 (product m k f) はこのように定義できます:

(defn product [m k f]
  (>>= m (fn [x] (>>= k (fn [y] (f x y))))))

Haskell ではこうです:

ここで product 関数を使ってこのように書くことができます:

(product m k (fn [x y] do-something..))

ずいぶんと書きやすくなりました。

当然ですが、これは Maybe とかにも適用できる一般的な関数となります。つまり product は リストに対して適用すると for マクロのように働くし、 maybe に対して適用すれば すべてが Just の場合だけ適用する関数のように働きます。

Clojure or other lisp な言語でモナドをする場合、 return をどう定義するか と悩んでいる人は多いと思います。 これの問題点を整理すると:

  • lisp の多態は引数による分岐である事が多いこと
  • return は引数では分岐できない関数であること

です。 Haskell には、たとえば read 関数など、引数では型を決定できない関数がいろいろとあります。 Haskell では、これを型による分岐 (型クラス) でうまく表現する事ができます。つまり:

read "1" :: Int
1
read "1" :: String
"*** Exception: Prelude.read: no parse

のように、型を指定して分岐するわけです。 今回は明示しましたが、実際には、戻り値型や、他の引数の関数の型によって推論されるので、明示しない事もあります。

動的言語の場合、型クラスは Object 指向おける mixin でうまく表現できる事は http://rb.blog.pasberth.com/post/49952066672 この記事で説明しました。

ということは、同じこと — つまり オブジェクト指向 — を Clojure にも実装してやれば、うまくできるはずです。

原則として、 return や guard といった関数は、引数を明示しなければならないものとします。 結局のところ、 (return option 42) のように書けばすべての問題は解決します。でも、その書き方はキモいし、 mzero とか、 guard とか、いちいち指定していたらやってられません。だから省略できるようにしてやればいいわけです。

ちなみに、 return の表現としては、マクロを使用して unit に束縛済みの unit を束縛したりする方法もあります。でも、そうすると guard の実装のためにも unit を束縛しつつ guard を定義する defmonadfn みたいなマクロを定義する必要があります。それはあまりにも面倒だし、 Applicative とかとの連携を考えるといい方法とは思いません。

それで、いろいろ考えていて思った事は、動的型づけに、少なくとも文脈としてのオブジェクトは必要不可欠だという事です。 静的型づけだと、型がその代わりになりますが、動的型かつ関数型であると、文脈が常に同じになってしまうので、この手の関数を定義するときに問題が起こります。

ちなみに、Clojureには潜在的にそのような関数は存在します。たとえば empty 関数は空のリストを返す関数です。これはMonadPlus の mzero とか Applicative の empty のような関数に相当する関数だと考えられますが、実際に Clojure の場合は無意味な引数をひとつ指定する必要があります。

非常に簡単に定義できるけど、いちおうブログにしておくことにした。

こんな感じ。すると (cfn [a b c] x) とかするとカリー化された関数になる。(f r) などと 引数をひとつ与えると a が部分適用された関数が返されるし、 (f r k) とふたつ与えると ab が部分適用された関数が返される。

Clojure でモナド的型クラスを模倣する方法は http://rb.blog.pasberth.com/post/49691550419/clojure-protocol で述べたが、これはとても一般的ではなく限定的な範囲にしか適用できない。しかし、これでしていることを一般化する方法について。

先のブログでは maybe-context という関数を作っていたけど、この中で instance? によって分岐している部分がある。まずはこれを protocol にしよう。つまり、 TypeClass というprotocolを作るのだ。

instance? による分岐は代わりに protocl による分岐になり、ループは再帰になる。

具体的な実装は https://github.com/pasberth/granjure/blob/30e76a57fb8ed783514fda2f2ae65a6908ef6d19/src/granjure/control.clj などを見てほしい。

次に、 (return a) のような関数を、 (Unit. a) のようなレコードとして定義しよう。そしてこれを TypeClass protocol の実装とする。具体的には https://github.com/pasberth/granjure/blob/30e76a57fb8ed783514fda2f2ae65a6908ef6d19/src/granjure/control/monad.clj#L26 このような実装になる。

return は単に Unit を返すだけだから、もちろんこれは実際のデータとして利用することはできない。これを specialize 関数を持って変換するわけだけど、明示しないで変換するのは簡単だ。これを具体的にデータに直すタイミングというのが存在するのだ。たとえば (>>= (Just. 42) (fn [a] (return a))) としたら、 return aUnit を返すわけだが、 >>= 関数は (Just. 42) という値を知っているので、これをもって Unit を具体的にできる。だから >>= を呼んだ瞬間 UnitJust に変換され、コンテキストを明示していないかのように振る舞うのだ。

しかも specializeTypeClass protocol で分岐できるので、 https://github.com/pasberth/granjure/blob/30e76a57fb8ed783514fda2f2ae65a6908ef6d19/src/granjure/control/applicative.clj#L21 たとえばこんなふうに、いくらでもコンテキストを追加できる。これで pure 関数も実装できた。 (>>= (Just. 42) (fn [a] (pure a))) も同じように変換されるのだ。

そして Unit とかは単なるデータだから、多態な関数の実装も簡単だ。 https://github.com/pasberth/granjure/blob/30e76a57fb8ed783514fda2f2ae65a6908ef6d19/src/granjure/control/monad.clj#L45 たとえばこんなふうに実装できる。驚くべきことに、 map-mf が返した値によって分岐するのだ。もちろん、 Nothing を返したらその時点で Nothing が帰る。しかも Unit を返したらそれがさらに多態な関数を生み出すのだ。