LISPマシン

LISPマシンは、LISPを主要なプログラミング言語として効率的に実行することを目的として設計された高水準言語マシンである。歴史的な意味では、最初の商用シングルユーザーワークステーションだったと言うこともできる。それほど数量的に大成功を収めたとはいえないが（1988年までに約7000台が出荷されたNewquist, Harvey. The Brain Makers, Sams Publishing, 1994. ISBN 0-672-30412-0）、その後よく使われることになる様々な技術を商用化する先駆けとなった。例えば、効率的ガベージコレクション、レーザープリンター、ウィンドウシステム、コンピュータマウス、高解像度ビットマップグラフィックス、などのネットワーキングにおける技術革新などである。1980年代にシンボリックス（3600、3640、XL1200、MacIvoryなど）、LMI（Lisp Machines Incorporated、LMI Lambda）、テキサス・インスツルメンツ（Explorer、MicroExplorer）、ゼロックス（InterLisp-D搭載ワークステーション）といった企業がLISPマシンを製造販売した。オペレーティングシステムは  やInterlisp（ゼロックスの場合）で書かれ、後に一部は Common Lisp で書かれた。

 歴史 
 背景 
1960年代から1970年代にかけて、人工知能プログラムは当時の基準では非常に多くのプロセッサ時間とメモリ空間を消費するものだった。当時の研究機関で使われていたコンピュータは高価であるために多くのユーザーが共有して使用するのが一般的だった。1960年代から1970年代にかけての集積回路技術の進展はコンピュータのサイズとコストを小さくしていったが、AIプログラムが使用するメモリ量は一般的な当時の研究用コンピュータ（DECのPDP-10）のアドレス空間を越えようとしていた。研究者たちは、巨大な人工知能プログラムを開発し動作させるのに最適化した新しいコンピュータを設計することを検討し始め、LISPプログラミング言語の実行に最適化されたマシンを作った。そのオペレーティングシステムを単純にするために、LISPマシンはシングルユーザー用のマシンとなった。

 初期の開発 
1973年、MIT AI研究所のプログラマ、リチャード・グリーンブラットとは MIT LISPマシンプロジェクトを立ち上げた。これは、基本的なLISPの機能がハード的に動作するコンピュータを構築するもので、24ビットのタグ付きアーキテクチャを採用していた。また、このマシンはインクリメンタルなガベージコレクションを採用していた。LISPの変数はコンパイル時ではなく実行時に型付けされるので、普通のハードウェアでは2つの変数の加算に通常の5倍の時間がかかる（型チェックと型ごとの分岐のため）。LISPマシンでは通常の加算命令で型チェックを同時に行う。型チェックが失敗した場合、並行して行っていた加算結果を捨て、再計算する。従って、多くの場合、単純な加算だけで済むので高速化される。このようなチェックを並行して行う手法は、配列の境界チェックなどのメモリ管理関連でも行われている。

Symbolics 3600シリーズでは、32ビットワードを36ビットワードに拡張することで型チェックがさらに強化・自動化された。これは後にさらに40ビットワード以上に強化されている（型チェックが関係しない場合、余分なビットは誤り検出訂正に使われた）。追加ビットの一部はデータ型を保持するのに使われ（タグ付きアーキテクチャ）、その他は（リストに要するメモリを約半分にする方式）の実装やガベージコレクションに使われた。さらなる改善として、2つのマイクロコード命令でLISPの関数呼び出しをサポートし、（一部のシンボリックスの実装では）関数呼び出し当たりのコストを20クロックサイクルに削減している。

