S-アルゴル

S-algol (セントアンドリュースアルゴル) ^{[1] : vii}は、 1979年にセントアンドリュース大学でロン・モリソンとトニー・デイビーによって開発されたALGOL 60の派生プログラミング言語です。この言語は、モリソンが博士論文用に作成した直交データ型を含むようにALGOLを修正したものです。モリソンはその後、同大学の教授となり、コンピュータサイエンス部門の責任者となりました。S-algol言語は、1999年まで同大学の学部レベルの授業で使用されていました。また、1980年代にはセントアンドリュースの地元の学校であるマドラスカレッジで数年間教えられていた言語でもありました。コンピュータサイエンスのテキストRecursive Descent Compiling ^{[2]には、S-algolで実装されたS-algolの}再帰下降コンパイラーについて説明されています。

PS-algol はS-algol の永続的な派生です。1981 年頃にエディンバラ大学とセントアンドリュース大学で開発されました。PS -algol プログラムの終了後も存続する 永続ヒープの形式でデータの寿命を確保することで、データベース機能をサポートします。

ロン・モリソンの1979年の博士論文「Algolの開発について」では、S-algol言語の設計と実装について説明しています。^[3] 言語を定義した技術レポート「S-algolリファレンスマニュアル」（1979、1988）では、1975年頃の言語設計に関する議論に対して協力してくれたデビッド・ターナーを含む数名に感謝の意を表しています。 ^{[4] : 5} 1981年のコンピュータサイエンスのテキスト「再帰降下コンパイル」では、コンパイラの実装とブートストラップのプロセスについて説明しており、^{[2] 1982年の書籍}「S-algolによるプログラミング入門」では、この言語を使ってコンピュータプログラミングを教えています。^[1]

最初の S-algol 実装は、Unixオペレーティングシステムを実行するPDP-11 /40 コンピュータ上で行われました。 ^{[1] : vii} PDP-11 で使用できるアドレス空間が64キロバイトと小さいため、インタープリタ型バイトコード実装が選択されました。^{[3] : 37–38} S-algol で記述されたシングルパスの再帰下降コンパイラは 、S -algol ソースを S-code、つまり S-algol 用にカスタマイズされたスタックベースの抽象マシンのバイトコードに変換しました。その後、S-code はインタープリタによって実行されました。S-algol 実装は、初期のPascalコンパイラでの動作と多くの類似点がありました。再帰下降コンパイラを使用して抽象マシンのコードを生成する手法はよく知られており、 1970 年代初頭のPascal P コンパイラは有名な例でした。^{[2] : 137} S-algolコンパイラは、Urs AmmanがPascalコンパイラの開発のために説明した段階的な改良プロセス^{[2] : 71を 使用して書かれており、 [5] Pascalの発明者である}Niklaus Wirthが推進しました。^[6]

PDP-11 のメモリ構成が 32K 16 ビットワードであることを反映し、S コード命令のエンコードは各バイトコードが 1 ワードで構成されるように設計された。^{[3] : 38}最初のブートストラップは、 IBM/360上でAlgol Wで S コードを生成する S-algol コンパイラを作成し、それを使用して S-algol で記述されたコンパイラを S コードにコンパイルすることによって実行された。結果として得られた S コード ファイルは PDP-11 にコピーされ、PDP-11 用に記述された S コード インタープリタで実行され、自己ホスティングされた。自己ホスト型 S-algol コンパイラは、約 770 万の S コード命令を実行して自分自身をコンパイルし、約 1 万の S コード命令 (16 ビット ワード) の出力ファイルを生成した。^{[3] : 45}

S-コードインタープリタは、VMS を実行するVAXコンピュータ用に書かれ、VAX は最初の S-algolポートとなった。S-algol は、言語に追加されたラスターグラフィックス機能を含め、CP/Mを実行するZilog Z80マイクロプロセッサにも移植された。1983 年、S-algol は、持続性の研究に使用される PS-algol システムの基礎として使用された。PS-algol S-コードインタープリタはCで実装され、S-コード言語はラスターグラフィックスを含むように拡張された。PS-algol の実装は、Cで書き直され、拡張された S-code をターゲットとするコンパイラを備えた、MacintoshおよびSun ワークステーションへの S-algol ポートの基礎となった。 ^{[4] : 5}

