Решение забавной задачки на JavaScript

Наша история начинается с твита Томаша Лакомы, в котором он предлагает представить, что такой вопрос встретился вам на собеседовании.

Мне кажется, что реакция на такой вопрос на собеседовании зависит от того, в чём конкретно он заключается. Если вопрос действительно в том, каково значение tree, то код можно просто вставить в консоль и получить результат.

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

Я стримил процесс решения этой задачи в Twitch. Трансляция долгая, но она позволяет ещё раз взглянуть на процесс пошагового решения таких задач.

Общие рассуждения

Во-первых, приведём код в вид, пригодный для копирования:

let b = 3, d = b, u = b;
const tree = ++d * d*b * b++ +
 + --d+ + +b-- +
 + +d*b+ +
 u

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

В первой строке просто создаются три переменные, которым присваивается значение 3. 3 — это примитивное значение, поэтому при каждом создании копии она создаётся по значению, поэтому все новые переменные создаются со значением 3. Если бы JavaScript присваивал значения этим переменным по ссылке, то каждая новая переменная указывала бы на предыдущую использованную переменную, но не создавала себе значения.

Дополнительная информация

Приоритет операторов и ассоциативность

Это ключевые концепции для решения данной ужасающей задачи. Если говорить вкратце, они определяют порядок, в котором вычисляется сочетание выражений JavaScript.

Приоритет операторов

Вопрос: в чём разница между этими двумя выражениями?

3 + 5 * 5

5 * 5 + 3

С точки зрения результата разницы нет. Любой, кто помнит школьные уроки математики, знает, что умножение выполняется перед сложением. На английском мы запоминаем порядок как BODMAS (Brackets Off Divide Multiply Add Subtract — скобки, степень, деление, умножение, сложение, вычитание). В JavaScript есть такая же концепция, называемая «приоритетом операторов» (Operator Precedence): она означает порядок, в котором мы вычисляем выражения. Если бы мы хотели принудительно вычислять первым 3 + 5, то сделали бы следующее:

(3+5) * 5

Скобки заставляют вычислять эту часть выражения первой, потому что приоритет оператора () выше, чем у оператора *.

Каждый оператор JavaScript имеет приоритет, поэтому при наличии такого большого количества операторов в tree нам нужно понять, в каком порядке они будут вычисляться. Особенно важно, что -- изменит значения b и d, поэтому нам нужно знать, когда эти выражения вычисляются относительно остальной части tree.

Важно: Таблица приоритетов операторов и дополнительная информация

Ассоциативность

Ассоциативность используется для определения того, в каком порядке выражения вычисляются в операторах с равным приоритетом. Например:

a + b + c

В этом выражении приоритета операторов нет, потому что имеется только один оператор. Так как же его нужно вычислять — как (a + b) + c или как a + (b + c)?

Я знаю, что результат будет одинаковым, но компилятору нужно это знать, чтобы он мог выбрать сначала одну операцию, а затем продолжить вычисления. В данном случае правильным ответом будет (a + b) + c, потому что оператор + левоассоциативный, то есть он сначала вычисляет выражение слева.

«Почему бы просто не сделать все операторы левоассоциативными?», — можете спросить вы.

Что ж, давайте рассмотрим такой пример:

a = b + c

Если мы воспользуемся формулой левоассоциативности, то получим

(a = b) + c

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

a + b = c

Это преобразуется в (a + b) = c, то есть сначала a + b, а потом значение этого результата присваивается переменной c.

Если бы нам пришлось думать таким образом, JavaScript был бы гораздо более запутанным, и именно поэтому мы используем различные ассоциативности для разных операторов — это повышает удобство чтения кода. Когда мы читаем a = b + c, порядок вычисления кажется нам естественным, несмотря на то, что внутри всё устроено более хитро и используются право- и левоассоациативные операнды.

Вероятно, вы заметили проблему ассоциативности в a = b + c. Если оба оператора имеют разную ассоциативность, то как узнать, какое выражение вычислять первым? Ответ: то, которое имеет более высокий приоритет оператора, как и в предыдущем разделе! В данном случае, + имеет больший приоритет, поэтому вычисляется первым.

В конце статьи я добавил более подробное объяснение, или же вы можете прочитать дополнительную информацию.

Разбираемся, как вычисляется наше выражение tree

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

Скобки

Здесь стоит упомянуть, что правильное добавление скобок — сложная задача. Я проверил, что ответ на каждом из этапов вычисляется правильно, но это не гарантирует, что мои скобки всегда расставлены верно! Если вы знаете инструмент для автоматической расстановки скобок, то напишите мне.

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

Постфиксный ++ и постфиксный --

const tree = ++d * d*b * (b++) +
 + --d+ + +(b--) +
 + +d*b+ +
 u

Унарный +, префиксный ++ и префиксный --

Здесь у нас есть небольшая проблема, но я начну с вычисления унарного оператора +, а уже потом мы дойдём до проблемной точки.

