Archive for 12月, 2014

[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は引数の数を間違えた時に、なぜかプログラムが停止せずにごみ集めが動き続けるという大惨事になることがあります。かなり酷い。

小学生並みの感想

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

[LSP42] Eiffel

木曜日, 12月 18th, 2014

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

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

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその31個目です。
Eiffelは名前を知っているので選んだという感じです。Eiffelのことはほとんど知りませんでしたが、スクリプト言語のように気軽に書けるものではないと考えていたのでずっと後回しにしてきました。しかし、実装に使った言語がいよいよ30を突破して、言語を選ぶのが非常に難しくなってきたので名前を知ってる言語はなんでも使ってしまおうと思いました。

外観

まずはこのプログラムをご覧ください。

class CONS

inherit
  LOBJ

create
  make_cons

feature
  car: LOBJ assign set_car
  cdr: LOBJ assign set_cdr

  set_car(x: LOBJ)
    do
      car := x
    end

  set_cdr(x: LOBJ)
    do
      cdr := x
    end

  make_cons(a: LOBJ; d: LOBJ)
    do
      car := a
      cdr := d
    end

end

「あ、この文法、教科書で見たやつだ!」と私は思いました。なんというか、ドキュメントをそのままプログラムにしたような感じといいますか、簡潔に言うと「古臭い」です。クラス名がすべて大文字なのも古臭くていい感じです。

オブジェクト指向

Eiffelはずばり、
「俺はオブジェクト指向言語だ! プログラムを書きたかったらまずクラスを作れ! クラスを作るたびにファイルを作れ! ヒャッハー!!!」
が完全に当てはまってしまいました。上記 CONS クラスのために新たなファイルを作る必要がありますし、 CONS のベースクラスである LOBJ クラスのためにも新たなファイルを作る必要があります。

class LOBJ
end

この2行だけで1つのファイルです。正直どうかと思います。でも、この文法とは妙にマッチしているような気もしました。

Void-safety

まずは次のプログラムをごらんください。

  nreverse(l: LOBJ): LOBJ
    local
      lst: LOBJ
      tmp: LOBJ
    do
      Result := kNil
      from
        lst := l
      until
        lst = kNil
      loop
        if attached {CONS} lst as c then
          tmp := c.cdr
          c.cdr := Result
          Result := lst
          lst := tmp
        else
          lst := kNil  -- break
        end
      end
    end

「うわっ、この文法、パパの枕の臭いがする!」という話ではなく、見るべくは if attached {CONS} lst as c then のところです。型がCONSか確認しているのですが、同時に Void (他の言語で言うNULL) でないことも確認しています。Eiffelは値がVoidになり得るかどうかをコンパイル時に確認しており、Voidの可能性がある場合にチェックなしで中身にアクセスしようとするとコンパイルエラーになります。見た目はともかくよく出来てます。
ちなみに、この attached は昔のEiffelには無かったようで、古い資料には載っていません。具体的には日本語版Wikipediaとそのリンク先。資料のとおりに書いたのにコンパイルエラーになったときは非常に悲しかったです。

コンパイル時の型チェック

上のVoid-safetyの話からも分かる通り、Eiffelはコンパイル時に色々なチェックをします。未初期化の変数の使用もちゃんと関数を超えてチェックします。ただ、配列の境界などはチェックしてくれません。「そのためには依存型を云々……」などという難しい話ではなく、配列の index が1-originなのにリテラルの 0 を書いてもコンパイルエラーにならないのはちょっと。

TUPLE

Eiffelにはタプルがあって、["ABC", 123] と書くと TUPLE [STRING, INTEGER] という型になるようです。しかし、タプルから要素を取り出す item という関数の型は問答無用で ANY (すべてのベースとなる型) になります。型はどうした。マニュアルでTUPLEを調べてみると integer_item とか boolean_item という関数があり、それぞれ INTEGER, BOOLEAN を返すようです。正直意味が分かりません。なんなんだ、これ。

契約

Eiffelといえば契約による設計ですね。(私を含め)Eiffelがどんな言語なのかほとんど知らない人も「Eiffelといえば契約による設計」と呪文のように覚えている人は多いのではないでしょうか。しかし、私にとっての目的は「なるべく早く42個の言語でLISPを実装する」ことだけなので、LISPを作るのに不要な機能は積極的にスルーしたので、契約による設計を意識することは一切ありませんでした。マニュアルを読んでる時に invariant とか ensure とか書いてるあたりがきっとそうなんだろうなーと思ったり、それっぽいコンパイルエラーをみって、きっとこれがそうなんだろうと思いつつ全てスルーしました。

小学生並みの感想

もっと勉強しないといけないと思いました。

[LSP42] LiveScript

水曜日, 12月 17th, 2014

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

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

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその30個目です。
JavaScript系の言語(*)はだいたいやり尽くしたと思っていたのですが、調べてみたらLiveScriptという言語がまだ残っているのに気づいたのので使うことにしました。

(*) ここでは、JavaScriptに変換できたりJavaScriptの代わりに使えるような言語のことだよ、お兄ちゃん!

禁断の項目

LiveScriptのマニュアルを上から順に読んで、そろそろLISPを作るのに十分な知識が得られたかなと思ったところで、マニュアルにCoffeeScript to LiveScript Conversion Guideという項目があることに気付きました。

これだけ

CoffeeScriptで書いたLISPを、LiveScriptとして動かしてみたら、途中まで動いてエラーを吐いて止まりました。エラーメッセジを見て修正、というのを3回ほどしたら完全に動いてしまいました。

% cat lisp.coffee \
| sed -e 's/str\[\([^.]*\)\.\.\.\]/str\.substring\(\1\)/g' \
| sed -e 's/str\[\.\.\.\([^]]*\)\]/str\.substring\(0, \1\)/g'  \
| sed -e 's/\.\.\./ til /g' > livelisp.ls

CoffeeScriptの [from...end] というrangeの構文を [from til end] に変えたのと、CoffeeScriptで部分文字列の取得にrangeの構文を使っていたのをsubstringというメソッドを呼ぶように変えただけです。

小学生並みの感想

これは酷いと思いました。

[LSP42] KotlinとJuliaとScala

火曜日, 12月 16th, 2014

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

KotlinJuliaScalaでLISPを作りました。
https://github.com/zick/KotlinLisp
https://github.com/zick/JuliaLisp
https://github.com/zick/ScalaLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその27〜29個目です。
Kotlinは例によって「JVMで動く(Java以外の)言語は(それなりの確率で)簡潔で簡単なはず」という私の脳内で成り立つ法則に基いて選びました。
JuliaはWikipediaを眺めている時に見つけて簡単そうだったので選んだような記憶があります。
Scalaも「JVMで(以下略)」で選びました。

Kotlinの思い出

I・D・E!! I・D・E!!

マニュアルを読みながらKotlinの処理系をインストールしていると「次にIDEの設定をします」という説明が出てきました。数百行のプログラムを書くだけなのでIDEは使わなくていいや、と思ったものの、いくら探してもコマンドラインからKotlinを使う方法が見つかりませんでした。色々と検索してもなかなか見つからず、かなり時間を書けて頑張った末にコマンドラインからの実行方法が分かりました。

% kotlinc-jvm -src kotlinlisp.kt -jar lisp.jar -includeRuntime && java -cp lisp.jar lisp.LispPackage

IDEが使えることは素晴らしいことだとは思いますが、マニュアルには是非ともIDE以外からの使い方も載せて欲しいです。

外観

今どきっぽい感じで嫌いじゃありません。トップレベルに関数が定義できるのも良いです。

class Nil {
}
val kNil = Nil()

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

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
}

