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

Оригинал: "Lisp: Tears of Joy, Part 5 "
Автор: Vivek Shangari
Дата публикации: October 1, 2011
Перевод: Н.Ромоданов
Дата публикации перевода: 25 октября 2012 г.
Первую статью серии читайте здесь.
Предыдущую статью серии читайте здесь.

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

Если вы облицовываете пол плиткой, размер которой с ноготь, вы не тратите излишних усилий.
– Пол Грем

Дуг Хойт (Doug Hoyte), создатель ресурса Antiweb приводит много примеров макросов, предназначенных для эффективного использования Lisp. Он говорит, что в то время, как в других языках у вас есть небольшие квадратные плиточки, в Lisp вы можете выбрать плитку любого размера и любой формы. В С программисты используют язык, который непосредственно привязан к возможностям универсального решающего устройства. Если не считать процедуры и структуры, то в C мало возможностей для абстрагирования. Lisp, с другой стороны, разрабатывался не в рамках возможностей и ограничений, имеющихся в компьютерах.

Вместо того, чтобы пытаться делать программу быстрой, лучше спросить, что делает программу медленной. Причины можно условно разделить на три основные категории: (1) плохие алгоритмы, (2) плохие структуры данных (3) и генерация кода.

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

Некто уже понял как, почему и как быстро работает алгоритм; все, что вам нужно сделать, чтобы использовать алгоритм, это перевесте его псевдо-код в то, что может понять ваша система.

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

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

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

Если в Lisp-е предоставляются такие хорошие алгоритмы и структуры данных, то как же возможно, что Lisp-код может быть медленнее, чем код на других языках? Объяснение основано на самой важной конструктивной особенности языка Lisp, т. е. общем коде, иначе знакомой нам как дуализм синтаксиса. Когда мы пишем код на языке Lisp, у нас столько вариантов написания, сколько допускается языком; так поступать нас побуждает сама структура языка.

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

Кажется, чем больше дуализма в каждом выражении, тем короче должна быть программа. Означает ли это, что чтобы достичь или превысить производительность языка C, мы должны сделать наши программы на Лиспе столь же длинными и столь же сложными, как соотвествующие им программы на языке C? Нет, в Lisp-е есть макросы.

Итак, достаточно рекламировать товар, пора перейходить к его использованию, не так ли? Мы начнем с некоторых основ.

Lambda — анонимная функция

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

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

Лямбда определение выглядит как определение defun без имени:

(lambda (a b c n)
    (+ (* a (* n n)) (* b n)))

Вы не можете вычислить лямбда определение; оно должно появиться только там, где Lisp ожидает найти функцию, как правило, в качестве первого элемента формы:

> (lambda (a b c n)
     (+ (* a (* n n)) (* b n)))
#<anonymous interpreted function 21AE8A6A>
 
> ((lambda (a b c n)
     (+ (* a (* n n)) (* b n)))
      1 3 5 7)
70

Макросы

Термин "макрос" ("macro") имеет в Lisp не то же значение, что в других языках. Макросом в Lisp может быть что угодно: от некоторого сокращения до компилятора для нового языка. Макросы (в смысле Lisp) все еще уникальны в Lisp-е. Это отчасти потому, что для того, чтобы иметь макросы, у вас, вероятно, должен быть свой собственный странный взгляд на язык, как и в Lisp.

Это возможно также связано с тем, что если вы прошли этот окончательный шаг к власти, вы больше не можете утверждать, что изобрели новый язык, а создали лишь новый диалект языка Lisp. Если определить язык, в котором есть car, cdr, cons, quote, cond, atom, eq и нотацию для функций, выражаемую в виде списков, вы можете из него построить всю оставшуюся часть языка Lisp. Это, по сути, является определением качества языка Lisp: для того, чтобы это стало возможным, Маккарти придал языку Lisp ту форму, которую он имеет.

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

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

> (defmacro setq-literal (place literal)
    `(setq, place ', literal))
SETQ-LITERAL
 
>(setq-literal a b)
B
 
> a
B
 
> (defmacro reverse-cons (rest first)
`(cons, first, rest))
REVERSE-CONS
 
>(reverse-cons nil a)
(B)