const tree = ++d * d*b * (b++) +
 + --d+ (+(+(b--))) +
 (+(+(d*b+ (+
 u))))

И здесь возникают сложности.

+ --d+

-- и +() имеют одинаковый приоритет. Как же нам узнать, в каком порядке их вычислять? Давайте сформулируем проблему в более простом виде:

let d = 10
const answer = + --d

Помните, что + здесь означает не сложение, а унарный плюс, или положительность. Можно воспринимать это как -1, только здесь это +1.

Решение заключается в том, что мы вычисляем справа налево, потому что операторы этого приоритета правоассоциативны.

Итак, наше выражение преобразуется в + (--d).

Чтобы разобраться в этом, попробуйте представить, что все операторы одинаковы. В данном случае + +1 будет эквивалентно (+ (+1)) согласно логике, что 1 — 1 — 1 эквивалентно ((1 — 1) — 1). Обратили внимание, что результат правоассоциативных операторов в записи со скобками противоположен случаю с левосторонними?

Если применить ту же логику к проблемной точке, то мы получим следующее:

const tree = ++d * d*b * (b++) +
 (+ (--d)) + (+(+(b--))) +
 (+(+(d*b+ (+
 u))))

И, наконец, вставив скобки для последнего ++, мы получим:

const tree = (++d) * d*b * (b++) +
 (+ (--d)) + (+(+(b--))) +
 (+(+(d*b+ (+
 u))))

Умножение (*)

Нам снова придётся иметь дело с ассоциативностью, но на этот раз с одинаковым оператором, являющимся левоассоциативным. По сравнению с предыдущим шагом это должно быть легко!

const tree = ((((++d) * d) * b) * (b++)) +
 (+ (--d)) + (+(+(b--))) +
 (+(+((d*b) + (+u))))

Мы дошли до этапа, на котором уже можно начинать вычисления. Можно было бы добавить скобок для оператора присваивания, но я думаю, что это больше запутает, чем упростит чтение, поэтому не будем этого делать. Обратите внимание, что показанное выше выражение — это всего лишь чуть более усложнённое x = a + b + c.

Мы можем сократить некоторые унарные операторы, но я сохраню их на случай, если они важны.

Разделив выражение на несколько частей, мы можем понять отдельные этапы вычислений и отталкиваться от них.

let b = 3, d = b, u = b;
 
const treeA = ((((++d) * d) * b) * (b++))
const treeB = (+ (--d)) + (+(+(b--)))
const treeC = (+(+((d*b) + (+u))))
const tree = treeA + treeB + treeC

Сделав это, мы можем начать исследовать вычисление разных значений. Начнём с treeA.

TreeA

let b = 3, d = b, u = b;
const treeA = (((++d) * d) * b) * (b++)

Первое, что здесь будет вычислено — это выражение ++d, которое выполнит возврат 4 и инкремент d.

// b = 3
// d = 4
((4 * d) * b) * (b++)

Далее выполняется 4*d: мы знаем, что на данном этапе d равно 4, поэтому 4*4 равно 16.

// b = 3
// d = 4
(16 * b) * (b++)

На этом шаге интересно то, что мы собираемся умножить на b до выполнения инкремента b, потому то вычисление производится слева направо. 16 * 3 = 48.

// b = 3
// d = 4
48 * (b++)

Выше мы говорили о том, что ++ имеет более высокий приоритет, чем *, поэтому это можно записать в виде 48 * b++, но тут есть и другие хитрости — возвращаемое значение b++ является значением до инкремента, а не после. Поэтому хоть в конечном итоге b становится равным 4, умножаемое значение будет равно 3.

// b = 3
// d = 4
48 * 3
// b = 4
// d = 4

48 * 3 равно 144, поэтому после вычисления первой части b и d равны 4, а результат выражения равен 144

let b = 4, d = 4, u = 3;
 
const treeA = 144
const treeB = (+ (--d)) + (+(+(b--)))
const treeC = (+(+((d*b) + (+u))))
const tree = treeA + treeB + treeC

TreeB

const treeB = (+ (--d)) + (+(+(b--)))

На этом этапе мы видим, что унарные операторы на самом деле ничего не делают. Если мы сократим их, то значительно упростим выражение.

// b = 4
// d = 4
const treeB = (--d) + (b--)

Мы уже видели этот трюк выше. --d возвращает 3, а b-- возвращает 4, но к моменту вычисления выражения обоим будет присвоено значение 3.

const treeB = 3 + 4
// b = 3
// d = 3

Итак, теперь наша задача выглядит примерно так:

let b = 3, d= 3, u = 3;
 
const treeA = 144
const treeB = 7
const treeC = (+(+((d*b) + (+u))))
const tree = treeA + treeB + treeC

TreeC

И мы почти закончили!

// b = 3
// d = 3
// u = 3
const treeC = (+(+((d*b) + (+u))))

Давайте для начала избавимся от этих надоедливых унарных операторов.

// b = 3
// d = 3
// u = 3
const treeC = (+(+((d*b) + u)))