型をそれなりに書かないといけないのは少々面倒ですが、某言語の function 名前(引数) : 型 という非常に冗長な構文を見た後だと、fun の3文字が非常に短く見えて幸せな感じです。

エラーメッセージ

Kotlinのコンパイラのエラーメッセージは一昔前のC++コンパイラ並にくどいです。例えば上のプログラムの Cons のコンストラクタの引数の型を省略してみると、次のようなエラーが出ます。

ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (42, 13) Parameters must have type annotation
ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (42, 16) Parameters must have type annotation
ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (231, 26) Overload resolution ambiguity:
internal final var car: [ERROR : Type annotation was missing] defined in lisp.Cons
internal open var : [ERROR : ] defined in root package

ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (232, 23) Overload resolution ambiguity:
internal final var car: [ERROR : Type annotation was missing] defined in lisp.Cons
internal open var : [ERROR : ] defined in root package

ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (234, 22) Overload resolution ambiguity:
internal final var cdr: [ERROR : Type annotation was missing] defined in lisp.Cons
internal open var : [ERROR : ] defined in root package

ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (397, 27) Overload resolution ambiguity:
internal final val data: jet.Int defined in lisp.Num
internal open var : [ERROR : ] defined in root package

exec() finished with COMPILATION_ERROR return code

長い。長すぎる。いくらなんでも長過ぎる。一番上の行を見れば「パラメータにタイプアノテーションをつけろ」と言ってるので何を間違えたかは明らかなんですが、なにもこんなに長いエラーメッセージを出さなくていいじゃないですか。