最初のマシンは CONS（LISPのリスト作成演算子にちなんだ名称）と呼ばれた。CONSはトム・ナイトが修士論文のテーマとしたことから「ナイト・マシン」とも呼ばれた。その後、さらに改良された CADR（LISPの cadr 関数 = CAR + CDR に由来）と呼ばれるバージョンが完成した。アーキテクチャは基本的には同じである。25台の CADR マシンがMIT内外に約5万ドルで販売された。ハッカーの間で人気となり、すぐさま各種ツールが移植されていった（例えば、Emacs は 1975年に ITS から移植された）。1978年にMITで開催されたAI会議で好評を博し、DARPAはその開発に資金提供を開始した。

 派生 
1979年、（AI研究所の管理者、後にシンボリックス社を創業）はLISPマシンが商業的にも将来性があると確信し、グリーンブラットにその技術の商業化の提案書を書かせた。根っからのハッカーであったグリーンブラットにとって商業化はポリシーに反することではあったが、AI研究所の雰囲気をそのまま持ち込んだような会社が作れるのではないかと考え、反対はしなかった。しかし、ノフツカーの考えはそれとは全く違っていた。両者は長時間にわたって話し合ったが、合意には至らなかった。AI研究所のハッカー達の全面的な支援がなければこの事業が成り立たないのは明らかであったため、ノフツカーを選ぶかグリーンブラットを選ぶかはハッカー達自身に任されることになった。

その後の議論により、研究所は2つの派閥に分裂する事態となった。1979年2月、大多数のハッカーはグリーンブラットの自己満足的な企業よりもノフツカーの考える企業の方が将来性があると判断した。グリーンブラットは負けたのである。

ノフツカーの企業シンボリックス社が徐々に形を成し（彼は給料を払っていたが、作業のための建物も設備も無かった。そのため、ハッカー達がMITでシンボリックスのための作業を続ける代わりに、その成果をMIT内部には無償で提供するという約束をしていた）、グリーンブラットが消沈していたころ、CDCのコンサルタントがグリーンブラットを訪ねてきた。CDC は自然言語処理アプリケーションを西海岸のハッカー達と開発しようとしており、それにグリーンブラットのLISPマシンが使えないかとやってきたのであった。ノフツカーと決着のついた話し合いから8ヶ月後のことであった。グリーンブラットはノフツカーに対抗するLISPマシン企業を始めると決めていたが、具体的には何もしていなかった。そのコンサルタント、アレキサンダー・ジェイコブソンはグリーンブラットが会社を興すのを助けることを決め、経営計画などをまとめた。この新たな企業は LMI（Lisp Machine, Inc.）と名づけられ、ジェイコブソン経由で CDC の資本で設立された。

このころ、シンボリックス社が事業を開始した。ノフツカーがグリーンブラットに対して一年間の猶予を与えると約束したことと、ベンチャーキャピタルからの資金集めが難航したための遅れであった。しかし、AI研究所のハッカー達のうち3、4人はグリーンブラットについたものの、他の14人のハッカーがシンボリックスで働くことになったことで、シンボリックスにとっては有利となった。ただし、リチャード・ストールマンとマービン・ミンスキーの2人はどちらにも与しなかった。ただし、ストールマンはAI研究所を中心としたハッカー文化を衰退させたとしてシンボリックスを非難している。1982年から1983年末までの2年間、ストールマンはシンボリックスのプログラマ達の成果のクローンを作る作業を行い、研究所のコンピュータ群においてシンボリックスが独占状態となるのを防ごうとしたLevy,S: Hackers. Penguin USA, 1984。

