Содержание


Пересекая границы

Красота Lisp

Эльдорадо языков программирования

Comments

Серия контента:

Этот контент является частью # из серии # статей: Пересекая границы

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Пересекая границы

Следите за выходом новых статей этой серии.

Я недавно пробежал свой первый марафон и обнаружил в этом намного больше полезного, чем мог предположить. Я превратил такое простое действие как шаг в нечто экстраординарное для человеческого тела, пробежавшего 26.2 мили. Некоторые языки, например, Smalltalk и Lisp, дают мне аналогичное ощущение. В Smalltalk шаг - это объект; все в Smalltalk имеет дело с объектами и передачей сообщений. В Lisp фундаментальный шаг еще проще - язык полностью состоит из списков. Но пусть простота не вводит вас в заблуждение. Этот 48-летний язык имеет невероятную мощь и гибкость, которые в Java отсутствуют.

Мое первое взаимодействие с Lisp в студенческие годы не было гладким. Я отчаянно боролся с языком, пытаясь втиснуть его в процедурную парадигму, которую знал, вместо того чтобы работать с его функциональной структурой. Хотя Lisp не является строго функциональным языком (некоторые из возможностей лишают его права так называться в строгом смысле слова), многие идиомы и функциональные возможности Lisp имеют сильный функциональный привкус. С того времени я научился использовать списки и функциональное программирование.

Эта очередная часть серии "Пересекая границы" демонстрирует утерянные сокровища. Сначала мы пройдемся по основным конструкциям Lisp и затем перепрыгнем на Lambda-выражения, рекурсии и макросы. Такой быстрый тур позволит оценить производительность и гибкость Lisp.

Начало работы

В данной статье я использую GNU GCL, который можно бесплатно загрузить для многих операционных систем. Но вы можете использовать любую версию Common Lisp с минимальными изменениями. Подробная информация о доступных версиях Lisp приведена в разделе "Ресурсы".

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

Язык списков

В своей основе Lisp - это язык списков. Все в Lisp, от данных до кода приложения, является списком. Любой список состоит из атомов (элементарных объектов) и списков. Числа являются атомами. Ввод числа просто возвращает это число в качестве результата:

Листинг 1. Простые атомы
>1
1
>a
Error: The variable A is unbound.

Если ввести букву, компилятор выдаст ошибку, как показано в листинге 1. Буквы являются переменными, поэтому необходимо присваивать им значение до использования. Если нужно указать букву или слово, отличное от переменной, используются кавычки. Указание перед переменной апострофа говорит Lisp задержать вычисление списка или атома, который следует за этим апострофом (см. листинг 2):

Листинг 2. Задержка вычисления и цитирование
>"a"
"a"
>'a
A

Обратите внимание на то, что Lisp перевел A в верхний регистр. Lisp предполагает, что вы хотите использовать букву A в качестве символа, поскольку не заключили ее в кавычки. Я рассмотрю операцию присваивания, но сначала я должен остановиться на списках. Список Lisp - это просто последовательность атомов, заключенных в круглые скобки и разделенных запятыми. Попробуйте напечатать список, например, приведенный в листинге 3. Он не будет выводиться, если не ввести апостроф.

Листинг 3. Вывод простого списка
>(1 2 3)
Error: 1 is invalid as a function.
>'(1 2 3)
(1 2 3)

Если перед списком не указан апостроф, Lisp считает каждый список функцией. Первый атом является оператором, а остальные атомы списка являются аргументами. В Lisp есть множество примитивных функций, включая многие математические функции, например, +, * и sqrt. (+ 1 2 3) возвращает 6, а (* 1 2 3 4) возвращает 24.

Списками управляют два типа функций: конструкторы и селекторы. Конструкторы создают списки, а селекторы разбивают их на части. Базовыми селекторами являются first и rest. Селектор first возвращает первый атом списка, а селектор rest возвращает весь список за исключением первого атома. В листинге 4 показаны эти селекторы:

