20 min

«We try to solve the problem by rushing through the design process so that enough time is left at the end of the project to uncover the errors that were made because we rushed through the design process».

— Glenford J. Myers,

«Code Complete»¹

Глава 5: Продвинутые алгоритмы

В этой главе хочется углубиться в тему грамматики языка алгоритмов спецификации ECMAScript. Мы узнаем, что обозначают префиксы ? и !, почему Return true не всегда возвращает true, как обарабатываются ошибки и почему не стоит воспринимать прямо всё то, что вы видите в спецификации.

Note

Далее речь пойдёт не об алгоритмах языка программирования JavaScript в общем их представлении. Здесь будут рассматриваться грамматические уловки языка алгоритмов ECMAScript, которые имеют огромное значение для понимания всей спецификации.

Введение

Благодаря алгоритмам спецификации любой специалист может научиться понимать внутреннюю природу выполнения кода и прогнозировать его поведение. И здесь я говорю больше не о последовательности выполнения того или иного statement-а, а о предложенных спецификацией инструкциях, позволяющих оценить количество и качество происходящих "под капотом" действий, чтобы на их основе оценить возможные затрачиваемые ресурсы и эффективность выбранного метода разработки.

За эффективность выполнения кода отвечает движок V8. На сегодняшний день он способен оптимизировать даже самые неочевидные моменты в любом коде, но всему есть предел. Поэтому задачей любого разработчика на JavaScript является не только знать алгоритмы, лежащие в основе каждой исполняемой операции, но и уметь разрабатывать свои продукты так, чтобы оптимизирующий движок смог безпрепятственно выполнить свою главную задачу — наилучшим образом скомпилировать код.

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

Погружение

Алгоритмы спецификации ECMAScript, ровно как и её грамматика, кажутся обманчиво простыми, но за этой простотой скрываются поистине сложные решения редакторов Ecma. Первый принцип, с которым необходимо начинать рассматривать любую её сущность или артефакт, заключается в изолировании своих знаний — забудьте всё, что приходилось изучать ранее.

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

Загадочный Evaluation of

Одним из сложных и неочевидных моментов в прочтении алгоритмов является конструкция Evaluation of. И почему вообще Evaluation? Давайте рассмотрим пример ниже и попытаемся объяснить, какую роль выполняет эта конструкция.

Equality Operators — RS: Evaluation

Первое, что мы видим на картинке, — стадия выполнения кода ECMAScript под названием Runtime Semantics: Evaluation (далее RS: Evaluation). Иными словами, syntax-directed операция, возвращающая Completion Record. Она гласит нам о том, что для низлежащего production-а во время выполнения кода (а именно во второй стадии выполнения) должен быть применён представленный далее алгоритм. Все эти сущности в достаточной форме можно увидеть на картинке.

Во второй строке представлен уже известный нам production с токеном ==. Очевидно, что в данном случае речь пойдёт об операторе свободного (нестрогого) равенства. Синтаксис задаёт syntactic grammar, указывающий на возможный вариант написания выражения, чтобы парсер смог успешно распознать поток Unicode code points, именно как данное выражение. То есть текущему production-у вполне может соответствовать такое выражение:

5 == 7 // EqualityExpression

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

Дело в том, что при разборе production-а перед нами предстают 3 nonterminal values. И это неслучайно, так как goal symbol (в нашем случае EqualityExpression) не является единственным выполняемым выражением. Согласно спецификации, в любой строке кода, подобной той, что представлена выше, содержится 3 выражения. И для всех трёх выражений необходимо провести этап оценки (RS: Evaluation).

Именно поэтому на этапе Evaluation для представленного на картинке left-hand-side выражения EqualityExpression происходит, как минимум, два этапа Evaluation для двух right-hand-side выражений по обе стороны от ==. То есть для них буквально выполняются те же самые стадии оценки RS: Evaluation, результаты которых, согласно приведённому на картинке алгоритму, связываются с соответствующими псевдонимами для последующих манипуляций.

Алгоритмическая конструкция Evaluation of — эта просто удобное написание, некая отсылка к выполнению syntax-directed операции над далее идущим выражением, с целью предварительной оценки значения перед последующим манипулированием над ним.

Неочевидный Return

