#:g1: MIT LOOPの紹介

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 LOOPは、MIT MacLISP系Lispの繰り返し構文です。

パッケージ情報

パッケージ名MIT LOOP
ドキュメント Glenn S. Burke, George J. Carrette, and Christopher R. Eliot. NIL Reference Manual corresponding to Release 0.286. Report MIT/LCS/TR-311, January 1984. — Software Preservation Group

インストール方法

 MacLISP系Lispでは標準で使えます。Common Lisp、MacLISP、Zetalisp、NIL、Franz Lisp等。Emacs Lispにも移植されています。

LOOPの歴史

 需要はないと思いますが、調べてみたら色々分かったことがあったのでLOOPの歴史でもまとめてみます。

Interlispから輸入(1976-1980)

 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のマニュアルに詳しく機能が説明されています。

MacLISP、Zetalisp、NIL、Franz Lispで共有(1980-1982)

 1980年当初は、どうもLispマシンがメインのプラットフォームだったようですが、すぐにMacLISPとNILでもソースコードが共有され始めます。ちょっと遅れてFranz LispがVAXのMacsymaのために移植。
丁度この時期に#+-リーダーマクロで読み込みを制御するようになったので、ソースコードも単一のものが使われていますが、当時のLispのスーパーセットのようなLSBで記述したものも存在したようです(LSBもGSB氏が関わっている)。

NILが開発の拠点となる(1983位)

 GSB氏はNILの主要開発者であるためか、一次ソースが開発されるのがNILのプロジェクトになります。
NIL自体は最終的に未完となりましたが、NILのLOOPのバージョン829が決定稿という感じで以後他の処理系でも使われます。

ベンダがCommon Lispへ拡張機能として導入しはじめる(1984)

 1984年当時決まったCommon Lisp仕様のLOOPは単なる無限ループですが、処理系が拡張機能として、NILのLOOP 829を添付することが多かったようです。
LOOP 829以外のバージョンの利用ということでは、Symbolicsは、Genera 6.1以降、LOOP 803を元にしたものをベースに改良され、TI-Explorerは何故かバージョン750位で枝分かれしたものを整理して使っていたようです。ちなみにこの頃開発が終っていたMacLISPではバージョン818が最終のようです。

GSB氏がCommon Lisp用に整理したものが共有される(1986)

 Common Lispも広まり始めた頃ですが、CLtL1な処理系のための多機能なLOOPが欲しいということだったのか、GSB氏が当時在籍していたPalladian社の仕事としてNILのLOOP 829を整理して配布します。
Lucid CLあたりがこのソースを使っていますが、何故か独自の実装も用意しています。
また、このソースは、CMUのAIレポジトリで公開されていますが、何故かANSI CL処理系のECLがこれを使っています。MCLもこちらを利用していた様子。

SymbolicsがANSI仕様に準拠させて整理したものを公開(1991)

ANSI Common Lisp対応(1991)

 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)

ANSI CLには取り込まれなかった便利構文

 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-path

 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

 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

 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は、

(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氏の作品といっても良いような気もします。

comments powered by Disqus