アルゴリズム (Web)

[1] Web 関連の仕様書では、プログラムの動作に関する要件の多くや文書の適合性に関する要件の一部はアルゴリズム (algorithm) として記述されています。

仕様書

[5] HTML Standard (2014-09-19 23:39:59 +09:00 版) https://html.spec.whatwg.org/#conformance-requirements

呼称

[2] 一連の処理をまとめたものの呼称として、「アルゴリズム (algorithm) 」の他に「steps」も用いられています。両者間に明確な使い分けはないようです。

[35] 「アルゴリズム」も「steps」も、構成する各段階は「step」といいます。

記述

[3] 仕様書上のアルゴリズムの記述方法は、共通の規定はなく、各仕様書によって若干の違いがあります。

[4] 現在ほとんどの仕様書では、自然言語 (英語) により規定を述べています。

適合性

[8] アルゴリズムとして記述された要件は、必ずしもそのまま実装しなくても構いません。外部から観測可能な結果が同じである限り、任意の方法で実装して構いません。 >>5

[9] このことは明記されていない仕様書もありますが、どの仕様書でもそうであると理解されています。アルゴリズムの形での要件の記述は、それが最も正確な記述方法であるから採用されているだけで、実装方法を制約する意図はありません。特に、わかりやすさのために性能を度外視していることがあります >>5。

[6] RFC 2119 助動詞によって要件を明記するスタイルの仕様書 (HTML Standard など) では、アルゴリズム内の動作は命令形で記述し、アルゴリズム全体を説明する文の助動詞が命令形の各文に適用されることとしています >>5。

[7] 例えば、

To eat an orange, the user MUST:
Peel the orange.
Separate each slice of the orange.
Eat the orange slices.

... は、

To eat an orange:
The user MUST peel the orange.
The user MUST separate each slice of the orange.
The user MUST eat the orange slices.

... と同じ要件を表しています >>5。

フロー制御

[10] アルゴリズムの各段階は「step」と呼ばれます。 step の粒度は仕様書の筆者や個々のアルゴリズムによって様々で一概には言えませんが、プログラミング言語で一行で書ける単位 (一般的に「1ステップ」とされる粒度) となっていることが多いようです。

[13] step は必要があれば連番によって参照されますが、ジャンプなどで参照される時は名前が付されていることがあります。

Rewind: If there are no entries before entry in the list of active formatting elements, then jump to the step labeled create.

[11] step は入れ子になっていたり、条件分岐となっていたりすることもあります。 step の中の step は「substep」と呼ばれます。

[12] 一連の step は、記述の順に実行されます。すなわち、連接は先のものから順に実行することを表しています。ただし、分岐などにより飛ばされることもあります。

[14] ジャンプは「jump to」や「go to」、「return to」などの表現で飛び先の step が指定されます。飛び先は「次のステップ」のような相対的な表現のこともあります。

If node is formatting element, then go to the next step in the overall algorithm.

[15] 条件分岐は「if」や「unless」などの文章で表現されたり、変数などの値によって動作が指定されたり (switch) します。

[16] 反復は「for each」、「while」、「repeat」のような文章で表現されることがあります。

[17] Ian Hickson の仕様書では反復は「if」と「go to」などで表現されることが多いです。

[18] アルゴリズムの停止は、「abort these steps」などの表現により示されます。ただしアルゴリズムの末端では自明に停止するため明記されないのが普通です。

[19] アルゴリズムは値を返す場合があり、「return」を使った文章で返す値が指定されます。またアルゴリズムは例外を投げる場合があり、「throw」を使った文章で記述されます。 Ian Hickson の仕様書ではこれらの場合でも「abort these steps」を明記するのが普通ですが (場合によっては更に処理が続くこともあります。)、仕様書によっては暗示的にアルゴリズムが停止することにしている場合もあるので、注意が必要です。

[22] アルゴリズムの返すものは常に同じ種類とは限りません。処理の内容によって違う種類 (型) のものを返すことがあります。また値ではなく「失敗」のような概念を返すことがあります。

[32] 継続についてはイベントループのスピンを参照。

アルゴリズムの呼び出し

[20] アルゴリズムは他のアルゴリズムを呼び出すことがあります (直接または間接に自身を呼び出すこともあります)。その場合、元のアルゴリズムは一旦停止し、呼び出したアルゴリズムが返した結果を (あれば) 受け取ってから処理を継続します。呼び出したアルゴリズムが例外を投げた場合は、明示的に捕獲していない限り元のアルゴリズムもそのまま停止すると解釈されています (このことは各仕様書には必ずしも明記されていませんので、注意が必要です)。

[27] 「即座に実行」と明記されることがありますが、普通は明記されなくても原則としてアルゴリズムは規定された事象が発生した時点で即座に実行されます。

[21] 呼び出されたアルゴリズムは呼び出したアルゴリズムの変数にアクセスしないのが普通ですが、中には呼び出したアルゴリズムの変数にアクセスするものもあります。その場合はその旨が明記されています。

フック

[23] アルゴリズムの中では「フック」を呼び出すものがあります。これは仕様書の記述上の技法で、他の仕様書または同じ仕様書の他の場所で定義されたアルゴリズム群の実行のタイミングを明確にしつつも、それらを別々の箇所で規定するものです。

