Основы символьной обработки
Идеальный Лисп изначально поддерживает программирование в функциональном стиле. Его основа - выбор подходящей структуры данных и базового набора функций над выбранной структурой. Информационная обработка в языке Лисп отличается от стандартных подходов к программированию тремя важными особенностями:
Природа данных
Любая информация представляется в форме символьных выражений.1) Система программирования над такими структурами обычно использует для их хранения всю доступную память, поэтому программист принципиально освобожден от заботы о распределении памяти под отдельные блоки данных.
Самоописание обработки символьных выражений
Важная особенность программ на Лиспе - они строятся из рекурсивных функций, определения и вызовы которых, как и любая информация, формально могут обрабатываться как обычные данные, получаться в процессе вычислений как значения и преобразовываться как символьные выражения.
Подобие машинным языкам
Система программирования на Лиспе допускает, что программа может интерпретировать и/или компилировать программы, представленные в виде символьных выражений. Это сближает программирование на Лиспе с методами низкоуровневого программирования и отличает от традиционной методики применения языков высокого уровня.
A Nil ATOM LISP Занятие2
| A Nil ATOM LISP Занятие2 Новый_год ВотДлинныйАтомНуОченьДлинныйНоЕслиНадоАтомМожетБытьЕщеДлинннее Ф4длш139к131б |
| Пример 3.1. |
| Закрыть окно |
Структуры данных
Любые структуры данных строятся из более простых составляющих, простейшие из которых – элементарные данные. В Лиспе элементарные данные называют атомами. Для начала примем, что атом – это последовательность из букв и цифр, начинающаяся с буквы.
A Nil ATOM LISP Занятие2 Новый_год ВотДлинныйАтомНуОченьДлинныйНоЕслиНадоАтомМожетБытьЕщеДлинннее Ф4длш139к131б
Пример 3.1.
(html, txt)
Одинаково выглядящие атомы не различимы по своим свойствам. Термин "атом" выбран по аналогии с химическими атомами, строение которых – предмет другой науки. Согласно этой аналогии атом может иметь достаточно сложное строение, но атом не предназначен для разбора на части базовыми средствами языка.
Более сложные данные в Лиспе выстраиваются из одинаково устроенных бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти, выделяемому системой программирования при организации и обработке структур данных. Выделение блока памяти и размещение в нем пары данных выполняет функция CONS (от слова consolidation), а извлечение левой и правой частей из блока выполняют функции CAR и CDR соответственно ("content of address part of register" , "content of decrement part of register").
| Cons |
Атом X | ( Атом . X ) | |
| Car | ( Атом . X ) | Атом | |
| Cdr | ( Атом . X ) | X |
При работе с системой соответствующие выражения показаны ниже:
| Cons |
Атом X | (CONS 'ATOM ' X ) | |
| Car | ( Атом . X ) | (CAR '(ATOM . X ) | |
| Cdr | ( Атом . X ) | (CDR '(ATOM . X ) |
Типичная форма записи символьных выражений называется списочной записью (list-notation). Элементы списка могут быть любой природы.
Список – это перечень произвольного числа элементов, разделенных пробелами, заключенный в круглые скобки.
По соглашению атом Nil выполняет роль пустого списка. Бинарный узел, содержащий пару атомов ATOM и Nil, рассматривается как одноэлементный список (ATOM ) :
или для наглядности:
Если вместо атома "ATOM" подставлять произвольные атомы, а вместо "Nil" - произвольные списки, затем вместо атомов - построенные списки и так далее, то мы получим множество всех возможных списков. Можно уточнить, что список - это заключенная в скобки последовательность из разделенных пробелами атомов или списков.
(C )
(B C )
(C (A B))
Пример 3.2.
(html, txt)
Можно уточнить, что список - это заключенная в скобки последовательность из разделенных пробелами атомов или списков.
(C )
(B C )
(C (A B))
Пример 3.2.
Упражнения 3.1.: Нарисуйте диаграммы для списков вида:
((A B) C)
((A B) (D C))
((A B)(D(C E)))
Любой список может быть построен из пустого списка и атомов с помощью CONS и любая его часть может быть выделена с помощью подходящей композиции CAR-CDR.
CONS - Функция, которая строит списки из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается в левой части бинарного узла, а второй, являющийся списком, - в правой.
CAR – Функция, обеспечивающая доступ к первому элементу списка - его "голове".
CDR – Функция, укорачивающая список на один элемент. Обеспечивает доступ к "хвосту" списка, т.е. к остатку списка после удаления его головы.
ATOM - Функция, различающая составные и атомарные объекты. На атомах ее значение "истина", а на более сложных структурах данных – "ложь".
EQ – Функция, которая проверяет атомарные объекты на равенство.
| CONS | A и Nil | (A ) |
| CONS | (A B) и Nil | ((A B) ) |
| CONS CONS | A и (B) (Результат предыдущего CONS) и ( C ) | (A B) ((A B) C) |
| CONS | A и (B C) | (A B C) |
| CAR | (A B C) | A |
| CAR | (A (B C)) | A |
| CAR | ((A B) C) | (A B) |
| CAR | A | Не определен |
| CDR | (A ) | Nil |
| CDR | (A B C D) | (B C D) |
| CDR | (A (B C)) | ((B C)) |
| CDR | ((A B) C) | ( C ) |
| CDR | A | Не определен |
| CDR CAR | (A B C) Результат предыдущего CDR | (B C) B |
| CAR CAR | (A C) Результат предыдущего CAR | A Не определен |
| CONS CAR | A и (B) Результат предыдущего CONS | (A B) A |
| CONS CDR | A и (B) Результат предыдущего CONS | (A B) (B) |
| ATOM | VeryLongStringOfLetters | T |
| ATOM | ( A B ) | Nil - выполняет роль ложного значения |
| CDR ATOM | ( A B ) Результат предыдущего CDR | (B) Nil |
| ATOM | Nil | T |
| ATOM | ( ) | T |
| EQ | A A | T |
| EQ | A B | Nil |
| EQ | A (A B) | Nil |
| EQ | (A B) (A B) | Не определен |
| EQ | (A B) (A B) | Не определен |
| EQ | Nil и () | T |
Если требуется явно изобразить значение "истина", то используется стандартная константа – атом T (true), но роль значения "истина" может выполнить любой, отличный от пустого списка, объект.
Упражнение 3.2. Посмотрите, что сделает Лисп-система с ниже приведенными выражениями2), сравнивая результаты с данными из таблицы 3.1:
(CONS 'Head Nil ) (CONS 'Head '(Body Tail) ) (CAR '(Head Body Tail)) (CDR '(Head Body Tail)) (ATOM 'Body) (ATOM '(Body)) (ATOM ()) (ATOM (CAR '(Head Body Tail))) (EQ Nil ())
Точечная нотация
При реализации Лиспа в качестве единой универсальной базовой структуры для конструирования символьных выражений использовалась так называемая "точечная нотация" (dot-nоtation), согласно которой левая и правая части бинарного узла равноправны и могут хранить данные любой природы.
Бинарный узел, содержащий пару атомов ATOM1 и ATOM2,
можно представить как запись вида:
( ATOM1 . ATOM2 )
Если вместо атомов "ATOM1", "ATOM2" рекурсивно подставлять произвольные атомы, затем построенные из них пары и так далее, то мы получим множество всех возможных составных символьных выражений – S-выражений.
S-выражение - это или атом или заключенная в скобки пара из двух S-выражений, разделенных точкой.
Все сложные данные создаются из одинаково устроенных блоков - бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти.
Списки – это подмножество S-выражений, движение вправо по которым завершается атомом Nil.
(A . B)
(C . (A . B))
Пример 3.3.
(html, txt)
Любое S-выражение может быть построено из атомов с помощью CONS и любая его часть может быть выделена с помощью CAR-CDR.
Упражнение 3.3. Нарисуйте диаграммы для следующих S-выражений:
((A . B) . C) ((A . B) . (D . C)) ((A . B) . (D . (C . E)))
Точечная нотация может точно представлять логику хранения любых структур данных в памяти и доступа к компонентам структур данных. В виде списков можно представить лишь те S-выражения, в которых при движении вправо в конце концов обнаруживается атом Nil, символизирующий завершение списка.
Упражнение 3.4. Посмотрите, что делает Лисп-система с ниже приведенными выражениями, сравнивая результаты с данными из таблицы 3.2:
(CONS 'Head 'Tail ) (CAR '(Head . Tail)) (CDR '(Head . Tail)) (ATOM 'Atom) (ATOM ()) (ATOM (CAR '(Head . Tail))) (EQ Nil ())
Атом Nil, рассматриваемый как представление пустого списка (), выполняет роль ограничителя в списках. Одноэлементный список (A) идентичен S-выражению (A . Nil). Список (A1 A2 … Ak) может быть представлен как S-выражение вида:
(A1 . (A2 . ( … . (Ak . Nil) … ))).
В памяти это фактически одна и та же структура данных.
| (A B C ) | (A . (B . (C . Nil))) |
| ((A B) C ) | ((A . (B . Nil)) . (C . Nil)) |
| (A B (C E)) | (A . (B . ((C . (E . Nil)). Nil))) |
| (A) | (A . Nil) |
| ((A)) | ((A . Nil) . Nil |
| (A (B . C)) | (A . ((B . C) . Nil)) |
| (()) | (Nil . Nil) |
| (A B . C) | (A . (B . C)) |
| CAAR | ((A ) B C) | A |
| CADR | (A B C) | B - CDR, затем CAR |
| CADDR | (A B C) | C - (дважды CDR), затем CAR |
| CADADR | (A (B C) D) | C - два раза:(CDR, затем CAR) |
(cAAr '((A) B C) ) (cADr '(A B C)) (cADDr '(A B C) ) (cADADr '(A (B C) D))
| (Append Список … ) | Сцепляет списки, полученные как аргументы |
| (Assoc Атом А-список) | Находит в А- списке пару, левая часть которой – Атом |
| Atom | Проверка на атомарность |
| Car | Первый элемент списка или левый элемент структуры |
| Cdr | Результат удаления первого элемена из списка или правый элемент структуры |
| Cons | Создание узла из двух элементов |
| (Eq Данное1 Данное2) | Истина при идентичных данных |
| (Equal Структура1 Структура2 ) | Истина при эквивалентных структурах |
| (Delete Объект Список ) | Строит копию Списка без заданного объекта |
| (Intersection Список … ) | Пересечение списков |
| (Last Список ) | Последний элемент структуры, представляющей список. Можно задавать длину завершающего отрезка списка. |
| (Lenth Список ) | Длина списка |
| (List Форма … ) | Строит список из значений Форм |
| (Member Объект Список ) | Ищет Объект в Списке |
| (Null Форма) | Истина для Nil |
| (Pairlis Атомы Данные А-спиок) | Пополняет А-список парами из Атомов и значений, соответствующих Данных. |
| (Reverse Список ) | Копия Списка с обратным порядком элементов |
| (Set-difference Список … ) | Разность множеств, представленных Списками |
| (Sort Список Предикат ) | Упорядочивает Список согласно Предикату |
| (Sublis А-список Структура ) | Преобразует Структуру согласно А-списку методом подстановки данных вместо связанных с ними атомов. |
| (Subst Новое Старое Структура ) | Преобразует Структуру, заменяя Старое на Новое. |
| (Union Список … ) | Объединение множеств, представленных Списками. |
это перечень произвольного числа элементов,
Список – это перечень произвольного числа элементов, разделенных пробелами, заключенный в круглые скобки.Элементы списка могут быть любой природы.S-выражение - это или атом или заключенная в скобки пара из двух S-выражений, разделенных точкой. Список – частный случай S-выражения.Любое S-выражение может быть построено из атомов с помощью CONS и любая его часть может быть выделена с помощью CAR-CDR.Для изображения S-выражений используют различные нотации: графическую, точечную и списочную.Базис Лиспа содержит элементарные функции CAR, CDR, CONS, EQ, ATOM.
