Чтобы чуть-чуть познакомиться с синтаксисом и основными функциями Лиспа, возьмём другой пример (с ним нам будет легче иметь дело) из книги норвежского писателя Эрленда Лу "Наивно. Супер":
Вот что бы я рисовал будь я художником:
- велосипеды,
- пустыни,
- мячи,
- девушек,
- часы,
- людей, опоздавших на автобус.
Этот список называется "Вот что бы я рисовал будь я художником", но для простоты мы назовём его would_be_painter. Это и будет именем переменной нашего списка.
Создаём список:
(setq would_be_painter (list bikes deserts balls girls clocks people_late_for_a_bus))
Эта строка, конечно же, нуждается в объяснении. Всё, что находится в скобках, в Лиспе обозначает список. Так, например, (1 2 3) - список, и (a (b c) d (1 2 3 4 5)) - тоже список. В приведённом примере, вы видите список, начинающийся словом (атомом в терминах Лиспа) setq, за которым следует атом would_be_painter, а за ним - последний элемент этого списка, который тоже заключён в скобки, то есть сам по себе является вложенным списком - (list bikes ...).
Некоторые из списков - особенные. Эти списки начинаются не просто с некоего атома, а с названия функции. Она может быть как встроенной функцией Лиспа, так и функцией, определённой пользователем. В нашем примере setq - это встроенная функция Лиспа, которая связывает имя переменной (которая является вторым элементом списка, возглавляемым setq) с её значением, представляющим собой третий, заключительный элемент списка. Вторым элементом списка идёт атом would_be_painter, который станет названием переменной, а третьим элементом - вложенный список, начинающийся со слова list.
Внимание! Мы подошли к очень важному моменту в понимании природы Лиспа. В Лиспе программа никак не отделена от данных. Мы только что увидели, что вызов функции - это самый настоящий список, ничего более, а список в Лиспе - это и есть главное хранилище данных программы.
Такой, казалось бы, простой вывод ведёт к очень серьёзным последствиям. Представление программ (то есть вызовов функций) в виде обычных данных программы даёт возможность манипулировать самой программой так, как будто это не программа, а просто список данных. И наоборот - из некоего набора элементов можно "на лету" сконструировать функцию Лиспа и вызвать её[1]. В этом смысле Лисп несколько напоминает язык ассемблера. Вспомните игру Core Wars и её ассемблерный язык Redcode. В памяти виртуального компьютера MARS инструкции Redcode ничем не отличались от данных языка, и это давало нам простую возможность видоизменять программу по ходу дела и позволяло программе копировать саму себя в памяти так, как будто это не программа, а просто её данные.
Однако, мы отвлеклись. Вернёмся к вложенному списку из нашего примера. Этот список - тоже вызов встроенной функции Лиспа - list. Назначение этой функции чрезвычайно просто - она возвращает список своих аргументов. Хочется добавить, что оно настолько просто, что даже не сразу удаётся понять, что же делает эта функция. А делает она вот что:
вызов функции
(list bikes deserts balls girls clocks people_late_for_a_bus)
в качестве значения вернёт список
(bikes deserts balls girls clocks people_late_for_a_bus).
Теперь должно быть понятно, что происходит в примере: переменная would_be_painter получает значение списка (bikes deserts balls girls clocks people_late_for_a_bus).
Перед тем, как начать экспериментировать с этим списком, вернёмся ещё раз к его рекурсивной структуре. На рисунке наш список "разобран на части": каждый раз вы можете увидеть его голову и хвост, который сам по себе тоже список и в свою очередь имеет голову и хвост, и так далее.
Несколько слов о рисунке.
В программировании связанные списки принято обозначать с помощью стрелок, которые ведут от одного элемента к другому в одном и том же направлении. Это объясняется внутренним представлением списка в памяти - каждый элемент списка действительно указывает на то место в памяти, где расположен следующий элемент. При таком спсобе обозначения мы всегда можем узнать, где у списка голова, а где хвост.
В конце списка вы видите треугольник[2] с надписью nil. Так в Лиспе обозначают пустой список, то есть список, не содержащий ни одного элемента. Чтобы сохранить рекурсивность определения (в котором, как вы помните, утверждается, что хвост каждого списка - это тоже список), считается, что последним "элементом" каждого списка является пустой список nil. Таким образом, даже у списка, состоящего из одного элемента, есть хвост - пустой список[3].
***
А теперь рассмотрим подробно самый, пожалуй, часто приводящийся пример рекурсивной программы на LISPе – вычисление факториала (то есть произведения всех натуральных чисел от единицы до данного числа N. Так, например, факториал 5 равен 1*2*3*4*5 = 120).
Чтобы понять рекурсивную сущность этой программы, давайте подумаем о том, как мы сами стали бы вычислять факториал 5, начиная с конца выражения 1*2*3*4*5, а не с начала.
Это несложно: пятерку мы должны умножить на то, что получится в результате выражения 1*2*3*4. Удивительно, но этого рассуждения достаточно, чтобы понять как работает рекурсия ! Ведь результат выражения 1*2*3*4 это по нашему же определению – факториал 4. Значит, чтобы найти факториал 5, нужно найти факториал 4 и результат умножить на 5.
И вот тут-то мы делаем огромный «концептуальный» шаг: мы предполагаем, что LISP (а в общем случае – любой другой язык программирования, разрешающий рекурсию) сам знает, как найти факториал 4. Нам нужно только взять результат и умножить его на 5.
В общем случае, если нам нужно найти факториал числа N, мы предполагаем, что LISP знает как найти факториал числа N-1, а нам остается только умножить результат на N, что не представляет проблемы.
Таким образом, функция fact по большей части состоит из умножения данного числа N на результат, возвращаемый этой же самой функцией c аргументом N-1.
Конечно, для такого смелого предположения как «LISP сам знает» нужны причины. И причины эти довольно просты: достаточно продолжить цепочку рассуждений.
Итак, чтобы найти факториал 5 нужно факториал 4 умножить на 5. Но, в свою очередь, чтобы найти факториал 4 достаточно 4 умножить на 1*2*3, то есть на факториал 3. А чтобы найти факториал 3, нужно умножить 3 на 1*2… Наши рассуждения останавливаются на единице, которая является факториалом самой себя.
Из такого рассуждения следует вывод: применение рекурсии возможно в задачах, которые делятся на более простые подзадачи, решаемые тем же самым способом.
В этих случаях мы предполагаем, что язык, на котором мы программируем, «знает» как решить более простую задачу, а мы лишь указываем ему как завершить дело (в нашем случае – умножение результата подзадачи на данное число это и есть «завершение дела»).
Здесь же необходимо упомянуть и о базисном случае рекурсии. Так называется задача, которая не делится на более простые подзадачи. В случае факториала – это число 1, которая является факториалом самого себя. Мы обязательно должны указать LISPу на такую «неделимую задачу», иначе рекурсия никогда не остановится.
Вооруженные всеми этими знаниями, мы готовы взглянуть на лисповскую программу, находящую факториал:
(defun fact (N)
(if (> N 1)
(* N (fact (- N 1)))
1
))
Первая строчка – это определение функции, вычисляющей факториал. Она будет называться fact. В качестве аргумента функция принимает целое число N.
Во второй строке происходит проверка на «базисный случай» рекурсии, а именно задается вопрос – больше ли данное число N единицы ? Если нет – ответ прост: факториал единицы это сама единица (четвертая строчка). Именно это значение вернет функция fact в таком случае. Если же число N больше единицы, значением функции станет то, что написано в третьей строке, а именно: результат умножения числа N на факториал числа N-1 (то есть на результат того, что вернет функция fact, если ей в качестве аргумента передать число N-1).
Это в точности соответствует нашим рассуждениям о нахождении факториала !
В следующей части мы подробно разберём решение ещё одной знаменитой рекурсивной задачи.
[1] Для вызова "на лету" сконструированной функции используется функция Лиспа eval, о которой речь впереди.
[2] Часто этот последний элемент списка обозначается в виде значка заземления.
[3] Хвостом самого пустого списка тоже будет пустой список.