N Variable1 Переменная2 LongSong ДолгаяПесня

X N Variable1 Переменная2 LongSong ДолгаяПесня

Пример 4.1.

Закрыть окно

Пример X

X
N
Variable1
Переменная2
LongSong
ДолгаяПесня

CONS CAR CDR ATOM EQ

CONS CAR CDR ATOM EQ

Пример 4.2.

Закрыть окно

Запись на алгоритмической

( Запись на алгоритмической нотации) алг ФАКТОРИАЛ ( цел N) арг N нач если (N = 0) то знач := 1 иначе знач := N * ФАКТОРИАЛ (N - 1) кон (эквивалентная Лисп-программа) (DEFUN Факториал (LAMBDA (N) (COND ((= N 0 ) 1 ) (T ( * N (Факториал (- N 1 ))) ) ) ) )

Пример 4.3. Факториал неотрицательного числа.

Закрыть окно

Запись на алгоритмической

( Запись на алгоритмической нотации)
алг ФАКТОРИАЛ ( цел N) арг N
нач
если (N = 0)
то знач := 1
иначе знач := N * ФАКТОРИАЛ (N - 1)
кон
(эквивалентная Лисп-программа)
(DEFUN Факториал (LAMBDA (N)
(COND ((= N 0 ) 1 )
(T ( * N (Факториал (- N 1 ))) )
) ) )

Пример (CAR (CONS 1 2 ) )

(CAR (CONS 1 2 ) ) (CONS (CAR (CONS 1 2 ) ) (CDR (CONS 3 4 ) ))

Пример 4.4.

Закрыть окно

Пример (CAR (CONS 1 2 ) )

(CAR (CONS 1 2 ) )
(CONS (CAR (CONS 1 2 ) ) (CDR (CONS 3 4 ) ))

Список из атомов объявлен

(QUOTE (C O N S T ))

Пример 4.5. Список из атомов объявлен константой

Закрыть окно

Пример '(C O N S T )

'(C O N S T )

Пример 4.6.

Закрыть окно

___________________________ параметр функции

(LAMBDA (x) (CAR (CDR (CDR x))) ) | |_____________________|_____определение функции | ___________________________ параметр функции

Пример 4.8.

Закрыть окно

_____определение функции

(LAMBDA (x) (CAR (CDR (CDR x))) )
| |_____________________| _____определение функции
| ___________________________ параметр функции

CAR x)

(COND ((EQ ( CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x))) (T x) )

Пример 4.9.

Закрыть окно

CAR x)

(COND ((EQ ( CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x))) (T x) )

x нач если Atom

Алг Левейший ( список x) арг x нач если Atom (x) то знач := x иначе знач := Левейший (Car (x)) кон

Пример 4.10. запись на алгоритмической нотации

Закрыть окно

список x) арг

Алг Левейший ( список x) арг x
нач
если Atom (x)
то знач := x
иначе знач := Левейший (Car (x))
кон

ATOM x) x)

(DEFUN Левейший (x) (COND (( ATOM x) x) (T (Левейший (CAR x))) ))

Пример 4.11. эквивалентная Лисп-программа

Закрыть окно

DEFUN Левейший

( DEFUN Левейший (x)
(COND ((ATOM x) x)
(T (Левейший (CAR x))) ))

алг АБС( цел x) арг

(Запись на алгоритмической нотации) алг АБС( цел x) арг x нач если (x < 0) то знач := - x иначе знач := x кон (эквивалентная Лисп-программа) (DEFUN Абс(LAMBDA (x) (COND ((< x 0 )(- x)) (T x))))

Пример 4.12. Абсолютное значение числа.

Закрыть окно

алг АБС( цел x) арг

(Запись на алгоритмической нотации)
алг АБС( цел x) арг x
нач
если (x < 0)
то знач := - x
иначе знач := x
кон
(эквивалентная Лисп-программа)
(DEFUN Абс(LAMBDA (x)
(COND ((< x 0 )(- x))
(T x))))

Алгоритм Евклида для нахождения наибольшего

(эквивалентная Лисп-программа) (DEFUN НОД (LAMBDA (x y) (COND ((< x y) (НОД y x)) ((= (остаток y x ) 0 ) x ) (T (НОД (остаток y x) x )) )) )

Пример 4.14. Алгоритм Евклида для нахождения наибольшего общего делителя двух положительных целых чисел при условии, что определена функция "Остаток".

Закрыть окно

DEFUN НОД

(эквивалентная Лисп-программа)
( DEFUN НОД (LAMBDA (x y)
(COND ((< x y) (НОД y x))
((= (остаток y x ) 0 ) x )
(T (НОД (остаток y x) x ))
))
)