シンボリックスは1980年から1981年にかけて CADR を LM-2 として販売開始し、LMI も LMI-CADR として販売開始した。シンボリックスは新たに開発していた3600ファミリをなるべく早く出荷し、LM-2 の販売を早々にやめる予定だったが、3600の開発は遅れに遅れ、結局7万ドルの LM-2 は約100台出荷された。両社は CADR ベースの第二世代の製品 Symbolics 3600 と LMI-LAMBDA を開発した。約1年後にリリースされた 3600 は、CADR のワード長を 36ビットに拡張して、アドレス空間を 28ビットとしMoon 1985、CADR ではマイクロコードで実装されていた機能の一部をハードウェアで実装し高速化したものであった。さらにその1年後（1983年）に登場した LMI-LAMBDA はマイクロコードレベルで CADR と互換性があるが、ハードウェアには差異がある。テキサス・インスツルメンツ(TI)社は、LMI-LAMBDA のライセンス供与を受け、互換マシン TI Explorer を開発した。LMI-LAMBDA と TI Explorer の一部はLISPマシンとUNIXマシンを1つにまとめたデュアルシステムとなっていた。TIはExplorer用にLISPマシンCPUの32ビットマイクロプロセッサも開発した。このチップはAppleの Macintosh II に接続できるNuBusボード型の MicroExplorer にも使われた。

シンボリックス社は 3600 ファミリとそのオペレーティングシステム Genera を開発し続け、シンボリックスのCPUをワンチップ化した Ivory も開発した。1987年には Ivory を使ったいくつかのマシンも開発された。例えば、SunのワークステーションやMac向けの拡張ボード、スタンドアロンのワークステーション、そして組み込みシステムなどにまで利用された。LMI社は CADR アーキテクチャをやめて新たに K-Machine を開発したが、リリースする前に倒産した。倒産直前のLMIでは、巨大仮想空間を複数マシン間で共有する分散システムを検討していたMoby space Patent application 4779191。

これらのマシンは様々な、コンパイルされたLISPプログラムに必要なプリミティブ的な操作をハードウェアでサポートしており、データ型チェック、CDRコーディング（リスト型のデータ構造を配列的に詰めたもの）、並列and・or並行ガベージコレクションのハードウェアサポートなどがある。これにより、大きなLISPプログラムを非常に効率的に動作させることができた。シンボリックス社のマシンは商用のスーパーミニコンピュータ（VAXなど）と競合したが、人工知能研究以外の用途に使われることはほとんどなかった。一部の例外的な用途として、シンボリックスのLISPマシンはコンピュータグラフィックスのモデリングやアニメーションにおけるアルゴリズム研究に用いられた例もある。

MITから派生したLISPマシンは、MITのMacLispを先祖とする  という方言を主要言語としていた。オペレーティングシステムもLISPで書かれていて、オブジェクト指向による拡張(Flavors)も使われていた。後にLISPマシンは Common Lisp もサポートするようになった。

 ゼロックスのLISPマシン 
BBNは、独自のLISPマシン Jericho を開発した。InterLispが動作するマシンであったが、市場には出されなかった。それに失望したAIグループのメンバーは同社を辞め、その多くがゼロックスのパロアルト研究所に雇われることになった。従って、ゼロックス社のパロアルト研究所が開発した Interlisp（後にCommon Lispも稼動）やSmalltalkのような言語が動作するよう設計されたマシンは、グリーンブラットらのMITでの開発とは独立している。しかし、ゼロックスは市場参入の時期を誤り、LMI やシンボリックスの後塵を拝することになった。Xerox 1100（ドルフィン）、Xerox 1132（ドラド）、Xerox 1108（ダンデライオン）、Xerox 1109（ダンデタイガー）、Xerox 6085（デイブレイク）などの機種がある。ゼロックスのLISPマシンのオペレーティングシステムは仮想マシンに移植され、Medleyという名前でいくつかのプラットフォーム上で動作した。ゼロックスのLISPマシンは先進的な開発環境で知られており、Altoから受け継がれたGUIとNoteCards（初期のハイパーテキストアプリケーション）などが有名である。ゼロックスのマシンは商業的には失敗だったが、そのグラフィカルユーザー環境や一部の概念は後にアップルのMacintosh等さまざまなコンピュータに間接的に影響を与えた。

ゼロックスはRISCベースのLISPマシン Xerox Common Lisp Processor を試作し、1987年に市販することを計画していたが、実現しなかった。

 Integrated Inference Machines 
