リリカル☆Lisp開発日記

先日述べたとおり、Kashiwa SchemeはSchemeからCへのトランスレータであり、
Schemeの(CPS変換された)手続きはCの関数に変換されます。
しかし、そのCの関数ではreturnにたどり着くことはなく、スタックは伸び続けます。
(詳しくは元ネタのこの論文を読んでください)

とまあ、本当にスタックが伸び続けたらいつかは死んでしまう訳で、
実際のところはスタックが一定より伸びた所で手を打ちます。
具体的には、スタック上にある『必要なもの』だけをヒープにコピーして、
longjmpを呼び出してスタックを巻き戻してから処理を再開します。

変換されたCの関数というのは以下のような形をしています

static void fun112_(env_t* penv113_, lobject g108_) {
  cont_t clos125_;
  env_t* cenv114_;
  check_stack(fun112_, penv113_, 1, g108_);
  ... (略)  ...
}

見ての通り、先頭でcheck_stackという関数を呼んでいます。
この関数は、スタックがどれほど伸びたかを確認します。
そして、スタックが閾値より伸びていた場合、
最後に呼ばれた関数(この場合fun112_)とその引数の値をヒープに保存して、
先ほど保存した引数からたどれるオブジェクトをすべてヒープにコピーします。
コピーが終了すると、longjmpでスタックを巻き戻し、
ヒープに保存した情報(最後に呼ばれた関数と引数)を使って処理を再開します。

「関数はreturnにたどり着かないため、呼び出し元に戻ることはない」
ということは
「最後に呼ばれた関数とその引数さえ覚えておけば処理を再開できる」
というわけです。
ただし、スタックに作ったSchemeのオブジェクトは、
『必要があれば』ヒープに移動する必要があります。
逆に言えば不要なものは捨ててしまうわけです。

この「オブジェクトのスタックからヒープへのコピー」という処理は、
スタックを”from space”、ヒープを”to space”としたcopying GCとみなせます。
ここでCheneyのアルゴリズムを用いると、
これ以上スタックを消費することもなく、安心してごみ集めを行えるわけです。

今回書いたのはこのスタックにおけるごみ集めだけで、
ヒープにおけるごみ集めはまだ書いてません。
まあ、こちらはただのごみ集めになるのであまり面白みもなさそうです。

面白いのが、スタックからヒープへのコピーという処理は、
スタックをyoung領域、ヒープをold領域とした世代別GCとも見なせる点です。
……と、ここまで書いた時点で、ヒープからスタックへの参照を、
remember setに入れて覚えておく必要がありそうな気がしてきたけど、
そんな処理は書いてないぞ。なんてこった。ライトバリアとか書きたくないぞ。

ええ、そうです。
また、Schemeの処理系を書き始めました。
これでLisp(系)処理系を書くのが何度目か数えるのも面倒になってきました。

今回作っているのはSchemeからC言語へのトランスレータで、
現在、こんなコードをコンパイルして動かすことができます。

(define cc 0)
(define (f x)
  (cons
   (call-with-current-continuation
    (lambda (k)
      (set! cc k)
      0))
   x))

(write (f 3))      ; => (0 . 3)
(newline)
(write (cc 48))  ; => (48 . 3)
(newline)

まだシンボルも作っていませんが、既にcall/ccが動作します。
完成まで程遠いのに『Kashiwa Scheme』という名前は決めました。

—

さてさて、時を遡ること、約半年。
偶然Chicken SchemeのWikipediaの記事を読んで衝撃を受けました。

A scheme program is compiled into C functions. These C functions never reach the return statement; instead, they call a new continuation when complete.

Schemeの手続きをCの関数にコンパイルするにもかかわらず、
そのCの関数は一切returnしないというのです。
説明を書くと長くなりそうなので、詳しくはこの論文を読んでください。

ということで、この実装があまりにも楽しそうだったので、
私も真似してみようと思い、Kashiwa Schemeを書き始めました。