Рекурсивные функции: определение и исполнение

Определения могут быть рекурсивны.

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

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

Алг Левейший ( список x) арг x нач если Atom (x) то знач := x иначе знач := Левейший (Car (x)) кон

Пример 4.10. запись на алгоритмической нотации (html, txt)

Новая функция "Левейший" выбирает первый атом из любого данного.

(DEFUN Левейший (x) (COND ((ATOM x) x) (T (Левейший (CAR x))) ))

Пример 4.11. эквивалентная Лисп-программа (html, txt)

Если x является атомом, то он и является результатом, иначе функцию "Левейший" следует применить к первому элементу значения x, которое получается в результате вычисления формулы (CAR x). На составных x будет выполняться вторая ветвь специальной функции COND, выбираемая по тождественно истинному значению встроенной константы T.

Определение функции "Левейший" рекурсивно. Эта функция действительно работает в терминах самой себя. Важно, что для любого S-выражения существует некоторое число применений функции CAR, после которого из этого S-выражения обязательно выделится какой-нибудь атом, следовательно процесс вычисления функции всегда определен, детерминирован, завершится за конечное число шагов. Можно сказать, что для определенности рекурсивной функции следует формулировать условие ее завершения.

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

Рассмотрим вычисление формы:

(APPLY (DEFUN Левейший (x) (COND ((ATOM x) x) (T (Левейший (CAR x))) ))) (QUOTE ((A . B) . C) ) )

Функция "APPLY" применяет функцию "Левейший", полученную как результат "DEFUN", к ее аргументам – константе "((A . B) . C)".

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

(Запись на алгоритмической нотации)

алг АБС( цел x) арг x нач если (x < 0) то знач := - x иначе знач := x кон

(эквивалентная Лисп-программа)

(DEFUN Абс(LAMBDA (x) (COND ((< x 0 )(- x)) (T x))))

Пример 4.12. Абсолютное значение числа. (html, txt)

(Запись на алгоритмической нотации)

алг ФАКТОРИАЛ ( цел N) арг N нач если (N = 0) то знач := 1 иначе знач := N * ФАКТОРИАЛ (N - 1) кон

(эквивалентная Лисп-программа)

(DEFUN Факториал (LAMBDA (N) (COND ((= N 0 ) 1 ) (T ( * N (Факториал (- N 1 ))) ) ) ) )

Пример 4.3. Факториал неотрицательного числа. (html, txt)

Это определение не завершается на отрицательных аргументах.

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

(Запись на алгоритмической нотации)

алг НОД ( цел x, y) арг x, y нач если (x < y) то знач := НОД ( y, x) инес Остаток (y, x) = 0 то знач := x иначе знач := НОД (Остаток (y, x), x) кон

остаток [x, y] - функция, вычисляющая остаток отделения x на y.

(эквивалентная Лисп-программа)

(DEFUN НОД (LAMBDA (x y) (COND ((< x y) (НОД y x)) ((= (остаток y x ) 0 ) x ) (T (НОД (остаток y x) x )) )) )

Пример 4.14. Алгоритм Евклида для нахождения наибольшего общего делителя двух положительных целых чисел при условии, что определена функция "Остаток". (html, txt)

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

Базис элементарного Лиспа образуют пять функций над S-выражениями CAR, CDR, CONS, ATOM, EQ и четыре специальных функции, обеспечивающие управление программами и процессами и конструирование функциональных объектов QUOTE, COND, LAMBDA, DEFUN.

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



Формально для перехода к практике нужна несколько большая определенность по механизмам исполнения программ, представленных S-выражениями:

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

Таблица 4.2. Clisp: Функции, строящие функциональные объекты.

(Declare Спецификации )	Специфицирует переменные – dynamic-extent, ftype, ignorable, ignore, inline, optimize, special, type
(Defmacro Название Параметры Определение )	Глобальное опреление макроса
(Defun Название Параметры Форма )	Определение функции
(Function Название )	#’ – выдает названную функцию
( Lambda Параметры Определение )	Конструирует бузымянную функцию

B) . C))".

x = ((A . B) . C))

Имя "Левейший" теперь работает как известное название функции, которое может быть вызвано в форме:

