JavaScript | Алгоритмические обозначения

В спецификации часто используется нумерованный список для определения шагов алгоритма. Эти алгоритмы используются для точного определения требуемой семантики языковых конструкций ECMAScript. Алгоритмы не предназначены для использования каких-либо конкретных методов реализации. На практике могут существовать более эффективные алгоритмы для реализации данной функции.

Алгоритмы могут быть явно параметризованы упорядоченной последовательностью псевдонимов, разделенных запятыми, которые могут использоваться на этапах алгоритма для ссылки на аргумент, переданный в этой позиции. Необязательные параметры обозначаются окружающими скобками ([ , name ]) и ничем не отличаются от обязательных параметров в шагах алгоритма. Остаточный параметр может находиться в конце списка параметров, обозначенных ведущим многоточием (, …name). Параметр rest записывает все аргументы, предоставленные после обязательных и дополнительных параметров, в Список. Если таких дополнительных аргументов нет, этот Список пуст.

Шаги алгоритма можно разделить на последовательные подэтапы. Подшаги имеют отступ и сами могут быть разделены на подшаги с отступом. Для идентификации подшагов используются схемы нумерации, при этом первый уровень подшагов помечен строчными буквенными символами, а второй уровень подшагов помечен римскими цифрами в нижнем регистре. Если требуется более трех уровней, эти правила повторяются с четвертым уровнем, используя числовые метки. Например:

1. Top-level step

a. Substep.

b. Substep.

i. Subsubstep.

1. Subsubsubstep

a. Subsubsubsubstep

i. Subsubsubsubsubstep

Шаг или подшаг можно записать как предикат «если»(if), который обуславливает его подшаги. В этом случае подшаги применяются только в том случае, если предикат истинен. Если шаг или подшаг начинается со слова «иначе»(else), это предикат, который является отрицанием предыдущего шага предиката «если»(if) на том же уровне.


Шаг может определять итеративное применение своих подшагов.

Шаг, начинающийся с «Assert:», утверждает неизменное условие его алгоритма. Такие утверждения используются для создания явных алгоритмических инвариантов, которые в противном случае были бы неявными. Такие утверждения не добавляют никаких дополнительных семантических требований и, следовательно, не требуют проверки реализацией. Они используются просто для уточнения алгоритмов.

Шаги алгоритма могут объявлять именованные псевдонимы для любого значения, используя форму «Пусть x будет someValue». Эти псевдонимы похожи на ссылки в том смысле, что и x, и someValue относятся к одним и тем же базовым данным, и модификации любого из них видны обоим. Шаги алгоритма, которые хотят избежать этого ссылочного поведения, должны явно делать копию правой части: «Пусть x будет копией someValue» создает неглубокую копию someValue.

После объявления псевдонима можно ссылаться на любых последующих шагах, и на него нельзя ссылаться с шагов до объявления псевдонима. Псевдонимы могут быть изменены с помощью формы «Установить x на someOtherValue».

 

Абстрактные операции (Abstract Operations)

Чтобы облегчить их использование в нескольких частях этой спецификации, некоторые алгоритмы, называемые «абстрактными операциями» (abstract operations), именуются и записываются в параметризованной функциональной форме, чтобы на них можно было ссылаться по имени из других алгоритмов. На абстрактные операции обычно ссылаются с использованием функционального стиля приложения, такого как OperationName(arg1, arg2). Некоторые абстрактные операции рассматриваются как полиморфно отправляемые методы абстракций спецификаций, подобных классам. На такие абстрактные операции, подобные методу, обычно ссылаются с использованием стиля приложения метода, такого как someValue.OperationName (arg1, arg2).

 

Операции, управляемые синтаксисом (Syntax-Directed Operations)

«Синтаксически управляемая операция» (syntax-directed operation) — это именованная операция, определение которой состоит из алгоритмов, каждый из которых связан с одним или несколькими производными одной из грамматик ECMAScript. Производство, которое имеет несколько альтернативных определений, обычно будет иметь отдельный алгоритм для каждой альтернативы. Когда алгоритм связан с производством грамматики, он может ссылаться на конечные и нетерминальные символы альтернативы производства, как если бы они были параметрами алгоритма. При использовании таким образом нетерминальные символы относятся к фактическому альтернативному определению, которое сопоставляется при синтаксическом анализе исходного текста. «Исходный текст, сопоставленный» (source text matched by) с грамматическим производством, — это часть исходного текста, которая начинается в начале первого терминала, участвовавшего в сопоставлении, и заканчивается в конце последнего терминала, участвовавшего в сопоставлении.