1980年代中ごろ、Integrated Inference Machines (IIM) がLISPマシンの試作機 Inferstar を開発している。

 アメリカ以外でのLISPマシン開発 
1984年から1985年にかけて、イギリスの Racal-Norsk はノルウェーの Norsk Data のミニコンのマイクロプログラムをLISPマシン化して CADR 用のソフトウェア Knowledge Processing System (KPS) を動作させることを試みている。

フランスでは2つのLISPマシン・プロジェクト、M3LとMAIAが実施されている。

ドイツではシーメンスがRISCベースのLISP用コプロセッサCOLIBRIを開発しているMüller-Schloer “Bewertung der RISC-Methodik am Beispiel COLIBRI”, “RISC-Architekturen”, Editor A. Bode, BI-Verlag, 1988Christian Hafer, Josef Plankl, F. J. Schmitt., COLIBRI: Ein RISC-LISP-System, Architektur von Rechensystemen, Tagungsband, 11. ITG/GI-Fachtagung, 7.-9. März 1990, München, Germany 1990。

 日本でのLISPマシン開発 
日本では、1979年に完動した神戸大のTAKITAC-7（FAST LISP）をはじめ、理化学研究所のFLATS、大阪大学のELVISなどが試作された。富士通のFACOM α（メインフレームのバックエンドとして動作。1984年発表）、NTT電気通信研究所のELIS（TAO/ELIS）、東芝のAIプロセッサ(AIP)、日本電気のLIMEのようにLISPマシン市場への参入を試みた例もある。青山学院大学で開発されたALPS/1は、8080の特定の命令実行を横取りし、ハードウェアでデータを処理させる、という仕組みであった。

情報処理学会のコンピュータ博物館サイトの「神戸大LISPマシン」の解説https://museum.ipsj.or.jp/computer/other/0001.htmlの最後に「TAKITAC-7のアーキテクチャは後のFACOM-αとNTTのELISが継承した．」とあるが、いずれもそのまま引き継いでいるわけではない。FACOM αは同社のメインフレームないしミニコンのバックエンドとして動作するものである。またELISについては関係者が執筆した記事によれば、設計者は（神戸大LISPマシンを）32ビットにしただけと言ったりもするが、VLSIチップにすることを前提にそれに適したアーキテクチャとして設計されており竹内郁雄の執筆記事「マルチパラダイム言語TAO 第1回 LispマシンELIS」（ https://www.nue.org/nue/tao/bitao/s001.html ）による、そういった点は独自性が強い。

 その後・現在 
RISCワークステーションの性能対価格比の向上により、これらLISPマシンの優位は消え失せ、ミニコンピュータなどともろともに、高水準言語寄りのアーキテクチャは基本的には「過去の遺物」とみなされるようになった。ワークステーションの後にはパーソナルコンピュータが続き、ワークステーションのメーカーも一掃された。現代では、一般のデスクトップPCが特別なハードウェア無しでLISPマシンの何倍も高速にLISPを実行できるようになった。

1990年代初めにはLISPマシンを製造していた企業は商売が成り立たなくなった。ゼロックス以外ではシンボリックスが今も残っている唯一の企業で、LISPマシン環境 Open Genera と 数式処理システム Macsyma を販売している。

各種LISPマシンのオープンソースのエミュレータを作る試みがいくつかなされている。
 CADRのエミュレーション
 シンボリックスのLISPマシンのエミュレーション
 E3プロジェクト（TI Explorer II のエミュレーション）
 Meroko（TI Explorer I のエミュレーション）
 Nevermore（TI Explorer I のエミュレーション）

2005年10月3日、MITはCADRのソースコードをオープンソースとして公開した。

BitsaversのPDF文書アーカイブには、シンボリックスのLISPマシン、TI ExplorerとMicroExplorer、ゼロックスのInterLisp-Dマシンについて、各種文書のPDF版が保管されている。

 その他の高水準言語マシン 