Juliaの思い出

外観

Juliaは変数や関数に型を書きません。私にとって大事なのはその一点です。

type Cons
  car
  cdr
end

function nreverse(lst)
  ret = kNil
  while isa(lst, Cons)
    tmp = lst.cdr
    lst.cdr = ret
    ret = lst
    lst = tmp
  end
  ret
end

function pairlis(lst1, lst2)
  ret = kNil
  while isa(lst1, Cons) && isa(lst2, Cons)
    ret = Cons(Cons(lst1.car, lst2.car), ret)
    lst1 = lst1.cdr
    lst2 = lst2.cdr
  end
  nreverse(ret)
end

このところ型を書く必要がある言語がずっと続いていたので型を書かない言語の素晴らしさを改めて再発見しました。型を書く必要がないという事実を前にしたら、あまり好きでないbegin/endの構文も、冗長なキーワードfunctionも大した問題ではありません。もう最高。とにかく最高。素晴らしい。

多分良い言語です

マニュアルを流し読みしたところ、Juliaはかなりいい言語のように見えました。ただ、あまりにも気軽かけるので1時間ちょっとでLISPが完成してしまったためあれこれ試す間もなく終わってしまったのが残念です。

Scalaの思い出

Scalaは実のところ使うのを避けていたんですよ。というのも、それなりに有名でカッコよく使っている人が多い言語なので、不勉強な状態でカッコ悪いLISPを書くのも嫌じゃないですか。LISPなのに。でも名前が思い浮かぶ言語がどんどん減ってきたので仕方なく使うことに。

外観

Scalaはそれなりに型を書かなければなりません。でも、型推論のおかげでかなりの箇所で型を省略できます。

def nreverse(lst: LObj) = {
  def doit(lst: LObj, ret: LObj): LObj = {
    lst match {
      case Cons(c) => {
        val tmp = c.cdr
        c.cdr = ret
        doit(tmp, lst)
      }
      case _ => ret
    }
  }
  doit(lst, kNil)
}

関数型言語らしく末尾再帰の形で書いています。これは趣味の問題ではなく、Scalaにはwhileというループ用の構文があるものの、いわゆるbreak相当のものがないので、ちょっと凝ったループをしようと思った場合は末尾再帰を使わないとかえって難しくなります。

case class

Scalaにはcase classというものがあり、これを使うとpretty printerが作られたり、型のパターンマッチができるようになったり、色々と便利なメソッドが自動で定義されるようです。こりゃ使わざるを得ないな、と思ったら、自動で比較関数まで作ってくれるらしく、これが内容比較なので、アドレス比較をしたい私にとっては邪魔でしかありません。そこで、case classのフィールドに直接値を入れるのではなく、フィールドにclass instanceを入れることで実質的にアドレス比較を行うようにしました。

abstract class LObj

class Nil0 {
}

class Cons0(a: LObj, d: LObj) {
  var car = a
  var cdr = d
}

case class Nil(obj: Nil0) extends LObj
val kNil = Nil(new Nil0)

case class Cons(obj: Cons0) extends LObj
def makeCons(a: LObj, d: LObj) = Cons(new Cons0(a, d))

このやり方が普通なのか異常なのかは知りませんが、少なくても今回に限ってはそれなりにうまくいきました。行数が増えるという問題を除いては。

再帰と相互再帰

OCamlは再帰をする関数を定義するときには rec というキーワードを付けました。Scalaはといいますと、再帰をする関数は戻り値の型を明記します。上のnreverseの内部で定義してあるdoitがそうなってますね。

さて、相互再帰の場合はStandard MLとOCamlは型推論の都合上、相互再帰をする関数を and で繋ぐ必要がありました。Scalaは通常の再帰と同様に戻り値の型を明記します。

def printObj(obj: LObj): String = {
  obj match {
    case Nil(_) => "nil"
    case Num(n) => n.data.toString
    case Sym(s) => s.data
    case Error(e) => ""
    case Cons(_) => printList(obj)
    case Subr(_) => ""
    case Expr(_) => ""
  }
}

def printList(obj: LObj): String = {
  def doit(obj: LObj, first: Boolean, ret: String): String = {
    obj match {
      case Cons(c) =>
        doit(c.cdr, false, ret + (if (first) "" else " ") + printObj(c.car))
      case Nil(_) => "(" + ret + ")"
      case _ => "(" + ret + " . " + printObj(obj) + ")"
    }
  }
  doit(obj, true, "")
}

複数の関数を and で繋ぐよりはこっちのほうが個人的に好きです。

小学生並みの感想

やはり簡単に書ける言語は素晴らしいと思います。