1. Функциональное программирование. Основы Лиспа
| Вид материала | Документы |
Содержание2. Списки в Лиспе Списки. Функции для работы со списками CAR обеспечивает доступ к первому элементу списка — его "голове". EQ выполняет проверку атомарных Многократные CAR-CDR |
- Рабочая программа по курсу "Функциональное программирование" Специальность, 144.38kb.
- Федеральное агентство по образованию, 124.95kb.
- В. А. Давыденко программирование и основы алгоритмизации лабораторный практикум, 1951.1kb.
- Петербургский Гуманитарный Университет Профсоюзов (СПбгуп), с-петербург учебный курс, 20.72kb.
- Программа дисциплины Математическое программирование Семестры, 10.84kb.
- Методические указания и задания к курсовому проекту по дисциплине «Функциональное, 73.42kb.
- Программа дисциплины Функциональное программирование и интеллектуальные системы для, 148.26kb.
- Методические рекомендации для студентов по изучению курса «Функциональное программирование», 49.76kb.
- Рабочая программа по дисциплине "Функциональное и логическое программирование, 152.21kb.
- Программа элективного курса «Алгоритмизация и программирование», 95.38kb.
2. Списки в Лиспе
Списки. Функции для работы со списками
Список – это основной тип данных в Lisp.
Списки - после довательности S-выражений, построенные из атомов, заключенных в скобки и разделенных пробелами, например:
((имя Джон Смит) (воз раст 99) (женат #Т) (дети (Том Мэри)))
Особым S-выражением является пустой список (), который считается атомом. Для обозначения пустого списка используется также специальная константа nil.
Примеры списков:
;пятиэлементный список
(1 2 3 4 5)
;четырехэлементный список
(1 2 ((3) 4) 5)
;одноэлементный список
((1 2 3 4 5))
Первый элемент списка называется головой списка, все прочие элементы, кроме первого, представленные как список, называются хвостом списка.
Примеры разделения списка на голову и хвост:
| Список | Голова | Хвост |
| (1 2 3 4 5) | 1 | (2 3 4 5) |
| (1 2 ((3) 4) 5) | 1 | (2 ((3) 4) 5) |
| ((1 2 3 4 5)) | (1 2 3 4 5) | () |
| (1) | 1 | () |
Списки легко реализовать с помощью структуры из двух указателей (для примера выше):
Для обработки S-выражений достаточно пяти функций:
Функция ^ CAR обеспечивает доступ к первому элементу списка — его "голове".
| `X | (CAR X) |
| (A B C) | A |
| (A) | A |
| ((A B)(C D)) | (A B) |
Функция CDR — возвращает укороченный на один элемент список (отбрасывая его первый элемент, «голову») — его «хвост», т.е. что, что остается после удаления головы.
| `X | (CDR X) |
| (A B C) | (B C) |
| (A) | () |
| ((A B)(C D)) | ((C D)) |
Функция CONS соединяет два S-выражения в единое S-выражение, так что первым элементом результата является первый аргумент функции, а хвостом -второй аргумент. Она строит списки из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается в левой части бинарного узла, а второй, являющийся списком, — в правой.
(*) Чтобы отличать константные S-выражения от вычисляемых выражений, перед константой будем ста вить апостроф (например, `х - символьная константа, а х – переменная). При сцеплении двух атомов cons(`A,`B) получается S-выражение, ко торое не является списком. Будем его записывать как точечную пару (А . B). Результат cons(`А,0) можно также записать либо как список (А) либо как точечную пару (А . ()). S-выражение (А . (B . (С . D))) можно записывать в более простой форме (A B C. D).
| `X | `Y | (CONS X Y) |
| A | (B C) | (A B C) |
| A | () | (A) |
| (A B) | ((C D)) | ((A B) (C D)) |
| (A B) | (C D) | ((A B) C D) |
| A | B | (A . B) |
Функция ATOM позволяет различать составные и атомарные объекты: на атомах ее значение "истина", а на структурированных объектах — "ложь".
| `X | (ATOM X) |
| A | T |
| (A) | NIL |
| () | T |
| 123 | T |
| NIL | T |
Функция ^ EQ выполняет проверку атомарных объектов на равенство. Если оба аргу мента функция являются списками, то результат не определен, так как анализируется только значение указателя.
| `X | `Y | (EQ X Y) |
| A | A | T |
| (A) | (A) | NIL |
| A | (A) | NIL |
Для многошагового доступа к отдельным элементам списка удобно пользоваться мнемоничными обозначениями композиций из многократных CAR-CDR. Имена таких композиций устроены как цепочки из "a" или "d", задающие маршрут движения из шагов CAR и CDR, соответственно, расположенный между "c" и "r". Указанные таким способом CAR-CDR исполняются с ближайшего к аргументу шага, т.е. в порядке, обратном записи.
Примеры многошагового доступа к элементам структуры
| | ^ Многократные 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) |
(*) Имена функций car и car происходят от имен регистров компьютера, на котором был реализован первый компилятор языка LISP. Эти имена сохранились, так как по зволяют использовать вместо car{cdr(cdr(x))) сокращенную запись caddr(x) (третий элемент списка х), см. примеры далее.
Любой список может быть построен из пустого списка и атомов с помощью CONS, и любая его часть может быть выделена с помощью подходящей композиции CAR-CDR.
Различие истинностных значений в Лиспе принято отождествлять с разницей между пустым списком и остальными объектами, которым программист может придать в программе некоторый другой смысл. Таким образом, значение "ложь" — это всегда Nil. (Во многих языках программирования используется 0 – 1 или идентификаторы True — False и др.)
Если требуется явно изобразить истинностное значение, то для определенности в качестве значения "истина" используется константа — атом T (true) как стандартное представление, но роль такого значения может выполнить любой, отличный от пустого списка, объект.