#:g1: frontpage

 

Lispとエディタ (3)

Posted 2015-07-02 22:42:11 GMT

 前回1960年代のLispのエディタ環境を眺めてみましたが、今回から1970年代を眺めてみようと思います。 まず、前回に引き続き、BBN-LISPの環境ですが、1971/2年のBBN-LISPのマニュアルを眺めると、構造エディタはかなり増強されています。
詳しくは579頁まで記述が増えたマニュアルに書いてありますが、

主な所としては、

  • 検索
  • パタンマッチによる置換
  • 複数マークを設定し移動が可能
  • アンドゥ機能
  • 文字列の編集
  • コマンドマクロ

でしょうか。
他、数え切れない程、コマンドが追加されています。

1966年には検索はありませんでしたが、様々な方法で検索でき、検索してからの置換も可能になっています。
アンドゥ機能も以前は、保存したものを戻すだけでしたが、かなりユーザーインターフェースが強化されています。
文字列の編集はS式単位だとアトム一つになるため編集単位が大き過ぎる問題がありますが、リストに変換して再度文字列に戻すようなコマンドが追加されました。
編集機能が充実したため、コマンドをまとめて実行するというtecoedsedの系譜のような、編集素材とコマンド(これもS式)を別々に与えるというような使われ方も発達しています(応用例を後述)。

The Programmer's assistant

 エディタもかなりの増強がされていますが、他に目立つ機能として、The Programmer's assistantと呼ばれる一連の機能があります。

に詳細が述べられていますが、主にREPL(toplevel)の履歴機能とコマンド編集、DWIM機能を中心とした支援システムです。

LISPX

この履歴編集機能はLISPXと呼ばれるようですが、機能としては、

  • 再実行(REDO)
  • アンドゥ(UNDO)
  • 修正(FIX)
  • コマンド内容の置換(USE …)

等々、Unixでいうとコマンドの履歴編集機能に相当します。
ちなみに、cshはINTERLISPの機能を真似したようなので、現在お馴染のUnixシェルの履歴機能の大元は、INTERLISP(BBN-LISP)ということになるようです。

Unixシェルと違うところといえば、LISP処理系がシェルになってしまっているということでしょうか。
また、cshはアンドゥ機能を取り込むことはなく後続のシェルでも該当する機能はありませんが、BBN-LISPでは、関数定義を取り消したり、

INTERLISP-10  31-Dec-84 ...
Hi.
3_defineq((foo(n)n)) ;fooを定義
=DEFINEQ
(foo)
4_undo ;定義を取消し
defineq undone.
5_(foo 8)

UNDEFINED CAR OF FORM ;定義されていないというエラー foo

6_redo 3 ;やり直し =DEFINEQ (foo) 7_(foo 8) 8 8_

変数に格納したリストを変更して、それを取り消したりすることが可能です。

INTERLISP-10  31-Dec-84 ...
Hi.
3_rpaqq(foo (0 1 2 3 4)) ; fooに '(0 1 2 3 4)というリストを代入
=RPAQQ
(0 1 2 3 4)
6_foo
(0 1 2 3 4)
7_(cdr foo)
=CDR
(1 2 3 4)
8_(rplaca foo 'a) ;carを'aに変更
=RPLACA
(a 1 2 3 4)
9_foo
(a 1 2 3 4)
10_undo 8 ;アンドゥ実行
rplaca undone.
11_foo
(0 1 2 3 4) ;元に戻った

また、FIXは、指定したコマンドを構造エディタで編集しますが、Unixシェルと違って非常に有用なものになっています。
Unixシェルだとエディタを呼び出してどうするんだろうなという感が強いですが、LISPXの場合は、プログラミング開発の最中なので有用度がかなり違っているという印象です。
さらにユーザーがLISPXのコマンドを定義して拡張することが可能です。

以上のように、プログラミング言語と環境がかなり混ざっている感もありますが、環境としてはかなり強力です。
現在人気のSLIME(Common Lisp開発環境)と比べてもBBN-LISPの方がインタラクティブな面は多々あります。

DWIM

DWIMは有名な機能ですが、スペル修正を含め、構文の間違いを訂正する機能です。
括弧の対応ミス等、打ち間違いを検出するとユーザーへの問い合わせが発生し、ユーザーの指示により訂正が実行されます。

BREAK PACKAGE

編集機能とはちょっと違ってデバッグ方面の発展です。 BREAK PACKAGEは、所謂breakなのですが、BBN-LISPが大元のようです。
デバッグ等で活躍しますが、breakしてからのエディタでの編集が構造エディタということもあり、かなり一体感があります。

PRINTSTRUCTURE

PRINTSTRUCTUREはプリティプリント系の方向の発展の気がしますが、呼出グラフを可視化する機能で、現在のCommon Lisp等でいうとwho-callsで知られる機能です。
関数を実行すると、プログラム全体の呼び出しグラフが表示され、全体の見取り図を提供します。

MAKEFILE

BBN-LISPはかなりファイル指向よりイメージ指向に近いものになってきていますが、メモリ上の定義をファイルに書き出す機能も充実しています。
整頓された書き出しにはMAKEFILEという関数を利用して、選択した関数をファイルにプリティプリントして出力します。

Super Parenthesis

細かい所ですが、超括弧も導入されています。
連続するコッカをまとめて']'で閉じることが可能。
[がある場合は、]は対応する[で閉じます。 プリティプリンタも超括弧を使って表示されるので、この方式がメジャーになっていれば「LISPは連続する)))がー」という話もなかったのかもしれません(まあ、どうも読み辛い気がしますが。)

TRANSOR

構造エディタは、S式sedとしても使えるように進化しましたが、この応用として異なるLISP方言のソースコードを変換するTRANSORという機能が実装されています。
個別の関数の変換の指定は、エディタのコマンド(S式)で記述します。
ちなみに、S式レベルで変換できないエスケープ文字などの違いは、prescanという関数で処理します。

まとめ

 以上、主にプログラムの編集機能を軸に1972年のBBN-LISPの環境を眺めてみました。 マニュアルを眺めてみると、スクリーン指向以前の行指向なターミナル環境としては、究極の最終形態に近いものではないかなと感じます。
現在、美麗な開発環境は多数あると思いますが、これ程の統一感もなかなか無いのではないでしょうか。
これらのアイデアと環境が半世紀近く前に存在したというのも凄い。

なかなかEmacsに辿きませんが、次回こそEmacsとLispの連携について書く予定です。


HTML generated by 3bmd in SBCL 1.2.13

Lispとエディタ (2)

Posted 2015-06-27 15:58:17 GMT

 前回1960年代の環境について書いたので今回は1970年代のEmacsを書こうと思いましたが、1966年発表のBBN-LISPの環境がどうもエポックメイキングな感じなので、これも調べてみました。

BBN-LISPは、1966年に登場した処理系で後にInterlispへと繋る処理系です。

色々と先進的な所がありますが、エディタ+開発環境という点に関しては、

  • 処理系に内蔵する方式
  • S式エディタ
  • LISPで実装されている
  • pretty printが実装されている
  • UNDO機能

という点が特長です。

editf、editv、edite (1966)

前回紹介したBinfordエディタは1969年にMacLISPとの統合ということなので、恐らくそれより以前からあるのだろうと思いますが、BBN-LISPのeditfは1966年ということなので、私が確認できた限りでは一番古いLISP内蔵型のS式エディタです。
editfは関数、editvは変数、editeはリストデータの編集のようです。

エディタの機能については上記のマニュアルに詳しいのですが、主なコマンドは下記の通り。

移動

  • 数字 ► 0 で上の階層へ、1は一番目の要素へ。2以下同様

編集

  • (n exp) ► listのn番目(1オリジン)を置き換える。-nの場合は、n番目の要素の前に挿入。(n)のみだとn番目の要素を削除
  • (N e1 e2...) ► リストの最後に要素を挿入。要素は複数可
  • (LI n) ► カッコを挿入という意味。動作としては、n番目から最後までを括弧で囲む。
  • (LO n) ► カッコを削除という意味。動作としては、n番目のリストをn-1番目と繋げる (a (b c) d)は、(a b c)となり後は消える
  • (RI n m) ► コッカを挿入という意味。動作としては、n番目のリストのコッカをm番目まで移動する。(a b (c d e) f)(RI 3 1)すると(a b (c) f)となる
  • (RO n) ► コッカを削除という意味。動作としては、n番目のリストのコッカを最後まで移動する。(a b (c d e) f)(RO 3)すると(a b (c d e f))となる
  • (E exp) ► 式を評価した値を返す。(1 (E (list 1 2 3)))は1番目の要素を(1 2 3)で置き換える等、他のコマンドと組み合わせて利用できる。

