Высший пилотаж
20 февраля 2004
Рубрика: Технологии.
Автор: Юрген Берлет.
pic

Функциональное программирование

Как известно, существует несколько разновидностей программирования: алгоритмическое, структурное, управляемое данными, управляемое событиями, объектно-ориентированное, логическое и функциональное. А также существуют уровни программирования. От низкого, то есть уровня железа: прямой адресации регистров, шин данных, команд, портов и так далее. И до высокого, когда программа пишется в нотации, близкой к математической, и впоследствии переводится на машинный язык, чтобы выполниться. Есть также и высший уровень — это функциональное программирование. Почему высший?

Да потому, что такое программирование не только относится к высокому уровню, но и ко всему прочему, с помощью функциональной составляющей можно формулировать задание компьютеру в любой разновидности программирования, с помощью алгоритмов, объектов, управления данными или событиями, а также в логической форме. По своей сути функциональное программирование является самым универсальным, и ширина охвата здесь ограничена разве что ресурсами компьютера. Хотя есть еще одно серьезное ограничение — человеческий фактор, то есть можно было бы и больше, да мышление программиста уже не позволяет. Почему? Потому что наше мышление интерактивно, и мы оцениваем будущее по текущей обстановке, основываясь на предыдущем опыте. Но даже не пытаемся вычислить все возможные варианты, а интуитивно хватаемся за тот, который внешне схож с уже испытанными. А компьютерный менталитет рекурсивен: то есть, ничего не зная о прошлом, он по текущей обстановке попытается, с помощью рекурсии перечисляя все возможные варианты, их подварианты и подварианты подвариантов, отбрасывать те направления, которые в конечном итоге не приводят к нужному результату. И так до тех пор, пока этот самый результат не будет достигнут или все варианты не будут перебраны. Установлено, что человеческое мышление при рекурсии глубины уже четвертого уровня просто запутывается. Это несложно проверить, если попробовать проанализировать шахматную партию на несколько ходов вперед. Отсюда становится понятным, что компьютер не может обладать нашим мышлением, хотя и мы не можем обладать компьютерным. Впрочем, ни одной, ни другой стороне такое обладание ни к чему. Ведь если возникнет необходимость рекурсивно просчитать возможные варианты, то мы можем для этой цели использовать компьютер. Хотя чаще всего используем не по назначению, вроде бы гвозди им не забиваем, но тем не менее.
Если вернуться к программированию, то оказывается, что функциональное построено только на рекурсии и по сей день является универсумом по возможностям рекурсивной обработки. Другие разновидности программирования — это скорее компьютерное моделирование нашей же ментальной ограниченности, а потому они весьма узки в своих сферах, как инвалид в своей коляске.

pic

Существовало (поскольку остальные вымерли) несколько реализаций функционального программирования. Из них осталась только одна — Lisp. Причем этот динозавр Юрского периода информатики не только пережил своих конкурентов по функциональности, но и всех своих ровесников из иных направлений и даже очень многих их потомков.
Датой рождения Lisp является 1958 год, когда профессор по связи из Массачусетского технологического института (MIT) Дж. Маккарти сформулировал и реализовал первые функции этого языка CAR, CDR, CONS, ATOM, EQ и лямбду Черча (функцию без имени). Уже в 1960 году благодаря усилиям Маккарти и Марвина Минского появилась первая среда программирования, причем не только для Lisp, но и вообще, поскольку ничего подобного в информатике еще не существовало. В том же году выходит первая версия Lisp-1, публикуется первая статья по нему, а также его первый выход за границу США — в Великобританию. Дальнейшее распространение Лисп можно сравнивать разве что с распространением компьютерных вирусов, с той лишь разницей, что они имеют конструктивную направленность, поскольку рано или поздно, но он доходил до различных точек земного шара, с успехом преодолевая государственные, финансовые и технические границы и преграды. Помимо всего этого Лисп получил еще одно преимущество, которым могут похвастаться не многие технологии программирования, — аппаратную поддержку, причем не только на уровне чипов или отдельных платок (первый такой чип LSI «Lisp on a Chip» был изготовлен в 1978 году), а целых интегрированных вычислительных комплексов, названных Лисп-машинами, производившихся компаниями Xerox, Lisp Machine Inc. (LMI) и Symbolics Inc., Texas Instruments из США, а также компанией Фуджицу из Японии. Впрочем, Лисп в то время оказывал огромное влияние на развитие вычислительной техники в целом, так как все, что не подходило для работы с ним, теряло практический, а соответственно и коммерческий интерес.