Операция setq-literal работает точно также, как и setq, за исключением того, что ни один из аргументов не вычисляется. Вспомните, что в setq оценивается второй аргумент. Тело setq-literal имеет форму, которая начинается с `(обратный штрих). Обратный штрих ведет себя как кавычка — подавляет оценку всех закрытых форм кроме случаев, когда в форме с обратным штрихом появляется запятая. Символ, идущий после запятой, оценивается.

Итак, в нашем вызове (setq-literal a b), приведенном выше, нужно сделать следующее:

В возвращаемой форме нет ни обратных штрихов, ни запятых. В обращении к setq-literal не оцениваются ни a, ни b, но по разным причинам: a не оценивается, поскольку оно выступает в качестве первого аргумента в setq; b не оценивается, поскольку в форме, возвращаемой макросом, оно появляется после кавычки.

Операция (reverse-cons nil a) реализуется аналогичным образом:

Оба аргумента в reverse-cons оцениваются, поскольку cons оценивает свои аргументы, и в теле нашего макроса не будет кавычек перед каким-либо аргументом. a оценивает символ b, а nil оценивает сам себя.

Макрорасширения

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

Поскольку иногда при отладке бывает полезно посмотреть на этот промежуточный код, в Lisp-е у нас есть возможность сделать это. Функция macroexpand получает на входе s-выражение, которое может быть вызовом макроса. Если это так, то macroexpand применяет макрорасширение к своим аргументам для того, чтобы получить объектный код. Она не будет оценивать этот код, а просто его вернет.

Интерпретатор языка Lisp использует macroexpand для того, чтобы раскрыть макрос, который он пытается оценить. С помощью этой функции вы получите точно такую же картину, которую видит сам интерпретатор языка Lisp.

Для примера, приведенного выше, это работает следующим образом:

> (macroexpand '(setq-literal a b))
(SETQ A (QUOTE B))
T
 
> (macroexpand '(reverse-cons nil a))
(CONS A NIL)
T

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

Обычный макрос

Как правило, аргументы соответствующей вложенной функции вызывают специальную функцию. В частности, достаточно часто используется выражение (function (lambda...)). В Common Lisp можно для (function x) использовать сокращение #'x, где 'x означает (quote x). Давайте напишем специальный макрос, который поможет сокращать эту специальную комбинацию. Мы можем определить макрос flambda, который будет раскрываться в (function (lambda...)) следующим образом:

> (defmacro flambda (&rest l)
       (list 'function (cons 'lambda l)))
FLAMBDA
 
> (macroexpand '(flambda (x y) (cons y x)))
(FUNCTION (LAMBDA (X Y) (CONS Y X)))
T

Поскольку lambda-выражение может содержать любое количество форм, мы для обозначения оставшихся параметров использовали специальный параметр &rest. Этому параметру будет присваиваться список всех аргументов, передаваемых в flambda. Например, в вызове flambda, приведенном выше, параметр rest получит параметр l в качестве значения ((x y) (cons y x)). Затем flambda просто добавит atom lambda перед этим списком, а затем поместит результирующее лямбда-выражение в список, который начинается с символа function. Таким образом, пример "flambda выражения", приведенный выше в качестве аргумента macroexpand, можно сократить при написании полного вызова (function (lambda...)).

Макрос pop

Более интересной функцией является макрос pop, который получает в качестве аргумента символ, значением которого является список. Он уменьшает этот список с помощью cdr и в качестве своего значения возвращает первый элемент списка. По сути, pop рассматривает список как стек и выдает его верхний элемент. Обращение к pop эквивалентно выполнению следующего фрагмента кода:

> (prog1 (car stack) (setq stack (cdr stack)))

Функция prog1 последовательно оценивает все свои аргументы и возвращает значение первого аргумента. Таким образом, для любого конкретного списка, вы можете выполнить строчку кода, показанного выше, которая выполняет нужную функцию. Все, что вы должны сделать — это определить макрос, который раскрывает в код этой формы. Таким образом, вы можете получить (pop stack), который будет раскрыт в prog1 так, как это показано выше.

В действительности в Common Lisp макрос pop определен. Здесь мы в качестве примера напишем свое собственное определение этой функции:

> (defmacro example-pop (stack)
       (list 'prog1
           (list 'car stack)
            (list 'setq stack (list 'cdr stack))))
EXAMPLE-POP

Давайте посмотрим, как работает макрос:

> (setq stack '(a b c))
(A B C)
 
> (example-pop stack)
A
 
> stack
(B C)

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

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

Специальные функции и макросы

Многие из так называемых специальных функций, на самом деле являются макросами. В частности, функции defun, prog, cond, setf и defmacro сами являются макросами в Common Lisp. Например, обращение к setf в свою очередь обращается к более базовой функции — обращению к функции setf, первый аргумент которой является символом, преобразованным в setq, а именно:

> (macroexpand '(setf a 'b))
(SETQ A 'B)

Однако, если левая сторона вызова setf является вызовом функции get, setf превращается в вызов некоторой внутренней функции list-changing, имеющейся в Common Lisp.

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

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

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

---

---