今のところ、Cのreturnを一切使わないという目標は達成できているんですが、
この実装方法のもう一つの肝である『スタックを対象としたごみ集め』に関しては、
まだ一切コードを書いていません。ここを書くのが楽しみなんですが、
先にシンボルを作ったり煩雑なところを少し進めることになりそうです。

—

継続について気になったことがあったので少しメモ。

最初、トップレベルの(define以外の)式は1つの手続きにまとめて、
Cのmain関数からはその手続き(をCの関数に変換したもの)を、
呼び出すような作りにしていました。

;;; コンパイル対象
(define (f x) ...)
(define (g y z) ...)
(f 3)
(g 4 5)

;;; main関数からこの手続を呼ぶ
(lambda ()
  (f 3)
  (g 4 5))

多くの場合はこれで問題なく動いたんですが、
call/ccが出てくると問題が発生しました。

例えば、上記のプログラムの場合、手続きfの途中で継続を取り出し、
手続きgの中でその継続を呼びだしてしまうと、
手続きfの途中から処理が再開してしまうため、再び手続きgが呼ばれ、
プログラムが無限ループに陥ってしまいます。

Schemeのレベルでこの問題を解決する方法が思いつかなかったため、
C言語のレベルで汚らしい方法で解決してしまったんですが、
なんとかならないものなんでしょうかね。
CPS変換についてもう少し詳しく調べたら定番の方法でも見つかるのかな。

何を言ってるのか　わからねーと思うが、
取り敢えず下の2つのファイルを御覧ください。