S-algolは1983年のPS-algol研究の基礎となり、数年後にはPS-algolはNapier88言語と実装の出発点となった。すべてのS-algolコンパイラは解釈可能なSコードを生成したが、後のNapier88実装ではCでコードを生成し、それをgccコンパイラでコンパイルしてネイティブコード実装を提供する実験が行われた。^[7]

S-algol プログラムは、宣言と節のシーケンスです。宣言される言語要素には、定数、変数、プロシージャ、構造体が含まれます。定数と変数の宣言では、初期値を指定する必要があります。コンパイラは、宣言された定数または変数のデータ型を初期値の型から推測するため、型は明示的に指定されません。データ型には、整数、実数、ブール値、文字列、ポインタ (構造体へのポインタ)、ファイル、およびこれらの型のベクトル (配列) が含まれます。プロシージャ宣言では、引数と戻り値のデータ型を指定します (void でない場合)。構造体でも、フィールドのデータ型を指定します。節には、式と制御構造 (if、case、for、while、repeat while) が含まれます。if および case 制御構造には値を指定でき、型互換性ルールが満たされている限り、式で自由に使用できます。^{[4] [1]}

! コメントは感嘆符で始まり、行末まで続きます。

!letキーワードは定数と変数の宣言を導入します
! 識別子はアルファベット文字で始まり、その後に英数字またはピリオド (.) が続きます。
! 初期値を与える必要があり、これによって宣言のデータ型が決まります

let width := 10 ! := は変数の値を設定します。これはintです。
動物:= "dog"としましょう! 文字列型

let x := -7 ; let y := x + x ! ; 節を区切ります。行に2つ以上の節がある場合にのみ必要です。

let na = 6.022e+23 ! = は定数の値を設定するために使用されます。これは cfloat (定数 float) です。

! if と case は値を持ち、式で使用できます
no.of.lives := 動物 = "猫" の場合 9、それ以外の場合は 1 とします。

! エラトステネスの篩
「n = までの素数を見つけてください。」と書いてください。
let n = readi ! プログラム実行中に定数値を設定できる
p = ベクトル 2::n of true とします。境界が 2 から n の bool のベクトル
i = 2 の場合、truncate(sqrt(n)) を実行します。インデックスは定数なので、:= ではなく = を使用します。
    if p(i) do ! ベクトルの参照解除は手続き呼び出しのように括弧を使用する
        j = 2 * iからnまでiによって行う
            p(j) := 偽
i = 2からnまで
    p(i) が i と書く場合、"'n" ! リテラル文字列内の 'n は改行文字です

! cstring のバイナリツリーの構造 (レコード) 型
! pntr データ型は任意の型の構造体を指すことができ、型チェックは実行時に行われます。
構造 tree.node(cstring name; pntr left, right)

! バイナリツリーの先頭に新しい文字列を挿入します
手順 insert.tree(cpntr head ; cstring new -> pntr)
! case 節は必須のデフォルトオプションで終わります。必要ない場合は default : {} を使用します。
真実の場合
    ヘッド = nil : tree.node(new, nil, nil)
    新しい < head(name) : { head(left) := insert.tree(head(left), new) ; head }
    new > head(name) : { head(right) := insert.tree(head(right), new) ; head }
    デフォルト: ヘッド

手順 print.tree(cpntr head)
if head ~= nil do ! ~= は等しくない演算子です
始める
    print.tree(ヘッド(左))
    head(名前)、"'n" と書く
    print.tree(ヘッド(右))
終わり

果物を nil にする
果物 := insert.tree(果物、"バナナ")
fruit := insert.tree(fruit, "キウイ")
果物 := insert.tree(果物、"リンゴ")
果物 := insert.tree(果物、"桃")
print.tree(fruit) ! ソートされた順序で印刷する

! S-algol プログラムの終了は ? で示されます。
?

その名前が示すように、S-algolはALGOLファミリーのプログラミング言語のメンバーです。モリソンはALGOLファミリーの5つの特徴を特定しています：^{[3] : 5}

