Определение функций

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

В языке Лисп для этого применяется лямбда-выражение:

(lambda ({переменная}*){форма}*)

Здесь конструкция ({переменная}*) называется лямбда ─ списком и представляет собой список формальных параметров, которые соответст­вуют аргументам функции. Последовательность форм в лямбда выражении определяет правило формирования значения функции и называется телом функции. Пусть требуется определить функцию, вычисляющую х⁵. Тогда лямбда-выражение будет иметь вид:

(lambda (х) ( * х х х х х))

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

(lambda (x у) (cons x (cons у nil)))

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

1. ((lambda (x)(* x x x x x)) 4) ─> 1024

2. ((lambda (x y) (cons x (cons у nil))) 'a 'b) ─ > (A B)

В первом примере формальному параметру X лямбда ─ списка присваивается фактическое зна­чение 4, а затем вычисляется тело лямбда ─ выражения. Во втором примере формальным параметрам X и У назначаются значения фактических пара­метров, заданных атомами А и В, из которых строится список (А В). После произведенных вычислений связи между формальными параметрами и значе­ниями фактических параметров разрушаются.

Вычисление с помощью лямбда ─ вызовов требует каждый раз при очередном вызове заново переписывать тело функции. Проблема решается, если с лямбда ─ выражением связать не­которое имя (символ). Для связи имени и лямбда ─ выражения в Лиспе применяется форма DEFUN:

( defun имя лямбда ─ выражение )

При этом для упрощения записи в лямбда ─ выражении опускается слово LAMBDA и скобки. В итоге получаем:

(defun имя лямбда ─ список {форма}*)

Результатом вызова формы DEFUN является имя определенной функции. Например:

(defun stepen 5 ( х ) (* х х х х х)) ─ > STEPEN 5

(defun spisok ( х у) (cons x (cons у nil))) ─ > SPISOK

Теперь указанные выше лямбда ─ вызовы можно заменить следующи­ми вызовами:

(stepen 5 4) ─ > 1024

(spisok 'а b) ─ > (АВ)

Отметим, что имя функции представляется символом. Поэтому мож­но говорить о том, что DEFUN устанавливает связь между символом и оп­ределением функции. Создавать функции можно в любом текстовом редакторе и хранить в файле с расширением .lsp. Определения функций могут храниться в файлах и загружаться используя функцию LOAD:

(load <имя файла>)

Эта функция загружает файл выражений и выполняет эти выражения.

<Имя файла> - это строковая константа, которая представляет собой имя

файла без расширения (подразумевается расширение ".lsp"). Если

операция успешно завершена, LOAD возвращает имя последней функции, определенной в файле. Если операция не выполнена, LOAD возвращает имя файла в виде строкового выражения.

После запуска интерпретатора необходимо функцией load загрузить файл с библиотекой, к примеру, созданных пользователем функций на диске С: в каталоге PROG.

>(load “C:\\prog\\bibl.lsp”)

Связывание и область действия переменных

Формы группы SET выполняют связывание в результате побочных эффектов. Возникающие при этом связи значений и переменных остаются в силе после завершения SET-вызовов.

Если требуется установить локальные Связи, то используется форма LET:

(let ({( переменная форма-инициализатор )}*){ форма }*)

Здесь форма-инициализатор задает новое значение переменной, ко­торое доступно только в переделах LET. По окончании LET-вызова восста­навливается старое значение переменной в соответствии со связями, кото­рые имела переменная во внешнем окружении LET. Значение, возвращае­мое LET-вызовом, соответствует последней вычисленной форме, входящей в LET. Например,

(setf х 5) ─ >5

(set у 7) ─ >7

let ((х 10) (z 6))(+ х у z)) ─ >23

х ─ > 5

z ─ > Error: UNBOUND ─ VARIABLE

В этом примере в LET ─ вызове устанавливаются локальные связи для переменных X и Z. Переменная Y в LET ─ вызове является свободной. Значе­ние свободной переменной определяется связями внешнего окружения LET, т.е. Y=7. После завершения LET─ вызова переменная X восстанавливает свое значение, так как была ранее связана с, помощью SETF. Переменная Z не имела связей во внешнем окружении LET, поэтому попытка определить ее значение за пределами LET завершается ошибкой - UNBOUND VARIABLE (несвязанная переменная).

