Начало истории

В конце лета 1955 года в колледже Дартмут под руководством доцента кафедры математики Джона МакКарти состоялся семинар, посвященный вопросам искусственного интеллекта. Результатом этого семинара стал запрос на проведение исследовательского проекта.

Целью исследования стала проверка гипотезы, что все детали обучения или любые другие особенности интеллекта [человека] в принципе могут быть описаны так, что станет возможно создать машину для их моделирования.

В проекте предполагалось рассмотреть следующие вопросы:

• возможно ли использование существующих компьютеров для симуляции некоторых функций мозга?

• представима ли человеческая речь с помощью компьютерной программы и если да, то как она должна быть представлена?

• как с помощью сетей (гипотетических) нейронов могут быть представлены концепты?

• как можно измерить эффективность вычислений и сложность вычислительных устройств?

• возможно ли самообучение вычислительных систем?

• поддаются ли классификации «абстракции» и возможно ли формирование абстракций на основе сенсорной информации?

• отличается ли творческая деятельность от лишенной воображения лишь наличием случайностей?

Проект задумывался небольшим, запрашивались оплачиваемые 20 человеко‑месяцев работы плюс расходы на командировки и оформление.

Финансирование было одобрено, и через год, летом 1956 года, работа началась. В рабочей группе помимо самого МакКарти были еще Клод Шеннон, Марвин Мински и Натаниэль Рочестер, а также несколько студентов.

Для целей повествования важно упомянуть второй вопрос из перечня выше. МакКарти писал, что участники семинара сошлись на том, что для представления речи как набора слов естественным выбором являются списки, где каждый элемент содержит данные и указание на то, где искать следующий элемент.

Такое представление появилось не на пустом месте. Ранее, обработка списков была реализована для компьютера JOHNNIAC в программе Logic Theorist. Она была написана на языке IPL 2.

Идея работы со списками для представления информации была весьма популярна и использовалась в разных разработках того времени. Больше того, быстро стало понятно, что префиксная форма записи удобнее инфиксной. В префиксной форме многие манипуляции со списком получались значительно проще. В префиксной форме действие над списком можно расположить в начале самого списка, что делает обработку близкой к тривиальной.

А раз так, то потребовалось представление для хранения данных. Префиксная форма записи списков оказалась значительно дешевле для сохранения и последующего восстановления в памяти в сравнении с другими языками и средами того времени.

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

Последним нерешенным оставался вопрос, стоит ли делать новый язык или можно использовать Фортран для реализации?

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

Стоит также отметить архитектуру компьютера IBM 704, серьезно повлиявшего и на дизайн языка, и на его реализацию.

Машинное слово этого компьютера состояло из 36 бит, разделенных на 4 группы:

• 15 бит адрес

• 3 бита префикс

• 15 бит декремент

• 3 бита тег

Префикс по сути представлял собой код инструкции, тег использовался инструкциями перехода, адреса состояли из 15 бит из‑за разрядности адресной шины.

После ряда экспериментов в реализации рантайма, еще не языка даже, появились функции cwr (Contents of the Word in Register number), возвращающая все машинное слово целиком, а также функции car (Contents of the Address part of Register number), cdr, cpr, ctr возвращающие адрес, декремент, префикс и тег соответственно.

Для функций car и cdr в архитектуре были инструкции, позволяющие реализовать функции тривиальным способом.

Очевидным образом в реализации появилась функция cons(a,d,p,t), которая изымала из свободной памяти элемент и формировала машинное слово для него (позже это станут называть конструктором во многих языках — прим. авт.)

Поначалу cons не была функцией, а была подпрограммой, однако в рамках параллельно проходившей работы над проектом FLPL (Fortran‑Compiled List‑Processing Language) стало ясно, что это должна быть именно функция. Такая реализация позволяет с помощью композиции функций строить списки произвольного размера и структуры.

В принципе для задачи управления списками можно было бы здесь остановиться, но FLPL имел 3 принципиальных проблемы:

• отсутствовала рекурсия

• отсутствовало условное выражение

• необходимо было вручную управлять высвобождением памяти

Рекурсия была нужна, поскольку МакКарти хотел иметь возможность использовать для написания программ математические определения, многие из которых рекурсивны по своей природе.

В Фортране имелся условный оператор, но его было неудобно использовать и МакКарти предложил функцию XIF(M, N1, N2), возвращавшую N1 или N2, в зависимости от того, равно ли M 0 или нет. Функция упростила и укоротила код, но ей все же не часто пользовались, у нее был существенный недостаток. Перед входом в эту функцию вычислялись её аргументы, M, N1 и N2.

Так появилось условное выражение, вычисляющее и возвращающее только одно из значений в зависимости от значения условия.

Однако, функцией XIF пользоваться было не очень удобно, поскольку требовалось вычисление обоих аргументов. Поэтому МакКарти реализовал вариант этой функции, не требовавшей вычисления обоих аргументов, вычислялся только один в зависимости от значения M.

Отступление №1

Многие на предыдущей фразе наверняка даже не споткнулись. А тем временем, это очень важное свойство языка программирования.

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

Статью об этом новом операторе не приняли в Communication of the ACM как слишком короткую.

Реализация Лисп

В принципе, для работы над основными задачами, обозначенными выше, уже было достаточно наработок. Но в 1958 МакКарти стал доцентом в МИТ и вместе с Мински там же начал «Проект по Искуственному интеллекту МИТ» под патронажем профессора Джерома Визнера, что давало определенную свободу.

Заручившись поддержкой руководства, Мински запросил помещение, двух программистов, секретаря, оператора терминала. Визнер же, в свою очередь, попросил взять шестерых студентов на практику и работа началась.