1. スコープルールとブロック構造– 名前は、ローカル環境の外部では定義されていないローカルな量を定義するために導入されることがあります。しかし、異なる環境では、異なるオブジェクトを表すために同じ名前が明確に使用されることがあります。^{[3] : 5}
2. 抽象化機能– プログラムを短縮し明確化するための強力な抽象化機能の提供。ALGOLファミリーでは、これはパラメータ付きの手続きによって提供される。^{[3] : 5}
3. コンパイル時の型チェック–プログラムの静的解析によって型をチェックすることができます。 ^{[3] : 5}
4. 無限保存– プログラマはストレージの割り当てに責任を負わず、必要な数だけデータオブジェクトを作成できます。^{[3] : 5}
5. 選択的ストア更新– プログラムはストアを選択的に変更することができます。ALGOLファミリーでは、これは代入文によって行われます。^{[3] : 6}

S-algol は、シンプルさによるパワーと、より高い一般性によるシンプルさを提供するというセマンティック原則に従って設計されており、ALGOL ファミリーの以前のメンバーとは異なるように設計されています。( Orthogonalを参照してください。) Morrison は、S-algol の設計を導いた 3 つのセマンティック原則について説明しています。

1. 対応の原則– 名前を管理する規則は統一されており、どこにでも適用できる必要があります。これは主に、宣言とプロシージャパラメータ間の対応に適用され、すべてのパラメータ渡しモードを考慮します。この原則は、RD Tennent が Pascal と共同で検討し、^[8] Peter Landin ^[9]とChristopher Stracheyの研究に端を発しています。^{[3] : 9–10  [10]}
2. 抽象化の原則–言語内のすべての意味のある意味カテゴリを抽象化できる必要があります。例としては、式の抽象化である関数や、文の抽象化である手続きなどがあります。テネントとモリソンは、抽象化すべき意味的に意味のある構成要素を特定するのが難しいため、この原則を適用するのは難しいと指摘しています。^{[3] : 10}
3. データ型の完全性の原則– すべてのデータ型は言語内で同じ権限を持ち、代入やパラメータとして渡されるなどの一般的な操作が許可されるべきである。^{[3] : 10} （ファーストクラスシチズンを参照。）

モリソン氏は、設計上の基本的な考慮事項をもう 1 つ挙げています。

1. 概念ストア– ストア（メモリ管理）に関する重要な設計上の決定には、ストアの使用方法、データ型との関係、ポインタの実装、保護（更新できない定数の場所）が含まれます。 ^{[3] ：10–11}

モリソンの論文では、設計原理が S-algol にどのように適用されたかが説明されています。

S-algol の基本データ型は、整数、実数、ブール値、ファイル、文字列です (後にピクセル型と画像型が追加され、ラスター グラフィックスがサポートされました)。 整数、実数、ブール値は、ほとんどのプログラミング言語に共通する型です。ファイル型は、データ オブジェクトの書き込みや読み取りを可能にする入出力(I/O)ストリームです。当時の多くの言語では、文字列型は複合型と見なされていましたが、これをネイティブ型として含めることで、連結、部分文字列の選択、長さ、比較 (等しい、より小さいなど) などの基本的な操作が使いやすくなります。Pascal で使用されている文字の配列よりもはるかに使いやすいです。^{[3] : 12}

ベクトルは任意の型の要素を持つ。任意のデータ型に対してT、*Tは型Tの要素を持つベクトルの型である。ベクトルの境界はその型の一部ではなく動的に決定され、多次元配列はベクトルのベクトルとして実装される。^{[3] : 12}

構造データ型は、それぞれが固定された型の任意の固定数のフィールドで構成されます。構造のクラスは型の一部ではありませんが、動的に決定できます。^{[3] : 12}

ベクターと構造体に対する基本型の閉包は、無限の数のデータ型を提供します。言語定義では、型が許容される場所であればどこでも任意の型を使用できます。これは、中置演算子には適用されません。中置演算子は一般的な関数の構文糖であり、セマンティックモデルの一部ではないためです。^{[3] : 12–13}

ベクトルと構造体は完全な権限を持ち、パラメータとして渡されるときに割り当てることができるが、割り当て時と渡されるときのコピーは大きなオブジェクトでは非効率になる可能性がある。ベクトルと構造体はオブジェクトへのポインタとして扱われ、ポインタはパラメータとして割り当てられ渡される。ALGOL 68やCのようにポインタ自体を一般オブジェクトとして扱うことは、 CAR Hoareのヌルポインタに関する懸念^[11]とダングリングポインタの問題のため、S-algolでは拒否される。^{[3] : 13}

