Posted 2014-12-23 15:00:00 GMT
(LISP Library 365参加エントリ)
(Lisp Advent Calendar 2014参加エントリ)
LISP Library 365 の358日目、Lisp Advent Calendar 2014の24日目です。
MIT LOOPは、MIT MacLISP系Lispの繰り返し構文です。
MacLISP系Lispでは標準で使えます。Common Lisp、MacLISP、Zetalisp、NIL、Franz Lisp等。Emacs Lispにも移植されています。
需要はないと思いますが、調べてみたら色々分かったことがあったのでLOOPの歴史でもまとめてみます。
MIT LOOPはどうやら1980年から開発が開始されたようです。開発開始と同時期に(BUG LOOP)と、(INFO LOOP)いうメーリングリストが作成されバグ報告が始まります。
実は、MIT LOOPには先行する繰り返し構文が存在していて、InterlispのCLispの繰り返し構文であるFORをPeter Szolovits氏が1976年にMacLISPに再現したのが始まりで、それを整理したのが、LOOPということみたいです(バージョン124のコメントによれば)。
主要開発者は、Glenn Burke(以降GSB)氏で、1980年から1989年頃まで、ほぼ一人でバグ修正の対応や新機能の追加をしているようです。
何の役にも立たない気はしますが、メーリングリストやソースコードのコメントに出てくるバージョンと日付をメモしておきます。
ちなみに手元で確認できたLOOPのバージョンは、
です。何の役に立つか判りませんが、少なくともこれらバージョンのLOOPのソースは現存します。
メーリングリストを眺めていて面白いのは、GLSが、「LOOPはあまり好きじゃないし使ったことがないけど」と言いつつ仕様の問題点の指摘(ぶらさがりdoの問題等)と、namedの提案をしていたりするところ(ブロックをnamedで指定する機能は取り込まれています)。1980年の時点で既にLOOPが好きじゃない人がいるようです。
マニュアルは、Technical Memo 169, "LOOP Iteration Macro"が発行されていますが、後のバージョンは、NILのマニュアルに詳しく機能が説明されています。
1980年当初は、どうもLispマシンがメインのプラットフォームだったようですが、すぐにMacLISPとNILでもソースコードが共有され始めます。ちょっと遅れてFranz LispがVAXのMacsymaのために移植。
丁度この時期に#+-リーダーマクロで読み込みを制御するようになったので、ソースコードも単一のものが使われていますが、当時のLispのスーパーセットのようなLSBで記述したものも存在したようです(LSBもGSB氏が関わっている)。
GSB氏はNILの主要開発者であるためか、一次ソースが開発されるのがNILのプロジェクトになります。
NIL自体は最終的に未完となりましたが、NILのLOOPのバージョン829が決定稿という感じで以後他の処理系でも使われます。
1984年当時決まったCommon Lisp仕様のLOOPは単なる無限ループですが、処理系が拡張機能として、NILのLOOP 829を添付することが多かったようです。
LOOP 829以外のバージョンの利用ということでは、Symbolicsは、Genera 6.1以降、LOOP 803を元にしたものをベースに改良され、TI-Explorerは何故かバージョン750位で枝分かれしたものを整理して使っていたようです。ちなみにこの頃開発が終っていたMacLISPではバージョン818が最終のようです。
Common Lispも広まり始めた頃ですが、CLtL1な処理系のための多機能なLOOPが欲しいということだったのか、GSB氏が当時在籍していたPalladian社の仕事としてNILのLOOP 829を整理して配布します。
Lucid CLあたりがこのソースを使っていますが、何故か独自の実装も用意しています。
また、このソースは、CMUのAIレポジトリで公開されていますが、何故かANSI CL処理系のECLがこれを使っています。MCLもこちらを利用していた様子。
ANSI CLでは、LOOPが多機能になるということがCLtL2によって広まると、ANSI CL対応のソースの需要が高まったのか、SymbolicsからNILのLOOP 829をベースにANSI CLの仕様に対応し整理されたコードが公開されます。
このバージョンのコードはヘッダにSymbolicsの署名があるので判別しやすいですが、現在メジャーなCommon Lisp処理系は、大体この実装を使っています。
作業についてのコメントもGSB氏が書いているので、当時はSymbolicsに在籍していたのかもしれません(なお在籍はしていたもののこの時期かどうかは不明)。
1986年4月のバージョンを元にしていて、GSB氏の最終バージョンではなかったようなのですが、当時それ以降のバージョンを紛失してしまったということです。
しかし、1986年4月以降のバージョンも後に見付かってCMUのレポジトリで公開されることになったようで、ちょっと捻れた関係になっていますが、ECLは一次紛失していたバージョンをベースに使ってしまっていてANSI対応は独自にしているようです。
ざっと並べると
がこのANSI CL仕様で整理された実装を処理系に合せて調整して利用しています。その他のものというと、CLISPが独自実装な位です。
ちなみにCLISPの実装は、CLtL2の仕様を元に作られている為、finally節でreturnが使えたりします。
(loop :for i :from 0 :to 5 :collect i :into is
:finally :return is)
;=> (0 1 2 3 4 5) NIL LOOP 829とANSI CL LOOPの違いですが、:across節の導入と、ユーザーがLOOPをカスタマイズできる機能の廃止が主なところです。
文章ばかりだったので、ここで廃止された機能を俯瞰してみましょう。
(loop :for e :being :the :elements :of (*:iota 100) :from 5 :to 10
:collect e)
;=> (5 6 7 8 9 10)こんな感じに、fromとtoで範囲が指定可能です。まあ、subseqと組み合せれば済むのですが、あれば便利そうです。
(loop :for e :being :the :elements :in '(a b c d e f g h) :downto 0
:collect e)
;=> (H G F E D C B A)downtoで指定した位置まで逆順で処理します。あまり使わなそうですがインパクトはあります。
using indexで添字を生成できます。
(loop :for e :being :the :elements :of '(a b c d e f g h) :using (:index i)
:collect (cons i e))
;=> ((0 . A) (1 . B) (2 . C) (3 . D) (4 . E) (5 . F) (6 . G) (7 . H))これも添字用のfor節を作れば良いのですが、あったら便利な気はします。
LOOP内で処理する流れをloop-pathと呼ぶのですが、初期のバージョン以降ですぐ廃止になったloop-pathを紹介しておきます。
(loop :for d :being :the :cdrs :of (*:iota 5)
:collect d)
;=> ((2 3 4) (3 4) (4) NIL)
(loop :for a :being :cars :of '((((1 2) 3) 4) 5)
:collect a)
;=> (((1 2) 3) (1 2) 1)
(loop :for a :being '((((1 2) 3) 4) 5) :and :its :car
:collect a)
;=> ((((1 2) 3) 4) ((1 2) 3) (1 2) 1)
being the cdrsはonで実現できますが、being the carsはcarの方向に進んで行くもので、これは後のLOOPの機能にはありません。ちなみに、cddrもあります。
なお、上記の実行結果を眺めると判りますが、being ... and its ...の方は包含的な動作になります。
ユーザーによる機能拡張の構文は、3つあり、ユーザーがLOOPの別名を付けることができるdefine-loop-macro、ユーザーがloop-pathを定義できるdefine-loop-pathと、シークエンス専用のdefine-loop-sequence-pathがあります。
define-loop-macroの方は、LOOP節と同じ名前で定義することで最初の節のキーワードを省略することが可能です。
(define-loop-macro for)
(define-loop-macro repeat)
(define-loop-macro with)
(for i :from 0 :to 5 :collect i)
;=> (0 1 2 3 4 5)
(repeat 8 :collect nil)
;=> (NIL NIL NIL NIL NIL NIL NIL NIL)
(with a := t :repeat 5 :collect a)
;=> (T T T T T)
この機能ですが、InterlispのFORはfor、do、collect、with等で書き始められるので、この辺りをサポートしようとしたのではないかと推測しています。
但し、InterlispのFORでは、
(collect x :for x :from 0 :to 8)のようなことも可能ですが、LOOPでは別名を定義してもできません。
define-loop-pathですが、例として初期で廃止になったcarとcdrのloop-pathを定義してみます。
(defmacro loop-lookup-keyword (item x)
`(assoc ,item ,x :test #'string-equal))
(defun loop-path-carcdr (name var dtype pps inclusive? preps data)
(declare (ignore preps))
(let ((vars) (step) (endtest `(,(cadr data) ,var)) (tem))
(or (setq tem (loop-lookup-keyword 'of pps))
(error "No initialization given for ~S path" name))
(setq vars `((,var ,(cond (inclusive? (cadr tem))
(t `(,(car data) ,(cadr tem))))
,dtype)))
(setq step `(,var (,(car data) ,var)))
(list vars nil nil nil endtest step)))
(define-loop-path (cdr cdrs) loop-path-carcdr (of) cdr atom)
(define-loop-path (car cars) loop-path-carcdr (of) car atom)
(define-loop-path (cddr cddrs) loop-path-carcdr (of) cddr null)
こんな感じのコードの追加で、上記の「その他のloop-path」で出てきたコードの動作になります。
define-loop-sequence-pathは、
(define-loop-sequence-path (schar schars) schar length simple-string
(or null character))
(loop :for c :being :each :schar :of "Temp String"
:for i :from 0
:collect (list i c))
;=> ((0 #\T) (1 #\e) (2 #\m) (3 #\p) (4 #\ ) (5 #\S) (6 #\t) (7 #\r) (8 #\i)
; (9 #\n) (10 #\g))
こんな感じのものを定義することが可能です。
ANSI CL対応版でもdefine-loop-pathより低レベルの拡張APIは用意されているので拡張することは可能ですが、どうも面倒です。
ANSI CL対応版のおまけで拡張用のコードも付属していたのですが、拡張用のコードが動かないので広まらなかったのかもしれません。この辺がちょっと残念です。
ちなみにANSI CL対応版での拡張では、SBCLのiterator protocol対応で、being the elements ofが使えるようになっているものと、Allegro CLで、sequence用に、in-sequenceが使えるようになっているものがあります。また、clsql等で独自のloop-pathを定義している例もあったりはします。
今回は、MIT LOOPを紹介してみました。
調べてみればこの34年位でLOOPマクロの実装は殆どの処理系で同じものが使われていたというのが意外でした。
CLtL1以後、Common Lispの繰り返しについて議論するワーキンググループがあり、そのまとめはJonL White氏がCLtL2に書いているので、JohnL氏あたりが中心となって開発しているのかと思っていましたが、実際のところは、GSB氏ほぼ一人がかなりの割合で面倒を見ていたというのも意外でした。
LOOPマクロはGSB氏の作品といっても良いような気もします。