Теория вычислений для программистов

Знаете ли вы, что такое язык программирования (ЯП)? Не торопитесь с ответом – может статься, что вы заблуждаетесь! Русскоязычная Wikipedia дает следующее определение этому понятию: «ЯП – формальная знаковая система, предназначенная для записи программ. ЯП определяет набор лексических, синтаксических и семантических правил, определяющих внешний вид программы и действия, которые выполнит исполнитель (обычно – ЭВМ) под ее управлением». В общем, это вполне приемлемое определение: краткое, емкое, но, увы, не понятное. Не верите? В таком случае давайте перечитаем это определение еще раз, но помедленнее.

Том Стюарт ISBN: 978-5-94074-979-0 Издательство «ДМК Пресс», 2013 http://dmkpress.com/catalog/computer/ programming/978-5-94074-979-0/

Что такое «формальная», что такое «знаковая» и что такое, наконец, «система»? Кто такой «исполнитель» и что именно он «выполняет»? Любой из этих терминов, в свою очередь, с неизбежностью вынуждает нас все глубже и глубже погружаться в новые и новые определения. Эти новые определения наслаиваются друг на друга подобно коржам в торте «Наполеон» или, скорее, перепутываются как спагетти. В конце концов, до нас доходит, что все это, так или иначе, связано с математикой. Более того, это все – и знак, и система, и формализм, и выполнение, и исполнитель – и есть математика. Правда, не школьная математика, которая наводила скуку на большинство школьников. Это – область математики, которая называется теорией вычислимости.

Теория вычислимости – это сравнительно молодая дисциплина, ей нет еще 100 лет, что для математики – младенческий возраст. Первые значимые результаты были получены норвежцем Торальфом Скулемом (1887-1693) в 1923 году, который показал, как, имея в своем распоряжении несколько самых что ни на есть элементарных арифметических операций, можно построить очень широкий набор функций (арифметических, алгебраических и проч.). Это было интересно, местами даже забавно, но не рассматривалось математиками тех лет, как нечто совершенно новое.

Однако, менее чем 10 лет, в 1931 году австриец Курт Гедель (1906-1978) подхватил идеи Скулема и с их помощью доказал две поразительные и неожиданные теоремы о неполноте арифметики: в арифметике существуют истинные, но не доказуемые средствами самой арифметики утверждения. А вот это уже была настоящая революция, после которой математика ужи никогда не была прежней. До Геделя математики верили, что рано или поздно, но для любой математической задачи будет найдено доказательство; после Геделя они стали куда менее категоричными. Конечно, с появлением результатов Геделя, математика не закончилась и не остановилась в своем развитии, но Геделю удалось показать, что математика сложнее (а в чем даже коварнее), чем это казалось. Эта сложность носит не столько технический, сколько фундаментальный характер, касающийся самих основ мышления и рассуждений в математике. И вот тут началось…

Работы Геделя стимулировали математиков заново исследовать самые привычные и знакомые едва ли не с пеленок понятия. Если уж «исхоженная» вдоль и поперек арифметика оказалась такой коварной, то что говорить о более сложных разделах? Так родилась теория вычислимости. Ее рождение было ярким и красивым. Один только список имен тех, кто работал в этой области, внушает почтение – Алонзо Черч, Стивен Клини, Алан Тьюринг, Эмиль Пост, Андрей Марков (мл.), Петр Новиков, Анатолий Мальцев. Они и их коллеги в течение двадцати лет после публикации результатов Геделя создали то, что мы называем сегодня теорией вычислимости. И, кстати, очень «удачно» этот период теоретических исследований совпал с появлением первых настоящих компьютеров. Оказалось, что теория вычислимости – это теоретическая основа программирования. Такое случается не часто – когда теория и практика развиваются практически одновременно и когда они взаимно обогащают друг-друга идеями, проблемами и их решениями.

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

К сожалению, книг, посвященных введению в теорию вычислимости без утомительных для начинающего математических подробностей, совсем не много. Тем приятнее то, что издательство «ДМК-Пресс» перевело и выпустило книгу английского специалиста Тома Стюарта «Теория вычислений для программистов». Эта относительно небольшая книга на ряде сквозных примеров достаточно полно демонстрирует сущность теории.

Автор начинает свое изложение с провокационного вопроса – «В чем смысл слова «смысл»?». В первой части книги перед читателем постепенно, очень аккуратно, но совсем не скучно разворачивается интригующая последовательность понятий, которые детально иллюстрируются примерами листингов на языке программирования Ruby. Автор касается достаточно сложных тем, таких, как денотационная семантика, формальная семантика, конечные автоматы (при этом особое внимание уделяется недетеминированным конечным автоматам), регулярные выражения (regexp-ы) и их реализации. После того, как читатель, под руководством автора, убеждается в том, что конечные автоматы имеют фундаментальные ограничения, вводятся автоматы с магазинной памятью (проще говоря – автоматы со стековой памятью) и демонстрируются лексический и синтаксический анализ конструкций языков программирования. Завершается первая часть книги вполне традиционно – обсуждением и программированием машин Тьюринга.

Вторая часть книги начинается с введения в лямбда-исчисление Алонзо Черча. Здесь автор аккуратно и постепенно демонстрирует построение языка программирования из которого убраны практически все привычные нам конструкции. На первый взгляд может показаться, что на таком языке программирования вообще нельзя написать никакой хоть чуточку полезной программы, но вскоре читатель с удивлением обнаруживает, что даже такой язык способен на все, что позволяют самые что ни на есть развитые языки программирования. Соответствующая глава так и называется «Программирование на пустом месте». Цель этой главы – научиться ценить то малое, что есть и уметь обходиться этим малым.

Следующая глава посвящена ряду интересных примеров. Здесь читатель продолжит знакомство с лямбда-исчислением, комбинаторами, частично-рекурсивными функциями, таг-системами. Заканчивается глава рядом примеров клеточных автоматов – игра «Жизнь» Джона Конвея и несколько вариантов т.н. «машин Вольфрама».

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

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

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

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

Книга прекрасно переведена. Единственное на что можно было бы посетовать, так это то, что в названии книги использовано слово «вычисление» вместо слова «вычислимость»; последний термин несколько точнее выражает смысл и определенно более распространен. Но в остальном нельзя не отметить прекрасной работы переводчика А.Слинкина, который не только прекрасно справился с переводом, но и способствовал более ясному изложению весьма сложной темы своими немногочисленными, но уместными и ценными примечаниями.

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

Наконец, отдельная благодарность издательству «ДМК-Пресс», которое продолжает «баловать» программистов столь изысканной интеллектуальной кухней.