Введение в
МИР ЛИСПА
По мотивам лекций Тарасова В.Г. и книг
Э.Хювенена "Мир Лиспа" и
Крюкова А.П. "Программирование на языка R-LISP"

Содержание

Введение

Достоинства языка LISP

Основные элементы языка

Вычисление в Лиспе

Первые программы на Лиспе



<h"

Приятная картинка

Введение

"

Язык Лисп был предложен Дж.Маккарти в 1960 г. и ориентирован на разработку программ для решения задач нечисленного характера.
Английское название этого языка LISP - является аббревиатурой выражения LISt Processing (обработка списков) и хорошо подчеркивает основную область его применения.
Понятие "список" оказалось очень емким. В виде списков удобно представлять алгебраические выражения, графы, элементы конечных групп, множества, правила вывода и многие другие сложные объекты.
Списки являются наиболее гибкой формой представления информации в памяти современных компьютеров. Неудивительно поэтому, что язык, специально предназначенный для обработки списков, быстро завоевал популярность.
Язык Лисп продолжает интенсивно развиваться. На протяжении почти сорокалетней истории его существования появился ряд диалектов этого языка: Common LISP, MacLISP, InterLISP, Standart LISP и многие другие. Различия между ними не носят принципиального характера и в основном сводятся к несколько отличающемуся набору встроенных функций и некоторой разнице в форме написания программ. Поэтому программист, научившийся работать на одном из них, без труда может освоить любой другой.
Вероятно, одним из наиболее значительных этапов развития Лиспа стало появление специализированных Лисп-процессоров и Лисп-машин, подобных компьютеру Symbolics. В них язык Лисп был был реализован аппаратно, что позволило резко повысить скорость работы написанных на Лиспе программ.


<h"

Достоинства языка Лисп

<h"

Одинаковая форма представления данных и программы

Хранение данных не зависящее от места

Автоматическое и динамическое управление памятью

Функциональный образ мышления

Возможность различных методов программирования

Пошаговое программирование

Интерпретирующий или компилирующий режимы выполнения

Лисп - бестиповый язык программирования

Единый системный и прикладной язык программирования <h"

Одинаковая форма представления данных и программы

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


Хранение данных не зависящее от места

Списки, представляющие программы и данные, состоят из списочных ячеек, расположение и порядок которых в памяти не существенны. Структура списка определяется логически на основе имен символов и указателей. Добавление и удаление элемента из списка может производится без переноса списка в другие ячейки памяти. Резервирование и освобождение осуществляется динамически, ячейка за ячейкой.


Автоматическое и динамическое управление памятью

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


Функциональный образ мышления

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


Возможность различных методов программирования

Кроме функционального в Лиспе можно использовать программирование, основанное на обычном последовательном исполнении операторов с присваиваниями, передачами управления и специальными операторами цикла. С помощью макропрограммирования можно запрограммировать новые структуры языка или реализовать совершенно новые языки. В зависимости от системы в Лиспе можно использовать методы программирования более высокого уровня, например такие, как объектно-ориентирование программирование, ситуационное программирование, продукционное программирование, логическое программирование.


Пошаговое программирование

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


Интерпретирующий или компилирующий режимы выполнения

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


Лисп - бестиповый язык программирования

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


Единый системный и прикладной язык программирования

Лисп является одновременно как языком прикладного, так и системного программирования. Он напоминает машинный язык тем, что как данные, так и программа представлены в одинаковой форме. Язык превосходно подходит для написания интерпретаторов и трансляторов как его самого, так и для других языков.
Традиционно Лисп-системы в основной своей части написаны на Лиспе. При программировании, например, транслятора есть возможность использовать методы искусственного интеллекта. Лисп можно в хорошем смысле считать языком машинного и системного программирования высокого уровня. И это особенно характерно для Лисп-машин, которые вплоть до уровня аппаратуры спроектированы для Лиспа и системное программное обеспечение которых написано на Лиспе.
"

Основные элементы языка

<h"

Атомы

Точечные пары

Списки

Базовые функции

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

Имя и значение символа

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

<h"

Атомы