Вполне резонно спросить: почему столь бурное развитие Лисп-систем в те времена не дошло до наших дней? Оно дошло, причем успешно. То, что я описываю, являлось достоянием немногих избранных, а точнее, академической среды и в особенности математиков. По сей день сохраняется та же самая тенденция, и Лиспом интересуются только специалисты. То, что мы не видим Лисп в каждом компьютере сегодня, является причиной того, что вычислительная техника перестала быть уделом профессионалов и приблизилась к пользователям, которым не то чтобы программирование, а даже настройка компьютера может стать непреодолимым препятствием. В лучшем случае пользователь встретится с Лиспом в среде AutoCAD, команды и диалоги которого реализованы на AutoLisp, или в многофункциональном редакторе (X)Emax, который полностью написан на Лиспе. Но и в том, и в другом случаях для использования подобных приложений вовсе не обязательно знать функциональное программирование или какое-либо еще, да и вообще можно даже не догадаться о том, с какой «интеллектуальной начинкой» приходится иметь дело.
Частенько распространяется мнение о том, что репутация Лиспа «пострадала» от провальных проектов искусственного интеллекта. Это недоразумение. Пострадало логическое программирование, а в частности язык Пролог — язык управления реляционными базами данных, который сегодня прекрасно заменяется SQL. Причем следует учесть, что сами проекты были заведомо провальными, так как еще задолго до появления первых компьютеров в 1931 году К. Геделем была доказана вторая теорема о неразрешимости формальных систем, под которую подпадает логическое программирование, и не только оно. Поэтому было бы удивительно, если бы нашумевший в восьмидесятые годы прошлого столетия международный бум «Создания машин Пятого поколения», в основу которого легло уже доказанное противоречие, стал реальностью. Фактом остается то, что Лисп к этому проекту не имел никакой причастности. К тому же существует еще одно важное обстоятельство: вторая теорема Геделя не распространяется на функциональное программирование, потому что последнее выходит за рамки формальных систем — теории чисел Пеано. Третья особенность тех событий заключалась в том, что «искусственный интеллект» в подобных проектах был лишь прикрытием, а в реальности преследовались иные цели и иные достижения: в числе инициаторов всегда были электронщики, а не программисты, и каждый очередной «кризис» искусственного интеллекта, как следствие, ознаменовывался бурным развитием электроники. Ну, а поскольку Лисп не может быть заведомо провальным, то его в таких случаях не используют. Ну и, наконец, чтобы уже закрыть эту тему, следует уточнить, что самого понятия искусственный интеллект не существует. Термин есть, а формулировки нет. Дело доходит до абсурда, когда на какой-нибудь конференции по искусственному интеллекту вдруг начинают выяснять, а что же это такое, и прения переходят в ожесточенный спор. В результате оказывается, что все проекты, включая машины «пятого поколения», имели целевое назначение, формулируемое, как в сказке: «Мы создадим то, сами не знаем что!».
Что больше всего навредило Лиспу, так это результат его же собственного бурного распространения в виде множества различных реализованных диалектов, которые несовместимы друг с другом. И как итог, чтобы программу, созданную для одного из диалектов, запустить в иной версии, нередко приходится ее не просто исправлять, а переписывать заново. Чтобы избавиться от подобных недоразумений, был создан стандарт, названный Common Lisp. Но его жесткие ограничения вызвали скорее возмущение многих пользователей, заметивших отсутствие некоторых привычных функций из какого-либо диалекта. Поэтому Common Lisp существует лишь в подгружаемых библиотеках функций и макросов к различным реализациям, и при необходимости можно ими воспользоваться. К сожалению, эта возможность чаще всего остается неиспользованной.

