Отправляет email-рассылки с помощью сервиса Sendsay

Разнообразие языков программирования. Изучим их все.

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Блогосфера: продвижение сайта и многое другое" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Август 2007   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Дятлов Виталий

Статистика

530 подписчиков
0 за неделю
←   Все выпуски   →

Разнообразие языков программирования. Изучим их все. Язык программирования LISP.


Здравствуйте!

В этом выпуске, мы с вами рассмотрим язык программирования LISP.

Lisp давно признан одним из великих языков программирования. Фанатики восхищаются им на протяжении всей его истории - уже почти 50 лет. В MIT Lisp играет основную роль в учебных планах всех программистов. Предприниматели (например, Пол Грехэм (Paul Graham)) использовали невероятную производительность Lisp в качестве топлива для успешного начала бизнеса. Но, к огорчению своих последователей, Lisp так и не стал широко распространенным языком. Однако Java™-программист, потратив некоторое время на Lisp, этот затерянный город сокровищ, обнаружит множество технических приемов, которые изменят способ его кодирования к лучшему.

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

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

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

Язык списков

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

Простые атомы 

>1
1
>a
Error: The variable A is unbound.

 

 

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

Задержка вычисления и цитирование
>"a"
"a"
>'a
A
Обратите внимание на то, что Lisp перевел A в верхний регистр. Lisp предполагает, что вы хотите использовать букву A в качестве символа, поскольку не заключили ее в кавычки. Я рассмотрю операцию присваивания, но сначала я должен остановиться на списках. Список Lisp - это просто последовательность атомов, заключенных в круглые скобки и разделенных запятыми. Попробуйте напечатать список, например, приведенный в листинге 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 показаны эти селекторы:

 Базовые 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 показаны конструкторы в действии:

 Использование конструкторов
> (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.
Создание второго элемента, третьего элемента, списка и добавление в список
>(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-функций являются, как вы конечно догадались, списками. В листинге, в котором создается функция, возвращающая второй элемент списка, показана форма объявлений функций:

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

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

Вычисление максимального из двух целых
(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 показывает, как это работает:

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

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


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

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

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

Выражения lambda
>(setf total '(lambda (a b) (+ a b)))
(LAMBDA (A B) (+ A B))

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

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

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

Заключение

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

 Ресурсы

  • 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.

Текст выпуска заимствован у Брюса Тэйта, за что ему огромное спасибо!

На этом наш выпуск завершен. Надеюсь он вам понравился! Выпуск получился на редкость содержательным и информативным ))). В следующем выпуске мы поговорим с вами о языке программирования Cobol. До встречи через неделю!
В избранное