Что такое стек и как он используется в JavaScript? И как это связано с Magic: the Gathering?
Как заядлый игрок в чрезвычайно популярную карточную игру Magic: the Gathering, я уже был знаком с концепцией, известной как стек, в контексте за пределами компьютера. программирование. Когда однажды во время учебного курса по веб-разработке в Lighthouse Labs я услышал о стеке, упомянутом лектором, я подумал: «Эй, я слышал об этом раньше. ”Я и не подозревал, насколько похожи концепции в Magic и вычислениях.
Итак, что такое «стек»? В Магии это процесс, с помощью которого произносятся заклинания (вызов магических существ, бросание огненных шаров, управление временем, воскрешение мертвых, вызов природы, общение с духами… такие классные вещи), ответы на них и решено. В вычислениях это структура данных, в которой данные и задачи хранятся и решаются. В обоих случаях стек является примером структуры данных типа Первый пришел - последний ушел (FILO).
Что это обозначает? Типичная аналогия - представить стопку бумаг или стопку книг на столе: вы кладете одну поверх другой, и если вы хотите убрать одну, вы начинаете с самого верхнего предмета и продвигаетесь вниз. Концепция стека повсеместно используется в вычислениях и относится к линейной структуре данных, которая используется для хранения объектов; объекты обычно добавляются действием «push» и удаляются действием «pop». Их также можно просмотреть, не удаляя их, используя действие «взглянуть». В JavaScript основной используемый стек называется стеком вызовов и относится к способу разрешения функций.
Объекты обычно добавляются в стек действием «выталкивания» и удаляются действием «выталкивания».
Другой тип структуры данных, используемый в JavaScript, - это структура очередь или Первый пришел - первый ушел (FIFO) - типичный пример из реальной жизни. быть в очереди в банке: первый человек в очереди - первый обслуживаемый. В вычислительной технике типичным примером является то, как файлы отправляются в очередь печати для печати: файлы печатаются в том же порядке, в котором они отправляются. В JavaScript очередь или FIFO-подобная структура используется для цикла событий - как обрабатываются асинхронные события, - но мы рассмотрим это позже в этой статье (это не строго система FIFO, как вы увидите).
Последняя структура данных, используемая в JavaScript, о которой мы сегодня будем говорить, называется куча, и это в значительной степени неструктурированная область памяти, которая используется для хранения объектов и переменных. По крайней мере, для целей этой статьи вам не так много нужно знать о куче.
Но возвращаясь к стеку, я собираюсь объяснить эту концепцию немного иначе, чем обычно: используя аналогию с магическими заклинаниями, которые произносятся и на которые реагируют дуэльные волшебники, путешествующие по измерениям. Аккуратный.
Magic: the Gathering (или просто MTG) - коллекционная карточная игра, изобретенная в 1993 году, в которую играют более двадцати миллионов игроков по всему миру. Он был создан американским математиком Ричардом Гарфилдом, что могло бы объяснить некоторые совпадения между концепциями в игре и областями математики и вычислений. Игра известна своей чрезвычайной глубиной и сложностью, и недавно было доказано, что она полная по Тьюрингу; это выходит за рамки данной статьи, но довольно интересно, и вы можете прочитать об этом здесь, если хотите . Я большой поклонник игры, она содержит красиво простую, но глубокую жизненную философию в виде цветного колеса l , И это даже помогло мне понять некоторые ключевые концепции программирования во время учебного лагеря.
Цель игры - уменьшить количество жизней вражеского волшебника (известного как planeswalker) до 0, начиная с 20 или 40 жизней (в зависимости от того, какой вариант игры ведется). Это достигается комбинацией заклинаний урона и способностей, атак существами и другими действиями. В этой статье я сосредоточусь на разыгрывании заклинаний, поскольку именно здесь стек вступает в игру.
На диаграмме выше показано, как заклинания и способности добавляются в стек в MTG. Вы можете думать о каждом игроке, добавляющем заклинания в стек, как о том, как JavaScript подталкивает функции к стеку вызовов для выполнения. Это не идеальная аналогия, но давайте рассмотрим сходства дальше с помощью кода.
Взгляните на следующий код JavaScript, уделяя особое внимание порядку файлов console.log ():
(Примечание: этот пример немного упрощен для целей этой аналогии. На самом деле console.log () также помещается в стек, как и main () контекст выполнения, внутри которого выполняется весь этот код. Чтобы глубже погрузиться в контекст выполнения, ознакомьтесь с этой статьей, в которой это объясняется гораздо глубже.)
Если вы прочитаете этот код сверху вниз, вы можете подумать, что console.log () появятся в выводе терминала сверху вниз в том же порядке, в котором они появляются в коде. Тем не менее, это не так. Давайте посмотрим, в каком порядке они фактически появляются в выводе:
Игрок 1 разыгрывает "Удар молнии"!
Игрок 2 применяет Контрзаклинание, нацеливая Удар молнии Игрока 1.
Больше нет заклинаний. Начните разбирать стек.
Контрзаклинание разрешается и нейтрализует Удар Молнии!
Удар молнии отменяется и удаляется из стека.
Так что здесь происходит? Давайте рассмотрим это шаг за шагом.
Первоначально стек вызовов пуст. Функции определены, но еще не вызваны.
castLightningBolt();
Внизу файла вызывается первая функция, которая помещается в стек вызовов. Первый console.log () выводит:
Игрок 1 разыгрывает "Удар молнии"!
function castLightningBolt() {
console.log('Player 1 casts Lightning Bolt!');
castCounterspell();
console.log('Lightning Bolt is countered and removed from the stack.');
}
Стек вызовов теперь содержит одну функцию / заклинание. Однако перед запуском второго console.log () вызывается следующая функция: castCounterspell ().
function castCounterspell() {
console.log('Player 2 casts Counterspell, targeting Player 1’s Lightning Bolt.');
resolvePhase();
console.log('Counterspell resolves and counters Lightning Bolt!');
}
Как и раньше, castCounterspell () помещается в стек вызовов, и печатается первый console.log () в функции castCounterspell ():
Игрок 2 применяет Контрзаклинание, нацеливая Удар молнии Игрока 1.
Стек вызовов теперь выглядит так:
Перед печатью второго console.log () в castCounterspell () вызывается функция resolvePhase () и нажимается в стек вызовов.
function resolvePhase() {
console.log('No further spells to cast. Begin resolving the stack.');
}
Поскольку в теле функции больше нет вызовов функций, она переходит к печати:
Больше нет заклинаний. Начните разбирать стек.
После полного выполнения resolvePhase () выталкивается из вершины стека.
Теперь оставшиеся функции в стеке начинают разрешать одну за другой в обратном порядке, в котором они были вызваны и извлечены из стека вызовов.
Итак, как вы можете видеть из последовательности журналов выше, функция castCounterspell () выводит свой второй console.log () - тот, который после вызов resolvePhase () - в консоль, затем удаляется из стека, после чего следует функция castLightningBolt (), выполняющая то же самое:
Контрзаклинание разрешается и нейтрализует Удар Молнии!
Удар молнии отменяется и удаляется из стека.
Стек теперь пуст; в MTG это приводит к окончанию фазы. В JavaScript это означает, что выполнение кода завершено.
(Обычно функции имеют вывод return, но функции в этом примере просто выводят текст на консоль.)
Стек вызовов имеет максимально достижимый размер (в браузере Chrome это 16 000 кадров); если размер стека превышает это значение, будет выдано сообщение об ошибке, и браузер выйдет из строя с сообщением Достигнута максимальная ошибка стека. Обычно это происходит из-за того, что функция входит в бесконечный цикл, а также может быть продемонстрировано с помощью карт Magic.
Посмотрите следующие карточки и посмотрите, получите ли вы их:
Теперь прочтите это в коде:
Как вы, вероятно, догадались, вызов ping () запускает цикл путем вызова exquisiteBlood (), который вызывает sanguineBond (), который вызывает exquisiteBlood (), который вызывает sanguineBo…. ты понял.
Это приводит к мгновенной победе игрока 2 и консольному выводу:
...15,995 lines of the same output above...
Player 2 gained one life. Player 1 loses one life.
Player 1 lost one life. Player 2 gains one life.
Player 2 gained one life. Player 1 loses one life.
Player 1 lost one life. Player 2 gains one life.
Player 2 gained one life. Player 1 loses one life.
_stream_readable.js:896
Readable.prototype.removeListener = function(ev, fn) {
RangeError: Maximum call stack size exceeded
at WriteStream.Readable.removeListener (_stream_readable.js:896:45)
at Object.Console.<computed> (internal/console/constructor.js:245:12)
at Object.log (internal/console/constructor.js:282:26)
at sanguineBond (/Users/commoddity/lighthouse/w8/d5-writing/mtg-infinite.js:14:10)
at exquisiteBlood (/Users/commoddity/lighthouse/w8/d5-writing/mtg-infinite.js:10:2)
Этот беспорядок кода в конце называется трассировкой стека и может быть чрезвычайно полезен для отладки. Обычно он содержит информацию, полезную для программиста, чтобы точно определить, что и где пошло не так.
Асинхронные функции и цикл событий
Этот цикл событий, о котором я упоминал ранее, представляет собой способ обработки асинхронных функций в JavaScript. Если вы не знаете, что это такое, вы можете прочитать отличное введение в концепцию асинхронности здесь.
По сути, почти все интернет-приложения в какой-то момент будут содержать код, который полагается на данные или ввод, которые могут возвращаться или происходить в неопределенное время. Поскольку JavaScript является однопоточным и блокирующим, это означает, что ему нужен способ работать с этими фрагментами кода, не останавливая весь блок кода, который он пытается. бежать. Если бы ему пришлось ждать каждой части этих неопределенных данных или ввода перед переходом к следующей строке, это могло бы занять очень много времени, или, возможно, никогда не запуститься; это плохо для пользователя и, следовательно, для программиста. Здесь на помощь приходит Цикл событий.
Когда вызывается асинхронная функция, она помещается в очередь, называемую очередью обратного вызова, где ожидает выполнения остальной части программы. Когда остальная часть (синхронного) кода завершится, функции в очереди обратного вызова будут выполняться , если данные, от которых они зависят, вернулись или произошло событие, которого они ждут . Помните, я сказал, что цикл событий использует структуру данных, подобную FIFO?
Функции в очереди обратного вызова будут выполняться в определенном порядке, но только при соблюдении их конкретного условия .¹
Если функция все еще ожидает выполнения условия, вместо нее будет запущена следующая функция в очереди, а пропущенная функция будет возвращена позже.
Если это все немного сбивает с толку, ничего страшного. Может быть, еще одна аналогия с Magic: the Gathering поможет прояснить это (не беспокойтесь о понимании всего текста правил на этих карточках).
Эффект Turn to Mist похож на асинхронную функцию; другими словами, он выталкивается из стека вызовов в очередь обратного вызова. Это показано в примере с помощью функции setTimeout () для имитации асинхронного поведения.
Имея это в виду, рассмотрим следующий код:
Как и в нашем первом примере, никакие функции не вызываются до последних двух строк программы. В этот момент вызывается castTurnToMist (), который печатает:
Игрок 1 разыгрывает Turn To Mist.
Удалите целевое существо из игры.
Затем для переменной saddlebackLagacInPlay устанавливается значение false.
Следующая после нее строка кода - это наша функция setTimeout (), которая ведет себя так, как если бы она была асинхронной, то есть она помещается в очередь обратного вызова. и разрешится по прошествии не менее 5000 миллисекунд², распечатайте его console.log () и установите для saddlebackLagacInPlay значение true .
setTimeout(() => {
phase = 'end of turn';
saddlebackLagacInPlay = true;
console.log(`Return target creature to play at ${phase}.`);
}, 5000);
// This function simulates the behaviour of an asynchronous function // by pushing its execution outside the call stack and into the
// event loop. In a real async function, this would be because the // function waits for data from a network request or user input.
На этом завершается тело функции castTurnToMist (), поэтому она выталкивается из стека вызовов.
Теперь вызывается castFireball (), направленный на бедного Saddleback Lagac. castFireball () условно печатает текст на основе логического значения s addlebackLagacInPlay, которое в настоящее время по-прежнему false.
const castFireball = () => {
if (saddlebackLagacInPlay === true) {
console.log('Saddleback Lagac targeted by Fireball.')
} else {
console.log('Invalid target. Saddleback Lagac is not in play.');
}
};
Несмотря на то, что функция setTimeout () была вызвана перед castFireball () в коде, она действует асинхронно, поэтому весь остальной код должен выполняется до того, как он сможет разрешиться из очереди обратного вызова.
Таким образом, saddlebackLagacInPlay по-прежнему false и castFireball () напечатает:
Неверная цель. Сэддлбек Лагак не участвует в игре .³
Через пять секунд мы видим следующее, напечатанное на консоли, когда тело функции setTimeout () разрешается из своего места в очереди обратного вызова:
Верните целевое существо в игру в конце хода.
[1] Подробнее о точном порядке читайте в этой статье.
[2] Если быть точным: 5000 миллисекунд плюс время, необходимое для выполнения синхронного кода, который должен быть выполнен до того, как очередь обратного вызова сможет начать работу.
[3] Если бы не функция setTimeout () в castTurnToMist (), весь код выполнялся бы синхронно. Это означает, что при вызове castFireball () saddlebackLagacInPlay был бы оценен как true, а castFireball () напечатал бы:
Седловик Лагак стал целью Огненного шара.
Я надеюсь, что этот пример сделал асинхронные функции и поведение цикла событий в JavaScript более понятным. Если нет, не волнуйтесь; это сложная тема, и может потребоваться больше чтения и опыта, чтобы прояснить ее. Статьи, на которые есть ссылки в этой статье, скорее всего, дадут более глубокое понимание темы, если вы захотите прочитать больше.
© 2020, Паскаль ван Леувен
Ссылки
Понимание выполнения функций Javascript - стек вызовов, цикл событий, задачи и многое другое - Гаурав Пандвиа, Средний
Стек вызовов - Веб-документы MDN
Стек (абстрактный тип данных) - Википедия
Стеки и очереди | Структуры данных в JavaScript - beiatrix, YouTube
The Stack: Last in, first out - Разъяснение механики ретро-игры, YouTube
