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

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Архитектору

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

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

Определение именованных функций: 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 позволяет писать обобщённый код, не зависящий от конкретной реализации операций. Это усиливает декларативность программ: вместо описания шагов выполнения акцент делается на том, что должно быть сделано.

---

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

Замыкание — это функция, которая сохраняет доступ к переменным из того лексического окружения, в котором она была создана. В 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))))

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

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

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

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

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

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

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

---