Функция putd, имеющая два аргумента, связывает атом, являющийся первым аргументом с lambda - или nlambda -выражением, выступающим в качестве второго аргумента, и возвращает в качестве своего значения имя определяемой функции. Например:

$ (putd F (lambda (X Y) (Cons X Y)))

F

Теперь, определив новую функцию F, мы можем обращаться к ней так:

$ (F 'A '(B))

(A B)

Основным назначением функции putd является, конечно, не возвращение имени, а связывание его с определением функции.

Для доступа к lambda - или nlambda-определениям предназначена функция getd одного аргумента (имя функции), которая возвращает лямбда-определение данной функции. Например:

$ (getd F)

(lambda (X Y) (cons X Y))

Если F есть функция, определенная пользователем, то обращение (getd F) декомпилирует и возвращает определение символа F в виде списка.

Если F является простой функцией или специальной формой, то обращение (getd F) возвращает адрес в физической памяти шаблона функции на машинном языке.

Если F не является специальной формой или функцией, то обращение (getd F) возвращает Nil.

Обращение (getd F flag) возвращает характеристику символа F:

special, если F является специальной формой,

lambda, если F является вычисляемой функцией,

nlambda, если F является невычисляемой функцией,

macro, если F является макро-функцией,

nil, если F неопределен.

Функция (putd F S) компилирует определение S в D-код (специвльное представление для хранения определений функций), при этом модифицирует старое определение функции F и возвращает F. Например:

$ (putd 'Square '(lambda (N) (* N N)))

Square

$ (Square 5)

Функция Movd присваивает функциональное значение, связанное с первым атомом, второму атому. Например:

$ (movd F B)

(lambda (X Y) (cons X Y))

$ (getd B)

(lambda (X Y) (cons X Y))

Функцию movd можно использовать для присваивания других мнемонических имен некоторым функциям LISP без ущерба для эффективности их выполнения.

$ (movd 'car 'First)

First

$ (movd 'cdr 'Rest)

Rest

$ (movd 'cadr 'Second)

Second

$ (movd 'caddr 'Third)

Third

$ (movd 'cadddr 'Fourth)

Fourth

