25 min

«An algorithm must be seen to be believed».

— Donald Knuth,

«The Art of Computer Programming», 1968¹

Глава 3.4: Алгоритмы "под капотом"

В этой главе хочется рассказать о том, что из себя представляют алгоритмы спецификации ECMAScript, зачем они нужны, как их правильно читать и понимать. Отдельное внимание стоит уделить сокращениям и, так называемым, вариантам записей "for notational convenience". Верное прочтение алгоритмов спецификации крайне необходимо с точки зрения понимания, как работают внутренние механизмы языка ECMAScript.

Боль современности

В наши дни люди привыкли представлять работу JavaScript, как некоторую "магию за кадром". Всех начинающих разработчиков учат запоминать результаты тех или иных операций или их цепочек, причём зачастую не имеющих ничего общего с языком. Делается это для ускоренного обучения, так как всем хочется пораньше избавить себя от теоретической рутины и наконец, будучи преисполненным в своём нелёгком умственном труде, "подойти к веб-станку". У всего этого есть своя неприятная подоплёка.

Человеческий мозг безумно ленив — это факт! На этом играют многие веб-ресурсы, предлагая быстрые знания с гарантией их "качественного" применения. Обычно там можно встретить выражения, типа "выучить за 1 час", "быстро и без лишней воды", "лёгко и доступно", "через несколько месяцев сможете брать заказы на фрилансе", "20% теории и 80% практики", "сможете показать диплом работодателю" и многие другие...

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

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

В итоге многие из таких людей намного позже, уже с большим опытом разработки на JavaScript, к сожалению, на подсознательном уровне не способны прийти к самостоятельной мысли, чтобы задаться логичным вопросом: "А что же на самом деле представляет из себя мой язык программирования?"

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

Теория

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

В computer science

Перед полноценным изучением алгоритмов спецификации языка ECMAScript необходимо понять, какое отражение они получили в современном мире. Что вообще такое алгоритм?

In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing.

~ wiki

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

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

Также важно отметить, что алгоритм по своей сути не обязательно должен использоваться только лишь при абстрактном описании решений. Сегодня вполне вероятно алгоритмически описать просто какой-нибудь отдельный процесс. Например, кто-то идёт на работу, и теоретически он может описать, какие шаги он предпринимает для того, чтобы выйти из дома и дойти до офиса. То есть, собрав воедино свои мысли и действия, отобразить это в каком-то общем алгоритмическом представлении.

Существует бесконечно много вариантов представления алгоритмов. Но как-то же должны регулироваться общие подходы к их описанию? Давайте обратимся к мировому опыту:

As an effective method, an algorithm can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function.

~ wiki

Из цитаты следует понимать, что эффективным методом представления алгоритма в общем виде является формат уже известного нам formal language. В одной из глав про формирование принципов этого языка подробно расписана вся теоретическая мысль данного подхода. Каждый человек при составлении алгоритма сам определяет, каким будет его formal language, или выбирает уже существующие успешные системы представления, например блок-схемы (flowchart) или реализация с помощью машины Тьюринга (Turing machine).

В программировании

Что ж, давайте немного отойдём от теоретической информатики и поговорим более приближённо про алгоритмизацию в программировании. Как в этой области представлены общий опыт и практики.

Boolos, Jeffrey & 1974, 1999 define an algorithm to be a set of instructions for determining an output, given explicitly, in a form that can be followed by either a computing machine or a human who could only carry out specific elementary operations on symbols.

~ wiki

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

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

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

Note

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

Алгоритмы ECMAScript

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

Несоответствие реализации

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

Грамматика

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

Example

Abstruct operation ToPrimitive() algorithm

Если детально изучить представленное изображение, мы увидим один большой алгоритм — ToPrimitive(). Наверху обычно представлен заголовок, в данном случае это абстрактная операция — один из вариантов представления алгоритмов. На картинке сам алгоритм.

Разбиение на шаги

Шаги (Steps) алгоритма ECMAScript могут быть разделены на последовательные подшаги (Substeps). Об этом будут свидетельствовать видимая внутренная вложенность и нумерация того или иного шага и его подшага. Так как все алгоритмы инкапсулированы по отношению друг к другу, вводимые по ходу сущности будут доступны только внутри него самого и только после объявления.

На картинке видно, что строки начинаются с цифр или букв. Это шаги и подшаги, соответственно.

Параметризация

Любой алгоритм имеет потенциальную возможность принимать какие-то внешние данные от других алгоритмов через параметры (Parameters). Вместе с этим существуют варианты передачи результатов из одних алгоритмов в другие. Они регулируются параметризацией. На страницах спецификации параметры чаще всего следуют сразу после названия операции в круглых скобках. Всего выделяют три вида параметров:

• Required: обозначаются простым словом. Например, ToPrimitive(input), где input — обязательный параметр.
• Optional: обозначаются словом в квадратных скобках с запятой. Например, ToPrimitive(input [, prefferedType]), где [, prefferedType] — необязательный параметр.
• Rest: обозначаются в самом конце всех параметров словом с многоточием. Собирает все аргументы, идущие после вышеуказанных в отдельный тип List, изначально пустой. Например, ToPrimitive(input [, prefferedType], ...name), где ...name — текущий rest-параметер.

На картинке абстрактная операция ToPrimitive принимает два параметра: required — input и optional — [, prefferedType].

Предикаты

Алгоритмы могут иметь вариативность шагов или по-простому разветвления. Для этого в спецификации ввели некое обозначение под названием предикат (Predicate). Всего выделяют два вида предикатов:

