- •Введение
- •Понятие функционального программирования
- •Языки функционального программирования
- •Лямбда-исчисление Введение в лямбда-исчисление
- •Алонсо Черч
- •Иллюстрация ромбического свойства на примере
- •Прикладные лямбда-исчисления
- •Данные и выражения языка Lisp. Понятия списков и атомов, вычисление функций.
- •Организация памяти Lisp-машины
- •Функции проверки типов и логические функции
- •Манипуляция элементами списков
- •Основные конструкции Лямбда - выражения и пользовательские функции
- •Последовательности вычислений
- •Условные операторы и циклы
- •Рекурсия
- •Проверка на вхождения атома в список
- •Удаление из списка n-ного элемента
- •Добавление в список элемента в позицию n
- •Функционалы
- •Макросы
- •Ввод и вывод
- •Типы данных Иерархия типов
- •Символы
- •Последовательности
- •Массивы
- •Структуры
- •Лабораторные работы Лабораторная работа 1
- •Лабораторная работа 2
- •Лабораторная работа 3
- •Дана схема метрополитена, найти кратчайший путь между станциями.
- •Игра в 15.
- •Задача о 8-ми ферзях.
- •Задача о 8-ми ферзях 2.
- •Задача о Ханойской башне.
- •Задача о составлении расписания
- •Раскрасить плоскую карту четырьмя цветами, так что бы любые две смежные области не были окрашены в один цвет
- •Задача о коммивояжере.
- •Лабораторная работа 4
Символы
Символ является достаточно необычной структурой данных. Во-первых, с символом может быть связано некоторое значение, с помощью использования функций SET, SETQ и SETF. Кроме того, символ может указывать на лямбда-выражение. И, наконец, символ может иметь свойства. Таким образом, символ является структурированным объектом, состоящим из нескольких элементов - имени, значения, лямбда-выражения и списка свойств, а также данные о пространстве имён, которому принадлежит этот символ.
Некоторые функции, такие как BOUNDP, FBOUNDP и SYMBOL-FUNCTION мы уже рассматривали, когда говорили о переменных и функциях. Здесь мы рассмотрим ещё несколько функций, связанных с получением значений символов.
symbol-name |
(symbol-name симвыол) Возвращает имя символа в виде строки. |
>(setq x 5) 5 >(symbol-name 'x) "X" |
Любопытной особенностью символов является возможность их связывания со специальными ячейками памяти, называемыми свойствами. Свойство символа характеризуется его именем и значением. У подобного механизма есть нечто общее с понятиями структур и записей таких языков, как С и Pascal, однако символ может иметь динамический набор свойств. Кроме того, свойства символа не связаны с его значением, независимо от изменения значения символа его свойства не меняются.
get |
(get символ свойство) Возвращает ссылку на свойство символа, если такого свойства не существует, оно не создаётся, возвращается NIL. По умолчанию ссылка может использоваться для чтения его значения, однако в случае применения функции SETF становится возможно создание свойства и запись в него нового значения. |
В следующем примере мы создаём у символа y свойство property, И записываем в него значение 5. Отметим, что способ, которым это было выполнено, специфичен для Common Lisp, в других диалектах для этого используется специальная функция PUTPROP:
>(get 'y 'property) NIL >(setf (get 'y 'property) 5) 5 >(get 'y 'property) 5 |
У символа может быть несколько свойств, различающихся именами. Тем самым, с помощью символов можно организовывать достаточно сложные структуры данных.
symbol-plist |
(symbol-plist символ) Возвращает список всех свойств и их значений для некоторого символа. |
remprop |
(remprop символ имя_свойства) Удаляет присвоенное ранее символу свойство. Функция возвращает Т, если такое свойство есть, и NIL, если такого свойства нет. |
>(setf (get 'sym 'size) 'big) BIG >(setf (get 'sym 'color) 'red) RED >(symbol-plist 'sym) (SIZE BIG COLOR RED) >(remprop 'sym 'color) T >(symbol-plist 'sym) (SIZE BIG) |
Списки
Наряду с атомом, список является основной структурой данных Lisp. Как уже упоминалось, любой список состоит из ячеек, включающих в себя голову и хвост. Абстрактной списковой ячейкой является точечная пара, у которой хвост может представлять собой не только список, но и атом. Важно понимать, что точечная пара является обобщением всех списковых ячеек, и её голова и хвост сами могут быть точечными парами.
Список может быть определён рекуррентно следующим образом:
NIL или () является списком.
Структура, состоящая из точечных пар, в каждой из которых хвост является списком, сама является списком.
Таким образом, результат объединения (CONS A (B)) является списком, а (CONS A B) нет, так как B это атом, а не список. Тем не менее, обе функции в результате дадут нам точечную пару.
Списки в Lisp имеют базовый тип LIST. Два основных его подтипа это пустой список NIL и непустой список CONS. Элементом списка может быть объект произвольного типа.
Многие операции со списками были уже рассмотрены ранее, поэтому здесь мы остановимся только на некоторых, ранее не упоминавшихся:
rplaca rplacd |
(rplaca список значение) (rplacd список значение) Функции изменяет значение соответственно головы и хвоста списка, указанного первым аргументом, на значение второго аргумента. |
>(setq x '(a b (c))) (A B (C)) >(rplaca x '(m n)) ((M N) B (C)) >x ((M N) B (C)) >(rplacd x 'nil) ((M n)) |
append |
(append список1 список2) Функция объединяет свои аргументы-списки в один список. В отличие от LIST, аргументы APPEND считаются списками элементов, а не элементами списка. |
>(APPEND '( a (b) c) '(d (e) f)) (A (B) C D (E) F) >(LIST '( a (b) c) '(d (e) f)) ((A (B) C) (D (E) F)) |
nconc |
(nconc список1 список2) Функция объединяет свои аргументы-списки в один список. В отличие от APPEND, функция разрушает структуру исходных данных - список, заданный первым аргументом, принимает значение результата NCONC. |
>(APPEND '( a (b) c) '(d (e) f)) (A (B) C D (E) F) >(nconc '( a (b) c) '(d (e) f)) (A (B) C D (E) F) >(setq arg1 '(a (b) c)) (A (B) C) >(setq arg2 '(d (e) f)) (D (E) F) >(nconc arg1 arg2) (A (B) C D (E) F) >arg1 (A (B) C D (E) F) |
Структуроразрушающие функции надо использовать с большой осторожностью, так как их вызов может неожиданным образом влиять на другие функции. Например, следующий вызов приводит к результатам, на первый взгляд достаточно странным :
>(setq x '(a)) (A) >(nconc x x) (A A A A A A A A A A ...) |
Таким образом, объединяя, казалось бы, два элементарных списка, мы получили список бесконечной длины5.
remove |
(remove образец список) Функция удаляет из списка все элементы, соответствующие её первому аргументу. Рассматриваются элементы, находящиеся на самом верхнем уровне списка - аргумента, т.е. если мы ищем атом A, в списке (A B C) он будет найден, а в списке ((A) B C) - нет. |
>(remove 'b '( a b c b a)) (A C A) >(remove 'b '( a (b c b) a)) (A (B C B) A) |
Функция REMOVE определяется с помощью различных методов сравнения элементов списка, по умолчанию это EQL. Если необходимо работать, например, со списками, функцию сравнения можно задать непосредственно:
>(REMOVE '(A B) '((A B) (C D))) ((A B) (C D)) >(remove '(a b) '((a b) (c d)) :test 'equal) ((C D)) |
substitute |
(substitute образец новое_значение список) Функция заменяет в списке все элементы, соответствующие образцу, на новое значение. Рассматриваются элементы, находящиеся на самом верхнем уровне списка - аргумента, т.е. если мы ищем атом A, в списке (A B C) он будет найден, а в списке ((A) B C) - нет. Функция работает аналогично REMOVE. |
>(substitute 'B 'A '(A C (A))) (B C (A)) >(substitute 'B 'A '(A C (A)) :test 'equal) (B C (A)) >(substitute 'B '(A) '(A C (A)) :test 'equal) (A C B) |
reverse |
(reverse список) Функция переворачивает список, т.е. формирует результат как список элементов исходного списка, следующих в обратном порядке. Также как APPEND, REMOVE и SUBSTITUTE рассматривает только первый уровень вложенности. |
>(reverse '(A (B C) D)) (D (B C) A) |
length |
(length список) Функция возвращает длину списка в элементах первого уровня. |
>(length '(A B C)) 3 >(length '(A (B C))) 2 |
Строки
Строковый тип данных STRING является одним из основных при отображении данных. Строка в Lisp состоит из последовательности знаков, имеющих, в свою очередь, тип CHARACTER. В общем случае знак отображается в Lisp так:
#\x
где x указывает на отображаемое данной записью слово или символ. В большинстве случаев этот символ повторяет x, однако бывают и исключения, например, #\Tab выводит символ табуляции а #\Return переводит строку. Знак является своего рода константой и его значением является он сам. Таким образом, строка является дочерним типом для последовательности.
Строка представляет собой последовательность символов, ограниченную с обеих сторон двойными кавычками, например, "String".
Stringp |
(sptingp объект) Функция проверяет, является ли объект строкой. Если да, возвращает T, если нет, NIL. |
>(STRINGP 1) NIL >(STRINGP "1") T |
char |
(char строка символ) Функция возвращает определённый символ из строки. Индексация начинается с нуля. |
Функция char может использоваться в качестве параметра SETF.
>(setq str "abcd") "abcd" >(setf (char str 0) #\e) #\e >str "ebcd" |
