【Common Lisp】
リスト終端記号nilが「空リスト」と
「偽」を兼ねる小歴史

by

関連記事

1. nilは最初はただの終端シンボルだった

Lispの nil は、条件式で「偽」になる「空リスト」です。

しかし、もともとのnilは、「空リスト」でも「偽」でもありませんでした。
1960年の原論文でMcCarthyが書いたのは、リストを終端するためのアトム記号としてのNILだけです。

1.1. 終端記号としてのNIL（1960年）

McCarthyの原論文「Recursive Functions of Symbolic Expressions and Their Computation by Machine」でS式は次のように定義されました。

「S式はアトムか、二つのS式のドット対のどちらかです1」

NIL、 (A B C) の内部表現において、「リストの終わり」を示す印として登場します。

(A . (B . (C . NIL)))

論文の原文では “NIL is an atomic symbol used to terminate lists” と一行で述べられているだけで、このときにはそれ以上の意味付けはありませんでした。
つまり、「NILは、シンボル」です。

このほか原論文で NIL が登場するのは、リスト略記法の定義と例示だけです。

(m) は (m.NIL) を、
(m1,...,mn) は (m1.(... (mn.NIL)...)) を、意味すると規定し、

((AB,C),D)    は  ((AB.(C.NIL)).(D.NIL))   の略記
((A,B),C,D.E) は  ((A.(B.NIL)).(C.(D.E)))  の略記Code language: CSS (css)

と例示する箇所です。

基本関数 car・cdr・cons・atom・eq の定義と使用例、再帰S関数を定義するコードはすべてドット対の形で書かれていて、NIL は出てきていません2。

1.2. 偽は F だった

真偽値についても、原論文では、偽は NIL とは別物の F が定義されています。

「Propositional Expressions and Predicates」セクションでは、「命題式の取りうる値はT（真）とF（偽）である」と定義しています。
また、「T と F を値域とする関数」を述語関数として、NILはここにも登場しません。

基本となる条件式は、現在のcondに近い (p1 → e1, ..., pn → en) という形式で、pがTになった最初のeを返します。
論理演算のAND・OR・NOTは、条件式で定義されています。

p ∧ q = (p → q, T → F)
p ∨ q = (p → T, T → q)
¬p   = (p → F, T → T)

最後の T は、「それ以外すべて」を意味する else節 に相当しています。

今のCommon Lisp風に書けば、

