【Common Lisp】
loop の成り立ちを考える
（CLISPとDSL）

by

Common Lispのloopは、「便利な反復マクロ」です。
ただ、見た目の「親しみやすさ」に反して、独自の文法、実行モデル、歴史的経緯を備えた、奥深い仕組みです。

ANSI Common Lisp や Common Lisp the Language, 2nd Edition（以下 CLtL2）の仕様などから、loopとは何なのか、考えてみたいと思います。

関連記事

1. loop とは何者か（DSL）

一言でいえば、loop は「言語」です。
Common Lisp の制御専用の DSL（domain-specific language）といえます。

Common Lisp の loop は何者か loop の正体 制御専用 DSL domain-specific language 独自の構文解析 変数束縛・終了判定・蓄積を統合 展開形は block + tagbody 2つの形式 simple loop 無限反復のみ・素朴な形式 extended loop keyword ベースの DSL ▼ 以降は extended loop

確かに loop の実装は、Lispマクロです。
つまり、「S 式を別の S 式へ置換する」仕組みですが、単なる「英語風の糖衣構文（Syntax Sugar）」というには不釣り合いなほど複雑な言語体系を持ちます。

loopは、マクロ展開時に独自の構文解析を行い、反復変数の束縛、初期化、更新、終了判定、蓄積、脱出を一つの構文系で統合しています1。

Common Lisp の仕様でも、loop単なるマクロ以上のもの、つまり「小さな反復言語」として 位置づけられています。
たとえば、HyperSpec 6.1 は、loop を通常の Lisp 構文の上に載った専用 facility として扱い、「変数初期化と更新」「値蓄積」「終了判定」「無条件実行」「条件付き実行」「その他」という節群へ分解しています。

  1. Common Lisp HyperSpec, Section 6.1, The LOOP Facility
  2. Guy L. Steele Jr., Common Lisp: The Language, 2nd Edition
  3. Warren Teitelman, “CLISP: A conversational lisp system”, 1973
  4. Richard P. Gabriel and Guy L. Steele Jr., “The Evolution of Lisp”

1.1. 単純 loop と 拡張 loop

ちなみに、Common Lispのloop には、よく使われる 拡張 loop のほか、まったく別物の単純 loop が共存しています。

  • 単純 loop は、本体を無限に繰り返す素朴な形式で、
  • 拡張 loop は、反復条件をキーワードで組み合わせた形式です。

単純 loop と、専用反復言語としての拡張 loopは、概念的にも歴史的にも別ものです2。
これ以降は、特に断りのない限り、拡張 loop を扱います。

1.2. 前置記法のルールを逸脱する節構造

拡張 loop は、原子的式（atomic expression）を含む本体を、loop keyword ベースの DSL として解釈します。

拡張 loopの仕様（HyperSpec）では、

  • extended loop の本体を loop clause に分解し、
  • 各 clause は loop keyword と form から構成される

と説明しています。

大事なことは、loop のコードは、通常の Lisp 式列ではないこと。
for、when、collect などの keyword を節導入子として持つトークン列として扱われます。

言い換えれば、for、as、collect、sum、while のような語は、通常の Common Lisp 評価規則に従う識別子ではなく、loop 内部でだけ特別な意味を持つキーワード3。
loop の構文規則が節を切り分ける起点になっています。

つまり、loop は、Lisp の前置記法から外れた言語体系で、この点がloop への好き嫌いにも関係しています。
しかし、同時に非常に高い「表現圧縮率」を持つことになります。

loopは、必要な制御構造を簡潔に書ける、そういう実用の産物です。

2. loopの元となる「読みやすいLisp」という考え方

Common Lisp の loop の発想は、ANSI Common Lisp から突然生まれたものではありません。

「読みやすいLisp」CLISP の遺産 Interlisp Teitelman 1973 CLISP Conversational LISP Common Lisp loop マクロ CLISP に実装された構文 中置演算子 A+B*C 形式 IF-THEN-ELSE 英語風条件構文 FOR-DO-WHILE 反復構文（loop の原型） 添字アクセス X:1 / X::1 形式 リスト構築記法 <A !B> 形式 Common Lisp に 残ったのは loop のみ ALGOL 風記法を Lisp に取り込む試み → 反復制御の局所領域のみ採用 Teitelman（Xerox PARC） 1973