Связывание переменных внутри формы LET выполняется параллель­но. Поэтому в следующем примере результат LET ─ вызова будет пять, а не три:

(setf а 3) ─ > 3

(let (( а 1 ) ( b ( + а 2)) b) ─ > 5

Иными словами, при связывании переменной В здесь используется не локальное значение переменной А, а глобальное, присвоенное вызовом SETF. .

Если необходимо, чтобы связи локальных переменных устанавлива­лись последовательно, то применяется форма LET*. Форма LET представляет собой видоизмененный лямбда-вызов:

(let ((x₁ a₁) (x₂ a₂) ... ( )) .{форма }*) <─>

((lambda (x₁ х₂...х_n) ; формальные параметры

{форма }*)

a₁ а₂ ...a_n) ; фактические параметры

Отсюда следует, что в LET─ форме формальные параметры представ­ляются переменными x₁ х₂ ... х_n, а фактические параметры a₁ а₂ ... a_n задают значения этих переменных. Связь формальных и фактических параметров является локальной и действует только в пределах этих форм. Так как лямбда ─ выражение подставляется вместо имени функции, то и при обычном вызове функции устанавливается связь фактических и формальных параметров, которая действительна только в пределах вызываемой функции.

Определим функцию, вычисляющую выражение

Воспользуемся формой LET*:

(defun f1 (y z)

(let* (( a ( sqrt ( + у z )))

( b ( 4- (* у у ) a))

(с (+ у (/ z 2)))

(x (/с b ))) ; конец списка инициализаторов

х )); возвращаемое значение

В функции F1 значения формальных параметров Y и Z будут локальными. Их начальные значения будут соот­ветствовать значениям фактических параметров, переданных в момент вызова функции. Никакие изменения значений формальных параметров внутри функции не могут отразиться на значениях фактических параметров, так как их связь является локальной. Иными словами, передача значе­ний от фактических параметров к формальным выполняется копированием (т.е. по значению).

Последовательные и условные вычислния

Последовательные вычисления в Лиспе выполняются с помощью форм PROG1, PROG2, PROGN. Данные формы соответствуют составным операторам алгоритмических языков и имеют схожий формат вызова:

(progn {форма}*)

(progl форма1 {форма}*)

(prog2 форма! форма2 {форма}*)

Здесь формы, выступающие в роли аргументов PROG ─ вызовов, вы­числяются последовательно, и в качестве результата возвращается значе­ние последней формы (PROGN), первой формы (PROG1) или второй фор­мы (PROG2). Рассмотрим пример моделирования стекового механизма:

(self stack '(a b с d e f)) ─ > (А В С D E F)

(progl (first stack) (setf stack (rest stack))) ─ > A

stack ─ > (BCDEF)

Последовательные вычисления можно также выполнять с помощью рассмотренной выше формы LET*. Эта форма позволяет использовать ло­кальные переменные и в качестве результата возвращает значение послед­ней вычисленной формы, входящей в LET ─ вызов.

Для выполнения условных вычислений в Лиспе могут применяться формы COND, IF, WHEN, UNLESS и др. Форма COND представляет собой макрос и позволяет выбрать одну из n-ветвей алгоритма. Формат вызова формы COND:

(cond {{тест-форма { форма }*)}*)

В этой записи тест-форма представляет собой логическое выраже­ние, построенное с помощью различных предикатов и логических функ­ций: AND (логическое И), OR (логическое ИЛИ), NOT (логическое отрица­ние). Конструкцию (тест ─ форма {форма}*) называют клозом (clause). Клоз представляет собой список форм.

Приведенный формат вызова формы COND является обобщением следующей записи:

(cond (тест-1 форма-11 форма-12 ... )

(тест-2 форма-21 форма-22 ... )

…

(mecm-i форма-i_l форма-i₂ ... )

…

(mecm-N форма-N1 форма-N2...))

Значение, возвращаемое формой COND, определяется следующими правилами. Последовательно вычисляются значения тест-форм, пока не встретится тест-форма, например mecm-i, значением которой является Т. Затем последовательно вычисляются формы, соответствующего клоза, т.е. форма-i₁, форма-i₂ и т.д. Значение последней вычисленной формы клоза будет представлять результат, возвращаемый формой COND в точку вызова. Если ни одна из тест-форм не получила значение Т, то результатом вы­зова формы COND будет NIL.

Обычно в качестве последней тест-формы используется символ Т. Соответствующие ей формы клоза будут вычисляться, когда ни одна из предшествующих тест-проверок не выполняется. К примеру:

(cond ((eq x 'Bern) 'Switzerland)

((eq x 'Paris) 'France)

((eq x 'Berlin) 'Germany)

((eq x 'Kiev) 'Ukraine)

(t 'unknown))

В рассмотренном примере выбиралась одна из пяти ветвей алгорит­ма. Когда требуется выбрать одну из двух ветвей алгоритма, то использу­ют специальную форму IF. Формат вызова формы:

(if тест-форма then-форма [else-форма])

Если результатом вычисления тест-формы является значение Т, то IF возвращает значение, определяемое then-формой, иначе ─ else-формой, ко­торая может отсутствовать. Условные вычисления можно также организовать с помощью мак­роформ WHEN и UNLESS. Форма WHEN имеет следующий формат вызова:

( when тест-форма { форма }*)

Здесь формы вычисляются лишь в том случае, если результат вычис­ления тест-формы ─ Т. Результатом вызова макроса WHEN является зна­чение последней вычисленной формы. Если тест-форма имеет значение NIL, то и вызов макроса WHEN возвращает NIL. Формат макровызова UNLESS аналогичен формату WHEN, но формы будут вычисляться лишь в том случае, если результат вычисле­ния тест-формы ─ NIL.

Итерационные циклические вычисления

В Лиспе имеется средства для организации цикли­ческих вычислений. Одним из них является макроформа LOOP. Различают два варианта за­писи вызова LOOP - простой и расширенный. Рассмотрим простой вызов LOOP:

(loop {форма}*)

Здесь конструкция {форма}* образует тело цикла. Формы, входя­щие в тело цикла, вычисляются циклически. Цикл завершается, когда управление, в одной из форм, передается макровызову возврата RETURN. При этом RETURN вычисляет значение, возвращаемое в точку вызова LOOP.

Рассмотрим пример. Пусть требуется найти сумму чисел от 1 до N. Ниже приведен текст функции, решающий эту задачу, с помощью макро­вызова LOOP:

(defun nsum (n)

(setf sum 0)

(loop (cond ((zerop n) (return sum))

(t (setf sum (+ sum n)) (setf n (- n 1))))))

Другая конструкция, применяемая для организации итерационных циклов, - макроформа DO. Эта форма позволяет задавать: локальные (лек­сические) переменные цикла, их начальные значения и правила обновле­ния; условие окончания цикла и значение, которое возвращает форма DO; формы, образующие тело цикла.

Общий формат макровызова DO:

(do (({переменная} [начальное_значение [обновление]])}*)

(условие_окончания [форма]*)

{форма}*)

Первый аргумент DO-вызова представляет собой список, состоящий из подсписков. Элементами подсписков являются: переменные цикла; формы, задающие начальные значения переменных; выражения, опреде­ляющие правила обновления переменных. Если форма, устанавливающая начальное значение переменной, не задана, то значение переменной равно NIL. Если не задана форма обновления, то значение переменной может об­новляться в теле цикла.

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

Пусть требуется вычислить факториал числа N. Определим для этого функцию FACTORIAL-DO:

(defun factorial-do (n)

(do ((counter 1 (+ counter 1)) ; управление counter

(result 1 (* result counter))) ; управление result

((= counter (+ n 1)) result))) ; условие окончания

В этом примере для вычисления факториала используется формула n!=(n-1)! n, т.е. факториал каждого следующего числа вычисляется через факториал предыдущего числа. Результаты вычислений на каждом шаге сохраняются в локальной переменной RESULT. Количество выполненных итераций запоминается в счетчике COUNTER. Выход из цикла происходит при условии COUNTER = (n+1).

Часто необходимо выполнять циклическую обработку каждого эле­мента списка. В этом случае применяется макроформа DOLIST:

(dolist (переменная список {результат]) { форма }*)

Если требуется выполнить некоторые действия N раз, то использу­ется макроформа DOTIMES:

(dotimes ( переменная счетчик {результат}) {форма}*)

Здесь действия выполняются для целочисленных значений перемен­ной, задаваемых формой счетчик и лежащих в диапазоне от 0 до N-1. Ко­гда переменная цикла станет равной N, цикл завершится, возвратив значе­ние формы результат.

Циклические вычисления, использующие передачу управления опе­раторам с метками, можно выполнить с помощью макроформы PROG. Уп­рощенный формат PROG-вызова имеет вид:

(prog ({переменная}*) {форма}*)

Указанные в начале PROG-вызова переменные являются локальны­ми. Их начальные значения равны NIL. При необходимости они могут быть инициализированы другими значениями аналогично LET-вызову. Даже ес­ли список переменных PROG-вызова пустой, его необходимо всё равно за­давать. Формы, записываемые внутри PROG-вызова, называются оператора­ми. Если какая-либо форма представлена символом или числом, то она рассматривается как метка. Передать управление на метку можно с помо­щью оператора GO:

(go метка)

Для окончания вычислений и возврата результатов из PROG-вызова применяется форма RETURN. В следующем примере PROG-форма применяется для вычисления факториала:

(defun factorial-prog (n)

(prog ((counter 1)(result 1))

A (setq result (* result counter))

(setq counter (+ counter 1))

(if (= counter (+ n 1)) (return result))

(go A)))

Здесь переменные COUNTER и RESULT получают начальные значе­ния, равные единице.

Рекурсивные функции

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

(defun factorial (n)

(cond ((zerop n) 1)

(t (* (factorial (- n i)) n))))

Процесс рекурсивных вызовов можно исследовать, используя воз­можности трассировки. Включение и выключение меха­низма трассировки выполняется с помощью входящих в состав интерпре­татора директив TRACE и UNTRACE:

Рис. 1. Схема рекурсивных вызовов при вычислении факториала числа 4 .

Лисп позво­ляет также эффективно определять рекурсивные функции для обработки символьных данных. Определим упрощенную версию функции MEMBER. Чтобы отличать ее от функции, встроенной в систему назовём ее MY-MEMBER. Функция проверяет, входит ли элемент X в список Y и воз­вращает подсписок Y, который начинается с обнаруженного элемента:

(defun my-member (x у)

(cond ((null у) nil)

((equal x (first у)) у)

(t (my-member x (rest у)))))

В функции выполняется сравнение элемента X с первым элементом списка Y. Если обнаруживается совпадение, то функция возвращает спи­сок У. Если совпадение не обнаружено, то продолжается поиск элемента X в хвосте списка У. Для этого рекурсивно вызывается функция MY-MEMBER. Первое условие формы COND на каждом шаге рекурсии контролирует спи­сок У. Если этот список исчерпан, то определяемая функция MY-MEMBER возвратит значение NIL. Функция MY-MEMBER использует простую рекур­сию.

Примером функции, выполняющей символьную обработку и осно­ванной на параллельной рекурсии, может служить рекурсивная версия функции MY-INTERSECTION:

(defun my-intersection (a b) (cond

((null a) nil) ;1)

((member (first a) b) ;2)

(cons (first a)(my-intersection (rest a) b))) (t (my-intersection (rest a) b)))) ;3)

Данная функция вычисляет список общих элементов двух списков А и В. В определении функции реализованы три правила:

1. если список А исчерпан, то список общих элементов пустой;

2. если первый элемент списка А входит в список В, то этот элемент

добавляется к списку общих элементов списков (REST А) и В; такой

список формируется рекурсивным вызовом функции MY- INTERSECTION, применяемой к хвосту списка А и исходному списку В;

3. если первый элемент списка А не входит в список В, то строится список общих элементов из хвоста списка А и списка В с помощью рекурсивного вызова функции MY-INTERSECTION.