Когда алгоритм связан с производственной альтернативой, альтернатива обычно отображается без каких-либо грамматических аннотаций «[]». Такие аннотации должны влиять только на синтаксическое распознавание альтернативы и не влиять на связанную семантику альтернативы.

Операции, управляемые синтаксисом, вызываются с помощью узла синтаксического анализа и, необязательно, других параметров с использованием соглашений на этапах 1, 3 и 4 в следующем алгоритме:

1. Пусть status будет SyntaxDirectedOperation из SomeNonTerminal.
2. Пусть someParseNode будет анализом некоторого исходного текста.
3. Выполните SyntaxDirectedOperation для someParseNode.
4. Выполните SyntaxDirectedOperation для someParseNode, передав значение "value" в качестве аргумента.

Если явно не указано иное, все цепные производства имеют неявное определение для каждой операции, которая может быть применена к левому нетерминалу этой продукции. Неявное определение просто повторно применяет ту же операцию с теми же параметрами, если таковые имеются, к единственному правому нетерминалу цепного производства, а затем возвращает результат. Например, предположим, что у некоторого алгоритма есть шаг формы: «Вернуть результат оценки блока Block» и что существует производство:

Block :

{ StatementList }

но операция Оценки (Evaluation) не связывает алгоритм с этим производством. В этом случае операция Оценки (Evaluation) неявно включает ассоциацию в форме:

Runtime Semantics: Evaluation

Block : { StatementList }

1. Вернуть результат оценки StatementList.

 

Семантика времени выполнения (Runtime Semantics)

Алгоритмы, определяющие семантику, которая должна вызываться во время выполнения, называются «семантикой времени выполнения» (Runtime Semantics). Семантика времени выполнения определяется абстрактными операциями или операциями, управляемыми синтаксисом. Такие алгоритмы всегда возвращают запись о завершении.

Неявные значения завершения (Implicit Completion Values)

Алгоритмы этой спецификации часто неявно возвращают Записи Завершения, [[Type]] которых является normal. Если иное не очевидно из контекста, оператор алгоритма, который возвращает значение, не являющееся записью о завершении, например:

1. Вернуть "Infinity".

означает то же, что и:

1. Вернуть NormalCompletion("Infinity").

Однако, если выражение значения оператора «return» является конструкционным литералом Записи Завершения, возвращается результирующая Запись Завершения. Если выражение значения является вызовом абстрактной операции, оператор «return» просто возвращает запись о завершении, созданную абстрактной операцией.

Абстрактная операция Completion(completionRecord) используется, чтобы подчеркнуть, что возвращается ранее вычисленная запись о завершении. Абстрактная операция Completion принимает единственный аргумент, completionRecord, и выполняет следующие шаги:

1. Assert: completionRecord is a Completion Record.
2. Return completionRecord as the Completion Record of this abstract operation.

Оператор «return» без значения на шаге алгоритма означает то же самое, что:

1. Вернуть NormalCompletion(undefined).

Любая ссылка на значение Записи Завершения, которая находится в контексте, который явно не требует полного значения Записи Завершения, эквивалентна явной ссылке на поле [[Value]] значения Записи Завершения, если только Запись Завершения не является Внезапным Завершением.

 

Выбрасывание исключения (Throw an Exception)

Шаги алгоритмов, которые говорят о том, чтобы выбросить исключение, например

1. Вызвать исключение TypeError.

означают то же, что и:

1. Верните ThrowCompletion(вновь созданный объект TypeError).

 

Возврат, если обрыв (ReturnIfAbrupt)

Шаги алгоритма, которые говорят или иначе эквивалентны:

1. ReturnIfAbrupt(argument).

означает то же самое, что и:

1. Если argument является внезапным завершением, вернуть argument.
2. Иначе, если argument является Записью Завершения, установите argument на argument.[[Value]].

Шаги алгоритма, которые говорят или иначе эквивалентны:

