Опоздавших не бывает, или книга о стеке

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

ISBN: 978-5-97060-517-2 Вторников Алексей Издательство «ДМК Пресс», 2017 https://dmkpress.com/catalog/computer/ programming/978-5-97060-517-2/

Недавно издательство «ДМК Пресс» представило книгу «Стек, или путешествие туда и обратно», полностью посвященной стеку. В книге рассматривается и подробно разбирается ряд задач нарастающей сложности. Главная особенность этих задач в том, что все они приводят к стеку. Иногда путь, ведущий к решению задачи, оказывается извилистым: то и дело возникают побочные «тропинки», приводящие в тупик. Но из любого тупика есть выход и таким выходом оказывается как раз стек.

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

Проницательный читатель, вероятно, увидел в таком названии сходство со знаменитой книгой Дж.Р.Р. Толкина «Хоббит, или путешествие туда и обратно» («The Hobbit, or There and Back Again»). Это сходство обусловлено тем, что работа со стеком действительно напоминает путешествие туда и обратно. Только теперь действующими лицами являются не хоббит Бильбо Бэггинс в компании с гномами во главе с неутомимым Гэндальфом, а числа и символы, которые то проваливаются в стек («туда»), то выталкиваются из него («обратно»).

Как мы уже упоминали, в книге рассматривается ряд задач возрастающей сложности, приводящих к стеку. Этим задачам посвящена первая и самая важная часть книги. Появление стека всегда тщательно подготавливается; он никогда не появляется ниоткуда, подобно кролику из шляпы. Для этого часто рассматриваются другие варианты решений, без использования стека. Это позволяет не на словах, а на деле (можно даже сказать «на собственной шкуре») сравнить разнообразные подходы и алгоритмы и убедиться в том, что стек – в соответствующих обстоятельствах, разумеется – именно то, что нужно. Для того, чтобы рассматриваемые задачи и их решения не зависели от какого-либо языка программирования, автор использует очень простой ассемблер, включающий в себя всего 7 команд (в основном передачи управления) и пару режимов адресации. Изложение в книге замкнуто: все, что необходимо - объясняется по мере необходимости, а также сопровождается многочисленными и простыми примерами программ, так что книгу могут читать даже те, у кого отсутствует опыт программирования на языках низкого уровня.

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

Читатели, знакомые хотя бы по наслышке, с языком программирования Forth, без труда обнаружат влияние последнего (за одним существенным отличием – в предлагаемом стековом компьютере нет словарей и, соответственно, нет их реализации в виде того или иного варианта т.н. «шитого» кода).

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

Наконец, приложение включает в себя несколько разделов, которые имеют в основном технический характер. Последнее их них содержит указания по компиляции и запуску транслятора и интерпретатора стековой машины, описанной во второй части книги для тех, у кого опыт программирования на Java совсем не велик. Исходные тексты транслятора и интерпретатора (это всего 5 файлов общим объемом чуть больше 700 строк исходного кода) могут быть загружены с сайта издательства «ДМК Пресс».

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

Книга «Стек, или путешествие туда и обратно» предназначена в первую очередь тем, кто уже попробовал «на вкус» что такое программирование и желает двигаться дальше, но кто пока не готов приступить к изучению тяжеловесных и фундаментальных руководств по структурам данных и алгоритмам. Начинающие программисты, студенты первых курсов колледжей, специализирующихся по информатике, а также продвинутые старшеклассники (при условии, что они готовы потрудиться) – вот те, кому в первую очередь предназначена книга. Если они хорошенько разберутся в теории (первая часть книги) и решат задачи (представленные во второй части), то они будут готовы к тому, чтобы попробовать себя в новых областях, где стек раскрывается во всей красоте.

Раздел, посвященный использованию стека для анализа и распознавания грамматик языков программирования, получился несколько конспективным. Впрочем, учитывая популярный характер изложения и то, что книга является по-существу вводным текстом, это вполне объяснимо. Распознавание и анализ синтаксических структур языков программирования – это, действительно, сложный предмет, который требует отдельного изложения и предварительной подготовки (в дополнение к библиографии, предложенной автором, мы хотим порекомендовать еще одну интересную книгу: Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. – М.: Мир, 1979).

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

Одним словом, мы рекомендуем присмотреться к этой книге. Как говорит сам автор «Пусть стек станет вашим другом и помощником».