表示

  • p(p n m)pは、(p 0 2)の略、n番目の要素をm階層まで表示。指定より深い階層は&で表示される

位です。

数値を指定して移動というのがBinfordエディタと違い、また検索がないですが、操作感としてはBinfordエディタより使い易い印象です。

UNDO

エディタでの編集は、内部的には、rplaca/rplacdでリストを破壊的に変更して行くので、保存する機能がないと何か間違いがあっても元に戻せません。
このため、COPYとRESTOREコマンドによってデータの保存を行ないます。
後々は、UNDOまで進化するようですが、UNDOというより手動セーブです。まあ、無いよりはましという所です。

セッション例

BBN-LISPの環境は確認できないのですが、後継のInterlisp-10にeditfが引き継がれているようなので、takを定義しているセッションを例として紹介してみます。
lessp {in tak} -> LESSP ? yesのようなものはInterlispのDWIMが機能して修正されている箇所です。
Interlispは大文字と小文字を区別しますが、Common Lispの標準のようにreadが大文字に畳み込むことはないので、DWIMがlesspという関数がないけれど、LESSPなら存在するので修正するか?という問い合わせが発生しています。
=というのも修正した、という意味です。

以下、;以降はコメントです。

INTERLISP-10  31-Dec-84 ...
Hello.    ;挨拶。ハロウィンやクリスマス等で挨拶が変わったりする 
3_(defineq(tak(x y z)(tak))) ; 大まかに定義してみる
=DEFINEQ
(tak)
4_editf(tak) ; editf起動。evalquote形式も受け付ける。
=EDITF
edit
1*p ;表示
(LAMBDA (x y z)   **COMMENT**   (tak))
1*4 p ;4番目を表示
(tak)
2*(n (tak (sub1 x) y z)) ; nで(tak (sub1 x) y z)を最後に追加
=N
3*p
(tak (tak & y z))
3*(n (tak (sub1 y) z x))
=N
4*(n (tak (sub1 z)x y))
=N
5*0
6*p
(LAMBDA (x y z)   **COMMENT**   (tak & & &))
6*(p 0 10)
=P
(LAMBDA (x y z)   **COMMENT**   (tak (tak (sub1 x) y z) (tak (sub1 y) z x) (tak 
(sub1 z) x y)))
7*(li 4) ;if〜を記述していなかったので、まず括弧を追加
=LI
8*
p
(LAMBDA (x y z)   **COMMENT**   (&))
8*4 p
((tak & & &))
9*(-1 if) ;先頭にifを挿入
10*p
(if (tak & & &))
10*(n then z else##
(-2 (lessp y x) then)
11*p
(if (lessp y x) then (tak & & &))
11*(-4 z)
12*p
(if (lessp y x) then z (tak & & &))
12*(-5 else)
13*p
(if (lessp y x) then z else (tak & & &))
13*0
14*0 p

can't - at top. 14*p (LAMBDA (x y z) **COMMENT** (if & then z else &)) 14*(p 0 100) =P (LAMBDA (x y z) **COMMENT** (if (lessp y x) then z else (tak (tak (sub1 x) y z) (tak (sub1 y) z x) (tak (sub1 z) x y)))) 15* ; エディタを^Dで抜けてtakを実行してみる

5_(tak 18 12 6) lessp {in tak} -> LESSP ? yes ;DWIMがスペル修正 sub1 {in tak} -> SUB1 ? yes sub1 {in tak} -> SUB1 ? ...yes sub1 {in tak} -> SUB1 ? yes 6 ; おや、結果が7でない。LESSPではなくて、(NOT (GREATERP))の間違いだった。 6_redo 4 ; コマンド番号4を再実行 edit 15*(## 4 16*p (if (LESSP y x) then z else (tak & & &)) 16*2 16*p (LESSP y x) 16*(1 greaterp) 17*p (greaterp y x) 18*(LI 1) 18*p ((greaterp y x)) 18*(-1 NOT) ; エディタを^Dで抜けてtakを実行してみる

14_redo 5 greaterp {in tak} -> GREATERP ? yes 7 15_(prettyprint '(tak)) ;prettyprintで定義を表示してみる =PRETTYPRINT

(tak [LAMBDA (x y z) **COMMENT** (if (NOT (GREATERP x y)) then z else (tak (tak (SUB1 x) y z) (tak (SUB1 y) z x) (tak (SUB1 z) x y]) (tak) 15_(prettydef '(tak)) ;prettydefの場合(DEFINEQが付く) =PRETTYDEF (DEFINEQ

(tak [LAMBDA (x y z) **COMMENT** (if (NOT (GREATERP x y)) then z else (tak (tak (SUB1 x) y z) (tak (SUB1 y) z x) (tak (SUB1 z) x y]) ) T

エディタはLispで実装されている

BBN-LISPの文献にはeditのソースが記載されていますが、Lispで実装されています。
Lispで実装されているということは、Lispで拡張することも可能ということで、もしかしたら最初期のユーザーがカスタマイズ可能エディタかもしれません。

ちなみにBinfordエディタですが、こちらはアセンブリ(MIDAS)で記述されていてLispではエディタを拡張できないようです。

Pretty Print

上のセッションでも紹介していますが、prettyprintや、prettydefという整形ツールが標準で装備されています。
これも最初期のものではないでしょうか。
BBN-LISPの文献のLispソースも綺麗に整形された状態で載っていますが、半世紀前の時点で手作業でインデントを調整するようなことはしていなかったようです。

まとめ

以上、BBN-LISPの1966年当時としてはとても先進的な機能を紹介してみました。

  • Lisp内蔵の式指向なエディタ
  • ソースの整形は自動

という点では、当然ながらメモ帳+REPLより全然強力です。
半世紀前の時点で既に、括弧の対応管理とインデントの調整は人間の仕事ではなくなっていたことが分かるかと思います。

BBN-LISPには、他に特筆すべき事項として、trace関数等もありますが、今回は、エディタの考察なのでまた別の機会にでも考察してみたいと思います。

次回こそは、1970年あたりのEmacsを考察してみたいと思います。


HTML generated by 3bmd in SBCL 1.2.12

Lispとエディタ (1)

Posted 2015-06-26 14:05:53 GMT

 LispとエディタといえばEmacsですが、Emacsは熟練しないと使い熟せないとか、EmacsばかりがLispエディタじゃない!等の話はよく耳にします。
といっても、そんな話にそれ以上の考察もなく同じ所をぐるぐる廻っているだけ、という感じがしていました。
そこで一つLispとエディタの関係について調べて考察してみようかなと思った次第です。

最初期のLispとエディタ (1960年頃)

まず、最初のLispといえば、LISP 1.5ですが、どうもバッチ方式のようです。
print以外にpunchなんて関数もあったりしますのでパンチカードでの入出力は標準だった様子。
LISP 1.5をIBM 7094のエミュレータで動かしてみた感じでもそんな感じですが、IBM 7094ので主に使われたエディタってなんなんでしょうね。

初の対話式 Lisp (1964年頃)

初の対話式Lispとなると、どうも当時17歳のL Peter Deutsch氏が開発したPDP-1 Lispのようです。
BASICも1964年あたりですが、対話式プログラミング環境としては最初の一つなのかもしれません。
PDP-1で利用されたエディタですが、Daniel L. Murphy氏が開発したTECOだと思われます。
TECOは、Emacsの先祖として有名ですが、Unix方面でいうと、edの先祖のqedの元になったものがtecoなので、Emacsもviも元はtecoともいえます。
このtecoで1964年あたりにLispの編集支援機能が作られていたかどうかはちょっと分かりませんでした。

Binford editor (1969年頃)

今から46年前の1969年9月24日のMacLISPの開発ニュースによれば、

THE S-EXPRESSION EDITING SYSTEM OF TOM BINFORD IS
NOW A REGULAR PART OF THE SYSTEM. A MEMO SHOULD BE
COMING OUT SOON ON ITS USE; IT IS VERY MUCH LIKE
USING TECO WHILE IN LISP.

ということなので、S式エディタとしてTom Binford氏作のBinfordエディタがMacLISPに統合されたようです。
TECOみたいなものとあるので、この辺りではTECOが主流だったことが分かります。
この時代には、TECO ⇔ Lisp処理系で連携する機能もあるようですが、資料があまり残っていないようなので詳細は不明です。

とりあえずBinford エディタは、現在でもMacLISPで動かすことができるので機能を確認してみましょう。

Binfordエディタのコマンド

Binfordエディタのコマンド MacLISPのマニュアルによれば、はこんな感じです。

$Escを表わし、$$というのは、連続2回入力を表わします。
TECOもそうですが、終端としては、$$が標準だった様子。
コマンドの確定には、Space+改行ですが、複数のアイテムを取れる場合には$$で終端します。 数引数は前置され、-は意味が反転されます。
また、カーソル位置は、$$で表現されます。

  • Q ► エディタを終了してREPLへ(といってもLisp/REPLの中で実行されている)
  • Y sym $$ ► シンボルの関数定義を挿入(Yank)
  • YV sym $$ ► シンボルの値セルの値を挿入
  • YP sym VALUE $$ ► シンボルの値セルの値を挿入/旧形式
  • YP sym prop $$ ► シンボルの属性を挿入
  • YP sym $$ ► シンボルの属性リストを挿入
  • J ► 式の先頭に飛ぶ
  • S e1 e2 … $$ ► e1、e2を式の中から探す。e1、e2 …で利用可能な名前はアトム単位
  • S $$ ► 探索の繰り返し
  • I e1 e2 … $$ ► e1, e2, … をカーソル位置に挿入
  • K ► カーソルの右の式を削除
  • KI exp ► カーソルの右の式をexpで置き換え
  • -KI exp ► カーソルの左の式をexpで置き換え
  • IV exp ► 式の評価値を挿入
  • EV exp ► 式を評価

移動系

移動系は数引数が前置可能で、回数分の繰り返しになります。(例.4F等々)

  • F ► 右に1トークン進む(括弧かアトム分)
  • -B ► Fに同じ
  • B ► 左に1トークン進む(括弧かアトム分)
  • -F ► Bに同じ
  • R ► 右に1式進む(括弧かアトム分)
  • L ► 左に1式進む(括弧かアトム分)
  • D ► 式を一階層降りる(非アトムの式)。方向は右側へ
  • U ► 式を一階層登る。方向は左側へ/式の先頭

仮想括弧

仮想括弧は独自の概念ですが、binford editorでは、まず仮想的な括弧を挿入し、()コマンドで確定させるという方式です。
仮想括弧は、|%I(%||%I)%|で表わされます。

  • ( ► 仮想カッコを挿入
  • ) ► 仮想コッカを挿入
  • D( ► 仮想カッコを削除
  • D) ► 仮想コッカを削除
  • () ► 仮想括弧を実体化

マーク

  • SS sym ► カーソルポジションにsymという名前のマークを設定
  • RS sym ► マークからカーソルポジションを復帰

表示系

  • SP ► 自動表示機能をトグル
  • P ► 式全体を表示
  • PW ► 表示幅を設定。前置引数で幅を設定(130pw )等

セッション例

コマンドは大体分かったので、実際にfibでも定義してみましょう。
色々試行錯誤してみましたが、editでエディタを立ち上げてから何かするというよりは、REPLにざっと適当に入力したものをeditで修正するのが一番楽なようです。
以下では、そんな感じでfibを定義してみます。

ざっと定義(1-の所でミスありだがeditで修正する予定)

(defun fib (n) (if (< n 2)n(+ (fib (1- ))(fib (- n 2)))))
FIB 

fibを編集

(edit fib)

s 1- $$1-を探す

s 1- $$

< N 2) N (+ (FIB (1- $$ )) (FIB (- N 2)))

i n $$nを挿入

i n $$

< N 2) N (+ (FIB (1- N $$ )) (FIB (- N 2)))

連続入力も可能

j f f f f

$$ EXPR (LAMBDA (N) (IF (< N 2) N (+ (FIB (1- N)) (FIB (- N 2))))))

EXPR $$ (LAMBDA (N) (IF (< N 2) N (+ (FIB (1- N)) (FIB (- N 2))))))

EXPR ( $$ LAMBDA (N) (IF (< N 2) N (+ (FIB (1- N)) (FIB (- N 2))))))

EXPR (LAMBDA $$ (N) (IF (< N 2) N (+ (FIB (1- N)) (FIB (- N 2))))))

ifcondに変更してみる例

ifを探す

s if $$

EXPR (LAMBDA (N) (IF $$ (< N 2) N (+ (FIB (1- N)) (FIB (- N 2))))))

condに置き換え

-ki cond

EXPR (LAMBDA (N) (COND $$ (< N 2) N (+ (FIB (1- N)) (FIB (- N 2))))))

仮想カッコを挿入

( 

EXPR (LAMBDA (N) (COND |%I(%| $$ (< N 2) N (+ (FIB (1- N)) (FIB (- N 2))))))

2式右へ移動

2r 

EXPR (LAMBDA (N) (COND |%I(%| (< N 2) N $$ (+ (FIB (1- N)) (FIB (- N 2))))))

仮想コッカを挿入

) 

EXPR (LAMBDA (N) (COND |%I(%| (< N 2) N |%I)%| $$ (+ (FIB (1- N)) (FIB (- N 2))))))

