Перейти к основному содержимому

Функции и рекурсия в Lisp

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ
Разработчику Архитектору

Функции и рекурсия в Lisp​

Common Lisp

defun, #', mapcar — Common Lisp. В Scheme то же выражается через define и (map f lst).

Функции в Lisp — объекты первого класса:

  • их можно передавать;
  • возвращать;
  • хранить в данных.

Интерактивное демо — вызов функции и стек на примере JavaScript. В Lisp объявление через defun, но вызов, аргументы и возврат устроены так же. Обобщённо: функции в коде.

Play ITЗагрузка интерактивного демо…

Определение именованных функций — defun​

Основной способ создания функции в Lisp — использование специальной формы defun. Эта форма связывает имя функции с её телом и списком параметров. Синтаксис defun универсален и поддерживается во всех диалектах Lisp, включая Common Lisp, Scheme и Clojure (с адаптацией под особенности конкретного языка).

Форма defun состоит из трёх обязательных компонентов:

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

Пример простой функции:

(defun square (x)
  (* x x))

Эта функция называется square, принимает один аргумент x и возвращает результат умножения x на самого себя. Вызов (square 5) приведёт к вычислению значения 25.

Параметры в defun могут быть простыми (позиционными), необязательными, ключевыми или собираться в список с помощью специального символа &rest. Это позволяет создавать функции с гибкой сигнатурой, адаптированные под разнообразные сценарии использования.

Например, функция с необязательным параметром:

(defun greet (name &optional greeting)
  (if greeting
      (format nil "~A, ~A!" greeting name)
      (format nil "Hello, ~A!" name)))

Вызовы (greet "Alice") и (greet "Alice" "Good morning") дадут разные результаты, демонстрируя, как одна и та же функция может вести себя по-разному в зависимости от контекста вызова.

Важная особенность defun — создание глобального имени. После определения функция становится доступной из любого места программы, где виден её символ. Это упрощает модульность и повторное использование кода.

Анонимные функции — lambda​

Помимо именованных функций, Lisp предоставляет механизм создания анонимных функций через форму lambda. Анонимная функция не имеет постоянного имени и существует только в том контексте, где она создана. Такие функции особенно полезны при передаче логики как аргумента другим функциям или при необходимости кратковременного вычисления без привязки к глобальному пространству имён.

Синтаксис lambda аналогичен defun, но без указания имени:

(lambda (x) (* x x))

Это выражение создаёт функцию, которая возводит аргумент в квадрат, но не связывает её ни с каким именем. Чтобы использовать такую функцию, её нужно либо применить немедленно, либо передать в другую функцию.

Пример немедленного применения:

((lambda (x) (* x x)) 7)

Результат этого выражения — 49.

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

Функции высшего порядка — mapcar, apply, funcall​

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

Одна из самых распространённых функций высшего порядка — mapcar. Она применяет заданную функцию к каждому элементу списка и возвращает новый список с результатами. Например:

(mapcar #'square '(1 2 3 4 5))

Это выражение вернёт список (1 4 9 16 25). Здесь #'square — синтаксический способ ссылки на функцию square. Знак #’ (читается как "function quote") сообщает интерпретатору, что речь идёт о функциональном объекте, а не о значении символа.

Если вместо именованной функции используется анонимная, запись выглядит так:

(mapcar (lambda (x) (+ x 10)) '(1 2 3))

Результат — (11 12 13).

Функция funcall предназначена для явного вызова функции, переданной как значение. Она принимает функциональный объект и аргументы, затем выполняет вызов:

(funcall #'+ 2 3 4)

Этот вызов эквивалентен (+ 2 3 4) и возвращает 9.

Функция apply похожа на funcall, но принимает последний аргумент в виде списка, который раскрывается как отдельные аргументы функции:

(apply #'+ '(2 3 4))

Этот вызов также возвращает 9, поскольку список (2 3 4) раскрывается в три отдельных аргумента.

Использование mapcar, funcall и apply позволяет писать обобщённый код, не зависящий от конкретной реализации операций. Это усиливает декларативность программ: вместо описания шагов выполнения акцент делается на том, что должно быть сделано.

Рекурсия на списках​

Классический шаблон: база на null, шаг через car/cdr.

(defun my-length (lst)
  (if (null lst)
      0
      (+ 1 (my-length (cdr lst)))))

(defun my-append (a b)
  (if (null a)
      b
      (cons (car a) (my-append (cdr a) b))))

В промышленном коде чаще length и append, но рекурсивная форма совпадает с определением списка как cons-цепочки.

Замыкания — захват окружения и сохранение состояния​

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

Рассмотрим пример:

(defun make-adder (n)
  (lambda (x) (+ x n)))

Функция make-adder принимает число n и возвращает анонимную функцию, которая добавляет n к своему аргументу x. При каждом вызове make-adder создаётся новое замыкание, связанное со своим значением n.

Пример использования:

(defvar add-ten (make-adder 10))
(funcall add-ten 5)  ; → 15

Здесь add-ten — это функция, которая "помнит", что n равно 10, несмотря на то, что make-adder уже завершила своё выполнение. Это возможно благодаря тому, что лямбда-выражение внутри make-adder ссылается на переменную n, и Lisp автоматически сохраняет эту связь в виде замыкания.

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

Ещё один пример — счётчик:

(defun make-counter ()
  (let ((count 0))
    (lambda ()
      (incf count))))  ; incf — мутация; для "чистого" стиля см. Clojure/atoms

Функция make-counter возвращает замыкание, которое при каждом вызове увеличивает внутреннюю переменную count на единицу:

(defvar counter (make-counter))
(funcall counter)  ; → 1
(funcall counter)  ; → 2
(funcall counter)  ; → 3

Переменная count недоступна извне — она существует только внутри замыкания. Это демонстрирует, как Lisp позволяет строить приватное состояние, управляемое через функциональный интерфейс.

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

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

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

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

Пошаговый разбор рекурсии​

Когда рекурсия "не щёлкает", разберите функцию по двум вопросам:

  1. База: когда мы точно останавливаемся?
  2. Шаг: как вход уменьшается к базе?

Пример на сумме списка:

(defun sum-list (lst)
  (if (null lst)
      0
      (+ (car lst) (sum-list (cdr lst)))))

Разбор:

  • если список пустой -> результат 0;
  • если нет -> берём голову и рекурсивно считаем хвост;
  • каждый шаг уменьшает задачу (cdr короче исходного списка).

Такой шаблон переносится на map, filter, обход дерева и многие другие задачи.

Когда брать рекурсию, а когда встроенные функции​

Рекурсия отлично объясняет модель вычисления, но в прикладном коде часто проще и безопаснее использовать библиотечные формы:

  • mapcar вместо ручного "пройти и собрать";
  • reduce вместо ручного аккумулятора;
  • remove-if-not вместо ручной фильтрации;
  • loop/dolist там, где нужен понятный императивный проход.

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

Содержание