Lisp: Слезы радости, часть 1

Оригинал: "Lisp: Tears of Joy, Part 1"
Автор: Vivek Shangari
Дата публикации: June 1, 2011
Перевод: Н.Ромоданов
Дата перевода: Август 2012 г.

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

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

В то время я считал, что я был асом в крутом современном объектно-ориентированном языке программирования, который был средством моего самовыражения: я ел, пил, спал и мечтал на этом языке. Он сделал меня Богом в моем компьютерном мирке. Я также верил, что я нравлюсь женщинам, проводил часы, приводя в порядок свою прическу, и вел свой старенький и потрепанный скутер Kinetic Honda точно так, как если бы это был крутейший спорт-байк 1340cc Suzuki Hayabusa.

Теперь я понимаю в этом больше ...

Дежа вю

О тех из нас, кто был свидетелем перехода от парадигмы неструктурного программирования к процедурному программированию, а затем - к объектно-ориентированному программированию, скажут то, что Пол Грэм (Paul Graham) уже сказал в своей книге "Хакеры и художники" ("Hackers & Painters"). В частности: "То, что вы не можете доверять мнению других о языке программирования, делает вас лучшим программистом. Вам будет достаточно любого языка программирования, который вам придется пользоваться, поскольку язык будет определять, как вы будете обдумывать программы. Я знаю это из собственного опыта, поскольку в старших классах школы писал программы на языке BASIC. В этом языке не поддерживается даже рекурсия. Трудно представить, как писать программы без рекурсии, но в тот момент я этого не заметил. Я думал на языке BASIC. И в нем я был волшебником. Лучшим среди всех".

Три недели на изучение Lisp-а и у меня возникло ощущение дежа вю — так было раньше, когда я сначала "продвигался" от BASIC к С и от С к C++ и к Java. Тогда на каждом шаге я приятно удивлялся растущей мощью (программирования), оказавшейся в моих руках. Снова и снова я удивляюсь, как я кодировал без объектов, методов, инкапсуляции, полиморфизма, наследования и так далее! Можно сказать, что это синтаксические сладости моей работы.

Но не с Lisp-ом, который является чистым экстези. Он не только красивый, он - странно красивый.

В своем знаменитом эссе "Как стать хакером" ("How to become a Hacker") Эрик Стив Реймонд (Eric Steven Raymond), автор многих бестселлеров, в том числе бестселлера "Собор и базар" ("The Cathedral and the Bazaar"), пишет: "Обучение в Lisp-е состоит в получении практического опыта, которым вы будете обладать, когда вы его, наконец, освоите. Этот опыт, даже если вы больше никогда не будете пользоваться языком Lisp, сделает вас лучшим программистом на всю оставшуюся жизнь".

Lisp научит вас как специалиста

Так что же такого замечательного в Lisp? Как это он вас научит как специалиста? Специалист по Lisp-у Пол Грэм (Paul Graham) объясняет это так искусно и методически, что неуместно отвечать на этот вопрос по-иному. Пять языков (Python, Java, C/C++, Perl и Lisp), которые Эрик Рэймонд (Eric Raymond ) рекомендует осваивать специалистам, сильны каждый по-своему. В каких-то специальных вопросах, каждый из них может уступать другому, но, я думаю, что выше всех находится Lisp. И в пользу этого утверждения, я расскажу вам об одной из возможностей, которая, как я считаю, когда я смотрю на другие четыре языка, просто забыта. Что вы в них можете сделать без макросов?

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

Если вы разбираетесь в том, как работают компиляторы, вы поймете, что дело на самом деле не в том, что в Lisp используется странный синтаксис (везде круглые скобки!), а в том, что в нем нет синтаксиса (на самом деле синтаксис присутствуют в любом языке; в языке Lisp используется чрезвычайно простой и интуитивно понятный синтаксис с использованием круглых скобок — прим.пер.). Вы пишете программы в виде деревьев синтаксического разбора, которые создаются компиляторами, когда те выполняют синтаксический анализ других языков программирования. И эти деревья разбора полностью доступны для ваших программ. Вы можете писать программы, которые обрабатывают эти деревья. В Lisp, эти программы называются макросами. Это те программы, которые пишут программы. (Если вы никогда не хотите попасть в "Матрицу", вы должны быть довольны тем, что вы управляете Lisp-ом).