( Левейший ' ((A . B) . C) ) Таблица 4.1. Схема вывода результата формы с рекурсивной функцией.Вычисляемая формаОчередной шагРезультат и комментарииВход в рекурсиюПервый шаг рекурсииВторой шаг рекурсииТретий шаг рекурсииВыход из рекурсии

(Левейший (QUOTE ((A . B) . C)))	Выбор определения функции и	(COND ((ATOM x) x)(T (Левейший (CAR x))) )
	Выделение параметров функции	(QUOTE ((A . B) . C))
(QUOTE ((A . B) . C))	Вычисление аргумента функции	X = ((A . B) . C)
(COND ((ATOM x) x)(T (Левейший (CAR x))) )	Перебор предикатов: выбор первого	(ATOM x)
(ATOM x)	Вычисление первого предиката	Nil = "ложь",т.к. X – не атом. Переход ко второму предикату
T	Вычисление второго предиката	T = "истина" – константа. Переход к выделенной ветви
(Левейший (CAR x))	выделение параметров функции	(CAR x)
(CAR x)	Вычисление аргумента функции	X = (A . B) Рекурсивный переход к редуцированному аргументу
(COND ((ATOM x) x)(T (Левейший (CAR x))) )	Перебор предикатов: выбор первого	(ATOM x)
(ATOM x)	Вычисление первого предиката	Nil = "ложь", т.к. X – не атом. Переход ко второму предикату
T	Вычисление второго предиката	T = "истина" – константа. Переход ко второй ветви
(Левейший (CAR x))	выделение параметров функции	(CAR x)
(CAR x)	Вычисление аргумента функции	X = A Рекурсивный переход к редуцированному аргументу
(COND ((ATOM x) x) (T (Левейший (CAR x))) )	Перебор предикатов: выбор первого	(ATOM x)
(ATOM x)	Вычисление первого предиката	T – т.к. X теперь атом Преход к первой ветви
X	Вычисление значений переменной	A Значение функции получено и вычисление завершено

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


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

(Запись на алгоритмической нотации)

алг АБС( цел x) арг x нач если (x < 0) то знач := - x иначе знач := x кон

(эквивалентная Лисп-программа)

(DEFUN Абс(LAMBDA (x) (COND ((< x 0 )(- x)) (T x))))

Пример 4.12. Абсолютное значение числа.

(Запись на алгоритмической нотации)

алг ФАКТОРИАЛ ( цел N) арг N нач если (N = 0) то знач := 1 иначе знач := N * ФАКТОРИАЛ (N - 1) кон

(эквивалентная Лисп-программа)

(DEFUN Факториал (LAMBDA (N) (COND ((= N 0 ) 1 ) (T ( * N (Факториал (- N 1 ))) ) ) ) )

Пример 4.3. Факториал неотрицательного числа.

Это определение не завершается на отрицательных аргументах.

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

(Запись на алгоритмической нотации)

алг НОД ( цел x, y) арг x, y нач если (x < y) то знач := НОД ( y, x) инес Остаток (y, x) = 0 то знач := x иначе знач := НОД (Остаток (y, x), x) кон

остаток [x, y] - функция, вычисляющая остаток отделения x на y.

(эквивалентная Лисп-программа)

(DEFUN НОД (LAMBDA (x y) (COND ((< x y) (НОД y x)) ((= (остаток y x ) 0 ) x ) (T (НОД (остаток y x) x )) )) )

Пример 4.14. Алгоритм Евклида для нахождения наибольшего общего делителя двух положительных целых чисел при условии, что определена функция "Остаток".

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

Базис элементарного Лиспа образуют пять функций над S-выражениями CAR, CDR, CONS, ATOM, EQ и четыре специальных функции, обеспечивающие управление программами и процессами и конструирование функциональных объектов QUOTE, COND, LAMBDA, DEFUN.

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



Формально для перехода к практике нужна несколько большая определенность по механизмам исполнения программ, представленных S-выражениями:

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

(Declare Спецификации )	Специфицирует переменные – dynamic-extent, ftype, ignorable, ignore, inline, optimize, special, type
(Defmacro Название Параметры Определение )	Глобальное опреление макроса
(Defun Название Параметры Форма )	Определение функции
(Function Название )	#’ – выдает названную функцию
( Lambda Параметры Определение )	Конструирует бузымянную функцию

Специальные функции

Константа представляется как аргумент специальной функции QUOTE в виде списка:

(QUOTE (C O N S T ))

Пример 4.5. Список из атомов объявлен константой (html, txt)

Используется и сокращенная запись – апостроф перед произвольным данным.

'(C O N S T )

Пример 4.6.

(html, txt)

В зависимости от контекста одни и те же объекты могут выполнять роль переменных или констант, причем значения и того, и другого могут быть произвольной сложности. Если объект выполняет роль константы, то для объявления константы достаточно заблокировать его вычисление, то есть как бы взять его в кавычки (quotation), выделяющие буквальное использование фраз, не требующее обработки. Для такой блокировки вводится специальная унарная функция QUOTE, предохраняющая свой аргумент от вычисления.

(QUOTE A)	Константа A объявлена.
(QUOTE (A B C) )	Константа (A B C) объявлена.
(ATOM (QUOTE A)) = T	Аргументом предиката "ATOM" является константа – атом "А"
(ATOM (QUOTE (A B C) )) = Nil	Аргументом предиката является константа - список (A B C)
(ATOM A)	Аргументом предиката "ATOM" является переменная – атом "А". Значение предиката не определено - оно зависит от вхождения переменной A, а ее значение зависит от контекста и должно быть определено или задано до попытки выяснить атом ли это.
(третий (QUOTE (A B C)))	Применение новой функции к значению, не требующему вычисления, - константа (A B C).

Пример 4.7.

(html, txt)

Упражнение. Запишите выражения, соответствующие применению функций из вышеприведенных определений.

Построить функцию можно с помощью Lambda-конструктора:

(LAMBDA (x) (CAR (CDR (CDR x))) ) | |_____________________|_____определение функции | ___________________________ параметр функции

Пример 4.8.

(html, txt)

При вызове такой безымянной функции заодно происходит задание значений параметров - связанных переменных:

((LAMBDA (x) (atom x)) 123) ; = T

X получит значение 123 на время применения построенной безымянной функции, действие которой заключается в выяснении, атом ли аргумент функции.

Связанную переменную можно объявить специальной функцией Lambda, а значение она получит при вызове функции.

Соответствие между названием функции и ее определением можно задать с помощью специального конструктора функций DEFUN, первый аргумент которого - имя функции, второй – собственно именуемое определение функции. Формальным результатом DEFUN является ее первый аргумент, который становится объектом другой категории. Он меняет свой статус – теперь это имя новой функции.

(DEFUN третий (x) (CAR (CDR (CDR x))) )) | | |__________________|_______ определение функции | |_____________________________ параметры функции |___________________________________ имя новой функции