Это один из основных типов данных в Лиспе. Атомы бывают двух классов: идентификаторы и константы. Идентификаторы являются основными элементами, из которых в Лиспе строятся символьные выражения.Примером могут служить: A, PIG, CAT и т.п.
Константы - это величины, которые остаются неизменными во время выполнения программы. В качестве примера можно привести числа 234, 12, -3.133 и т.п. Еще один вид констант - строки. Константами являются также специальные атомы T и NIL.


Более формально в Лиспе бывают следующие типы атомов:


    1. Числа:
      1. Целые числа
      2. Числа с плавающей точкой
    2. Строки
    3. Идентификаторы
    4. Константы T и NIL.


Для того чтобы синтаксически определить эти типы, нам понадобятся следующие вспомогательные определения:

<цифра>
::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0
<буква>::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
<спецсимвол>::= !<любой символ>
<первый символ>::= <буква>|<спецсимвол>
<правильный символ>::= <первый символ>| <цифра>.
Основные же определения выглядят так:

<атом>
::= <число>| <идентификатор>| <строка>| Т | NI
<число>
::= <целое>| <число с плавающей точкой>
<целое>::= <целое без знака>| +<целое без знака> | -<целое без знака>
<целое без знака>::= <цифра>| <целое без знака><цифра>
<число с плавающей точкой>::= <основание>| <основание><показатель>
<основание>::= <целое>. | <целое>.<целое без знака>
<показатель>::= E<целое>
<идентификатор>::= <первый символ>| <первый символ><последовательность>
<последовательность>::= <правильный символ>| <последовательность><правильный символ>
<строка>::= "<последовательность любых символов, не содержащая двойных кавычек>"
Может показаться, что использование в идентификаторах специальных символов - ненужная роскошь, однако это не так. Пусть, например, у нас есть параметр, задающий максимальную степень полинома. Его можно обозначить через М или MAXDEGREE. Однако использование в идентификаторе специальных символов, позволяет обозначить этот параметр через MAXI_DEGREE или даже через МАХ! DEGREE, поскольку "! " согласно определению есть специальный символ.


Точечные пары

Это второй основной тип данных в Лиспе. Точечная пара - это просто упорядоченная пара в которой в качестве разделителя используется точка. Синтаксически точечная пара определяется следующим образом:

<точечная пара>
::=
(<атом>.<атом>) |
(<атом>.<точечная пара>) |
(<точечная пара>.<атом>) |
(<точечная пара>.<точечная пара>)

Примеры точечных пар:

(JOHN.SMITH)
(A.(B.C)).(A.B)

Часто бывает удобно не различать атомы и точечные пары. В это случае говорят об "S-выражениях". По определению:

&tS-выражение ::= <атом>
| <точечная пара>


Списки

Поскольку последовательности являются весьма популярным способом представления данных, в Лиспе выделяется специальные тип S-выражения - список. Он определяется следующим способом:

<список>
::= NIL | ( .<список>)
Если считать атом NIL пустым списком, то это определение можно переписать, используя понятия "первого элемента" и "хвоста" списка:

<список>
::= <пустой список>| (<первый элемент>.<хвост>)
<пустой список>::= NIL
<первый элемент>
::= &ltS-выражение
<хвост>
::= <список>

Пример:

(A.(CAT.(EATS.(MICE.NIL))))
(SINGLE.NIL)

Для того чтобы явно указать на то, что список является линейной структурой, в Лиспе принято также изображать список состоящий из S-выражений S1, S2, S3 , ... , SN, как (S1 S2 S3 ... SN). Пустой список изображается как ().
Правила записи списков можно сформулировать так:
NIL <->()
(S1 . (S2 . (... SN.NIL))) <->(S1 S2 ... SN)

Пример:

(A CAT EATS MICE)
(SINGLE)


Базовые функции

Функцией в математике называется отображение, которое однозначно отображает одни значения в другие. В общем случае функция может задавать отображение из нескольких множеств в множество значений. Например
f(x,y) - z ; отображение пар элементов x,y в множество z.
В языке Лисп как для вызова функции, так и для записи выражений принята единообразная префиксная форма записи, при которой как имя функции или действия, так и сами аргументы записываются внутри скобок. Приведенная выше функция выглядела бы:
(f x y) ; где f - имя функции.
Таким же образом записываются и арифметические действия:
 