pic

Многие утверждают, что писать программы на Лиспе очень трудно. Уверяю вас, что это не так. Формулировать задачу с помощью Лиспа намного проще, чем с помощью Бейсика. И здесь, скорее, скажется обманчивая «легкость», приписываемая Бейсику, которая очень быстро раскрывается, когда переходишь к задачам более емким, нежели лабораторная работа по информатике. Ведь программист должен только сформулировать задачу, в то время как подстановка данных и решение — прерогатива конечного пользователя.
Поэтому сложилась устойчивая практика, особенно в коммерческой области, когда крупный проект создают и отлаживают на Лиспе, а потом, выяснив, в каком направлении программирования его можно реализовать, переписывают на другой язык и компилируют приложения уже для конечного пользователя и с соответствующим интерфейсом. Существует и множество других промежуточных технологий формулировок задач, но Лисп здесь, пожалуй, лидирует, практически не имея конкурентов.
Конечно же, может возникнуть резонный вопрос, о том, почему же Лисп не используется так широко программистами? Могу ответить, что используется и гораздо шире, чем вы даже представляете. Просто у обывателя сложилось мнение, что программист — это прыщавый очкарик, который ведет базу данных для бухгалтерии (я не говорю о США, где под словом программист могут иметь в виду любого пользователя, освоившего работу с любым программным пакетом или даже не пользователя, а настройщика или аникейщика. Например, программист текстового редактора MSWord.). В некотором роде это тоже программисты. Но по большому счету разработка и создание баз данных — это ремесло, которое может дать стабильный кусок хлеба. А программирование — искусство, которое может не дать копейку сегодня, но с лихвой окупится завтра.
Коли речь коснулась бухгалтерии, то Лисп долгое время вообще был непригоден для этой области — в нем не было реализовано четыре элементарных арифметических действия, без которых бухгалтер, как без рук. Но, даже несмотря на это, уже тогда он был инструментом для математиков, поскольку с успехом позволял обрабатывать алгебру, дифференцирование, интегрирование и прочую высшую математику. Разве это возможно? Возможно, и не только это. Первые системы общения компьютера с человеком на человеческом же языке тоже были созданы на Лиспе. Все дело в том, что это язык символьной обработки, и ему без разницы, что там символами записано: слова, числа, математические операции и так далее. Если в обычном алгоритмическом языке, чтобы решить уравнение, вам необходимо реализовать соответствующий алгоритм, причем для каждого вида уравнений свой, то в Лиспе все намного проще, так как достаточно только ввести с клавиатуры эти самые уравнения и получить в результате формулу, которая может включать в себя и неизвестные (!!!). По сути с его помощью можно упрощать математические выражения и не только математические, при этом даже не решая их. Именно эта особенность и является основным козырем Лиспа, поскольку остальные технологии могут лишь претендовать на узкоспециальную часть.
То же самое и с лингвистикой. Вы думаете, что компьютер способен общаться с человеком? В некотором роде, да. Например, выдать сообщение об ошибке, после того как слишком поздно. На самом деле «человекоподобные» беседы — это фокус наподобие циркового, поскольку программа даже не имеет понятия, о чем идет речь, и разбираться не станет. Создаются такие поделки очень просто. Имеется база данных, в которой собраны реальные диалоги людей, например из интернетовских чатов. Вы вводите какую-либо фразу. А компьютер «проводит ее смысловой анализ» на предмет встречаемости так называемых регулярных выражений. Ищет в своей базе что-либо схожее, а то, что различается, подбирает из ваших же фраз. Такой алгоритм называется унификацией и используется в логическом программировании. В результате получается некий суррогат, схожий со «смысловой» беседой, который рано или поздно раскрывается, если продолжить развивать эту же тему и не дать компьютеру эту тему сменить. Это, конечно же, игрушки. Более того, зная эту кухню, нетрудно понять, почему логическое программирование не может претендовать на роль заменителя человека, коли оно является всего лишь разновидностью формального шулерства и не подразумевает даже попытки осмысления.
Что касается рекурсии основного козыря компьютера перед человеком, то здесь Лисп также примитивен, поскольку в нем реализован лишь простейший полный перебор всех вариантов, включая подварианты. Но такая ситуация запросто исправляется — достаточно немного добавить в программу, определив несколько функций, и заведомо бесполезные варианты отбрасываются, даже не поступая в список на рассмотрение. Причем делается это весьма изящно. Да и все, что относится к Лиспу, это изящество, изысканность, виртуозность. И даже эти высокопарные выражения не в полной мере отражают то, что можно на нем творить.

pic

Ну и, наконец, сам процесс программирования. Лисп — диалоговый язык, в нем можно программировать, постепенно общаясь с компьютером. Процесс этот, скорее, похож на игру. Почему? Потому что структура Лиспа — это своего рода элементы некоего конструктора — атомы, которые можно сцеплять друг с другом, для чего у каждого элемента есть по две ссылочные связи для последующих элементов — CAR и CDR. Программист составляет из атомов структуру и передает ее в процессе диалога компьютеру. Тот, в свою очередь, берет ее и интерпретирует, то есть команды выполняет, а символы вычисляет. Например, если символ — это запись числа, то он вернет его таким, как есть. Если слово, то в ассоциативном списке будет найдено значение, которое ему соответствует. Если список, то первый — атом — это команда, а остальные команды перед выполнением следует вычислять. Причем результат таких вычислений это не просто одна цифра или последовательность таковых, а опять же набор атомов, сцепленных друг с другом. Ведь команды Лиспа — это команды его конструктора, которые могут брать элементы списков, отделять, присоединять и заменять их на другие. Чем-то похоже на компьютерную игру: сначала программист сооружает атомарную конструкцию, потом компьютер, потом опять программист и так далее, пока, в конце концов, не получится конечный результат. Есть еще одна возможность, а именно взять и записать всю задачу в виде текста программы, а компьютеру передать на выполнение. Такой вариант часто используют для тестирования крупных проектов, и если произошла ошибка, то интерактивно общаясь с компьютером, можно ее тут же исправить, а не обращаться к разработчику. Все, что нужно знать, так это то, что означают надписи на атомах и правила «игры». Многие «знатоки» могут заявить, что не все так гладко, как я описываю, поскольку интерфейс предполагает знание обратной польской записи. Но не так страшен черт, как его малюют — польская запись не сложнее, а намного понятнее, нежели правила игры «Цивилизация». Зато конструирование атомов Лиспа не уступает по азарту любой стратегической игрушке. Да и, наверное, не только приятно, но еще и более полезно общаться с диалоговой системой Лисп, нежели часами торчать в интернет-чатах. Самое главное — цель оправдывает средства.
Маккарти (McCarthy) Джон (родился 4.9.1927, Бостон), американский ученый, специалист по теории ЭВМ, математической логике, языкам программирования ЭВМ, искусственному интеллекту. В 1948 году окончил Калифорнийский технологический институт. Работал в исследовательских и учебных центрах Принстона, Дартмута, Станфорда, в Массачусетском технологическом институте. С 1962 года профессор Станфордского университета. Автор одного из языков программирования (LISP), используемого при решении ряда сложных задач на ЭВМ. Член ряда научных ассоциаций, занимающихся теорией ЭВМ, методами вычислений.

Orphus system
Подписывайтесь на канал infoCOM.UZ в Telegram, чтобы первыми узнавать об ИКТ новостях Узбекистана
В Telegram
В WhatsApp
В Одноклассники
ВКонтакте