RazyK をリリースしました。RazyK は Ruby で実装した純粋関数型言語 LazyK の処理系です。
依存ライブラリ等
以下の gems パッケージに依存しています。
また ruby-graphviz を利用するためには GraphViz がインストールされていて、dot コマンドが利用できないといけません。
[追記]大事なことを書き忘れていました。Ruby 1.9 でしか動作確認していません。1.8 だと動作しないかもしれません。[/追記]
[追記]1.8 で存在しないメソッドを利用していたところがあったので修正して 0.0.1 をリリースしなおしました。[/追記]
使いかた
コマンドラインツール razyk を起動して利用します。
$ razyk examples/reverse.lazy or $ razyk -e "i"
のように LazyK のプログラムが格納されたファイルを指定するか、-e オプションで直接プログラムを書いて起動します。
$ razyk --step examples/reverse.lazy
のように --step オプションを付けることで、ステップ毎に展開された式をコンビネータ式の形式(S式に近いです)でダンプします。
$ razyk --server [PORT]
のように --server オプションを指定して起動すると http サーバとして動作し、ブラウザ経由でステップ実行することができます(後述)。--server オプションにはポート番号を指定できます。省略時のデフォルトポートは 9292 です。
LazyK
LazyK について詳しくは
http://homepages.cwi.nl/~tromp/cl/lazy-k.html
http://e.tir.jp/wiliki?%CB%DD%CC%F5%3A%A5%D7%A5%ED%A5%B0%A5%E9%A5%DF%A5%F3%A5%B0%B8%C0%B8%ECLazy_K
などを参照してください。簡単に特徴を挙げると
- SKI コンビネータのみで記述するミニマムな純粋関数型言語
- 関数をプリミティブとして持つ、というより関数以外ない。数値や文字列もない
- 参照透明性を持つ
- 遅延評価
- ストリームベースの入出力機能
- 型システムはない
- コンビネータ式の他、Unlambda, Iota, Jot の文法に対応
いわゆる Esoteric Language(奇妙な言語)の一種です。
RazyK の特徴
RazyK は主に SKI コンビネータの式がどのように展開(簡約)されるのかを確かめるという学習用の目的で作成しました。そのため簡約の様子を観察するための機能を追加してあります。
- 式の展開(簡約)毎に式をダンプする機能(--step)
- ブラウザによるステップ実行機能
- 文法の拡張 / # 以降は行末尾までコメントとして扱う
- 文法の拡張 / $COMB の記法で任意のコンビネータを記述
- 文法の拡張 / リストの省略記法としての文字列リテラルをサポート
しかし速度は遅いですし、あまり大きな式はスタックオーバフローで実行できないなど、実用的なプログラムを動かすのには向いていないと思います。
ブラウザによるステップ実行機能
$ razyk --server
と起動すると http サーバとして動作しはじめます。ブラウザで http://localhost:9292/ にアクセスすると以下のようなページが表示されます。(Firefox 3.6, Safari 5.0.2 で動作確認)
一番上の "enter program" のテキストボックスに評価したい式を書いて "set program" ボタンを押します。以下のように式の内部表現*1をコンビネータ式で表現したものと、graphviz が利用できれば ツリー構造の画像が表示されます。コンビネータ式は適用する関数とその引数をサブツリーとする二分木(正確には循環しない有向グラフ(DAG))で表現されます。
"step" ボタンを押すことで1ステップごとに式の展開(簡約)のようすを観察することができます。
"LazyK application mode" のチェックボックスをチェックすると、LazyK のストリーム I/O の機能を追加した状態で式の評価を行ないます。チェックボックスにチェックをつけると表示される "stdin" のテキストボックスに標準入力に渡したい文字列を記入してから "set program" を押すことで標準入力をセットします。今のところステップ実行の途中の変更は効きません。出力結果は "stdout" の下に表示されます。下図は入力をそのまま出力に流す cat コマンド相当のプログラム(LazyK では "I" 一文字、もしくはただ空文字列で cat を実現できます)を途中まで評価しているところです。
$ 記法
オリジナルの LazyK は s k i および Iota, Jot の文法のみサポートしていますが、RazyK では $hoge のように $ 記号のあとに英数文字とアンダースコア(_)、ハイフン(-)、ピリオド(.)からなるコンビネータ名を書くことで、パーサにその名前のコンビネータをそのまま生成させることができます。
RazyK は S, K, I などのコンビネータは内部でもそのまま S, K, I という名称を利用しているので、以下の2つのプログラムは同等です。
(S (K I))
($S ($K $I))
また RazyK は内部で利用するために CONS, CAR, CDR などのリストのためのコンビネータやチャーチ数のコンビネータを認識しますので、$ 記法でこれらのコンビネータを生成することで簡単にリストやチャーチ数を書くことができます。
($CAR ($CONS $0 $1))
RazyK が認識しないコンビネータ名は簡約できないコンビネータとして扱われます。これはたとえばチャーチ数の展開を確認するために、(num f x) のような式を展開する時に、f, x の部分は変数として、勝手に展開されないコンビネータが必要になるので、そういう時のために導入しました。
(S(S(KS)K)I) $f $x # S(S(KS)K)I はチャーチ数 2 のはずなので確認したい
文字列リテラル
RazyK では文字列は 0-255 のチャーチ数のリストとして表現できます。これを簡単に効率的な内部表現と表記で記述するために、ダブルクオートでくくった文字列リテラル表現を受け付けるようにしています。
これにより入力を無視して "Hello World!"(改行つき)を出力するプログラムは以下のように書けます。ちなみに先頭の K は、入力は捨てて標準出力を生成する時の書きかたの定石です。
K "Hello World!\n"
作ってみて感想など
そもそもは Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~ の付録で Unlambda という LazyK の元になっている言語が紹介されていたのが最初のきっかけです。
Ruby VM の実装を読んだりするうちに、体系的な学習はしていないものの、手続き型やオブジェクト指向の言語の処理系や VM はなんとなく想像がつくようになってきました。しかし関数しか存在していないのにいろいろデータの表現や計算が可能だというのを読んで、はたしてそれがどういう世界なのか、そしてどうやってそんな処理系が作れるのだろうかというのがさっぱり想像もできませんでした。
わからないものは作ってみるのが一番だな、ということと、社内でテーマ自由で何か TechTalk をしてくれと依頼を受けたので、作ってみました。途中で Unlambda には LazyK というよりシンプルな亜種があると知ったので LazyK をターゲットにしました。
関数型言語の処理系の実装については教科書的な本があることはなんとなくきいたことがありましたが、今回はそういった予備知識はなしで作りました。そのためセオリーに反したおかしな実装になっていたり、普通なら採用するテクニックが抜けていたりすることがあるかもしれません。しかし自分の持ち合わせている知識と発想だけでなんとか工夫して実際に動く処理系ができたので、とても満足していますし自信がつきました。それに最初は想像もつかなかった遅延評価の実装方法がわかって、Haskell もこんな感じなのかなぁとうっすらと想像がつくようになった気がします。まあ型システムというおそらくもっと難しいものが RazyK には存在しないのでまだぜんぜんですけども。今後ちゃんと教科書的な本を読んで勉強してみたいなと思います。型推論の読み易い日本語の本出ないかなぁ。
また、コンビネータ式を内部どう表現しているかとか、実装しててつまづいたことなどをちまちまと書き溜めているので、機会があればいずれ発表してみたいと思っています。おそらく関数型言語に詳しい人達にとってはしょーもない内容ですが、わたしのような「関数型? なにそれ怖い」な人にとってはとっつきやすいんじゃないかなーとかってに思っています。
では、Happy Hacking!