Компилятор получился не сразу, сначала было много экспериментов. Поскольку уже была реализация рантайма, в качестве основы для трансляции использовались M‑выражения, которые были максимально похожи на текст на Фортране при выводе.

М‑выражения печатались рантаймом, затем вручную перебивались и заново запускались. МакКарти написал статью, в которой описывался процесс вычисления рекурсивных функций для символических вычислений. В ней определялись и использовались М‑выражения, включавших в себя S‑выражения (symbolic expressions).

Пример M‑выражения:

apply[fn;x;a] =
 [atom[fn] →
 [eq[fn;CAR] → caar[x];
 eq[fn;CDR] → cdar[x];
 eq[fn;CONS] → cons[car[x];cadr[x]];
 eq[fn;ATOM] → atom[car[x]];
 eq[fn;EQ] → eq[car[x];cadr[x]];
 T → apply[eval[fn;a];x;a]];
 eq[car[fn];LAMBDA] → eval[caddr[fn];parlis[cadr[fn];x;a]];
 eq[car[fn];LABEL] → apply[caddr[fn];x;cons[cons[cadr[fn];caddr[fn]];a]]]

Пример M-выражения, содержащего вложенные S-выражения:

car[append[(A B C); (D E F)]]

Однако, Стивен Рассел, прочитав статью МакКарти, предложил и для вычислений использовать S‑выражения. То есть, получив сначала функцию eval[e;a], он предложил идею, что интерпретируемый код должен иметь ту же форму, что и списочные данные, то есть S‑выражения.

Отступление №2

Хотя S‑выражения выглядят как нечто в скобочках, в них есть внутренняя логика.

S‑выражения строятся по очень простым правилам:

• атом (число, строка, ключевое слово, символ) является S‑выражением

• выражение вида (x . y) является S‑выражением.

Такая форма отражает структуру машинного слова, определенную выше. x и
y являются элементами упорядоченной пары. По соглашению, список вида
(a b c) представлен в виде (a . (b . (c . NIL))), где второй элемент
пары является ссылкой на следующую ячейку, а последний элемент
содержит пустую ссылку, т. е. NIL.

Про Лисп много шутят, что это ((скобочки)). Это правда лишь отчасти. В крупных проектах статистически скобок тоже немало, только они расположены не (так), а так().

С другой стороны, именно S‑выражения позволили сделать единообразие во всем:

• очень простой синтаксис

• однозначная трактовка областей видимости

• простые правила макроопределений, поскольку код представляет собой S‑выражения

• самое, на мой взгляд, важное: функция (eval f) позволяет интерпретировать S‑выражения как код, что позволяет реализовать (совместно с макросами, конечно) концепцию «расставим скобочки вокруг этого и попробуем запустить».

Сборка мусора

Еще одна вещь, которую обязательно упоминают, говоря о Лисп — сборка мусора.

Сам термин появился в статье Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, причем, скорее как шутка, поскольку был записан в сноске к фразе:

«Когда требуется свободный регистр (ячейка памяти — прим. авт.) и ни одного не осталось в списке свободных блоков, запускается цикл переработки.»

В сноске было написано следующее:

«Мы уже называем это „сборкой мусора“, но я полагаю, что струсил использовать такую формулировку в статье, поскольку дамы‑редакторы Исследовательской лаборатории электроники не позволили бы мне это сделать.»

Вообще идея сборки мусора родилась как попытка сохранить математическую элегантность рекурсивных определений. Когда МакКарти рассматривал FLPL как способ реализации программы дифференцирования алгебраических выражений (в 1958 году), он отмечал:

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

Сама реализация сборки мусора была тривиальной по нынешним меркам: сохраняются списки занятых и свободных блоков, а когда свободные блоки заканчиваются, то перебираются все блоки и те из них, что из программы или стека недоступны, становятся свободными.

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

Десятое правило Гринспена

Примерно в 1993 году (точнее и сам автор выражения не помнит) Филип Гринспен сформулировал шуточное правило относительно Лисп, которое назвал «Десятое правило Гринспена»:

«Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp.»

Правило названо Десятым для того, чтобы название было звучным. Предыдущих девяти правил не существует.

Лисп, изначально строившийся как обработка списков, затем их выполнение, вырос в очень гибкую динамическую систему, из которой очень удобно «лепить» программную конструкцию. Он (язык) прошел стандартизацию, став Common Lisp'ом, появилось множество диалектов и родственных проектов (в том числе Scheme и Clojure).

Как сказал один из самых активных комментаторов вопросов по Лисп на StackOverflow Rainer Joswig:

«Common Lisp — аллигатор среди диалектов Лисп. У него древний дизайн (сотни миллионов лет) и почти нет изменений, выглядит немного пугающе и, время от времени, сжирает кого‑то молодого.»

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

Больше того, современные реализации Лисп значительно продвинулись в плане производительности и при правильном использовании могут на равных соревноваться с промышленными языками.

Но гибкость и мощность инструмента имеет и обратную сторону. Умение им пользоваться требует строгой внутренней дисциплины и навыков. Увидеть красоту, стройность подходов в Лисп дается не каждому.

Но кому удается, ценят эту элегантность и красоту, вместе с мощностью и силой, которые он дает.

Заключение

С Лиспом стоит познакомиться, хотя бы для того, чтобы увидеть «код как данные» или динамическую компилируемую систему, где границы между компиляцией и исполнением стерты. Этот язык другой, потребуется немало усилий, чтобы его понять и научиться им пользоваться.

Литературы по этому языку немного, но она есть.

Отправной точкой рекомендую прекрасный ресурс cl‑cookbook.

На русском языке издана книга «Практическое использование Common Lisp».

(удачи)