Мы знаем, что язык Java должен быть достаточно хорошим, поскольку это крутой язык программирования. Так ли это? В субкультуре хакеров, есть еще один язык, называемый Perl, который считается еще более крутым, чем Java. Но есть еще один язык, Python, пользователи которого обычно смотрят свысока на Perl, и есть еще один язык, называемый Ruby, который некоторые считают наследником языка Python.

Если вы будете рассматривать эти языки в указанном порядке - Java, Perl, Python и Ruby, то, если вы являетесь специалистом по Lisp, вы увидите интересную особенность. Каждый следующий из них все больше и больше похож на язык Lisp. Python копирует даже те особенности, которые многие специалисты по Lisp считают ошибочными. И если бы вы в 1975 году показали Ruby и описали его как диалект с синтаксисим языка Lisp, то никто с вами не стал бы спорить.

С 1958 года языки программирования почти догнали Lisp! Первоначально Lisp был создан Джоном Маккарти (John McCarthy) в 1958 году и только сейчас популярные языки программирования догнали те идеи, которые в нем были тогда разработаны.

Lisp просветит вас как личность

Все женатые мужчины будут солидарными со Стивеном Леви (Steven Levy), когда он в своей книге "Хакеры: Герои компьютерной революции" (Hackers: Heroes of the Computer Revolution) приводит пример того, как мыслят хакеры. Мардж Сондерс должна была утром в выходной день вернуться в гараж и попросила своего мужа Боба о следующем: "Есть ли у тебя желание помочь мне отнести продукты?". На что тот ответил: "Нет".

Ошеломленная, она должна была сама тянуть на себе продукты. После того, как то же самое произошло несколько раз, она взорвалась, посылая мужу проклятия и требуя объяснить, почему он всегда отвечает на ее вопрос - "Нет". "Глупо спрашивать", - сказал он. "Конечно, я не хочу помогать тебе нести продукты. Вот, если бы ты спросила, могу ли я помочь тебе их перенести, то это было бы другое дело".

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

С тех пор я узнал, что правильный ответ на вопрос Мардж Сондерс был бы: "Конечно, дорогая! Тебе нужно, чтобы я еще что-нибудь сделал для тебя?". Излишне говорить, что моя жена счастлива и в прошлом месяце мы отпраздновали наш седьмой год совместной семейной жизни.

Граница функционального программирования

В своей знаменитой работе "Why Functional Programming Matters" (Прим.пер.: Есть перевод этой статьи на русский язык — смотрите его по ссылке "Сильные стороны функционального программирования") эксперт по компьютерным наукам Джон Хьюз (R John M Hughes) говорит, что традиционные языки программирования смещают концептуальные ограничения в ту сторону, где проблемы могут быть решены с помощью разбиения на модули. Функциональные языки программирования снимают эти ограничения.

Две особенности функциональных языков, в частности - функции высшего порядка и отложенные вычисления, могут в принцип модульности внести существенный вклад. Например, Lisp позволяет нам работать со списками и деревьями, программировать некоторые численные алгоритмы и реализовывать эвристики вида alpha-beta (алгоритмы из области искусственного интеллекта, используемые в игровых программах). Хотя ключом к успешному программированию является модульность, жизненно важное значение для реального мира имеют функциональные языки, такие как Lisp.

Начинаем

Любой язык, который подчиняется принципам языка Lisp, считается диалектом Lisp. Тем не менее, подавляющее большинство сообщества Lisp использует следующие две версии: ANSI Common Lisp (часто сокращаемый до CL) и Scheme. Здесь, я буду говорить исключительно о диалекте ANSI Common Lisp, чуть более популярном из двух этих диалектов.

Есть много отличных компиляторов Lisp. Но проще всего для начала воспользоваться пакетом CLISP — компилятором Common Lisp с открытым исходным кодом. Он прост в установке и работает в любой операционной системе — на платформах Windows, Mac и в различных вариантах Linux. Пользователи Mac, возможно, захотят воспользоваться компилятором LispWorks, который будет проще заставить работать на их машинах.

Устанавливаем CLISP