1. ReturnIfAbrupt(AbstractOperation()).

означает то же самое, что и:

1. Пусть hygienicTemp будет AbstractOperation().
2. Если hygienicTemp является Внезапным Завершением, верните hygienicTemp.
3. Иначе, если hygienicTemp является Записью Завершения, установите hygienicTemp на hygienicTemp.[[Value]].

Где hygienicTemp недолговечен и отображается только на этапах, относящихся к ReturnIfAbrupt.

Шаги алгоритма, которые говорят или иначе эквивалентны:

1. Пусть result будет AbstractOperation(ReturnIfAbrupt(argument)).

означает то же самое, что и:

1. Если argument является внезапным завершением, вернуть argument.
2. Если argument является Записью Завершения, установите argument на argument.[[Value]].
3. Пусть result будет AbstractOperation(argument).

 

Возврат, если обрыв — сокращения (ReturnIfAbrupt Shorthands)

Вызов абстрактных операций и операций, управляемых синтаксисом, с префиксом значка вопроса ? указывают, что к результирующей Записи о Завершении следует применить ReturnIfAbrupt. Например, шаг:

1. ? OperationName().

эквивалентен следующему шагу:

1. ReturnIfAbrupt(OperationName()).

Точно так же для стиля приложения метода шаг:

1. ? someValue.OperationName().

эквивалентно:

1. ReturnIfAbrupt(someValue.OperationName()).

Аналогично префикс восклицательного знака ! используется, чтобы указать, что следующий вызов абстрактной или синтаксической операции никогда не вернет внезапное завершение и что результирующее поле Записи Завершения [[Value]] должно использоваться вместо возвращаемого значения операции. Например, шаг:

1. Пусть val будет ! OperationName().

эквивалентен следующим шагам:

1. Пусть val будет OperationName().
2. Утверждено: val никогда не бывает внезапным завершением.
3. Если val является Записью Завершения, установите для val значение val.[[Value]].

Операции, управляемые синтаксисом для семантики времени выполнения, используют это сокращение, помещая ! или же ? перед вызовом операции:

1. Выполнить ! SyntaxDirectedOperation для NonTerminal.

 

Статическая семантика (Static Semantics)

Бесконтекстные грамматики не обладают достаточной мощью, чтобы выразить все правила, определяющие, образует ли поток входных элементов действительный Сценарий или Модуль (Script или Module) ECMAScript, который может быть оценен. В некоторых ситуациях требуются дополнительные правила, которые могут быть выражены либо с использованием соглашений об алгоритмах ECMAScript, либо с использованием требований прозы. Такие правила всегда связаны с производством грамматики и называются «статической семантикой» (static semantics) производства.

Статические семантические правила имеют имена и обычно определяются с помощью алгоритма. Именованные статические семантические правила связаны с грамматическими произведениями, и продукция, имеющая несколько альтернативных определений, обычно будет иметь для каждой альтернативы отдельный алгоритм для каждого применимого именованного статического семантического правила.

Особый вид статического семантического правила — это «правило ранней ошибки» (Early Error Rule). Правила ранней ошибки определяют условия ранней ошибки (см. Раздел 17), которые связаны с конкретными грамматическими произведениями. Оценка наиболее ранних правил ошибок не вызывается явно в алгоритмах этой спецификации. Соответствующая реализация должна перед первой оценкой Сценария или Модуля (Script или Module) проверить все правила производств ранних ошибок, используемых для синтаксического анализа этого сценария или модуля. Если какое-либо из правил ранней ошибки нарушено, Сценарий или Модуль (Script или Module) недействительны и не могут быть оценены.

 

Математические операции (Mathematical Operations)

Эта спецификация ссылается на следующие виды числовых значений:

  • Математические значения (Mathematical values): произвольные действительные числа, используемые в качестве числового типа по умолчанию.
  • Расширенные математические значения (Extended mathematical values): математические значения вместе с +∞ и -∞.
  • Числа (Numbers): значения с плавающей запятой двойной точности IEEE 754-2019.
  • Большие целые числа (BigInts): значения ECMAScript, представляющие произвольные целые числа во взаимно-однозначном соответствии.