その祖型は、Interlisp 系の CLISP（Conversational LISP）に現れます。
CLISP は、通常の Lisp に混在できる、ALGOL風・英語風の補助構文系です4。

ALGOLは、1950年代末から1960年代にかけて設計された初期のプログラミング言語で、ブロック構造などの記法は、C言語などの多くの言語に影響を与えています5。

Warren Teitelman の 1973 年論文では、CLISPの「可読的」な構文として、中置演算子、IF ... THEN ... ELSE ...、FOR ... DO ... WHILE ... のような構文が用意されていました。
しかも、Lisp 本体を置き換えるものではなく、既存 Lisp の上に乗る「会話的」層という位置づけだったことが興味深いです。

Lispマクロのもつメタプログラミングの柔軟性、DSLの作りやすさが、ALGOLやCOBOLのような記法を取り込もうとした試みというわけです。たぶん、今でこそExcelの位置にある事務計算の分野で使われるためには、「読みやすさ」は重要だったのでしょうね。

2.1. 中置演算子構文

CLISPの「会話的構文層」とはどんな発想なのか、他の構文も見てみます。

まず、驚くのは CLISP には、A+B*C のような中置演算子構文があったことです。
たとえば、通常の Lisp なら (+ A (* B C))と書く式を、CLISP ではA+B*Cと書けるのです6。

(DEFINEQ
  (DISCRIMINANT (LAMBDA (A B C)
    B^2 - 4*A*C))
  (ROOT1 (LAMBDA (A B C)
    (-B + SQRT(B^2 - 4*A*C)) / (2*A)))
  (ROOT2 (LAMBDA (A B C)
    (-B - SQRT(B^2 - 4*A*C)) / (2*A))))Code language: Lisp (lisp)

ラムダ式の中身が、数学的な数式の形で記述されています。
これは、リーダーマクロに近い層で読み取り時に従来の Lisp 式へ変換する仕組みが想定されていました。

FortranのCompute文みたいですね。

2.2. 英語風 if 条件構文

さらに英語風の if 構文があり、たとえば通常の Lisp では、ifは特殊形式ですが、

(defun factorial (n)
   (if (= n 0)
     1
     (* n (factorial (- n 1)))))Code language: Lisp (lisp)

CLISP では、手続き言語的な形が示されています。

(DEFINEQ
  (FACTORIAL (LAMBDA (N)
    (IF N=0
        THEN 1
        ELSE N * FACTORIAL(N-1))))

  (ABSVAL (LAMBDA (X)
    (IF X<0
        THEN -X
        ELSE X))))Code language: Lisp (lisp)

ポイントは、IF、THEN、ELSE は特殊形式ではなく、句構造を作る導入語になっていることである。
後の Common Lisp loop で when、unless、else、and が節の境界を作るのと同じ発想は、ここで萌芽が見えます7。

IF-THEN-ELSEは、あんまり読みやすくなった気はしませんが。

2.3. loopの原型となる for

loop に似た for の反復構文もありました。

たとえば Gabriel/Steele が引用する CLISP 系の例では、

(DEFINEQ
  (SUM-ODD-SQUARES (LAMBDA (N)
    (PROG (S)
      S_0
      (FOR I_1 TO N
           UNLESS EVENP(I)
           DO S_S + I*I)
      (RETURN S)))))Code language: Lisp (lisp)

のような書き方が用意されました。

Teitelman 論文には FOR-DO-WHILE-UNLESS-FROM-TO 系の語群がまとまった family（同族構文群）として現れる。

(FOR I FROM 1 TO 10 DO (PRINT I))
(FOR X IN L WHILE P(X) COLLECT F(X))
(FOR K FROM 10 TO 1 BY -1 UNLESS (ODDP K) DO (PRINT K))Code language: Lisp (lisp)

ポイントは FOR が単独の文ではなく、FROM、TO、BY、WHILE、UNLESS、DO などの補助語と一緒に句を組み立てることです。
「主語となる導入語 + 補助語の列」という設計は、後の loop の 節システムにつながっています8。

2.4. 添字風アクセス記法

ほかに、X:1 や X::1 のような添字風アクセス記法がありました。

これは、Lisp の car / cdr 鎖や nth 的操作を、「添字でわかりやすくする」という発想である。

