#:g1: frontpage

 

Common Lispの機能大盛りでズンドコキヨシ

Posted 2016-03-21 17:12:12 GMT

Common Lispの機能大盛りでズンドコキヨシを書いてみました。
大分無理矢理です。

(eval-when (:compile-toplevel :load-toplevel :execute)
  #+cmucl   (import 'pcl:funcallable-standard-class)
  #+sbcl (import 'sb-mop:funcallable-standard-class)
  #+allegro (import 'mop:funcallable-standard-class)
  )

;;; utilities (defun lsh&inc (n delta bytespec) (ldb bytespec (+ (ash n 1) delta)))

(define-modify-macro lsh&incf (delta bytespec) lsh&inc)

;;; (defconstant kiyoshi-state #b11110 "ズン = 1, ドコ = 0 ズンズン ズンズン ドコ = 11 11 0")

(define-condition kiyoshi () ())

(defclass zundoko-function (standard-generic-function) ((state :initform 0)) (:metaclass funcallable-standard-class))

(defgeneric zundoko (zd) (:method ((zd (eql 0))) (write-line "ドコ")) (:method ((zd (eql 1))) (write-line "ズン")) (:generic-function-class zundoko-function))

(defmethod update-zundoko-function-state ((zd integer) (gf (eql #'zundoko))) (lsh&incf (slot-value gf 'state) zd (load-time-value (byte (integer-length kiyoshi-state) 0))))

(defmethod reset-zundoko-function-state ((gf (eql #'zundoko))) (setf (slot-value gf 'state) 0))

(defmethod zundoko :after (zd) (when (= kiyoshi-state (update-zundoko-function-state zd #'zundoko)) (write-line "キ・ヨ・シ!") (reset-zundoko-function-state #'zundoko) (signal 'kiyoshi)))

(handler-case (loop (zundoko (random 2))) (kiyoshi ())) ;>> ドコ ;>> ズン ;>> ドコ ;>> ズン ;>> ズン ;>> ドコ ;>> ズン ;>> ズン ;>> ズン ;>> ドコ ;>> ズン ;>> ズン ;>> ズン ;>> ズン ;>> ドコ ;>> キ・ヨ・シ! ;>> ;=> nil #-allegro (quit) #+allegro (exit)


HTML generated by 3bmd in LispWorks 7.0.0

Lisp都市伝説を検証する: KCL登場以前にCommon Lispの処理系は存在しなかった、は本当か

Posted 2016-02-01 14:35:08 GMT

KCL(Kyoto Common Lisp)は、1984年に登場したCommon Lisp処理系です。
名前にKyotoと冠するように日本発の処理系で、湯浅太一先生と萩谷昌己先生の御二方が中心となって作製されました。 この処理系に思い入れのあるユーザーは日本には多いようですが、無償で配布されたため日本の大学等で広く使われたようです。
KCLは後に、テキサス大学オースティン校のBill Schelter氏によってAKCL(Austin Kyoto Common Lisp)としてメンテナンスされ、そこからGNUに引き継がれ、現在GNU Common Lispとして知られています。
派生の処理系は沢山あるのですが、KCL系の処理系でANSI Common Lispに準拠したものとしては、ECLやMKCLがあります。

さて、そんなKCLなのですが、「KCLは世界初のCommon Lisp処理系なんだよ」などという話を良く耳にします。
その他色々尾鰭が付いたりしますが、

  • たった二人だけで
  • 仕様を読んだけで
  • 世界で始めて
  • 巨大な仕様のCommon Lisp処理系を作成した
  • 世界中の計算機科学者が仰天した

あたりのコンビネーションが大体のようです。

例を挙げると、

紫藤のWiki: GCL - GNU Common Lisp

1984年にGuy SteeleによってCommon Lisp the Languageが纏められるも、「こんなデカい仕様の言語、一体どこの誰が実装出来るんだ?」と誰もが頭に来ているところに、いきなり日本でKCLが登場したのに世界中の人々はビックリしたらしい。 従って、KCLは世界で殆ど初めて登場したCommon Lisp処理系である。

古都がはぐくむ現代数学: 京大数理解析研につどう人びと

第六章 応用の「花畑」から 第一景 Kyoto Common Lisp を作ったつわ者たち p223

『しかし、問題はあった。言語の仕様はできていても、実際のコンピュータ上で動く言語処理系としてのCommon Lispはまだ存在していなかった。設計図はあっても「建物」はまだ誰も建てていなかったのである』 正式な仕様も完成していなかった

「仕様書を読んだだけでこんな巨大なシステムを作った!?」。驚く計算機科学者は多かったという。Common Lispの処理系がまだ存在しなかった世界では、二人の「無謀な開発」に仰天したのだ。

のようなものがあります。Wikiのようなライトなものから書籍まで幅広いようですが、以下、伝説を眺めつつ検証してみたいと思います。

たった二人だけで

これはコアな部分は御二方で作製されていたようなので、そんな感じのようです。
1984年のコンピュータソフトウェア1(2)の「KCl: / 湯浅太一、萩谷昌己」という記事によれば、DG(データゼネラル)の矢部輝夫、原田年康、両氏に謝辞があります。
両氏の担当としては、マシンに依存な低レイヤー部分や、エディタ等々の作製で活躍されたようです。
開発チームの最大人数としては4人とも考えられます。

仕様を読んだけで

これは本当です。引用文献で出てきますが、

  • Common Lisp Reference Manual, Laser Ed., CMU 1982
  • Common Lisp Reference Manual, Mary Poppins Ed., CMU 1983

の参照のみで作製したようです。
Common Lisp Reference Manualは、正式は出版時には、お馴染のCommon Lisp the Lnaguageとなります。
Mary Poppins Ed. は完成の一歩手前のようです。
正確には、仕様の草稿を元に処理系が作られたということになり、Common Lisp the Languageの発表前に完成している謎はこの辺りに原因があります。

なお、Common Lisp策定グループとは独立して作られた処理系ということで、仕様に記述がない暗黙の規則等々を洗い出すことになりました。
「The Evolution of Lisp」でも、この点が非常に評価されたと回想されています。

世界で初めて/まだ誰も処理系を作っていなかった

これは単純に事実と違います。 上述の御二方のKClの記事でも、

米国ではPERQ上のSpice Lispをはじめ、いくつかのCommon Lispシステムがすでに稼動していると聞くが、我が国ではまだCommon Lispはよく知られていないようである。

と書かれていますが、1982年のLFPでのCommon Lispのお披露目時点で、作成中のCommon Lisp処理系として、

  • Lisp Machine(Symbolics、LMI、MIT)
  • Spice Lisp
  • VAX LISP
  • NIL
  • TOPS-20 Common Lisp
  • S-1 Lisp

が挙げられています。

(前例の無い)巨大な仕様のCommon Lisp処理系を作成した

上記の最初期の処理系のうちCommon Lispの仕様の下敷になったのは、Spice Lispのマニュアルでした。
また、NILは、1979年からMacLISPの後続として開発がスタートしましたが、途中からCommon Lispとなりました。
Common Lispへの重要な影響としては、NILがレキシカルスコープを採用していた為、Common Lispもそれを取り入れることになったようです。

他にLispマシン上のLisp Machine Lispがありますが、これら大別すると3つのMacLISP系方言の共通のサブセット的なものを作ろうというのが、そもそものCommon Lispのスタートです。
共通仕様策定の動機としては、ARPA(DARPA)からLisp系プロジェクトに資金援助をしても良いけれど、それぞれ小さく分散しつつ競合しているような状況で資金援助するのは無駄で嫌なので統一して欲しい、という注文がバックグラウンドにあったようです。

そういう感じのなので、当時の人達の認識としては、Common Lispは新しい機能もあるとはいえMacLISP系の共通のサブセットであり、全く新規の前人未踏の山という認識では全然なかったといえます。

実際LispマシンのLisp Machine Lispの方がCommon Lispより何倍も大きく、NILもCommon Lispよりは大きいです。

こんな感じだからなのか「世界初のCommon Lisp処理系」という点については、そういう判断基準や価値観や興味がなかったらしく、当時の資料を沢山眺めてみても、そのような記述が全然ありません。

世界中の計算機科学者が仰天した

これは当時の熱狂を知るすべがないのですが、現在残る資料を眺めても、これが元ネタか、というようなものはありません。

1984年の6月にCommon Lispの策定グループにKCLのグループがKCLについてメールをしたようなのですが、ここで初めてCommon Lispの策定グループに認知されることになったようです。
最初の報告を受けてFahlman氏は、Spice Lispキットのコードを元に移植したのだろう、と勘違いしていたようですが、策定グループとは全く別個にスクラッチで書かれたと知り賞賛していたようです。

There has been some confusion, partly my fault, about whether the Kyoto
University version of Common Lisp is based on our portable Spice Lisp
code.  I have just received a letter from Taiichi Yuasa of Kyoto
University which makes clear that their implemenation is TOTALLY
INDEPENDENT of our code.  They did receive some early drafts of the
manual, papers, and benchmark code from us (by way of Nippon Data
General), but they did not receive any Lisp system code from us until
several months AFTER their implemenation was finished and running.  I
just wanted to set the record straight.  They apparently got this
implementation running from a standing start in five months with a team
of four people, with no direct input at all from the Common Lisp
designers -- an awesome performance.

To further clarify things, Data General has their own implemenation for the Eclipse. This is the one that was demonstrated at AAAI, and it IS based on our code, though the task of porting it to Data General hardware was done with essentially no help from CMU.

-- Scott

当時、Common Lispの普及の一環として、Spice Projectでは、Spice Lispのコードのマシン依存の部分を書き換えたり、付け足したりすれば動くようなCommon Lispのキットを配布していたようです。
このキットを利用した処理系としては、上記のVAX LISP、TOPS-20 Common Lisp等々があります。
また、bit Vol.17 No.6 1985: Common Lisp 入門(3)によれば、SymbolicsもCommon Lispのエミュレータを配布していたようで、新しく提案される仕様を検証する上で両者は中核になっていたようです。

こういう背景があるので、これらのキットを利用していないこと、また、Common Lispの策定グループとのやりとりもなく仕様書のみで短期間で実装されたことが賞賛された、という所のようです。

とりあえず、実現できるかも分からない巨大な仕様を初めて動くものとして提示して世界を驚かせた、という感じではないことが分かると思います。

まとめ

KCLの業績は偉大です。
偉大ではありますが、世のKCL伝説は想像が多々混じっているようで、ちょっと誇張しすぎな所もあるかなと思います。
実際に、湯淺/萩谷先生の報告では、そういう誇張は一切ないので後の人々が伝説化してしまったのだろうなと想像しています。

ちなみに、当時のKCLの記録は面白いの読んでみては如何でしょうか。


HTML generated by 3bmd in LispWorks 7.0.0

Lisp都市伝説を検証する: Common Lisp vs Scheme (1)

Posted 2016-01-20 13:25:57 GMT

Common LispとSchemeを対比して曰く

LISP系言語はSchemeとCommon Lispを二大潮流とするが、提案された機能を原則全て導入するCommon Lispに対して、成員の全員一致を原則とするSchemeという特徴を持っている。

これは、WikipediaのSchemeからの引用ですが、割と耳にすることが多いSchemeとCommon Lisp特徴の対比です。
しかし、Common Lispの歴史を眺めてみる限りでは、そんなことないよなあと常々思っているので検証してみました。

話の大元

日本語と英語のWikipediaのSchemeの項目を比較してみると、この記述は日本のものにしか存在しないようです。
以前、昔のbitを眺めていて似たような話を目にしたことがあったので探してみた所、大元になったと思われる話を発見することができました。

bit 1996-4、5月号に掲載された、Guy L. Steele Jr.の『Scheme 過去◇現在◇未来』(訳 井田昌之)というものに、ほぼそのまま該当する発言があるようです。

Schemeコミュニティはフレンドリーで…(中略)…Revised reportの作業をしていたときの委員会の大原則 は、「もし変更が提案された場合、誰かがnoと言ったらそれは入れられない」 ということでした。

これとCommon Lispコミュニティと比べてもいいかもしれません。Common Lisp はフレンドリーではないとも言えるでしょう。コンセンサスで動くのではなかっ た。…(中略)…「変更が提案されるとき、誰かがyesと言うとその機能は言語に入れられていきます!」だから、 Common Lispは大きくなりました。

検証

Scheme方面

GLSの話の1996年当時、Schemeは、R4RSでIEEE Schemeも決定、R5RSは作成途中だったようです。 ここまでは全会一致の原則は守られていた、というような話ですが、IEEE Schemeは、95%の賛成で決まったようなので既に崩れてしまっているような…。

Scheme Steering Committee Position Statement(2009)によると、IEEE Schemeが、95%の賛成、R6RSが、66%の賛成で議決されているということです。

R5RSの記述がないですが、IEEE Schemeの上位互換なので、全会一致の下敷にはなり得なそうです(反対だった人もやっぱ賛成という話はあるかもしれませんが…)、とはいえ、R6RS程の混乱もなかったようなので、1998年のR5RSまでは、古き良きScheme精神は保たれていた、という感じなのでしょう。

厳密にいうと、R4RS(1991)まででしょうか。

ちなみに、R7RSは全会一致で議決されたようですが、Scheme Steering Committee Position Statement(2009)があるように、90%の賛成で議決されるとなっているので、全会一致で〜というのはポリシー的にも過去の話になっているようです。

Common Lisp方面

「変更が提案されるとき、誰かがyesと言うとその機能は言語に入れられていきます!」とのことですが、Schemeと対比した誇張と思われ、発言の文字通りであったと考えるのは間違いだと思われます。

仕様策定時でも現在でも有用だと思われる機能で却下(放置)になった機能は沢山ありますが、代表的なものをピックアップしてみました。

ちなみに、ラムダキーワードをキーワードシンボルと同一化するのは、ISLispでは仕様に取り込まれましたし、大域/動的変数についてもISLispで割合に整理されました。
KMP氏は自身の提案を記録に残していることが多いですが中々の執念を感じます。

その他、

  • ローカルな定数宣言/フォーム → 議題にのぼるも立ち消え?
  • 繰り返し機構としてのSeriesの導入 → GLS他が推していてCLtL2に掲載したりするも取り入れられず(ちなみにSeriesの前身のLetSの提案もCLtL1成立前からあったので2回見送られているとも言える)

等々、議題になった提案から、メーリングリストでの提案、真面目なものから戯言まで沢山あります。

蛇足ですが、色々な提案が飛び交うCommon Lispの取り纏めに四苦八苦するGLSというイメージがありますが、GLSからの思考実験/ジョーク/釣り的な提案、ちゃちゃ入れは寧ろ多かったようです。 そういう時は大抵Quux名義なのですが、GLSの幅の広さを感じます。

まとめ

まとめてみると

  • Common Lispでは提案された機能を原則全て導入するなどということはなく、妥当なものでも見送られる(忘れられる)ことがあった
  • Schemeの仕様が全会一致で決まっていた時代は過ぎ去った

という所ですが、Schemeの性質の説明の為に誇張した話が言語ポリシー伝説にまで昇華してしまったのかなと思います。


HTML generated by 3bmd in LispWorks 7.0.0

スペシャル宣言を取り消したい

Posted 2016-01-13 16:07:59 GMT

年始の1/2にCommon Lisp Recipes — A Problem-Solution Approachを購入しました!
お値段は電子版で、$48.99 でした。
755ページもあり、まだ自分は7章までしか読んでいないですが、Common Lispを日常的に書く人には必携の書という感じです。
全部読んだら感想でも書いてみようかなと思っています。

ということで(もないですが) Common Lisp Recipes風にレシピの一つでも書いてみようかなと思い立ち、『スペシャル宣言を取り消したい』というネタで書いてみました。

問題: スペシャル宣言を取り消したい

(defvar var 42)

...

(defun foo () (let ((var 0)) (lambda () (incf var))))

(set 'bar (foo))

(loop :repeat 5 :collect (funcall bar)) ;=> (43 44 45 46 47) ??? (1 2 3 4 5)を期待していたが

クロージャーを作ってカウンターを作ったつもりだったが、意図しない挙動になった。
調べてみると、閉じ込めた変数と大域スペシャル変数との名前が被ったことが原因と分かったので大域のスペシャル宣言を取り消したい。

解決策: なし

一度シンボルに対して宣言してしまったら、スペシャル宣言を取り消す方法は規格にありません。
名前が被らないように、スペシャル変数には、*耳当て*を付けましょう。

しかし、ここでのポイントは、宣言はシンボルに対して、ということです。
ということで、処理系を再起動しなくても、該当のシンボルを破棄してしまえば、復帰できます。

(unintern 'var)

(compile (defun foo () (let ((var 0)) (lambda () (incf var))))) ;=> foo ; nil ; nil

(set 'bar (foo))

(loop :repeat 5 :collect (funcall bar)) ;=> (1 2 3 4 5)

上記のコードを眺めると復帰するのに色々と手間が掛っているように見えますが、新しいシンボルオブジェクトに置き換える必要があるので、良く考えれば妥当であることが理解できるでしょう。

なお処理系によっては、SBCLのように宣言を取り消せるものもあります。

(setf (sb-int:info :variable :kind 'var) :unknown)
;=>  :unknown

しかし、宣言を取り消しても、上記fooの再コンパイルは必要のようです。
ちょっと不思議ですが、規格にない機能なのでしょうがないかなとは思います。

仕組み

Common Lispなどの古典的なLispでは、ソースコードはリストとシンボル/アトムで表現されています。
字面上の表現だけに囚われず、生きたオブジェクトで構成されていると捉えれば、不可解と思われる挙動もすっきり理解できることも多いです。

参考: #:g1: Common Lispの変数の種類と振舞い


HTML generated by 3bmd in LispWorks 7.0.0

Lisp系ウェブサイトのページビューはどんなものか 2015年版

Posted 2015-12-31 12:10:51 GMT

一年を通してLispの記事も色々書かれているわけですが、Lisp系ウェブサイトのページビューはどんなものなのでしょうか。
毎年集計していけば、何らかの傾向が観測されるかもしれないと思い、自分が関わっているサイトのPVをまとめてみることにしました。

Reddit lisp_ja PV: 59,318pv

日本では、ほぼ知られていないRedditですが、海外では割合に人気があります。
今年2chの移住騒ぎで、日本利用者もちょっと増えた感じですが、lisp_jaも利用者は増えてきました。
去年の分を記録していませんでしたが、年間24,000位だったんじゃないかなと思います。

Common Lisp users jp: 30,986pv

更新が滞っているCommon Lisp系情報まとめサイトですがPVはぼちぼちあります。
しかし、更新頻度が上がればPVが伸びるかというとそうでもない様子。

逆引きCommon Lisp/Scheme: 16,114 pv(6月から)

最近あまり更新できていない逆引きCL/Schemeですが、今年6月からで16114pvです。
大体2300pv/月位でしょうか。

lisphub.jp: 4,764 pv

広報活動に失敗している感のあるlisphub.jpですが、今年も年間で4764しかありませんでした。

に関してはかなり充実した内容だと思うんですが、そもそも誰にリーチするのかという気もします。

個人の部

ここからは、私個人のLisp系記事のPVについてです。

このブログ g000001.cddddr.org 25,429 pv

大体月間2,000pvといった所でしょうか。 はてなグループで書いていた時は、年間40,000pv位でしたが、ブログというものが今より元気でしたし、若干のLispブームもありました。

ちなみに、2014年は、21,000pv位でした。300記事位書いたのに…。

Qiita 20,645 pv

QiitaもGoogleアナリティクスが設置できるので試しに設置してみていましたが、去年は、3,200pv位で全然駄目でした。
今年は1月にポエムを投稿したのが好調でPVが伸びたようです。

まとめ

案外サイトのPVは伸びた一年だったようです。
来年も細々と行きたいと思います。

Lisp系記事を書いて露出を増やしたい場合は、是非reddit lisp_jaを利用してみて欲しいですね。


HTML generated by 3bmd in LispWorks 7.0.0

2015年振り返り

Posted 2015-12-31 10:38:07 GMT

毎年振り返りのまとめを書いているので、今年も書いてみます。

今年の前半は、Open Gereraを動かしてSymbolicsの環境を探索したり、Lucid CLをQemu SPARCで動かしたり、またMedleyに触ってみたりで遺跡巡りに勤しんでいました。

後半では、LispWorksを購入したことが自分的には大きなイベントでしたが、9月から子猫を飼い始めた所、PC作業を悉く邪魔してくるので作業する気が無くなっていました。

なお、一体誰の為に書いたのか不明ですが、長文エントリーが多くさらに連続物が多かったのが今年の特徴です。
『Lispとエディタ』については7つも書きました…。

Lispとエディタ (全7回)

あとは、Twitter等で見掛けたLispに関する疑問や誤解のようなものをネタに返信のような形で単発エントリーを書くことも多かったようです。

来年やってみたいこと

来年は消化の年にしたいと思っています。
新しいものには手を出さず、積極的にLisp本の積読などを消化する所存です。

LispWorksも全然掘り下げられていないので、掘り下げたい。

過去のまとめ


HTML generated by 3bmd in LispWorks 7.0.0

Springer祭り Lisp篇

Posted 2015-12-28 15:52:22 GMT

この数日Springerが2004年迄の本や論文を無料でダウンロードできるようにしたことが話題になっています。
Lisp系の本を探してTwitter等でつぶやいている方もいますが、ざっとまとめてみましょう。

ちなみに、AmazonでSpringer+lispで検索して出て来た本を、Springerのサイトで検索すると良い感じにみつけられるようです。

Lisp

Common Lisp

  • Common LISP Modules
    古典的な人工知能の題材をCommon Lispで扱うという本です。手書き文字の判読などが面白そうです。
    GUIのキットは、古いMCL(Coral CL)のObject LISPをベースにいるようなので、その辺りは自作する必要がありそうです。
  • LISP, Lore, and Logic
    Lispの歴史的なところから、Lispの基礎、人工知能、数学的なバックボーン、等々、割合にバリエーションに富んだ内容です。 想定している処理系は、Common Lisp(GCLISP)です。
  • The Art of Lisp Programming
    Lispの入門書です。OOPの章では、またもやObject LISP(Coral CL)が登場。

Scheme

Dylan

  • Programming in Dylan
    Dylanの本もあるようです。Common Lispとの比較が多いのでCommon LispのOOP方面のプログラミングの参考になったりするかもしれません。

まとめ

Springer 太っ腹ですね。
素晴しい!


HTML generated by 3bmd in LispWorks 7.0.0

インライン宣言を利用して型情報を伝搬させる

Posted 2015-12-26 10:50:41 GMT

最適化に困っているというエントリーを目にしたので自分なりに考えてみました。

コンパイラの警告について色々書いてありますが、このエントリーで扱っている問題は、突き詰めれば型が伝搬して行かないので意図したものよりは汎用的なコンパイルコードが出てしまう、ということなのかなと思います。

自分が知っている限りの対策としては、SBCL等を利用した場合の話になりますが、

  1. 最適化したい関数には型宣言はせず、代りに関数にはインライン宣言をして、使われる場所で固めの宣言をする
  2. deftransformを使う

位かなあと思いました。

インライン宣言を使う

最適化したい関数には型宣言はせず代りに関数にはインライン宣言をして使われる場所で固めの宣言をする、というのは下記のようなものです。

一点断わっておくと、型宣言を浸透的にする為にインライン宣言をしているという意図が汲み取れるようなコードをこれまで自分は見たことがありません。
原理的には、まあそうだろうなという所ではありますが、仕様がこの動作を保証している訳でもないと思います。

(declaim (inline ref/inline))
(defun ref/inline (seq i)
  (aref seq i))

(defun bar (seq i) (declare (optimize (speed 3) (safety 0) (debug 0)) (simple-string seq) (fixnum i)) (ref/inline seq i))

disassembleの結果

; disassembly for bar (assembled 59 bytes)
        lea eax, [rdx-15]                ; no-arg-parsing entry point
        test al, 15
        jne L0
        cmp byte ptr [rdx-15], -27
        jeq L3
L0:     lea eax, [rdx-15]
        test al, 15
        jne L2
        cmp byte ptr [rdx-15], -31
        jne L2
        sar rdi, 1
        movzx edx, byte ptr [rdx+rdi+1]
L1:     shl edx, 8
        or edx, 73
        mov rsp, rbp
        clc
        pop rbp
        ret
L2:     break 10                         ; error trap
        byte #X04
        byte #X0F                        ; NIL-ARRAY-ACCESSED-ERROR
        byte #XFE, #X1B, #X01            ; RDX
L3:     mov edx, [rdx+rdi*2+1]
        jmp L1

arefを直接使ったものとの比較

(defun baz (seq i)
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (simple-string seq)
           (fixnum i))
  (aref seq i))

; disassembly for baz (assembled 59 bytes) lea eax, [rdx-15] ; no-arg-parsing entry point test al, 15 jne L0 cmp byte ptr [rdx-15], -27 jeq L3 L0: lea eax, [rdx-15] test al, 15 jne L2 cmp byte ptr [rdx-15], -31 jne L2 sar rdi, 1 movzx edx, byte ptr [rdx+rdi+1] L1: shl edx, 8 or edx, 73 mov rsp, rbp clc pop rbp ret L2: break 10 ; error trap byte #X04 byte #X0F ; NIL-ARRAY-ACCESSED-ERROR byte #XFE, #X1B, #X01 ; RDX L3: mov edx, [rdx+rdi*2+1] jmp L1

;;; ?:inst=はディスアセンブルの結果が同じかを判定するツールとする (?:inst= #'bar #'baz) ;=> t

インライン宣言は、オープンコードともいわれるように実際の所ほぼマクロと同じなので型宣言も浸透的に働きます。
インライン化しないと下記のようになります。

(defun ref (seq i)
  (aref seq i))

(defun foo (seq i) (declare (optimize (speed 3) (safety 0) (debug 0)) (simple-string seq) (fixnum i)) (ref seq i))

; disassembly for foo (assembled 24 bytes) mov rdx, rcx ; no-arg-parsing entry point mov rdi, rbx mov rax, [rip-98] ; #<FDEFINITION for ref> mov ecx, 4 push qword ptr [rbp+8] jmp qword ptr [rax+9]

fooでは最適化とは無縁のrefを呼んでいるだけなので、それ以上は最適化できそうにないことが分かります。

deftransformを使う

SBCLや、CMUCL等のPytonコンパイラ系の処理系ではdeftransformを使って型情報に応じた最適化したいフォームを振り分けることが可能です。

(sb-c:defknown ref* (t t) t)

(sb-c:deftransform ref* ((seq i) (simple-string fixnum)) `(aref seq i))

(defun quux (seq i) (declare (optimize (speed 3) (safety 0) (debug 0)) (simple-string seq) (fixnum i)) (ref* seq i))

; disassembly for quux (assembled 59 bytes) lea eax, [rdx-15] ; no-arg-parsing entry point test al, 15 jne L0 cmp byte ptr [rdx-15], -27 jeq L3 L0: lea eax, [rdx-15] test al, 15 jne L2 cmp byte ptr [rdx-15], -31 jne L2 sar rdi, 1 movzx edx, byte ptr [rdx+rdi+1] L1: shl edx, 8 or edx, 73 mov rsp, rbp clc pop rbp ret L2: break 10 ; error trap byte #X04 byte #X0F ; NIL-ARRAY-ACCESSED-ERROR byte #XFE, #X1B, #X01 ; RDX L3: mov edx, [rdx+rdi*2+1] jmp L1

;;; ?:inst=はディスアセンブルの結果が同じかを判定するツールとする (?:inst= #'quux #'bar) ;=> t

まとめ

実際の所arefにはdeftransformのような形でコンパイラ内部での式変形による最適化のレシピが幾つか設定されているので、上記のインライン化した例ではそれが使われています。
deftransformで定義した場合も、式変形を直接書くことによって邪魔なものを迂回しているので大体同じようなものです。
マクロで書いてしまうという方法もありますが、インライン化ができるのに関数呼び出しを犠牲にしてまでわざわざマクロで書く必要はないと思います。
また、今回の場合は、arefを呼び出している関数を迂回するだけなので、このような場合にはコンパイラマクロを設定して迂回させてもOKかなと思います。

何れにせよコンパイラが賢ければ、こんなことはしなくても良きに計らってくれる筈なんだと思いますが…。


HTML generated by 3bmd in LispWorks 7.0.0

GNU Emacs以外のEmacs特集

Posted 2015-12-23 15:11:37 GMT

Emacs Advent Calendar 2015の24日目です。

Emacsといえば、GNU Emacsですが、GNU EmacsだけがEmacsじゃないよということでGNU Emacs以外にはどんなEmacsがあったのかを紹介したいと思います。
ちなみにこの記事は、LispWorksのエディタ(HemlockというEmacsのCommon Lisp実装の末裔らしい)で書いてます。

大元のTeco Emacs (1975-mid1980)

最初のEmacsはTecoのコマンドの寄せ集めであったというのは周知のことかなと思います。
作ったのは、RMSだけではありませんが、当時、RMSがTecoの専門家であったためRMSがメインとなって保守/改良が進みます。
ITSや、TOPS-20で1980年代中盤頃まで広く使われ、Version 165が最終版のようです。
Lispを中心としてプログラミング言語用のモードやメーラーもありますし、動作もサクサクで、後の1980年代のGNU Emacsの動作の評判が嘘のようです。 (GNU Emacsは当時としては、高スペックマシンでの動作を考慮していた様子)

現在でも、エミュレータのSIMHや、KLH-10、また、公開されているTOPS-20、ITS上で、オリジナルのEmacsを動かしてみることができます。

EINE〜ZWEI〜Zmacs (1977-mid1990)

Lispで実装された最初のEmacsです。
メインの実装者は、当時17歳位のDaniel Weinreb氏ですが、Lispマシン上の実装だったため必然的にLispで書かれることになり、ユーザーによる拡張もLispで行ないます。
Lispの方言は、Lisp Machine Lisp(Zetalisp)で、Emacs LispにもLisp Machine Lispの影響が見受けられます(RMSもLisp Machine Lispのコードを沢山書いていた)。

Lispで実装された最初のEmacsは、Multics Emacsだと度々RMSが発言したお蔭か、世の中ではそういう見方が大勢になっていると思いますが、後にRMSもMultics Emacsの作者のGreenberg氏からの指摘を受けて訂正しています。

ZWEI〜Zmacsは、SymbolicsのLispマシンを中心に広く愛用されましたが、ユーザー定義のコマンドは、Lispの関数とは別にエディタのコマンドを定義する defcommandを使う等、GNU Emacsとは異なった所が多くあります。
また、ユーザーは、Zmacs上からOSを操作できるためユーザーのフロントエンドとして使われることが多く、『EmacsはOS』、『Emacsは環境』という感覚の元祖かなと思います。
GNU Emacsと同じようにユーザーによる拡張も多数書かれました。

Multics Emacs (1978)

Multics MACLISPで実装されたEmacsです。
端末表示に工夫が凝らされた実装のようですが、MACLISPでユーザーが拡張できるのも特長です。
エディタのコマンドは、Lisp関数をそのまま呼び出すようですし、save-excursion等RMSが参考にした機能は多いと思います。

Hemlock (1982-)

1980年代のCommon Lisp(とその前身)では、開発環境としてEmacsが付いてくるのが標準的だったようです。
Hemlockは、Spice Lisp(Common Lisp)で実装され、ワークステーションの標準エディタとして利用されていたようですが、ユーザーはCommon Lispでコマンドを書くことになります。
Hemlockの系統としては、Hemlockそのもの以外にも、Lucid Common LispのHelix、Macintosh Common LispのFred、LispWorksのエディタ等、があります。

Zmacsと同じくコマンドは、Lisp関数とは別にコマンド定義用のdefcommandで定義します。

Common Lispで実装されたEmacsとしては他にNILのSteve、TAO/ELISのZen等がありますが大体似たような感じです。

GNU Emacs (1985-)

ご存知、GNU Emacsです。
マクロ言語として、Emacs Lispを備えますが、他のEmacs実装と比較すると、Lisp関数とコマンド関数を同じdefunで定義((interactive)の有無で区別)する等、色々と工夫がみられます。

Edwin (1989?-)

MIT Schemeで実装されたEmacsです。
カスタマイズもSchemeで可能ですが、エディタ単体としての発展もそれ程無かったようなので、処理系に付属のエディタという性格が強いかもしれません。

Xyzzy (1997-)

日本では有名なエディタで、Common Lisp風Lispをマクロ言語にすることを特徴とすると説明されることが多いですが、他のCommon Lispで実装されたEmacsからすると、Windows上に独自にGNU Emacsを参考にしつつ実装したエディタという感じが強いです。
ユーザーのコマンド拡張もGNU Emacsの方式になっています。

Climacs (2005-)

Common LispとCLIMで実装されたエディタです。
ユーザーは少なく常用している人も稀かなと思いますが、Hemlock風というか、Common Lispで実装された他のEmacsと大体似た感じになっていて、ユーザーのコマンドの方法も似ています。

その他 Emacs実装/Emacs風エディタ

枚挙に暇がありませんが、Gosling Emacsは有名ですね。

まとめ

GNU Emacsの開発者/利用者からは、Emacsの拡張を作るに当って、Emacs Lispの貧弱さがネックだ、という話は良く耳にします。
その解決策として、Common Lispを採用しよう、Schemeを採用しようというのがありますが、実際にこれらの言語で過去に実装されたEmacsの話は出てきません。

Common Lispでの実装の場合、実際に沢山の実装がありますが、GNU Emacsに匹敵する使い勝手を実現するものはZmacs位しかない所をみると、実装言語やマクロ言語をCommon Lisp/Scheme etcにしても大して解決することは多くないんじゃないのかなあと思っています。
Emacs Lispに比べて、Common LispやSchemeは言語機能は上かもしれませんが、エディタのマクロ言語としては別途沢山の調整が必要なのではないでしょうか。
機会があれば、Common Lispや、Schemeで実装されたEmacsを使ってみることをお勧めします :)


HTML generated by 3bmd in LispWorks 7.0.0

Lispと中置記法

Posted 2015-12-23 15:00:01 GMT

Lisp Advent Calendar 2015の24日目です。

Lispで中置記法を実現しようという試みは本当に昔から存在します。 今回はそんな『Lispで中置記法を』という試みを年代順に眺めてみたいと思います。

そもそも何故中置記法を導入したいのか

中置記法といえば、二項演算子で、X op Yのような形式ですが、 数学でも、f(x, y)や、f x yのような記法は前置演算子ですし、前置で書く演算子は他にもあるので、中置記法であることが眼目という訳でもないようです。
Lispに中置記法を導入したい、というよりは、慣れ親しんだ数学の記法を導入したい、ということが多いように思われます。

前置記法とは

Lispの前置記法が数学に由来するのかは分かりませんが、前置記法(ポーランド記法)の、出自は数学で、考案者のヤン・ウカシェヴィチ氏がポーランド人であることに由来するようです。
面白いのが、前置にすることで優先順位を表記するための括弧を減らすことを目的としていたようで、parenthesis-free notation などとも表現されています。

1×(2+3)÷4という風に括弧が必要な所を÷ × 1 + 2 3 4のように括弧が省略できますが、中置演算子がデリミタ兼ねている所を別途デリミタ(空白等)を用意して補う必要があります。

この辺りの事情からか、常に括弧を明示するLispの記法は、Cambridge Polish notationと呼ばれることもあるようです。

LISP 1 〜 LISP 1.5 (1959年頃)

大元のMcCarthy先生のLISPですが、プログラムを記述するためのM式と、データとしてのプログラムを表現する形式のS式があります。
しかし、そのままS式を書いてしまえば良いじゃないかというユーザー達の選択により、M式はS式に敗退してしまいます。
中置記法の敗退としては一回目でしょうか。

M式中の中置演算子としては、defineの意味の=位しかありません。
あとは括弧の位置が関数の前に来るか後に来るかの違いしかなく、読み易くもないという印象です。

fib = λ[[n];
        [lessp[n;2]→n;
         T→plus[fib[difference[n;1]];
                 fib[difference[n;2]]]]]

LISP 2 (1965年頃)

S式で書くことが広まってしまったLispですが、Algol記法で書いてS式に変換するLISP 2が登場します。
これは、ほぼそのままAlgolなので、Lispで中置記法を実現するという意味では、この時点で完全なものが出てしまったという感があります。
LISP 2以降に登場する中置記法が大抵独自文法なのに対し、Algolとのソースコード上での互換性を持たせようとしていた、というのも注目すべき点かなと思います。 全く広まらなかったようなので中置記法の敗退としては二回目でしょうか。

integer function fib(n); integer n;
  if n < 2 
  then n 
  else fib(n - 1) + fib(n - 2);
end;

KLISP (1968)

一般には実用化されなかったとされるM式ですが、日本の中西先生が1968年に作成したKLISPという処理系はM式をベースにしたものでした。

LISP 2のようにS式に変換する方式ですが、これはGLISPと呼ばれ、ソースコードがAlgol互換ではなくM式であったのがLISP 2との違いです。
また、LISP 2がAlgolとの融合を図ったのに対し、KLISPでは、LISP 1.5に忠実で、M式をメインに考えた処理系であったといって良いと思います。
中西先生は、その後の著作や作成した処理系でもM式をベースにされていたようです。

CGOL (1973)

1973年にPlatt氏によって考案されたCGOLですが、主に数学の記法に慣れ親しんだMACSYMAプロジェクトの人達の為に用意されたもののようです。
主にMACSYMAプロジェクト近辺のMACLISPやNILで利用されたようですが、次に紹介するLispマシンと同様リーダーマクロによってLispコードと混ぜて記述することが可能です。

define fib(n);
  if n<2 then
    n
  else
    fib(n-1)+fib(n-2)

INTERLISP — CLISP (1976年頃)

INTERLISP方面は、ちょっと変っていて、DWIM機能が進化し、対話性向上の一環として中置記法が取り入れられました。
これはトランスレータではなく、S式の記法の中に中置的な記法を混ぜることができるというもので、中置演算子や、if、繰り返しのforで利用できます。
Common Lispのloopは、forに由来し、S式の中で中置的な記法を使うという手法が受け継がれています。

define((fib (n)
         (if n<2 
          then n
          else fib(n-1)+fib(n-2))))

MIT Lispマシン界隈 (1984頃)

CGOLからの伝統の継承なのか、MIT系商用Lispマシンでも中置記法がサポートされていました。
CGOLとはまた少し違ったもののようですが、下記のように書けます。

(defun fib (n &optional (a1 1) (a2 0))
  #◊
  if n = 1 then
    a1
  else if zerop(n) then
    a2
  else
    fib(n - 1, a1 + a2, a1))

日本のTAO/ELISでも中置記法はサポートされていたようです。

Dylan (1994)

当初のシンタックスはS式でしたが、早い時期からCかAlgolシンタックスの供給を考えていて、最終的にはAlgolシンタックスになりました。
Dylanでは、Lispの伝統を受け継ぎ識別子に-等の記号が使えるため、中置演算子はデリミタで区切る必要があります。
この辺りはLispっぽいなと思う所です。 また、パタンマッチによる衛生マクロの仕組みがあります。

define function fib(n :: integer) => integer
  if (n < 2)
    n;
  else
    fib(n - 1) + fib(n - 2);
  end;
end;

honu (2011年頃)

最近になると、Lispを中置で書くというよりは、一般的なシンタックスのプログラミング言語にマクロを導入する一環としての試みが多いようです。
Racket方面では、Algol記法で書けたり、JavaScript風のhonu等が開発されていますが、中置記法で衛生マクロというDylanの流れを踏襲しているようです。

function fib (n) {
  if (n < 2) {
    n;
  } else {
    fib(n - 1) + fib(n - 2);
  }
}

Readable Lisp S-expressions Project (2013)

Common LispやSchemeに中置記法を導入し、よみやすくするというプロジェクトですが、この“Readable Lisp s-expressions”以外にも類似のものが何点かあります。

define fib(n)
  if {n < 2}
    n
    {fib{n - 1} + fib{n - 2}}

INTERLISPの流れを汲む、処理系内の半トランスレータという感じですが、それに由来する制限や謎の規則があったりし、全体的に中途半端な感じになることが多いようです。

まとめ

Lispの60年弱の中置記法への取り組みを眺めてみました。
ソースコードのトランスレータ方式は50年前、Lispのリーダー/リーダーマクロでどうにかしてみようというのが40年前、S式の中でどうにかしてみようというのは3、40年前からあることがわかります。
また、20年前位のDylanあたりから別の流れとして、中置記法にLisp的なマクロを導入する試みがあり、最近ではこの辺りが合流したりしている様子。
近頃Lisp的な構文指向のマクロを取り入れる新言語が増えてきているように思えますが、逆方向からのアプローチではあるものの歴史は繰り返す感があり感慨深いです。

Lispでの中置記法について色々な方式や提案はありましたが、S式に埋め込んだ中置記法以外は、ぱっとせずに廃れた所を鑑みるに、入門者向け、数学者向け等のシンタックスを用意しても、結局、Lispを書いていてコードをデータとして扱うようになってしまった人はS式を選択してきたということかなと思います。


HTML generated by 3bmd in LispWorks 7.0.0

Older entries (1996 remaining)