Mark-sweepのunmarkをサボる

3月 27th, 2016

ガベージコレクション 自動的メモリ管理を構成する理論と実装を読んでたら、ごみ集めのたびにマークビットの意味を反転させればunmarkのコストを避けれる、という話があったので試してみた。
恐らく、これが効果があるのはヒープが巨大な時と、unmarkのコストが大きい時だろう。巨大なヒープを使うのはいやなので、unmarkのコストが大きい(要するに遅い)NScLisperでこれを実装してみた

Benchmark program:
  (define (muda n . r) (if (<= n 0) r (muda (- n 1) (cons 0 0))))
  (time (muda 3000))
Before: 47143 ms
After:  46688 ms

どちらも評価時にごみ集めは8回走った。

まあ、速くなったといえば速くなったけど、それほど大きな違いはなかった。
恐らくNScLisperのヒープが小さすぎるのが一番の原因だろう。NScLisperのヒープは2900セルしかない。
それから、consingの際に、これまではマークビットが0であることが保証されていた (初期値は0だし、再利用の際もsweep時に0になる) ので何もする必要はなかったが、この変更により「マークされてないことを表す値」をマークビットに設定する必要が出てくる。このコストはunmarkと変わらない。つまり、unmark処理省略の恩恵を受けれるのは基本的に生きているオブジェクトだけだ。
(正確にはプログラム終了時に使われてないセルについてもunmarkのコストを避けたことになるが、逆に最初のごみ集めが起こるまでのconsingでは余計なコストが増えている)
このプログラムでは常に約700セルが使われているので、8回のごみ集めで合計5600回分のunmarkのコストを避けたことになる。これだけで455ms速くなったのだからお得といえばお得な気もする。
ただし、変数が合計で4096個しか作れない(ヒープやスタックも含む)環境下で変数を1つ消費する価値が有るかというと、やはり微妙なところだ。

(自分用メモ)
マーク済みを表す値ではなくマークされてないことを表す値を変数に入れたほうが減算の回数が減るのではないかと気付き試したが、結果に変化は見られなかったのでrevertした。

Common Lispのenvironmentがよく分からない

1月 14th, 2016

Common Lisp HyperSpecをまじめに読んでたら、だんだんenvironmentが分からなくなってきたのでメモ。
なお、ここでのenvironmentはenvironment objectではなくbindingの集合の意味でのenvironment。

3.1.1 Introduction to Environmentsを読むと、”the global environment”, “a lexical environment”, “a dynamic environment” と書いてあるところから、global environmentはただ一つだけ存在して、lexical environmentとdynamic environmentは複数存在することがうかがえる。ただし明示的にそんなことは書いてない
3.1.1.23.1.1.3によると、プログラム実行中のある時点でactiveなlexical/dynamic environmentのことを “the lexical/dynamic environment” というらしい。ただ、何をもって “active” というのか探したが見当たらないので非常に困る。

3.1.2.1.2.1 Special Formsによるといくつかのspecial operatorはsubformを評価するときに使うためのlexical/dynamic environmentを新たに作るらしい。やはりlexical/dynamic environmentは複数存在するという予想は正しそうだ。
それから具体例としてblockが新たにlexical environmentを作ると書いてある。そのenvironmentはblock formを評価するときに有効(in force)なenvironmentにblock nameとexit pointのbidingを加えたものらしい。何をもってin forceと呼ぶのかわからないのは置いておいて、肝心のblockの説明を見に行くとenvironmentについて何も言及していない。
いかにもenvironmentを作りそうなletの説明を見ても新たなbindingを作るとは書いてあるがenvironmentについてはやはり言及していない。
結局、どのspecial operatorが新たなenvironmentを作るのかわからない

HyperSpecを探しまわった所、with-accessorsがenvironmentを作るという記述を見つけた。

Creates a lexical environment in which the slots specified by slot-entry are lexically available through their accessors as if they were variables.

with-accessorsはsymbol-macroletに展開できるという話も書いてあるので、symbol-macroletはenvironmentが作ると考えてもいいのかもしれない。しかし、symbol-macroletの説明を見ると、やっぱりenvironmentを作るなんて話は書いてない。

とりあえず、よく分からないということがよく分かった。

機械もすなる論理学を機械にやらせてみた

10月 25th, 2015

TL;DR: Prologの双方向代入最高!

はじめに

8年ほど前に『論理学を作る』という本を読みまして、そこにタブローの方法と呼ばれる論理式の集合が充足可能か調べるアルゴリズムが載っていました。「暇があったらいつか実装してみるか」と思っていたら8年も経ってしまいましたが、暇があったので実装してみました。Prologで。

タブロー(tableau)とは要は木で、木を書くと論理式の集合が充足可能かどうか分かるというものです。こういう時にはWikipediaさんに説明を任せたいのですが、日本語版にはまるで情報がありません。英語版はきちんと書いてあるっぽいので気になる方はそちらを参照してください。

少しだけ説明をすると、与えられた論理式の集合をルートとして、その中の複合式を充足させるのに必要な(より小さな)式を子として木を作っていき、ルートからリーフに至る経路にAと¬A (Aはリテラル) の両方が現れなければ充足可能。すべての経路にAと¬Aの両方が現れたら矛盾とわかるという仕組みです。

例えば論理式の集合 {A∨B, ¬A} に対してタブローを描くと次のようになります(記号は適切に読み替えてください)。

A∨Bを充足させるためにはAかBが真になる必要があります。しかし、¬Aがあるので、Aは真には出来ません(右の経路)。しかしBが真になれるのでこの集合は充足可能です(左の経路)。

はい、ようやくPrologの話です

さて、この図ですが、Prologで書きました。

?- tableau([a+b, not(a)], R).
digraph tableau {
  node101 [ label = "b\n" ];
  node100 [ label = "fail\n" ];
  node99 [ label = "a\n" ];
  start [ label = "a+b\nnot(a)\n" ];
  start -> node101
  node99 -> node100
  start -> node99
}
R = ok.

述語tableauの第一引数に論理式の集合を入れてやると、DOT言語を出力するので、こいつを dot コマンドに入れてやると図が出てくるという仕組みです。変数Rが ok というのは充足可能という意味です。入力に ¬B を加えてやると矛盾となり、Rには fail が入ります。

?- tableau([a+b, not(a), not(b)], R).
(中略)
R = fail.

もっと複雑な入力を入れてみましょう。集合 {A→B, B→C, C→D, ¬(A→D)} が充足可能か調べます。

?- tableau([a->b, b->c, c->d, not(a->d)], R).

R = fail.

はい。見事に矛盾していると見抜けました。やったね。

Prologといえば双方向代入

これだけなら「どんなプログラミング言語で書いても一緒だろ」という物言いが付きそうなので、Prologならではのことをやってみようと思います。先ほどの集合 {A→B, B→C, C→D, ¬(A→D)} は少しいじれば充足可能に出来そうです。そこで A→B の A の部分を何か別の論理式に変えることを考えてみましょう。つまり {α→B, B→C, C→D, ¬(A→D)} が充足可能となるような α を見つけましょう。
タブローを作るプログラムしか書いていない場合、多くのプログラミング言語ではこのようなことをするために新たにプログラムを書き足す必要がありそうですが、Prologではプログラムを一切書き換えること無くこのようなことが出来ます。

;;; グラフの出力は省略
?- tableau([X->b, b->c, c->d, not(a->d)], ok).
X = not(a);
X = not(not(d));
X = not(not(c));
X = not(not(b));
X = not(not(_G1749));
X = not(a*a);
X = not(a*not(d));
X = not(a*not(c));
X = not(a*not(b));
...

¬A のような単純なものから始まり ¬(A∧¬B) などという少々複雑なものも出てきて面白いです。このまま続けていけば非常に長い式も得られるのですが、 ¬(A∧(A∧(A∧(A∧(A∧(A∧(A∧¬D))))))) のような面白みのないものになってしまいました。

今回は命題論理だけを扱いましたが、『論理学を作る』ではこのあとタブローを述語論理に対応させたりどんどん拡張していくので、こちらも暇があったらやってみようと思います。

[LSP42] ドキッ!LISPだらけの大運動会

12月 25th, 2014

(この記事はLISP Implementation Advent Calendar 25日目のためのエントリかもしれません。)

