LISPマシン

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

歴史[編集]

背景[編集]

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

初期の開発[編集]

MITに展示されている初期のLISPマシン

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

Symbolics 3600シリーズでは、32ビットワードを36ビットワードに拡張することで型チェックがさらに強化・自動化された[2]。これは後にさらに40ビットワード以上に強化されている(型チェックが関係しない場合、余分なビットは誤り検出訂正に使われた)。追加ビットの一部はデータ型を保持するのに使われ(タグ付きアーキテクチャ)、その他はCDRコーディング英語版(リストに要するメモリを約半分にする方式)の実装やガベージコレクションに使われた。さらなる改善として、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年間、ストールマンはシンボリックスのプログラマ達の成果のクローンを作る作業を行い、研究所のコンピュータ群においてシンボリックスが独占状態となるのを防ごうとした[3]

シンボリックスは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ビットとし[4]、CADR ではマイクロコードで実装されていた機能の一部をハードウェアで実装し高速化したものであった。さらにその1年後(1983年)に登場した LMI-LAMBDA はマイクロコードレベルで CADR と互換性があるが、ハードウェアには差異がある。テキサス・インスツルメンツ(TI)社は、LMI-LAMBDA のライセンス供与を受け、互換マシン TI Explorer を開発した。LMI-LAMBDA と TI Explorer の一部はLISPマシンとUNIXマシンを1つにまとめたデュアルシステムとなっていた。TIはExplorer用にLISPマシンCPUの32ビットマイクロプロセッサも開発した。このチップはアップルの Macintosh II に接続できるNuBusボード型の MicroExplorer にも使われた。

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

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

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

ゼロックスのLISPマシン[編集]

BBNは、独自のLISPマシン Jericho を開発した[7]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年に市販することを計画していたが[8]、実現しなかった。

Integrated Inference Machines[編集]

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

アメリカ以外でのLISPマシン開発[編集]

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

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

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

ドイツではシーメンスがRISCベースのLISP用コプロセッサCOLIBRIを開発している[21][22]

その後・現在[編集]

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

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

各種LISPマシンのオープンソースのエミュレータを作る試みがいくつかなされている。

  • CADRのエミュレーション[23]
  • シンボリックスのLISPマシンのエミュレーション[24]
  • E3プロジェクト(TI Explorer II のエミュレーション)[25]
  • Meroko(TI Explorer I のエミュレーション)[26]
  • Nevermore(TI Explorer I のエミュレーション)[27]

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

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

その他の高水準言語マシン[編集]

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

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

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

エリクソンErlangに最適化したプロセッサ ECOMP を開発したが[40]、製品化はしていない。

用途[編集]

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

1980年代の主要な商用エキスパートシステムはLISPマシンに移植されている。インテリコープの Knowledge Engineering Environment (KEE)、The Carnegie Group Inc. の Knowledge Craft、Inference Corporation の ART (Automated Reasoning Tool) などである[41]

技術概要[編集]

もともと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 などに使われた。