概念的には、たとえば、(car x)、(cdr x)、(cadr x)のようなアクセスを、CLISP では、X:1 X::1 X:2のような記法で書きます。

; Subscript-like access: X:1 / X::1
(DEFINEQ
  (SECOND-AND-TAIL (LAMBDA (X)
    (LIST (QUOTE SECOND) X:2
          (QUOTE TAIL)   X::2)))
  (ROTATE3 (LAMBDA (X)
    <X:2 X:3 X:1>)))Code language: Lisp (lisp)

2.5. リスト構築記法

さらに <A !B> のようなリスト構築記法もありました。

! は「後ろにつなぐ」「残りのリストを差し込む」という記号です。
これは (cons a b)に近い動作を、角括弧風の視覚記法で表します。

; Angle-bracket list construction with splice: < ... ! ... >
(DEFINEQ
  (PAIR-WITH-TAG (LAMBDA (TAG ITEMS)
    <TAG !ITEMS>))
  (MAKE-LET-BINDING (LAMBDA (VAR VALUE BODY)
    <(LET ((,VAR ,VALUE)) !BODY)>)))Code language: Lisp (lisp)

2.6. loopがDSLとして残った

Conversational LISP では、Lisp の内部表現を保ったまま、式、条件、反復、データアクセス、データ構築を横断する一群の Algol 風の記法ができるようにする構想です。

Common Lisp は、このような全面的な構文を受け入れることはありませんでしたが、反復などの局所領域に限定して取り入れました9。
それが、 loop構文 の固有性として生き残っているわけです。

CLISP のもっとも大きな遺産が、loop ということになります。

3. loop以外に検討された反復構文

ちなみに、lispに効率的で「高級」な反復構文を作るのに際しては、loop以外の設計も検討されました。
それが、series、generators です。