日本の第五世代コンピュータ計画では、LISPよりもさらに高水準の、論理推論の操作をハードウェア化し、Prologなどの論理プログラミング言語の高速処理を目的としたマシン（逐次推論型マシン PSI、並列推論型マシン PIM）が開発された。また、Prologをより直接的に実装することを意図したプロセッサやコプロセッサが1980年代後半から1990年代前半にかけていくつか開発されている。例えばカリフォルニア大学バークレー校の VLSI-PLM、その後継のPLUM、関連するマイクロコード実装などがある。設計レベルに留まり、実際にハードウェアが製作されなかった例もいくつかある。LISPと同様、Prologの基本計算モデルは標準的な命令型設計とは大きく異なるため、計算機科学者や電気工学者は根底にある計算モデルのエミュレートによって生じるボトルネックをなんとか解消しようとしてきた。

ニクラウス・ヴィルトのLilithプロジェクトでは、Modula-2言語を指向した独自CPUを採用している。

近年の例には、1990年代終盤に最初に構想されたサン・マイクロシステムズによるものを代表とする、Javaに最適化されたJavaプロセッサ（:en:Java processor）がある。

エリクソンはErlangに最適化したプロセッサ ECOMP を開発したがhttp://www.erlang.se/euc/00/processor.ppt、製品化はしていない。

 用途 
LISPマシンは主に人工知能アプリケーションの領域で使われたが、コンピュータグラフィックス、医用画像処理などの分野でも使われた。

1980年代の主要な商用エキスパートシステムはLISPマシンに移植されている。インテリコープの Knowledge Engineering Environment (KEE)、The Carnegie Group Inc. の Knowledge Craft、Inference Corporation の ART (Automated Reasoning Tool) などであるRichter,Mark: AI Tools and Techniques. Ablex Publishing Corporation USA, 1988, Chapter 3, An Evaluation of Expert System Development Tools。

 技術概要 
もともとLISPマシンはLISPによるソフトウェア開発のための個人用ワークステーションとして設計された。1人の人間が使用するようになっていて、マルチユーザーモードはない。大きなモノクロのビットマップディスプレイ、キーボード、マウス、ネットワークアダプター、ハードディスク、1MB以上のRAM、シリアルインタフェース、拡張カードスロットなどを備えている。カラーグラフィックス、磁気テープ装置、レーザープリンターなどはオプションである。

プロセッサはLISPを直接実行するわけではなく、コンパイルされたLISPに最適化された命令セットを持つスタックマシンになっている。初期のLISPマシンはマイクロコードで命令セットを実装していた。いくつかの演算で、型チェックとディスパッチがハードウェアで実行時に行われる。例えば、加算命令は1つだけで、各種数値型（整数、浮動小数点数、有理数、複素数）の加算を自動的に行う。そのため、LISPコードをコンパイルしたものは非常にコンパクトになる。

次の例はリスト (list) の要素それぞれに対して述語 (predicate) を作用させ、「真」を返す要素数を数える関数である。

(defun example-count (predicate list)
  (let ((count 0))
    (dolist (i list count)
      (when (funcall predicate i)
        (incf count)))))

この関数を（シンボリックスの Ivory マイクロプロセッサ向けに）コンパイルした機械語コードを逆アセンブルしたものを以下に示す。

