バロース B5000
バロース B5000は、バロースが1961年にリリースした大型コンピュータの名称。当時バロースは、大型・中型・小型でそれぞれ全く異なるアーキテクチャを採用し、ロバート・S・バートンのコンセプトからそれぞれ命令セットを特定の高水準言語向けに最適化するという戦略をとった。大型システムの設計部門はスタックマシン型命令セットを採用し、命令の密度を高めると共にデータワード長を48ビットとした。B5000は ALGOL 60 向けに最適化されており、単純なコンパイラでコンパイル可能とした。後継にはB5500がある。その後、B6500/B6700 やその後継機がリリースされた。なお、中型システムはCOBOLに最適化されており、小型システムはコントロールストアが書き換え可能で命令セットを置換可能とされた。
1880年代に創業したバロースはコンピュータ業界では最古参だったが、1950年代末の同社の主力製品はまだ電気機械式の会計機 Sensimatic などだった。IBM、NCR、UNIVACといったライバル企業は既に大型コンピュータを生産し始めていた。遅れて参入することになったバロースは、当時の最新のアイデアに基づく全く新たな設計を採用するという戦略をとった。B5000のアーキテクチャは長続きしなかったが、それをベースとしてB6500が生まれている。そのアーキテクチャはユニシスの ClearPath Libra ファミリに受け継がれており、B6700からサポートしているMCPというオペレーティングシステムがほぼそのまま動作している。第三の大型システムであるB8500は商業的には成功しなかった。
B5000
最初のB5000はロバート・S・バートン率いるチームが設計した。先進的なマシンとして知られている。
コンピュータアーキテクトとして知られる John Mashey は最も素晴らしいアーキテクチャの1つに B5000 を挙げ、「私が見た中でも最も革新的なハードウェア/ソフトウェアの結合された例であり、当時としては極めて先進的だった」としている。後継としてB5500やB5700がある。その後、直接の後継は存在しないが、B6500はB5000シリーズから大きな影響を受けている。またオペレーティングシステムの Master Control Program (MCP) がB5000シリーズから移植されている。
斬新なシステム設計
B5000は、ソフトウェアのニーズを考慮してアーキテクチャと命令セットが設計されたという点で、当時としては革新的であった。当時、プロセッサとその命令セットは設計が完了してからソフトウェア開発者に渡されるのが通例であった。
言語サポート
B5000は高級言語をサポートするよう設計された。当時、FORTRANとCOBOLが登場したばかりである。FORTRANもCOBOLもソフトウェア技術から見れば不足である。したがってもっと新しい、まだ試されていないALGOL-60が採用された。正確にはALGOLから派生した言語 Elliott ALGOL が採用された。これはアントニー・ホーアが Elliott 503 というマシン用に開発したものである。ALGOLに現実的な入出力命令を追加したもので、強力な文字列操作機能を持っている。ホーアのチューリング賞受賞講演では、これについて論じている。
ALGOL-60は、FORTRANなど他の言語を設計した経験のある専門家たちが設計した。設計にはバッカス・ナウア記法を用い、非常にきれいな文法を持つ言語となっている。多くの言語の先祖でもあり、Pascal、C言語、Simula、Ada、Eiffelなどがそれにあたる。
B5000はしたがって非常に強力な言語に基づいている。他のベンダーはALGOLコンパイラの実装を試みたが、実装できなかったという。しかし、当時学生だったドナルド・クヌースは、夏休み期間中にバロースの以前のマシン上に ALGOL-58 を実装した。ALGOLなどの高級言語はアセンブリ言語と同等の能力がないと思われがちで、ALGOLのシステム記述言語としての潜在能力に気づいていなかった。この風潮はC言語が開発されるまで続いた。
バロースのALGOLコンパイラは非常に高速であった。エドガー・ダイクストラはパサデナのB5000の工場で自身の書いたプログラムのコンパイルを行い、その高速さに驚き、即座に何台か大学（アイントホーフェン工科大学）に欲しいと言ったとされる。このコンパイラの高速性にはいくつか理由があるが、最も大きな理由はワンパスコンパイラだったためである。初期のコンピュータはメモリ容量が小さく、ソースコードをメモリ上に全て置くのも難しかった。そのためソースコードをメモリ上に保持せず、何度か読み込む必要があった。バロースのALGOLでは、各変数を使用する前に宣言する必要があった。これにより、ソースコードを1度読み込んだだけでコンパイルを完了させることができた。この概念は理論的にも深い意味があるが、同時にそれによってコンパイルが非常に高速化される。パンチカードからソースコードを読み込むと即座にコンパイルでき、バロースのカードリーダーは業界でも最速だった。
COBOLコンパイラもワンパスコンパイラで、同様に高速だった。パンチカード4000枚のCOBOLプログラムを毎秒1000枚のカードを読み込んでコンパイルできた。全ソースコードを読み込むと、即座にコンパイル済みのプログラムを実行可能だった。
B8500
B8500は、B5000をベースとして開発された軍用コンピュータD825から生まれた。
B8500は、1960年代にB5500とD825の設計を統合しようとして設計された。集積回路と磁気薄膜メモリを採用している。ワード長は48ビット、スタックマシンであり、B5500のような識別子を採用しているが、互換性はなかった。またハードウェアの信頼性が低く、完全なシステムが納入されたという実績もなく、1970年以降にプロジェクトが中止となった。
ALGOL
B5000のアーキテクチャはALGOLスタックアーキテクチャである。これ（のメモリレイアウトとプログラムからの使い方）は、PDP-11やMC68000などのリニアなアーキテクチャとも、x86などのセグメント方式のアーキテクチャとも異なる。
ALGOLはシステム記述言語であり、B5000はALGOLを意識して設計された。これが出発点である。他のCOBOLなどの言語もサポートされた。強力な文字列操作命令により、高速なコンパイラの開発が可能となったのである。
B5000上のALGOLは拡張版であり、強力な文字列操作命令を持っているが、ALGOL本来の一部の要素（特に仮引数の型指定が不要という点）が排除されている。また、C言語の #define よりも整然としたDEFINE機構を持っており、プリプロセッサというよりも言語仕様に組み込まれていた。また、EVENT というデータ型が追加されており、プロセス間通信に使われた。また ON FAULT ブロックでプログラムの障害を扱うことができた。
ユーザーレベルのALGOLにはオペレーティングシステム (OS) が必要とするような危険な機能は提供されていない。そのために2つのレベルの言語拡張が用意されている。ESPOLとNEWPはOSおよびOSに密接に関連するソフトウェアの記述用、DCALGOLとDMALGOLはより特殊なシステムソフトウェア用である。
ESPOL と NEWP
本来、B5000のOSであるMCPはALGOLを拡張したESPOL(Executive Systems Programming Oriented Language)という言語で記述されていた。これは70年代後半にNEWPという言語に置き換えられた。NEWPの名称の由来は不明だが、一説にはNo Executive Washroom Privilegesではないかといわれている。NEWPもALGOLの拡張だが、ESPOLよりもセキュリティを強化している。危険のある構文要素はそれを使用するブロックに明示的に使用することを示さない限り使うことができない。これによって複数レベルの保護機構を提供する。
NEWPでは、危険な構文要素を持つプログラムは実行できない。システムのセキュリティ管理者がそのようなプログラムを実行可能に設定することができるが、他のユーザーは（どれだけ特権レベルが高くても）その設定を自分で行うことはできない。NEWPは汎用のプログラミング言語だが、ALGOLの持つ機能全てをサポートしているわけではない。
NEWPにはALGOLにない制御機能もある。例えばINLINEプロシージャがある。いわゆるインライン展開を可能にするもので、論理的にはプロシージャだが実際には呼び出し側のコード内に直に展開されてコンパイルされる。これにより、プログラムの可読性とコードの効率を両立させている。
NEWPには大規模なソフトウェアの開発を可能とする機能がある。具体的にはコードのモジュール性を高める機能で、インタフェース（関数とデータの組）、インタフェースのグループ、モジュール、スーパーモジュールといったものがある。いずれも基本的には関数とデータをまとめるものであり、ある広域データのスコープを限定するものと言える。インタフェースはモジュール間のインポート/エクスポートを可能とする。
DCALGOL とメッセージ制御システム(MCS)
NEWPで書かれたOSとALGOLで書かれたユーザープログラムの中間に位置するものとしてミドルウェアがある。ミドルウェアはDCALGOL (data comms ALGOL) で記述される。これはOSおよびプロセス間のメッセージ交換に使われる。例えばCOMSというミドルウェアはネットワークからメッセージを受け取り、それを特定のプロセスやMCS（メッセージ制御システム）にディスパッチする。
MCSは複数のユーザーセッションを単一のMCSスタックで制御する。負荷バランス制御もMCSレベルで行われる。例えば、ひとつのスタックで30ユーザーまで管理するとした場合、ユーザーセッションが増えたらスタックを増やすことで対応する。このため、B5000では普通ならセッション毎にプロセスを生成するところをひとつのスタックで複数セッションを制御するため、性能的に有利である。MCSは大規模トランザクション処理の根幹も担っている。
MCSは外部コプロセッサ TCP (Terminal Control Processor) とやりとりする。これは24ビットのミニコンピュータで、一般的なレジスタ・アーキテクチャであり、数千の端末を制御する入出力機能を有する。TCPとB6500はメモリ内のメッセージでやりとりし、それは今日のパケットと基本的には同じである。MCSはB6500側でそれらメッセージの処理を受け持っている。TCPにはアセンブラがあるが、そのアセンブラはB6500のALGOLコンパイラに対応していた。TCPの命令ごとに対応するALGOL関数があり、そういった関数を呼び出すと、TCPに対応する命令が発行される。TCPのプログラムは、そういった関数の呼び出しが並んでいるだけのALGOLプログラムであり、アセンブリ言語のプログラムと1対1に対応している。ここではALGOLはマクロアセンブラのように機能する。まず、ALGOLで書かれたTCPプログラムをコンパイルするとB6500上の実行ファイルが生成され、それをB6500上で実行するとTCP用のバイナリがTCPに向かって渡される。
DMALGOL とデータベース
DMALGOL (Data Management ALGOL) は、DMSII データベース向けに拡張されたALGOLである。DMALGOLはDASDLコンパイラで生成されたデータベース記述ファイルからDMSIIデータベースソフトウェアをコンパイルする言語であり、データベースを利用する側は普通のALGOLやCOBOLを使うことができる。DMALGOLの最大の機能は、テーブルやインデックスを操作するコードを生成するプリプロセッシング機構である。
DMALGOLのプリプロセッシングは変数やループを含み、コンパイル時の変数に基づいて名前を生成できる。これによりループのないプリプロセッシングより遥かに調整が容易である。
DMALGOLは DMSII データベースのためのアクセスルーチンを提供するのに使われる。DASDL (Data Access and Structure Definition Language) でデータベースを定義した後、そのスキーマをプリプロセッサで翻訳し、DMALGOLのアクセスルーチンが生成され、それをコンパイルする。したがって、他のDBMS実装とは異なり、実行時のデータベース固有の if/then/else の判断が不要となる。1970年代、この最適化はメモリ使用量と実行時間の削減に大いに威力を発揮した。その後、低レベルなメモリと速度のチューニングがあまり重要ではなくなってきたことと、プリプロセッシングを廃することでコードが単純化されより重要な最適化が可能になることから、このような技法は徐々に廃れた。
後にコンパイラのコードサイズがあまり問題にならなくなってくると、プリプロセッシングの構文要素の多くがユーザーレベルのALGOLの一部に編入された。DMALGOLに残されたのは、ユーザーレベルでは安全でないと考えられる要素と、データベース記述ファイルの直接処理機能だけとなった。
スタックアーキテクチャ
初期のシステムや言語では、小さなルーチンは敬遠された。サブルーチン呼び出しと復帰は時間のかかる処理であり、コールスタックを管理するには多くの命令を実行しなければならなかった。B5000はスタックマシンであり、配列（文字列やオブジェクトを含む）以外のデータは全てスタック上にある。このため、スタック操作は効率を重視して最適化されている。スタック指向マシンであるため、ユーザーがアクセスできるレジスタは存在しない。
マルチタスクもB5000では効率化されている。コンテキストスイッチは MVST (move stack) というひとつの命令で実行できる。各スタックがプロセス（タスクまたはスレッド）に対応しており、各タスクは待っているリソース上でブロックされる。実行されるのを待っているタスクはプロセッサというリソース上でブロックする。MVSTはユーザープログラムからは実行できない。
スタックの速度と性能
スタック・アーキテクチャがレジスタに基づくアーキテクチャよりも遅いと信じる人もいる。性能を向上させるには可能な限りデータをプロセッサの近くに置く必要がある。B5000では、スタックの先頭2ワードをレジスタ（レジスタAとB）にしている。ほとんどの命令はこのスタック先頭2ワードを使って行われる。
性能をさらに向上させるには、スタック上のレジスタ化する部分を増やせばよい。スタックアーキテクチャの利点は、そのような性能向上策を施してもソフトウェアを全く変更する必要がない点である。レジスタをプログラムが意識するアーキテクチャでは、レジスタ数が増えれば再コンパイルなどが必要となる。
また、CPUのシングルチップ化が困難ではないかという指摘もあった。しかし、現にB5000の後継マシンはシングルチップのCPUになっている。
プログラムとスタックのマッピング
プログラムがスタックアーキテクチャにマッピングされる例を以下に示す。
begin
    — ここは語彙レベル2(レベル0はOS用。レベル1はコードセグメント用)
    — レベル2では、広域変数を置く    integer i, j, k
    real f, g
    array a [0:9]
    procedure p (real p1, p2)
         value p1 — p1 は値渡し、p2 は指定されていないので参照渡し    begin
         — 語彙レベル3
         real r1, r2
         r2 := p1 * 5
         p2 := r2 — 'g' の値として r2 の値がセットされる          p1 := r2 — 'p1'の値が r2 となるが、'f' は変化しない                       — 値渡しの引数を更新しているのでエラーとなるべきところである。
                       — 一部のALGOLの後継言語では、このような引数をリードオンリーとして                       — 問題解決しているが、多くの場合そのままとなっている。
         if r2 > 10 then
         begin
              — 変数が定義されているので、ここが語彙レベル4となる              integer n
              — 変数が宣言されているため、このブロックではスタック生成コードが呼ばれる。
                — 通常、このような場所では変数を宣言しない。
              ...   <== 後述のスタックの例はこのあたりを実行している状態である。
         end
    end
    .....
    p (f, g)
