Лисп

Материал из Викиучебника

Лисп полон примечательных особенностей. Он — старейший из ныне живущих языков программирования^[1]. Притом по своей высокоуровневости и продвинутости Лисп превосходит чуть ли не все прочие языки. Например, это также и первый язык, хотя все остальные парадигмы, идеологии, философии, методики и привычки программирования, включая непопулярные и чисто гипотетические, он также поддерживает — гибко и эффективно.

«Ого! Как так?» Дело в том, что лисповый код…

(с виду (опять-таки) необычный (весьма)
(из-за
 (кажущегося (на первый взгляд) избыточным)
обилия (круглых) скобок))

…представляется простой и обычной структурой данных. А ведь Лисп с таковыми на короткой ноге. Вот и получается, что его можно любым образом изменить и надстроить посредством программ, написанных на нём самом. Метапрограммирование — в самой основе Лиспа.

Такое полное превосходство объясняется происхождением Лиспа. Ведь ныне популярные языки программирования создаются обычно инженерами, телефонизаторами, «разработчиками программного обеспечения», «хакерами» (и простыми студентами), веб-дизайнерами, лингвистами, математиками, любителями языка Си, японцами… для целей вроде создания веб-сайтов, популяризации среди школьников и первокурсников, программирования экзотичных операционных систем или стиральных машин, обработки текстовых файлов или создания «значительно лучшего» соперника существующим языкам, или вообще не весть для чего. Популярность таких языков длится обычно не дольше семи лет, — срока, нужного среднеразумному человеку для осознания ошибки профессионального выбора.

Лисп ничем таким похвастаться не может. Его изобрёл в 1958 году лауреат премии Тьюринга (1971) и творец термина «искусственный интеллект» Джон Маккарти.

Обычно говорят, что Лисп — это не просто язык, а семейство языков программирования, в котором лишь два отдельных члена (диалекта) ныне используются:

Common Lisp,

примеры в этом учебнике будут на нём, и

Схим (Scheme).

О нём есть статья в «Потенциале»: Введение в язык Scheme для школьников.

Популярности Лисп пока не завоевал^[2]. Хотя сам язык от того никак не страдает, хорошего и полного русского учебника о нём нет. Даже на английском таковых единицы^[3]. Так, дорогие знатоки Лиспа и те, кто пока лишь учится, давайте вместе, по ходу изучения и поучительных бесед, напишем свободный учебник по Common Lisp в формате вики.

[править] Вступление

Как же угодить вам, дорогие читатели? Прежде всего, внимая отзывам на этот вопрос. Перед вами — викиучебник, а это больше, чем учебник: это домашняя страница открытой школы Лиспа, где каждый может быть слушателем или преподавателем^[4].

Пока же положения таковы. Вы хорошо понимаете информатику и информационные технологии^[5]; вероятно, имеете навык программирования на популярных ныне алголоподобных языках (Паскаль, Си[-плюс-плюс], Java, Руби…) или даже на языках стройного замысла — вроде Пролога, Смоллтока и Хаскелла. Но независимо от такого навыка начинающему лиспнику приходится открывать много нового, порою старательно отвыкая от ограничений других языков.

Второе важное требование: знание лучшего языка программирования вам нужно для решения некоей сложной задачи, либо определённого класса задач. Вы, образно говоря, не лингвист, знакомящийся с грамматикой, лексикой и этимологией забавного языка, а деловой человек, нуждающий не просто «знать язык», а точно, кратко и доходчиво излагать на нём определённые мысли. Толстый академический справочник по грамматике вы не откроете никогда, а в словарь заглянете лишь изредка, за толкованием важного ключевого слова, непонятного из контекста. Винить за такую непонятность следует только учебный текст; он должен совершенствоваться, покуда у читателя не отпадёт нужда в сторонних справочных материалах.

Этому помогут, опять-таки, ваши отзывы и замечания.

[править] Отличия

Повторяем: бывалым программистам при изучении Лиспа порою придётся переучиваться:

1. Отличать значения некоторых терминов в Лиспе от таковых в других языках, например: макрос, оператор, функция, определение функции, присвоение переменной.
2. Изучать необычные заменители привычных приспособлений, например: макросы, родовые функции, условия, продолжения, обобщённые переменные.
3. Привыкать к иной манере программирования, поощряемой уникальными свойствами Лиспа, — такими, например, как макросы.

Первое — путаницу в терминологии — легко простить Лиспу; как-никак, многие из таких понятий были впервые введены в нём. Второе требование также не шибко досадно: лисповы «заменители» оказываются изящнее и гибче, чем их привычные аналоги в иных языках.

А вот последнее требование — менять способ составления программ — отвратит от Лиспа многих программистов. Оно вовсе не обязательно: на Лиспе можно программировать в «фортранном» стиле. Однако, безумной расточительностью будет это человеку, уже привыкшему к фортраноподобным языкам. Не переходить же на новый язык ради одних только «удобств» вроде родовых функций!

[править] Восходящее программирование

Частный аспект этого нового способа назван «восходящим программированием» (по-английски — bottom-up programming — «программирование со дна вверх»). Вообще-то любая программа составляется и «снизу», и «сверху», — если она, конечно, написана не прямо на автокоде. Программист на Фортране/Алголе/Си++/Джаве «восходит» по лестнице концептуальной сложности программы всякий раз, когда пишет библиотеку. Но целую программу не создашь на одних библиотеках, да и ограничения языка вскоре дают о себе знать. Так программист встаёт на более традиционный путь «нисходящего программирования»: начиная с наиболее общего взгляда на проектируемую систему, мысленно дробит её на такие части, какие легче всего представить средствами данного языка и существующими библиотеками.