[24] 例えば DOM Standard は要素の挿入のアルゴリズムの途中で insertion steps を呼び出します。 HTML Standard はいくつかの HTML要素に関して insertion steps を定義しています。これらにより、例えば script 要素が appendChild されるとスクリプトが実行される、という動作が規定されています。

[25] フックの実行方法は他のアルゴリズムと変わりません。ただしフックは該当するアルゴリズムが複数存在することがあり、その場合はいずれをも実行します。該当するアルゴリズムが存在しない時は何も実行しません。

[26] 複数存在しても、それらの実行順序が問題となることはないように規定されているはずです。

並列性

[28] アルゴリズムの一部または全部が並列に実行されることがあります。その場合は並列に実行される部分を無視した続きを継続して処理するものと、並列に実行される部分を処理するもので、複数の処理が同時に進行することになります。

詳しくは並列実行を参照。

[29] また並列に実行した処理の後のいくつかの step が同期区間として記されていることがあります。同期区間は安定状態を待ってイベントループ内で実行されるものです。

詳しくは安定状態を参照。

[41] 並列に実行されている他のアルゴリズムを停止 (abort) させることがあります。

[42] fetch 関係のアルゴリズムやバイブレーションを実施するアルゴリズムは、自身が別途実行中なら、それを停止させることがあります。

[43] バイブレーションを実施するアルゴリズムは他のアルゴリズムにより停止されることがあります。

[30] I/O に関わる処理のほとんどは並列に実行されることになっています。

[44] 並列でないことを即座に実行するといいます。通常アルゴリズムは別途指定がなければ各段階を即座に順に実行していきますが、そのことを明確にするために敢えて即座に実行すると指示されることもあります。

[54] 他の処理や、何らかの条件が整うのを待って、次の処理に進むよう指示されている場合もあります。

仕様書は仕様書としての正確性や理解の容易性を優先しているので、そのままの形で実装できる場合もあれば、「待つ」を使わない形に読み替えて実装するのが現実的な場合もあります。

遅延実行

[31] アルゴリズムの一部または全部の実行はキューに入れられて遅延されることがあります。そのようなキューには次のものがあります。

[33] 安定状態を待って同期区間を実行する手順はマイクロタスクキューに入れられます。

歴史

[36] プロトコルの動作やマーク付け言語の処理の規定などをアルゴリズムの形で記述することは古くから部分的に行われてきましたが、どちらかといえば例外的なものとされることがほとんどでした。アルゴリズムが提示される場合であっても、規定ではなく参考とされることも多々ありました。

[37] これはアルゴリズムの提示によって実装方法が必要以上に詳細に制限されてしまうのを避ける目的があったり、アルゴリズムによる手続き的な記述よりも宣言的な記述や構文記述言語等による形式的な記述がより理解しやすい、あるいは政治的に好ましいと考える人が多いことに由来しているようです。関連する分野で歴史的に使われてきた記述方法を引き継ぐ (例えば同じ BNF の方言を用いる) 場合も多々ありました。

[38] しかし、少なくても Web においては、従来の仕様書が曖昧にしていたことが原因で相互運用性に著しい支障をもたらしたことがわかってきたこと、理解にしやすさに難があったとしてもこれ以上に正確に記述する方法が他にないことなどから、アルゴリズムによる規定が一般的になってきました。

[40] Web 関連仕様の中では、 ECMAScript がプログラミング言語の仕様書ということもあり、早くからアルゴリズムによる詳細な処理方法の規定を行っていました。

[39] 00年代の中期に Ian Hickson による Web Applications 1.0 (現在の HTML Standard) がHTML構文解析器をはじめとする HTML の処理方法をアルゴリズムの形で正確に規定するようになり、やがて Web IDL、 DOM、CSSOM、Fetch、CSP など他の仕様書でも同様の形で規定するようになりました。

[34] Add algorithms be implemented in any manner · f765c1a · whatwg/url (2014-10-23 02:21:07 +09:00 版) https://github.com/whatwg/url/commit/f765c1ad6bf6e339f5ccca0476ea6ef1c1ff51cf

[45] Re: Writing spec algorithms in ES6? (Joshua Bell 著, 2015-06-12 06:25:20 +09:00 版) https://lists.w3.org/Archives/Public/public-webapps/2015AprJun/0865.html

I just did a rework of the IDB "v2" editor's draft and probably 90% of the
spec is basically an additional layer of "bindings" between
WebIDL/ECMAScript and the the core concepts of the spec. That 90% was
previously written as blocks of prose rather than imperative algorithms and
behavior does differ among implementations. Fortunately, that mostly
applies to edge cases (bad inputs, getters/setters). Maybe it's just IDB,
but the remaining 10%of the spec is where all the fun
implementation-specific optimizations happen and is 90% of the actual code,
it's just short in the spec because it can be described in abstract terms.

[46] IRC logs: freenode / #whatwg / 20150914 (2015-09-15 10:58:37 +09:00 版) http://krijnhoetmer.nl/irc-logs/whatwg/20150914

[47] Deprecating old IDL (Marcos Caceres 著, 2015-09-20 00:55:21 +09:00 版) https://lists.w3.org/Archives/Public/public-script-coord/2015JulSep/0074.html