脚注[編集]

  1. ^ Newquist, Harvey. The Brain Makers, Sams Publishing, 1994. ISBN 0-672-30412-0
  2. ^ "Architecture of the Symbolics 3600", David A. Moon”. Portal.acm.org. doi:10.1145/327070.327133. 2011年11月12日閲覧。
  3. ^ Levy,S: Hackers. Penguin USA, 1984
  4. ^ Moon 1985
  5. ^ Lisp Machine Inc. K-machine, http://fare.tunes.org/tmp/emergent/kmachine.htm 
  6. ^ Moby space Patent application 4779191
  7. ^ http://www.aaai.org/ojs/index.php/aimagazine/article/download/94/93+(1981).+“Computing Facilities for AI: A Survey of Present and Near-Future Options”. AI Magazine 2 (1). 
  8. ^ a b “The AAAI-86 Conference Exhibits: New Directions for Commercial AI, VLSI Lisp Machine Implementations Are Coming”. AI Magazine 8 (1). (1987). http://www.aaai.org/ojs/index.php/aimagazine/article/view/574/510. 
  9. ^ Computer Algebra in Norway, Racal-Norsk KPS-5 and KPS-10 Multi-User Lisp Machines”. Springerlink.com. 2011年11月12日閲覧。
  10. ^ 【神戸大学】 神戸大LISPマシン”. 情報処理学会コンピュータ博物館. 2012年4月23日閲覧。
  11. ^ 【理化学研究所】 数式処理計算機FLATS”. 情報処理学会コンピュータ博物館. 2012年4月23日閲覧。
  12. ^ 【大阪大学】 EVLISマシン”. 情報処理学会コンピュータ博物館. 2012年4月23日閲覧。
  13. ^ 【富士通】 FACOM α”. 情報処理学会コンピュータ博物館. 2012年4月23日閲覧。
  14. ^ 竹内郁雄. “マルチパラダイム言語 TAO”. 2012年4月23日閲覧。
  15. ^ 【電電公社】 通研ELIS”. 情報処理学会コンピュータ博物館. 2012年4月23日閲覧。
  16. ^ A 32-bit LISP Processor for the Al Workstation ELIS with a Multiple Programming Paradigm Language, TAO”. Ci.nii.ac.jp (1990年8月25日). 2011年11月12日閲覧。
  17. ^ Architecture of an AI Processor Chip (IP1704)”. Ci.nii.ac.jp (1990年8月25日). 2011年11月12日閲覧。
  18. ^ 【日本電気】 LispマシンLIME”. 情報処理学会コンピュータ博物館. 2012年4月23日閲覧。
  19. ^ M3L, A Lisp-machine”. Limsi.fr. 2011年11月12日閲覧。
  20. ^ MAIA, Machine for Artificial Intelligence”. Limsi.fr. 2011年11月12日閲覧。
  21. ^ Müller-Schloer ”Bewertung der RISC-Methodik am Beispiel COLIBRI”, ”RISC-Architekturen”, Editor A. Bode, BI-Verlag, 1988
  22. ^ Christian 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
  23. ^ CADR Emulation”. Unlambda.com. 2011年11月12日閲覧。
  24. ^ Symbolics L Lisp Machine Emulation”. Unlambda.com (2004年5月28日). 2011年11月12日閲覧。
  25. ^ The E3 Project, TI Explorer II emulation”. Unlambda.com. 2011年11月12日閲覧。
  26. ^ Meroko Emulator (TI Explorer I)”. Unlambda.com. 2011年11月12日閲覧。
  27. ^ Nevermore Emulator (TI Explorer I)”. Unlambda.com. 2011年11月12日閲覧。
  28. ^ MIT CADR Lisp Machine Source code”. Heeltoe.com. 2011年11月12日閲覧。
  29. ^ Bitsavers' PDF Document Archive”. Bitsavers.org. 2011年11月12日閲覧。
  30. ^ Symbolics documentation”. Bitsavers.org. 2011年11月12日閲覧。
  31. ^ TI Explorer documentation”. Bitsavers.org (2003年5月15日). 2011年11月12日閲覧。
  32. ^ TI MicroExplorer documentation”. Bitsavers.org (2003年9月9日). 2011年11月12日閲覧。
  33. ^ Xerox Interlisp documentation”. Bitsavers.org (2004年3月24日). 2011年11月12日閲覧。
  34. ^ A Detailed Description of the VLSI-PLM Instruction Set: A WAM Based Processor for Prolog”. 2012年4月24日閲覧。
  35. ^ A high performance Prolog processor with multiple function units”. 2012年4月24日閲覧。
  36. ^ Implementing Prolog via Microprogramming a General Purpose Host Computer”. 2012年4月24日閲覧。
  37. ^ A VHDL-based methodology for designing a Prolog processor”. 2012年4月24日閲覧。
  38. ^ A Prolog coprocessor for superconductors”. 2012年4月24日閲覧。
  39. ^ Pascal for Small Machines – History of Lilith”. Pascal.hansotten.com (2010年9月28日). 2011年11月12日閲覧。
  40. ^ http://www.erlang.se/euc/00/processor.ppt
  41. ^ Richter,Mark: AI Tools and Techniques. Ablex Publishing Corporation USA, 1988, Chapter 3, An Evaluation of Expert System Development Tools

参考文献[編集]

外部リンク[編集]