背景

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装しました。ソースコードはすべてGitHub上においてます。作り終えたらやりたくなることは一つ。そう、速度の比較ですね。そんなわけで42個のLISP処理系の速度を計測しました。言語によって100倍以上の速度差があるため、すぐ終わるベンチマークでは速い言語同士の比較ができず、時間のかかるベンチマークだと遅い言語が終わらないため、3種類のベンチマークを用意して速度を比べました。計測には time コマンドの total を使用し、各言語3回の計測を行い、その中間値を使用しました。ハッキリ言っていい加減な値なので、きちんとした結果を知りたい人は各自42個の言語処理系を用意して計測しなおしてください。

なお、この記事はクリスマスが暇で仕方ない人向けに必要以上に水増しして長くしてあるので、暇でない方は最後だけ読まれることをおすすめします。

一回戦

最初のベンチマークは相互再帰によるフィボナッチ数の計算。 (fib 15) の実行時間を測りました。

((lambda(x) (defun fib (n) (if (eq n 1) 1 (if (eq n 0) 1 (+ (fib(- n 1)) (fib(- n 2)))))) (fib x)) 15)

計算自体は一瞬で終わる言語が多いため、実質的に起動時間のベンチマークといえるかもしれません。一部の言語処理系は起動に2秒以上かかるので、それにより大きく順位を落としています。

対数グラフであることに注意してください。
トップはCoffeScriptの0.002秒。続いてOCamlの0.007秒。そして3位はなんとOberon-2の0.01秒です。
最下位はEの33.311秒、そしてCeylonの18.358秒、Scratchの6.25秒が続きます。
Scratchは起動時間を含んでいませんが、それでもCeylonとEより速いのは明らかです。これには業界のアナリストも苦笑いでしょうか。

目がいい人はグラフに41言語しかないことに気づいたかもしれません。これはIokeがスタックオーバフローを引き起こし計算を最後まで出来なかったためです。スタックサイズを増やす方法を調べたのですが見つからなかったので諦めました。

二回戦

次のベンチマークも相互再帰によるフィボナッチ数の計算。 (fib 15) の実行時間を測りました。ただし、LISPで書かれたLISP評価器の上で計算を行います。
つまり、ある言語の上でLISP処理系が動き、そのLISP処理系の上でLISP評価器が動き、その上でフィボナッチ数の計算を行います。