На языке данной спецификации числовые значения различаются среди различных числовых типов с помощью суффиксов нижнего индекса. Нижний индекс 𝔽 относится к числам, а нижний индекс относится к BigInts. Числовые значения без суффикса нижнего индекса относятся к математическим значениям.

Числовые операторы, такие как +, ×, = и , относятся к этим операциям, как определено типом операндов. Применительно к математическим значениям операторы относятся к обычным математическим операциям. Применительно к Numbers операторы ссылаются на соответствующие операции в IEEE 754-2019. Применительно к BigInts операторы относятся к обычным математическим операциям, применяемым к математическому значению BigInt.

Как правило, когда эта спецификация относится к числовому значению, например, во фразе «длина y» или «целое число, представленное четырьмя шестнадцатеричными цифрами …», без явного указания числового вида, фраза относится к математическому значению. Фразы, которые относятся к Number или значению BigInt, явно аннотируются как таковые; например, «Числовое значение для количества кодовых точек в…» или «значение BigInt для…».

Числовые операторы, применяемые к операндам смешанного типа (таким как Число и математическое значение), не определены и должны рассматриваться в данной спецификации как редакционная ошибка.

Эта спецификация обозначает большинство числовых значений в «base 10»; она также использует числовые значения формы «0x», за которыми следуют цифры 0-9 или буквы A-F в качестве значений с основанием 16 (base-16).

Когда термин «целое«(integer) используется в этой спецификации, он относится к математическому значению, которое находится в наборе целых чисел, если не указано иное. Когда в данной спецификации используется термин «целое число» (integral Number), он относится к Числовому значению, математическое значение которого находится в наборе целых чисел.

Преобразования между Математическими Значениями и Числами или BigInts всегда явным образом указаны в этом документе.

Преобразование математического значения или расширенного математического значения x в число обозначается как «Числовое значение для x» или 𝔽(x) и определено в пункте 6.1.6.1.

Преобразование целого x в BigInt обозначается как «значение BigInt для x» или (x).

Преобразование Number или BigInt x в математическое значение обозначается как «математическое значение x» или (x).

Математическое значение +0𝔽 и -0𝔽 является математическим значением 0. Математическое значение «не-конечных» значений не определено. Расширенное математическое значение (extended mathematical value) x является математическим значением x для конечных значений и равно +∞ и -∞ для +∞𝔽 и -∞𝔽 соответственно; это не определено для NaN.

Математическая функция abs(x) выдает абсолютное значение x, которое равно —x, если x <0, и в противном случае является самим x.

Математическая функция min(x1, x2,…, xN) производит математически наименьшее из значений от x1 до xN. Математическая функция max(x1, x2, …, xN) производит математически наибольшее из значений от x1 до xN. Область и диапазон этих математических функций представляют собой расширенные математические значения.

Обозначение «x по модулю y» (y должно быть конечным и отличным от нуля) вычисляет значение k того же знака, что и y (или ноль), так что abs(k) < abs(y) и xk = q × y для некоторого целого q.

Фраза «результат зажатия(clamping) x между нижним lower и верхним upper» (где x — расширенное математическое значение, а lower и upper — математические значения, такие, что lowerupper) дает значение «lower», если x < lower, дает upper, если x > upper, и в противном случае производит x.

Математическая функция floor(x) дает наибольшее целое (ближайшее к +∞), которое не превышает x.

Математические функции min, max, abs и floor не определены для Numbers и BigInts, и любое использование тех методов, которые имеют аргументы нематематического значения, было бы редакционной ошибкой в этой спецификации.

Примечание

floor(x) = x — (x modulo 1).

 

Обозначение Значения (Value Notation)

В этой спецификации значения языка ECMAScript выделены жирным шрифтом. Примеры включают null, true или «hello«. Они отличаются от более длинных последовательностей кода ECMAScript, таких как Function.prototype.apply или let n = 42; .

Значения, которые являются внутренними для спецификации и не наблюдаются напрямую из кода ECMAScript, обозначаются шрифтом без засечек (sans-serif). Например, поле [[Type]] записи о завершении принимает такие значения, как normal, return или throw.

 

Информационные ссылки

Условные обозначения

Стандарт ECMAScript — Раздел «5.2 Algorithm Conventions» — https://tc39.es/ecma262/#sec-algorithm-conventions

Поделись записью