Листинг 4. Базовые Lisp-функции
> (first '(lions tigers bears))
LIONS

> (rest '(lions tigers bears))
(TIGERS BEARS)

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

Если нужно создать списки, а не разобрать их на части, необходимы конструкторы. Как и в языке Java, конструкторы создают новые элементы: объекты в Java и списки в Lisp. Примерами конструкторов являются cons, list и append. Основной конструктор, cons, принимает два аргумента: атом и список. cons добавляет атом в список в качестве первого элемента. Если вызвать cons с типом nil, Lisp считает nil пустым списком и создает список с одним элементом. append соединяет два списка. list содержит список всех аргументов. В листинге 5 показаны конструкторы в действии:

Листинг 5. Использование конструкторов
> (cons 'lions '(tigers bears))
(LIONS TIGERS BEARS)

> (list 'lions 'tigers 'bears)
(LIONS TIGERS BEARS)

> (append '(lions) '(tigers bears))
(LIONS TIGERS BEARS)

cons может создать любой список, если использовать его вместе с первым и остальными атомами. Операторы list и append - это просто удобные атрибуты, но вы будете часто их использовать. Фактически, можно создать любой список или возвратить любой фрагмент списка, используя cons, first и rest. Например, для получения второго или третьего элемента списка нужно взять first из rest, или first из rest из rest, как показано в листинге 6. Для создания списка из двух или трех элементов можно использовать cons вместе с first и rest для имитации list и append.

Листинг 6. Создание второго элемента, третьего элемента, списка и добавление в список
>(first (rest '(1 2 3)))
2

>(first (rest (rest '(1 2 3))))
3

>(cons '1 (cons '2 nil))
(1 2)

>(cons '1 (cons '2 (cons '3 nil)))
(1 2 3)

>(cons (first '(1)) '(2 3))
(1 2 3)

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

Создание функций

Объявления Lisp-функций являются, как вы конечно догадались, списками. В листинге 7, в котором создается функция, возвращающая второй элемент списка, показана форма объявлений функций:

Листинг 7. Создание функции second
(defun my_second (lst)
  (first (rest lst))
)

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

Lisp также обрабатывает такие условные конструкции как выражение if. Его формат: (ifвыражение_условиявыражение_thenвыражение_else). В листинге 8 показана простая функция my_max, вычисляющая максимальную из двух входных переменных:

Листинг 8. Вычисление максимального из двух целых
(defun my_max (x y)
  (if (> x y) x y)
)

MY_MAX
(my_max 2 5)

5
(my_max 6 1)

6

Подведем итог всему, рассмотренному выше:

  • Lisp использует списки и атомы для представления как данных, так и программ.
  • Вычисление списка означает интерпретацию первого элемента как функции списка, а остальных элементов - как аргументов функции.
  • Условные операторы Lisp используют выражения true/false с кодом.

Рекурсия

Lisp предоставляет программные структуры для итераций, но рекурсия является намного более популярным способом навигации по спискам. Комбинация first и rest отлично работает с рекурсиями. Функция total в листинге 9 показывает, как это работает:

Листинг 9. Использование рекурсии для вычисления суммы значений элементов списка
(defun total2 (lst)
(labels ((total-rec (tot lst)
(if lst (total-rec (+ tot (first lst)) (rest lst)) tot)))
(total-rec 0 lst)))

Функция total в листинге 9 принимает список в виде единственного аргумента. Первое выражение if останавливает рекурсию, если список пуст, возвращая ноль. Если нет, функция добавляет первый элемент к сумме остальной части списка. Здесь можно увидеть, почему first и rest сделаны именно такими. first может извлечь первый элемент из списка, а rest облегчает применение концевой рекурсии (tail recursion - тип рекурсии, использованной в листинге 9) к оставшимся элементам.

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

Функции высокого порядка

Lisp становится более интересным при нивелировании различий между данными и кодом. В последних двух статьях данной серии рассматривались функции высокого порядка в JavaScript и замыкания в Ruby. Обе эти функциональные возможности передают функции в виде аргументов. В Lisp функции высокого порядка являются тривиальными, поскольку функции не отличаются от любого другого вида списка.

Возможно, самым традиционным применением функций высокого порядка является lambda-выражение, являющееся Lisp-версией замыкания. Функция lambda представляет собой определение функции, использующейся для передачи функций высокого порядка в Lisp-функции. Например, выражение lambda в листинге 10 вычисляет сумму двух целых чисел:

Листинг 10. Выражения lambda
>(setf total '(lambda (a b) (+ a b)))
(LAMBDA (A B) (+ A B))

>total
(LAMBDA (A B) (+ A B))

>(apply total '(101 102))
203

Если вы когда-либо использовали замыкания или функции высокого порядка, то, возможно, лучше поймете код, приведенный в листинге 10. Первая строка определяет lambda-выражение и связывает его с символом total. Вторая строка просто отображает функцию lambda, связанную с total. Наконец, последнее выражение применяет функцию lambda к списку, содержащему (101 102).

Функции высокого порядка предлагают более высокий уровень абстракции, чем объектно-ориентированная концепция. Их можно использовать для выражения идей лаконичнее и понятнее. Святым Граалем программирования является обеспечение больших возможностей и большей гибкости при использовании меньшего количества строк кода, не жертвуя при этом читабельностью или производительностью. Функции высокого порядка делают все это.

Заключение

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


Ресурсы для скачивания


Похожие темы

  • Оригинал статьи "Crossing borders: The beauty of Lisp".
  • "За пределами Java" (O'Reilly, 2005): Книга автора о подъеме и становлении языка программирования Java, о технологиях, которые могут бросить вызов Java-платформе в некоторых областях.
  • GNU Common Lisp: Одна из наиболее популярных реализаций Lisp, и Lisp-интерпретатор, использованный в данной статье.
  • Carl de Marcken: Внутри Orbitz: Обсуждение функциональных возможностей Lisp в производстве показывает, что может сделать Lisp в реальной жизни.
  • " Структура и интерпретация компьютерных программ, 2-е издание" (Гарольд Абельсон (Harold Abelson) и др., McGraw-Hill, 1996): Вечная классика, быстро ставшая философией Lisp.
  • Ассоциация пользователей Lisp: Международная организация, поддерживающая сообщество Lisp.
  • The Common Lisp Directory: Этот отличный сайт предоставляет изобилие информации о Lisp и связанных с ним ресурсах, включая CLiki, ссылающийся на ресурсы для свободно распространяемого программного обеспечения, реализованного на Common Lisp и на дополнительные ресурсы ALU Lisp.
  • Common Lisp Implementations: Коммерческие и бесплатные реализации Common Lisp.

Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=200247
ArticleTitle=Пересекая границы: Красота Lisp
publish-date=03062007