end
         
スタックフレームは現に実行中の環境の語彙レベル (lexical level) に対応している。例でわかる通り、語彙レベルとはプログラムの静的な入れ子構造であって、動的な呼び出しの入れ子ではない。ALGOLでは、現在実行中の位置より前に宣言された変数だけが参照可能というのが基本である。また、入れ子の内部で外側と同じ名前の変数を宣言すると、外側の変数を参照できなくなる。
語彙の入れ子は静的なので、5レベル以上の入れ子構造のプログラムは非常に珍しいし、そのようなプログラムは構造化不足と言える。B5000は最大32レベルの入れ子まで可能である。
スタック構造の利点
スタック構造の利点として、プログラムが異常終了するときにスタックのダンプを取れば、状態が完全に把握できるのでプログラマは問題を正確に見つけ出すことができる点が挙げられる。
また、スタックアーキテクチャでは、プログラムは必然的に再帰可能となる。FORTRANは再帰不可能な言語であり、当時の人々がALGOLの実装に苦労した点は「再帰」をどう実装したらよいかという点だった。B5000では問題は全く逆で、再帰しないはずのプログラムを再帰させないようにするにはどうしたらよいかに頭を悩ませた。結局機能を限定することに時間を費やすのは無駄なので、バロースのFORTRANコンパイラは再帰可能なままとなっている。
結果として、バロースのFORTRANの実装は高く評価されている。例えば、サブルーチンや関数呼び出しで引数の個数が合っているかを（ALGOLと同様に）チェックできる。他のシステムではそのような間違いはクラッシュを引き起こした。バロースはオブジェクト指向言語Simulaなど、他の言語の実装でも優れていることで知られていた。APLの設計者ケネス・アイバーソンはバロースのAPL実装が最高であると宣言した。LISPを設計したジョン・マッカーシーは、LISP本来の能力である自己書き換えができないという点でB5000に不満を持っていた。ただし、LISPは多くの場合インタプリタとして動作する。
スタックアーキテクチャであってもプロセスが使用するメモリ量は他のアーキテクチャと同程度である。当時他のシステムでタスクを実行するに当たって必須であったメモリ割り当ての事前設定 (SYSGEN) はB5000では不要である。実際、B5000では新たな周辺機器を追加する場合も再コンパイルなどが不要だった。
B5000の影響
Forth言語の設計者であるチャールズ・ムーアはMITでB5500に触れ、そのスタックアーキテクチャに影響された。Forth - The Early Yearsの中でムーアはForthのDUP, DROP, SWAPといったワードはB5500の命令 (DUPL, DLET, EXCH) に対応していると述べている。
ソビエト連邦のメインフレームおよびスーパーコンピュータ Elbrus シリーズはB5000の影響を受けており、スタックアーキテクチャでタグ付きメモリを採用していた。一種のアセンブリ言語 El-76 を備えていたが、これが実際には ALGOL-60 の修正版であった。なお、その後 Elbrus はEPICアーキテクチャ風のVLIW型CPUに移行している。
ヒューレット・パッカード社にはバロースの元従業員だった技術者がいて、HP 3000 システムはB5000の影響を受けている。ボブ・バートンの逆ポーランド記法 (RPN) に関する業績はHPのプログラム電卓に採用され、例えば HP-35 などが有名である。
タンデムコンピューターズが1970年代末から1980年代初めにかけて設計した NonStop システムは16ビットのスタックマシンであり、HP 3000 の影響を受けているため、間接的にB5000の影響を受けている。1990年ごろMIPSアーキテクチャに移行したが、従来のスタックマシン用バイナリをエミュレーションでサポートし続けた。2000年以降、Itaniumに移行したが、そこでもスタックマシンのエミュレーションを継続サポートしている。
ボブ・バートンはアラン・ケイにも影響を与えた。アラン・ケイは B5000 のデータ駆動型タグ付きアーキテクチャに影響され、オブジェクト指向プログラミングや Smalltalk に関する考察に至った。