仮想カッコを挿入

( 

EXPR (LAMBDA (N) (COND |%I(%| (< N 2) N |%I)%| |%I(%| $$ (+ (FIB (1- N)) (FIB (- N 2))))))

tを挿入

i t $$

EXPR (LAMBDA (N) (COND |%I(%| (< N 2) N |%I)%| |%I(%| T $$ (+ (FIB (1- N)) (FIB ( - N 2))))))

1式右へ移動

r 

EXPR (LAMBDA (N) (COND |%I(%| (< N 2) N |%I)%| |%I(%| T (+ (FIB (1- N)) (FIB (- N 2))) $$ )))

仮想コッカを挿入

) 

EXPR (LAMBDA (N) (COND |%I(%| (< N 2) N |%I)%| |%I(%| T (+ (FIB (1- N)) (FIB (- N 2))) |%I)%| $$ )))

仮想括弧を実体化

() 

EXPR (LAMBDA (N) (COND ((< N 2) N) (T (+ (FIB (1- N)) (FIB (- N 2)))))) $$ )

終了

q 

REPLに抜けて関数を実行

* 
(fib 10.)
55 

関数の本体を後でまとめて定義してみる

仮想括弧を入力して確定するのが結構面倒なのですが、何か楽な方法はないかと考えてみました。
ivを使えば、Lispの式が挿入できるので、これを使ってみた例です。

(defun fib (n)n)
FIB 

(edit fib) (SLURPED EDIT FASL)

$$ EXPR (LAMBDA (N) N)) 80pw

$$ EXPR (LAMBDA (N) N)) 2r

EXPR (LAMBDA (N) N) $$ ) 2b

EXPR (LAMBDA (N) $$ N)) k

EXPR (LAMBDA (N) $$ )) iv '(if (< n 2)n(+))

EXPR (LAMBDA (N) (IF (< N 2) N (+)) $$ )) b

EXPR (LAMBDA (N) (IF (< N 2) N (+) $$ ))) b

EXPR (LAMBDA (N) (IF (< N 2) N (+ $$ )))) iv '(fib (1- n))

EXPR (LAMBDA (N) (IF (< N 2) N (+ (FIB (1- N)) $$ ))))

iv '(fib (- n 2))

EXPR (LAMBDA (N) (IF (< N 2) N (+ (FIB (1- N)) (FIB (- N 2)) $$ ))))

式指向と行指向

 以上、Binfordエディタを試してみたり解説してみたりしましたが、既に現在のEmacsでのLispの編集と大枠では同じことが可能であるのが分かるでしょうか。
特長としては下記のような事項が挙げられます

  • 式単位で編集/移動/検索が実行できる
  • ツリー構造を扱える(葉/根の方向に移動)
  • Lisp環境の値を取り込める
  • 括弧の対応を勘定したりしていない

Lispでは何故、式指向のエディタが望まれたのかですが、Lisp自体が式指向であるからではないかと思います。
式が値を返すということは、思考単位にしろデバッグの単位にしろ式が意味単位となり、これを相手にしなければなりません。
Lispの意味は行単位ではありません。行で区切られても意味単位ではないので不便です。
行エディタで快適に編集できるプログラム言語というものは、文が主であったりして、値は何かに代入され、その代入されるという表現も大概行に収まります。