Вы можете скачать инсталлятор CLISP с официального сайта. В Windows, вы просто запускаете инсталляционную программу. Для Mac нужно выполнить несколько дополнительных настроек, которые подробно описаны на сайте. Для Linux-машин на базе Debian вы обнаружите, что CLISP уже существует в стандартных репозиториях программного обеспечения. Просто запустите в командной строке команду apt-get install clisp и CLISP будет у вас установлен автоматически. Для других дистрибутивов (Fedora, OpenSUSE и т.д.), вы можете воспользоваться стандартными пакетами, перечисленными на сайте CLISP в разделе "Пакеты для Linux" (если они отсутствуют в репозиториях дистрибутивов).

Запускаем его

Чтобы запустить CLISP, выполните в командной строке команду clisp. Если все пойдет по плану, то вы увидите приглашение к работе, показанное на рис.1.

Рис.1: Запуск CLISP

Точно также как и во всех средах Common Lisp, в среде языка CLISP после того, как вы его запустите, произойдет переход в режим "ввод — вычисление — выдача результата" (read-eval-print-loop, который называется циклом REPL). Это означает, что вы можете сразу же начать вводить код на языке Lisp. Попробуйте, набрав для этого строку (* 7 (+ 4 3)). Ниже под набранным выражением вы увидите результат:

> (* 7 (+ 4 3))
49

В выражении (* 7 (+ 4 3)) символы * и + называется операторами, а числа 7, 4 и 3 называются аргументами.

В повседневной жизни мы должны были бы писать это выражение как ((4 + 3) * 7), но в Lisp мы первым помещаем оператор, за которым идут аргументы, а все выражение заключаем в круглые скобки. Это называется префиксной нотацией, поскольку на первом месте стоит оператор.

Кстати, если вы допустили ошибку и CLISP начнет вести себя ненормально, просто наберите команду :q и все будет исправлено. Если вы хотите завершить работу CLISP, просто наберите команду (quit).

А что под "капотом"?

Давайте не будем идти традиционным путем, начиная изучать с азов (изучение синтаксиса языка, его основных функций и т.д.). Иногда, выяснение деталей, лежащих в основе, оказывается более трудным, чем общее понимание возможностей. Конрад Барский (Conrad Barski) пытаясь заинтересовать нас языком Lisp, показывает, как на нем написать игру. Давайте воспользуемся его методом и напишем простую игру с интерфейсом из командной строки, в которой используется алгоритм двоичного поиска.

Мы знаем, что методика двоичного поиска представляет собое деление данных на две части, что постепенно сужает область поиска до тех пор, пока не будет найдено совпадение или пока для обработки не будет больше элементов. Это классическая игра на отгадывание чисел. Попросите вашего друга (или, лучше - вашего начальника, которые не силен в технологиях, и который кричал на вас в последний раз, когда вы уснули во время заседания) выбрать (в уме) число от 1 до 100 и ваша программа на Lisp-е отгадает его не более, чем за 7 итераций.

Вот как Барский объясняет игру:

Чтобы создать эту игру, нам нужно написать три функции: guess-my-number (отгадывание-числа), smaller (число-меньше) и bigger (число-больше). Игрок просто вызывает эти функции в цикле REPL. Чтобы вызвать функцию в Lisp, вы должны заключить ее в скобки, а также указать любые параметры, которые вы хотите передать в функцию. Поскольку для этих функций не требуется никаких параметров, мы, когда входим в них, просто заключает названия этих функций в скобки.

Стратегия этой игры следующая:

В Common Lisp функции определяются с помощью определения defun следующим образом:

defun function_name(arguments)
...)

Когда игрок будет обращаться к функциям, которые составляют нашу игру, программе потребуется отслеживать нижний и верхний пределы. Чтобы делать это, нам нужно создать две глобальных переменных, которые будут называться *small* and *big*. Переменная, которая определяется в Lisp как глобальная, называется определением верхнего уровня. Мы можем с помощью функции defparameter создать новые определения верхнего уровня.

> (defparameter *small* 1)
*SMALL*
> (defparameter *big* 100)
*BIG*

Звездочки, окружающие имена *big* и *small*, ласково называемые наушниками, выбраны совершенно произвольным образом и являются обязательными. Lisp рассматривает эти звездочки как часть имени переменной и игнорирует их как операции. У пользователей языка Lisp принято помечать глобальные переменные таким образом с тем, чтобы их можно было отличать от локальных переменных, которые будут рассмотрены в следующих статьях. Кроме того, когда Lisp читает ваш код, лишние пробелы и разрывы строк полностью игнорируется.