Математическая запись

Лисповская запись

X - Y

(- X Y)

X - Y*Z

(- X (* Y Z))

(X - Y)*Z

(* (- X Y) Z)

(X - Y)*(Z+V)

(*(- X Y) (+ Z V))


Единообразная и простая структура вызова функции удобна как для программиста, так и для интерпретатора Лиспа. Вычисляя значения функций, не нужно осуществлять сложный синтаксический анализ выражений.
В конструкцию вводимой функции могут, в свою очередь, входить функциональные подвыражения. Тогда аргументы вычисляемой функции заменяются на новые вычисления, ведущие к определению значений этих аргументов. И т.д. пока значения выражений нельзя будет определить непосредственно, как, например констант.
Вычисление выражений происходит слева на право. Как и в математике первым вычисляются выражения, заключенные в скобки.
В некоторых случаях, если нужно само выражение, а не результат - нужно блокировать вычисления. Например мы хотим обработать (+ 2 3) как список, а не как 5. Чтобы предотвратить вычисление значения выражения, перед выражением нужно поставить апостроф " ' ". Это говорит Лиспу, что выражение надо использовать как есть. Апостроф - это сокращение лисповской формы QUOTE:
'выражение <->(QUOTE выражение)


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

В Лиспе для построения, разбора и анализа списков существуют очень простые базовые функции, которые в этом языке являются примитивами. Простота базовых функций и их малое число - характерные черты Лиспа. Базисными функциями обработки символьных выражений (атомов и списков) являются:
CAR, CDR, CONS, ATOM и EQ
Функции по принципу их использования можно разделить на функции разбора, создания и проверки.

ИСПОЛЬЗОВАНИЕ

ВЫЗОВ

РЕЗУЛЬТАТ

Разбор

(CAR точечная пара)

s-выражение

(CAR список)

s-выражение

(CDR точечная пара)

s-выражение

(CDR список)

список

Создание

(CONS s-выражение s-выражение)

точечная пара

(CONS s-выражение список)

список

Проверка

(ATOM s-выражение)

T или NIL

(EQ символ символ)

T или NIL