Ранее мы установили, что по определению алгоритм — это конечная последовательность инструкций, где в качестве конечного пункта (выход из алгоритма) всегда выступает слово Return, даже если в момент выполнения кода происходит ошибка. Благодаря чему алгоритм всегда выходит с каким-то определённым результатом.

В случае с syntax-directed операциями конструкция Return с единственным исключением всегда возвращает значение, указанное в описании к операции без использования дополнительных proxy-конструкций², о которых дальше пойдёт речь. То есть, если в условно третьей строке выход из алгоритма происходит посредством 3. Return true, такая операция вернёт ожидаемое ECMAScript language value — true.

В случае же с abstruct операциями и тем самым исключением в виде syntax-directed операции RS: Evaluation конструкция Return, согласно спецификации, всегда дополнительно применяет для возвращаемого значения некоторую proxy-конструкцию, которая его полностью изменяет.

Proxy-конструкция

Ещё её можно назвать "промежуточной операцией". В спецификации этот раздел называется Implicit Normal Completion. Это некоторое правило, согласно которому, над возвращаемым значением, перед тем как его вернуть, происходят указанные действия. То есть прежняя конструкция Return true исходя из этого правила превращается в ряд дополнительных шагов:

Implicit Normal Completion

По итогу, согласно этому правилу, любое значение на выходе из алгоритма abstruct операции должно быть завёрнуто в Completion Record и, следовательно, будет использоваться в других алгоритмах именно как Completion Record. Предлагаю рассмотреть этот подход на реальном примере:

Operations on Objects — set the value of a specific property

Перед нами abstruct операция Set(). В её алгоритме представлено два варианта выхода: throw и Return. Первый из них будет разобран позже, поэтому давайте обратим внимание на второй — 3. Return UNUSED. Если бы это была syntax-directed операция, то, вероятнее всего, если в описании не указано иного, было бы возвращено некоторое значение unused типа Enum.

Но в данном случае мы имеем дело с abstruct операцией, так что, согласно правилу Implicit Normal Completion, 3. Return UNUSED будет изменено в 3. Return Completion Record { [[Type]]: NORMAL, [[Value]]: UNUSED, [[Target]]: EMPTY }.

Выбрасываемый throw

Так называемый "выброс исключения" в разных языках программирования отчасти существует таким, каким его привыкли представлять, и в языке ECMAScript. С точки зрения спецификации это не заставляет программу "выпасть в ошибку". На самом деле throw является всего лишь отдельным случаем уже известной нам конструкции Return, который следует отдельному алгоритму:

Throw an Exception under the hood

Как можно заметить, возвращается всё тот же Completion Record, но с другим значением типа Enum внутреннего поля [[Type]] — throw, а объект исключения занимает поле [[Value]] и зависит от соответствующего исключения.

Рассмотренный выше пример соответствует выбросу исключения алгоритмами спецификации языка ECMAScript в результате ошибки компиляции. Но ровно по тому же принципу работает и явный ThrowStatement — команда throw в JavaScript.

Скрытный Mr. ReturnIfAbrupt()

Более сложными грамматическими обозначениями языка алгоритмов являются префиксы ! и ?. Пожалуй, это две самые запутанные конструкции во всех алгоритмах. Их использование можно увидеть на той же картинке, что была выше.

Equality Operators — RS: Evaluation

Здесь представлены 5 шагов алгоритма, и все из них содержат загадочный префикс ?. Обращаю внимание, что он находится строго перед операциями. Чтобы понять, почему он так необходим, важно заглянуть внутрь всех них и узнать, что они возвращают (с каким значением производится выход из алгоритма в результате Return или его скрытого варианта throw).

Нам уже известно, что, согласно спецификации, syntax-directed операция Evaluation of всегда возвращает Completion Record. Аналогичным образом abstruct операции GetValue() и IsLooslyEqual() возвращают, согласно алгоритмам, тот же Completion Record. Ранее мы пришли к осознанию того, что значения с помошью Let ... be ... зачастую связываются с некими alias (псевдонимами). Полчается, в данном случае связывание происходит с теми же сущностями Completion Record? Ответ: нет.

В это месте и проявляется скрытая природа языка алгоритмов. Всё дело в неком алгоритмическом предопределённом переопределении.

Предопределяем исключение с ?

Этим заголовком справедливо будет выразить всю ту машинерию, которая заложена внутри обозначений ? и ! в алгоритмах. Его смысл вы поймёте чуть дальше.