Новая функция "третий" действует так же как "Caddr" в таблице 3.4.

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

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

Представления функции могут вычисляться и передаваться как параметры или результаты других функций.

Соответствие между именем функции и ее определением может быть изменено, подобно тому, как меняется соответствие между именем переменной и ее значением.

Ветвление (условное выражение) характеризуется тем, что ход процесса зависит от некоторых условий. Условия следует сгруппировать в общий комплект и соотнести с подходящими формами. Такую организацию процесса вычисления обеспечивает специальная функция COND (condition). Ее аргументами являются ветви, представленные как двухэлементные списки, содержащие предикаты и соответствующие им выражения.


Количество ветвей не ограничено. Обрабатываются они по особой схеме: сначала вычисляются первые элементы аргументов по порядку, пока не найдется предикат со значением "истина". Затем выбирается второй элемент этого аргумента и вычисляется его значение, которое и считается значением всего условного выражения.

(COND (p1 e1) (p2 e2) ... (pk ek) ) |______|________|__________ предикаты для выбора ветви |______|____ ___|__________ ветви условного выражения

Каждый предикат pi или ветвь ei может быть любой формы: переменная, константа, вызов функции, композиция функций, условное выражение.

Обычное условное выражение (if Predicate Then Else) или (если Predicate то Then иначе Else) может быть представлено с помощью функции COND следующим образом:

(COND (Predicate Then)(T Else))

Или более наглядно:

(COND (Predicate Then ) (T Else ) )

Вычисление ряда форм в определении может быть обусловлено заранее заданными предикатами.

(COND ((EQ (CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x))) (T x) )

Пример 4.9.

(html, txt)

Атом "T" представляет тождественную истину. Значение всего условного выражения получается заменой первого элемента из значения переменной x на B в том случае, если (CAR x) совпадает с A.

Объявленные здесь специальные функции QUOTE, COND, LAMBDA и DEFUN существенно отличаются от элементарных функций CAR, CDR, CONS, ATOM, EQ правилом обработки аргументов. Обычные функции получают значения аргументов, предварительно вычисленные системой программирования по формулам фактических параметров функции.

Специальные функции не требуют такой предварительной обработки параметров.

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

Основные понятия, возникающие при написании

Основные понятия, возникающие при написании программ – это переменные, константы, выражения, ветвления, вызовов функций и определения. Все они представимы с помощью S-выражений.Связанную переменную можно объявить специальной функцией Lambda, а значение она получит при вызове функции.Представления функции могут вычисляться и передаваться как параметры или результаты других функций.Специальные функции не требуют предварительной обработки параметров. Базис элементарного Лиспа образуют пять функций над S-выражениями CAR, CDR, CONS, ATOM, EQ и четыре специальных функции, обеспечивающие управление программами и процессами и конструирование функциональных объектов QUOTE, COND, LAMBDA.

---

---