;;; a.lisp
(defmacro foo (x)
  `(list ,x ,x))

;;; b.lisp
(defun bar ()
  (foo (+ 1 2)))  ; 上記マクロを使いたい

処理系を起動した直後に、
これらのファイルを次のようにコンパイルする場合を考えます。

(compile-file "a.lisp")
(compile-file "b.lisp")

さて、この行為は実は問題があります。
a.lispをコンパイルしただけでは、マクロfooは定義されません。
そのため、b.lispをコンパイルするときにfooは未束縛になってしまいます。

例えばAllegro CLであればコンパイル時に次のような警告が出ます。

Warning: While compiling these undefined functions were referenced:
FOO from character position 0 in b.lisp

Clozure CLであればこんな感じ。

;Compiler warnings for “b.lisp” :
; In BAR: Undefined function FOO

上記メッセージから分かるように、fooが関数扱いされるため、
この後、コンパイル済みのファイルをロードして、
(bar)を評価するとエラーになります。

と　こ　ろ　が、
SBCLやCLISPで同じ事をやると、問題なく動いてしまいます。

(compile-file "a.lisp")
(compile-file "b.lisp")
(load "b")
(f)  ; => (3 3)

コンパイル時に警告がでることもありません。

何が起こっているのか調べてみたところ、
compile-fileした時点で、マクロが定義されているみたいです。

(compile-file "a.lisp")
(macro-function 'bar)  ; => #<FUNCTION>

これは驚きです。

でも、ポータブルなコードでなくなるので、
こんなコードは書かないほうがいいでしょう。

リリカルLisp ver1.5を公開しました。
約半年ぶりの更新です。

今回の変更点は、エラーのチェックです。
今までのバージョンでは、実引数が仮引数より多かろうが、少なかろうが、
未束縛の変数を使おうが、シンボルの足し算を行おうが、
どんな無茶をしても、(大抵の場合、意味のない)値が返ってきました。
それが、今回の変更で「エラーです」と通知する機能が付きました。

> x
エラー：top-levelにおいて、xは未束縛です
> (cons 1)
エラー：consに与える引数が少なすぎます
> (+ 'a 'b)
エラー：+において、aは数ではありません
> (let 3 4)
エラー：letの使い方が間違っています

大体こんな感じです。
日本語を選ぶのに苦労しました。

—

プログラミング言語の学習(した気分になる)ソフトなのだから、
このような機能は付いていて当たり前だとは思うのですが、
最初のバージョンでは時間の関係から付けることができませんでした。
そして、その後は、
「今更、そんなものつけてもなー」
という思いからずっと放置されてきました。

今になってエラーのチェックを付けた理由は、
次のようなメールがきたからです。

I can’t get past lesson 2. When I type
(define x 4)
the result is x
Then, when I type
(* (x+3) 4)
the result is -2358896
I thought it should be 28

なんというか、ごめんなさい。
もう放置しても誰も困らないだろうと思っていたけど、
そんなことはなかったみたいです。

—

余談ですが、
リリカルLispのソースをgithubで公開してからちょうど1年が過ぎました。
誰も触ってくれないだろうなと思っていたけど、
ほんとに誰も触ってくれませんでした。
ショックですっ ＞＜

compileは対象の関数のみを見て最適化を行うのに対して、
compile-fileはファイル内すべての関数/変数を見て最適化を行えるので、
両者の結果が異なるのは、当たり前といえば当たり前です。
しかし、ファイルに単一の関数しかなくても、
compileとcompile-fileの生成するコードが異なることがあります。

(defun f ()
  (eq '(a b c) '(a b c)))

SBCLやAllegro CLにおいて、
関数compileでコンパイルした場合、(f)の値はNILとなりました。
しかし、関数compile-fileでこの関数をコンパイルすると、(f)の値はTとなりました。
＃残念なことに、CLISP、Clozure CLではどちらの場合もNILとなりました。

さて、compile-fileした場合Tになる理由は前回のエントリを読んでください。
＃前回の実験ではACLではcoalesceは行われませんでしたが、
＃今回の実験ではcoalesceが行われているようです。
＃恐らく、関数単位でcoalesceを行なっているのではないかと思います。

compileした場合にNILになる理由は、すばりcoalesceが行われていないからです。
では、何故coalesceが行われないかというと理由は簡単。
仕様でそう決まっているからです。

Literal objects appearing in code processed by the compile function are neither copied nor coalesced. The code resulting from the execution of compile references objects that are eql to the corresponding objects in the source code.

CLHS Function COMPILE

理由は分かるんですが、ややこしい話です。

Common Lispでは、
よく似てるけどeqlではない2つのリテラルを含むソースをコンパイルしたら、
コンパイル後には2つのリテラルがeqlになることがあるそうです。
そのことを「2つのリテラルはコンパイラによって合体された」と言うとか何とか。

ちゃんとした定義はこちら
(“similar”は「似ている」ではなく厳密な定義が与えられています)

coalesce v.t. (literal objects that are similar) to consolidate the identity of those objects, such that they become the same object. See Section 3.2.1 (Compiler Terminology).

(CLHS 26.1 Glossary)

The term coalesce is defined as follows. Suppose A and B are two literal constants in the source code, and that A’ and B’ are the corresponding objects in the compiled code. If A’ and B’ are eql but A and B are not eql, then it is said that A and B have been coalesced by the compiler.

(CLHS 3.2.1 Compiler Terminology)

ということで実際に試してみました。
使用したのはSBCL 1.0.50です。

(defvar a '(a b c))
(defvar b '(a b c))

こちらのソースコードをloadして (eql a b) を試したところ、NILになりました。
しかし、compile-fileしたものをloadすると、 (eql a b) の値はTになりました。
まさに2つのリテラルが合体したという感じです。

ちなみに、CLISP、Clozure CL、Allegro CLではcompile-fileしてもNILのままでした。
smilarなリテラルがたくさん出てくるようなソースコードでは、
リテラルを合体した方が、コンパイル後のバイナリファイルのサイズや、
ロードした際のヒープの使用量を節約できそうですが、
コピペを繰り返したソースでもない限り、効果は薄いような気がします。
誰かcoalesceの効果の程を測った人とかいないんでしょうかね。

こんなメールがきた。

I get an error using Lyrical Lisp with the latest NScripter.
“グローバル変数設定に写える数字大きすぎます。”
Do you know the cause?

で、実際にNScripterを最新のものに差し替えて実行したら、
確かにエラーメッセージが表示されました。
そんなわけで修正を加えたバージョン、
ver1.4.1を作ったんですが、この変更を嬉しがる人も少なそうなので、
zipで固めたものは作らず、スクリプトファイルだけを置いときます。

nscript.dat (ver1.4.1)
(2011/09/03 追記)
新しいバージョンがリリースされましたので、こちらをご利用ください。

必要な方は、リリカルLisp ver1.4のnscript.datとこれを差し替えてください。

先日、後輩が
「風子の誕生日を祝ったのに、観鈴ちんの誕生日を忘れてた人がいるらしいですよ」
と私の古傷をえぐってきたので、
傷を癒すためにゲームを作った。

遊ぶ

どっかで見たことがあるようなゲームな気もするけど、
たぶん気のせいだろう。

突然ですが、(/ 22 7.)この式の値は何でしょうか。
7の後にドットがあるのがポイントです。

実際に評価してみると、
Common Lispでは22/7といったように分数になり、
Schemeでは3.142857142857143というように小数になります。

CLHSのここを見れば分かる通り、CLでは数の後にドットのみが続くものはintegerとして扱い、
R5RSのここにあるように、Schemeではintegerとして扱わないようです。
あまり困ることもないでしょうが紛らわしい話です。

＃ちなみに本日7/22は「円周率近似値の日」らしいですよ

* はじめに *
ここ最近(昔から?)、C言語の本や記事などに
「ポインタを使うことで参照呼び(call by reference)が…」
なんて書いてあると、
「C言語には値呼び(call by value)しかないくぁwせdrftgyふじこlp…」
などというツッコミで荒れるみたいでが、
C++の本や記事に「参照呼び」と書いてあることで荒れるところを
(少なくても私は)見たことがないのが不思議なので、このエントリを書きます。

* 参照でcall by reference? *
C++でこんなコードを書くと、

int f(int& x) { ... }
int g() {
  ...
  f(a + 1);
  ...
}

こんな感じのエラーが出ますと。

error: invalid initialization of non-const reference of type ‘int&’ from a temporary of type ‘int’
error: in passing argument 1 of ‘int f(int&)’

C++がこういう仕様であること自体には何も問題はないと思います。
でも、これがエラーになるということは、C++の参照を使っても、
call by referenceにはなっていないということです。

* call by referenceの定義 *
私が説明をつらつらと書いても納得してもらえなさそうなので、
有名どころから引用します。

参照呼び

引数を参照呼び(番地呼びまたは記憶場所呼びともいう)にすると，一般には，
呼出側の手続きは，呼び出される側に対して，次のように実引数の記憶場所
の番地を渡す．

1. 実引数が名前または左辺値をもつ式であれば，その左辺値自身を渡す．
2. しかし，実引数がa+bや2のような式であれば，左辺値はないので，式を
   評価して，その値を新しい記憶場所に格納し，その番地を渡す．

(『コンパイラII 原理・技法・ツール』 初版 517ページ)

ついでにもう一冊

This parameter-passing mechanism is called call-by-reference. If an operand is simply a variable reference, a reference to the variable’s location is passed. The formal parameter of the procedure is then bound to this location. If the operand is some other kind of expression, then the formal parameter is bound to a new location containing the value of the operand, just as in call-by-value.

(“Essentials of Programming Languages” second edition, p.109)

お分かりいただけたでしょうか。
call by referenceでは、上記プログラムのようなa+1みたいな式も渡せないといけないのです。
つまり、C++の参照をつかってもcall by referenceにはならないということですね。
ちなみに、その昔FORTRANではcall by referenceしかなかったので、a+0のような式を書くことで、
call by valueをシミュレートするという技があったらしいです。
今時のFORTRANがどうなっているかは知りません。

* おわりに *
Javaも「参照」という言葉を使っているためか、
時折「Javaの参照呼びが云々」と書かれることがありますが、
これには「それは参照の値呼びだ！」という、
分かりやすく分かりにくいツッコミが入るところを何度か見たことがあります。
しかし、冒頭にも書いたとおり、C++の参照に関してはツッコミが入ったところを見たことがありません。
単に私が見ているところが悪いだけなのか、それともC++特有の文化があるのか(たとえばC++の仕様書に”call by reference”と書いてあるとか)。

謎です。