【Common Lisp】
なぜ1次元配列を「ベクタ」と呼ぶのか
（ベクトル演算と高階関数）

by
  • Common Lispの「ベクタ」は1次元配列を指し、リストや文字列と同じシーケンス型としてmapやreduceが使えます。
  • Lispの”vector”は、数学的なベクトル概念に由来するが、線形代数の演算子ではなく、高階関数で操作します。
  • 「配列」ではなく「ベクタ」と呼ぶのは、メモリの実装詳細ではなく、型抽象化の考え方があります。

関連記事

1. 配列とベクタ

Common Lispで、C言語のような配列構造を使いたいときに出会うのが「ベクタ（vector）」です。

配列とベクタ C言語の配列 int arr[5] = {10,20,30,40,50}; *(arr + 2) → 30 メモリアドレスの 連続したバイト列 ポインタ算術でアクセス Common Lispのベクタ (make-array 5 :initial-contents ‘(10 20 30 40 50)) (aref v 2) → 30 シーケンス型の一種 map / reduce が使える メモリ詳細に踏み込まない vs 1次元配列 → Cは「配列」、Lispは「ベクタ」と呼ぶ

「ベクタ」は、make-arrayで作る1次元の配列のことで、O(1)で添字アクセスできます1。

(defparameter v
  (make-array 5 :initial-contents '(10 20 30 40 50)))

(aref v 2)    ;=> 30Code language: Lisp (lisp)

ただ、Common Lispでは、「ベクタ」と呼びます。
C言語の「配列」や数学の「ベクトル」とは、違いがあるのでしょうか？

この用語がどこから来たのか、少し掘り下げてみます。

1.1. Cでは「配列」、Lispでは「ベクタ」になった理由

C言語では、配列を「メモリアドレスから連続して並んだバイト列」として扱います。

/* C: メモリとインデックスの計算が直接見える */
int arr[5] = {10, 20, 30, 40, 50};
int x = *(arr + 2);   /* ポインタ算術で要素にアクセス */Code language: Arduino (arduino)

ポインタ算術で要素にアクセスし、実装の詳細が前面に出る言語設計です。

ただ、Lispでは少し発想が違います。
ベクタは、添字アクセスができますが、それだけでなくリストや文字列と並ぶシーケンス型の一種として規格化されています。
map、reduce、findといった関数が同じように使えるのです。

;; Common Lisp: リストでもベクタでも同じ関数が使える
(map 'vector #'(lambda (x) (* x 2)) '(1 2 3 4 5))
;=> #(2 4 6 8 10)

(map 'vector #'(lambda (x) (* x 2)) #(1 2 3 4 5))
;=> #(2 4 6 8 10)

(reduce #'+ #(1 2 3 4 5))
;=> 15

(find 3 #(1 2 3 4 5))
;=> 3Code language: Lisp (lisp)

つまり、ベクタであれば「インデックスを渡すと要素が返る」「長さがわかる」という操作によって定義され、メモリの詳細には踏み込みません。

また、Common Lispでは多次元配列もサポートされています。
つまり、「配列」という語だと多次元も含む概念になるため、1次元に限定したものを区別する必然性がありました2。

この型システム上の位置づけも、「配列」より「ベクタ」という名前を選ぶ動機になっています。

1.2. 「ベクトル」と「ベクタ」

ちなみに、日本語では、数学用語は「ベクトル」、プログラミング用語は「ベクタ」と表記が分かれていますが、これは表記上の問題で、英語ではどちらも同じ “vector” です。

実は、数学の「ベクトル」というのは英語ではなく、ドイツ語の Vektor の読み方に由来します3。
日本の数学教育はかつてドイツ語の影響を強く受けていたため、この読み方が定着したのです。

一方、プログラミング用語は英語からそのまま入ってきたため「ベクタ」と書かれます。

2. vectorという語の来歴 — 数学から始まり、Lispで変質するまで

そもそも “vector” という語はどこからコンピュータ科学に持ち込まれたのか。
その出発点はIversonのAPL、1962年に遡ることができます。

vector という語の来歴 1962 APL（Iverson） スカラー・ベクタ・行列の階層 1970s MacLisp arrayとして登場（非一級型） 1984 Common Lisp vectorをシーケンス型として明文化 1985 Scheme R2RS vectorを標準型として採用 APLのベクトル演算 v × 2 → スカラー倍 +/v → 総和 v +.× v → 内積 Lispの高階関数へ (map …) → 変換 (reduce #’+ v) → 総和 演算を構造から分離

Iversonが著書 “A Programming Language” で確立した体系では、データをスカラー・ベクタ・行列という次元で分類していました4。

数学の線形代数をそのまま引き継いだ用語体系で、1次元配列をvectorと呼び、ベクトル演算も定義されていました。
APLのvectorは、数学のベクトルの同様、スカラー倍や加算、内積が使えます。

⍝ APL: ベクタに対して演算がそのまま適用できる
v ← 1 2 3 4 5        ⍝ ベクタの定義
v × 2                 ⍝ → 2 4 6 8 10  （スカラー倍）
+/ v                  ⍝ → 15          （総和、reduceに相当）
v +.× v               ⍝ → 55          （内積）

一方、Lispの世界では、連結リストが主なデータ構造で、1次元配列が登場したのは1970年代のMacLispにおいてです。
このときはまだ “array” という名前で、一級のデータ型でもありませんでした5。

vectorが登場するのは、1984年です。
DARPAの支援で複数のLisp方言を統一する作業が進み、”Common Lisp the Language” として最初の仕様が公開されました6。
この中で、1次元配列はシーケンス型の一種として “vector” と呼ぶことが明文化されます。

ほぼ同時期に同じ Lisp方言のSchemeでも、R2RS（1985年）からvectorを標準データ型になり、両この用語が定着しました7。

2.1. 演算子と高階関数

Common LispやSchemeの設計に深く関わる Guy Steeleは、APLを本格的に使った経験を持ち8、APLの概念はLisp系言語の設計にも流れ込んでいました。
つまり、APLのスカラー・ベクタ・行列という階層的な名称体系がLispの用語に影響を与えたと考えられます。
ただし、線形代数の演算子そのものは Lisp に持ち込みませんでした。

APLで演算子として組み込まれていたものは、Lispではmapやreduceという汎用の高階関数として提供されました。

APLのv × 2（スカラー倍）は(map 'vector #'(lambda (x) (* x 2)) v)に、
+/v（総和）は(reduce #'+ v)に対応します。

演算子か高階関数かという形は異なりますが、やっていることは似ています。

Lispのベクタは、ベクトル演算の代わりに、「インデックスで要素にアクセスできる順序付きの列」という構造だけを残しました。
これは「汎化」でもあり、演算はmapやreduceとして任意に適用できます。

もちろん、数値計算ライブラリでは、配列に対して線形代数の演算をそのまま適用できます。
その場合は「プログラミングのベクタ」を使って「数学のベクトル」を表現している、という構造になっている、と言えます。

3. 余談 — C++ STLのvectorとの意外なつながり

C言語に話を戻すと、C++には std::vector があります。
動的にサイズが変わる1次元配列です。

// C++: std::vector は動的にサイズが変わる
#include <vector>
#include <numeric>
#include <algorithm>

std::vector<int> v = {1, 2, 3, 4, 5};
v.push_back(6);                            // 末尾に追加
int sum = std::accumulate(v.begin(), v.end(), 0);  // → 21
auto it = std::find(v.begin(), v.end(), 3);        // 検索Code language: C++ (cpp)

C++のvectorは、実はCommon Lispのベクタと系譜がつながっています。

C++ STL vector との意外なつながり Common Lisp シーケンス抽象 map / reduce Scheme vector 標準型（1985） Stepanov ジェネリックプログラミング 静的型付けで再現 C++ STL std::vector （1994提案） （1998標準化） Stepanov「STLのvectorという名前はSchemeとCommon Lispから取った。 このデータ構造はarrayと呼ぶべきだった」 — From Mathematics to Generic Programming (2014)

C++ STLを設計したAlexander Stepanovは、1970年代からジェネリックプログラミングの研究を続けていた人物です。
これは、「型に依存しないアルゴリズムの設計」という考え方です。

その発想の元に一つに、Lispが動的型付けによって自然に持っていた汎用性をどう静的型付け言語で実現するか、という問いでした。
Lispではmapやreduceがリストでもベクタでも文字列でも型を問わず動きます。

Stepanovが挑んだのはその同じ汎用性を、静的型付け言語であるC++で再現することです。
その答えが、C++のテンプレート。
std::findやstd::accumulateがどんな型のコンテナにも適用できるのはそのためです。

つまり、「コンテナとアルゴリズムを分離する」というC++のSTL（標準テンプレートライブラリ）の設計原則は、Lispのシーケンス抽象を静的型付けの制約の中で再発明したものとも言えます9。
STLのvectorは1994年に提案が承認され、1998年のC++98で標準化されました。

ちなみに、”vector” という名前の由来については、Stepanov自身が著書 “From Mathematics to Generic Programming” の中で、面白いことを言っています10Alexander StepanovとDaniel Roseの共著 “From Mathematics to Generic Programming”（2014年、Addison-Wesley）の中でStepanovは「STLのvectorという名前はSchemeとCommon Lispから取った。残念ながらこれは数学における同語のはるかに古い意味と矛盾していた。このデータ構造はarrayと呼ぶべきだった」と述べています。 – Introduction to std::vector and list constructors – learncpp.com[/efn_note**。
「STLのvectorという名前はSchemeとCommon Lispから取った。残念ながらこれは数学における同語のはるかに古い意味と矛盾していた。このデータ構造はarrayと呼ぶべきだった」という内容です。

4. まとめ

「ベクタ」の出発点は数学の線形代数ですが、SchemeとCommon Lispでは、線形代数の演算子は持ち込まれませんでした。

かわりにmapやreduceという汎用の高階関数を用意することで、演算を構造から切り離しました。
これが、「数学のベクトル」ではなく、任意の演算を適用できる「抽象的な列」に一般化しました。

Lispのベクタはもはや数学のベクトルとは別の概念として定着しており、「インデックスでアクセスできる抽象的な列」という意味で、ベクタはベクタとして使えばよいでしょう。

Cでは「配列」、LispやC++では「ベクタ」と呼ぶ。
その違いは、型の抽象化の話なのかもしれません。

  1. make-arrayに整数を一つ渡すと1次元配列、すなわちベクタが生成されます。リストを渡した場合は多次元配列になります。詳細はCommon Lisp HyperSpecのmake-array項を参照してください。 – CLHS: Function MAKE-ARRAY
  2. CLtL（Common Lisp the Language）には「1次元配列はCommon Lispではvectorと呼ばれ、arrayのサブタイプを構成する。vectorとlistはまとめてsequenceとみなされる」と明記されています。 – 2.5.1. Vectors – CLtL
  3. ドイツ語 Vektor はラテン語 vector（運ぶもの）に由来します。日本の近代数学教育はドイツの影響を強く受けており、明治期にドイツ語読みで用語が定着しました。 – APL (programming language) – Wikipedia
  4. Iversonの著書 “A Programming Language”（1962年、John Wiley & Sons）はAPLの源流となった数学的記法を記述したもので、この体系ではスカラー・ベクタ・行列という階層でデータを分類し、1次元配列をvectorと呼んでいます。 – A Programming Language – APL Wiki
  5. WikipediaのMaclisp項には「後から追加されたデータ型として配列があるが、一級のデータ型ではなかった」と明記されています。 – Maclisp – Wikipedia
  6. Common Lispの標準化は1981年4月のDARPA主催の会合をきっかけに始まり、Symbolics、SPICEプロジェクト、NILプロジェクト、S-1 Lispプロジェクトが参加しました。CLtL初版は1984年3月16日にGuy L. Steele Jr.によって出版されています。 – Common Lisp – Wikipedia
  7. SchemeのR2RS（Revised Revised Report on Scheme）は1985年にMITとインディアナ大学で公表され、この時点でvectorが標準データ型として規定されています。 – Scheme has had a standard vector datatype since R2RS (1985) – docs.scheme.org
  8. Peter Seibel著「Coders at Work」所収のGuy Steeleへのインタビューによると、Steeleが真剣に使ったプログラミング言語の一覧にAPLが含まれています。 – Guy Steele – SpringerLink（Coders at Work）
  9. STLの標準化の経緯は、1993年11月にStepanovがANSI/ISO委員会でライブラリを発表し、1994年7月に正式承認されたというものです。HPが同年8月に実装をインターネット上で公開し普及の契機となりました。 – History of the Standard Template Library – Wikipedia