Представитель Шуры Люберецкого в ЖЖ (brat_luber) wrote,
Представитель Шуры Люберецкого в ЖЖ
brat_luber

Category:

Математика, логика и программирование. Часть вторая, про 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 – последний является интересным примером реализации “чистого” лямбда-исчисления, не допускающего побочных эффектов. В нем отсутствуют такие привычные “императивным” программистам понятия, как переменные и присваивания – а для “неминуемых” операций с побочными эффектами, вроде ввода-вывода, применяются так называемые “монады”.

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

Запись опубликована в блоге Шуры Люберецкого. Вы можете оставлять свои комментарии там, используя свое имя пользователя из ЖЖ (вход по OpenID).

Tags: программирование
Subscribe

  • Про гиков

    Прочитал статейку на Look at Me под совершенно прекрасным заголовком – “ Гики в России: Как стать свободным в стране, которой ты не…

  • Про майданобесие

    Иногда просматриваю в твиттере несколько аккаунтов, которые ведут вроде бы нормальные люди, но при этом активно поддерживающие (поддерживавшие?)…

  • По делам их узнаете их

    Наблюдаю за реакцией различных политически активных персонажей на штурм мятежного Славянска и вообще события на востоке Украины и в Одессе. Стоит…

Comments for this post were disabled by the author