S-algol
S-ALGOL（セントアンドリュースアルゴル） ：VIIは、 コンピュータであるプログラミング言語の誘導体ALGOL 60で開発セントアンドリュースの大学によって1979年にロン・モリソンとトニーデイビー。この言語は、モリソンが博士論文のために作成した直交データ型を含むようにALGOLを変更したものです。モリソンは大学の教授になり、コンピュータサイエンス学科の長になりました。S-algol言語は、大学の学部で教えるために使用されました1999年までのレベル。1980年代にマドラス大学セントアンドリュースの地元の学校で数年間教えられた言語でもありました。コンピュータサイエンスのテキストRecursiveDescent Compiling は、S-algolに実装されたS-algol用の再帰下降 コンパイラについて説明しています。
S-アルゴル
パラダイム
マルチパラダイム：手続き、不可欠、構造化
家族 ALGOL によって設計された
ロン・モリソン、トニー・デイビー
デベロッパー
セントアンドリュース大学
初登場
1979 ; 42年前 （1979）S-アルゴル
プラットホーム
PDP-11 / 40、IBM System / 360、VAX、Zilog Z80、Macintosh、Sun-3 OS Unix、BOS / 360、VMS、CP / M
に影響を受けた ALGOL 60 影響を受ける
PS-algol、Napier88
PS-アルゴールはS-アルゴールの永続的な誘導体です。1981年頃にエジンバラ大学とセントアンドリュース大学で開発されました。PS-algolプログラムの終了後も存続する永続ヒープの形式でデータの寿命を提供することにより、データベース機能をサポートします。
コンテンツ
1 歴史と実装
2 言語の概要
3 意味論の原則
4 設計
4.1 データ型 4.2 店舗 4.3 制御構造 4.4 抽象化 4.5 宣言とパラメーター 4.6 産業連関モデル 4.7 具体的な構文
5 も参照してください
6 参考文献
7 外部リンク
歴史と実装
Ron Morrisonの1979年の博士論文、On the Development of Algolは、S-algol言語の設計と実装について説明しています。言語を定義するテクニカルレポート、S-algolリファレンスマニュアル（1979、1988）は、1975年頃の言語設計に関する議論をしてくれたDavid Turnerを含め、何人かの人々の助けに感謝します。 ：5 1981年のコンピュータサイエンステキストRecursive Descent Compilingは、コンパイラの実装とブートストラッププロセスについて説明しています。1982年の著書「S-algolを使用したプログラミング入門」では、この言語を使用してコンピュータプログラミングを教えています。
最初のS-algolの実装は、Unixオペレーティングシステムを実行しているPDP-11 / 40コンピューター上にありました。 ：vii PDP-11で使用可能な64キロバイトのアドレス空間が小さいため、解釈されたバイトコードの実装が選択されました。 ：37–38 S-algolで記述されたシングルパスの再帰下降コンパイラは、S-algolソースをS-codeに変換しました。これは、S-algol用に調整されたスタックベースの抽象マシンのバイトコードです。その後、Sコードはインタプリタによって実行されました。S-algolの実装には、以前のPascalコンパイラでの作業と多くの類似点がありました。再帰下降コンパイラを使用して抽象マシンのコードを生成する手法はよく知られており、PascalPコンパイラは1970年代初頭の有名な例です。 ：137 S-algolコンパイラは、段階的詳細化プロセス ：71を使用して作成 され、Pascalコンパイラの開発のためにUrs Ammanによって記述され、Pascalの発明者であるNiklausWirthによって支持されました。
PDP-11のメモリ構成を32K16ビットワードとして反映し、Sコード命令エンコーディングは各バイトコードが1ワードで構成されるように設計されました。 ：38 初期ブートストラップにおけるS-ALGOLコンパイラ書き込むことによって行ったアルゴルW上のIBM / 360 Sコードを生成し、SコードのS-ALGOLに書き込まれたコンパイラをコンパイルするためにそれを使用。結果のSコードファイルはPDP-11にコピーされ、PDP-11用に作成されたSコードインタープリターで実行され、セルフホスティングになりました。自己ホスト型S-algolコンパイラは、約770万のSコード命令を実行して自身をコンパイルし、約1万のSコード命令（16ビットワード）の出力ファイルを生成しました。 ：45
VMSを実行しているVAXコンピューター用にSコードインタープリターが作成され、VAXが最初のS-algolポートになりました。S-algolは、CP / Mを実行するZilogZ80マイクロプロセッサにも移植されました。これには、言語に追加されたラスターグラフィックス機能が含まれます。1983年に、S-アルゴールはPS-アルゴールシステムの基礎として使用され、持続性の研究に使用されました。PS-algol SコードインタープリターはCで実装され、Sコード言語はラスターグラフィックスを含むように拡張されました。PS-algolの実装は、MacintoshおよびSunワークステーションへのS-algolポートの基礎であり、Cで書き直され、拡張Sコードを対象とするコンパイラーを備えています。 ：5
S-algolは1983年のPS-algol研究の基礎であり、数年後、PS-algolはNapier88言語と実装の出発点になりました。すべてのS-algolコンパイラが解釈されるSコードを生成しましたが、後のNapier88実装は、Cでコードを生成し、それをgccコンパイラでコンパイルしてネイティブコード実装を提供することを試みました。
言語の概要
S-algolプログラムは、一連の宣言と句です。宣言される言語要素には、定数、変数、プロシージャ、および構造が含まれます。定数および変数の宣言では、初期値を指定する必要がコンパイラは、宣言された定数または変数のデータ型を初期値の型から推測するため、型は明示的に記述されデータ型には、整数、実数、ブール値、文字列、（構造体への）ポインター、ファイル、およびこれらの型のベクトル（配列）が含まれます。プロシージャ宣言は、引数のデータ型と戻り値を指定します（voidを除く）。構造体は、フィールドのデータ型も指定します。句には、式と制御構造（if、case、for、while、repeat while）が含まれます。ifおよびcase制御構造は値を持つことができ、型の互換性ルールが満たされている限り、式で自由に使用できます。
！コメントは感嘆符で紹介され、行末まで続きます。！letキーワードは、定数と変数の宣言を導入します！識別子は英字で始まり、その後に英数字またはピリオド（。）が続きます。！初期値を指定する必要があり、これにより宣言のデータ型が決まります幅：= 10にしましょう！：=変数の値を設定します。これはintです。動物：=「犬」にしましょう！タイプ文字列x：= -7; y：= x + x！; 行に2つ以上の句がある場合にのみ必要な句を区切りますna = 6.022e + 23とします！=定数の値を設定するために使用されます。これはcfloat（定数float）です。！ifとcaseは値を持ち、式で使用できますlet no.of.lives：= if animal = “cat” then 9 else 1！エラトステネスのふるい「n =までの素数を見つける？」と書くn = readiとしましょう！プログラムの実行中に定数値を設定できますp = vector 2 :: n of true！境界が2からnのブールのベクトルfor i = 2 to truncate（sqrt（n））do！インデックスの場合は定数であるため、：=ではなく=を使用します p（i）が行う場合！ベクトル逆参照は、プロシージャコールのように親を使用します
for j = 2 * i to n by i do
p（j）：= falsei = 2からnの場合 p（i）がiを書く場合、 “‘n”！リテラル文字列の ‘nは改行です！cstringsの二分木の構造（レコード）型！pntrデータ型は任意の型の構造を指すことができ、型チェックは実行時に行われます構造tree.node（cstring name; pntr left、right）！二分木の頭に新しい文字列を挿入しますプロシージャinsert.tree（cpntr head; cstring new-> pntr）！case句は必須のデフォルトオプションで終わります。不要な場合はdefault：{}を使用してくださいの場合 head = nil：tree.node（new、nil、nil） new
意味論の原則
その名前が示すように、S-algolはプログラミング言語のALGOLファミリーのメンバーです。モリソンは、ALGOLファミリーの5つの特徴を特定しています： ：5
スコープルールとブロック構造–名前を導入して、ローカル環境の外部で定義されていないローカル数量を定義できますが、異なる環境では、異なるオブジェクトを表すために同じ名前を明確に使用できます。 ：5
抽象化機能–プログラムを短縮および明確化するための強力な抽象化機能の提供。ALGOLファミリーでは、これはパラメーターを使用したプロシージャによって提供されます。 ：5
コンパイル時の型チェック–型はプログラムの静的分析によってチェックできます。 ：5
無限ストア–プログラマーはストレージ割り当ての責任を負わず、必要な数のデータオブジェクトを作成できます。 ：5
選択的なストアの更新–プログラムはストアを選択的に変更する場合がALGOLファミリーでは、これは代入ステートメントによって影響を受けます。 ：6
S-algolは、セマンティックの原則に従って設計され、シンプルさによってパワーを提供し、より一般性によってシンプルさを提供することで、ALGOLファミリーの以前のメンバーとは異なるように設計されました。（直交を参照して）モリソンは、S-アルゴールの設計を導いた3つの意味論的原則について説明しています。
対応の原則–名前を管理する規則は統一され、どこにでも適用される必要がこれは主に、すべてのパラメータ受け渡しモードの考慮を含め、宣言とプロシージャパラメータ間の対応に適用されます。この原理は、パスカルと共同でRDテネントによって検討され、ピーター・ランディンとクリストファー・ストレイチーの研究にそのルーツが ：9–10
抽象化の原則–言語内のすべての意味のあるセマンティックカテゴリを抽象化できる必要が例には、式の抽象化である関数や、ステートメントの抽象化であるプロシージャが含まれます。TennentとMorrisonは、抽象化する必要のある意味的に意味のある構成を特定するのが難しいため、これを適用するのは難しい原則であると述べています。 ：10
データ型の完全性の原則–すべてのデータ型は言語で同じ権限を持っている必要があり、割り当てやパラメーターとして渡されるなどの一般的な操作で許可される必要が ：10 （一級市民を参照。）
モリソンはまた、もう1つの基本的な設計上の考慮事項を特定しています。
概念ストア–ストア（メモリ管理）に関する重要な設計上の決定には、ストアの使用方法、データ型との関係、ポインターの実装、および保護（更新できない一定の場所）が含まれます。 ：10–11
設計
モリソンの論文は、S-algolで設計原理がどのように適用されたかを説明しています。
データ型
S-algolの基本データ型またはプリミティブデータ型は、整数、実数、ブール値、ファイル、および文字列です。（ラスターグラフィックスをサポートするために、後のピクセルおよび画像タイプが追加されました。）整数、実数、およびブール値は、ほとんどのプログラミング言語に共通のタイプです。ファイルタイプは、入力/出力（I / O）ストリームデータオブジェクトを書き込む又は読み出すことができます。当時の多くの言語の文字列型は複合型と見なされていましたが、ネイティブ型として含めると、連結、部分文字列の選択、長さ、および比較（等しい、より小さいなど）の基本操作が使いやすくなります。Pascalで使用される文字の配列よりもはるかに快適です。 ：12
ベクトルには、あらゆるタイプのコンポーネントが付属しています。任意のデータ型についてT、*TはタイプTのコンポーネントを持つベクトルのタイプです。ベクトルの境界はそのタイプの一部ではなく動的に決定され、多次元配列はベクトルのベクトルとして実装されます。 ：12
構造データ型がフィールドの固定タイプの各々の任意の固定数を備えます。構造体のクラスは型の一部ではありませんが、動的に決定できます。 ：12
ベクトルと構造に対する基本型のクロージャは、無限の数のデータ型を提供します。言語定義により、タイプが受け入れられる場所であればどこでも、任意のタイプを使用できます。中置演算子は一般的な関数の構文糖衣であり、セマンティックモデルの一部ではないため、これは適用されません。 ：12–13
店舗
ベクトルと構造体には完全な権限があり、パラメーターとして渡されたものとして割り当てることができますが、割り当て時および渡されたときにコピーすることは、大きなオブジェクトに対して非効率的である可能性がベクトルと構造体はオブジェクトへのポインターとして扱われ、ポインターはパラメーターとして割り当てられて渡されます。ポインタのような一般的なオブジェクト自体としてALGOL 68及びCは、理由の懸念のS-ALGOLのために拒否されCARホーア約ヌルポインタとの問題ダングリングポインタ。 ：13
S-algolは、真の定数値、つまり値を更新できないオブジェクトを提供します。このアイデアはStracheyによるものですが、Pascalなどの多くの言語の定数はマニフェスト定数であり、コンパイル時に処理され、保護された場所として実装されません。また、スカラー型だけでなく、任意のデータ型の定数を宣言できる必要が ：13
制御構造
S-ALGOL式指向の言語であり、ステートメントがある表現型の空。結果として、一部の制御構造は値を生成する式です。
いくつかの条件付き構文が条件if
case句は、選択された句を見つけるために、同じタイプの表現に対して等価試験を使用して整合される任意のタイプのセレクタを有しています。case句はステートメントまたは式にすることができるため、結果句はすべてステートメント（タイプvoid）または同じタイプの式である必要が一致は順番にテストされるため、これは非決定論のないEdsgarDijkstraの保護されたコマンドに似ています。 ：14
ループ文は、主に従来のものです。forループはHoareのループに似ています。制御識別子は定数であり、ループ内で変更することはできません。また、従来型のwhile
抽象化
S-algolは、式を関数として抽象化し、ステートメント（void式）をプロシージャとして抽象化します。モジュールは宣言の抽象化を提供しますが、S-algolには、ブロック構造化スコープで発生する問題のため、モジュールは含まれ最後の構文カテゴリは、シーケンサー、つまり制御構造です。Tennentは、シーケンサーの抽象化に続編という用語を使用しました。これらは、gotoとbreakの一般化です。このカテゴリで最もよく知られている抽象化は、call-with-current-continuationですが、数年後までよく理解されません。S-algolには、gotoやbreakは含まれまた、シーケンサーの抽象化も含まれ ：14
宣言とパラメーター
S-algolのすべてのデータオブジェクトには、宣言時に値を指定する必要がこれは、値による呼び出しパラメーターの受け渡しに対応し、初期化されていない値を使用する可能性を排除します。実際、値による呼び出しは、S-algolの唯一のパラメーター受け渡しメソッドです。参照パラメーターと結果パラメーターは拒否されます。これは、l値の受け渡しに関するS-algolの禁止と一致しています。構造体とベクトルはオブジェクトへのポインターとして渡されますが、動作は割り当ての右側で使用される値と同じであるため、これは値によって呼び出されます。 ：15
すべての宣言には、パラメトリックに相当するものがすべてのプロシージャー・パラメーター・タイプを指定する必要がパラメータとして渡されるプロシージャには、（Pascalとは対照的に）完全な型が指定されており、構造体クラスについても同じことが言えます。 ：15
産業連関モデル
S-ALGOLを提供するfileI / Oストリーム、及びいくつかのバリエーションのためのデータ型readとwriteの基本的なタイプで動作するように定義されています。個々の実装は、必要に応じてこれらの単純な機能を拡張することが期待されます。 ：15
具体的な構文
ALGOLの言語は、冗長であると批判されてきました。S-algolは、制限の少ない構文を提供することにより、これを改善しようとします。 ：159 これは主に宣言構文で示されます。変数宣言には常に初期値を含める必要があるため、型を明示的に指定する必要はありません。 ：17
プロシージャが呼び出される場所を調べることで、プロシージャのパラメータと戻り値のタイプを推測することは可能ですが、S-algolではパラメータと戻り値のタイプを指定する必要が呼び出しを調べなくても手順を理解できるはずなので、これは実際的な決定です。 ：17
ほとんどのALGOLでは、すべての宣言がブロック内のステートメントの前に来る必要がS-algolでは、宣言を使用する前にすべてを宣言する必要があり、宣言を飛び越えることを許可するgotoがないため、宣言がステートメントと混在する場合が ：17
も参照してください
Napier88
参考文献
^ Cole、AJ; Morrison、R。（1982）、S-algolを使用したプログラミング入門、ケンブリッジ大学出版局、ISBN 978-0-521-25001-6 ^ Davie、Antony JT; Ronald Morrison（1981）、Brian Meek（ed。）、Recursive Descent Compiling、Ellis Horwood series in Computers and their Applications、Chichester、West Sussex：Ellis Horwood、ISBN 978-0-470-27270-1 ^ ac ad Morrison、R。（1979）。アルゴール（PhD）の開発について。セントアンドリュース大学。pp。1–70。
^ Morrison、Ron（1988）、S-algol言語リファレンスマニュアル（技術レポートCS / 79/1）、ファイフ：セントアンドリュース大学、pp。1–53
^ Amman、Urs（1972）、「コンパイラの開発」、Proc。Int。コンピューティングに関するシンポジウム、北ホラント、93〜99ページ
^ Wirth、Niklaus（1971年4月）、「段階的詳細化によるプログラム開発」、Communications of the ACM、14（4）：221–227、doi：10.1145 / 362575.362577、hdl：20.500.11850 / 80846
^ Bushell、SJ; 親愛なる、A; ブラウン、AL; Vaughan、FA（1994）、「永続システムでのネイティブコード生成のためのコンパイラターゲット言語としてのCの使用」（pdf）、Atkinson、MP; Maier、D; ベンザケン、V（編）、Proc。第6回永続オブジェクトシステムに関する国際ワークショップ（POS6）、フランス、タラスコン、コンピューティングのワークショップ、Springer-Verlag、164〜183ページ
^ Tennent、RD（1977）、「セマンティック原理に基づく言語設計方法」、Acta Informatica、8（2）：97–112、doi：10.1007 / bf00289243
^ Landin、PJ（1966年3月）、「次の700プログラミング言語」、Communications of the ACM、9（3）：157–164、doi：10.1145 / 365230.365257
^ Strachey、C。（1966）、「形式的意味論に向けて」、形式言語記述言語、北ホラント、pp。198–220
^ Hoare、CAR（1975）、「再帰的データ構造」、International Journal of Computer and System Sciences、4（2）：105–132、doi：10.1007 / bf00976239
^ Hoare、CAR（1972）、「forステートメントに関する注記」、BIT、12（3）：334–341、doi：10.1007 / bf01932305
^ Edsgar Dijkstra（1973）。ドナルド・クヌースへの個人的なコミュニケーション、
Knuth、D。（1974）、”Structured Programming with go to Statements” （PDF）、Computing Surveys、6（4）：261–301、CiteSeerX 10.1.1.103.6084、doi：10.1145 /356635.356640からアーカイブ、オリジナル（PDF） 2013年10月23日に
外部リンク
Algol 60の実装と方言、コンピューター歴史博物館ソフトウェア保存グループ
永続的なS-アルゴール