S-algol は真の定数値、つまり値を更新できないオブジェクトを提供します。このアイデアは Strachey によるものですが、Pascal などの多くの言語の定数は明示的な定数であり、コンパイル時に処理され、保護された場所として実装されていません。また、スカラー型だけでなく、任意のデータ型の定数を宣言できる必要があります。^{[3] : 13}

S-algol は式指向言語であり、文はvoid型の式です。結果として、一部の制御構造は値を生成する式になります。

条件文にはいくつかの種類があります。 条件文の2択バージョンは で、節は文または式にすることができます。式の場合は、同じ型でなければなりません。片腕の条件文の型はvoidです。^{[3] : 13}条件文で の代わりにを使用すると、ぶら下がっている else構文の曖昧さを回避できます。^{[2] : 20}if <condition> then <clause> else <clause>if <condition> do <statement>doelse

節にcaseは任意の型のセレクタがあり、同じ型の式との等価性テストを使用してマッチングされ、選択された節が検索されます。case節は文または式にすることができるため、結果節はすべて文（型void）または同じ型の式でなければなりません。一致は順番にテストされるため、これは非決定性のないエドガー・ダイクストラのガード付きコマンドに似ています。^{[3] : 14}

ループ文は、ほとんどが従来のものです。forループは、Hoare のものと似ています。^[12] 制御識別子は定数であり、ループ内で変更することはできません。また、ループwhile <condition> do <statement>も従来のものですrepeat <statement> while <condition>。repeat <statement> while <condition> do <statement>構造は、早期終了または「n と半分」^[13]ループを提供します。^{[3] : 14}

S-algol は式を関数として、文 (void 式) を手続きとして抽象化します。 モジュールは宣言の抽象化を提供しますが、ブロック構造のスコープで問題が発生するため、S-algol にはモジュールは含まれていません。最後の構文カテゴリはシーケンサ、つまり制御構造です。Tennent はシーケンサの抽象化にsequelという用語を使用しましたが、これはgotoとbreakの一般化です。このカテゴリで最もよく知られている抽象化はcall-with-current-continuationですが、数年後まで十分に理解されませんでした。S-algol には goto や break は含まれておらず、シーケンサの抽象化も含まれていません。^{[3] : 14}

S-algol のすべてのデータ オブジェクトは、宣言時に値を指定する必要があります。これは、値渡しによるパラメータの呼び出しに対応し、初期化されていない値を使用する可能性を排除します。実際、値渡しは S-algol で唯一のパラメータ渡し方法です。参照パラメータと結果パラメータは拒否されますが、これは S-algol の左辺値の渡し禁止と一致しています。構造体とベクトルはオブジェクトへのポインタとして渡されますが、動作は代入の右側で使用される値と同じであるため、これは依然として値渡しです。^{[3] : 15}

すべての宣言には、パラメトリックな同等物があります。すべてのプロシージャパラメータの型を指定する必要があります。パラメータとして渡されるプロシージャはすべて、その完全な型が指定されます（Pascalとは対照的）。同じことが構造体クラスにも当てはまります。^{[3] : 15}

S-algolはfileI/Oストリームのデータ型を提供し、いくつかのバリエーションreadとがwrite基本型を操作するために定義されています。個々の実装では、必要に応じてこれらの単純な機能を拡張することが期待されています。^{[3] : 15}

ALGOL言語は冗長であると批判されてきました。S-algolは、より制限の少ない構文を提供することでこれを改善しようとしています。^{[1] : 159} これは主に宣言構文で実証されています。変数宣言には常に初期値が含まれている必要があるため、型を明示的に指定する必要はありません。^{[3] : 17}

プロシージャが呼び出される場所を調べることでプロシージャのパラメータと戻り値の型を推測することは可能ですが、S-algolではパラメータと戻り値の型を指定する必要があります。これは、呼び出しを調べなくてもプロシージャを理解できるはずなので、実用的な決定です。^{[3] : 17}

ほとんどのALGOLでは、ブロック内の文の前にすべての宣言が来る必要があります。S-algolでは、すべてが使用される前に宣言されなければならず、宣言を飛び越えることを許可するgotoがないため、宣言と文を混在させることができます。^{[3] : 17}

• ネイピア88

• Algol 60 の実装と方言、コンピュータ歴史博物館ソフトウェア保存グループ
• 持続性S-アルゴル