リリカル☆Lisp開発日記

何を言ってるのか　わからねーと思うが、
取り敢えず下の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>

これは驚きです。

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

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の効果の程を測った人とかいないんでしょうかね。

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

遊ぶ

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

突然ですが、(/ 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”と書いてあるとか)。

謎です。

久しぶりに新・ニコ動でLispを見てみたら、

数値比較したいです先生

というコメントがあったので、数値比較のための関数
=, <, >, <=, >=
を追加しました。

それから、階乗のプログラムを書く人が後を絶たないので、乗算も追加しました。
皆がどんなプログラムを試したかが残るというのはなかなか便利なものです。

comp.lang.lispのとある記事を見てて気づいたんですが、
(loop :until ... :do ...)
なんて書き方ができたんですね。
私は今まで
(loop :do ... :until)
のようなコードしか見たことがありませんでした。
当然、:untilだけでなく:whileでも同じようなことが出来るみたいです。

で、これらは同じ意味かと思ったら違うみたいです。

(loop :do (print 'oh!) :until t)
; OH!
; => NIL

(loop :until t :do (print 'oh!))
; => NIL

(macroexpand '(loop :do (print 'oh!) :until t))
; =>
; (MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
;  (BLOCK NIL
;   (LET NIL
;    (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
;     (TAGBODY SYSTEM::BEGIN-LOOP
;      (PROGN (PROGN (PRINT 'OH!)) (WHEN T (LOOP-FINISH)))
;      (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
;      (MACROLET
;       ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN)
;         '(GO SYSTEM::END-LOOP))))))))) ;
; T

(macroexpand '(loop :until t :do (print 'oh!)))
; =>
; (MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
;  (BLOCK NIL
;   (LET NIL
;    (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
;     (TAGBODY SYSTEM::BEGIN-LOOP
;      (PROGN (WHEN T (LOOP-FINISH)) (PROGN (PRINT 'OH!)))
;      (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
;      (MACROLET
;       ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN)
;         '(GO SYSTEM::END-LOOP))))))))) ;
; T

:doを先に書いた場合は、その内容が必ず1度は評価されるのに対し、
:whileや:untilを先に書いた場合はテストが先に行われるため、
:doの内容が評価されない場合もあるみたいです。

CLHSを眺めたところ、loopは基本的に書かれたとおりの順番に動くみたいです。
次のように気持ち悪いことも出来ます。

(loop :for i :from 0 :do (print i) :while (< i 3)  :collect i)
; 0
; 1
; 2
; 3
; => (0 1 2)

:whileを:collectより先に書いてあるので、リストに3は含まれません。
もちろん、:whileと:collectの順番を逆にすると、リストに3が含まれます。
loop恐るべし。

プログラミング Coqを参考に、CoqとCoqIDEを入れて試してみたが、
どうもCoqIDEの動きがおかしい。時々固まったり変な動作をする。
周りの人に相談したところ
「CoqIDEは使いものにならないからProof Generalを使え」
と言われたのでProof Generalとやらを入れてみた。
Emacs上で動く便利なものらしい。

以下はただのメモ書き。

* ダウンロード *
公式サイトからダウンロードする。
現時点のバージョンは4.0のようだ。

* インストール *
公式サイトの説明に従い、ファイルを展開して、
.emacsにload-fileを追加。

試しにEmacsで拡張子がvのファイルをひらいてみるが、
「Emacsのバージョンが23.1じゃないからダメ」
と怒られる。これまた公式サイトの説明に従いmake。

make clean
make compile EMACS=`which emacs`

しかし、make時にエラーが起こる。
「`font-lock-beginning-of-syntax-function’はobsoleteだから’syntax-begin-function’を使え」
と言ってるようなので、何も考えずにソースコード中の
font-lock-beginning-of-syntax-functionをsyntax-begin-functionに置換。
makeはこれで通った。

* 起動 *
Emacsで拡張子がvのファイルを開くと自動的にProof Generalが立ち上がる。
公式サイトのマニュアルを適当に眺めたところ、

• C-c C-nで証明をひとつ進める
• C-c C-uで証明をひとつ戻す

らしい。今の私の知識ではどうせこれしか使わない。後のものは後で覚えよう。

C-c C-RETでカーソルの位置まで証明を進めるみたいだが、
これをやろうとすると「C-c RET is undefined」と言われてしまう。
controlを押しながらreturnを押してるはずなんだけど、なんでだろう。
まあ、誰か詳しい人が解決法を教えてくれるだろう。

* 疑問点 *
CoqIDEでは「Eval simpl in xxx」みたいなものを、
専用の場所に書いていたけど、Proof Generalではどこに書けばいいんだろう。
ソース中に書いたら動いたけど、ソースとは分離したい。

前回に続いて、こんどはファイルのアップロード機能を付けました。

添付ファイルについて

セキュリティとか何も考えてないので結構怖いけど、
まあ、誰も使わないので今のところ大丈夫(?)でしょう。

前回とのdiffを貼っつけておきます。
(さらに…)