Введение в программирование на Лиспе

         

Основы символьной обработки


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

Природа данных

Любая информация представляется в форме символьных выражений.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 – Функция, которая проверяет атомарные объекты на равенство.

Таблица 3.1. Элементарные функции над списками. Примеры соответствия между аргументами и результатами элементарных функций обработки списков.ФункцияАргументыРезультатКонструирование структур данныхДоступ к компонентам структуры данных:СлеваСправаОбработка данных:Предикаты:Атомарность – неделимостьРавенство
CONSA и Nil(A )
CONS(A B) и Nil((A B) )
CONS

CONS
A и (B)

(Результат предыдущего CONS) и ( C )
(A B)

((A B) C)
CONSA и (B C)(A B C)
CAR(A B C)A
CAR(A (B C))A
CAR((A B) C)(A B)
CARAНе определен
CDR(A )Nil
CDR(A B C D)(B C D)
CDR(A (B C))((B C))
CDR((A B) C)( C )
CDRAНе определен
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)
ATOMVeryLongStringOfLettersT
ATOM( A B )Nil - выполняет роль ложного значения
CDR

ATOM
( A B )

Результат предыдущего CDR
(B)

Nil
ATOMNilT
ATOM( )T
EQA AT
EQA BNil
EQA (A B)Nil
EQ(A B) (A B)Не определен
EQ(A B) (A B)Не определен
EQNil и ()T
Различие истинностных значений в Лиспе принято отождествлять с разницей между пустым списком и остальными объектами, которым программист может придать в программе некоторый другой смысл. Таким образом, значение "ложь" – это всегда Nil.

Если требуется явно изобразить значение "истина", то используется стандартная константа – атом 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) … ))).

В памяти это фактически одна и та же структура данных.

Таблица 3.3. Соответствие списков и равнозначных им S-выраженийList-notation - списочная запись объектаDot-notation - точечная запись того же объекта
(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))
Для многошагового доступа к отдельным элементам такой структуры удобно пользоваться мнемоническими обозначениями композиций из многократных CAR-CDR. Имена таких композиций устроены как цепочки из "a" или "d", задающие маршрут движения из шагов CAR и CDR соответственно, расположенный между "c" и "r". Указанные таким способом CAR-CDR исполняются с ближайшего к аргументу шага, т.е. в порядке, обратном записи.

Таблица 3.4. Примеры многошагового доступа к элементам структуры.Композиции CAR-CDRВычисляются в порядке, обратном записи:
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)
Упражнение 3.5. Посмотрите, что делает Лисп-система с ниже приведенными выражениями, сравнивая результаты с данными из таблицы 3.3:



(cAAr '((A) B C) ) (cADr '(A B C)) (cADDr '(A B C) ) (cADADr '(A (B C) D)) Таблица 3.5. Clisp: Функции для работы с данными
(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.