X3J13 が検討した3つの反復構文 loop 命令的 DSL 制御構造として反復を記述 (loop for i in list when (plusp i) sum i) 節の列で制御を記述 ✓ ANSI 標準採用 series データフロー変換 関数合成 → ループへ変換 (collect-sum (choose-if #’plusp (scan list))) R.C.Waters（MIT）設計 CLtL2 付録止まり generators 入出力プロトコル next-in / next-out で接続 (let ((g (gatherer #’collect-sum))) (next-out g i) …) Perdue & Waters 設計 CLtL2 付録止まり

1984 年の初版 Common Lisp: The Language では、まだ拡張 loop が標準機能に収まっていませんでした。
cltl2 によると、X3J13 が追加の反復機構の一つとして拡張loopが採用したのは、1989年1月。
当時、X3J13 Iteration Subcommittee は三つの候補、すなわち loop、series、generators を検討しました。

後でコードを読みますが、loop、series、generators を並べると、

  • loop は、命令的なコードが自然に書けるDSL
  • series は、パイプ処理指向で関数的明晰さと反復効率を両立する案
  • generators は、オブジェクト指向の入出力ストリームライブラリに近い案

3.1. loop: 逐次制御を一つの DSL に圧縮する案

Common Lisp が loop を採用したのは、命令的なコードに自然に埋め込められることにあったと考えられます。

loop の良さは、制御の要素（反復変数の導入、終了条件、条件付き実行、結果蓄積）を一箇所にまとめられることです。
手続き指向の考え方で、展開後のモデルも暗黙ブロック、局所変数束縛、更新、終了判定、tagbody 的制御に近いです。

(loop for i in '(1 -2 3 -4)
      when (plusp i)
      sum i)
;=> 4Code language: Lisp (lisp)

この例では、繰り返し処理のリスト走査、条件分岐、蓄積は、loopの clause 列として押し込めています。

3.2. series: 関数合成を保ったままループへ落とす案

series は、sequence、stream、loop の性質を兼ね備えた仕組みです。

これは、コードを読んだ方が速いです。

(collect-sum 
   (choose-if #'plusp 
       (scan '(1 -2 3 -4))))
;=> 4Code language: Lisp (lisp)

この式は、リストを scan で series 化し、choose-if で変換し、collect-sum で合計を計算する処理を示しています。

scan は、 series 系の入口で、リスト '(1 -2 3 -4) を series オブジェクトに変換しています。
choose-if や、collect-sumは series 系の演算子で、全ての要素を述語関数 #'plusp でフィルターして、合計して通常の値へ落とします。

これらの仕組みで、処理パイプラインを作ることができるのです。

無限系列から必要部分だけを使う例としては、

(let ((x (subseries (scan-range :from 0 :by 2) 0 5)))
  (values (collect x) (collect-sum x)))
;=> (0 2 4 6 8) and 20Code language: Lisp (lisp)
  • scan-range は series を生成する演算子で、ここでは 0, 2, 4, 6, ... という偶数列を作っています。
  • subseries は series の一部分だけを切り出す演算子で、0 以上 5 未満の範囲、つまり最初の5要素を残す。
  • collect や collect-sum は series をリストや総和へ落とす終端演算子である。

通常のCommon Lispでは、複数の関数処理をそのまま mapcar などでつなぐと、値の受け渡しに毎回リストを生成して計算効率が極端に悪くなってしまいます。
そのために、反復構文が必要とされます。

seriesオブジェクトの利点は、「中間リストを作らずに反復へと変換できるようにする」ことです。
つまり、系列全体に対する演算として書きながら、実装では（可能なら）それを反復処理に変換することで効率を両立させるための設計になっています。
「人間にはデータフローとして見せ、処理系ではループへ落とす」設計なのです10。

ただし、この series は強力なのですが、コンパイラにとっては複雑で「関数的表現をどこまで安全に反復へ変換できるか」という問題に依存することになります。

Haskellのシーケンス操作に似ていますね。

3.3. generators: 単方向の入出力プロトコルとして反復を捉える案

generators の設計では、generatorとgathererというSmalltalk 的な「入出力オブジェクト」を使って反復処理を記述します。

generator は、一般化入力ストリーム（generalized input stream）で、next-in で要求された時にだけ次の要素を計算し、取り出された要素は副作用により消費されます。
一方、gatherer はその出力側の対となる 一般化出力ストリーム（generalized output stream）で、next-out で値を流し込み、result-of で最終結果を得ます。

つまり、generators のコンセプトでは、「次の要素を要求する」という next-in プロトコルです。

コード例を見ると、

(let ((x (generator (scan '(1 2 3 4)))))
  (with-output-to-string (s)
    (loop (prin1 (next-in x (return)) s)
          (prin1 (next-in x (return)) s)
          (princ "," s))))
;=> "12,34,"Code language: Lisp (lisp)

generator は、scan で作ったseriesを、さらに1要素ずつ取り出せる generator オブジェクトへ変換します。
next-in は、generator x から次の要素を1つ取り出します。
単純loopは、無限ループになっていますが、next-in の第二引数で、要素が尽きたときの脱出動作(return) を指定しています。

同じ Appendix B には gatherer（出力側）についても例があります。

(let ((g (gatherer #'collect-sum)))
  (dolist (i '(1 2 3 4))
    (next-out g i)
    (if (evenp i) (next-out g (* 10 i))))
  (result-of g))
=> 70Code language: Lisp (lisp)

標準的な dolist のループの中で逐次的に値を送り込み、最後に結果を得ている。

gatherer は、先に集約処理として#'collect-sum関数を渡しています。
next-out は、値を1つずつ gatherer g へ流し込み集約処理が進めます。
gatherer には値が蓄積していくので、result-of で最終結果を取り出します。

つまり、generatorsのコンセプトはストリーム的です。
副作用を含むので、単方向・単回消費の制御に向いています11。

C++のiostreamやiteratorのような設計ですね。当時は、こういうのが流行りだったんでしょうね。

4. まとめ

Common Lisp の loop は、「使いやすい反復とは何なのか」という議論の中で残りました。

反復を何として捉えるかには、いろんな答えがあります。

  • 伝統的なLispでは、反復は「再帰」で扱いました。
  • loop は、反復を「制御構造」として捉えます。
    変数、更新、終了、蓄積、脱出を一つの局所言語へまとめる。
  • series は、反復を「データフロー変換」として捉えます。
    関数合成で書かれた系列演算を、処理系が必要に応じてループへ変換します。
  • generators は、反復を「ストリーム」として捉えます。
    入力側と出力側を next-in / next-out / result-of で接続します。

ただし、series と generators は、より洗練されている反面、採用時点では言語の中心機構としてはまだ先進的すぎたといえる12。

  1. loopマクロの展開形は、変数を束縛するletまたはlambda形式と、ループ制御構造を表すblockおよびtagbodyを含む形式で構成されます。プロローグ（初期化）、本体、エピローグ（後処理）の3部構造がtagbodyの中に配置されます。 – Common Lisp HyperSpec 6.1.1.4 – Expanding Loop Forms
  2. X3J13のIteration Subcommitteeの委員長はJon L. Whiteで、loopを「ALGOL的」な構文を持つDSLとして採用することを主導しました。この構文がLispの通常のS式構文と異なる点は当時から論争的で、現在も議論が続いています。 – X3J13 – Wikipedia
  3. Common Lispにはloop専用のキーワード名前空間があります。for、when、collectなどの語は通常のシンボルとして評価されず、loopマクロの構文解析器が節の区切りとして解釈します。CL標準はloopのキーワードを通常パッケージシステムの外に置いています。 – Common Lisp – Wikipedia
  4. CLISPはWarren TeitdelmanがXerox PARCで開発したInterlisp上の構文拡張で、エラーハンドリング機構を利用して実装されていました。評価エラーが発生した式をCLISP構文として走査し、通常のLisp式へ変換するという仕組みで、インタープリタ本体を変更せずに実現していました。 – Warren Teitelman. CLISP – Conversational LISP. 1973
  5. ALGOLは1958年にチューリッヒでの国際会議で設計が始まり、ALGOL 60がブロック構造、lexical scope、再帰などを導入しました。C、Pascal、Ada、Simula、BCPLなど多数の後継言語の設計に影響を与え、30年以上アルゴリズム記述の標準記法として使われました。 – ALGOL – Wikipedia
  6. CLISPの中置演算子はリーダーマクロに近い層、あるいはエラー回復機構で処理されていました。通常の評価でエラーになった式をCLISP構文として再解釈し、等価なLisp前置形式へ変換します。Fortranのcompute文に似た数式スタイルでLispコードを記述できました。 – Warren Teitelman. CLISP – Conversational LISP. 1973
  7. CLISPのIF-THEN-ELSE構文でTHENとELSEが句境界として機能する設計は、後のloopのwhen/unless/elseが節境界として機能する設計に直結しています。どちらも通常のLisp評価を受けない「節導入語」という役割を担っています。 – Richard P. Gabriel and Guy L. Steele Jr., “The Evolution of Lisp”
  8. InterLisp側ではこのFOR構文が1974年にLarry Masinterによってさらに洗練されました。Common Lispの歴史ドキュメントは「TeitlermanのIterationコンストラクトがLisp Machinesおよび MacLispのloopマクロに影響を与えた」と明記しています。 – History of the Lisp Language
  9. X3J13はCLISP系の構文を全面採用するのではなく、反復制御という局所領域のみにDSLを限定することを選択しました。CLtL1（1984年）にはまだ拡張loopは含まれておらず、X3J13が1989年1月に採択したことでCLtL2（1990年）に収録されました。最終的なANSI CL標準は1994年に公開されています。 – Common Lisp the Language – Wikipedia
  10. seriesはMITのRichard C. Watersが開発し、CLtL2（1990年）のAppendix Aに収録されました。Watersによれば、約7年間で6名のプログラマが10万行のアプリケーションコードをseriesで書いており、そのほぼ全反復処理に活用されたと報告しています。現在もSBCLなどで利用できるライブラリとして維持されています。 – Appendix A. Series – CLtL2
  11. generatorsとgatherersはCrispin PerduとRichard C. WatersがCLtL2 Appendix Bとして執筆しました。series同様、X3J13はこの提案を標準に採用せず付録扱いとしましたが、将来の標準化に向けて作業を継続する方針を示していました。最終的にANSI Common Lisp（1994年）にも含まれませんでした。 – Appendix B. Generators and Gatherers – CLtL2
  12. CLtL2にはseriesとgeneratorsが付録として収録されましたが、series・generatorsともにANSI Common Lisp最終標準（1994年）には含まれませんでした。Steele自身はCLtL2の序文でこれらが実用的価値を持つと述べつつ、標準化の判断はX3J13に委ねるとしていました。 – Common Lisp the Language – Wikipedia