В основе этих двух конструкций лежит логика грамматических сокращений (Shorthands). Рассмотрим работу самого частого их них — префикса ? — на шаблонном примере:

Prefix "?" shorthand under the hood

Как можно заметить, префикс ? просто оборачивает операцию справа в некоторую конструкцию ReturnIfAbrupt(). На этом его миссия, как части языка алгоритмов, завершена. Это всего лишь сокращение для другого алгоритма — вышеупомянутого ReturnIfAbrupt(). Так давайте же посмотрим, какие шаги кроются за ним:

ReturnIfAbrupt under the hood

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

• 1. Let hygienicTemp be AbstractOperation(). — связываем с alias-ом hygienicTemp сущность Completion Record, как результат асбтрактной операции AbstractOperation(). То есть hygienicTemp указывает на те же данные, что и вышеупомянутый Completion Record.
• 2. Assert: hygienicTemp is a Completion Record. — вспомогательный predicate Assert:, указывает семантическое ожидание, какое значение задумывалось обрабатывать этим алгоритмом. В нашем случае это совпало.
• 3. If hygienicTemp is an abrupt completion, return Completion(hygienicTemp). — разветвляющий predicate If, проверяет значение Completion Record на abrupt completion, чтобы в таком случае выйти из нашего алгоритма со значением Completion Record { [[Type]]: ABRUPT, [[Value]]: value, [[Target]]: EMPTY }., где вместо value будет помещён объект исключения.
• 4. Else, set hygienicTemp to hygienicTemp.[[Value]]. — разветвляющий predicate Else, переопределяет (пересвязывает) hygienicTemp alias с помощью конструкции Set ... to ... так, что теперь он указывает на внутреннее поле Completion Record — hygienicTemp.[[Value]] — теперь просто обычный ECMAScript language value.

Исходя из разобранного теоретического примера следует, что в реальном алгоритме после употребления префикса ? происходит оценка возвращаемого abstruct операцией значения. Если это abrupt completion, вернуть его же с объектом исключения; в противном случае переопределить alias и неявно вернуть его со ссылкой на внутреннее поле Completion Record [[Value]].

Благодаря этой машинерии получилось описать целую систему обработки ошибок на любом из шагов алгоритма, хоть она и далеко не идеальная.

Предопределяем отсутствие исключения с !

Для этих же целей используется и префикс !, но немного в другом контексте. Давайте, согласно спецификации, рассмотрим его алгоритм на шаблонном алгоритме:

Prefix "!" shorthand under the hood

• 1. Let val be OperationName(). — связываем с alias-ом val результат некоторой операции (abstruct или syntax-directed).
• 2. Assert: val is a normal completion. — вспомогательный predicate Assert:, указывает семантическое ожидание, какое значение задумывалось обрабатывать этим алгоритмом. В данном случае Completion Record { [[Type]]: NORMAL, [[Value]]: value, [[Target]]: EMPTY }..
• 3. Set val to val.[[Value]]. — переопределяет (пересвязывает) val alias с помощью конструкции Set ... to ... так, что теперь он указывает на внутреннее поле Completion Record — val.[[Value]] — теперь просто обычный ECMAScript language value.

Этот алгоритм гарантирует, что вызов любой операции не вернёт abrupt completion.

К выводу

Подведём итоги вышесказанному и сделаем выводы:

• Алгоритмы не так просты в прочтении, когда дело доходит до глубокого понимания.
• Конструкция Evaluation of — это просто сокращённая запись вызова второй стадии выполения кода RS: Evaluation для отдельного выражения.
• Конструкции Return и throw — это почти идентичные выходы из алгоритмов. В случае с abrupt операциями и одной syntax-directed RS: Evaluation операции для возвращаемого значения применяется proxy-конструкция. Для других такого правила не действует.
• Префиксы ? и ! — сокращённые записи для предопределённой обработки исключений.

Footnotes

1. Фраза из книги Code Complete: практическое руководство по созданию программного обеспечения Стива МакКоннелла ↩

2. Proxy-конструкция — авторский термин, описывающий некоторую внутреннюю машинерию языка, выступающую неявным обработчиком значения, намеренно изменяющим его перед последующим возвращением в другую операцию в рамках отведённых правил. ↩