エクセル

XPL（エキスパートプログラミング言語^[1]）は、 PL/Iをベースにしたプログラミング言語で、独自の言語で書かれたポータブルなワンパスコンパイラと、他の言語用の同様のコンパイラを簡単に実装するためのパーサージェネレータツールです。XPLは、コンパイラ設計の原則を教え、学生が独自の言語用のコンパイラを構築するための出発点として、1967年に設計されました。

XPLは、スタンフォード大学のウィリアム・M・マッキーマン、^{[2] [3]}デビッド・B・ワートマン、ジェームズ・J・ホーニングらによって設計・実装されました。XPLは、1968年秋の合同コンピュータ会議で初めて発表されました。その手法とコンパイラについては、1971年の教科書「A Compiler Generator」で詳しく説明されています。

彼らは、この統合作業を「コンパイラ ジェネレータ」と呼びました。しかし、これは、新しい言語や新しいターゲット用のコンパイラを作成するために、言語やターゲット固有のプログラミングがほとんどまたはまったく必要ないことを意味します。XPL のより適切な呼び方は、トランスレータライティング システムです。これは、新しいプログラミング コードや変更されたプログラミング コードを少なくしてコンパイラを作成するのに役立ちます。

XPL 言語は、 PL/Iのシンプルで小型で効率的な方言であり、主にコンパイラの作成を目的としています。XPL 言語は、使用可能になると他の目的にも使用されました。XPL は、シンプルなコンパイラによって、ほとんどの最新マシンに簡単にコンパイルできます。コンパイラの内部は XPL で簡単に記述でき、コードは読みやすいです。PL/I 言語は、Fortran、COBOL、およびALGOLに代わる包括的な言語として、1964 年にIBM の委員会によって設計され、すべての顧客および社内のニーズを満たします。これらの野心的な目標により、PL/I は複雑になり、効率的に実装するのが難しくなり、使用時に驚くような結果になることもあり得ました。XPL は、完全な言語の小型の方言です。XPL には、PL/I にはない 1 つの追加機能があります。動的な長さを持つSTRINGデータ型です。文字列値は、古い値の自動ガベージ コレクションを備えた、テキストのみの別のヒープメモリ領域に存在します。シンプルなコンパイラが行うことの多くは、入力テキストと出力バイト ストリームを操作することなので、この機能は XPL ベースのコンパイラを簡素化するのに役立ちます。

XPL コンパイラはXCOMと呼ばれ、テーブル駆動型パーサーとシンプルなコード生成技術を使用するワンパス コンパイラです。XCOM にはさまざまなマシン アーキテクチャ用のバージョンがあり、それぞれのターゲット用に異なる手書きのコード生成モジュールを使用しています。元のターゲットはIBM System/360で、これはIBM System/370、IBM System/390、およびIBM System zの適切なサブセットです。

XCOM は XPL ソース コードからコンパイルしますが、XCOM 自体は XPL で記述されているため、それ自体をコンパイルできます。つまり、他のコンパイラに依存しない自己コンパイル コンパイラです。自己コンパイル コンパイラを持つ有名な言語はいくつかあり、 Burroughs B5000 Algol、PL/I、C、LISP、Javaなどがあります。このようなコンパイラの作成は、鶏が先か卵が先かという難問です。言語は、最初に他の言語で記述された一時コンパイラ、またはインタープリタ (多くの場合、BCPL がintcode またはO-codeで実行できるように、中間コード用のインタープリタ) によって実装されます。

XCOM は、Burroughs マシンで実行される Algol プログラムとして始まり、XPL ソース コードを System/360 マシン コードに変換しました。XPL チームは、Algol ソース コードを手動で XPL ソース コードに変換しました。その後、XCOM の XPL バージョンは Burroughs でコンパイルされ、System/360 マシン用の自己コンパイル型 XCOM が作成されました。その後、Algol バージョンは破棄され、それ以降のすべての改善は XPL バージョンでのみ行われました。これは、コンパイラのブートストラップと呼ばれます。XPL の作者は、ブートストラップ プロセスを文書化するために、トゥームストーン ダイアグラムまたは T ダイアグラムを考案しました。

新しいマシン アーキテクチャ用にコンパイラを再ターゲットする場合も同様の作業ですが、コード生成モジュールのみを変更する必要があります。

XCOM はワンパス コンパイラです (ただし、前方分岐、ループ、その他の定義された状況に対しては、出力されたコード修正プロセスがあります)。XCOM は、プロシージャ全体またはプログラム全体を解析するまで待つのではなく、ステートメント内の各文法規則が認識されるたびに、各ステートメントのマシン コードを生成します。解析ツリーやその他の必要な中間プログラム形式はなく、ループ全体またはプロシージャ全体の最適化もありません。ただし、XCOM はピープホール最適化を実行します。各文法規則に対するコード生成応答は、その規則に関連付けられます。この即時アプローチは、非効率的なコードとマシン レジスタの非効率的な使用につながる可能性があります。これは、実装の効率、つまり前述の動的文字列の使用によって相殺されます。コンパイル中にテキストを処理する際に、部分文字列操作が頻繁に実行されます。これらは、整数への代入と同じくらい高速で、実際の部分文字列は移動されません。つまり、XCOM は迅速で、短いコースで簡単に教えることができ、適度なサイズのメモリに収まり、異なる言語または異なるターゲット マシンに合わせて簡単に変更できます。