Функции ATOM и EQ являются базовыми предикатами. Предикаты - это функции которые проверяют выполнение некоторого условия и возвращают в качестве результата логическое выражение T (в более общем виде, произволное выражение, отличное от NIL) или NIL.
Функции CAR и CDR осуществляют выбор соответственно первого и второго элемента точечной пары. Их можно определить так:
(CAR '(S1.S2)) = S1
(CDR '(S1.S2)) = S2

где S1 и S2 - некоторые S-выражения.
Если аргументом функций является список (в принципе - точечная пара):
Функция CAR возвращает в качестве значения головную часть списка.
Функция CDR возвращает в качестве значения хвостовую часть списка.
Первый элемент списка называется головой, а остаток списка, т.е. список без первого элемента, называется хвостом списка. Обе функции имеют смысл только для аргументов, являющихся списками, а следовательно, имеющих голову. Для аргумента атома они не определены.

Пример:

(car '(a s d f))
a

(car '((as sa) a))
(as sa)

(cdr '(as))
NIL

(cdr '(l s d))
(s d)
Функция CONS позволяет строить S-выражения из частей, создавая точечную пару из двух S-выражений. Его определение выглядит так:
(CONS 'S1 'S2) = (S1.S2)

где S1 и S2 - некоторые S-выражения.
В случае списка CONS присоединяет голову к списку. Конструюрование списка при помощи CONS оказывается довольно громоздким. Для устранение этого неудобства, в Лиспе имеется функция LIST. Ее значением является список, образованные значениями ее аргументов:
(LIST S1 ... SN) = (S1 S2 ... SN) = (S1.(S2.( ... (SN.NIL)...)

Пример:

(cons 'a '(x e))
(a x e)

(cons 'a '(a.b))
(a.(a.b))
Предикат ATOM проверяет, является ли аргумент атомом, что может потребоваться, например, перед применением функции CAR и CDR. Пустой список - является атомом.
Предикат EQ проверяет тождественность двух символов и возвращает T, если они идентичны, и NIL - в противном случае.
Предикат NULL проверяет: является ли список пустым, т.е. значение аргумента равно NIL.

Пример:

(atom '(l a s t))
NIL

(atom 'a)
T

(eq 'cat (car '(cat eat mice)))
T

(eq 'err 'error)
NIL

(null '(s s d))
NIL

(null nil)
T


Имя и значение символа

Значением констант в Лиспе являются сами константы, например, числа и логические константы. Если мы введем константу, то интерпретатор в качестве результата вернет выдаст саму эту константу.
Символам в Лиспе можно присвоить некоторое значение. Для этого используется функция SET, которая позволяет присвоить или связать с символом некоторое значение.
SET вычисляет имя и связывает его
Обратите внимание, что SET вычисляет оба аргумента. Если же вычислять имя символа не надо, то можно использовать функцию SETQ:
(SETQ name 'vaue ) <->(SET 'name 'value)

Пример:

(setq fun '(joke smile))
(joke smile)

fun
(joke smile)

joke
Error: Unbound atom JOKE

Для проверки, связан ли атом, используется предикат BOUNDP, который истинен, когда атом имеет какое-нибудь значение.


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

Определение функций и их вычисление в Лиспе основано на лямбда-исчислении Черча, предлагающем для этого простой и точный формализм. В Лиспе лямбда-выражение имеет вид
(LAMBDA(x 1 x 2 ... x N) f N)
Символ AMBDA означает, что мы имеем дело с определением функции. Символы x i являются формальными параметрами определения, которые именуют аргументы в описывающем вычисления теле функции f N.
Входящий в состав формы список, образованный из параметров, называется лямбда-списком. Телом функции является произвольная форма, значение которой может вычислить интерпретатор Лиспа, например: константа, связанный со значением символ или композиция из вызовов функций.
Например функцию, вычисляющую сумму квадратов двух чисел, можно определить следующим лямбда-выражением:
(lambda(x y)(+ (* x x) (* y y)))
Формальность параметров означает, что их можно заменить на любые другие символы, и это не отразится на вычислениях, определяемых функцией.
Лямбда-выражение - это определение вычислений и параметров функций в чистом виде без фактических параметров. Для применения такой функции к некоторым аргументам, нужно в вызове функции поставить лямбда-определение на место имени функции:
(лямбда-выражение a 1 a 2 ... a N)

где a
i - формы, задающие фактические параметры, которые вычисляются как обычно.

Пример

((lambda(x y)(+ (* x x) (* y y))) 2 3)
13
Лямбда-выражение - функция без имени, это чисто абстрактный механизм для определения и описания вычислений. Ее трудно использовать снова, т.к. она сразу пропадает после вычисления формы.
Безымянные функции используются, например, при передаче функции в качестве параметра другой функции или при формировании функции в результате вычислений.
Дать имя описанию функции можно используя функцию DEFUN, которая вызывается так:
(DEFUN имя лямбда-список тело)

Что можно представить как сокращение
(DEFUN имя лямбда-выражение)
DEFUN соединяет символ с лямбда-выражением (аналогично SET), и символ начинает представлять определенные этим лямбда-вычисления. Значением этой формы является имя новой функции.
Предикат FBOUNDP проверяет, связано ли с символом определение функции.

Пример

(defun list1(x y)
(cons x (cons y NIL)))
LIST

(list1 'ask 'you)
(ask you)

"

Вычисление в Лиспе

<h"

Программа на Лиспе состоит из форм и функций

 

 

LET создает локальную связь

 

 

Предложения PROG1, PROG2 и PROGN

 

 

Разветвление вычислений: условное предложение COND

 

 

Другие условные предложения: IF, WHEN и UNESS

 

 

Циклические вычисления: предложение DO

 

 

Формы динамического прекращения вычислений <h"

Программа на Лиспе состоит из форм и функций

Под формой понимается такое символьное выражение, значение которого может быть найдено интерпретатором.
Ранее мы уже использовали простые формы языка: константы, переменные, лямбда-вызовы, вызовы функций и их сочетания. Кроме того были рассмотрены некоторые специальные формы, такие как QUOTE и SETQ, трактующие свои аргументы иначе, чем обычные функции.
Управляющие структуры Лиспа являются формами и выглядят внешне как вызовы функций. Они будут записываться в виде скобочных выражений, первый элемент которых действует как имя управляющей структуры, а остальные элементы - как "аргументы". Результатом вычисления, так же как у функции, является значение.
Наиболее важные с точки зрения программирования синтаксические формы можно на основе их использования разделить на следующие группы.


LET создает локальную связь

Вычисление вызова функции создает на время вычисления новые связи для формальных параметров функции. Новые связи внутри формы можно создать и с помощью предложения LET. Эта структура определяется так:
      (LET ((m1 знач1)(m2 знач2) ... )     
         форма1
         форма2 ...)
Предложение ET вычисляется так, что сначала статические переменные m1, m2, ... из первого "аргумента" формы связываются (одновременно) с соответствующими значениями знач1, знач2, ... Затем, слева направо вычисляются значения форм форма1, форма2, ...
В качестве значения всей формы возвращается значение последней вычисленной формы. Как и у функций, после окончания вычисления, связи статических переменных m1, m2, ... ликвидируются и любые изменения их значений (SETQ) не будут видны извне.
Значения переменных присваиваются одновременно, т.е. значения вычисляются до того как происходит связывание с формальными параметрами. Новые связи этих переменных еще не действуют в момент вычисления начальных значений переменных.
В форме LET* подобной LET, вычисления значений переменных происходят последовательно слева направо.


Последовательные вычисления: PROG1, PROG2 и PROGN

Предложения PROG1, PROG2 и PROGN позволяют работать с несколькими вычислимыми формами.
(PROG1 форма1, форма2, ... формаN )
(PROG2 форма1, форма2, ... формаN )
(PROGN форма1, форма2, ... формаN )
У этих специальных форм переменное число аргументов, которые они последовательно вычисляют и возвращают в качестве значения значение первого (PROG1), второго (PROG2) и последнего (PROGN) аргумента.


Разветвление вычислений: условное предложение COND

Предложение COND является основным средством разветвления вычислений. Она позволяет управлять вычислениями на основе определяемых предикатами условий. Структура условного предложения такова:
     (COND (p1 a1)
           (p2 a2)
           ...
           (pN aN))
Предикатами p i и результирующими выражениями a i могут быть произвольные формы. Значение предложения COND определяются следующим образом:
    1. Выражения p i , выполняющие роль предикатов, вычисляются последовательно слева направо (сверху вниз) до тех пор, пока не встретится выражение, значением которого не является NIL, т.е. логическим значением которого является истина.
    2. Вычисляется результирующее выражение, соответствующее этому предикату, и полученное значение возвращается в качестве значения всего предложения COND.
    3. Если истинного предиката нет, то значением COND будет NIL.
Рекомендуется в качестве последнего предиката использовать T, и соответствующее ему результирующее выражение будет вычисляться всегда в тех случаях, когда ни одно другое условие не выполняется.
Возможен следующий синтаксис COND:
     (COND (p1 a1)
           (p2 a2)
           ...
           (pi )
           ...
           (pk ak1 ak2 ... akN )
           ...)   
Если условию не ставится в соответствие результирующее выражение, то в качестве результата предложения COND, при истинности предиката, возвращается само значение предиката.
Если же условию соответсвует несколько форм, то при его истинности формы вычисляются последовательно слева направо и результатом предложения COND будет значение последней формы последовательности.


Другие условные предложения: IF, WHEN и UNLESS

Предложение COND представляет собой наиболее общую структуру. В простом случае можно воспользоваться вполне естественной и содержащей мало скобок формой IF.
     (IF условие то-форма иначе-форма)
 <->
     (COND (условие то-форма)
             (T иначе-форма))
Можно еще использовать формы WHEN и UNLESS:
     (WHEN условие форма1 форма2 ...)
 <->
     (UNLESS (NOT условие) форма1 форма2 ...)
 <->
     (COND(условие форма1 форма2 ...))
 <->
     (IF условие (PROGN форма1 форма2 ...) NIL)


Циклические вычисления: предложение DO

В случае повторяющихся вычислений в Лиспе используются вызывающие сами себя (рекурсивные) функции и условные предложения, либо известные по процедурным языкам циклы, передачи управления и другие подобные механизмы.
Самым общим циклом или итерационным предложением в Коммон Лиспе является DO. С его помощью можно задать: Набор внутренних статических переменных с их начальными значениями, как в предложении LET Ряд форм, вычисляемых последовательно в цикле Изменения внутренних переменных после каждой итерации (например, наращивание счетчиков) Условие окончания цикла и выражение, значение которого будет значением всего предложеия.
Предложение DO имеет следующую форму:
     (DO ((var1 знач1 шаг1)(var2 знач2 шаг2) ...)
         (условие-окончания форма11 форма12 ...)
           форма21
           форма22
           ...)
Первый аргумент предложения описывает внутренние переменные var1, var2, ... , их начальные значения знач1, знач2, ... , а также формы обновления шаг1, шаг2, ... .
Вычисление предложения DO начинается с присваивания значений переменным формы таким же образом, как в случае предложения LET. Переменным, начальное значение которых не задано, присваивается по умолчанию NIL.
В каждом цикле, после присваивания значения переменным, вычисляется условие окончания. Как только значение условия не равно NIL, последовательно вычисляются формы форма11, форма12, ... и значение последней формы возвращается в качестве значения всего предложения DO.
В противном случае, последовательно вычисляются формы форма21, форма22, ... из тела предложения DO. На следующем цикле переменным vari присваиваются (одновременно) значения форм шагi, вычисляемых в текущем контексте, проверяется условие окончания и т.д.
Если переменной не задана форма, по которой она обновляется, то значение переменной не меняется.


Формы динамического прекращения вычислений:CATCH и THROW

До сих пор мы рассматривали лишь структуры, вычисление которых производилось в одном статическом контексте.
В некоторых случаях возникает необходимость прекратить вычисление функции динамически из другого вычислительного контекста, где вычисляются некоторые подвыражения, и выдать результат в более раннее состояние, не осуществляя нормальную последовательность возвратов из всех вложенных вызовов. Это нужно, например, тогда, когда какая-нибудь вложенная программа обнаружит ошибку, по которой можно решить, что дальнейшая работа бесполезна, либо может даже навредить.
Такое динамическое прерывание вычислений можно запрограммировать в Коммон Лиспе с помощью форм CATCH и THROW. Подготовка к прерыванию осуществляется специальной формой CATCH:
     (CATCH метка форма1 форма2 ...)
При вычислении формы сначала вычисляется метка, а затем формы форма1, форма2, ... слева направо. Значением формы будет последнее значение, при условии, что во время вычисления непосредственно этих форм или форм, вызванных из них, не встретится предложение THROW:
     (THROW метка значение)
Если аргумент метка вызова THROW представляет собой тот же Лисповский объект, что и метка в форме CATCH, то управление передается обратно в форму CATCH и его значение станет значение второго аргумента формы THROW.

"

Первые программы на Лиспе

<h"

Что такое рекурсия

 

 

Первые примеры рекурсивных функций

 

 

Соединение списков <h"

Что такое рекурсия

Под рекурсией в программировании понимают вызов программы самой себя либо непосредственно, либо посредством вызываемых ею подпрограмм.
Большинство современных языков программирования, в том числе Пасскаль, Си и Модула-2, позволяют использовать рекурсию.
Рекурсивное определение функции часто встречается в математике. Рассмотрим рекурсивное определение вычисления факториала (произведения первых N натуральных чисел):
           1          при N=0
      N! =
           N * (N-1)! при N0
Приведем в качестве еще одного примера рекуррентные соотношения, определяющие полинома Лежандра:
      P0(X)=1,
      P1(X)=X,
      PN+1(X) = ((2*N+1)*X*PN(X) - N*PN-1(X))/(N+1);


Первые примеры рекурсивных функций

Одним из первых примеров вычисления рекурсивных функций принято приводить вычисление факториала и чисел Фибоначчи. Их рекурсивное определение:
      F(1)=1,
      F(2)=1,
      F(N)=F(N-1) + F(N-2) , при N2.

Пример функции выполняющей вычисление факториала
;  Вычисление факториала числа n
(defun fact (n)
       (cond ((= n 1) 1)
             (t (* n (fact (- n 1))))))
Пример функции выполняющей вычисление чисел Фибоначчи:
;  Вычисление n-го числа Фибоначчи
(defun fib (n)
       (cond ((= n 1) 1)
             ((= n 2) 1)
             (t (+ (fib (- n 1))(fib (- n 2))))))
Приведенные примеры демонстрируют не только достоинство рекурсии - простоту и ясность полученнной программы, но и недостатки.
Приведенное выше определение функции, вычисляющей числа Фибоначчи крайне не эффективно. При этом способе вычисления число вызовов, растет как a*b(N-2), где a приблизительно равно 1.8, а b - 1.6, хотя действительно необходимо только n вызовов.
Ниже приведен пример программы выполняющей подсчет количества вызовов функции при вычислении числа Фибоначчи:
;  Подсчет количества вызовов функции при
;  вычислении n-го числа Фибоначчи

(defun fibs (n)
       (cond ((= n 1) 0)
             ((= n 2) 0)
             (t (+ (fibs (- n 1))(fibs (- n 2)) 2) )))
Пример функций вычисляющих длину списка
;  Длина списка верхнего уровня
(defun ength(u)
       (cond ((null u) 0)
             (t (1+ (length(cdr u))))))

;  Длина списка полная
(defun fullength(u)
       (cond ((atom u) 1)
             (t (+ (fullength(CAR u))(fullength(cdr u))))))


Соединение списков

Одной из наиболее часто встречающихся операций при работе со списками является их соединение. Определим функцию, зависящую от двух аргументов, которая по двум спискам строит новый список, содержащий последовательно все элементы первого списка и все элементы второго списка.
Сначала создается копия первого аргумента, а когда сответствующий список исчерпывается, то в качестве результата возвращается второй аргумент.
;  Соединение списков
;   Пример:
(defun append_t(u v)
       (cond ((null u) v)
             (t (cons (car u) (append_t (cdr u) v)
                )
             )
       )
)
Рассмотрим примеры работы функции append_t:

(append_t '(a b) NIL)
(a b)

(append_t '(a b) '(c d))
(a b c d)
Лиспе для отладки программ используются функции TRACE и UNTRACE. Они предназначены соответственно для включения и выключения трассировки функций и имеют следующий формат:
     (TRACE имя_функции1 имя_функции2 ...)

     (UNTRACE имя_функции1 имя_функции2 ...)
Каждый раз, когда происходит вызов трассируемой функции, на экране появляется сообщение о вызове этой функции и выводятся значения ее аргументов, а при завершении работы - сообщение об окончании вычисления и значение возвращенное трассируемой функцией.

Пример:
(trace append_t)
(APPEND_T)

(append_t '(I like ice-cream) '(and fruits))
  1 (APPEND_T (I LIKE ICE-CREAM) (AND FRUITS))
    2 (APPEND_T (LIKE ICE-CREAM) (AND FRUITS))
      3 (APPEND_T (ICE-CREAM) (AND FRUITS))
        4 (APPEND_T NIL (AND FRUITS))
        <4 (APPEND_T (AND FRUITS))
      <3 (APPEND_T (ICE-CREAM AND FRUITS))
    <2 (APPEND_T (LIKE ICE-CREAM AND FRUITS))
  <1 (APPEND_T (I LIKE ICE-CREAM AND FRUITS))
(I LIKE ICE-CREAM AND FRUITS)
В Лиспе существует встроенная функция для соединения списков APPEND.