ということで、Lispの編集には式指向であることが求められのですが、式指向エディタについては、Interlisp方面でさらに進化がみられるようなので、そちらも調べてみたいところです。

ファイルへの出力は?

ファイルへの書き出しについてはいまいち不明なのですが、Lispファイルの整形には、grindというプリティプリントのプログラムが良く使われていました。
これで一括で出力することも可能だったのではないかと思われます。

まとめ

 最初期のエディタから、式指向のエディタが出始めた約60年前〜50年前あたりを考察してみました。

上記「式指向と行指向」でも述べましたが、Lispでは式の表現を扱う手段が必要とされ、半世紀前には既にそれが実践されていたことも分かります。
しかし行指向の言語がメジャーであるために、半世紀経過した現在でさえ、(行指向エディタでは)Lispは書きにくいのが問題である、というような話も良く耳にします。
根本的には、式というものが理解されていないのが原因ではないでしょうか。
考えてみれば、C/JavaのようにLispをぶらさがり括弧で記述するのも、どうにか行指向に合せようとした結果のような気もしますが、括弧の対応など式の整合性を取る作業は人力でやらないというのが半世紀前に出ていた結論な気がします。

文より式をメインとするプログラミング言語がどんどん増えてきましたが、式指向の考え方がメジャーになっていくことを期待したいところです。

次は、Emacsが出始める40年位前を考察してみたいと思います。


HTML generated by 3bmd in SBCL 1.2.12

Common Lispで多方向分岐の最適化がされない場合にどうするか

Posted 2015-06-23 14:27:15 GMT

前回Common Lispと多方向分岐について書きましたが、最適化は処理系任せでした。

クロージャーの配列を使う

これをユーザーレベルでどうにかしよう、という例も昔からあって、前回紹介したSymbolicsの最適化についての議論でもJeffrey Mark Siskind氏が、配列にクロージャーを詰めれば良いじゃないか、というような発言があります。

このアイデアは割合に定番なものですが、残念ながらcaseの場合と比較してみると100倍位遅いことが多いです。

(defun 256way/vector (i)
  (let ((rand (random 10)))
    (macrolet ((fcase (i &body body)
                 `(funcall
                   (svref (vector ,@(loop :for b :in body
                                          :collect `(lambda () ,b)))
                          ,i))))
      (fcase i
             . #.(loop :for x :from 0 :repeat 256
                       :collect `(progn (* i rand)))))))

(defun 256way/case (i) (let ((rand (random 10))) (case i . #.(loop :for x :from 0 :repeat 256 :collect `((,x) (progn (* i rand)))))))

(let (tem) (dotimes (i 1000000 tem) (setq tem (256way/vector 255)))) ;=> 2040 #|------------------------------------------------------------| Evaluation took: 2.568 seconds of real time 2.572000 seconds of total run time (2.568000 user, 0.004000 system) [ Run times consist of 0.052 seconds GC time, and 2.520 seconds non-GC time. ] 100.16% CPU 8,455,561,305 processor cycles 10,256,001,056 bytes consed

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz |------------------------------------------------------------|#

(let (tem) (dotimes (i 1000000 tem) (setq tem (256way/vector 0)))) ;=> 0 #|------------------------------------------------------------| Evaluation took: 2.608 seconds of real time 2.612000 seconds of total run time (2.596000 user, 0.016000 system) [ Run times consist of 0.068 seconds GC time, and 2.544 seconds non-GC time. ] 100.15% CPU 8,586,032,115 processor cycles 10,255,968,880 bytes consed

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz |------------------------------------------------------------|#

(let (tem) (dotimes (i 1000000 tem) (setq tem (256way/case 0)))) ;=> 0 #|------------------------------------------------------------| Evaluation took: 0.026 seconds of real time 0.028000 seconds of total run time (0.028000 user, 0.000000 system) 107.69% CPU 85,510,905 processor cycles 0 bytes consed

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz |------------------------------------------------------------|#

(let (tem) (dotimes (i 1000000 tem) (setq tem (256way/case 255)))) ;=> 2295 #|------------------------------------------------------------| Evaluation took: 0.169 seconds of real time 0.168000 seconds of total run time (0.168000 user, 0.000000 system) 99.41% CPU 555,737,934 processor cycles 0 bytes consed

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz |------------------------------------------------------------|#

何もしていないcaseで一番遅い場合より遅いので、速度という面では何もしない方が良いケースが多そうです。

諦めない

しかし、ここで一頑張りした例があり、load-time-valueでクロージャーの配列をロード時に固定しようというアイデアがあります。
アイデアとしては処理系が用意する分岐テーブルを自前で用意するのに近いです。