XCOM コンパイラには、手書きの語彙スキャナと機械的に生成されたパーサがあります。コンパイラの入力言語 (この場合は XPL) の構文は、簡略化されたBNF 文法で記述されます。XPL の文法解析ツールANALYZERまたはXA は、これを、構文規則のすべての正当な組み合わせとその識別方法を記述した大規模なデータ テーブルのセットに変換します。このテーブル生成ステップは、言語が変更された場合にのみ再実行されます。コンパイラが実行されると、これらのデータ テーブルは、言語に依存しない小さな解析アルゴリズムによって使用され、入力言語を解析して応答します。このスタイルのテーブル駆動型パーサは、一般に、完全に手書きの再帰降下パーサよりも簡単に記述できます。XCOM はボトムアップ解析方式を使用します。この方式では、コンパイラは、どの構文規則に遭遇したかの判断を、そのフレーズの右端を確認するまで遅らせることができます。これは、トップダウン方式よりも広範囲のプログラミング言語を処理します。トップダウン方式では、コンパイラはフレーズの左端しか見ていないときに、特定の構文規則を早期に推測またはコミットする必要があります。

XPL には、XPL 文字列値の割り当てとガベージ コレクションを行うための最小限のランタイム サポート ライブラリが含まれています。このライブラリのソース コードは、XPL で記述されたほとんどすべてのプログラムに含める必要があります。

XPL コンパイラ記述システムの最後の部分は、SKELETONというサンプル コンパイラです。これは、XPL の完全な文法ではなく、サンプルのおもちゃの文法の解析テーブルを備えた XCOM です。これは、新しい言語が XPL と大きく異なる場合に、その言語用のコンパイラを構築するための出発点となります。

XPL はモニターXMONの制御下で実行されます。XMONは、このシステムの唯一のオペレーティングシステム固有の部分であり、XCOM 自体または XCOM を使用して開発されたプログラムの「ローダー」として機能し、XCOM が使用するための 3 つの補助記憶装置も提供し、ブロック番号によって直接アクセスされます。最初に公開された XMON は、IBM 2311用に最適化されていました。XMON パラメーター FILE= により、モニターはブロック サイズが大きい他のディスクを効率的に使用できるようになりました。^[4] 作業ディスクのブロック サイズは、XCOM のコンパイル時定数でもありました。^[5]

XMON はディスク直接アクセスに非常に単純な戦略を採用していました。NOTE はディスク トラックのアドレスを提供し、POINT は次のディスク トラックの位置を NOTE によって以前に返されたアドレスに設定します。この戦略は、XMON を他の OS に簡単に移植できるようにし、当時利用可能なはるかに複雑なディスク直接アクセス オプションを回避するために採用されました。^[6]

XMON を、トラックあたり 1 ブロックの NOTE、POINT、および READ/WRITE ディスク操作の基本的な使用から、トラックあたりn ブロックのEXCP (つまり、新しいレコードの書き込み/作成) およびXDAP (つまり、古いレコードの読み取り/更新) に変換することで (n は実行時にターゲット デバイスの物理的特性から計算され、1 より大幅に大きい値になる場合があります)、アプリケーション パフォーマンスが大幅に向上し、オペレーティング システムのオーバーヘッドが削減されました。

XMON (オリジナルの NOTE、POINT、READ/WRITE 実装、または EXCP および XDAP 拡張機能) は、もともと OS /360用に開発されましたが、OS/370、XA、 OS/390、z/OSなど、その後リリースされた IBM OS でも、通常は変更なしで動作します。

XCOM はもともと、XPL チームによって発明された、現在は廃止されたMixed Strategy Precedenceと呼ばれるボトムアップ解析テーブル方式を使用していました (ただし、公式にリリースされたバージョンでは MSP パーサーが保持され、後にリリースされた「ピープホール最適化」や、元の実装チーム以外で開発された追加のデータ型は含まれていません)。 MSP は、Niklaus WirthがPL360用に発明した単純な優先順位パーサー方式を一般化したものです。単純な優先順位自体は、A+B*(C+D)-E などの式にうまく機能する、非常に単純な演算子優先順位方式を一般化したものです。 MSP テーブルには、予想される言語シンボルのトリプレットのリストが含まれています。このリストは文法サイズの 3 乗に比例して大きくなり、一般的な完全なプログラミング言語では非常に大きくなります。 XPL 由来のコンパイラは、メモリが限られた 1970 年代のミニコンピュータに収めるのが困難でした。^{[注 1]} MSP は、考えられるすべての文法を処理できるほど強力ではありません。これは、言語が広く使用される前に、言語設計者が言語定義を MSP の制限に合わせて調整できる場合にのみ適用されます。

