663.txt

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

* 仕様書

[REFS[
- [5] [CITE@en-GB-x-hixie[HTML Standard]] ([TIME[2014-09-19 23:39:59 +09:00]] 版) <https://html.spec.whatwg.org/#conformance-requirements>
]REFS]

* 呼称

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

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

* 記述

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

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

* 適合性

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

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

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

[EG[
[7] 例えば、
>
To eat an orange, the user [['''MUST''']]:
[FIG(steps)[
= Peel the orange.
= Separate each slice of the orange.
= Eat the orange slices.
]FIG]

... は、
>
To eat an orange:
[FIG(steps)[
= The user [['''MUST''']] peel the orange.
= The user [['''MUST''']] separate each slice of the orange.
= The user [['''MUST''']] eat the orange slices.
]FIG]

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

* フロー制御

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

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

[EG[
>
= '''Rewind''': If there are no entries before [VAR[entry]] in the list of active formatting elements, then jump to the step labeled '''create'''.
]EG]

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

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

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

[EG[
>
= If [VAR[node]] is [VAR[formatting element]], then go to the next step in the overall algorithm.
]EG]

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

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

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

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

** 並列性

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

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

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

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

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

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

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

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

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

** 遅延実行

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

[FIG(short list)[
- [[タスクキュー]]
- [[マイクロタスクキュー]]
- [[大域スクリプト片付けジョブリスト]]
- [[セッション履歴探索キュー]]
- [[pending application cache download process tasks]]
- [[animation frame task]]
]FIG]

;; [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]] など他の仕様書でも同様の形で規定するようになりました。

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

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

> 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.

]FIG]


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