(defun 256way/ncase (i)
  (ncase i
         . #.(loop :for x :from 0 :repeat 256
                   :collect `((,x) (progn (* ,x (random 10)))))))

(let (tem) (dotimes (i 1000000 tem) (setq tem (256way/ncase 255)))) ;=> 1020 #|------------------------------------------------------------| Evaluation took: 0.031 seconds of real time 0.032000 seconds of total run time (0.032000 user, 0.000000 system) 103.23% CPU 103,156,092 processor cycles 0 bytes consed

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz |------------------------------------------------------------|#

これだと結構速度が出ていてcaseの時より速い位ですが、実はコードが違っていることに気付いたでしょうか。
ncaseload-time-valueを利用するためフォームの周りのローカル変数は取り込めず等価なコードは実現できないのです。惜しい。

まとめ

環境を捕捉できるncaseがあれば解決かなと思いますが、可能なのでしょうか。自分は無理かなあと思っています。
何にしろ、多分、捕捉したら遅くなるのでしょう。
変数を捕捉する必要がないのならば、load-time-valueを使うのは有力なテクニックかなと思います。


HTML generated by 3bmd in SBCL 1.2.12

Common Lispと多方向分岐の最適化

Posted 2015-06-23 11:13:17 GMT

Common Lispのcaseだとifの連鎖に展開されるので非効率なのが残念という話を耳にしました。
結論からすると、そんなことはないけれど、最適化されなければそういうこともある、という感じです。

Common Lispではcaseのような多方向分岐の最適化には2通りあります。

  1. caseのようなフォームを直接低レベルで効率の良い多方向分岐の記述に変換する
  2. ifの連鎖を検査して、ある条件を満した場合に、低レベルで効率の良い多方向分岐の記述に変換する

です。

caseを最適化

caseを直接変換する方式には、CLISPや、Symbolics Genera 7以降のLマシン(3600系)があるようです。
Generaの方は、手元のOpen Generaで確認してみましたが、どうも3600シリーズ限定の機能の様子。

(case x
  ((0) ...)
  ((1) ...)
  ((2) ...)
  ((3) ...)
  (otherwise :default))

==> (compiler:computed-go x ... )

のような変換がされるようです。
ソースがないので詳細は不明ですが、computed-goとあるので、何か計算型gotoのプリミティブがあるのかもしれません。
参考のSLUGのメールによるとGenera 7.1位とのことなので、1987年位にはあった機能ということになります。

CLISPのほうは、caseの場合ハッシュテーブルで分岐用のテーブル作成するようです。
caseifや、condまで展開した後ではこうならないようなので、caseにはオプティマイザが付いているのでしょう。

caseから低レベルなフォームへの変換について

Common Lispでは、任意のマクロはスペシャルフォームであっても良いことになっています。
しかし、マクロに位置付けられたフォームは、マクロの展開形を持っていなければならないので、処理系依存でスペシャルフォームとなっているフォームも展開されて見えます。
ということで、

  1. 展開するとifの連鎖になって見える
  2. 処理系は、ifの連鎖から多方向分岐の最適化はしない

場合でも最適化していないとは限りません。
この場合、disassembleでもしてみないと分からない、ということになります。
ちょっとややこしい。

ifの並びから多方向分岐を検出して最適化

ifの並びから多方向分岐を検出して最適化する方式を採用している処理系は、古くは、Lucid CL、Allegro CLがあるようです。
Lucid CLは、version 4(1990)辺りから、Allegro CLもversion 4辺り(1993辺り?)なので結構古くからある最適化です。
Clozure CLは、1.8(2012年)からこの最適化が入りました。

どの処理系もCLISPのように分岐用のテーブルを作成して分岐するので要素数に比例してどんどん遅くなるということはありません。
この最適化では、テーブルを作成することが多いですが、最適化の発動条件もテーブルが作れるかどうか、という感じになります。
処理系によって、最大の分岐数や、範囲と値の分布状況によって発動したりしなかったりします。
この条件は処理系のマニュアルに載っていたりいなかったりという感じですが、載ってないことの方が多い印象です。

最適化がない処理系

SBCL、CMUCL、ECL、LispWorks辺りはこの最適化が搭載されていません。現在最も身近なSBCLに搭載されていないため、Common Lispはこの類の最適化はしないものと思われても仕方ないかなあとも思います。

256分岐位のcaseでベンチを作成して実行してみると、最速と最遅では大体10倍位の速度の開きがあるようです。

Lispと computed go

MacLISPでは、所謂 computed go が使えました。

(defun foo (x)
  (prog ()
        (cond ((minusp x) (go a))
              (t (go b)))
     a  (print 'foo)
     b  (print 'bar)))

こういうものが

(defun bar (x)
  (prog ()
        (go (cond ((minusp x) 'a)
                  (t 'b)))
     a  (print 'foo)
     b  (print 'bar)))

こんな感じに書けるのですが、Common Lispでは採用されなかったようです。

まとめ

Fortran 90で computed go が廃止予定になり実際に廃止になったのは、Fortran 95だったようですが、代わりにcaseが入りました。 代わりに入ったということは、恐らくcaseには computed go 的な最適化はそれなりに期待されているのでしょう。

CLtL1のgoの解説によれば、 computed gocaseで効率を落さず代用できる、ということなので似たような状況だったかと思いますが、実際の所、最適化はされたりされなかったりです。

Wikipedia:Multiway branchで引用されているクヌース先生のStructured Programming with go to Statementsの話では、多方向分岐については、非効率な実装をされがちというのは昔から嘆かれることが多かったようですが、Common Lispの場合も忘れられている処理系が結構あるという所なのかなあ、という所です。


HTML generated by 3bmd in LispWorks Personal Edition 6.1.1

いい加減にCLtL2(COMMON LISP 第二版)を参照するのはやめたらどうか

Posted 2015-06-21 22:51:30 GMT

 CLtL2はGuy L. Steele, Jr.(GLS)氏による注釈も豊富で読み物としても面白く、邦訳もされているのでこれを仕様として参照する人が多いです。
仕様でないと分かっている人でも参考として眺めている人は多いと思いますが、CLtL2の問題点を整理してみましょう。

  • ANSI Common Lisp 規格策定中の1990年時点でのGLS氏個人による中間報告であり仕様ではない
  • 1994年に決定したANSI Common Lispの規格には存在しないものが載っている
  • 1994年に決定したANSI Common Lispの規格には存在するものが載っていない

位の所でしょうか。
まず、1990年に何故中間報告が出ることになったのか、という点に関しては、出版社やベンダーからのプレッシャーが大きかったようです。
1984年にCLtL1が出てから5年あまりが経過し、ANSI Common Lisp規格もいつ決まるのか分からないという時期だけに需要は大だったようです。
邦訳では更にタイトルが「COMMON LISP 第二版」となっているので完全に規格書といった体ですが、CLtL2の文頭にもGLS氏が書いている通り、飽く迄個人的なまとめです。

この辺りの経緯については、Kent M. Pitman(KMP)氏のCommon Lisp: The Untold Story に詳しいですが、CLtL2の問題点は元より、1994年にHyperSpecを準備しはじめたKMP氏が1995年のCLtL2のウェブ版公開により打ちひしがれた様子が回想として記述されています。
ちなみに、CLtL2はLaTeXで記述されていてHTMLへの変換が簡単だったためウェブ版が作られたようです。(CLtL1はTeXとのこと)

ANSI Common Lispと内容が違っている点ですが、新しく加わったものとしては、

  • array-displacement
  • constantly
  • ensure-directories-exist
  • lambda(マクロ)
  • read-sequence
  • write-sequence
  • allocate-instance
  • define-symbol-macro

あたりがあります。
この辺りの関数はいまいち知名度が低い気がしますが、現在参考にされる書籍も1994年より前に書かれたものが多く登場しないことが殆どなので、この辺りが影響しているのかもしれません。
特にconstantly 辺りは折角用意されているのにlambdaで書いちゃう人が多いですね。
allocate-instanceの項目がCLtL2に無いなんて意外ですが、確かに全体的な動作説明の中にしか登場してないみたいです。

名前が変更になったものには、

  • get-setf-methodget-setf-expansion
  • get-setf-method-multiple-valueget-setf-expansion
  • define-setf-methoddefine-setf-expander
  • special-form-pspecial-operator-p
  • simple-condition-format-stringsimple-condition-format-control
  • base-characterbase-char
  • extended-characterextended-char

があります。

廃止になったものと、CLtL2にしか載っていないものについては、

  • variable-information
  • function-information
  • declaration-information
  • augment-environment
  • parse-macro
  • enclose
  • define-declaration
  • generic-flet
  • generic-function
  • generic-labels
  • with-added-methods
  • *applyhook*
  • *evalhook*

があります。
この辺は、処理系拡張で使えることも多いです。

詳しくは、Converting CLtL2 to ANSI CL というまとめがあるので参照してみて下さい。
良く使うmapcarのような関数でも結構重要な違いがあります。

まとめ

Common LispがANSI INCITS 226-1994 (R2004)として規格化されてから21年です。
いい加減25年前の中間報告を仕様として参照するのは止めても良いのではないでしょうか。
と思ったので書いてみました。
ちなみに、CLtL1については、HTML化もされず古本を求めて参照する人もほぼ居らずという感じで、CLtL1とANSI Common Lispの違いを把握する人が非常に少ない理由になっている気がしないでもありません。
(「Common Lispでは○○なんです!」という主張が実はCLtL1では成立していなかったりすることも案外あったり)

Common Lisp: The Untold Story を読んでいるとKMP氏は色々と重要な仕事をボランティアのような形で行なっていることが多いことが分かります(会社が支援してくれることになったりもしていますが)。
KMP氏に感謝の念を抱きつつHyperSpecを参照しましょう。


HTML generated by 3bmd in International Allegro CL Enterprise Edition 8.2 [64-bit Linux (x86-64)] (Apr 26, 2015 8:54)

cl:stringを拡張することについて

Posted 2015-06-21 09:29:29 GMT

cl:stringに限らず、cl:length等にも云える話ではあるのですが、一般的な名前の関数だとこれを拡張してみたいことがあります。
例えば、

(string (net.uri:uri "http://example.com"))
;=> "http://example.com"

(string (stp:string-value node)) ;=> "foo"

第一の壁: 標準のものは拡張できない

みたいな所ですが、cl:string は関数なので総称関数のように拡張はできません。
ということで、諦めないなら、

(defpackage :g
  (:use)
  (:export :string))

(defgeneric g:string (x) (:method (x) (cl:string x)))

(defmethod g:string ((uri net.uri:uri)) ...)

(defmethod g:string ((stp stp:text)) ...)

こんな定義を拵えて、こんな風に使います。

(defpackage :latumofis
  (:use :cl :g)
  (:shadowing-import-from :g :string))

(in-package :latumofis)

(string (net.uri:uri "http://example.com")) ;=> "http://example.com"

第二の壁: cl:string 型指定子でもある

しかし、同じパッケージ内で型指定子としてstringを使うと、こんな風にエラーになる訳です。

(coerce #(#\f #\o #\o) 'string)
;!> unknown type specifier: string

まあ諦めて

(coerce #(#\f #\o #\o) 'CL:STRING)
;=>  "foo"

と書けば良いでしょうが、stringcl:stringの違いを説明できる人は割とCLに詳しい人ですね。
ということで、諦めないなら、型指定子としても定義することになるでしょう。

(deftype string (&rest args)
  `(cl:string ,@args))

(coerce #(#\f #\o #\o) 'string) ;=> "foo"

第三の壁: cl:string はクラス名でもある

型指定子としても定義すれば解決だと思いきや、こんな所に壁があります。

(defmethod foo ((x string))
  (list x"))
;!> There is no class named g:string.

このように、クラスとしては定義されていないので使うことができません。cl:stringクラスは、cl:built-in-classで、cl:built-in-classのサブクラスは拡張できないので、この辺りで段々詰んできている気がします。
しかし、諦めないなら、クラス名としてエイリアス的なものを定義します。

(setf (find-class 'string)
      (find-class 'cl:string))

(find-class 'string) ;=> #<built-in-class cl:string>

(defmethod foo ((x string)) (list x))

(foo "foo") ;=> ("foo")

第四の壁: 実装依存拡張の罠(もしくは処理系のバグ)

これで大丈夫だろうという所で、大抵の処理系での挙動に問題はありません。
しかし、SBCLでは、

;; cl:string is too hairy for sequence functions.
(concatenate '(string 6) "foo" "bar")
;=>  "foobar"

とエラーになります。
これは、具体的には、make-sequenceで型指定子の展開で再帰的に展開していないのが原因だと思うのですが、これがバグなのか仕様なのか判然としません。
これは型を調整している箇所で型指定子を再帰的に展開すればOKです。

  • src/code/seq.lisp

(adjusted-type
          (typecase expanded-type
            (atom (cond
                    ((eq expanded-type 'string) '(vector character))
                    ((eq expanded-type 'simple-string)
                     '(simple-array character (*)))
                    (t expanded-type)))
            (cons (cond
                    ((eq (car expanded-type) 'string)
                     `(vector character ,@(cdr expanded-type)))
                    ((eq (car expanded-type) 'simple-string)
                     `(simple-array character ,(if (cdr expanded-type)
                                                   (cdr expanded-type)
                                                   '(*))))
                    (t expanded-type)))))

(adjusted-type
          (typecase expanded-type
            (atom (cond
                    ((eq (typexpand-all expanded-type) 'string) '(vector character))
                    ((eq expanded-type 'simple-string)
                     '(simple-array character (*)))
                    (t expanded-type)))
            (cons (cond
                    ((eq (typexpand-all (car expanded-type)) 'string)
                     `(vector character ,@(cdr expanded-type)))
                    ((eq (car expanded-type) 'simple-string)
                     `(simple-array character ,(if (cdr expanded-type)
                                                   (cdr expanded-type)
                                                   '(*))))
                    (t expanded-type)))))

とする。

まとめ

以上、無駄にがんばっている感が強いですが、印字としての名前とシンボルについて考えるには良い題材かなとも思い書いてみました。
cl:stringを拡張することについて、と云いつつもcl:stringは拡張できないという内容でしたね。
SBCLの件についてはバグな気もするので報告でもしてみたいと思います。


HTML generated by 3bmd in International Allegro CL Enterprise Edition 8.2 [64-bit Linux (x86-64)] (Apr 26, 2015 8:54)

defglobalの使い所

Posted 2015-06-18 19:00:49 GMT

 配列やハッシュテーブルを関数として利用できる機構は1970年代位からあるようですが、最近だとClojureやArcなどが活用しています。
Common Lispでもそんな感じのライブラリはあったりはするのですが、簡単に定義もできるので適当に試して遊んでみていました。 例えば、レキシカル変数を共有すれば、こんな感じで定義できます。

(defmacro defdict/closure (name &rest keys&vals)
  `(let ((tab (plist-hash-table (list ,@keys&vals))))
     (defun ,name (&optional (key nil keyp))
       (if keyp
           (gethash key tab)
           tab))
     (defun (setf ,name) (val key)
       (setf (gethash key tab) val))
     ',name))

(defdict/closure d0 :a 0 :b 1 :c 2) ;=> dict

(d0 :a) ;=> 0 ; t

(d0 :d) ;=> nil ; nil

(setf (d0 :a) 42) ;=> 42 (d0 :a) ;=> 42 ; t

この辺りはLisp-1だと綺麗な気もしますが、まあそれは置いておきます。

折角なのでインライン展開して欲しい

この方式はまずまず良いのですが、トップレベルのdefunでないとインライン展開してくれないことが殆どです。
上記の場合は、letの中にdefunがあるので大抵はコンパイラはインライン展開を諦めます。
これを避けるには、大域で定義する他ありません。
ということで、こんな感じになりました。

(defmacro defdict/defvar (name&opts &rest keys&vals)
  (let* ((tab (gensym "dict-"))
         (name (if (consp name&opts) (car name&opts) name&opts))
         (tabopts (and (consp name&opts) (copy-list (cdr name&opts))))
         (default (getf tabopts :default)))
    (remf tabopts :default)
    `(progn
       (defvar ,tab (plist-hash-table (list ,@keys&vals) ,@tabopts))
       (declaim (inline ,name (setf ,name)))
       (defun ,name (&optional (key nil keyp))
         (if keyp
             (gethash key ,tab ,default)
             ,tab))
       (defun (setf ,name) (val key)
         (setf (gethash key ,tab) val))
       ',name)))

(defdict/defvar d1 :a 0 :b 1 :c 2)

(d1 :a) ;=> 0 ; t

インライン展開もされるし、まずまず良いのですが、disassembleしてみると、gethashと比べて、どうも長いのが気になります。

  • d1

; disassembly for d1 (assembled 130 bytes)
L0:     mov rcx, [r12+96]                ; thread.binding-stack-pointer
        mov [rbp-16], rcx
        cmp r8, 537919511
        jne L1
        mov rax, [rip-139]               ; '#:|dict-1521|
        mov edx, [rax-11]
        mov rdx, [r12+rdx]
        cmp edx, 97
        cmoveq rdx, [rax-7]
        cmp edx, 81
        jeq L2
        mov rsp, rbp
        clc
        pop rbp
        ret
L1:     mov rax, [rip-172]               ; '#:|dict-1521|
        mov edi, [rax-11]
        mov rdi, [r12+rdi]
        cmp edi, 97
        cmoveq rdi, [rax-7]
        cmp edi, 81
        jeq L3
        mov rdx, r9
        mov esi, 537919511
        mov rax, [rip-199]               ; #<FDEFINITION for sb-impl::gethash3>
        mov ecx, 6
        push qword ptr [rbp+8]
        jmp qword ptr [rax+9]
        mov r9d, 537919511               ; :optional entry point
        mov r8d, 537919511
        jmp L0
        break 16                         ; Invalid argument count trap
L2:     break 10                         ; error trap
        byte #X02
        byte #X1B                        ; UNBOUND-SYMBOL-ERROR
        byte #X1B                        ; RAX
L3:     break 10                         ; error trap
        byte #X02
        byte #X1B                        ; UNBOUND-SYMBOL-ERROR
        byte #X1B                        ; RAX

gethashはこんな程度です。

  • gethash

; disassembly for gethash (assembled 37 bytes)
L0:     mov rdx, r10                    ; no-arg-parsing entry point
        mov rdi, r9
        mov rsi, r8
        mov rax, [rip-246]              ; #<FDEFINITION for sb-impl::gethash3>
        mov ecx, 6
        push qword ptr [rbp+8]
        jmp qword ptr [rax+9]
        mov r8d, 537919511              ; :optional entry point
        jmp L0
        break 16                        ; Invalid argument count trap

defglobalを使ってみる

何が長くなる原因なのかなと考えましたが、ハッシュテーブルをスペシャル変数に格納しているのが原因かなと考えました。
大域変数に格納するとなると、スペシャル変数か定数かしか選択肢はないのですが、スペシャル変数の場合、ローカルに束縛される可能性があるので、それ用のコードが含まれることになります。

今回の場合、格納用の変数が束縛される必要はないので無駄だなあ、と思っていたのですが、もしや、こういう場合に、defglobalを使うのではないだろうかと思い、defglobalに置き換えてみました。

defglobalとは、スペシャル変数なんだけれども、再束縛はできず、値の変更は代入でしかできない変数を宣言するものです。
ANSI Common Lispには含まれていませんが、Lispマシンの時代からある機能で、定番拡張となっていて、大抵の処理系には含まれています。

(defmacro defdict (name&opts &rest keys&vals)
  (let* ((tab (gensym "dict-"))
         (name (if (consp name&opts) (car name&opts) name&opts))
         (tabopts (and (consp name&opts) (copy-list (cdr name&opts))))
         (default (getf tabopts :default)))
    (remf tabopts :default)
    `(progn
       (#+sbcl sb-ext:defglobal
        #+lispworks hcl:defglobal-variable
        ,tab (plist-hash-table (list ,@keys&vals) ,@tabopts))
       (declaim (inline ,name (setf ,name)))
       (defun ,name (&optional (key nil keyp))
         (if keyp
             (gethash key ,tab ,default)
             ,tab))
       (defun (setf ,name) (val key)
         (setf (gethash key ,tab) val))
       ',name)))

(defdict (d2 :test #'eql :default :default) :a 1 :b 2)

(d2 :a) ;=> 1 ; t

; disassembly for d2 (assembled 90 bytes)
L0:     mov rcx, [r12+96]                ; thread.binding-stack-pointer
        mov [rbp-16], rcx
        cmp r8, 537919511
        jne L1
        mov rax, [rip-151]               ; '#:|dict-0|
        mov rdx, [rax-7]
        mov rsp, rbp
        clc
        pop rbp
        ret
L1:     mov rax, [rip-168]               ; '#:|dict-0|
        mov rdi, [rax-7]
        mov rdx, r9
        mov rsi, [rip-174]               ; :default
        mov rax, [rip-173]               ; #<FDEFINITION for sb-impl::gethash3>
        mov ecx, 6
        push qword ptr [rbp+8]
        jmp qword ptr [rax+9]
        mov r9d, 537919511               ; :optional entry point
        mov r8d, 537919511
        jmp L0
        break 16                         ; Invalid argument count trap

予想どおり大分すっきりしました。

インライン展開もされるので、gethashを手書きした場合とほぼ同じです。

(defun foo ()
  (declare (optimize (speed 3) (safety 0) (compilation-speed 0)))
  (dotimes (i 100 (d3 :q))
    (incf (the fixnum (d3 :q)))))

; disassembly for foo (assembled 206 bytes) xor r8, r8 ; no-arg-parsing entry point jmp L1 nop L0: mov [rbp-8], r8 mov rax, [rip-139] ; '#:|dict-0| mov rdi, [rax-7] lea rbx, [rsp-16] sub rsp, 24 mov rdx, [rip-151] ; :q mov rsi, [rip-150] ; :default mov rax, [rip-149] ; #<FDEFINITION for sb-impl::gethash3> mov ecx, 6 mov [rbx], rbp mov rbp, rbx call qword ptr [rax+9] mov r8, [rbp-8] mov rsi, rdx add rsi, 2 mov [rbp-8], r8 mov rax, [rip-209] ; '#:|dict-0| mov rdi, [rax-7] lea rbx, [rsp-16] sub rsp, 24 mov rdx, [rip-221] ; :q mov rax, [rip-204] ; #<FDEFINITION for sb-kernel:%puthash> mov ecx, 6 mov [rbx], rbp mov rbp, rbx call qword ptr [rax+9] mov r8, [rbp-8] lea rcx, [r8+2] mov r8, rcx L1: cmp r8, 200 jl L0 mov rax, [rip-281] ; '#:|dict-0| mov rdi, [rax-7] mov rdx, [rip-284] ; :q mov rsi, [rip-283] ; :default mov rax, [rip-282] ; #<FDEFINITION for sb-impl::gethash3> mov ecx, 6 push qword ptr [rbp+8] jmp qword ptr [rax+9]

  • 手書きした場合

(defglobal *h* (make-hash-table))

(defun bar () (declare (optimize (speed 3) (safety 0) (compilation-speed 0))) (dotimes (i 100 (gethash :q *h* 0)) (incf (the fixnum (gethash :q *h* 0)))))

; disassembly for bar (assembled 191 bytes) xor r9, r9 ; no-arg-parsing entry point jmp L1 nop L0: mov [rbp-8], r9 mov rax, [rip-123] ; '*h* mov r8, [rax-7] mov [rbp-16], r8 mov rdi, r8 lea rbx, [rsp-16] sub rsp, 24 mov rdx, [rip-142] ; :q xor esi, esi mov rax, [rip-143] ; #<FDEFINITION for sb-impl::gethash3> mov ecx, 6 mov [rbx], rbp mov rbp, rbx call qword ptr [rax+9] mov r8, [rbp-16] mov rsi, rdx add rsi, 2 lea rbx, [rsp-16] sub rsp, 24 mov rdi, r8 mov rdx, [rip-195] ; :q mov rax, [rip-186] ; #<FDEFINITION for sb-kernel:%puthash> mov ecx, 6 mov [rbx], rbp mov rbp, rbx call qword ptr [rax+9] mov r9, [rbp-8] lea rcx, [r9+2] mov r9, rcx L1: cmp r9, 200 jl L0 mov rax, [rip-255] ; '*h* mov rdi, [rax-7] mov rdx, [rip-258] ; :q xor esi, esi mov rax, [rip-259] ; #<FDEFINITION for sb-impl::gethash3> mov ecx, 6 push qword ptr [rbp+8] jmp qword ptr [rax+9]

まとめ

以前からdefglobalの使い道ってあるのかなあと思ったりしていましたが、再束縛する必要はない大域変数というのもそれなりにある気がするので、実は使い所は多かったりするのかもしれません。


HTML generated by 3bmd in LispWorks Personal Edition 6.1.1

Common Lispのパッケージを考える #1

Posted 2015-06-12 14:14:07 GMT

 Common Lispの機能の中でも入門者には難しいと云われることが多い気がするパッケージですが、一体何が難しいのかをシリーズで考えてみたいと思います。

柔軟でありつつ柔軟でない

 まず、パッケージはファーストクラスで、パッケージに関連する操作も全て実行時に行なえます。
恐らくパッケージの動的機能については、文句はないというか、多分活用もできない程動的な気がします。
実行時にパッケージ名を変更したりもあまりしませんし、実行時に名前空間を作りたいこともあまりありません。

 非常に動的なパッケージではありますが、パッケージが存在しないことによるエラーや、シンボルの競合等の解決は初学者には難しい物になっているかなと思います。
動的なので、「パッケージが存在しない」→作成、「シンボルの競合が発生」→解決、を動的に行なえる筈なのに、何故このような問題が発生するかといえば、コードの記述に含まれる情報は、リード時より前に決定していなければならないから、ということになります。

表記について

例えば、

(defun foo:fun (n) n)

というコードの記述があった場合、まず、このコードがreadに読み取られる前にfooというパッケージが存在する必要があります。
さらに、foo:funという記述は、funfooパッケージからexportされていることを表わしているので、これもread前に決定している必要があります。
これら2つの前提が揃わなければ、読み取り時に、パッケージが存在しない、もしくは、exportされていないよというエラーになります。
つまり、コードで記述する場合についてはパッケージの仕組みがいくら柔軟でも、それ以前に用意できる情報のみで宣言しなければいけないということになります。

また、パッケージ名を変更したりしても、ソースコード上の記述が書き変わるわけではないので、ソースコードの再読み込み等を考えると、実質ソースコード上の記述に縛られると考えた方が良いでしょう。

シンボルの競合について

 シンボルの競合については、Common Lispでの識別子の名前は単なる名前ではなく、名前が付いたシンボルという オブジェクト を管理している、という感覚でいないと色々と厄介なことを引き起しがちです。
とりあえず、名前の競合の解決について説明したいと思いますが、同一パッケージには同時には一つの名前しか存在できないので、同一の名前のシンボルが割り込んで来た時には、correctable error となり、対応が求められます。
この対応を求められることが、初学者には意味不明と云われることが多いかなと思います。
例えば、

(defpackage :foo
  (:use)
  (:export :a :b :c))

(defpackage :bar (:use) (:export :a :b :c))

という定義があったとして、

(use-package :foo :bar)

を実行した場合に、SBCLだと、

use-package #<package "FOO"> causes name-conflicts in
#<package "BAR"> between the following symbols:
  foo:c, bar:c
   [Condition of type name-conflict]
See also:
  Common Lisp Hyperspec, 11.1.1.2.5 [:section]

Restarts: 0: [keep-old] Keep symbols already accessible BAR (shadowing others). 1: [take-new] Make newly exposed symbols accessible in BAR, uninterning old ones. 2: [resolve-conflict] Resolve conflict. 3: [retry] Retry SLIME interactive evaluation request. 4: [*abort] Return to SLIME's top level. 5: [abort] abort thread (#<thread "worker" running {103C927743}>)

こんな感じに対応が求められます。keep-oldtake-newresolve-conflict、等の選択肢は、処理系によって異なるので、Common Lispに馴れた自分でさえ何がどうだったのかすぐ忘れる始末です。

しかし、上述のようにパッケージは、非常に動的なので実行時にすべて解決できます。
まず、何が起きているかといえば、fooパッケージとbarパッケージはabcという名前をexportしていますが、use-packageは、exportされたシンボルを丸ごと取り込むというものなので、都合3つのシンボルで競合が発生します。
これを解決するには、方針を決定して指示しなくてはいけません。
とりあえずの例として、

  1. aは、fooパッケージのもの
  2. bbarパッケージのもの
  3. cは、fooパッケージのもの

とすれば、

(prog ()
   :again
      (handler-bind ((package-error 
                      (lambda (c)
                        (shadowing-import (list (find-symbol "A" "FOO")
                                                (find-symbol "C" "FOO"))
                                          "BAR")
                        (shadow (list (find-symbol "B" "BAR"))
                                "BAR")
                        (go :again))))
        (use-package :foo :bar))
      (return (export (mapcar (lambda (s)
                                (find-symbol (string s) "BAR"))
                              '(a b c))
                      "BAR")))

(do-external-symbols (s :foo) (print s)) ;>> ;>> foo:c ;>> foo:a ;>> foo:b ;=> nil

(do-external-symbols (s :bar) (print s)) ;>> ;>> foo:a ;>> foo:c ;>> bar:b ;=> nil

位の所でしょうか。
やっていることですが、

  1. package-errorを摑まえて、ACshadowing-import(内部シンボルを使わない)を実行、Bは、shadow(内部シンボルを使う)を実行
  2. 再度exportしなおし

です。
処理系によっては、どのシンボルが競合していてかがコンディション内の情報に含まれているので、細かく設定できると思いますが、貧弱なABCLに合せて書いてみたら、ignore-errorsを使った方がましなのではないかというものになってしまいました。

なんとなく分かると思いますが、“BAR”のパッケージは破壊的に変更されています。
シンボルは一部元とは違うものとなってしまうので、もし関数定義等があれば、定義しなおす必要があります。

それはさておき、上記のように、実行時に解決できるということなのですが、実際の所はこんなコードを書いてはおらず、パッケージ定義の記述時に指定します。

(defpackage :foo
  (:use)
  (:export :a :b :c))

(defpackage :bar (:use :foo) (:shadow :b) (:shadowing-import-from :foo :a :c) (:export :a :b :c))

(do-external-symbols (s :foo) (print s)) ;>> ;>> foo:c ;>> foo:a ;>> foo:b ;=> nil

(do-external-symbols (s :bar) (print s)) ;>> ;>> foo:c ;>> foo:a ;>> bar:b ;=> nil

関数定義等は、このdefpackageでのパッケージ定義の後に行なうので、消えるということはありません。
ただし、パッケージを定義しなおせば、似たようなことが発生します。

パッケージの設計

なんとなくですが、シンボルのまとまりとしてのパッケージの設計は、ある程度天下り的に設計する必要があることが分かるかと思います。
パッケージの扱いについては開発時の柔軟性はある程度諦めて、静的なもの、ソースコード記述時に決定しているもの、と考えるのが吉だと私個人は考えています。
つまり、パッケージのシンボル設計はソース記述前に設計を完了してから記述するか、開発が終わってから綺麗に整理しなおし、天下り的に書き直すか、です。

まとめ

 パッケージは非常に柔軟であるものの、シンボルの読み取りや、競合で問題が発生した場合は、その問題が発生したフェーズより前で対応しなければならないということを説明してみました。

説明としてはいまいちな感がありますが、今後、何か良い説明方法を思い付いたら改訂してみたいと思います。


HTML generated by 3bmd in SBCL 1.2.12

特異メソッドという訳語の謎

Posted 2015-06-10 13:53:50 GMT

特異メソッド といえばRubyですが、Qiitaでこんな記事を見付けました。

この記事にもコメントしてみたのですが、 特異メソッド については、語源と日英の訳の対応がちょくちょく話題になるようです。
上記Qiitaの記事と関連してかしないでかは不明ですが、最近またTwitterで話題になっていたようです。

確か以前にも話題になって調べてなんらかの結論を出した記憶があるのですが、どうも記事にまとめてなかったのでまとめてみたいと思います。

Rubyの 特異メソッド の呼称の由来

まず、Rubyの 特異メソッド 呼称の由来ですが、Bit別冊 Common Lisp オブジェクトシステム(1989)で間違いないようです。

CLOS概説(井田昌之先生): 筆者はこうしたことのためのメソッドを特異メソッドと呼んでいる(P.18)

CLOS解説: 2.10 特異メソッド(P39)

とあり、CLOS解説の方は、大久保清貴氏と、吉川昌澄氏の記事なので、この本の執筆チームで、 特異メソッド という訳語を作った、もしくは造語した可能性が高いと思われます。
では、井田先生は英語ではなんと表現しているのかなと調べてみると、common-lisp-object-systemメーリングリストでは、individual methodと表現されていますので、

特異メソッドindividual method

という対応があると思われます。

I have an experience to write
   methods which have several sigular
   points, and whose bodies are same.
   I feel happy if a syntax like,
   (defmethod foo ((x (member A B C D)))
      ...)

という表現もされているので、特異点(singular point 上記引用ではタイポあり)という表現が気に入っている風でもあります。

individual method については、Sonya Keene氏のObject-Oriented Programming in COMMON LISP(1989年/ISBN-10:0201175894)での用例がありますが、こちらの翻訳である、COMMON LISP オブジェクト指向(CLOS)(1991年/ISBN-10:4810180131)では、 個体メソッド と訳されているようです。

それで、そもそもの individual method の由来ですが、CLOSの大元のCOMMONLOOPS (1985)での、

II.A. Specializing to individuals

individual-specific method

という表現かなと思います。
これは、 (defmethod foo ((x 'foo)) ...)みたいな形式ですが、これが汎用的になったものが、CLOSの(eql foo)という形式です。

Common Lispでの特異メソッド/individual method という用語

Common Lispで 特異メソッド個体メソッドindividual method もあまり耳にしたことがないなあという印象がありますが、実際調べてみるとCommon Lisp界隈ではあまり使われてはいないようです。
CLOSの仕様を議論するcommon-lisp-object-systemメーリングリストでさえ、 individual method と表現しているのは井田先生のみの様子。

それでは、何と呼んでいるのかと調べてみましたが、common-lisp-object-systemメーリングリストでは、大抵は EQL method 、Portable CommonLoops(PCL - SBCL、CMUCL等が採用)のソースコードでは、 EQL methodEQL specializer method 、Lucid CLでも、 EQL method 、TICLOSでは、メソッドの呼称はないものの(eql x)という形式を individual type と呼称、その他の処理系は不明、という感じで、いまいちはっきりしないながらも、 EQL method という呼称が多いようです。
Keene氏のCLOS本は、CLOSの教科書的な立ち位置かと思っていましたが、この本での呼称が広まっていないのも割合に不思議ではあります。

一方、Dylanでは

CLOSの流れを汲むDylanでは、 singleton method というようです。

書法も、

define method double (thing :: singleton(#"cup"))
...
end

という風にCommon Lispのメソッドでのeqlの箇所がsingletonに置き換わっています。

特異メソッドと多重メソッド

一連のTwitterの議論では、 多重メソッド だと(一つに決まらないので) 特異メソッド特異感 が薄まるので、多重メソッド誕生前のFlavorsに起源があるのではないか、というような流れもありますが、上述のように多重メソッドのCommonLoopsが起源だと思われるのでFlavors起源ではないと思います。
一応Flavorsも調べてみましたが、 individual method という言葉はソースコードにみられるものの個別のメソッドを指しているようです。
そもそも多重メソッドでも起動するメソッドは一つのなので妙な話の気もします(Smalltalkの技法のようなDouble dispatchではないので)
まあ、この辺りは思想の違いなのかもしれません。
ついでに、Object LISPとCommonObjectsも調べてみましたが、どちらも該当するものはありませんでした。

まとめ

individual method という呼称があまり使われない理由を考えてみましたが、総称関数は、複数のメソッドを束ねているため『個別のメソッドは〜』というように言及することが多く、ややこしいからかなと推測しています。
EQL method という割り切った呼称がそれなりに定着してしまったからかもしれません。
また、そもそも総称関数なので個別のメソッドのことはあまり分けて意識しないので、呼び方も頓着していないという所かもしれません。


HTML generated by 3bmd in SBCL 1.2.12

Older entries (1938 remaining)