トロント大学はその後、XCOM と XA を変更し、代わりにDonald KnuthのLR パーサーボトムアップ メソッドのバリアントを使用するようになりました。 ^{[nb 2] XCOM のバリアントは}Simple LRまたは SLR と呼ばれます。これは MSP よりも多くの文法を処理しますが、 LALRまたは完全なLR(1)ほど多くの文法を処理しません。LR(1) との違いは主にテーブル ジェネレータのアルゴリズムにあり、コンパイル時のパーサー メソッドにはありません。XCOM と XA は、Unix とそのyaccパーサー ジェネレータ ツールが広く利用可能になる前から存在しています。XA と yacc は同様の目的を持っています。

XPL はオープン ソースです。System/360 バージョンの XPL は、IBM SHAREユーザー組織を通じて配布されました。他のグループは、1970 年代の多くの大型マシンに XPL を移植しました。さまざまなグループが XPL を拡張したり、XPL を使用して他の中規模言語を実装したりしました。

XPL は、さまざまな言語やシステム用の多数のコンパイラの開発に使用されてきました。

• ストーニーブルック パスカル
• HAL/S、スペースシャトル計画で使用された言語^[7]
• MALUS は、ゼネラルモーターズがマルチコンソールタイムシェアリングシステムの開発に使用したシステムプログラミング言語です。
• ニューイングランドデジタルは、 1970年代半ばから、研究室の自動化、コンピュータネットワーク、音楽合成ハードウェアの制御に使用されるABLEシリーズコンピュータに「Scientific XPL」と呼ばれるXPLの変種を使用していました。

XPLは現在のコンピュータに移植され続けています。x86/ FreeBSDへの移植は2000年に行われ、^[8] x86/ Linuxへの移植は2015年に行われ、XPLからCへのトランスレータは2017年に行われました。^{[9] [10]}

• Alexander, WG および Wortman, DB「XPL プログラムの静的および動的特性」IEEE Computer 1975 年 11 月、41-46 ページ。
• Ancona, Massimo、Dodero, Gabriella、および Durante, Ercole Luigi「トランスレータ ライティング システムを使用したマイクロプロセッサのクロス ソフトウェア開発」1979 年第 4 回国際ソフトウェア エンジニアリング会議の議事録: 399-402。
• Kamnitzer, SH「IBM/360 から UNIVAC 1100 への XPL のブートストラップ」ACM SIGPLAN Notices 1975 年 5 月: 14-20。
• Karger, Paul A. 「Multics 用の XPL の実装」 SB 論文。マサチューセッツ工科大学、1972 年。
• Klumpp, Allan R.「宇宙ステーションの飛行ソフトウェア: Hal/S か Ada か?」Computer 1985 年 3 月号: 20-28 ページ。
• Leach, Geoffrey および Golde, Helmut。「XDS Sigma 5 コンピュータへの XPL のブートストラップ」ソフトウェア: 実践と経験 3 (1973): 235-244。
• McKeeman, William M.、Horning, James J.、Wortman, David B. 『コンパイラ ジェネレータ』。ニュージャージー州エングルウッド クリフス: Prentice-Hall、1970 年。
• McKeeman, WM、Horning, James J.、Nelson, EC、および Wortman, DB「XPL コンパイラ ジェネレータ システム」。AFIPS 会議議事録: 1968 年秋季合同コンピュータ会議。ワシントン DC: The Thompson Book Company。1968: 617-635。
• Sitton, Gary A.、Kendrick, Thomas A.、および Carrick, Jr., A. Gil. 「PL/EXUS 言語と仮想マシン」、ACM-IEEE 高級言語コンピュータ アーキテクチャ シンポジウム議事録、1973 年 11 月: 124-130。
• Slimick, John「現在のシステム実装言語: 1 人のユーザーの視点」システム実装言語に関する SIGPLAN シンポジウム議事録、1971 年 10 月: 20-28 ページ。
• Storm, Mark W.、および Polk, Jim A.「XPL ベースのコンパイラ ジェネレータ システムの使用」第 14 回 ACM 南東部地域会議の議事録、1976 年 4 月: 19-26 ページ。
• Wortman、DB「XPL 実装の一覧」ACM SIGPLAN 通知 1978 年 1 月: 70-74。

• PL/M

• McKeeman, William Marshall、Horning, James J.、Wortman, David B.、「A Compiler Generator」 (1971)、ISBN 978-0-13-155077-3。XPLシステムのすべてのコンポーネントのソース コードを含む、決定的なリファレンス。 

• トロント大学 XPL ホームページ
• XPLプログラミング言語
• Amazon.com のコンパイラ ジェネレーターのページ
• New England Digital Corporation の ABLE シリーズ コンピュータ向け Scientific XPL