$ (First '(A B C D))

A

2.7.3.2. Функция defun

Fakt

Как и в случае с функцией setqи putd возвращаемое значение функции defun не является главным в ее использовании. Основным является побочный эффект функции defun: она заносит во внутренний словарь имя новой функции и связывает его с правилом вычисления возвращаемого значения.

Данное определение эквивалентно следующему:

$ (putd 'fakt '(lambda(N) (if (= N 0) 1 (* N (fakt (- N 1))))))

Fakt

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

(defun fakt (N)(if (< N 0) nil

(if (= N 0) 1

(* N (fakt (- N 1)))

)

)

)

или

(defun fakt (N)(cond ((< N 0) nil)

((= N 0) 1)

(T (* N (fakt (- N 1))))

)

)

Приведем примеры применения функции defun. Определим функцию atoms, подсчитывающую число атомов в своём аргументе. Функция будет работать следующим образом: Если аргументом является список U, то число атомов равно сумме числа атомов в (car U) и (cdr U). Так как число атомов в каждом из слагаемых меньше, чем в исходном списке, при каждом новом обращении мы будем обрабатывать всё более и более короткие списки и, наконец, придём к случаю, когда аргумент либо пустой список, либо атом. Значением функции atoms при этом должно быть 0 или 1, соответственно. Мы сформулировали сходящуюся рекурсивную процедуру и условие выхода из неё:

(defun atoms (U)(cond ((null U) 0)

((atom U) 1)

(T (+ (atoms (car U)) (atoms (cdr U))))

)

)

(atoms '(A B C)) --> 3

(atoms '(17 217 (13 4) 22)) --> 5

(atoms '()) --> 0

Определим функцию append1 эквивалентную встроенной функции append:

(defun append1 (L1 L2)(if (null L1) L2

(cons (car L1) (append1 (cdr L1) L2)))

)

Встроенная функция reverse инвертирует список. Напишем собственную функцию reverse1, которая будет инвертировать список и все его подсписки любого уровня вложенности:

(defun reverse1 (L)(if (atom L) L

(append (reverse1 (cdr L)) (list (reverse1 (car L))))

)

)

(reverse1 '(A B C D E)) --> (E D C B A)

(reverse1 '(A B ((C D) E))) --> ((E (D C)) B A)

Приведенные примеры определения функций atoms, reverse1 и append1 демонстрируют типичный метод реализации функций обработки списков: при помощи car и cdr список разбивается на две части и каждая из них обрабатывается отдельно (при этом почти всегда используется рекурсивный вызов определяемой функции) и полученные результаты объединяются в конечный ответ.

Рассмотрим еще один метод, часто используемый в функциональном программировании. Вернемся к определению функции reverse1: отдельные элементы списка, являющегося конечным результатом, «накапливаются» на стеке при рекурсивном вызове функции. Когда мы добираемся до самого глубокого уровня вложенности функций, начинается возврат из последовательности вызовов и элементы списка снимаются со стека и собираются в конечный результат (конкретные детали могут зависеть от реализации языка, но суть не изменится). Введем явно объект, накапливающий отдельные элементы результирующего списка: определим функцию rev с двумя аргументами - списками, второй из них будет последовательно получать элементы первого и присоединять к себе в обратном порядке:

(defun rev (L1 L2)

(if (null L1) L2 (rev (cdr L1) (cons (car L1) L2)))

)

Теперь можно определить функцию reverse2 аналогичную reverse1:

(defun reverse2 (L) (rev L nil))

Такой метод носит название «метод накапливающего параметра». Этот метод может привести к существенному повышению эффективности вычислительного процесса. Вернемся к определению функции reverse1 и подсчитаем, сколько раз вызывается основная функция построения списков cons. В случае обращения линейного списка (без подсписков) состоящего из N элементов функция reverse1 вызывает себя рекурсивно N раз; N раз будет вычисляться выражение (list (reverse1 (car L))) эквивалентное (cons (car L) nil) для случая линейного списка. Кроме того, функция reverse1 делает N вызовов функции append, для каждого из этих вызовов append длина первого ее аргумента равна соответственно 1, 2, ..., N-1 и ровно столько раз append будет обращаться к функции cons (см. определение append1). Таким образом, количество вызовов cons функцией append составит

1 + 2 + ... + (N-1) = N*(N-1)/2

Общее количество вызовов cons в функции reverse1 составит

N + N*(N-1)/2 = N*(N+1)/2

В случае использования «метода накапливающего параметра» (функция reverse2) cons будет вызываться функцией rev ровно N раз. Итак, «метод накапливающего параметра» дает существенную экономию вычислений.

Правда, функция reverse2 менее мощная, она обращает только линейные списки. Для обращения вложенных списков можно видоизменить определения функций следующим образом:

(defun rev1 (L1 L2)

(if (null L1) L2 (rev (cdr L1)(cons (list (reverse3(car L1))) L2)))

)

(defun reverse3 (L) (rev L nil))

Рассмотрим еще один пример - сортировки списка, составленного из числовых элементов. Вначале определим функцию insert, которая имеет два аргумента: числовой атом X и упорядоченный список L, а своим значением возвращает упорядоченный список построенный из исходных списка и числа:

(defun insert (X L)(cond((null L) (list X))

((<= X (car L)) (cons X L))

(T (cons (car L) (insert X (cdr L))))

)

)

Теперь определим функцию sort1, которая берет элементы неупорядоченного списка L1 и добавляет их в упорядоченный список L2:

(defun sort1 (L1 L2)(if (null L1) L2

(sort1 (cdr L1) (insert (car L1) L2))

)

)

и, наконец, определим функцию сортировки sort-ins; действие которой сводится к вызову функции sort1 с пустым списком в качестве второго аргумента:

(defun sort-ins (L) (sort1 L nil))

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

(defun fakt (N) (if (= N 0) 1 (* N (fakt (- N 1))))) <==>

(defun fakt (lambda(N) (if (= N 0) 1 (* N (fakt (- N 1))))))

С помощью –формы можно определять невычисляющие функции.

(defun nl1 (nlambda (X) (Car X)))

$ (nl1 ((* 1 2) (+ 1 4))) --> (* 1 2)