Математика, логика и программирование. Часть вторая, про Lisp и функциональное программирование

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

Итак, возвращаемся к «историческому обзору». Разумеется, что первые компьютеры могли «программироваться» только в пресловутых «машинных кодах» или на некотором «мнемоническом» языке — подобии ассемблера. Но написавший таким способом уже две-три программы программист может заметить что-то общее и выделить эти «общие» части в подпрограмму. Дальше хочется автоматизировать способы выделения и вызова этих подпрограмм — для чего служили первые «языки программирования» — наверное, стоит упомянуть названия типа Autocode.

Кстати, уже тогда возникло разделение подпрограмм на процедуры и функции. Процедурой называлась выделенная для многократного использования последовательность действий, функцией — подпрограмма, вычисляющая значение какой-то математической функции.

Своего рода «революцией» стал появившийся в 1958 (а разработка началась в 1954) язык FORTRAN, где предусматривалось преобразование чего-то похожего на математические выражения в машинный код. FORTRAN буквально означает FORmula TRANslator. Думаю, преимущества FORTRAN и более позднего ALGOL над ранними «языками программирования» очевидны, а дискуссия о применении оператора goto вместо конструкций ветвления или цикла все еще отражена в школьных учебниках программирования. Я бы не хотел подробно останавливаться на императивных языках, они всем хорошо известны, а хотел бы перейти к более интересным вещам.

В том же «Логико-философском трактате» (да, мне он очень нравится) содержится, видимо, общепринятая сегодня точка зрения о том, что язык ограничивает возможность выражения мыслей, причем очень интересно сформулированная:

Границы моего языка означают границы моего мира.

Витгенштейн сделал из этого вывод, что вместо «естественного» языка необходим какой-то специальный, освобожденный от неоднозначностей — что-то вроде «языка» математической логики Фреге и Рассела. Правда, особых успехов в этом направлении он не достиг и в своих более поздних работах от этой идеи отказался, перейдя от вопросов построения «правильного» языка к вопросам понимания «естественного». Для нас важно то, что утверждение Витгенштейна остается верным и применительно к языкам программирования. В той же книжке Себесты эта мысль вообще считается самоочевидной, и используется для обоснования того тезиса, что «хороший» программист должен знать несколько языков программирования, желательно разных.

В математической логике довольно важную роль играет теория вычислимости, из результатов которой хотелось бы отметить построенное в 1941 году Черчем лямбда-исчисление. В середине 50-х появились первые попытки «научить» ЭВМ доказывать теоремы по геометрии, после работы Гильберта это казалось хорошей демонстрацией способности компьютера «думать», то есть пользоваться формальной логикой. В 1956 году Ньюэлом, Шоу и Саймоном была создана программа Logical Theorist, а в 1958 году МакКарти, работая в IBM над системой символьных вычислений, пришел к выводу, что комбинация FORTRAN c заложенными в Logical Theorist идеями (называлось это FLPL — FORTRAN List Processing Language, язык обработки списков на базе FORTRAN) окажется нежизнеспособна — и сделал лямбда-исчисление «теоретической базой» нового языка программирования, названного Lisp (от LISt Processor).

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

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

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

С другой стороны, Lisp оказался очень далек от реального аппаратного обеспечения. Более того, в 60-х считалось, что языки программирования делятся на две категории — Lisp и «все остальные». Это было правдой, «все остальные» языки программирования придерживались императивного подхода, в той или иной степени обобщавшего реальное устройство компьютера, то есть «машину фон Неймана». Lisp вообще никак не был привязан к свойствам оборудования, и считался очень неэффективным. Правда, в середине 70-х появились так называемые лисп-машины с аппаратной поддержкой некоторых свойств языка, но они были вытеснены быстро развивавшимися компьютерами общего назначения. «Обычным» применением для Lisp и его более современных диалектов (Scheme и Common Lisp) считается «искуственный интеллект» и связанные с ним задачи — например, представление знаний, машинное обучение, обработка естественных языков и тому подобные задачи. Правда, никто не мешает использовать Lisp и в более «стандартных» областях — например, на Lisp написан текстовый редактор Emacs, Scheme используется в некоторых системах информационной безопасности, на Common Lisp была написана одна из первых в мире систем интернет-магазинов.

Среди других функциональных языков стоит назвать РЕФАЛ (РЕкурсивных Функций АЛгоритмический язык), созданный Валентином Турчиным в 1966 году. Кстати, рекурсия впервые появилась именно в Lisp, и является для функциональных языков «естественной» — тогда как в императивных она оказывается чем-то сложным и чужеродным. Из более современных — ML (возникший, как часть системы доказательства теорем LCF), его «потомков» Caml и OСaml, Erlang — интересный тем, что сразу предназначался для «практического» программирования, Haskell — последний является интересным примером реализации «чистого» лямбда-исчисления, не допускающего побочных эффектов. В нем отсутствуют такие привычные «императивным» программистам понятия, как переменные и присваивания — а для «неминуемых» операций с побочными эффектами, вроде ввода-вывода, применяются так называемые «монады».

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *