Lisp: маленький гигант

 АЛЕКСЕЙ ВТОРНИКОВ, ЗАО КБ «Ростовский Универсальный», ведущий программист, pdp8dec@gmail.com

Lisp: маленький гигант

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

Курица – это способ, которым яйцо создает другое яйцо.

Сэмюэл Джонсон

Истоки

В апреле 1960 года в журнале Communications of the Association for Computing Machinery (более известном как CACM) была опубликована 12-страничная статья «Recursive Functions of Symbolic Expressions and Their Computation by Machine. Part I» (часть II так никогда и не появилась). Автором статьи был математик Джон Маккарти, работавший вМассачусетском технологическом институте (Кембридж, США). В статье автор рассказал об итогах своей работы над новым языком для программирования искусственного интеллекта (кстати, именно Маккарти и был автором термина «искусственный интеллект», который в наши дни обезобразили до неудобоваримого «искин»). Справедливости ради нужно сразу же отметить, что Маккарти, являясь, безусловно, главным автором идеи, трудился не в одиночку: у него была небольшая лаборатория, в работе которой активное участие принимали его студенты, участвовавшие в реализации языка и предложившие ряд ценных нововведений.

Структурно статья разделена на три части. В первой части описываются математические формализмы, положенные Маккарти в основу языка (рекурсивные функции и λ-исчисление, разработанное за 20 лет до этого Алонзо Черчем).

Во второй части автор вводит т.н. S-выражения, служащие одновременно и для представления данных и для представления программ, написанных на этом языке. Здесь же вводятся основные операции над S-выражениями и описывается связь S-выражений с формализмами из предыдущей части статьи.

Наконец, в последней части статьи описывается собственно сам язык (по состоянию на февраль 1960 года).

Эта статья и описанный в ней язык стали стартовой точкой целого направления в информатике, известного сегодня как функциональное программирование. Имя языка должно быть известно всякому, кто претендует на звание профессионала, – это, конечно же, Lisp.

Замечание. Этимология названия языка забавна. Сам Маккарти образовал его из слов «LISt Processing», т.е. «обработка списков». Разумеется, это и есть официальное его название. Однако в английском языке слово «lisp» означает «шепелявить», «сюсюкать», что, конечно, послужило поводом для многочисленных, хотя и безобидных, шуток. Но есть еще одна и, надо признать, довольно едкая расшифровка «Lots of Irritating Superfluous Parentheses», т.е. «множество раздражающих лишних скобок» (слово «irritating» нередко заменялось куда более грубым «idiotic»). Причина столь резких нападок на скобки объясняется тем, что в программах на Lisp количество скобок непривычно велико по сравнению с традиционными языками программирования. На первых порах это действительно может раздражать, но очень скоро вы начинаете это ценить: скобки придают программам на Lisp особый стиль, удивительно ясный синтаксис и своеобразный интеллектуальный «аромат».

Значимость Lisp хорошо иллюстрируется хотя бы тем, что он второй (после Fortran) по возрасту активно используемый язык программирования. Подавляющее большинство языков, появившихся в те или даже в более поздние годы, давно и надежно забыты (например, Algol или PL/1). А вот Lisp жив и не просто жив, а еще и весьма «плодовит» – он явился предтечей множества языков программирования, порой на него совершенно не похожих. Более того, многие концепции Lisp были заимствованы не родственными ему языками (например, замыкания, динамическая типизация, каррирование, сборка мусора, анонимные функции). Lisp как никакой другой язык обогатил информатику. С него и с его помощью начались интенсивные исследования семантики (смысла и значения) языков программирования. Даже если вы не будете использовать Lisp в практической деятельности, то все равно полезно хотя бы поверхностно с ним ознакомиться. Но для начала – несколько слов об авторе Lisp.

Об авторе Lisp

Джон Маккарти родился в 1927 году в Бостоне в семье, далекой от математики: его отец был профсоюзным деятелем, мать – журналисткой. У мальчика рано проявились недюжинные математические способности. Будучи еще школьником, Джон приобрел университетские учебники и задачники, самостоятельно их изучил и перерешал все задачи, чтопозволило ему пропустить первые два курса по математике после поступления в Калифорнийский технологический институт (семья к этому времени переехала в Калифорнию). После недолгой военной службы он закончил обучение и многие годы занимался исследовательской работой и преподаванием в ряде ведущих американских университетов (причем в последнем из них – Стэнфордском – он проработал до 2000 года, вплоть до выхода на пенсию).

Математик Джон Маккарти

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

В 1971 году Джон Маккарти был удостоен самой престижной премии в области информатики – премии Тьюринга (с Аланом Тьюрингом, кстати, он был лично знаком). Еготрадиционная лекция на церемонии вручения премии была опубликована (после существенной переработки первоначального варианта) только в 1986 году, но достойна того, чтобы ознакомиться с ней. В ней Маккарти честно и открыто рассказывает о сложностях, возникших при попытках создания искусственного интеллекта (далее – ИИ), и признает, что«системы искусственного интеллекта страдают отсутствием общности». Кроме того, «никто не знает, как создать базу данных, содержащую общеполезные знания об окружающем мире (знания «здравого смысла»), которую могла бы использовать любая программа, нуждающаяся в этих знаниях». Хотя с той поры прошло уже 30 лет, вопросы, поднятые Маккарти продолжают оставаться актуальными.

Кроме премии Тьюринга, Джон Маккарти был удостоен и ряда других престижных научных наград.

Джон Маккарти сотрудничал с советскими математиками, а с А.П. Ершовым (1931-1988) состоял в многолетней переписке и личной дружбе; он неоднократно посещал Советский Союз с лекциями и участвовал в работе ряда проводившихся в СССР конференций и семинаров.

Умер Джон Маккарти в сентябре 2011 года в возрасте 84 лет. Новость о его смерти стала распространяться только спустя несколько дней. Увы, так часто бывает: уход из жизни человека, создавшего одно из самых важных, продуктивных и полезных направлений в программировании, прошел практически незамеченным. Но наследие, оставленное Маккарти, продолжает жить и развиваться. Более того, все свидетельствует о том, что роль функционального программирования будет только расти. Джон Маккарти сам, своими трудами иидеями, создал себе памятник.

Шапочное знакомство с Lisp

Для решения сложных задач, которыми всю жизнь и занимался Джон Маккарти, нужны сильные инструменты. Давайте познакомимся с основными концепциями Lisp: именно здесь лежат все основные идеи. При этом мы будем ориентироваться на ANSI Common Lisp (часто используется сокращение «CL») – самую, пожалуй, распространенную версию языка. Но это не должно служить препятствием к изучению других реализаций (и прежде всего Scheme) – основные принципы остаются неизменными.

Замечание. Справедливости ради необходимо отметить, что первым языком программирования, специально разработанным для решения задач ИИ, был язык IPL (Information Processing Language), сознанный в 1956 году А. Ньюэллом, К. Шоу и Г. Саймоном из RAND Corporation и Института Карнеги. IPL – это своего рода ассемблер для символьных вычислений. Мы не будем сейчас на нем останавливаться, но надо упомянуть, что IPL оказался удачной разработкой. На IPL был реализован ряд проектов ИИ (игра в шашки, первая экспертная система, программа для доказательства теорем и ряд других). Lisp испытал сильное влияние IPL (особенно в том, что касалось представления структур данных), ноМаккарти в конечном счете выбрал иной путь; в итоге Lisp быстро вытеснил IPL, о котором сейчас почти никто не вспоминает (и, откровенно говоря, напрасно).

Идея S-выражений очень проста, но, чтобы увидеть за этой простотой истинные возможности, нужно, чтобы появился гений.

Название S-выражение происходит от symbol expression, что можно перевести как «символьное выражение». S-выражение – это всего лишь способ (или форма) записи данных ипрограмм. S-выражения состоят из данных двух типов – атомов и списков.

Атом – это либо число (например, 127, -88 или 3.1415926), либо алфавитно-цифровой символ (например, A, СОБАКА или B52), либо строка (последовательность символов, ограниченная кавычками, например, «Hello World»). Обратите внимание, что понятие символа в Lisp отличается от такового в Java или C, где символ – это действительно одиночный знак, например, 'A' или '*'.

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

(У ПОПА БЫЛА СОБАКА)

(У (ПОПА (БЫЛА (СОБАКА)))

(ПАПА ВАСЯ 35 МАМА Лена 30 СЫН МИША 8)

((ПАПА ВАСЯ 35)(МАМА ЛЕНА 30)(СЫН МИША 8))

()

Статью целиком читайте в журнале «Системный администратор», №06 за 2016 г. на страницах 64-69.

PDF-версию данного номера можно приобрести в нашем магазине.

Комментарии могут оставлять только зарегистрированные пользователи