Основные функции обработки списков

К операциям выделения отдельных частей списков и создания из них новых структур сводятся многие алгоритмы обработки символьной ин­формации. Основными функциями, на основе которых выполняются ука­занные действия, являются встроенные функции CAR, CDR и CONS. Эти функции определяются на основе функций CAR, CDR, CONS. Список - частный случай точечной пары, то применимы функции, аргументы которых заданы точечными парами.

Для доступа к первому элементу точечной пары или списка приме­няется функция CAR. К примеру:

(саr '(а. b)) ─>А

(саr '(а b)) ─> А

Здесь апостроф, обозначает вызов специальной формы QUOTE, ко­торая блокирует вычисление значения s ─ выражения (а. b) или (а b). Если этого не сделать, то Лисп-интерпретатор (EVAL) предпримет попытку вы­числить эти s-выражения. В соответствии с правилами работы интерпрета­тора, первый элемент s-выражения воспринимается как имя функции. Од­нако, на самом деле, функции с именем А нет. Поэтому возникает ошибка: UNDEFINED-FUNCTION (неопределенная функция). Применение функции QUOTE сообщает Лисп ─ системе, что аргументы функции CAR не подлежат вычислению и представляют самих себя.

Для выделения второго элемента точечной пары применяется функ­ция CDR. К примеру:

1. >(cdr'(a.b))

                              В

2. >(cdr'(a b))

                             (В)

В первом случае возвращается атом В, а во втором случае - список, содержащий атом В. Этот результат объясняется тем, что список (А В) в точечной записи имеет вид (А. (В. NIL)). Функция CDR возвращает второй элемент точечной пары (В. NIL), т.е. (В).

Функция CAR и CDR определены только для точечных пар. Для ар­гументов атомов результаты функций CAR и CDR неопределенны.При попытке вызова (саг 'а) формируется сообщение об ошибке. Для выделения произвольных элементов списка используются ком­позиции функций CAR и CDR. К примеру:

1. > (саг (саг '((а b) (b с))))

                                              А

2. > (car (cdr (cdr '(1 2 3))))

            3

Композиции функций CAR и CDR встречаются довольно часто, по­этому для них введены специальные имена:

(car (car х)) < ─ >(сааr х),

(car (cdr х)) < ─ > (cadr x),

(cdr (car x)) < ─> (cdar x),

(cdr (cdr х)) < ─ > (cddrx),

…

(cdr (cdr (cdr (cdr x)))) < ─ > (cddddr x).

В Коммон Лиспе для выделения отдельных элементов списков мож­но использовать более удобные имена функций, отражающие суть выпол­няемой операции. Например:

REST  ─ эквивалентна CDR, возвращает хвост вписка;

FIRST ─ эквивалента CAR, возвращает первый элемент вписка;

SECOND ─ эквивалентна CADR, возвращает второй элемент списка;

THIRD ─ эквивалентна CADDR, возвращает третий элемент списка и т.д.;

TENTH ─ возвращает десятый элемент списка. Имена указанных функций соответствуют порядковым числительным английского языка.

Для создания точечной пары из s ─ выражений в Лиспе применяется функция CONS (конструктор):

                       (cons 'а 'b) ─ > (А. В)

Конструирование списков с помощью функции CONS осуществляет­ся последовательными вызовами:

(cons ('х (cons 'у (cons 'z NIL)))) ─ > (X Y Z)

Здесь сначала строится точечная пара (Z. NIL), затем точечная пара -(Y. (Z. NIL)), а в конце - точечная пара (X.(Y. (Z. NIL))), которая и пред­ставляет список (X Y Z). Таким образом, функция CONS включает очеред­ной элемент в начало списка, представленного ее вторым аргументом. В Лиспе имеется функция LIST с произвольным числом аргументов, которая упро­щает задачу создания списков:

(list 1 'b 'с) ─ > (1 В С)

Списки можно также создавать из других списков путем их объеди­нения. Для этого применяется функция APPEND. К примеру,

(append '(1 2 а) '(b 4 5)) ─ > (1 2 А В 4 5)

В Лиспе имеется ряд других полезных функций для обработки списков:

• LAST  ─ выделяет последний элемент списка (результат - список);

• NTH   ─ выделяет n-й элемент списка;

• SUBST ─выполняет замену элементов в списке;

• BUTLAST ─ выделяет список без последних элементов;

• MEMBER ─ проверяет принадлежность элемента списку;

• LENGTH  ─вычисляет длину списка;

• REVERSE  ─ выполняет обращение списка;

• ADJOIN ─добавляет элемент в множество, представленное списком;

• REMOVE─ удаляет элемент из списка.

 Присваивание значений

Переменные в языке Лисп обозначаются с помощью символов. Пе­ременные ─ это объекты программы, которые меняют свои значения в хо­де её выполнения. Когда символ интерпретируется как форма, представ­ленная переменной, то возвращается его значение. Интерпретация символа как переменной это только одна из возможностей. Для того, чтобы присвоить символу значение, применяется функция SET. Эта функция присваивает символу некоторое значение и возвра­щает его в качестве результата. Функция SET имеет два аргумента. Первый аргумент представляется формой, задающей символ, а второй ─ формой, определяющей значение символа, к примеру:

1. (set 'х '(a b с)) ─ > (А В С)

2. (set (car x) '(d e)) ─ > (D E)

Здесь символу X присваивается значение (А В С), а символу А значе­ние ─ (D Е). Символу можно также присвоить значение с помощью вызова спе­циальной формы SETQ или макроса SETF. Формат вызова специальной формы SETQ:

(setq {символ форма }*)

В отличие от функции SET, форма SETQ блокирует вычисление зна­чений символов. К примеру,

1. (setq x'(a b с)) ─> (А В С)

2. (setq у 12 z (+ у 10)) ─ > 25

Присваивание значений символам в форме SETQ выполняется по­следовательно слева направо, т.е. в момент присваивания значения симво­лу Z, символ Y уже получил значение 12. Результатом вызова SETQ являет­ся последнее присвоенное значение или NIL, если аргументы формы SETQ не были заданы.

 Предикаты

Для обработки данных необходимы различные функции, позволяю­щие выяснять те или иные свойства данных. Функции, выполняющие такую проверку, возвращают логические значения и называются предикатами. В Лиспе имеется боль­шой набор предикатов. Рассмотрим основные встроенные предикаты Лисп ─ систем.

Функция EQ сравнивает значения двух своих аргументов. При этом сравнение выполняется не на логическом уровне, а на физическом, т.е. вы­ясняется, представлены ли аргументы в памяти ЭВМ одной и той же физи­ческой структурой данных. Функция EQ возвращает значение Т, если ее аргументы ─ символы, и в памяти ЭВМ они представлены одной и той же структурой. Функция EQ требует, чтобы ее аргументы были символами. К примеру:

(eq 5.0 5.0) ─ > NIL

В Лиспе имеется функция EQL, которая аналогична EQ, но дополни­тельно позволяет сравнивать числовые значения одинаковых типов. Срав­нение чисел разных типов выполняется с помощью предиката "=". К примеру:

(eql 5.0 5.0) ─ > Т

(= 5 5.0 0.5е1) ─ > Т

Сравнение объектов Лисп ─ программы на уровне абстрактных струк­тур выполняется с помощью предиката EQUAL. Данный предикат обобщает предикат EQL и может сравнивать символы, однотипные числа, строки, списки:

(equal 'а 'а) ─ > Т

                       (equal '(a b с) '(a b с)) ─ > Т

 (equal 5.0 5) ─ >NIL

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

Предикат NULL позволяет установить, представляет ли его аргумент пустой список:

(null (cdr '(а))) ─ > Т

 (null T) ─ > NIL

В Лиспе имеется большой выбор предикатов, классифицирующих типы значений: ATOM, NUMBER, INTEGERP, FLOATP, RATIONALP, SYMBOLP, LISTP и др. Предикат АТОМ проверяет, представляет ли его аргумент атом:

(atom 'a) ─ > Т

(atom nil) ─ > Т

Предикат NUMBERP устанавливает, является ли его аргумент чис­лом:

(number 5.0) ─ > Т

(number 'а) ─ > NIL

Предикаты INTEGERP, FLOATP, RATIONALP позволяют выяснить, относится ли значение аргумента к целым, вещественным или рациональ­ным числам, соответственно. Предикаты SYMBOLP, CONSP, LISTP позволяют из множества раз­личных значений выделять символы, точечные пары и списки:

(setq х '(a b с)) ─ > (А В С)

(symbolp х) ─ > NIL

(consp х) ─ >Т

(listp х) ─ >Т

(consp '()) ─ >NIL

(listp '())─ > Т

Для проверки свойств числовых значений в Лиспе используются предикаты: ZEROP (равенство нулю), ODDP (нечетность), EVENP (чет­ность), MINUSP (отрицательность).

Рассмотренные предикаты применяются при построении тест-форм условных выражений.

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

Чтобы определить функцию, необходимо указать количест­во аргументов функций и их тип, а также правило 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 {форма}*)

(prog 2 форма! форма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 форма- N 1 форма- N 2...))

Значение, возвращаемое формой 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.

 Ввод-вывод

При работе с интерпретатором Лиспа ввод-вывод выполняется ав­томатически. Интерпретатор читает вводимое пользователем s-выражение (READ), вычисляет его (EVAL) и выводит результаты (PRINT). В простей­шем случае функция READ не требует аргументов. После вызова этой функции происходит обращение к стандартному входному потоку и счи­тывание введенного пользователем s-выражения. Введенное выражение возвращается в точку вызова READ.

Определим функцию, которая находит сумму четырех введенных с клавиатуры чисел:

(defun sum4 ()

(+ (read) (read) (read) (read))

Для вызова этой функции необходимо напечатать (sum4), а затем ввести четыре числа:

> (sum 4)

1 234

─ > 10

 >

Если требуется вводить данные из файлов, то сначала необходимо открыть с помощью функции OPEN соответствующий входной поток:

(setf vvod (open "extern.dat" direction:input))

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

(read vvod)

В этом случае произойдет обращение к файлу "extern.dat", и из него будет считано одно s-выражение. Результатом вызова функции READ будет s-выражение, введенное из файла.

Для вывода значений в Лиспе используется функция PRINT. Эта функция имеет один аргумент, значение которого выводится в выходной поток. Функция PRINT перед выводом значения осуществляет переход на новую строку, а после печати значения выводит пробел

(print '(abc))

(a b с)

─ > (А В С)

Здесь список (А В С) дважды отображается на экране. Дополнительный автоматический вызов функции PRINT происходит в цикле READ-EVAL-PRINT интерпретатора.

Для вывода значений могут также использоваться функции PRIN 1 и PRINC. Функция PRIN 1 аналогична PRINT, но не выполняет переход на но­вую строку и не выводит пробел. Функция PRINC дает возможность напе­чатать строку без ограничивающих кавычек:

(princ "lisp") ─ > lisp

Для перехода при выводе значений на новую строку можно исполь­зовать функцию TERPRI. У функции TERPRI нет аргументов. Если требует­ся вывести на печать имя символа, содержащее пробелы, скобки или строчные и заглавные буквы, то применяют знак отмены "\" или ограничи­вающие вертикальные линии "|". Все рассмотренные функции вывода по­зволяют осуществлять вывод в выходной поток открытый, с помощью функции OPEN:

(serf stran (open "extern.dat" direction:output:if-exists:append))

(print '|a b с d| stran) ─>  |a b с d|

(print '\a\C \ \d stran) ─>  |aC d|

(princ '|a b с d| stran) ─ > |a b с d|

Здесь вторым аргументом функции является выходной поток STRAN, связанный с файлом EXTERN. DAT.

При работе с файлами удобно использовать макроформу WITH-OPEN-FILE. Она позволяет открыть поток, задать режим работы с ним, выполнить необходимую его обработку и закрыть его:

(with - open - file (поток имя-файла {опция}*) {декларация}* {форма}*)

Вызов WITH-OPEN-FILE базируется на использовании функции OPEN. Ре­жимы открытия потока задаются с помощью аргумента опция. Они полно­стью соответствуют ключевым параметрам, указываемым при вызове функции OPEN. Формы вызова WITH-OPEN-FILE вычисляются последова­тельно. В качестве результата возвращается значение последней формы. В приведенном ниже примере открывается поток с именем STORE, который связывается с файлом TEST1.LSP. В файл циклически записываются s-выражения, вводимые с клавиатуры. Формирование файла завершается, если с клавиатуры вводится атом EOF:

(defun writer ()

(with-open-file (store "testl.lsp": direction:output

    : if-exists: append

    : if-does-not-exist:create)

(princ "Введите s -выражение")

(terpri)

(princ "Для завершения ввода напечатайте EOF ")

(terpri)

(do ((item (read) (read))); чтение s- выражения

((eq item 'eof) 'end-of-session)

(print item store))))

Для управления формой вывода в Коммон Лиспе применяется функ­ция FORMAT:

(format поток шаблон & REST аргументы)

Если поток задан символом Т, то функция осуществляет вывод на экран. Шаблон представляет собой строку, которая может содержать коды для управления печатью. Перед управляющими кодами записывается знак "~" (тильда). Если в шаблоне нет управляющих кодов, то функция FORMAT выводит строку шаблона так же, как и функция PRINC.