Command: (disassemble (compile #'example-count))

  0  ENTRY: 2 REQUIRED, 0 OPTIONAL      ;Creating PREDICATE and LIST
  2  PUSH 0                             ;Creating COUNT
  3  PUSH FP|3                          ;LIST 
  4  PUSH NIL                           ;Creating I
  5  BRANCH 15
  6  SET-TO-CDR-PUSH-CAR FP|5
  7  SET-SP-TO-ADDRESS-SAVE-TOS SP|-1
 10  START-CALL FP|2                    ;PREDICATE 
 11  PUSH FP|6                          ;I 
 12  FINISH-CALL-1-VALUE
 13  BRANCH-FALSE 15
 14  INCREMENT FP|4                     ;COUNT 
 15  ENDP FP|5
 16  BRANCH-FALSE 6
 17  SET-SP-TO-ADDRESS SP|-2
 20  RETURN-SINGLE-STACK

オペレーティングシステムは仮想記憶によって大きなアドレス空間を提供している。OSのメモリ管理機能の一部としてガベージコレクションも行う。全てのコードは単一のアドレス空間を共有している。メモリに格納されているあらゆるデータオブジェクトにはタグが付属しており、実行時にデータ型を判別できる。単一アドレス空間内に複数の実行スレッドがあり、それらを「プロセス」と呼ぶ。

全OSソフトウェアはLISPで書かれている。ゼロックスはInterLisp、シンボリックスとLMIとTIはMaclispから派生した Lisp Machine Lisp を使っている。Common Lisp が登場するとLISPマシンでも Common Lisp をサポートするようになり、Common Lisp でソフトウェアが書かれるようになった。

後期のLISPマシン（TI MicroExplorer、Symbolics MacIvory、Symbolics UX400/1200 など）はワークステーションとしてではなく、何らかのホストコンピュータ（Macintosh II や Sun-3/4 など）に組み込むカードの形で製品化された。

Symbolics XL1200 などのLISPマシンは特別なグラフィックスカードを備え、グラフィックス機能が強化されていた。そのようなLISPマシンは医用画像処理、3次元アニメーション、CAD などに使われた。

 脚注 

 参考文献 
 "LISP Machine Progress Report", Alan Bawden, Richard Greenblatt, Jack Holloway, Thomas Knight, David Moon, Daniel Weinreb, AI Lab memos, AI-444, 1977.
 "CADR", Thomas Knight, David A. Moon, Jack Holloway, Guy L. Steele. AI Lab memos, AIM-528, 1979.
 "Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode", Guy Lewis Steele, Jr., Gerald Jay Sussman, AI Lab memo, AIM-514, 1979
 David A. Moon. Chaosnet. A.I. Memo 628, Massachusetts Institute of Technology Artificial Intelligence Laboratory, June 1981.
 "Implementation of a List Processing Machine". Tom Knight, Master's thesis. 
 Lisp Machine manual, 6th ed. Richard Stallman, Daniel Weinreb, David Moon. 1984.
 "Anatomy of a LISP Machine", Paul Graham, AI Expert, December 1988
 Free as in Freedom: Richard Stallman's Crusade for Free Software

 外部リンク 
 Symbolics
 Medley
 Bitsavers にある PDF 文書群
 LMI documentation
 MIT CONS documentation
 MIT CADR documentation
 Symbolics documentation
 TI MicroExplorer documentation
 TI Explorer documentation
 Xerox Interlisp documentation
 Lisp Machine マニュアルなど
 "The Lisp Machine manual, 4th Edition, July 1981"
 "The Lisp Machine manual, 6th Edition, HTML/XSL version"
 "The Lisp Machine manual"
 "Lisp Machine Inc. K-machine: The Deffenbaugh, Marshall, Powell, Willison architecture as remembered by Joe Marshall"
 "My Lisp Experiences and the Development of GNU Emacs" - リチャード・ストールマンによる GNU Emacs、LISP、LISPマシン に関する講演を書き起こしたもの
 CADR simulation
 L-machine simulation
 CADR LISP Machine source code released by MIT (Oct 3 2005)
 "A Few Things I Know About LISP Machines" 
 LISPMACHINE.NET - Lisp Books and Information
 Lisp machines timeline LISPマシンの年表
 Zeta-C

  "Présentation Générale du projet M3L" - フランスでの同様のプロジェクト

Category:人工知能
Category:コンピュータアーキテクチャ
Category:ミニコンピュータ
Category:ワークステーション
ましん