Избавились, но тут нужно быть аккуратнее со скобками и т.п.

// b = 3
// d = 3
// u = 3
const treeC = (d*b) + u

Теперь всё довольно просто. 3 * 3 равно 9, 9 + 3 равно 12, и наконец, у нас остался…

Ответ!

let b = 3, d= 3, u = 3;
 
const treeA = 144
const treeB = 7
const treeC = 12
const tree = treeA + treeB + treeC

144 + 7 + 12 равно 163. Ответ на задачу: 163.

Заключение

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

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

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

Даже если знаешь, как решить задачу, существует множество синтаксических неоднозначностей, с которыми нужно разобраться по пути. И я уверен, что многие вы заметили, изучая наше выражение tree. Я перечислил некоторые из них ниже, но каждая из них стоит отдельной статьи!

Также мне хотелось бы поблагодарить https://twitter.com/AnthonyPAlicea,, без курса которого мне ни за что не удалось бы разобраться во всём этом, и https://twitter.com/tlakomy для этот вопрос.

Примечания и странности

Я выделил мини-загадки, которые встречались мне по пути, в отдельный раздел, чтобы процесс поиска решения оставался прозрачным.

Как влияет изменение порядка переменных

Посмотрите это видео

let x = 10
console.log(x++ + x)

Здесь можно задать несколько вопросов. Что будет выведено в консоль и каково значение x во второй строке?

Если вы считаете, что это то же число, то извините, я вас обхитрил. Хитрость заключается в том, что x++ + x вычисляется как (x++) + x, и когда движок JavaScript вычисляет левую часть (x++), он выполняет инкремент x, поэтому когда дело доходит до + x, значение x равно 11, а не 10.

Ещё один хитрый вопрос — какое значение возвращает x++?

Я дал довольно очевидную подсказку о том, что ответом на самом деле является 10.

В этом и заключается разница между x++ и ++x. Если рассмотреть лежащие в основе операторов функции, то они выглядят примерно так:

function ++x(x) {
  const oldValue = x;
  x = x + 1;
  return oldValue;
}
function x++(x) {
  x = x + 1;
  return x
}

Рассматривая их таким образом, мы можем понять, что

let x = 10
console.log(x++ + x)

будет означать, что x++ возвращает 10, и на момент вычисления + x его значение равно 11. Поэтому в консоль будет выведено 21, а значение x будет равно 11.

Эта относительно простая задача указывает на распространённый антипаттерн, используемый во всём коде — перемешанные выражения и побочные эффекты. Подробнее.

Может ли быть два оператора с одинаковым приоритетом, но разными ассоциативностями?

Давайте двигаться по порядку и забудем пока о слове «ассоциативность».

Возьмём операторы + и =, и обобщим ситуацию.

Выше показывалось, что a + b + c вычисляется как (a + b) + c, потому что + левоассоциативен.

a = b = c вычисляется как a = (b = c), поскольку = правоассоциативен. Обратим внимание, что = возвращает значение присвоенное переменной, поэтому a будет равно тому, чему равно b после вычисления выражения.

Заменим операнды на их приоритет:

a left b left c = (a left b) left c
a right b right c = a right (b right c)

но что насчёт

a left b right c = ?
a right b left c = ?

Видите, что вторые примеры логически невозможны? a + b = c возможен только потому, что + имеет приоритет перед =, поэтому парсер знает, что делать. Если два оператора имеют одинаковый приоритет, но разную ассоциативность, то парсер синтаксиса не сможет определить, в каком порядке выполнять действия!

Итак, подведём итог: нет, операторы с одинаковым приоритетом не могут иметь разную ассоциативность!

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

Унарные операторы

Интересный момент, обнаруженный при разборе порядка вычисления +n и ++n.

Невозможно выполнить -- -i, потому что - возвращает число, а с числами нельзя производить инкремент или декремент, и невозможно выполнить ---i, потому что смысл --- неоднозначен (это -- - или - --? См. комментарии ниже.), но можно сделать так:

let i = 10
console.log(-+-+-+-+-+--i)

Запутанная положительность

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

let i = 10
console.log(i++ + + ++i)

Каждый операнд имеет собственный смысл, приоритет и ассоциативность. Это напоминает мне знаменитую словесную головоломку:

Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo.

Унарные операторы или присваивание?

+ может означать или унарный оператор, или присваивание. Чем он является в случае u задачи из начала статьи?

... +
u

В конечном итоге ответ зависит от… того, что есть. Если бы мы написали всё в одну строку

... + u

то ответ был бы разным для x + u и x - + u. В первом случае символ означает сложение, а во втором — унарный +. Единственный способ разобраться, что он значит — анализировать остальную часть выражения, пока не останется только один оператор, который он может обозначать!

---

На правах рекламы

VDS для программистов с новейшим железом, защитой от атак и огромным выбором операционных систем. Максимальная конфигурация — 128 ядер CPU, 512 ГБ RAM, 4000 ГБ NVMe.

Автор: Mikhail

Источник