Лисп же, будучи усвоен программистом, не торопит навязывать свои структуры и процедуры, а даёт все приспособления для творения новых, — творения, фактически, собственного языка. Опять же, библиотечные функции делают подобное в других языках. Но Лисп идёт намного дальше, позволяя создавать «библиотечное что-угодно»: не только функции или классы, а любую абстракцию вычислительных процессов и структур данных. Например, CLOS — система классового программирования в Common Lisp, — это лишь набор макросов. Это равно что на каком-нибудь C# написать библиотеку… например, логического программирования. А вот на Лиспе целая реализация Пролога вместилась в 180 неторопливых строк^[6].

Одна из задач, предлагаемых в этом учебнике — придумать новую «парадигму» или «философию» программирования, затем реализовать её в Лиспе.

Так, Лисп позволяет программировать эффективнейшим способом: создать удобный набор понятий и составить из них решение вычислительной задачи. Или же наоборот: разделить задачу на систему более простых понятий, (и не обязательно только «модулей», «структур», «процедур», «объектов») а затем без особых ограничений реализовать те понятия и взаимосвязи между ними.

[править] Начинающим программистам

Предостережение выше было обращено к программистам, привыкшим к нелисповым языкам. Но и совершенным новичкам может быть немудро начинать с изучения Лиспа. Во-первых, это сложный язык, а Common Lisp — сложнейший из диалектов. Во-вторых, он непопулярен: намного трудней найти с ним трудоустройство, хостинг для веб-приложений или помощь.

Для начала, новичку следует выбрать реализацию ЛИСП. Считается, что одной из лучших сред для программирования на ЛИСП является связка Emacs+w:slime+SBCL (sbcl может быть заменён другой реализацией, например cmucl). Однако неопытному программисту или тому, кто программистом ещё не стал, подобная связка может оказаться трудной в работе и настройке. Для них рекомендуется использовать более дружественный Eclipse с плагином ЛИСП — Cusp, подробнее об их использовании можно прочесть здесь.

Однако, изучение Лиспа будет полезно хотя бы для глубокого понимания информатики и проектирования программ.

[править] Внешний вид

Не будем отвлекаться на рассмотрение связи Лиспа с примитивными операциями вычислительных машин, сразу перейдём к языку. Вот как можно упорядочить последовательность элементов по возрастанию^[7]:

(defun partition (fun array)
  (list (remove-if-not fun array) (remove-if fun array)))
 
(defun sort (array)
  (if (null array) nil
    (let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
      (append (sort (car part)) (cons (car array) (sort (cadr part)))))))

Отсюда полностью видны синтаксические правила Лиспа и понятие формы («действия», «оператора», «функции»…) Если непонятно, почитайте теоретическое отступление: Лисп/Синтаксис.

[править] Установка интерпретатора

[править] Основы программирования на языке Лисп

После успешной установки и запуска clisp, у вас должна появиться командная строка. Попробуем вычислять простые арифметические выражения:

[1]> (+ 1 1)
2
[2]> (* 5 (+ 2 10))
60
120
[3]> (* 2 2 2)
8
[4]>

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

Мы привыкли писать f(x,y), где под f мы подразумеваем некоторую функцию от двух аргументов x и y, но "+" это тоже функция. Конечно математику удобнее писать x+y, чем +(x,y), но согласитесь запись +(x,y) более универсальна, а это значит что нам не нужно будет придумывать отдельные механизмы работы с арифметическими операциями.

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

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

Рассмотрим следующую порцию кода:

[5]> (car '(1 2 3 4 5 6 7 8))
1
[6]> (cdr '(1 2 3 4 5 6 7 8))
(2 3 4 5 6 7 8)
[7]> (cons 1 '(2 3))
(1 2 3)
[8]> (cons 1 nil)
(1)
[9]> (cdr '(1))
NIL
[10]>

Данный пример демонстриует три базовых операции со списками car, cdr, cons.

[править] Примечания

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

1. ↑ Ибо Ассемблер не назовёшь языком программирования, а Фортран — ныне живущим.
2. ↑ О том бытуют разные домыслы: от общефилософских, как у Пола Грэхэма, до оголтело конспирологических.
3. ↑ Пол Грэхэм в 1993 и 1995 годах выпустил книги «On Lisp» (частные подробности) и «ANSI Common Lisp» (обстоятельное описание с примерами). Ещё недавно вышла книжка Петера Зейбеля «Practical Common Lisp», очень вводная. Прочее короче, меньше, хуже.
4. ↑ Читайте страницу Справка, учитесь работать в вики, высказывайтесь на странице обсуждения учебника.
5. ↑ Требование высокое. Но такова цена знания и умения программировать; да и понимание ИТ в нынешнем обществе пригодится каждому.
6. ↑ Paul Graham, On Lisp, ISBN 0130305529.
7. ↑ Данный способ весьма эффективен для общего случая, ибо реализует алгоритм «быстрой сортировки» Хоара. Для введения в алгоритмы упорядочения читайте статью в «Потенциале»: Алгоритмы сортировки.