((lambda (ge) (setq #+nil (defun funcall (f x) (f x))) (defun mcon% (a d) (lambda (c) (if (eq c 'car) a (if (eq c 'cdr) d (if (eq (car c) 'car) (setq a (cdr c)) (if (eq (car c) 'cdr) (setq d (cdr c)))))))) (setq ge (mcon% (mcon% (mcon% 't 't) ()) ())) (defun cadr% (x) (car (cdr x))) (defun cddr% (x) (cdr (cdr x))) (defun assoc% (k l) (if l (if (eq k (funcall (funcall l 'car) 'car)) (funcall l 'car) (assoc% k (funcall l 'cdr))) ())) (defun fv% (k a) (if a ((lambda (r) (if r r (fv% k (funcall a 'cdr)))) (assoc% k (funcall a 'car))) ())) (defun ea% (e a) ((lambda (b) (if b (funcall b 'cdr) e)) (fv% e a))) (defun el% (e a) (cons '%e% (cons (car e) (cons (cdr e) a)))) (defun ae% (s v) (funcall ge (cons 'car (mcon% (mcon% s v) (funcall ge 'car)))) s) (defun eval% (e a) (if (atom e) (ea% e a) (if (eq (car e) 'quote) (cadr% e) (if (eq (car e) 'if) (if (eval% (cadr% e) a) (eval% (cadr% (cdr e)) a) (eval% (cadr% (cddr% e)) a)) (if (eq (car e) 'lambda) (el% (cdr e) a) (if (eq (car e) 'defun) (ae% (cadr% e) (el% (cddr% e) a)) (if (eq (car e) 'setq) ((lambda (b v) (if b (funcall b (cons 'cdr v)) (ae% (cadr% e) v)) v) (fv% (cadr% e) a) (eval% (cadr% (cdr e)) a)) (apply% (eval% (car e) a) (evlis% (cdr e) a))))))))) (defun pairlis% (x y) (if x (if y (mcon% (mcon% (car x) (car y)) (pairlis% (cdr x) (cdr y))) ()) ())) (defun evlis% (l a) (if l (cons (eval% (car l) a) (evlis% (cdr l) a)) ())) (defun progn% (l a r) (if l (progn% (cdr l) a (eval% (car l) a)) r)) (defun apply% (f a) (if (eq (car f) '%e%) (progn% (cadr% (cdr f)) (mcon% (pairlis% (cadr% f) a) (cddr% (cdr f))) ()) (if (eq (car f) '%s%) (funcall (cdr f) a) f))) (defun es% (e) (if (atom e) e (if (eq (car e) '%s%) ' (if (eq (car e) '%e%) ' e)))) (defun eval%% (e) (es% (eval% e ge))) (ae% 'car (cons '%s% (lambda(x)(car(car x))))) (ae% 'cdr (cons '%s% (lambda(x)(cdr(car x))))) (ae% 'cons (cons '%s% (lambda(x)(cons(car x)(cadr% x))))) (ae% 'eq (cons '%s% (lambda(x)(eq(car x)(cadr% x))))) (ae% 'atom (cons '%s% (lambda(x)(atom(car x))))) (ae% '+ (cons '%s% (lambda(x)(+(car x)(cadr% x))))) (ae% '* (cons '%s% (lambda(x)(*(car x)(cadr% x))))) (ae% '- (cons '%s% (lambda(x)(-(car x)(cadr% x))))) (ae% '/ (cons '%s% (lambda(x)(*(car x)(cadr% x))))) (ae% 'mod (cons '%s% (lambda(x)(mod(car x)(cadr% x))))) (eval%% '((lambda(x) (defun fib (n) (if (eq n 1) 1 (if (eq n 0) 1 (+ (fib(- n 1)) (fib(- n 2)))))) (fib x)) 15))) ())

読みやすい形のLISP評価器はGitHubにおいてあります。
https://github.com/zick/ZickStandardLisp/blob/master/lisp.lsp

今回はそれなりに時間がかかるため純粋に速さの勝負となります。また、リスト操作が非常に多いためコンスセルの実装方法も速度に大きな影響を与えそうです。

これも対数グラフなので注意してください。
トップはKotlinの0.764秒。続いてDartの0.782秒。そしてOCamlの0.91秒が続きます。KotlinはJVMで動く言語ですがJavaを大きく引き離しているのが印象的です。JavaScript系の言語はどれも好成績を収めていますが、その中でも独自のVMを使うDartが他の言語を一歩上回りました。OCamlはStandard MLを倍近く引き離しました。F#ははるか後ろですがこれは私の実装方法が悪かったせいかもしれません。
最下位はHaxeの130.88秒。そしてPerlの104.08秒、Pikeの62.23秒が続きます。PerlやPikeのように型が柔軟な言語が後ろの方に来るのはある程度しかたがないことかもしれませんが、ガチガチに型を書いたHaxeがこうも遅いと悲しくなります。

なお、RIconIokeEはスタックオーバフローのため計測できず。ScratchIoTclFalconCeylonEiffelは5分以内に終わらなかったので打ち切りました。

決勝戦

最後のベンチマークも相互再帰によるフィボナッチ数の計算。 (fib 15) の実行時間を測りました。ただし、LISPで書かれたLISP評価器の上で動く、LISPで書かれたLISP評価器の上で計算を行います。
つまり、ある言語の上でLISP処理系が動き、そのLISP処理系の上でLISP評価器が動き、そのLISP評価器の上でLISP評価器が動き、その上でフィボナッチ数の計算を行います。

((lambda (ge) (setq #+nil (defun funcall (f x) (f x))) (defun mcon% (a d) (lambda (c) (if (eq c 'car) a (if (eq c 'cdr) d (if (eq (car c) 'car) (setq a (cdr c)) (if (eq (car c) 'cdr) (setq d (cdr c)))))))) (setq ge (mcon% (mcon% (mcon% 't 't) ()) ())) (defun cadr% (x) (car (cdr x))) (defun cddr% (x) (cdr (cdr x))) (defun assoc% (k l) (if l (if (eq k (funcall (funcall l 'car) 'car)) (funcall l 'car) (assoc% k (funcall l 'cdr))) ())) (defun fv% (k a) (if a ((lambda (r) (if r r (fv% k (funcall a 'cdr)))) (assoc% k (funcall a 'car))) ())) (defun ea% (e a) ((lambda (b) (if b (funcall b 'cdr) e)) (fv% e a))) (defun el% (e a) (cons '%e% (cons (car e) (cons (cdr e) a)))) (defun ae% (s v) (funcall ge (cons 'car (mcon% (mcon% s v) (funcall ge 'car)))) s) (defun eval% (e a) (if (atom e) (ea% e a) (if (eq (car e) 'quote) (cadr% e) (if (eq (car e) 'if) (if (eval% (cadr% e) a) (eval% (cadr% (cdr e)) a) (eval% (cadr% (cddr% e)) a)) (if (eq (car e) 'lambda) (el% (cdr e) a) (if (eq (car e) 'defun) (ae% (cadr% e) (el% (cddr% e) a)) (if (eq (car e) 'setq) ((lambda (b v) (if b (funcall b (cons 'cdr v)) (ae% (cadr% e) v)) v) (fv% (cadr% e) a) (eval% (cadr% (cdr e)) a)) (apply% (eval% (car e) a) (evlis% (cdr e) a))))))))) (defun pairlis% (x y) (if x (if y (mcon% (mcon% (car x) (car y)) (pairlis% (cdr x) (cdr y))) ()) ())) (defun evlis% (l a) (if l (cons (eval% (car l) a) (evlis% (cdr l) a)) ())) (defun progn% (l a r) (if l (progn% (cdr l) a (eval% (car l) a)) r)) (defun apply% (f a) (if (eq (car f) '%e%) (progn% (cadr% (cdr f)) (mcon% (pairlis% (cadr% f) a) (cddr% (cdr f))) ()) (if (eq (car f) '%s%) (funcall (cdr f) a) f))) (defun es% (e) (if (atom e) e (if (eq (car e) '%s%) ' (if (eq (car e) '%e%) ' e)))) (defun eval%% (e) (es% (eval% e ge))) (ae% 'car (cons '%s% (lambda(x)(car(car x))))) (ae% 'cdr (cons '%s% (lambda(x)(cdr(car x))))) (ae% 'cons (cons '%s% (lambda(x)(cons(car x)(cadr% x))))) (ae% 'eq (cons '%s% (lambda(x)(eq(car x)(cadr% x))))) (ae% 'atom (cons '%s% (lambda(x)(atom(car x))))) (ae% '+ (cons '%s% (lambda(x)(+(car x)(cadr% x))))) (ae% '* (cons '%s% (lambda(x)(*(car x)(cadr% x))))) (ae% '- (cons '%s% (lambda(x)(-(car x)(cadr% x))))) (ae% '/ (cons '%s% (lambda(x)(*(car x)(cadr% x))))) (ae% 'mod (cons '%s% (lambda(x)(mod(car x)(cadr% x))))) (eval%% '((lambda (ge) (setq #+nil (defun funcall (f x) (f x))) (defun mcon% (a d) (lambda (c) (if (eq c 'car) a (if (eq c 'cdr) d (if (eq (car c) 'car) (setq a (cdr c)) (if (eq (car c) 'cdr) (setq d (cdr c)))))))) (setq ge (mcon% (mcon% (mcon% 't 't) ()) ())) (defun cadr% (x) (car (cdr x))) (defun cddr% (x) (cdr (cdr x))) (defun assoc% (k l) (if l (if (eq k (funcall (funcall l 'car) 'car)) (funcall l 'car) (assoc% k (funcall l 'cdr))) ())) (defun fv% (k a) (if a ((lambda (r) (if r r (fv% k (funcall a 'cdr)))) (assoc% k (funcall a 'car))) ())) (defun ea% (e a) ((lambda (b) (if b (funcall b 'cdr) e)) (fv% e a))) (defun el% (e a) (cons '%e% (cons (car e) (cons (cdr e) a)))) (defun ae% (s v) (funcall ge (cons 'car (mcon% (mcon% s v) (funcall ge 'car)))) s) (defun eval% (e a) (if (atom e) (ea% e a) (if (eq (car e) 'quote) (cadr% e) (if (eq (car e) 'if) (if (eval% (cadr% e) a) (eval% (cadr% (cdr e)) a) (eval% (cadr% (cddr% e)) a)) (if (eq (car e) 'lambda) (el% (cdr e) a) (if (eq (car e) 'defun) (ae% (cadr% e) (el% (cddr% e) a)) (if (eq (car e) 'setq) ((lambda (b v) (if b (funcall b (cons 'cdr v)) (ae% (cadr% e) v)) v) (fv% (cadr% e) a) (eval% (cadr% (cdr e)) a)) (apply% (eval% (car e) a) (evlis% (cdr e) a))))))))) (defun pairlis% (x y) (if x (if y (mcon% (mcon% (car x) (car y)) (pairlis% (cdr x) (cdr y))) ()) ())) (defun evlis% (l a) (if l (cons (eval% (car l) a) (evlis% (cdr l) a)) ())) (defun progn% (l a r) (if l (progn% (cdr l) a (eval% (car l) a)) r)) (defun apply% (f a) (if (eq (car f) '%e%) (progn% (cadr% (cdr f)) (mcon% (pairlis% (cadr% f) a) (cddr% (cdr f))) ()) (if (eq (car f) '%s%) (funcall (cdr f) a) f))) (defun es% (e) (if (atom e) e (if (eq (car e) '%s%) ' (if (eq (car e) '%e%) ' e)))) (defun eval%% (e) (es% (eval% e ge))) (ae% 'car (cons '%s% (lambda(x)(car(car x))))) (ae% 'cdr (cons '%s% (lambda(x)(cdr(car x))))) (ae% 'cons (cons '%s% (lambda(x)(cons(car x)(cadr% x))))) (ae% 'eq (cons '%s% (lambda(x)(eq(car x)(cadr% x))))) (ae% 'atom (cons '%s% (lambda(x)(atom(car x))))) (ae% '+ (cons '%s% (lambda(x)(+(car x)(cadr% x))))) (ae% '* (cons '%s% (lambda(x)(*(car x)(cadr% x))))) (ae% '- (cons '%s% (lambda(x)(-(car x)(cadr% x))))) (ae% '/ (cons '%s% (lambda(x)(*(car x)(cadr% x))))) (ae% 'mod (cons '%s% (lambda(x)(mod(car x)(cadr% x))))) (eval%% '((lambda(x) (defun fib (n) (if (eq n 1) 1 (if (eq n 0) 1 (+ (fib(- n 1)) (fib(- n 2)))))) (fib x)) 15))) ()))) ())

非常に時間が掛かることが予想されたため、二回戦の上位8言語に対してのみ計測を行いました。

今回は対数グラフではありません。
まずはじめに、V8上で動くCoffeScript、TypeScript、LiveScriptの3言語はスタックオーバフローため最後まで走り切ることができませんでした。
Standard MLは無事最後まで走り切ることができましたが、654.27秒というイマイチな記録。
OCamlはStandard MLの倍以上速い296.88秒という記録でこれに続きました。
3位はJava。記録は279.96秒。JVMで動く言語が多数あるなか本家が良い記録を残しました。
2位はDart。記録は184.57秒。3位を大きく引き離しました。
そして栄えある1位はKotlin。記録は177.09秒。JVM上で動く新しい言語が42言語の頂点に立ちました。

あらためてKotlinの思い出

作っていた時の感触から、Dart、[Coffee,Type,Live]Script、Standard ML、OCamlあたりが上位に行くことはなんとなく分かっていました。また、JavaがJVMの力により上位に来ることも予想していました。しかし、Kotlinが1位はおろか、上位に来ることさえ予想していませんでした。
KotlinでLISPを実装した時に私は次のようなメモを書き残していました。

2014-06-29
Kotlin
コンパイルして実行する方法が分からず長時間時間以上悩む。IDEの使い方しか載ってないような言語は等しく灰に還ればいいのに。whileとisの組み合わせがちょっと冗長。型を間違えると、お前は昔のC++かと言いたくなるくらい、怒涛の勢いでエラーを出す。言語としては悪く無いと思うけど、コマンドラインからの実行方法が書いてなくて悩んだせいで心象が悪い。

そう。思い返してみるとコマンドラインから実行する方法を見つけるまで非常に時間がかかり、ものすごく心象が悪かったんです。6月末に実装したわけですが、12月に時点では「ああ、IDEの使い方しか載ってなかった言語か」という程度しか覚えておらず、速かったか遅かったかなどまったく覚えていなかった訳です。
ちなみに「whileとisの組み合わせ」というのはこれです。

fun nreverse(l : Any) : Any {
  var lst = l
  var ret : Any = kNil
  while (true) {
    val elm = lst
    if (elm is Cons) {
      val tmp = elm.cdr
      elm.cdr = ret
      ret = lst
      lst = tmp
    } else {
      break
    }
  }
  return ret
}

本当は while (lst is Cons) のように書きたいのですが、それが許されていないためネストも深くなるしコードも冗長になってしまいます。これはなんとか改善して欲しいですね。

KotlinとJava、どうして差がついたのか…慢心、環境の違い

同じJVMで動くKotlinとJavaでどうしてこうも差がついたのでしょうか。Kotlinのコンパイラがものすごい賢いコードを出力するのでしょうか。その可能性もなくは無いでしょうが、主な原因はコンスセルの表現の違いでしょう。Javaでは気まぐれで次のようにコンスセルを表現しました。

enum Type {
    NIL, NUM, SYM, ERROR, CONS, SUBR, EXPR,
}

class LObj {
    public Type tag() { return tag_; }
    public LObj(Type type, Object obj) {
        tag_ = type;
        data_ = obj;
    }
    public Cons cons() {
        return (Cons)data_;
    }
    ....
    private Type tag_;
    private Object data_;
}

class Cons {
    public Cons(LObj a, LObj d) {
        car = a;
        cdr = d;
    }
    public LObj car;
    public LObj cdr;
}

コンスもシンボルもLObjという一種類のクラスで表現し、data_フィールドに実体を入れて、型はtag_を見て判断します。どうしてこの実装にしたかの詳しい経緯は12/24の記事を読んでください。詳しくない経緯は「気まぐれ」です。さて、この実装でコンスのCAR部を取り出そうとすると、次のようなバイトコード(もしくはそれをJITコンパイルしたもの)が実行されます。

aload_0  // 対象のオブジェクトをスタックに置く
invokevirtual LObj.tag  // tag()を呼び、tag_をスタックに置く
getstatic Type.CONS  // CONSをスタックに置く
if_acmpne  // tag_がCONSでなければ(どこかに)ジャンプ
aload_0  // 再度、対象のオブジェクトをスタックに置く
invokevirtual LObj.cons  // cons()を呼び、data_をスタックに置く
getfield Cons.car  // CAR部を取り出す

consメソッドはこんな感じです。

aload_0  // 引数をスタックに置く
getfield data_  // data_フィールドをスタックに置く
checkcast Cons  // data_の型がConsか確認(異なれば例外を投げる)
areturn  // data_を返す

一方、Kotlinではコンスセルを次のように表現しました。

class Cons(a : Any, d : Any) {
  var car = a
  var cdr = d
}

そのままです。型を見るときには前述した is を使います。この実装でコンスセルのCAR部を取り出そうとすると、次のようなバイトコード(もしくはそれをJITコンパイルしたもの)が実行されます。

aload_0  // 対象のオブジェクトをスタックに置く
instanceof Cons  // 型がConsなら1、異なれば0をスタックに置く
ifeq  // 0なら(どこかに)ジャンプ
aload_0  // 再度、対象のオブジェクトをスタックに置く
checkcast Cons  // オブジェクトの型がConsか確認(異なれば例外を投げる)
invokevirtual Cons.getCar  // getCarを呼ぶ

getCarはKotlinが自動生成するメソッドで、次のようになります。

aload_0  // 引数をスタックに置く
getfield car  // carを取り出す
areturn  // carを返す

Kotlinの方が短いですね。細かな違いはJITコンパイルされると消えてしまうかもしれませんが、(恐らく)消えないのは getfield data_ でしょう。Javaはどうあがいても2回参照をたどらないとCARにたどり着けません。一方Kotlinは一回の参照でCARにたどり着けます。何度もリスト操作を繰り返す今回のベンチマークではこれが大きな差を産んだのではないでしょうか。

と、仮説だけを書いているといろんな人に怒られそうなので、実際に検証してみました。
こちらはJavaのプロファイル結果。

findVarが一番時間をくっているというのは環境に連想リストを使っているので当然の結果ですね。注目すべき点は cons() が二番目というところです(どうしてこのメソッドがこんなに遅いか調べるのは読者の練習問題とします)。それ以降にもリスト関連のメソッドが並んでいます。
次はKotlinのプロファイル結果。

findVarが一番時間をくっているのはJavaと同じですが、当然ながら cons() に相当するものがありません。それからJavaのmakeConsよりKotlinのCons.<init>が速いというのもポイントですね。考えてみたらJavaはLObjとConsの2つのオブジェクトを作るのに対し、Kotlinは単一のオブジェクトしか作らないのでこれも当然ですね。
この結果を見る限り、やはりコンスの実装の違いが実行時間に影響を与えているようです。

では、ここでひとつの疑問が出てきます。Javaの実装をKotlinと同じようにすればどちらが速いのか。これは読者の練習問題とします。

父兄の皆様へ

「うちの言語がこんなに遅いわけがない!」「あんたの書き方が悪いんだ!うちの言語に謝れ!!」とお怒りの方もいらっしゃるかもしれません。最初に書きましたがソースコードはすべてGitHub上においてますので、納得がいくまでご自由に改造してください。ただし、計測はセルフサービスとなっておりますので予めご了承ください。

小学生並みの感想

Kotlinが一番速かったです。

[LSP42] OzとBoo

12月 24th, 2014

(この記事はLISP Implementation Advent Calendar 24日目のためのエントリです。)

OzBooでLISPを作りました。
https://github.com/zick/OzLisp
https://github.com/zick/BooLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその41〜42個目です。
Ozは人を殴り殺せる分厚さの青い本で知り、簡単そうだったので最後に楽をしようと選びました。
BooはWikipediaで見つけ、簡単そうなので最後の最後に楽をしようと選びました。

Ozの思い出


Ozはマルチパラダイム言語で、関数型言語としても使えるし、オブジェクト指向言語としても使えるし、並列論理型言語としても使える、めっちゃカッケー言語です。しかし、不思議なことにあまり流行っていません。不思議なことに私も書いたことがありませんでした。

マニュアルを見るとそこには本の紹介が

これまで使った言語でも何回かありました。言語/処理系の公式サイトのマニュアルのページを見ると本の紹介が載っているというパターン。「この言語を学ぶためにはまず本を買え」ということでしょうか。何のためにウェブサイトがあるんだと言いたくなります。そのたびにイラッ☆っとしてきたんですが、Ozもそのパターンでした。紹介されている本は幸いにも日本語版があるんですが、その価格は8200円+税。現在の貨幣価値に換算すると8856円である。これは酷いと言いたいところですが、私はすでにこの本を持っていたので何の問題もありませんでした。わーい。

外観

さて、いろんなパラダイムが使えるOzですが、その文法は(私はあまり好きではない)begin/end系です。

fun {Nreverse Lst} Rec in
   fun {Rec Lst Acc} Tmp in
      case Lst
      of cons(_ D) then
         Tmp = @D
         D := Acc
         {Rec Tmp Lst}
      else Acc
      end
   end
   {Rec Lst nil}
end

中括弧{}がブロックや集合以外の目的で使われているというのが少し珍しいのではないでしょうか。LISPに慣れている人はこの中括弧をただの括弧に読み替えるとしっくり来るかと思います。このNreverseの定義に今回言いたいことがほぼすべて入っているのですが、順をおって説明します。

LISPオブジェクトの表現

Ozはマルチパラダイム言語ゆえ、データを色々な方法で表現することが出来ます。クラスを使ってもいいし、DylanのときのようにOzの型をそのまま使うというのもひとつの手です。でも、今回のように簡単なLISPを作るのであればタプルを使うのが恐らく最善かと思います。Ozにおけるタプルとは name(Val1, Val2, ...) のような名前と値の列の組です。名前はシンボルで任意の名前を使えます。例えば num(42) とか error("invalid syntax") とか cons(X, Y) とかです。このタプルはパターンマッチングができるので非常に便利です。Nreverseを見なおしてみると of cons(_ D) then という部分がありますね。これは値がこのパターンにマッチした場合、変数DがコンスのCDR部に束縛される訳です。タプルを使うために面倒な宣言などを書く必要もありませんし、非常に楽な上に便利なわけですね。わーい。

破壊的代入

基本的にOzの変数はimmutableで書き換えることは出来ません。mutableなものを表現するためにはセルを使います。

fun {MakeCons A D}
  cons({NewCell A} {NewCell D})
end

このMakeConsは初期値Aをもつセルと初期値Dをもつセルを作り、それをタプルでまとめています。あらためてNreverseを見なおしてみると、 Tmp = @D とか D := Acc という箇所が出てきますね。 @ はセルから値を取り出す操作、 := はセルの中身を書き換える操作です。このセルのお陰で簡単に楽しい破壊的ライフがおくれるわけですね。わーい。

最後に邪魔をするのはbegin/end

そんなこんなで楽しくOzを書くことが出来たのですが、最後まで邪魔だったのがbegin/end系の文法です。42個中2個目の言語の時から「begin/endの文化があまり好きでない」と書きましたが、最後まで好きには慣れませんでした。ある程度は慣れたものの、このOzのときにも elseif と書くべきところで else if と書いてしまい「endが足らない」というコンパイルエラーにあったり悲しい目に会いました。

Booの思い出

「42個の言語でLISPを実装する」ことが決まった時には「最初と最後は難しくて面白い言語を使おう」と考えていました。実際に最初の言語はScratchというなかなかインパクトのある言語を使いました。でもそんな思いも使った言語が20を超えたあたりから「もうなんでもいいから早く終わりたい。出来るだけ簡単な言語。出来るだけ簡単な言語を使って少しでも早く終わらせるんだ」という非常に軟弱な思いによってかき消されてしまいました。
さて、このBooですがテキトーに調べてみると「型の付いたPythonみたいな言語」みたいな紹介がありました。こりゃとんでもなく楽に違いないと思い、最後の最後に一番楽な思いをしてやろうとBooを一番最後に使うことにしました。

外観

ではBooのプログラムを見てみましょう。

def nreverse(lst as object):
  ret as object = kNil
  while lst.GetType() == Cons:
    cell = toCons(lst)
    tmp = cell.cdr
    cell.cdr = ret
    ret = lst
    lst = tmp
  return ret

ところどころに lst as object とか型を明示している箇所を除くとPythonみたいです。これならすごく簡単そうですね。

相互再帰

相互再帰を使おうとしたら型のエラーが出ました。型の強い言語ではよくあることですね。ML系の言語なら相互再帰する関数は and で繋ぐ。Scalaなら相互再帰する関数は型を明示する。何らかの手段を取らないといけないというのは容易に想像が付くのですが、Booでの相互再帰の方法がいくら調べても見つかりませんでした。色々と試しても駄目。これまでの41個の実装ではアトムのリードとリストのリード、アトムの表示とリストの表示、evalとevlisとapplyとprogn。様々な関数が相互再帰を使っていました。もし相互再帰が使えないとなると、42個目にして実装方法を変えなければいけません。

どうするかしばらく考えました。この日は朝はランニング、午前から昼にかけてOzでLISPを実装、午後はBooでLISPを実装、夕方からは友人と焼肉を食べに行くという予定でした。OzでLISPを実装するところまでは順調だったのに、すぐに終わると考えていたBooでまさかの大問題。ここで遅れが出てしまうと焼き肉に支障をきたします。

プログラムの美しさと焼き肉を天秤にかけた結果、「相互再帰をすべて手で展開してしまえ」という結論に至りました。自己再帰は出来るのだから、単純に展開してしまうだけで動くはず。そう考えて美しさも何も気にせずに単純作業としてプログラムを書きました。他の言語では4個以上の関数に分けていたeval関連の関数もすべて1つの関数に。それはもう悲しいプログラムが出来上がりました。コミットログ

THis is the worst evaluator ever.

という言葉を書いてしまうくらい。 This をタイプミスしたことに気づかないくらい悲しみに満ち溢れていました。でも、この作業が案外簡単だったのが驚きでした。Booを使わなければ気づけなかったかもしれませんね。

やはり最後に邪魔をするのはbegin/end

BooはPythonと同じくインデントでブロックを表すオフサイドルールの文法で、begin/end系の文法ではないのですが、Ozを書いた直後に使ったせいで無意識に end と書いてコンパイルエラーになるという悲しい思いを何度もしました。本当にありがとうございました。

小学生並みの感想

end

[LSP42] PikeとProcessing

12月 23rd, 2014

(この記事はLISP Implementation Advent Calendar 23日目のためのエントリです。)

PikeProcessingでLISPを作りました。
https://github.com/zick/PikeLisp
https://github.com/zick/ProcessingLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその39〜40個目です。
Pikeはちょうどこのころネットニュースで「いまPikeが熱い!」みたいな記事が出てたので使うことにしました。
Processingは名前は知っていたものの明らかにLISPを作るのには不向きと思って使っていなかったんですが、「名前を知ってる言語は使ってしまえ」戦略により使うことにしました。

Pikeの思い出

さてここで問題です

Pikeの公式サイトを開いて初心者用のチュートリアルのページまで辿り着いてください。30秒以内に辿りつけた人は私より優秀なので、ぜひとも84個の言語でLISPを実装してください。

外観

Pikeは皆おなじみC-likeの文法です。

LObj nreverse(LObj lst) {
  LObj ret = kNil;
  while (consp(lst)) {
    LObj tmp = lst.cdr;
    lst.cdr = ret;
    ret = lst;
    lst = tmp;
  }
  return ret;
}

LObjは定義上スロットを持たないにもかかわらず、キャストもすること無く cdr にアクセスできます。

class LObj {
}

class Cons {
  inherit LObj;
  LObj car;
  LObj cdr;
  void create(LObj a, LObj d) { car = a; cdr = d; }
}

詳しくは調べてませんが、スロットの解決は実行時に行われるようです。そうなると、型を書くべきすべての場所に LObj と書くだけなので、実質的に型がないのと変わりません。コンパイル時に型をチェックしたい人には残念でしょうが私にとっては極めて楽でした。

_typeof

オブジェクトの型を比較する機能を探したんですが見つけることが出来ませんでした。代わりにオブジェクトの型を返す関数を見つけたので以下の様な方法で型を見ることに。

LObj kCons = Cons(kNil, kNil);
bool consp(LObj x) { return _typeof(x) == _typeof(kCons); }

まあ、動くんですけどなんだか微妙な感じに。

流行りの言語はやはり楽だった

冒頭に書いたとおり(当時)「いまPikeが熱い!」みたいな記事が出て、それなりに多くの人が反応していただけあって、Pikeは使いやすかったです。テキトーに書いてもなんだかよく分からないけど動く。Squirrel並みの速さでLISPを完成させることが出来ました。それ故に思い出が少ないです。

Processingの思い出

Processingといえばナウなヤングにバカウケな言語で、なんだかよく分からんけど視覚的にインパクトのあるチャラチャラしたプログラムを書くことに特化しているやつです。多分。でも今回はターミナルしか使いません。

標準入力なんてなかった

Processingの主な使用目的を考えたら当たり前のことなのですが、Processingには標準入力から文字列を読み込む機能なんてありません。幸い、Javaと連携する機能があるのでそれを使って標準入力から文字列をとってこようとしたのですが、コンパイルは通るもののなぜか上手く行かず。しかたがないのでLISPのプログラムはファイルから読み込むという方式に。これまでScratchを除くすべての言語で標準入力を使っていたので残念で仕方ありません。でもProcessingを使うのをやめて別の言語を探すほどの元気はなかったのでこの方式で逃げました。

外観

またしてもC-likeな文法です。

LObj nreverse(LObj lst) {
  LObj ret = kNil;
  while (lst.tag == CONS) {
    LObj tmp = lst.cons().cdr;
    lst.cons().cdr = ret;
    ret = lst;
    lst = tmp;
  }
  return ret;
}

次はLObjの定義を見てみましょう。

class LObj {
  int tag;
  Object data;
  LObj(int t, Object o) {
    tag = t;
    data = o;
  }

  Integer num() { return (Integer)data; }
  String str() { return (String)data; }
  Cons cons() { return (Cons)data; }
  Subr subr() { return (Subr)data; }
  Expr expr() { return (Expr)data; }

  ...
}

私の過去の記事を読んでいた人はすぐに分かりますね。完全にJavaです。public とか private とか書かない分記述が短くなったJavaです。ひょっとしたらまったくJavaっぽくない書き方ができたのかもしれませんが、ようやく40個目の言語までたどり着き、少しでも早く42個の言語でLISPを書き終えたかった私は深く考えず、限りなくJavaに近い何かを書くことに専念しました。

小学生並みの感想

やはり、頭を使わずに書ける言語は素晴らしいと思いました。

[LSP42] DylanとIokeとE

12月 22nd, 2014

(この記事はLISP Implementation Advent Calendar 22日目のためのエントリです。)

DylanIokeEでLISPを作りました。
https://github.com/zick/DylanLisp
https://github.com/zick/IokeLisp
https://github.com/zick/ElangLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその36〜38個目です。
DylanはLISPの派生言語と知っていたので絶対楽ができると思い、最後の方に楽をしようととっておいたものを満を持して使った感じです。
IokeはIoやSmalltalkについてWikipediaで調べている時に見つけたので使いました。
Eを選んだ理由はとよく覚えていませんが、恐らくWikipediaで見つけたのだと思います。なお「E」という名の言語は複数あるようですが、今回使ったのは「分散計算のための言語」であるEです。

Dylanの思い出

ファイルがいっぱい

マニュアルにそってhello worldを作ろうとしたら「まずこのコマンド実行しろ」という記述が出てきました。実行すると複数のファイルが生成されました。そう、私の嫌いな「hello worldを作るだけでも複数のファイルを適切な名前で適切な場所に置かないといけない言語」じゃないですか。やだー。ライブラリの依存関係とか解決してくれるのはいいですが、単一のファイルでもコンパイルして実行できるようにして欲しいです。あと、Dylanのツールはとにかく大量に出力します。コンパイラも成功失敗にかかわりなく物凄い量のメッセージを出します。あまりに出力が多すぎるためコンパイルエラーを見落とすということさえもありました。どうなんだ、これ。

外観

「DylanはかつてはLISPと同様のS式を使っていたが、途中で独自の文法を使うようになった」ということは知っていたのですが、それがどんな文法かは知りませんでした。知ってびっくり。(私があまり好きじゃない)begin/end系の文法でした。

define function pairlis(lst1, lst2)
  local method rec(lst1, lst2, acc)
    if (instance?(lst1, ) & instance?(lst2, ))
      rec(tail(lst1), tail(lst2), pair(pair(head(lst1), head(lst2)), acc));
    else
      reverse!(acc);
    end;
  end;
  rec(lst1, lst2, #());
end;

LISPみたいな言語を使えると思い込んでいた私はもうショックすぎて手元が狂いそうになりました。あと、マニュアルには end if とか end function 関数名 などと書いてあり、絶望のあまり死にそうになったのですが、 end の後の記述は省略可能と知って無事息を吹き返しました。でもまあ、見た目はアレですが、よく見るとLISPを知っている人なら簡単にLISPに書き換えられそうな感じですね。確かにLISPの派生言語という気もします。

インチキ

今回はLISPのオブジェクトはDylanのオブジェクトをそのまま使うというインチキをしました。つまり、LISPのシンボルにはDylanのシンボルをそのまま使い、LISPのコンスにはDylanのペア、LISPのSUBRにはDylanの関数をそのまま使うといった感じです。特殊なものとして、LISPのエラーはDylanの文字列を使い、LISPのEXPRはDylanのベクタを使って「引数/本体/環境」の3つ組を表しました。あとは上記pairlisのように instance? を使って型を見るだけです。
これで超簡単、超ラクチンとか思っていたんですが、いざ出来上がったものを見てみると、なんだかイマイチな感じに。単純に汚いのは最初から予想していたので別にいいんですが、なんだかよく分からないけど納得がいかない感じになってしまいました。書き直したい気もしましたが、先を急ぐためそのまま放置することに。

Iokeの思い出

Iokeは簡潔に言うと「JVMで動くIoみたいな言語」です(*)。JVMで動く言語は当たりが多いし、Ioは既に使ったことがあるので簡単に出来る予感がしました。

(*) 実際にはCLRとかの上でも動くらしいよ、お兄ちゃん!

外観

Iokeのプログラムはこんな感じの見た目です。

nreverse = method(lst,
  ret = kNil
  while(lst kind?("Cons"),
    tmp = lst cdr
    lst cdr = ret
    ret = lst
    lst = tmp)
  ret)

ここでIoのnreverseを見てみましょう。

nreverse := method(lst,
  ret := kNil
  while (lst tag == "cons",
    tmp := lst cdr
    lst cdr := ret
    ret := lst
    lst := tmp)
  ret)

代入が = なのか := なのかという違いくらいしかありません。まあ、実際には見た目以上に色々と違うのですが、そのあたりは各自勉強して下さい。あとデータ型のチェックについては後述します。

mimic

Iokeのドキュメントには「Iokeのオブジェクトは0個以上の cell と 0個以上の mimic を持つ」と書いてあります。ここで言うcellは値を入れる箱で、メソッドもcellの中に入れます。で、mimicって何だ。

Nil = Origin mimic
kNil = Nil mimic

Cons = Origin mimic
Cons initialize = method(a, d,
  @car = a
  @cdr = d)
makeCons = method(a, d,
  Cons mimic(a, d))

IokeはIoやJavaScriptと同じprototype-baseの言語であるという前提知識のもとに見るとmimicの意味がなんとなく分かるのではないでしょうか。そう、上記プログラムの mimic はIoでいうところの clone で、オブジェクトをコピーしているわけです。

ドキュメントの続きに目を通してみると「mimic は親オブジェクト(parent of the object)とも呼ぶ」と書いてあります。じゃあ、最初からそう書け。

更にドキュメントを読むと “mimic chain” なんて言葉も出てきます。なんでそう頑なに mimic という言葉を使うんだ。それはともかく、 mimic chain のなかに目的のオブジェクトが含まれているか判定する kind? というメソッドがあります。上記nreverseの lst kind?("Cons") です。なぜ引数が文字列なのか意味が分かりません。Ioにある同等のメソッド hasProto の引数はオブジェクトです。こっちのほうがしっくりします。ちなみに、Ioのときはこれについて速さの議論をしましたが、もう面倒なのでIokeではkind?を使わない話なんてしません。もう疲れました。

そのほかもろもろ

IoとIokeのnreverseの違いをしっかりと見た人は気づいたかもしれませんが、Ioでは while (...) と書いてある箇所が Iokeでは while(...) となっています。これは私が気分でスペースを入れたり入れなかったりしたというわけではありません。Iokeではメッセージに引数を付ける場合にはスペースを開けてはいけません。スペースを開けると、続くものは次のメッセージとして扱われてしまうからです。ある意味一貫したきれいな文法とも言えるんですが、ifやwhileのあとにスペースを入れてエラーになった時には困ったのでこのことはマニュアルの分かりやすいところにデカデカと書いて欲しかったです。

Iokeのドキュメントは、文法や全般的なことを書いた”Guide” と組み込みのオブジェクト一覧が書いてある “Reference” があります。しかしどちらを探しても標準入力から一行取得する方法が見つかりませんでした。しかし、よく考えてみるとIokeはJVMで動く言語であり、Javaとも連携できます。標準入力から読み込むところだけJavaのメソッドを呼んでやればいいんです。いいアイディアだと思ったんですが、試してみたらJavaの String とIokeの Text が違う型だと怒られました。必死に色々探して両者を変換する方法を見つけて何とかなったんですが、こういうのもマニュアルの分かりやすいところにデカデカと書いて欲しかったです。

これでSmalltalk系の言語はIo、Smalltalk、Iokeで3つ目となりました(処理系のインストールに失敗したので使わなかったけどSelfという言語も少し勉強しました)。思ったのは、みんなそれぞれ独自の世界を持っており、学習コストが妙に高いということです。Smalltalkは仕方ないとして、その後に続く言語がそれぞれちょっとずつ違うというのは初心者にはなかなかつらいです。短時間で学習してLISPを実装しないといけない人の気持ちも考えて欲しいです。

Eの思い出

「D言語は使ったから次はE言語だろ」という安直な考えで選びました。このE言語は分散処理のために設計されたみたいですけど、私の目的は簡単なLISPを実装することなので、分散処理についての機能は何一つ調べてないです。ごめんなさい。あとJVMで動きます。

インストール手順長すぎ

マニュアルを読んでEの処理系をインストールしようと思ったら物凄い長い手順が書いてありました。それはもう、全部見る前にそっと閉じてしまうくらい。この手順を無視してテキトーにやったら、なんだかよく分からいけど動きました。なんだかよく分かりません。

外観

EはC-likeな文法でなおかつ変数に型を書かなくていいので、なかなか私好みです。

def nreverse(var lst) {
  var ret := kNil
  while (lst.tag() == "cons") {
    def tmp := lst.cdr()
    lst.setCdr(ret)
    ret := lst
    lst := tmp
  }
  return ret
}

うん。見るからに簡単そうですね。

var

上記プログラムを見ると var ret := kNil のように var で変数を作っている箇所と、 def tmp := lst.cdr() のように def で変数を作っている箇所があります。この違いは、 var で作った変数はmutableで、 def で作った変数はimmutableになることです。便利なんですが、気になるのは引数の nreverse(var lst) というところ。なんだか参照渡しみたいじゃないですか。参照渡しに見えない人は見えるようになるまでFORTRAN系の言語でLISPを実装し続けてください。

:= と ==

Eの代入は := で、比較は == という演算子を使います。Eには = という演算子はありません。これはなかなかおもしろい試みだと思いました。かならず2文字タイプしないといけないというのは手間ですが、代入と比較を間違えることはほぼなくなります。あまり好みではないですがこういうものありだと思います。

Javaとの連携

EもJVMで動く言語なのでJavaのメソッドを呼び出せます。しかし、これを試そうとすると失敗。処理系のインストールを手順通りにしなかったバチが当たったのかもしれません。しかし、IokeのときのようにJavaのメソッドを呼ばないと解決できないような問題はなかったので、すべてをEのなかで完結させることで特に問題なくLISPを実装できました。

独自の名前

残念ながらEのドキュメントはあまり充実していません。でもJVMで動く言語だし、メソッド名などはJavaと同じものを使っているのだろうと思ったら、実際はぜんぜん違う名前を使っていました。文字列の長さは length ではなく size 。部分文字列は substring ではなく、変数に対してカッコを付けて foo(start, end) のように書きます。他にも色々と違いがあったかと思います。独自の名前をつけるのはかまいませんが、それならマニュアルを充実させて欲しいです。

小学生並みの感想

マニュアルが充実している言語はそれだけで素晴らしいと思いました。

[LSP42] Oberon-2

12月 21st, 2014

(この記事はLISP Implementation Advent Calendar 21日目のためのエントリです。)

Oberon-2でLISPを作りました。
https://github.com/zick/Oberon2Lisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその35個目です。
使った言語が30を超えてからは基本的に「名前を知ってる言語は使ってしまえ」戦略をとっていて、「次は本で見たことがあるModula-3を使おう」と思っていました。しかし、Modula-3の処理系のインストールが上手く行かず失敗。Wikipediaを読むとOberon-2という似たような言語があると書いてあり、こっちは処理系のインストールがうまくいったので使うことにしました。

外観

Oberon-2のプログラムはなかなかインパクトがあります。

PROCEDURE Nreverse(lst: LObj): LObj;
VAR
  ret: LObj;
  tmp: LObj;
BEGIN
  ret := kNil;
  LOOP
    WITH
      lst: Cons DO
        tmp := lst.cdr;
        lst.cdr := ret;
        ret := lst;
    ELSE
      EXIT
    END;
    lst := tmp  (* This statement can't be in WITH due to type checking. *)
  END;
  RETURN ret;
END Nreverse;

で、出た〜wwww大文字奴〜wwwwwww
教科書などに載っている古いFORTRANのプログラムみたいです。まあ、FORTRANを元にした言語なので間違ってはいないのですが、90年代に作られた言語なのにキーワードがすべて大文字なのはどうかと思います。でも、シンタックスハイライトがなくてもキーワードがすぐに分かるのはある意味いいかもしれませんね。見るぶんには。タイプするときにはたまったものじゃありません。

オブジェクト

Oberon-2ではレコード型があるので、これでLISPのオブジェクトを表すことにしました。

TYPE
  LObjDesc = RECORD END;
  LObj = POINTER TO LObjDesc;
  NilDesc = RECORD (LObjDesc) END;
  Nil = POINTER TO NilDesc;
  ConsDesc = RECORD (LObjDesc) car, cdr: LObj END;
  Cons = POINTER TO ConsDesc;

実際に使うときはレコードそのものより、そのポインタの方が便利なのでレコードとそのポインタにそれぞれ名前をつけます。レコードは継承関係を作ることが出来ます。上記NreverseのようにWITHを使ってキャストをすることもできます。
レコードの実体をつくるにはNEWを使います。

PROCEDURE MakeCons(a, d: LObj): LObj;
VAR
  cons: Cons;
BEGIN
  NEW(cons);
  cons.car := a;
  cons.cdr := d;
  RETURN cons
END MakeCons;

未初期化の変数に対してNEWを呼ぶのがなんだか違和感があります。ちなみに、NEWで作ったレコードはごみ集めによって自動的に回収されます。昔のFORTRANみたいな文法の言語とは思えないくらい気が利いてます。

メソッド

レコードに対してはメソッド(のようなもの)を定義することも出来ます。

TYPE
  SubrFnDesc = RECORD END;
  SubrFn = POINTER TO SubrFnDesc;
  SubrCarDesc = RECORD (SubrFnDesc) END;
  SubrCar = POINTER TO SubrCarDesc;
  ...
  SubrDesc = RECORD (LObjDesc) fn: SubrFn END;
  Subr = POINTER TO SubrDesc;
...
PROCEDURE (f: SubrFn) Call(args: LObj): LObj;
BEGIN
  RETURN MakeError("unknown subr")
END Call;

PROCEDURE (f: SubrCar) Call(args: LObj): LObj;
BEGIN
  RETURN SafeCar(SafeCar(args))
END Call;

関数Callは subr.fn.Call(args) のように呼び出します。 fn の型に応じてどの Call が呼ばれるかが決まるという仕組みです。 Call に現れる f はいわゆる this の役割で、好きな名前をつけることが出来ます。

論理積は & で、論理否定は ~ です。しかし論理和はなぜか OR です。意味が分かりません。
無条件ループをつくる LOOP では、それを抜け出す EXIT が使えるのに、条件付きループをつくる WHILE では EXIT が使えません。意味が分かりません。
なんか、色々と古臭いのに、処理系のヘルプを読む限りJITコンパイルをしてるみたいです。逆に意味が分かりません。

小学生並みの感想

大文字が許されるのはFORTRAN 77までだよねー

[LSP42] SquirrelとIcon

12月 20th, 2014

(この記事はLISP Implementation Advent Calendar 20日目のためのエントリです。)

SquirrelIconでLISPを作りました。
https://github.com/zick/SquirreLisp
https://github.com/zick/IconLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその33〜34個目です。
Squirrelはゲーム用のいわゆる組み込み言語です。Luaと同様の用途と聞いてそれなら簡単に違いないと思って使いました。
IconはWikipediaで見つけ、面白そうだったので選びました。マニュアルを見ると分かりますが、びっくりするくらいコンパクトな言語です。

Squirrelの思い出

外観

Squirrelのプログラムはこんな感じの見た目をしています。

class Nil {
}
kNil <- Nil();

class Cons {
  constructor(a, d) { car = a; cdr = d; }
  car = kNil;
  cdr = kNil;
}

function nreverse(lst) {
  local ret = kNil;
  while (lst instanceof Cons) {
    local tmp = lst.cdr;
    lst.cdr = ret;
    ret = lst;
    lst = tmp;
  }
  return ret;
}

そう。テキトーに書いても動くやつです。何も考えずに口を半開きにしてヨダレを垂れ流しながらでも書けるような簡単な言語です。やったー!

標準入力の罠

しかし、標準入力から一行取得しようとしたところでいきなりハマりました。そんな関数がライブラリにないのです。それどころか標準入力から一文字読み込むという関数もありません。使えそうなのはSquirrelのプログラムをロードするという関数。「シェルスクリプトと上手く連携させてユーザが文字列を入力するたびにファイルに書き込んでそれをロードして......」などと複雑なものを書き終えた後に、Squirrelの文字は8-bit整数で、標準入力から8-bit整数を読み込むとで文字の読み込みができる事に気付きました。マニュアルに注釈くらいは書いて欲しいです。

最速伝説

標準入力からの文字列の取得は戸惑いましたが、あとはマニュアルをほぼ読まずにテキトーに書いても、ほぼ想像通りに動いたのであっという間にLISPが完成しました。Squirrelはエラーメッセージが貧弱で分かり難いという問題点もありましたが、ほとんどエラーに遭遇しなかったので今回はあまり問題にならず。恐らく42言語中、もっとも早くLISPが完成しました。

Iconの思い出

外観

procedure の終わりには end がつくのでbegin/end系の言語かと思いきや、ブロックは中括弧{}で表します。

procedure makeCons(a, d)
    local obj
    obj := table()
    obj["tag"] := "cons"
    obj["car"] := a
    obj["cdr"] := d
    return obj
end

procedure nreverse(lst)
    local ret, tmp
    ret := kNil
    while lst["tag"] == "cons" do {
        tmp := lst["cdr"]
        lst["cdr"] := ret
        ret := lst
        lst := tmp
    }
    return ret
end

あと、久しぶりに連想配列でLISPのデータを表す方針を取りました。

Goal-directed execution

Iconの一番面白いところは goal-directed execution と呼ばれる機能でしょう。Goalの条件式の値は true/false ではなく success/failure の二種類の値を取り、式の一部が失敗したらその時点で全体が失敗します。

Wikipediaには次のような例が載っています。

while write(read())

これは write(read()) が成功し続ける限りそれを繰り返します。 read() はEOFを読み込むと失敗するので、そのときは「式の一部の失敗」となり、writeが呼ばれる前に式全体が失敗し、ループが終わります。
私のLISPでも同じ仕組を使ってみました。

while (exp := read1(read())) do {
    write(printObj(eval(exp[1], g_env)))
    writes("> ")
}

この goal-directed execution はなかなかに面白い機能だとは思うのですが、簡単なLISPを作るくらいだと使いドコロがほとんどなかったのが残念で仕方ありません。暇があればもっと色々と遊んでみたいところです。あとIconの日本語版Wikipediaはあまりにも間違った記述が多いので英語版を読むことをおすすめします。

range

Iconは部分文字列を取得するために str[start:end] のような書き方ができます。このindexは1-originで、exclusive (end-1番目の要素まで含む。end番目は含めない) です。この1-originとexclusiveの組み合わせはどうも違和感があります。多くの言語は0-originとexclusiveの組み合わせか1-originとinclusive (end番目の要素を含む) の組み合わせだと私の直感が言っています。inclusiveだとサイズ0のrangeを表現できないのでIconはexclusiveにしたのではないかと思いますが、それなら0-originにして欲しいです。あと、終端までのrangeを取得する方法が str[start:0] というのもちょっと違和感があります。

小学生並みの感想

何はともあれ型を書かなくて良い言語は最高だと思いました。

[LSP42] Smalltalk

12月 19th, 2014

(この記事はLISP Implementation Advent Calendar 19日目のためのエントリです。)

SmalltalkでLISPを作りました。
https://github.com/zick/SmalltalkLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその32個目です。
Smalltalkといえば、開発環境と実行環境が共に同一のGUI環境という世界が特徴で、CUIのアプリケーションを作るのには不向きだと思っていたのですが、同僚から「GNU SmalltalkはCUIしかない」と聞いて、Smalltalkを使うことにしました(余談ですが、今のGNU SmalltalkはGUIの環境を備えています)。

OSX版の罠

GNU SmalltalkをOSXにインストールして、チュートリアルを読みながら簡単なプログラムをいくつかREPLから試し、「よしこれでLISPが書けるだろう」と思い、標準入力から一行取得するプログラムを書いたところでいきなりハマりました。 line := stdin nextLine. なんとこのプログラムを動かすとSIGABRTが飛んできます。意味が分かりません。試しにUbuntuにGNU Smalltalkをインストールして動かしてみるとちゃんと動きました。ちょっと酷い。

外観

Smalltalkといえば独特の文法でも有名ですね。

Util class >> nreverse: lst [
  | l tmp ret |
  l := lst.
  ret := kNil.
  [(l class) = Cons] whileTrue: [
    tmp := l cdr.
    l setCdr: ret.
    ret := l.
    l := tmp
  ].
  ^ret
]

Util class >> pairlis: lst1 with: lst2 [
  | l1 l2 ret |
  l1 := lst1.
  l2 := lst2.
  ret := kNil.
  [((l1 class) = Cons) & ((l2 class) = Cons)] whileTrue: [
    ret := Cons new: (Cons new: (l1 car) with: (l2 car)) with: ret.
    l1 := l1 cdr.
    l2 := l2 cdr
  ].
  ^self nreverse: ret
]

知識としては知っていたのですが、いざ書いてみるとなかなか混乱します。特にドットとコロンを書き忘れることが非常に多く、42個の言語の中でも私がコンパイルエラーを起こした回数No1の業績を残したような気もします。あと、上記pairlisの with のように引数の前に名前をつけるといいう文化も最後まで馴染みませんでした。SmalltalkやObjective-Cが好きな人は「これがいいんだ」と主張しますが、慣れていない私は何かと with とタイプする回数が増えるだけでした。

オブジェクト指向

さて、Smalltalkといえばオブジェクト指向です。しかし、これまで使った30以上の言語の中でオブジェクト指向っぽくLISPを作ったことがほとんどない私です。今回も「オブジェクト指向なんかに負けない!」と気合を入れてプログラムを書きました。

Object subclass: LObj [
  LObj class >> new: t [^super new]
]

LObj subclass: Nil [
  print [^'nil']
  eval: env [^self]
]

LObj subclass: Cons [
  | ar dr |
  Cons class >> new: a with: d [^super new setData: a with: d; yourself]
  setData: a with: d [ar := a. dr := d]
  setCar: a [ar := a]
  setCdr: d [dr := d]
  car [^ar]
  cdr [^dr]
  print [
    | obj ret first |
    obj := self.
    ret := ''.
    first := true.
    [(obj class) = Cons] whileTrue: [
      first = true ifTrue: [
        first := false
      ] ifFalse: [
        ret := ret, ' '
      ].
      ret := ret, ((obj car) print).
      obj := obj cdr
    ].
    (obj class) = Nil ifTrue: [
      ^'(', ret, ')'
    ] ifFalse: [
      ^'(', ret, ' . ', (obj print), ')'
    ]
  ]
  eval: env [^Util evalCompound: self env: env]
]

各クラスが print と eval というメソッドを持っています。オブジェクトにevalというメッセージと環境を渡すと値が得られるわけです。
書きやすいように作ろうと思ったら気が付いたらオブジェクト指向っぽくなってしまいました。なんか非常に悔しい。違う書き方をした方が速い気もしますが、面倒なのでそのままにしました。

終わらないごみ集め

Smalltalkのように柔軟な言語は引数の数が正しいかなどは、コンパイル時には分からず実行時にエラーになることがあります。私は柔軟さが好きなのでこれは仕方ないことだと思っているのですが、GNU Smalltalkは引数の数を間違えた時に、なぜかプログラムが停止せずにごみ集めが動き続けるという大惨事になることがあります。かなり酷い。

小学生並みの感想

まじめに勉強してないから書くことがない!