Теперь давайте определим первую функция, которая будет называться guess-my-number (отгадай мое число). В ней для отгадки числа, которое задумал игрок, будут использоваться значения переменных *big* и *small*. Определение будет выглядеть следующим образом:

> (defun guess-my-number()
        (ash (+ *small* *big*) -1))
GUESS-MY-NUMBER

Всякий раз, когда мы в цикле REPL запускаем фрагмент кода, подобный приведенному выше, в командную будет для введенного выражения выдаваться значение результата. В каждой команде в ANSI Common Lisp генерируется возвращаемое значение. Команда defun, например, просто возвращает имя вновь созданной функции. Вот почему после того, как мы обратились к defun, мы увидим в REPL имя функции, которое было нам возвращено.

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

Мы реализуем это в функции guess-my-number, добавив сначала цифры, которые представляют собой верхний и нижний пределы, затем с помощью функции арифметического сдвига ash делим пополам сумму пределов и сокращаем возможные результаты. Встроенная функция ash в Lisp берет число в двоичном виде и сдвигает его двоичные разряды влево или вправо, отбрасывая те биты, которые теряются в процессе сдвига. Например, число 11, записанное в двоичном формате, имеет вид 1011. Мы можем сдвинуть биты с помощью комады ash влево на 1 позицию, которая указывается в качестве второго аргумента:

> (ash 11 1)
22

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

> (ash 11 -1)
5

Давайте посмотрим, что происходит, когда мы вызываем нашу новую функцию:

> (guess-my-number)
50

Поскольку это наша первая догадка, то значение, которое мы видим, когда вызываем эту функцию, указывает, что все происходит так, как и планировалось: программа выбрала номер 50, который как раз посередине между 1 и 100. Теперь, давайте напишем наши функции smaller и bigger. Точно также как и функция guess-my-number, они являюся глобальными функциями, определяемыми с помощью defun:

> (defun smaller()
      (setf *big* (1- (guess-my-number)))
      (guess-my-number))
SMALLER
 
> (defun bigger()
      (setf *small* (1+ (guess-my-number)))
      (guess-my-number))
BIGGER

Во-первых, давайте воспользуемся defun для того, чтобы начать определение новой глобальной функции smaller. Затем воспользуемся функцией setf для изменения значения глобальной переменной *big*. Поскольку мы знаем, что число должно быть меньше, чем последняя догадка, наибольший предел должен быть на единицу меньше, чем последнее значение, предложенное в качестве догадки.

Это вычисляется с помощью кода (1- (guess-my-number)) следующим образом: сначала вызывается наша функция guess-my-number, которая берет самое последнее значение, предложенное в качестве догадки, и с помощью функции 1- из результата вычитается 1.

Наконец, мы хотим, чтобы наша функция smaller показала нам новую догадку. Мы делаем это, поместив вызов функции guess-my-number в последней строке в теле функции. На этот раз функция guess-my-number будет использовать обновленное значение *big*, в результате она вычислит следующую догадку. Окончательное значение нашей функции будет возвращено автоматически, в результате чего наша новая отгадка (сгенерированная функцией guess-my-number) должна быть возвращена функцией smaller.

Функция bigger работает точно так же, за исключением лишь того, что она увеличивает значение *small*. Если вы, в конечном счете, вызываете функцию bigger, вы говорите, что ваш номер больше, чем предыдущие предположение, так что наименьшее значение, которое загаданное число может принимать (которое теперь будет представлено переменной *small*), будет на единицу больше, чем предыдущая догадка. Функция 1+ просто добавляет 1 к значению, возвращаемому функцией guess-my-number.

Чтобы завершить нашу игру, давайте добавим функцию start-over, которая будет перезагружать наши глобальные переменные:

> (defun start-over()
      (defparameter *small* 1)
      (defparameter *big* 100)
      (guess-my-number))

Как вы видите, функция start-over перезагружает значения *small* и *big*, а затем снова вызывает функцию guess-my-number для того, чтобы выдать новую первоначальную догадку. Всякий раз, когда вы захотите начать совершенно новую игру с другим номером, вы можете вызвать эту функцию и перезагрузить игру.

На рис.2 наша игра показана в действии для случая, когда загадано число 74.

Рис.2: Игра в действии.

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

Продолжение следует...

---

---