Тайны бессмертия Лиспа. Common Lisp: музейный экспонат или мощное средство создания интеллектуального софта?

LinkFly (http://linkfly.ru)

«Lisp - крайне интересная штука. Требует, конечно, полного переосмысления жизненного пути и погружения в изначальное Дао, но все-таки интересная»

Из Сети

Сегодня мы попробуем взорвать твой мозг торжественным раскрытием тайны бессмертия языка «Lisp». Ты узнаешь, что за штуку придумал Джон Маккарти (тогдашний «Эйнштейн» мира программирования) в 1958 году, почему эта «штука» не планирует подвергаться забвению и кто такие странные существа – «Лисперы».

«Адепты Лиспа - головная боль людей в белых халатах?» Подобный вопрос порой задают те, кому приходилось с ними (адептами) контактировать. Вот, например, высказывание одного из модераторов форума известного ресурса http://rsdn.ru: «Функциональные языки в целом и Лисп в частности собрали вокруг себя много откровенно невыдержанной и фанатичной публики». Что ж, приобщимся к их знаниям.

Теория. Скажи «нет» синтаксическому разврату!

Сразу уточню, что под термином «Лисп» в статье подразумевается диалект «Common Lisp» (тем не менее, очень многое с небольшими оговорками применимо и к диалекту Лиспа «Scheme»). На сегодняшний день (если не говорить о языках общего назначения – ELisp и AutoLisp/VisualLisp) в широком употреблении остались только эти два диалекта.
Итак, что же это за зверь – Lisp? Это язык общего назначения, особенно удобный для символьных вычислений, а значит, для разработки экспертных систем и других AI-приложений. Разумеется, для разработки веб-приложений, приложений взаимодействующих с базами данных и прочего общественно-полезного стаффа он также используется.
Одно из многих положительных качеств Лиспа - его максимально аскетичный синтаксис. Два основных правила таковы:

1. Твоя программа, а конкретно - вызов функции, должна быть заключена в скобки:

Например: (твоя_программа параметр1 параметр2 … параметрN).

2. На месте параметра может быть вызов другой функции, и ее результат будет считаться параметром: (твоя_программа (+ 1 2) параметр2).

В Лиспе реализовано множество свойств, которые создатели других языков не устают из него черпать, постепенно превращая свои языки в Лисп. Одно из них - это использование функциональных объектов. В качестве параметров функции ты можешь передавать другие функции, которые, кстати, возможно определить во время выполнения программы. Да, именно так: программа может быть сгенерирована во время выполнения! Кроме того, ты можешь переопределить уже определенные функции, то есть, язык позволяет писать самоизменяемые программы без использования ассемблера. Все эти манипуляции можно производить и в «докомпиляционной» стадии, что очень способствует построению оптимизированных программ. Для более основательного ознакомления с фичами языка весьма рекомендую зайти на один из лучших ресурсов по основам Лиспа: http://pcl.catap.ru, там находится переведенная на русский язык книга «Практический Common Lisp» Питера Сейбеля.

Подготовка инструментов

Для начала скачаем бесплатную версию простенькой Лисп-системы LispWorks, которая поджидает любого начинающего экспериментатора на www.lispworks.com/downloads.

Что ты говоришь? Не желаешь пользоваться «простенькой системой»? Желаешь иметь в своем распоряжении набор «кнопочек, пимпочек» и всякой подобной ерунды для построения GUI? Легко! По адресу http://franz.com/downloads тебя ждет Лисп-система «Allegro CL 8.1 Free Express Edition». Сей агрегат представляет собой бесплатную редакцию платной системы; здесь содержится все необходимое – и GUI-конструктор, и генерация exe-шников.

Обе системы ставятся на Windows, Linux, MacOS, FreeBSD (оцени масштабы). Повозившись с бесплатными версиями, тебе нужно будет решить: отдавать ли свои кровные за полноценные редакции? Например, на момент написания статьи самая дешевая версия LispWorks (для коммерческого использования) стоила $1500. Но не стоит впадать в панику (а лишь ощутить серьезность и мощь отрасли) – существуют и полностью бесплатные альтернативы, причем, весьма качественные. Если ты заядлый «виндузятник», – тебе нужно раздобыть плагин для Eclipse, включающий в себя Лисп-систему SBCL, под названием «CUSP», по адресу: http://bitfauna.com/projects/cusp. Кстати о SBCL. Скачать ее можно с http://www.sbcl.org/platform-table.html. Сходить по этой ссылке я советую в любом случае, хотя бы для того, чтобы посмотреть, насколько основательно разработчики подошли к вопросу переносимости. Вот, например, список архитектур, на которые они ориентируются: X86, AMD64, PPC, SPARC, Alpha, MIPSbe, MIPSle. А что насчет операционных систем? Список также внушает почтение: Linux, Darwin(Mac OS X), Solaris, FreeBSD, NetBSD, OpenBSD, Windows. Впечатляет, не правда ли? Но учти, что под неистребимый Windows портирование еще не завершено (причем, только под архитектуру x86). Главное, чего пока нет в Windows-версии, - многопоточности. Все остальное должно работать на «ура», правда, я, помнится, так и не смог побороть глюк библиотеки ASDF-INSTALL, предназначенной для загрузки и компиляции библиотек из общего хранилища Лисп-исходников (смотри http://cliki.net).

Итак, SBCL – это Лисп-система (не среда разработки), и для экспериментов с Common Lisp’ом ее может быть вполне достаточно. Для серьезных разработок я тебе рекомендую добыть модуль к редактору Emacs – SLIME. Самая что ни на есть крутая и бесплатная комбинация - это «EMACS - SLIME - SBCL». SLIME можно взять отсюда: http://common-lisp.net/project/slime. Если ты хочешь все и сразу, то можешь скачать один из вариантов LispBox здесь: http://common-lisp.net/project/lispbox или здесь: http://gigamonkeys.com/book/lispbox.

Практика. Основные функции Лиспа

После установки и запуска выбранной Лисп-системы ты увидишь перед собой консоль интерпретатора. Например, в случае LispWorks строка приглашения консоли будет выглядеть так:

CL-USER 1 >

Да, именно сюда тебе и следует вводить выражения языка Лисп. Все хозяйство напоминает UNIX Shell: вводи выражения, нажимай Enter и смотри результат вычисления в ответе интерпретатора.

Экспресс-курс в основы языка

• S-expression (или s-expr) – символьное выражение, его может вычислить интерпретатор.
• Атом и список являются S-выражениями.
• Атом – все, что не список, а также NIL (который является пустым списком - '()).
• '( ... ) - список. Может содержать любое количество объектов, в том числе другие списки.
• QUOTE - блокировка (сокращение – «'»), блокирует вычисление списка.
• SETQ - присваивание переменной (любого типа): (setq myvar '(a b c)) (setq myvar2 999).
• SETF - обобщенное присваивание: (setf (cadr mylist) 'newatom). Второй аргумент - место хранения объекта.
• LIST - создает список из аргументов: (list 'a 'b 'c) > (a b c).
• LET - создает локальную связь, а также замыкание в определяемой в его теле функции: (let ((myvar1 1) (myvar2 3)) (+ myvar1 myvar3)).
• DEFUN - определяет функцию: (defun my-func (arg1 arg2) ... <операции с arg1 и arg2>).
• DEFMACRO - определяет макрос, который будет разворачиваться перед компиляцией (подобно DEFUN, но без вычисл. аргументов).
• MACROEXPAND - позволяет оценить работу макроса: (macroexpand '(mymacro arg1 arg2)).
• FUNCALL - применение функции к аргументам (funcall (symbol-function 'list) 'a 'b).
• SYMBOL-FUNCTION - возвращает функциональный объект, связанный с символом, или место его хранения (для SETF).
• MACRO-FUNCTION - возвращает макрос, связанный с символом, или место его хранения.
• ZEROP - возвращает T, если аргумент равен нулю.
• PRINT - печатает аргумент в стандартный поток вывода.

Практика. Переопределяем один из механизмов Лиспа

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

(defun factorial(x)
(if (zerop x)
1
(* x (factorial (1- x)))))

; не стоит заниматься подсчетом скобок, среда
; программирования это сделает за нас :)

> factorial

(factorial 5) ; проверка

> 120

А теперь представим себе, что необходимо эту функциональность (функциональный объект) связать с другим символом. В смысле, не конкретно именно эту функциональность, а вообще, какую-либо функциональность, определенную ранее и связанную с каким-либо символом. Зачем? Это во многом зависит от нашей фантазии. Сможем найти смысл в возможности переназначать функциональный объект, значит, будем использовать, если нет, ну значит не судьба.

И все-таки, чем бы нам это могло помочь? Допустим, у нас есть чужой код, в который нет времени/желания влезать, но скорректировать его работу нужно, просто позарез. Мы можем осуществить это следующим образом:

1. Ввести в систему новый символ (скажем, ‘B) и сохранить в нем функциональный объект, связанный с неким символом (скажем, ‘A) и поведение которого требуется скорректировать.

2. Определить новую функцию, которая осуществляет какие-либо нужные нам действия, дополняющие действия функционального объекта (связанного с ‘A, а теперь еще и с ‘B), а также действия этого функционального объекта (этого самого – связанного с ‘A и ‘B). При определении этой функции для вызова функции изначальной нужно пользоваться символом ‘B. Почему – будет понятно далее.

3. Связать функциональный объект, представляющий новую функцию, с символом ‘A. Поэтому, собственно, для вызова «родной» функции и нужно было пользоваться новым символом ‘B, - символ ‘A теперь будет связан с функцией, включающей дополнительные действия.

На примере:

;Определяем функцию от двух аргументов
(defun relation-is (obj1 obj2)
(list obj1 'is obj2))

;проверка
(relation-is 'cat 'animal)

> (cat is animal)

;Сохраняем старую версию функции
(setf (symbol-function 'old-relation-is)
(symbol-function 'relation-is))

;Добавляем функциональности
(defun relation-is (obj1 obj2)
;теперь relation-is связан с другой функцией
(list :relation (old-relation-is obj1 obj2)))

;проверка нового варианта
(relation-is 'cat 'animal)

> (:RELATION (CAT IS ANIMAL))

Попробуем то же самое провернуть с рекурсивной функцией, в нашем случае - с факториалом:

(setf (symbol-function 'old-factorial)
;сохраняем старую версию
(symbol-function 'factorial))

(defun factorial(x)
(print x)
(list (list 'factorial x) ;
(old-factorial x)))
(factorial 5) ;проверка
> Ошибка!!! «In * of (1 (('FACTORIAL 0) 1)) arguments should be of type NUMBER.»

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

Немного подумаем. Нам нужно успешно вызвать в функции саму себя, причем не функцию, связанную с каким-либо символом (так как может происходить переназначение функций), а использовать функцию, реально выполняющуюся в данный момент. Сразу напрашивается вопрос – а не предоставляет ли язык нам такую возможность? Какую-нибудь системную переменную вроде *this*, содержащую текущий, выполняемый функциональный объект. Тогда можно было бы сделать так:

;Новое определение факториала
(defun factorial(x)
(if (zerop x)
1
(* x (funcall *this* (1- x)))))

;;; Далее код из Листинга 3.

Однако всеведущие создатели не позаботились о системной переменной, подобной *this*. Это было сделано ради борьбы за производительность и, видимо, для стимуляции зрелой самостоятельности в среде программистов. Ладно, мы все сделаем сами:

(defmacro defun-new (name args &body body)
`(let (*this*) ;это нужно для создания замыкания
(defun ,name ,args ,@body)

;модифицируем замыкаемое значение
(setq *this* (symbol-function ',name))

;возвращаем символ определенной ф-ии
',name)) ;defmacro

;Проверка
(defun-new f(x) (list x *this*))
(f 34)
> (34 #<interpreted function F 200D8832>)

Как работает сие чудо? Разберем по косточкам:

(macroexpand '(defun-new f(x) (list x *this*)))

> (LET (*THIS*)
(DEFUN F (X) (LIST X *THIS*))
(SETQ *THIS*
(SYMBOL-FUNCTION (QUOTE F)))
(QUOTE F))

Вот в такой вот код разворачивается макрос defun-new:

1. Функция LET создает локальную связь с символом *THIS*.
2. Далее создается функция с помощью стандартной формы DEFUN, в теле которой может использоваться замыкаемое значение локальной переменной *THIS*.
3. Форма (SETQ *THIS* (SYMBOL-FUNCTION (QUOTE F))) изменяет локальное определение *THIS*, а значит, и замыкаемое значение переменной в определяемой с помощью DEFUN функции. Причем изменяет она его со значения NIL на значение, равное функциональному объекту, соответствующему только что определенной функции.
4. (QUOTE F) – Возвращает символ определенной функции.

Теперь достаточно определить factorial с помощью макроса DEFUN-NEW, используя переменную *THIS* в теле функции, и добавлять функциональность описанным выше способом. Я предлагаю тебе провести этот эксперимент лично и увидеть все своими глазами.

Откровенно говоря, чтобы решить поставленную выше задачу («добавление функциональности рекурсивным функциям»), применять новый способ определения функций (через DEFUN-NEW), учитывающий появление замыкаемой переменной *THIS* в теле функции, вовсе не обязательно. Но дело в том, что для переменной *THIS* есть и другое применение. Например, можно заставить функцию регистрировать себя где-либо, используя для этого функциональный объект, соответствующий выполняемой в настоящий момент функции. Заметь, что просто зарегистрировать символ имени функции может быть недостаточно из-за возможности переназначения функциональных объектов. Я уверен, найдется множество способов применения *THIS*, но вот для чего его применить не получится, так это для добавления функциональности к уже созданным кем-то функциям. Либо из-за отсутствия исходников, либо из-за необходимости добавлять функциональность в run-time.

Далее я покажу тебе, как обойтись без *THIS* при добавлении функциональности к уже готовым функциям, а затем рассмотрю ситуацию, когда *THIS* все-таки нужен, но создавать новый способ (макрос) определения функций не хочется.

Вот код, который следует использовать для «апгрейда» уже готовых рекурсивных функций (без *THIS*):

;;; Добавление функциональности к уже
;;; готовым рекурсивным функциям

;определение факториала без *THIS*
(defun factorial(x)
(if (zerop x) 1 (* x (factorial (1- x)))))

(setf (symbol-function 'old-factorial)
(symbol-function 'factorial))

(defun factorial(x)
(print x) ;какое-либо действие
(list (list 'factorial x)
(let ((new-factorial
(symbol-function 'factorial)))
(setf (symbol-function 'factorial)
(symbol-function 'old-factorial))
(prog1
;можно и (factorial x)
(old-factorial x)
(setf (symbol-function 'factorial)
new-factorial)
)) ;prog1, let
) ;list
) ;defun

(factorial 5) ;проверка

Теперь добьемся того, чтобы стандартный процесс определения функций позволял нам пользоваться переменной *THIS*. Для этого мы напишем код, подобный определению DEFUN-NEW, но с некоторыми коррективами:

;Сохраняем текущее значение системной функции DEFUN
(setf (macro-function 'defun-old)
(macro-function 'defun))

;Переопределяем системную функцию DEFUN,
; используя ее старую версию в DEFUN-OLD
(defmacro defun (name args &body body)
`(let (*this*)
(defun-old ,name ,args ,@body)
(setq *this* (symbol-function ',name))
',name))

;Проверка
(defun f(x)(list x *this*))
(F 5)

;Восстанавливаем прежнее значение, если в новой DEFUN больше нет необходимости
(setf (macro-function 'defun)
(macro-function 'defun-old))

Ощути величие ситуации! Мы дополнили системный механизм определения новых функций своим собственным кодом! Попробуй-ка проделать то же самое, например, с Си. Дополни int my_function(char arg1, char arg2) {…} нужным тебе функционалом. Если ты всерьез задумался над этим вопросом, - смотри не загреми в компанию к Наполеону с Македонским ;).

На этом примере мы с тобой осознали одну важную вещь: Лисп – это наш слуга, а не наоборот, как бывает обычно. И это еще одна причина Бессмертия Лиспа.

Заключение

Если ты понял суть вышеописанного, и твой мозг не взорвался, - то можешь при желании вступать в секту и гордо называться «Лиспером» :). К сожалению, много чего осталось за рамками статьи: и оригинальный процесс разработки, не идущий ни в какое сравнение по качеству с традиционным, и описание сборки автономных исполняемых файлов (exe, elf), и поднятие программируемого динамического лисп-веб-сервера, и рассказ о лидерах сообщества, их творчестве и бесплатных библиотеках, и … в общем, много чего хотелось бы еще рассказать, но, к сожалению, статья не резиновая. Судя по всему – To be continued …

Десять рецептов эликсира вечной молодости Лиспа

1. Единообразный и простой синтаксис (облегчает генерацию кода макросами).
2. Макросы времени компиляции на самом Лиспе.
3. Определение и переопределение функций во время выполнения.
4. Компиляция и выполнение кода, сгенерированного в run-time.
5. Определение языков с синтаксисом под задачу.
6. Огромное количество open-source библиотек (http://cliki.net).
7. Более гибкая и динамичная, по сравнению с другими языками, объектная система (CLOS).
8. Возможность модифицировать собственное ядро, даже во время выполнения.
9. Поддержка практически всех существующих на данный момент парадигм программирования.
10. Декларативное описание циклических алгоритмов (с помощью формы LOOP).

CD

Файл с листингами к статье и весь необходимый стафф ты найдешь на нашем пацанском диске.

WWW

• Всемирная ассоциация пользователей Лиспа, даже начинающий адепт должен знать это:alu.org.
• Огромный Лисп-портал с тоннами исходного кода: common-lisp.net.