• If и Else: нужны для разветвления шага на несколько подшагов; определяют условие, с выполнением которого происходит выполнение подшагов шага If, а с невыполнением — шага Else . Например, 1. If input is an Object, then.
• Assert: нужен просто для пояснения алгоритмов; вводит некоторое ожидание для значения; определяет всегда истинное инвариантное условие с одним искусственным разветвлением. Например, 1. Assert: prefferedType is NUMBER.

На картинке представлен алгоритм, в котором присутствуют, как If / Else, так и Assert предикаты.

Псевдонимы

Алгоритмам необходимо всегда взаимодействовать с какими-либо значениями. Они могут быть внешними, пришедшими с параметрами или просто глобальными в рамках спецификации, и внутренними. Доминирующее превосходство по частоте использования одерживают внутренние, и с ними важно правильно взаимодействовать. Для этого были придуманы именованные псевдонимы (named aliases).

Они по своей природе реализуются в формате reference-like, что определяет их схожесть в поведении с ссылками (Reference). Эта схожесть заключается в том, что псевдоним указывает на те же данные, что и любая приводимая в той же строке далее конструкция. Проще всего это можно понять на примере:

Named alias declaration/modification

На этой картинке в первой строке представлена типичная инициализация псевдонима x. Исходя из механизма их работы, согласно спецификации, как x, так и someValue обязаны указывать на одну и ту же структуру данных, а изменение одного из них необратимо должно привести к аналогичному изменению другого. После объявления псевдонима на него можно ссылаться на любых последующих и только последующих шагах. Обозначается как Let x be someValue. Подобное этому отображено и на картинке.

Алгоритмы призваны быть гибкими, поэтому жёсткая сцепка двух сущностей одной стуктурой данных не всегда является достаточным. Так был придуман принцип инициализации псевдонима, при котором он ссылается не на уже лежащие в основе данные другой сущности, а на специально созданную копию данных сущности, по сути, становясь самой копией. В таком случае модификация одной из сущностей никак не скажется на другой. Обозначается как Let x be a copy of someValue. Такой вариант показан во второй строке.

Ну и для модификации псевдонимов, чтобы указать ему, на какие новые данные необходимо теперь ссылаться, существует конструкция вида Set x to someOtherValue. Этот вариант показан в третьей строке.

Значения

Иногда в алгоритмах можно встретить некоторые значения в bold стиле шрифта. В таком случае речь будет идти о ECMAScript language value. Например, есть алгоритм, в котором выделенные значения являются просто LiteralExpressions языка ECMAScript:

1. Let str be "hello".
2. Let num be 2.
3. If x is not undefined, then

Так, на картинке нам представлены такие значения в количестве пяти штук.

Выход

По своему определению алгоритм — это конечная последовательность инструкций. В качестве итога всегда выступает слово Return, благодаря чему алгоритм выходит с каким-то определённым результатом. Обычно форма возвращаемого результата приводится в описании к операции.

На картинке мы видим пример трёх явных выражений Return и одного неявного в строке Throw a TypeError exception., являющейся очередным сокращением "for notational convenience", которое внутри себя содержит тот же Return.

Виды представления

На страницах спецификации существует три вида представления алгоритмов. Под представлением подразумевается то, в каком виде они реализованы и как используются. Давайте рассмотрим их детальнее:

Note

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

Syntax-directed operations

Синаксически-ориентированная (Syntax-directed) операция представляет из себя артефакт спецификации², необходимый для связывания различных синтаксических конструкций и лежащих в их основе алгоритмов. Это наиболее частый вариант представления из указанных.

Самым известным примером syntax-directed операции является Runtime Semantics: Evaluation, благодаря которой описано внутреннее поведение всех возможных синтаксических конструкций ECMAScript.

Также большинство операций, выполняющихся перед фактическим выполнением кода на этапе Runtime Semantics, тоже имеют syntax-directed природу и входят в состав Static Semantics — некоторый набор правил в помощь к сложившейся production-системе определения валидности потоков токенов для дальнейшей оценки.

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

Abstruct operations

Абстрактная операция (Abstruct operation) представляет из себя очередной артефакт спецификации, необходимый для облегчённого описания алгоритмов. В данном случае справедливо будет провести параллель с декларативным стилем программирования, в котором предпочтение отдаётся разбиению кода на смысловые части, имеющие общую самостоятельную компонентно-инкапсулированную логику, а не поочерёдному выполнению примитивных операций, как в императивном стиле.

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

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

Так, в спецификации мы можем наблюдать уже известный нам пример абстрактной операции ToPrimitive().

Methods

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

Так, например, в спецификации с помощью тех же самых алгоритмов представлена работа метода bind().

К выводу

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

• Современное изучение JavaScript зачастую имеет поверхностную неглубинную природу, никак не связанную с реальным положением вещей. Тема алгоритмов "под капотом" заменяется на частичное запоминание распространённых случаев.
• На самом деле алгоритмы внутренней машинерии языка ECMAScript — базовое ядро на пути к полноценному пониманию работы языка.
• Для алгоритмов введена своя грамматика, помогающая структуризировать их написание и понимание. Можно уверенно сказать, что она далеко не идеальная, до сих пор находят баги спецификации. И да, можно было сделать её более "человеческой".
• Алгоритмы имеют три распространённые формы представления, каждая из которых образует свой принцип описания языка.
• Грамматика алгоритмов не ограничивается базовыми правилами. Их верное прочтение невозможно без знания "продвинутых" обозначений.

Footnotes

1. Фраза из известной монографии «The Art of Computer Programming», представленной в 1968 году американским учёным в области математики и информатики — профессором Дональдом Кнутом. Этот труд до сих пор на завершён и продолжает писаться. ↩

2. Артефакт спецификации — термин, присущий именно самой спецификации без необходимости реализации. Стоит его рассматривать исключительно как сущность языка спецификации ECMAScript и не более. ↩