;; p ∧ q = (p → q, T → F)
(defmacro my-and (p q)
  `(cond (,p ,q)
         (t nil)))Code language: Lisp (lisp)

つまり、当初のLisp設計では、リスト終端と真偽値の体系は分かれていて、NIL と F に設計上の接点はありませんでした。

2. 二つの統合（Lisp 1.5〜MacLisp、1960年代〜1970年代）

Lisp 1.5の実装を進める中で、終端シンボル NIL に 2つの意味を追加すると「都合が良い」ことがわかっていきます。

  • 空リスト
  • 偽値

つまり、NILの扱いは、「Recursive Functions of Symbolic Expressions and Their Computation by Machine」で提示された理論を元に、実装していく中で '() や F と統合されたわけです。

これらが固まるは、Lispの初期の普及を担った MacLisp です。
MacLispは、Lisp 1.5の直系として MITのProject MACで開発され、1960年代後半に登場し、1970年代に多くの研究室で使われました。

このMacLispでは nil は完全に三つの役割を担うようになっています。

  • リスト終端記号
  • 空リスト () と同一のオブジェクト
  • 条件式における偽

この MacLisp の NIL 実装が、その後に Lisp に大きな影響を与えます。

2.1. NIL をリストの文脈で使う

もともと原論文のS式には「空リスト '()」という概念は出てきませんでした。

S式はアトムかドット対のどちらかで、要素ゼロのリストを表す方法はありませんでした。
ところが、リストを引数に取る関数を実装していると、「何もない」状態を渡したい場面が繰り返し出てきました。

たとえば、appendにリストが一つもない場合です。
もし、NILがただの終端シンボルなら、lengthや append などのリストを引数とする関数に渡すと型エラーになってしまいます。

;; シンボルには長さはない
(length :NIL) 
;=> TYPE-ERROR expected-type: SEQUENCECode language: Lisp (lisp)

ですが、NIL をそのまま空リスト () として扱えると、(length NIL) や(append NIL some-list) が自然に動きます。

(defparameter empty (cdr '(a . NIL)))  ; => EMPTY -> NIL
(length empty)                         ; => 0
(append empty '(b c))                  ; => (B C)Code language: Lisp (lisp)

つまり、NILはシンボルでありながら、「要素ゼロのリスト」でもあるのは、ほかのリストと同じ文脈で扱えるようにするためです。

2.2. NIL を条件式の文脈で使う

もう一つの統合は、真偽値の「偽」との関係です。

当初は、「偽」を表すシンボルとして F が想定されましたが、これを NIL で兼用する、という設計です。

リストを再帰で処理する関数には、必ず「リストが終端に達したか」を判定する条件分岐があります。

(defun my-length (lst)
  (if (null lst)
      0
      (+ 1 (my-length (cdr lst)))))Code language: Lisp (lisp)

もし、NIL を F とみなせば、null 関数の処理が不要になります。

(defun my-length (lst)
  (if lst
      (+ 1 (my-length (cdr lst)))
      0))Code language: Lisp (lisp)

リスト自体を条件式に渡すだけで、再帰が進んで lst が空になったら止めることができます。
述語関数 null や endp を使わずとも、暗黙的に終端チェックできるのです。

2.3. 条件式の一般化ブーリアン

この変更では、同時にもう一つ大きな意味があります。
「TかFを取る」から「nilか非nilを取る」への転換です。

原論文では、条件式に T か F の2つだけしか入れられませんでした。
しかし、「空ではないリスト」などの値も、「真」とみなすことになります。

これを「generalized boolean（一般化ブーリアン）」と呼びます3。
generalized booleanでは、nilが偽、nil以外のすべての値が真として扱われます。

数値の1も文字列も、リストの残りの部分も、nilでなければすべて真です。

(if 42      "true" "false")  ; => "true"
(if "hello" "true" "false")  ; => "true"
(if '(a b)  "true" "false")  ; => "true"Code language: Lisp (lisp)

このことのメリットは、「見つかった要素そのもの」や「残りのリスト」を返す member などの探索関数をそのまま条件式で使えることです。

(if (member 'x my-list)
    (do-something)
    (handle-missing))Code language: Lisp (lisp)

memberが失敗すればnilが返り、条件式は偽になります。
探索とboolean判定が自動的に一致する、この一貫性がMacLispスタイルの再帰処理を簡潔に しました。

;; Common Lisp
(defun my-member (item lst)
  (if lst
      (if (equal (car lst) item)
          lst
          (my-member item (cdr lst)))
      nil))Code language: Lisp (lisp)

型としての真偽値が消え、「nilでないこと」が真を意味する体系に変わりました。

つまり、

  • NIL と()の統合は、関数の引数として何を受け入れるかという問題で、
  • NIL と F の統合は、条件式に何を受け入れるかという問題だったわけです。

3. Common Lispによる統合の明文化（1984年〜）

この流れは、Common Lisp にも引き継がれています。

1981年のDARPAスポンサードの会議を経て、Symbolics、SPICEプロジェクト、NILプロジェクト、S-1 Lispプロジェクトが合流し、Common Lispの仕様策定が始まりました。
1984年に最初の仕様、1994年にANSI標準が出ています。

ここで、nilの三重の役割は仕様として明文化されました。
ANSI HyperSpecでは、3つ表記が同一のオブジェクトを指します。

コンテキスト慣用表記意味
ブーリアン値としてnil偽
シンボルとして'nilシンボル
空リストとして'()空リスト

人間にどの役割を意図しているかを伝えるために、慣習的に3つの書き方がありますが、コードとしては同一オブジェクトを意味します。

(eq nil (not t)) ;=> T
(eq nil 'nil)    ;=> T
(eq nil '())     ;=> TCode language: Lisp (lisp)

3.1. Emacs Lisp（1985年〜）

Emacs Lispも、nil と '() は同一オブジェクトです。

Emacs Lispは、GNU Emacsというエコシステムに特化しています。
そのため、仕様の変更を行う動機が乏しく、MacLisp由来の設計がそのまま残っています4

4. Schemeにはnilはない（1975年〜、R5RSで確定）

Lisp 1.5、MacLisp、Common Lisp、Emacs Lisp のように nilが3つの役割を持つ流れ以外にも、Lisp方言は分化しています。

McCarthy論文
└─ Lisp 1.5
   ├─ MacLisp
   │  ├─ Common Lisp
   │  ├─ Emacs Lisp
   │  └─ Clojure
   └─ Scheme系Code language: CSS (css)

もっとも、純粋な言語設計を指向しているのが Scheme です。

Schemeは、MacLispをベースにした小さなインタプリタとして始まりました5が、設計の整理を重ねるうちに nil を分離する方向に進みました。

Schemeでは、偽を表すシンボルは #fで、nilというシンボルは特別扱いされません。

(if #f  "true" "false")  ; => "false"  ← #fだけが偽
(if '() "true" "false")  ; => "true"   ← 空リストは真Code language: Scheme (scheme)

初期のSchemeでは後方互換のために'()が偽であることを許容していましたが、1990年代には「#fだけが偽」と確定しました6
R5RSには「他の方言に慣れた開発者は、Schemeが#f・空リスト・シンボルnilを区別することを知るべきだ」と書かれています。

4.1. 関数が失敗の表現を明示する言語設計

Schemeでは、memberの簡易実装は以下のように、終端条件の書き方が変わります。

;; Scheme
(define (my-member item lst)
  (if (null? lst)
      #f
      (if (equal? (car lst) item)
          lst
          (my-member item (cdr lst)))))Code language: Scheme (scheme)

Schemeでは、(null? lst)を明示し、返り値も#fを明示的に返します。

この違いは「失敗の表現をどこが担うか」という設計哲学の差です。
Common Lispなどでは「nilが偽」という言語仕様が「暗黙の契約」として機能し、関数はnilを返すだけでよいです。
一方、Schemeでは「失敗時は#fを返す」という責任は言語仕様への依存ではなく、関数の契約として明示されます。

4.2. Schemeはなぜ逆方向に進んだか

Schemeの分離はMacLispへの批判から来ています。

nilが「終端・空リスト・偽」の三役を担うとき、コードにはあいまいさがあります。

たとえば、(if some-list ...)というコードは、「リストが存在するか」を問うているのか「リストが空でないか」を問うているのか、文脈なしには判断できません7。

そこで、Schemeは、#fだけを偽とすることで、boolean判定とリスト操作の概念が分離され、コードの意図が述語の名前から読み取れるようになります。
その代わり、MacLispで一行で簡潔に書けたパターンでも、Schemeではnull?やpair?の明示する必要があります。
簡潔さと明示性のどちらを優先するかという判断が、そのまま設計の分岐になりました。

5. Clojureのnilは「参照がない」（2007年〜）

Clojureの nil には、JVMというホスト環境によって独自の位置づけがあります。

nilは偽ですが、空リストは真です。
また、Clojureには、偽を表すfalseも持っています8。

(if false "true" "false"); => "false"  ← falseは偽
(if nil "true" "false")  ; => "false"  ← nilは偽
(if '() "true" "false")  ; => "true"   ← 空リストは真Code language: Clojure (clojure)

nilとfalseが両方とも偽なのは、Javaのboolean型との対称性を保つためです。
JavaのAPIはbooleanを返すメソッドを多く持っていて、その結果をClojureの条件式でそのまま使えるようにするには、falseを偽として扱います。

5.1. ヒープオブジェクトの欠損を表す

Javaには、変数がどのオブジェクトも指していない状態を表す null があります。
これは「参照が存在しない」ことを意味します。

List<Integer> a = null;              // 参照なし
a == null; // trueCode language: Java (java)

Javaでは、変数宣言時にオブジェクトを参照しないことができます。
一方、空のリストはnew ArrayList<>()としてHeap上のオブジェクトとして存在します。
そのため、nullとは別物なのです。

List<Integer> b = new ArrayList<>(); // 空リストのオブジェクトが存在する
b == null; // falseCode language: Java (java)

Clojureで JavaのAPIを呼び出したときに返すnullを Clojureの世界で受け取る値がnilです9。

(.get (java.util.HashMap.) "missing-key")  
; => nil（JavaのnullがClojureのnilになる）Code language: Clojure (clojure)

したがって、Clojureのnilは、Lisp由来の「リスト終端」や「空リスト」ではありません。
「値が存在しない」という欠損値の意味を持ちます。
空リスト'()は nil とは別のオブジェクトとして存在し、関数に渡せる正当なコレクションです。

(nil? nil)   ; => true
(nil? '())   ; => false  ← 空リストはnilではない
(empty? '()) ; => true   ← 空かどうかは別の述語で確認するCode language: Clojure (clojure)

ちなみに、「空リストをnilとして条件判定したい」という場面では、Clojureでは seqを使ってnilに変換するパターンが慣用的に使われます。

(seq '())    ; => nil    ← 空リストをseqに通すとnilが返る（慣用）Code language: Clojure (clojure)

6. まとめ

各方言のnilの扱いを一覧にすると次のようになります。

方言nilと'()は同一空リストの真偽値真になるもの偽になるもの
McCarthyの原論文概念なしなしTのみF
Lisp 1.5（慣習）○偽nil以外すべてnil
MacLisp○偽nil以外すべてnil
Common Lisp○偽nil以外すべてnil
Emacs Lisp○偽nil以外すべてnil
Scheme（R5RS〜）✕真#f以外すべて#fのみ
Clojure✕真nilとfalse以外すべてnilとfalse

McCarthyのNILは終端記号として生まれ、Lisp 1.5の実装の中でFと統合されました。
MacLispがその慣用を洗練させ、Common Lispが仕様として確定させました。
一方、Schemeはその統合を概念をあえて分解し直しました。
また、Clojureはホスト言語であるJavaとの関係で nil には別の役割を与えました。

  1. 原論文はCommunications of the ACM 1960年4月号（Vol.3, No.4, pp.184-195）に掲載されました。McCarthyは論文の中で「このformalismはプログラミング言語としてだけでなく、計算の理論を発展させるための手段としても利点がある」と述べており、実用言語と数学的形式体系の両立を意図して書かれています。 – Recursive Functions of Symbolic Expressions and Their Computation by Machine
  2. carとcdrという名前はIBM 704のハードウェアアーキテクチャに由来します。704の36ビットワードはアドレス部とデクリメント部に分割されており、carは「Contents of the Address part of the Register」、cdrは「Contents of the Decrement part of the Register」の略です。最初の実装者Steve Russellは後に「他の名前を思いつかなかった」と述べており、McCarthyらはfirst/restへの変更を試みましたが定着しなかったと伝えられています。 – The origin of CAR and CDR in LISP
  3. ANSI Common Lisp仕様書HyperSpecでは、generalized booleanを「nilが偽、それ以外のすべての値が真として解釈される値」と定義しています。tは真を表す標準的な値ですが、真として機能するのにtである必要はなく、nilでない任意のオブジェクトが真として評価されます。 – ANSI Common Lisp HyperSpec: Generalized Boolean
  4. Emacs LispはGNU EmacsのオリジナルであるMulitcs EmacsがMacLispで書かれていたことを直接継承しています。Richard StallmanがGNU Emacsを開発する際、MacLispとの互換性を重視した設計を選びました。GNU Emacsリファレンスマニュアルでは「nilは空リストとしても偽としても使えるが、使い分けの慣習として()は空リストを強調したいとき、nilは偽を強調したいときに使う」と記述しています。 – nil and t – GNU Emacs Lisp Reference Manual
  5. Schemeの最初の論文は「Scheme: An Interpreter for Extended Lambda Calculus」（MIT AI Memo No.349, 1975年12月）で、Carl HewittのActorモデルを理解するための実験として書かれました。SussmanとSteeleはその後1980年にかけて「Lambda Papers」と呼ばれる一連のAI Memoを発表し、末尾呼び出し最適化やファーストクラス継続などの概念を確立しました。 – The Lambda Papers
  6. R5RSの正式名称は「Revised⁵ Report on the Algorithmic Language Scheme」で、RnRSシリーズの5番目の改訂にあたります。()と#fの分離がR5RSで確定したことについて、R5RS自体は「他のLisp方言に慣れた開発者はSchemeがNILと空リストと#fを区別することを知るべきだ」と明記しています。 – Revised(5) Scheme – Standard procedures
  7. この設計上の問題はLispコミュニティで長く議論されてきました。Hacker Newsのスレッド「NIL」（2021年）では「nilが複数の役割を担うことはCommon Lispが妥協せざるを得なかった点の一つだ」という意見が挙がっています。 – NIL | Hacker News
  8. ClojureのRich Hickeyはこのnilとfalseだけを偽とする設計について「nilがfalseになる問題を解決することはできなかった」と述べており、JavaのBoolean型との相互運用のためにtrue/falseリテラルも別途用意されています。when-letやif-letなどのマクロは、nilとfalseyを統一的に扱うための慣用的な構文として提供されています。 – Clojure For Java Programmers – talk transcript
  9. Clojureの作者Rich Hickeyは2005年から約2年半をかけてClojureを開発し、2007年10月に公開しました。Hickeyは講演の中で「nilはnothingを意味し、JavaのnullとClojureのnilは同じ値だ。Javaから受け取ったnullはnilと表示される」と明言しています。またnilという語はラテン語の「nihil（無）」の短縮形で、Lisp以前から数学や論理学の文脈で使われていました。 – Rich Hickey – Wikipedia