Введение в программирование на Лиспе
Введение в программирование на Лиспе
Диалог с Лисп-системой
Рассмотрим особенности функционирования Лисп-интерпретатора на примере системы GNU Clisp.> clisp
Работа системы начинается с заставки вида:
> clisp
i i i i i i i ooooo o ooooooo ooooo ooooo I I I I I I I 8 8 8 8 8 o 8 8 I \ `+' / I 8 8 8 8 8 8 \ `-+-' / 8 8 8 ooooo 8oooo `-__|__-' 8 8 8 8 8 | 8 o 8 8 o 8 8 ------+------ ooooo 8oooooo ooo8ooo ooooo 8 Copyright (c) Bruno Haible, Michael Stoll 1992, 1993 Copyright (c) Bruno Haible, Marcus Daniels 1994-1997 Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998 Copyright (c) Bruno Haible, Sam Steingold 1999-2002
[1]>
Символ ">" - приглашение к вводу выражений для интерпретации. Выход из Лисп-системы осуществляется как вызов функции "BYE"
[1]> (BYE)1)
Происходит возврат к операционной системе.
[1]> (BYE) Bye.
Основной рабочий цикл начинается с ввода данных, представляющих так называемое символьное выражение.
[1]> (CONS 1 2)
Интерпретатор вычисляет это выражение, затем печатается полученный результат и появляется очередное приглашение:
[1]> (CONS 1 2) (1 . 2) [2]>
При недостатке правых скобок ничего не происходит:
[1]> (CONS 1 2
Система ждет, пока не получит недостающие скобки, прежде чем предложить прочитанную форму интерпретатору:
[1]> (CONS 1 2 ) (1 . 2) [2]>
Баланс скобок проще всего поддерживать, набирая пары "()" и вставляя потом между ними нужный текст. При наборе закрывающей скобки система на полсекунды перемещает курсор на соответствующую левую скобку, что также помогает замечать нарушения в балансе скобок.
При невозможности интерпретировать полученное данное как символьное выражение система печатает диагностическое сообщение:
[2]> (CONS A B) *** - EVAL: variable A has no value2) 1. Break [3]>
В этом примере перед атомами "A" и "B" следует поставить апострофы, показывающие системе, что здесь эти атомы не рассматриваются как переменные. Система перешла в режим обработки прерывания, выйти из которого можно с помощью Ctrl-D (одновременное нажатие).
[5]> (cons a 'b)
*** - EVAL: variable A has no value 1. Break [6]>3) [7]> (cons 'a 'b) (A . B) [8]>
Оперативную коррекцию можно делать без повторного набора текста строковым редактором. Стрелка вверх, предназначенная для перемещения курсора, здесь используется для перехода к ранее набранной строке.
[1]> (CONS 1 2) (1 . 2) [2]>4) (CONS 1 2)
Теперь эту строку можно подкорректировать:
[1]> (CONS 1 2) (1 . 2) [2]> (CONS 4 5)5) (4 . 5)
Можно пользоваться любым регистром при наборе имен, включая русский регистр.6) При выводе происходит сведение к заглавным буквам.
[1]> (cons 'ГОЛОВА 'хвост) (ГОЛОВА . ХВОСТ) [2]>
Пошаговое вычисление
В системе имеется функция "STEP", обеспечивающая пошаговую интерпретацию сложных выражений.Унарная функция "STEP" выполняет пошаговую интерпретацию своего аргумента. Ее работа начинается с приглашения выбрать действие по управлению интерпретацией (см. таблицу):
[2]> (step (cons (car '(a . b)) 'd )) step 1 --> (CONS (CAR '(A . B)) 'D ) Step 1 [3]>
| Help | :h (or ?) | this command list |
| Полный список команд | ||
| Error | :e | Print the recent Error Message |
| Вывод последнего сообщения об ошибке | ||
| Continue | :c | continue evaluation |
| Продолжение вычислений | ||
| Step | :s | step into form: evaluate this form in single step mode |
| Продвижение к внутреннему подвыражению | ||
| Next | :n | step over form: evaluate this form at once |
| Вычисление данной формы сразу, полностью | ||
По действию "step" выбирается вычисление первого аргумента функции "CONS":
Step 1 [2]> (step (cons (car '(a . b)) 'd )) Step 1 --> (CONS (CAR '(A . B)) 'D ) Step 1 [3]> step Step 2 --> (CAR '(A . B)) Step 2 [4]>
Это же действие "step" теперь можно выбирать с помощью стрелки вверх:
Step 1 [2]> (step (cons (car '(a . b)) 'd)) Step 1 --> (CONS (CAR '(A . B)) 'D) Step 1 [3]> step Step 2 --> (CAR '(A . B)) Step 2 [4]> step1) Step 3 --> '(A . B) Step 3 [5]>
Теперь шаг за шагом смотрим как интерпретатор перебирает подвыражения и получает их значения:
(step (cons (car '(a . b)) 'd )) step 1 --> (CONS (CAR '(A . B)) 'D) Step 1 [15]> step step 2 --> (CAR '(A . B)) Step 2 [16]> step step 3 --> '(A . B) Step 3 [17]> step
step 3 ==> value: (A . B) step 2 ==> value: A step 2 --> 'D Step 2 [18]> step
step 2 ==> value: D step 1 ==> value: (A . D) (A . D) Step 1 [14]>
Сайты с Лисп-системами
Интернет-браузер на запрос "Lisp" даст многочисленные ссылки на сайты, среди которых можно найти следующее:| http://lisp.narod.ru/ | Русскоязычный сайт для новичков с форумами и дискуссионными статьями. |
| http://www.dvo.ru/tech/lisp/index.html | Отсканированный текст известного двухтомника "Мир Лиспа" |
| http://langos.lrn.ru/langs/funclng.php | Материалы по языкам функционального программирования |
| http://www.intuit.ru/ | Сайт Интернет-Университета Информационных Технологий с большим числом дистанционных курсов по программированию |
| http://lists.unixcenter.ru/archives/mlug/2000-August/000232.html | Материалы сравнения Си с Лиспом |
| http://www.shareware-ownload.org/lisp.php | Бесплатные Lisp-системы. |
| http://ru.wikipedia.org/wiki/LISP/ | Статья про Лисп в электронной энциклопедии. |
| ftp://ftp.gnu.org/gnu/clisp/release/2.29/ | Сайт со свободно распространяемыми реализациями Clisp (clisp-2.29-win32.zip) |
| http://www.cs.cmu.edu/~dst/Lisp/ | Сайт CMU |
| http://penguin.kurgan.ru/doc/lisp.html | Про AutoLisp |
| http://www.ystok.ru/index.html | Сайт фирмы, использующей Лисп в качестве базовой технологии |
| http://www.marstu.mari.ru/mmlab/home/lisp/title.htm | Сайт Морозова с введением в программирование на Лиспе |
| http://vspu.ac.ru/~lmiker/5im/rezn.htm | Сайт Микеровой с учебником по Лиспу |
| Сайт Заочной школы программирования и Информационных технологий, включающий материалы по Лиспу |
Можно воспользоваться комплектом GNU Clisp, на базе которого подготовлены примеры в данного курса, выставленным на сайте http://green.iis.nsk.su/lisp
Установка Лисп-системы
Система программирования на языке Лисп представляет собой комплекс функций для обработки различных структур данных, включая многоуровневые списки, числа, строки, файлы и их имена. Программа на Лиспе может дополнять их комплекс. Функции встраиваются в систему как атомы, имеющие определения на уровне исполнимого кода или языка программирования. В систему входит компилятор, обеспечивающий перевод функций с уровня языка программирования на уровень исполнимого кода, поэтому нет формальной разницы между определениями разного уровня. В целом работа Лисп-системы обеспечивается интерпретатором, вычисляющим отдельные выражения, последовательность которых и есть программа.Запуск Лисп-программ из файлов
Программа на Лиспе – это последовательность интерпретируемых выражений.Представим, что подготовлен файл с именем "start.lsp":
; пример программы (defun первый (x) (car x)) ;; определение новой функции (print (первый '(one two))) ;; вывод результата применения новой функции
Расширение "lsp" символизирует тексты на Лиспе. В этом файле содержится программа с построчными комментариями. Комментарии отделяются от программы символом ";".
Defun – функция трех аргументов: первый – имя объявляемой новой функции, второй – список ее аргументов, третий – тело определения. Функция "Defun" встраивает в систему новую, определяемую в программе функцию.
Print – унарная псевдо-функция, печатающая свой аргумент.
Заранее подготовленный файл с программой можно ввести и сразу исполнить с помощью функции LOAD.
[1]> (LOAD 'start.lsp) T ONE [2]>
Перед именем файла ставится апостроф. Результат "T" означает, что чтение файла прошло успешно. При чтении файла произошла интерпретация содержащихся в нем выражений. Чтобы увидеть результаты работы программы здесь применение функции оформлено как аргумент псевдо-функции "PRINT".
На примерах видно, что символьное выражение может выглядеть как имя, число или круглоскобочная структура.
Введение в программирование на Лиспе
Основы символьной обработки
Идеальный Лисп изначально поддерживает программирование в функциональном стиле. Его основа - выбор подходящей структуры данных и базового набора функций над выбранной структурой. Информационная обработка в языке Лисп отличается от стандартных подходов к программированию тремя важными особенностями:Любая информация представляется в форме символьных выражений.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 Список … ) | Объединение множеств, представленных Списками. |
это перечень произвольного числа элементов,
Введение в программирование на Лиспе
Пример X
XN
Variable1
Переменная2
LongSong
ДолгаяПесня
N Variable1 Переменная2 LongSong ДолгаяПесня
| X N Variable1 Переменная2 LongSong ДолгаяПесня |
| Пример 4.1. |
| Закрыть окно |
список x) арг
Алг Левейший ( список x) арг xнач
если Atom (x)
то знач := x
иначе знач := Левейший (Car (x))
кон
x нач если Atom
| Алг Левейший ( список x) арг x нач если Atom (x) то знач := x иначе знач := Левейший (Car (x)) кон |
| Пример 4.10. запись на алгоритмической нотации |
| Закрыть окно |
DEFUN Левейший
( DEFUN Левейший (x)(COND ((ATOM x) x)
(T (Левейший (CAR x))) ))
ATOM x) x)
| (DEFUN Левейший (x) (COND (( ATOM x) x) (T (Левейший (CAR x))) )) |
| Пример 4.11. эквивалентная Лисп-программа |
| Закрыть окно |
алг АБС( цел x) арг
(Запись на алгоритмической нотации)алг АБС( цел x) арг x
нач
если (x < 0)
то знач := - x
иначе знач := x
кон
(эквивалентная Лисп-программа)
(DEFUN Абс(LAMBDA (x)
(COND ((< x 0 )(- x))
(T x))))
алг АБС( цел x) арг
|
(Запись на алгоритмической нотации) алг АБС( цел x) арг x нач если (x < 0) то знач := - x иначе знач := x кон (эквивалентная Лисп-программа) (DEFUN Абс(LAMBDA (x) (COND ((< x 0 )(- x)) (T x)))) |
| Пример 4.12. Абсолютное значение числа. |
| Закрыть окно |
DEFUN НОД
(эквивалентная Лисп-программа)( DEFUN НОД (LAMBDA (x y)
(COND ((< x y) (НОД y x))
((= (остаток y x ) 0 ) x )
(T (НОД (остаток y x) x ))
))
)
Алгоритм Евклида для нахождения наибольшего
|
(эквивалентная Лисп-программа) (DEFUN НОД (LAMBDA (x y) (COND ((< x y) (НОД y x)) ((= (остаток y x ) 0 ) x ) (T (НОД (остаток y x) x )) )) ) |
| Пример 4.14. Алгоритм Евклида для нахождения наибольшего общего делителя двух положительных целых чисел при условии, что определена функция "Остаток". |
| Закрыть окно |
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 ))) )
) ) )
Запись на алгоритмической
|
( Запись на алгоритмической нотации) алг ФАКТОРИАЛ ( цел N) арг N нач если (N = 0) то знач := 1 иначе знач := N * ФАКТОРИАЛ (N - 1) кон (эквивалентная Лисп-программа) (DEFUN Факториал (LAMBDA (N) (COND ((= N 0 ) 1 ) (T ( * N (Факториал (- N 1 ))) ) ) ) ) |
| Пример 4.3. Факториал неотрицательного числа. |
| Закрыть окно |
Пример (CAR (CONS 1 2 ) )
(CAR (CONS 1 2 ) )(CONS (CAR (CONS 1 2 ) ) (CDR (CONS 3 4 ) ))
Пример (CAR (CONS 1 2 ) )
| (CAR (CONS 1 2 ) ) (CONS (CAR (CONS 1 2 ) ) (CDR (CONS 3 4 ) )) |
| Пример 4.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))) )| |_____________________| _____определение функции
| ___________________________ параметр функции
___________________________ параметр функции
| (LAMBDA (x) (CAR (CDR (CDR x))) ) | |_____________________|_____определение функции | ___________________________ параметр функции |
| Пример 4.8. |
| Закрыть окно |
CAR x)
(COND ((EQ ( CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x))) (T x) )CAR x)
| (COND ((EQ ( CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x))) (T x) ) |
| Пример 4.9. |
| Закрыть окно |
Рекурсивные функции: определение и исполнение
Как правило рекурсивное применение функций должно быть определено в комплекте с нерекурсивными ветвями процесса. Основное предназначение условных выражений - рекурсивные определения функций.
Для примера рассмотрим функцию, выбирающую в списке самый левый атом:
Алг Левейший ( список 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-выражениями:
| (Declare Спецификации ) | Специфицирует переменные – dynamic-extent, ftype, ignorable, ignore, inline, optimize, special, type |
| (Defmacro Название Параметры Определение ) | Глобальное опреление макроса |
| (Defun Название Параметры Форма ) | Определение функции |
| (Function Название ) | #’ – выдает названную функцию |
| ( Lambda Параметры Определение ) | Конструирует бузымянную функцию |
B) . C))".
x = ((A . B) . C))
Имя "Левейший" теперь работает как известное название функции, которое может быть вызвано в форме:
( Левейший ' ((A . B) . C) )
| (Левейший (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-выражениями:
| (Declare Спецификации ) | Специфицирует переменные – dynamic-extent, ftype, ignorable, ignore, inline, optimize, special, type |
| (Defmacro Название Параметры Определение ) | Глобальное опреление макроса |
| (Defun Название Параметры Форма ) | Определение функции |
| (Function Название ) | #’ – выдает названную функцию |
| ( Lambda Параметры Определение ) | Конструирует бузымянную функцию |
Специальные функции
(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 (x) (CAR (CDR (CDR x))) ) | |_____________________|_____определение функции | ___________________________ параметр функции
Пример 4.8.
(html, txt)
При вызове такой безымянной функции заодно происходит задание значений параметров - связанных переменных:
((LAMBDA (x) (atom x)) 123) ; = T
X получит значение 123 на время применения построенной безымянной функции, действие которой заключается в выяснении, атом ли аргумент функции.
Связанную переменную можно объявить специальной функцией Lambda, а значение она получит при вызове функции.
(DEFUN третий (x) (CAR (CDR (CDR x))) )) | | |__________________|_______ определение функции | |_____________________________ параметры функции |___________________________________ имя новой функции
Новая функция "третий" действует так же как "Caddr" в таблице 3.4.
Именование функций работает подобно заданию значений переменным. Идентификатор представляет структуру, символизирующую функциональный объект. В ней содержится список формальных параметров функции и тело ее определения – аргументы для лямбда-конструктора.
Обычно в рассуждениях о переменных и константах молчаливо подразумевается, что речь идет о данных. Разница между константами и переменными заключается лишь в том, что значение переменной может быть в любой момент изменено, а константа изменяется существенно реже. Лисп рассматривает представления функций как данные, поэтому функции могут быть как константными, так и переменными.
Представления функции могут вычисляться и передаваться как параметры или результаты других функций.
Соответствие между именем функции и ее определением может быть изменено, подобно тому, как меняется соответствие между именем переменной и ее значением.
Количество ветвей не ограничено. Обрабатываются они по особой схеме: сначала вычисляются первые элементы аргументов по порядку, пока не найдется предикат со значением "истина". Затем выбирается второй элемент этого аргумента и вычисляется его значение, которое и считается значением всего условного выражения.
(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-выражений.
Основные понятия, возникающие при написании
Введение в программирование на Лиспе
Основные методы обработки списков
Следующие функции используются, когда рассматриваются лишь списки.APPEND - функция двух аргументов x и y, сцепляющая два списка в один.
(DEFUN append (x y) (COND ((null x) y) ((QUOTE T) (CONS (CAR x) (append (CDR x) y) ) ) ) ) (append '(A B) '(C D E)) ;= (A B C D E)
MEMBER - функция двух аргументов x и y, выясняющая встречается ли S-выражение x среди элементов списка y.
(DEFUN member (x y) (COND ((null y) (QUOTE Nil)) ((equal x (CAR y)) (QUOTE T)) ((QUOTE T) (member x (CDR y)) ) ) (member ' A '( B (A) C)
PAIRLIS - функция трех аргументов x, y, al, строит список пар соответствующих элементов из списков x и y - связывает и присоединяет их к списку al. Полученный список пар, похожий на таблицу с двумя столбцами, называется ассоциативным списком или ассоциативной таблицей. Такой список может использоваться для связывания имен переменных и функций при организации вычислений интерпретатором.
(DEFUN pairlis (x y al) (COND ((null x) al) ((QUOTE T) (CONS (CONS (CAR x) (CAR Y) ) (pairlis (CDR x) (CDR y) al) ) ) ) )
(pairlis '(A B C) '(u t v) '((D . y)(E . y))) ;= ((A . u)(B . t)(C . v)(D . y)(E . y))
ASSOC - функция двух аргументов x и al. Если al - ассоциативный список, подобный тому, что формирует функция pairlis, то assoc выбирает из него первую пару, начинающуюся с x. Таким образом, это функция поиска определения или значения по таблице, реализованной в форме ассоциативного списка.
(DEFUN assoc (x al) (COND ((equal x (CAAR al)) (CAR al)) ((QUOTE T) (assoc x (CDR al)) ) ) ) (assoc 'B '((A . (m n)) (B . (CAR x)) (C . w) (B . (QUOTE T)))) ;= (B . (CAR x))
Частичная функция - рассчитана на наличие ассоциации.
SUBLIS - функция двух аргументов al и y, предполагается, что первый из аргументов AL устроен как ассоциативный список вида ((u1 . v1) ... (uK . vK)), где u есть атомы, а второй аргумент Y - любое S-выражение. Действие sublis заключается в обработке Y, такой что вхождения переменных Ui, связанные в ассоциативном списке со значениями Vi, заменяются на эти значения.
Другими словами в S-выражении Y вхождения переменных U заменяются на соответствующие им V из списка пар AL. Вводим вспомогательную функцию SUB2, обрабатывающую атомарные S-выражения, а затем - полное определение SUBLIS:
(DEFUN sub2 (al z) (COND ((null al) z) ((equal (CAAR al) z) (CDAR al)) ((QUOTE T) (sub2 (CDR al) z)) ) )
(DEFUN sublis (al y) (COND ((ATOM y) (sub2 al y)) ((QUOTE T)(CONS (sublis al (CAR y)) (sublis al (CDR y)) ) )))
(sublis '((x . Шекспир)(y . (Ромео и Джульетта))) '(x написал трагедию y)) ;= (Шекспир написал трагедию (Ромео и Джульетта))
Пример 5.1.
(html, txt)
INSERT – вставка z перед вхождением ключа x в список al.
(DEFUN insert (al x z) (COND ((null al) Nil) ((equal (CAR al) x) (CONS z al)) ((QUOTE T) (CONS (CAR al) (insert (CDR al) x z))) ) )
(insert '(a b c) 'b 's) ; = (a s b c)
ASSIGN – модель присваивания переменным, хранящим значения в ассоциативном списке. Происходит замена значения, связанного с данной переменной в первой найденной паре, на новое заданное значение. Если не было пары вообще, то новую пару из переменной и ее значения размещаем в конец а-списка, чтобы она могла работать как глобальная.
(DEFUN assign (x v al) (COND ((Null al) (CONS (CONS x v) Nil )) ((equal x (CAAR al))(CONS (CONS x v) (CDR al))) ((QUOTE T) (CONS (CAR al) (assign x v (CDR al)))) ) ) (assign 'a 111 '((a . 1)(b . 2)(a . 3))) ;= ((a . 111)(b . 2)(a . 3)) (assign 'a 111 '((c . 1)(b . 2)(a . 3))) ;= ((c . 1)(b . 2)(a . 111)) (assign 'a 111 '((c . 1)(d . 3))) ;= ((c . 1)(d . 3) (a . 111))
Упражнение 5.1: Введите функции с именами – Пусто, Пара_в_список, Список_в_пару, входит_ли, Соединение, Элемент, Связывание, Ассоциация, Ряд_подстановок, Вставка, Присваивание, как аналоги вышеприведенных функций.
Упражнение 5.2: Напишите определение функции REVERSE – обращение списка, т.е. перечисление его элементов в обратном порядке.
Ответ:
(defun reverse (m) (cond ((null m) NIL) (T (append(reverse(cdr m)) (list(car m)) )) ))
Теперь посмотрим ее вариант как пример использования накапливающих параметров и вспомогательных функций:.
(defun rev (m n) (cond ((null m) N) (T (rev(cdr m) (cons (car m) n))) ))
(defun reverse (m) (rev m Nil) )
Такое определение экономнее расходует память.
| (Append Список … ) | Сцепляет списки, полученные как аргументы |
| (Assoc Атом А-список) | Находит в А- списке пару, левая часть которой - Атом |
| (Eq Данное1 Данное2) | Истина при идентичных данных |
| (Equal Структура1 Структура2 ) | Истина при эквивалентных структурах |
| (Delete Объект Список ) | Строит копию Списка без заданного объекта |
| (Intersection Список … ) | Пересечение списков |
| (Last Список ) | Последний элемент сруктуры, представляющей список. Можно задавать длину завершающего отрезка списка. |
| (Lenth Список ) | Длина списка |
| (List Форма … ) | Строит список из значений Форм |
| (Member Объект Список ) | Ищет Объект в Списке |
| (Null Форма) | Истина для Nil |
| (Pairlis Атомы Данные А-спиок) | Пополняет А-список парми из Атомов и значений соответсвующих Данных. |
| (Reverse Список ) | Копия Списка с обратным порядком элементов |
| (Set-difference Список … ) | Разность множеств, представленных Списками |
| (Sort Список Предикат ) | Упорядочивает Список согласно Предикату |
| (Sublis А-список Структура ) | Преобразует Структуру согласно А-списку методом подстановки данных вместо связанных с ними атомов. |
| (Subst Новое Старое Структура ) | Преобразует Структуру, заменяя Старое на Новое. |
| (Union Список … ) | Объединение множеств, представленных Списками. |
x написал трагедию
(sublis '((x . Шекспир)(y . (Ромео и Джульетта))) '( x написал трагедию y));= (Шекспир написал трагедию (Ромео и Джульетта))
x написал трагедию
| (sublis '((x . Шекспир)(y . (Ромео и Джульетта))) '( x написал трагедию y)) ;= (Шекспир написал трагедию (Ромео и Джульетта)) |
| Пример 5.1. |
| Закрыть окно |
В некотором смысле это сосредотачивает
Введение в программирование на Лиспе
Определение универсальной функции
Универсальная функция eval, которую предстоит определить, должна удовлетворять следующему условию: если представленная аргументом форма сводится к функции, имеющей значение на списке аргументов этой же формы, то это значение и является результатом функции eval.(eval '(fn arg1 ... argK))
Результат применения "fn" к аргументам "arg1, ..., argK".
Предикаты и истинность в Лиспе
В Лиспе есть два атомных символа, которые представляют истину и ложь соответственно. Эти два атома - T и NIL. Эти символы - реальные значения всех предикатов в системе. Главная причина в удобстве кодирования. Во многих случаях достаточно отличать произвольное значение от пустого списка.Не существует формального различия между функцией и предикатом в Лиспе. Предикат может быть определен как функция со значениями либо T либо NIL. Можно использовать форму, не являющуюся предикатом там, где требуется предикат: предикатная позиция условного выражения или аргумент логического предиката. Семантически любое S-выражение, только не NIL, будет рассматриватсья как истинное в таком случае. Предикат EQ ведет себя следующим образом:
Выполнено достаточно строгое построение совершенно формальной математической системы, называемой "Элементарный ЛИСП". Составляющие этой формальной системы:
Выполненное определение универсальной функции – макетный образец Лисп-системы, основные черты которой унаследованы многими системами программирования.
| (Apply Функция Список-ргументов ) | Применяет функцию к списку аргументов |
| ( Compile Название ) | Компилирует названную функцию, кроме того сообщает, успешна ли компиляция |
| (Eval Форма ) | Вычисление формы |
| (Funcall Функция Аргумент … ) | Применяет функцию к аргументам |
| (The Тип Форма) | Приводит значение Формы к заданному Типу |
| (Type-of Данное ) | Выдает тип данного |
| (Quote Форма ) | Форма без вычсления выдается как результат |
Пример <форма> ::= <переменная>
<форма> ::= <переменная>| (QOUTE )
| (COND (<форма> <форма>) ... (<форма> <форма>))
| (<функция> <аргумент> ... <аргумент>)
<аргумент> ::= <форма>
<переменная> ::= <идентификатор>
<функция> ::= <название>
| (LAMBDA <список_переменных> <форма>)
| (DEFUN <название> <функция>)
<список_переменных> ::= (<переменная> ... )
<название> = <идентификатор>
<идентификатор> ::= <атом>
Синтаксическая сводка программ на языке
|
<форма> ::= <переменная> | (QOUTE <аргумент> ::= <форма> <переменная> ::= <идентификатор> <функция> ::= <название> | (LAMBDA <список_переменных> <форма>) | (DEFUN <название> <функция>) <список_переменных> ::= (<переменная> ... ) <название> = <идентификатор> <идентификатор> ::= <атом> |
| Пример 6.1. Синтаксическая сводка программ на языке Лисп |
| Закрыть окно |
Вычисление
Явное определение такой функции позволяет достичь четкости механизмов обработки Лисп-программ.(eval '((LAMBDA (x y) (CONS (CAR x) y)) '(A B) '(C D) )) = (A C D)
Вводим две основные функции eval и apply для обработки форм и обращения к функциям соответственно. Каждая из этих функций использует ассоциативный список для хранения связанных имен - значений переменных и определений функций. Сначала этот список пуст.
Вернемся к синтаксической сводке вычислимых форм.
<форма> ::= <переменная> | (QOUTE
<аргумент> ::= <форма>
<переменная> ::= <идентификатор>
<функция> ::= <название> | (LAMBDA <список_переменных> <форма>) | (DEFUN <название> <функция>)
<список_переменных> ::= (<переменная> ... )
<название> = <идентификатор>
<идентификатор> ::= <атом>
Пример 6.1. Синтаксическая сводка программ на языке Лисп (html, txt)
Каждой ветви этой сводки соответствует ветвь универсальной функции:
(DEFUN eval (e) (ev e '((Nil . Nil))))
Вспомогательная функция ev понадобилась, чтобы ввести накапливающий параметр – ассоциативный список, в котором будут храниться связи между переменными и их значениями и названиями функций и их определениями.
(defun ev (e a) (COND ( (atom e) (cdr (assoc e a)) ) ( (eq (car e) 'QUOTE) (cadr e)) ( (eq(car e) 'COND) (evcon (cdr e) a)) ( T (apply (car e) (evlis (cdr e) a) a) )) )
Поясним ряд пунктов этого определения.
Первый аргумент ev - форма. Если она - атом, то этот атом может быть только именем переменной, а значение переменной должно бы уже находиться в ассоциативном списке.
Если CAR от формы - QUOTE, то она представляет собой константу, значение которой вычисляется как CADR от нее самой.
Если CAR от формы - COND, то форма - условное выражение. Вводим вспомогательную функцию EVCON, (определение ее будет дано ниже), которая обеспечивает вычисление предикатов (пропозициональных термов) по порядку и выбор формы, соответствующей первому предикату, принимающему значение "истина".
Эта форма передается EV для дальнейших вычислений.
Все остальные случаи рассматриваются как список из функции с последующими аргументами.
Вспомогательная функция EVLIS обеспечивает вычисление аргументов, затем представление функции и список вычисленных значений аргументов передаются функции APPLY.
(defun apply (fn x a) (COND ((atom fn) (cond ((eq fn 'CAR) (caar x)) ((eq fn 'CDR) (cdar x)) ((eq fn 'CONS) (cons (car x) (cadr x)) ) ((eq fn 'ATOM) (atom (car x)) ) ((eq fn 'EQ) (eq (car x) (cadr x)) ) ((QUOTE T) (apply (ev fn a) x a)) ) ) ) ((eq(car fn)'LAMBDA) (ev (caddr fn) (pairlis (cadr fn) x a) )) ((eq (car fn) 'DEFUN) (apply (cadddr fn) x (cons (cons (cadr fn) (cons 'LAMBDA (caddr fn) ) ) a) ))))
Первый аргумент apply - функция. Если она - атом, то существует две возможности: атом представляет одну из элементарных функций (car cdr cons atom eq). В таком случае соответствующая ветвь вычисляет значение этой функции на заданных аргументах. В противном случае, этот атом - имя ранее заданного определения, которое можно найти в ассоциативном списке.
Если функция начинается с LAMBDA, то ее аргументы попарно соединяются со связанными переменными, а тело определения (форма из лямбда-выражения) передается как аргумент функции EV для дальнейшей обработки.
Если функция начинается с DEFUN, то ее название и определение соединяются в пару и полученная пара размещается в ассоциативном списке, чтобы имя функции стало определенным при дальнейших вычислениях. Они произойдут как рекурсивный вызов apply, которая вместо имени функции теперь работает с ее определением при более полном ассоциативном списке - в нем теперь размещено определение названия функции. Поскольку определение размещается на "верху" стека, оно становится доступным для всех последующих переопределений, то есть работает как локальный объект. Глобальные объекты, такие как обеспечивает псевдо-функция DEFUN в системе Clisp, устроены немного иначе, что будет рассмотрено в следующей лекции.
assoc и pairlis уже определены ранее.
(DEFUN evcon (c a) (COND ((ev (caar c) a) (ev (cadar c) a) ) ( T (evcon (cdr c) a) ) ))
*) Примечание. В идеальном Лиспе не допускается отсутствие истинного предиката, т.е. пустого C.
(DEFUN evlis (m a) (COND ((null m) Nil ) ( T (cons(ev (car m) a) (evlis(cdr m) a) )) )
При
(DEFUN eval (e) (ev e ObList ))
определения функций могут накапливаться в системной переменной ObList, тогда они могут работать как глобальные определения. ObList обязательно должна содержать глобальное определение встроенной константы Nil, можно разместить в ней и представление истины - T.
Определение универсальной функции является важным шагом, показывающим одновременно и механизмы реализации языков программирования, и технику функционального программирования на любом языке. Пока еще не описаны многие другие особенности языка Лисп, которые будут рассмотрены позднее. Но все они будут увязаны в единую картину, основа которой согласуется с этим определением.
Во многих Лисп-системах все элементарные функции вырабатывают результат и на списках, и на атомах, но его смысл зависит от системных решений, что может создавать трудности при переносе программ на другие системы. Базисный предикат EQ всегда имеет значение, но смысл его на неатомарных аргументах будет более понятен после знакомства со структурами данных, используемыми для представления списков в машине.
Введение в программирование на Лиспе
Безымянные функции
Определения в примерах 4 и 5 не вполне удобны по следующим причинам:С одной стороны последнее противоречит пониманию смысла именования как техники, обеспечивающей неоднократность применения поименованного объекта. С другой стороны придумывать хорошие, долго сохраняющие понятность и соответствие цели, имена - задача нетривиальная.
Учитывая это, было бы удобнее вспомогательные определения вкладывать непосредственно в определения целевых функций и обходиться при этом вообще без имен. Конструктор функций lambda обеспечивает такой стиль построения определений. Этот конструктор любое выражение expr превращает в функцию с заданным списком аргументов (x1 ... xK) в форме так называемых lambda-выражений:
( lambda (x1 ... xK) expr )
Имени такая функций не имеет, поэтому может быть применена лишь непосредственно. Defun использует этот конструктор, но, кроме того, дает функциям имена.
(defun sqware (xl)(map-el(lambda(x)(* x x))xl)) (defun duble (xl)(map-el(lambda(x)(cons x x))xl))
Пример 7.9. Определение функций duble и sqwure из примеров 4 и 5 без использования имен и вспомогательных функций: (html, txt)
Любую систему взаимосвязанных функций можно преобразовать к одной функции, используя вызовы безымянных функций.
Числа и строки
Любую информацию можно представить символьными выражениями. В качестве основных видов символьных выражений выбраны списки и атомы. Атом - неделимое данное, представляющее информацию произвольной природы. Но во многих случаях знание природы информации дает более четкое понимание особенностей изучаемых механизмов.Программирование работы с числами и строками – привычная, хорошо освоенная область информационной обработки, удобная для оценки преимуществ использования функционалов. Опуская технические подробности, просто отметим, что числа и строки рассматриваются как самоопределимые атомы, смысл которых не требует никакого ассоциирования, он понятен просто по виду записи. Например, натуральные числа записываются без особенностей и могут быть почти произвольной длины:
1 -123 9876543210000000000000123456789
Можно работать с дробными и вещественными числами:
8/12 ;= 2/3 3.1415926
Строки заключаются в обычные двойные кавычки:
"строка любой длины, из произвольных символов, включая все что угодно"
Со строками можно при необходимости работать посимвольно, хотя они рассматриваются как атомы.
(string-equal "строка 1" " строка1");=Nil (ATOM "a+b-c") ;= T (char "стр1" 4 ) ;= "1"
Список - составное данное, первый элемент которого может рассматриваться как функция, применяемая к остальным элементам, также представленным как символьные выражения.
Это относится и к операциям над числами и строками.
Большинство операций над числами при префиксной записи естественно рассматривать как мультиоперации от произвольного числа аргументов.
(+ 1 2 3 4 5 6) ;= 21 (- 12 6 3) ;= 3 (/ 3 5) ;= 3/5
Любое данное можно превратить в константу, поставив перед ним "'" апостроф. Это эквивалентно записи со специальной функцией "QUOTE". Для чисел и строк в этом нет необходимости, но это не запрещено:
'1 ;= 1 '"abc" ;= "abc"
Отказ от барьера между представлениями функций и значений дает возможность символьные выражения использовать как для изображения заданных значений, включая любые структуры над числами и строками, так и для определения функций, обрабатывающих любые данные. (Напоминаем, что определение функции - данное.)
Функционалы - это функции, которые используют в качестве аргументов или результатов другие функции. При построении функционалов переменные могут выполнять роль имен функций, определения которых находятся во внешних формулах, использующих функционалы.
| (= Число … ) | Истина, если разница между любыми двумя аргументами равна нулю |
| (/= Число … ) | Истина, если никакие два аргумента не равны между собой |
| (> Число … ) | Истина, если каждый аргумент превышает прешественника |
| (< Число … ) | Истина, если каждый аргумент меньше прешественника |
| (<= Число … ) | Истина, если каждый аргумент меньше или равен прешественнику |
| (>= Число … ) | Истина, если каждый аргумент превышает или равен прешественнику |
| (* Число … ) | Произведение произвольного числа аргументов. 1 при их отсутствии. |
| (+ Число … ) | Сумма произвольного числа аргументов. 0 при их отсутствии. |
| (- Число … ) | Эквивалентно расстановке минусов между аргументами, т.е. (- a b c ) = a – b – c |
| (/ Число … ) | Первое число делится на произведение остальных, среди которых не должно быть нуля. |
| (1+ Число ) | ( + Число 1) |
| (1- Число ) | ( - Число 1) |
| (Boole Операция Целое1 Целое2 ) | Вычисляет результат применеия побитовой Операции к двум Целым. |
| (Gcd Число …) | Наибольший общий делитель. Ноль без аргументов. |
| (Lcm Число … ) | Наименьшее общее произведение, 1 при отсутствии аргументов. |
| (min Число …) | |
| (max Число …) |
Функционалы
Рассмотрим технику использования функционалов и наметим, как от простых задач перейти к более сложным.(defun next (xl) ; Следующие числа: (cond ; пока список не пуст (xl (cons (1+ (car xl)) ; прибавляем 1 к его голове (next (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список
(next '(1 2 5 )) ; = (2 3 6 )
Пример 7.1. Для каждого числа из заданного списка получить следующее за ним число и все результаты собрать в список. (html, txt)
(defun 1st (xl) ; "головы" элементов = CAR (cond ; пока список не пуст (xl (cons (caar xl) ; выбираем CAR от его головы (1st (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список
(1st '((один два )(one two )(1 2 )) ) ; = (один one 1)
Пример 7.2. Построить список из "голов" элементов списка (html, txt)
(defun lens (xl) ; Длины элементов (cond ; Пока список не пуст (xl (cons (length (car xl)); вычисляем длину его головы (lens (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список
(lens '((1 2 ) () (a b c d ) (1 (a b c d ) 3 )) ) ; = (2 0 4 3 )
Пример 7.3. Выяснить длины элементов списка (html, txt)
Внешние отличия в записи этих трех функций малосущественны, что позволяет ввести более общую функцию map-el, в определении которой имена "car", "1+" и "lenth" могут быть заданы как значения параметра fn:
(defun map-el (fn xl) ; Поэлементное преобразование XL ; с помощью функции FN. (cond ; Пока XL не пуст, (xl (cons (funcall fn (car xl) ) ; применяем FN как функцию к голове XL
(map-el fn (cdr xl)) ; и переходим к продолжению списка, ) ) ) ) ; собирая результаты в новый список.
Примечание: funcall – это аналог apply, не требующий заключения аргументов в общий список:
(APPLY (DEFUN Пара (x y) (CONS x y)) (QUOTE (A (B C))));=(A B C)
(FUNCALL (DEFUN Пара (x y) (CONS x y)) (QUOTE A) (QUOTE (B C)));=(A B C)
Эффект функций next, 1st и lens можно получить выражениями:
(map-el #'1+ xl) ;следующие числа (map-el #'car xl) ;"головы" элементов = CAR
#’ x ;= (FUNCTION x) - сокращенное обозначение функции-значения соответственно.
(map-el #'length xl) ; Длины элементов
(map-el #'1+ '(1 2 5 )) ; = (2 3 6 ) (map-el #'car ' ((один два)(one two)(1 2)));=(один one 1) (map-el #'length '((1 2)()(a b c d)(1(a b c d)3))) ; = (2 0 4 3 )
Эти определения функций формально эквивалентны ранее приведенным – они сохраняют отношение между аргументами и результатами.
Все три примера можно решить с помощью таких определяющих выражений:
(defun next (xl) (map-el #'1+ xl )) ; Очередные числа: (defun 1st (xl) (map-el #'car xl )) ; "головы" элементов = CAR (defun lens (xl) (map-el #'length xl )) ; Длины элементов
Параметром функционала может быть любая вспомогательная функция.
(defun sqw (x) (* x x)); Возведение числа в квадрат (sqw 3) ; = 9
Пример 7.4. Пусть дана вспомогательная функция sqw, возводящая числа в квадрат (html, txt)
Построить список квадратов чисел, используя функцию sqw:
(defun sqware (xl) ; ; Возведение списка чисел в квадрат (cond ; Пока аргумент не пуст, (xl (cons (sqw (car xl)) ; применяем sqw к его голове (sqware (cdr xl)) ; и переходим к хвосту списка, ) ) ) ) ; собирая результаты в список
(sqware '(1 2 5 7 )); = (1 4 25 49 )
Можно использовать map-el:
(defun sqware (xl) (map-el #'sqw xl))
Ниже приведено определение функции sqware- без вспомогательной функции, выполняющее умножение непосредственно. Оно влечет двойное вычисление (CAR xl), т.е. такая техника не вполне эффективна:
(defun sqware- (xl) (cond (xl (cons (* (car xl) (car xl) ); квадрат головы ; вычислять приходится дважды (sqware- (cdr xl)) ) ) ) )
(pair '(один два two three) '(1 2 два три)) ; = ((один . 1)(два . 2)(two два )(three три ))
Пример 7.6. Построить ассоциативный список, т.е. список пар из имен и соответствующих им значений, по заданным спискам имен и их значений:
(defun map-comp (fn al vl) ; fn покомпонентно применить ; к соотвественным элементам AL и VL (cond (xl (cons (fn (car al) (car vl)) ; Вызов данного FN как функции (map-comp (cdr al) (cdr vl)) ) ) ) )
Пример 7.7. Определить функцию покомпонентной обработки двух списков с помощью заданной функции fn:
Теперь покомпонентные действия над векторами, представленными с помощью списков, полностью в наших руках. Вот списки и сумм, и произведений, и пар, и результатов проверки на совпадение:
(map-comp #'+ '(1 2 3) '(4 6 9)) ; = (5 8 12 ) - Суммы (map-comp #'* '(1 2 3) '(4 6 9)) ; = (4 12 27)-Произведения (map-comp #'cons '(1 2 3) '(4 6 9)) ; = ((1.4)(2.6)(3.9))-Пары (map-comp #'eq '(4 2 3 ) '(4 6 9)) ; = (T NIL NIL)-Сравнения
Достаточно уяснить, что надо делать с элементами списка, остальное делает отображающий функционал map-comp.
(defun mapf (fl el) (cond ; Пока первый аргумент не пуст, (fl (cons ((car fl) el ) ; применяем очередную функцию ; ко второму аргументу (mapf (cdr fl) el) ; и переходим к остальным функциям, ) ) )) ; собирая их результаты в общий список
(mapf '(length car cdr)'(a b c d));=(4 a(b c d))
Пример 7.8. Для заданного списка вычислим ряд его атрибутов, а именно - длина, первый элемент, остальные элементы списка без первого.
Композициями таких функционалов можно применять серии функций к списку общих аргументов или к параллельно заданной последовательности списков их аргументов. Естественно, и серии, и последовательности представляются списками.
Композиции функционалов, фильтры, редукции
Вызовы функционалов можно объединять в более сложные структуры таким же образом, как и вызовы обычных функций, а их композиции можно использовать в определениях новых функций.Композиции функционалов позволяют порождать и более мощные построения, достаточно ясные, но требующие некоторого внимания.
(defun decart (x y) (map-el #'(lambda (i) (map-el #'(lambda (j) (list i j)) y) ) x) )
Пример 7.10. Декартово произведение хочется получить определением вида: (html, txt)
Но результат вызова
(decart '(a s d) '( e r t))
дает
(((A E)(A R)(A T))((S E)(S R)(S T))((D E)(D R)(D T)))
вместо ожидаемого
((A E)(A R)(A T)(S E)(S R)(S T)(D E)(D R)(D T))
Дело в том, что функционал map-el, как и map-comp (пример 7), собирает результаты отображающей функции в общий список с помощью операции cons так, что каждый результат функции образует отдельный элемент.
А по смыслу задачи требуется, чтобы список был одноуровневым.
Посмотрим, что получится, если вместо cons при сборе результатов воспользоваться функцией append.
(defun list-ap (ll) (cond (ll (append (car ll) (list-ap (cdr ll) ) ) ) ) )
(list-ap '((1 2)(3 (4)))); = (1 2 3 (4))
Пример 7.11. Пусть дан список списков. Нужно их все сцепить в один общий список. (html, txt)
Тогда по аналогии можно построить определение фукнционала map-ap:
(defun map-ap (fn ll) (cond (ll (append (fn (car ll) ) (map-ap fn (cdr ll) ) ) ) ) )
(map-ap 'cdr '((1 2 3 4)(2 4 6 8)( 3 6 9 12))) ; = (2 3 4 4 6 8 6 9 12)
Следовательно, интересующая нас форма результата может быть получена:
(defun decart (x y) (map-ap #'(lambda (i) (map-el #'(lambda (j) (list i j)) y) ) x) ) (decart '(a s d) '( e r t)) ;=((A E)(A R)(A T)(S E)(S R)(S T)(D E)(D R)(D T))
Соединение результатов отображения с помощью append обладает еще одним полезным свойством: при таком сцеплении исчезают вхождения пустых списков в результат. А в Лиспе пустой список используется как ложное значение, следовательно такая схема отображения пригодна для организации фильтров. Фильтр отличается от обычного отображения тем, что окончательно собирает не все результаты, а лишь удовлетворяющие заданному предикату.
(defun heads (xl) (map-ap #'(lambda (x)(cond (x (cons (car x) NIL)))) ; временно голова размещается в список, ; чтобы потом списки сцепить xl ) ) (heads '((1 2)()(3 4)()(5 6))) ;=(1 3 5)
Пример 7.12. Построить список голов непустых списков можно следующим образом: (html, txt)
Рассмотрим еще один типичный вариант применения функционалов. Представим, что нас интересуют некие интегральные характеристики результатов, полученных при отображении, например, сумма полученных чисел, наименьшее или наибольшее из них и т.п. В таком случае говорят о свертке результата или его редукции. Редукция заключается в сведении множества элементов к одному элементу, в вычислении которого задействованы все элементы множества.
(defun sum-el ( xl) (cond ((null xl) 0) (xl (+ (car xl) (sum-el (cdr xl) ) ) ) ) )
(sum-el '(1 2 3 4 ) ) ; = 10
Пример 7.13. Подсчитать сумму элементов заданного списка. (html, txt)
Перестроим определение, чтобы вместо "+" можно было использовать произвольную бинарную функцию:
(defun red-el (fn xl) (cond ((null xl) 0) (xl (fn (car xl) (red-el fn (cdr xl) ) )))) (red-el '+ '(1 2 3 4 ) ) ; = 10
В какой-то мере map-ap ведет себя как свертка - она сцепляет результаты без сохранения границ между ними.
Такие формулы удобны при моделировании множеств, графов и металингвистических формул, а к их обработке сводится широкий класс задач не только в информатике.
| (Mapc Функция Список … ) | Отображает ряд списков с помощью Функции. Число списков должно соотвествовать числу аргументов Функции. Возвращает первый аргумент. |
| (Mapcan Функция Список … ) | Отображает ряд списков с помощью Функции, прменяемой к элементам списков. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции, полученный с помощью nconc. |
| (Mapcar Функция Список … ) | Отображает ряд списков с помощью Функции, прменяемой к элементам списков. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции. |
| (Mapcon Функция Список … ) | Отображает ряд списков с помощью Функции, применяемой к редуцируемым спискам. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции, полученный с помощью nconc. |
| (Mapl Функция Список … ) | Отображает ряд списков с помощью Функции, применяемой к редуцируемым спискам. Число списков должно соотвествовать числу аргументов Функции. Возвращает первый аргумент. |
| ( Maplist Функция Список … ) | Отображает ряд списков с помощью Функции, применяемой к редуцируемым спискам. Число списков должно соотвествовать числу аргументов Функции. Возвращает список результатов Функции. |
пока список не
(defun next (xl) ; Следующие числа:(cond ; пока список не пуст
(xl (cons (1+ (car xl)) ; прибавляем 1 к его голове
(next (cdr xl)) ; и переходим к остальным,
) ) ) ) ; собирая результаты в список
(next '(1 2 5 )) ; = (2 3 6 )
Для каждого числа из заданного
|
(defun next (xl) ; Следующие числа: (cond ; пока список не пуст (xl (cons (1+ (car xl)) ; прибавляем 1 к его голове (next (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список (next '(1 2 5 )) ; = (2 3 6 ) |
| Пример 7.1. Для каждого числа из заданного списка получить следующее за ним число и все результаты собрать в список. |
| Закрыть окно |
defun decart
( defun decart (x y)(map-el #'(lambda (i)
(map-el #'(lambda (j) (list i j))
y)
) x) )
Декартово произведение хочется получить определением
| (defun decart (x y) (map-el #'(lambda (i) (map-el #'(lambda (j) (list i j)) y) ) x) ) |
| Пример 7.10. Декартово произведение хочется получить определением вида: |
| Закрыть окно |
cdr ll)
(defun list-ap (ll)(cond
(ll (append (car ll)
(list-ap ( cdr ll) )
) ) ) )
(list-ap '((1 2)(3 (4)))); = (1 2 3 (4))
Пусть дан список списков. Нужно
|
(defun list-ap (ll) (cond (ll (append (car ll) (list-ap (cdr ll) ) ) ) ) ) (list-ap '((1 2)(3 (4)))); = (1 2 3 (4)) |
| Пример 7.11. Пусть дан список списков. Нужно их все сцепить в один общий список. |
| Закрыть окно |
временно голова размещается
(defun heads (xl) (map-ap#'(lambda (x)(cond (x (cons (car x) NIL))))
; временно голова размещается в список,
; чтобы потом списки сцепить
xl
) )
(heads '((1 2)()(3 4)()(5 6))) ;=(1 3 5)
чтобы потом списки сцепить xl
| (defun heads (xl) (map-ap #'(lambda (x)(cond (x (cons (car x) NIL)))) ; временно голова размещается в список, ; чтобы потом списки сцепить xl ) ) (heads '((1 2)()(3 4)()(5 6))) ;=(1 3 5) |
| Пример 7.12. Построить список голов непустых списков можно следующим образом: |
| Закрыть окно |
null xl)
(defun sum-el ( xl)(cond (( null xl) 0)
(xl (+ (car xl)
(sum-el (cdr xl) )
) ) ) )
(sum-el '(1 2 3 4 ) ) ; = 10
Подсчитать сумму элементов заданного
|
(defun sum-el ( xl) (cond ((null xl) 0) (xl (+ (car xl) (sum-el (cdr xl) ) ) ) ) ) (sum-el '(1 2 3 4 ) ) ; = 10 |
| Пример 7.13. Подсчитать сумму элементов заданного списка. |
| Закрыть окно |
выбираем CAR от его
(defun 1st (xl) ; "головы" элементов = CAR(cond ; пока список не пуст
(xl (cons (caar xl) ; выбираем CAR от его головы
(1st (cdr xl)) ; и переходим к остальным,
) ) ) ) ; собирая результаты в список
(1st '((один два )(one two )(1 2 )) ) ; = (один one 1)
выбираем CAR от его головы
|
(defun 1st (xl) ; "головы" элементов = CAR (cond ; пока список не пуст (xl (cons (caar xl) ; выбираем CAR от его головы (1st (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список (1st '((один два )(one two )(1 2 )) ) ; = (один one 1) |
| Пример 7.2. Построить список из "голов" элементов списка |
| Закрыть окно |
Пока список не
(defun lens (xl) ; Длины элементов(cond ; Пока список не пуст
(xl (cons (length (car xl)); вычисляем длину его головы
(lens (cdr xl)) ; и переходим к остальным,
) ) ) ) ; собирая результаты в список
(lens '((1 2 ) () (a b c d ) (1 (a b c d ) 3 )) ) ; = (2 0 4 3 )
Пока список не пуст
|
(defun lens (xl) ; Длины элементов (cond ; Пока список не пуст (xl (cons (length (car xl)); вычисляем длину его головы (lens (cdr xl)) ; и переходим к остальным, ) ) ) ) ; собирая результаты в список (lens '((1 2 ) () (a b c d ) (1 (a b c d ) 3 )) ) ; = (2 0 4 3 ) |
| Пример 7.3. Выяснить длины элементов списка |
| Закрыть окно |
defun sqw
( defun sqw (x) (* x x)); Возведение числа в квадрат(sqw 3) ; = 9
Пусть дана вспомогательная функция sqw,
| (defun sqw (x) (* x x)); Возведение числа в квадрат (sqw 3) ; = 9 |
| Пример 7.4. Пусть дана вспомогательная функция sqw, возводящая числа в квадрат |
| Закрыть окно |
defun tuple
( defun tuple (x) (cons x x))(tuple 3) ; = (3 . 3)
(tuple 'a) ; = (a . a)
(tuple '(Ха))
; = ((Ха).(Ха))=((Ха)Ха)-это одно и то же!
Пусть дана вспомогательная функция tuple,
| (defun tuple (x) (cons x x)) (tuple 3) ; = (3 . 3) (tuple 'a) ; = (a . a) (tuple '(Ха)) ; = ((Ха).(Ха))=((Ха)Ха)-это одно и то же! |
| Пример 7.5. Пусть дана вспомогательная функция tuple, превращающая любое данное в пару: |
| Закрыть окно |
то CDR будет давать
(defun pairl (al vl); Ассоциативный список(cond ; Пока AL не пуст,
(al (cons (cons (car al) (car vl))
; строим пары из "голов".
(pairl (cdr al) (cdr vl))
; Если VL исчерпается,
; то CDR будет давать NIL
) ) ) )
(pair '(один два two three) '(1 2 два три))
; = ((один . 1)(два . 2)(two два )(three три ))
то CDR будет давать NIL
|
(defun pairl (al vl); Ассоциативный список (cond ; Пока AL не пуст, (al (cons (cons (car al) (car vl)) ; строим пары из "голов". (pairl (cdr al) (cdr vl)) ; Если VL исчерпается, ; то CDR будет давать NIL ) ) ) ) (pair '(один два two three) '(1 2 два три)) ; = ((один . 1)(два . 2)(two два )(three три )) |
| Пример 7.6. Построить ассоциативный список, т.е. список пар из имен и соответствующих им значений, по заданным спискам имен и их значений: |
| Закрыть окно |
к соотвественным элементам AL
(defun map-comp (fn al vl) ; fn покомпонентно применить; к соотвественным элементам AL и VL
(cond
(xl (cons (fn (car al) (car vl))
; Вызов данного FN как функции
(map-comp (cdr al) (cdr vl))
) ) ) )
Вызов данного FN как функции
| (defun map-comp (fn al vl) ; fn покомпонентно применить ; к соотвественным элементам AL и VL (cond (xl (cons (fn (car al) (car vl)) ; Вызов данного FN как функции (map-comp (cdr al) (cdr vl)) ) ) ) ) |
| Пример 7.7. Определить функцию покомпонентной обработки двух списков с помощью заданной функции fn: |
| Закрыть окно |
Пока первый аргумент не
(defun mapf (fl el)(cond ; Пока первый аргумент не пуст,
(fl (cons ((car fl) el )
; применяем очередную функцию
; ко второму аргументу
(mapf (cdr fl) el)
; и переходим к остальным функциям,
) ) )) ; собирая их результаты в общий список
(mapf '(length car cdr)'(a b c d));=(4 a(b c d))
Пока первый аргумент не пуст,
|
(defun mapf (fl el) (cond ; Пока первый аргумент не пуст, (fl (cons ((car fl) el ) ; применяем очередную функцию ; ко второму аргументу (mapf (cdr fl) el) ; и переходим к остальным функциям, ) ) )) ; собирая их результаты в общий список (mapf '(length car cdr)'(a b c d));=(4 a(b c d)) |
| Пример 7.8. Для заданного списка вычислим ряд его атрибутов, а именно - длина, первый элемент, остальные элементы списка без первого. |
| Закрыть окно |
defun sqware
( defun sqware (xl)(map-el(lambda(x)(* x x))xl))(defun duble (xl)(map-el(lambda(x)(cons x x))xl))
и sqwure из примеров
| (defun sqware (xl)(map-el(lambda(x)(* x x))xl)) (defun duble (xl)(map-el(lambda(x)(cons x x))xl)) |
| Пример 7.9. Определение функций duble и sqwure из примеров 4 и 5 без использования имен и вспомогательных функций: |
| Закрыть окно |
Отображающие функционалы позволяют строить программы
Введение в программирование на Лиспе
Именование значений и подвыражений
Переменная - это символ, который используется для представления аргумента функции.Атом может быть как переменной, так и фактическим аргументом. Некоторые сложности вызывает то обстоятельство, что иногда аргументы могут быть переменными, вычисляемыми внутри вызова другой функции.
Часть интерпретатора, которая при вычислении функций связывает переменные, называется APPLY. Когда APPLY встречает функцию, начинающуюся с LAMBDA, список переменных попарно связывается со списком аргументов и добавляется к началу ассоциативного списка.
Часть интерпретатора, которая потом вычислит переменные, называется EVAL. При вычислении тела функции универсальная функция EVAL может обнаружить переменные. Она их ищет в ассоциативном списке. Если переменная встречается там несколько раз, то используется последнее или самое новое значение.
Проиллюстрируем это рассуждение на примере. Предположим, интерпретатор получает следующее S-выражение:
((LAMBDA (X Y) (CONS X Y)) 'A 'B)
Функция:
(LAMBDA (X Y) (CONS X Y))
Аргументы: (A B)
EVAL передает эти аргументы функции APPLY. (См. параграф 6).
(apply #'(LAMBDA (X Y) (CONS X Y)) '(A B) Nil )
APPLY свяжет переменные и передаст функцию и удлинненный а-список EVAL для вычисления.
(eval '(CONS X Y) ' ((X . A) (Y . B) ))
EVAL вычисляет переменные и сразу передает их функции CONS, строящий из них бинарный узел.
(Cons 'A 'B) = (A . B)
Можно добиться большей прозрачности сложных определений функций, используя иерархию контекстов и средства именования выражений. Специальная функция Let сопоставляет локальным переменным независимые выражения. С ее помощью можно вынести из сложного определения любые совпадающие подвыражения.
(defun UNION- (x y) (let ( (a-x (CAR x)) (d-x (CDR x)) ) (COND ((NULL x) y) ((MEMBER a-x y) (UNION d-x y) ) (T (CONS a-x (UNION d-x y)) ) ) ))
Пример 8.1.
(html, txt)
Обычно переменная считается связанной в области действия лямбда-конструктора функции, который связывает переменную внутри тела определения функции методом размещения пары из имени и значения в начале ассоциативного списка (а-списка).
В том случае, когда переменная всегда имеет определенное значение независимо от текущего состояния а-списка, она будет называться константой. Такую неизменяемую связь можно установить, размещая пару (a . v) в конец a-списка. Но в реальных системах это организовано с помощью так называемого списка свойств атома, являющегося представлением переменной. Каждый атом имеет свой список свойств (property list - р-список), доступный через хэш-таблицу идентификаторов, что работает эффективнее, чем a-список. С каждым атомом связана специальная структура данных, в которой размещается имя атома, его значение, определение функции, представляемой этим же атомом, и список произвольных свойств, помеченных индикаторами. При вычислении переменных EVAL исследует эту структуру до поиска в а-списке. Такое устройство констант не позволяет им служить переменными в а-списке.
Глобальные переменные реализованы аналогично, но их значение можно изменять с помощью специальной функции SET.
Особый интерес представляет тип констант, которые всегда означают себя – Nil и T, примеры таких констант. Такие константы как T, Nil и другие самоопределимые константы (числа, строки) не могут использоваться в качестве переменных. Числа и строки не имеют списка свойств.
Ситуация, когда атом обозначает функцию, реализационно подобна той, в которой атом обозначает аргумент. Если функция рекурсивна, то ей надо дать имя. Это делается связыванием названия с определением функции в ассоциативном списке. Название связано с определением функции точно также, как переменная связана со своим значением.
На практике связывание в ассоциативном списке для функций используется редко. Удобнее связывать название с определением другим способом - размещением определения функции в списке свойств атома, символизирующего ее название. Выполняет это псевдо-функция DEFUN, описанная в начале этого параграфа. Когда APPLY интерпретирует функцию, представленную атомом, она исследует р-список до исследования текущего состояния а-списка.
Тот факт, что большинство функций - константы, определенные программистом, а не переменные, изменяемые программой, происходит отнюдь не вследствие какого-либо недостатка понятий Лиспа.
Напротив, этот резерв указывает на потенциал подхода, который мы не научились использовать лучшим образом.
Некоторые функции вместо определений с помощью S-выражений закодированы как замкнутые машинные подпрограммы. Такая функция будет иметь особый индикатор в списке свойств с указателем, который позволяет интерпретатору связаться с подпрограммой. Существует три случая, в которых низкоуровневая подпрограмма может быть включена в систему:
Обычно EVAL вычисляет аргументы функций до применения к ним функций с помощью APPLY. Таким образом, если EVAL задано (CONS X Y), то сначала вычисляются X и Y, а потом работает CONS над полученными значениями. Но если EVAL задано (QOUTE X), то X не будет вычисляться. QUOTE - специальная форма, которая препятствует вычислению своих аргументов.
Специальная форма отличается от других функций двумя чертами. Ее аргументы не вычисляются до того, как специальная форма сама просмотрит свои аргументы. COND, например, имеет свой особый способ вычисления аргументов с использованием EVCON. Второе отличие от функций заключается в том, что специальные формы могут иметь неограниченное число аргументов.
Определение рекурсивной функции можно преобразовать к безымянной форме. Техника эквивалентных преобразований позволяет поддерживать целостность системы функций втягиванием безымянных вспомогательных функций внутрь тела основного определения. Верно и обратное: любую конструкцию из лямбда-выражений можно преобразовать в систему отдельных функций. Техника функциональных определений и их преобразований позволяет рассматривать решение задачи с естественной степенью подробности, гибкости и мобильности.
Специальная функция FUNCTION обеспечивает доступ к функциональному объекту, а функция FUNCALL обеспечивает применение функции к произвольному числу ее аргументов.
(funcall f a1 a2 ... ) = (apply f (list a1 a2 ...))
Разрастание числа функций, манипулирующих функциями, связано с реализационным различием структурного представления данных и представляемых ими функций.
defun UNION-
( defun UNION- (x y) (let ( (a-x (CAR x))(d-x (CDR x)) )
(COND ((NULL x) y)
((MEMBER a-x y) (UNION d-x y) )
(T (CONS a-x (UNION d-x y)) ) ) ))
NULL x) y)
| (defun UNION- (x y) (let ( (a-x (CAR x)) (d-x (CDR x)) ) (COND (( NULL x) y) ((MEMBER a-x y) (UNION d-x y) ) (T (CONS a-x (UNION d-x y)) ) ) )) |
| Пример 8.1. |
| Закрыть окно |
Пример (CAR '(A B))
| (CAR '(A B)) = (CAR (QUOTE(A B))) |
| Пример 8.2. |
| Закрыть окно |
Пример (CONS 'A '(B . C))
| (CONS 'A '(B . C)) |
| Пример 8.3. |
| Закрыть окно |
Пример (CONS '(CAR (QUOTE (A . B)))
(CONS '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )Пример CDR (QUOTE (C . D)
| (CONS '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) ) |
| Пример 8.4. |
| Закрыть окно |
Программы для Лисп-интерпретатора.
Цель этой части - помочь на первых шагах избежать некоторых общих ошибок.(CAR '(A B)) = (CAR (QUOTE(A B)))
Пример 8.2.
(html, txt)
Функция: CAR
Аргументы: ((A B))
Значение есть A. Заметим, что интерпретатор ожидает список аргументов. Единственным аргументом для CAR является (A B). Добавочная пара скобок возникает т.к. APPLY подается список аргументов.
Можно написать (LAMBDA(X)(CAR X)) вместо просто CAR. Это корректно, но не является необходимым.
(CONS 'A '(B . C))
Пример 8.3.
(html, txt)
Функция: CONS
Аргументы: (A (B . C))
Результат (A . (B . C)) программа печати выведет как (A B . C)
(CONS '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )
Пример 8.4.
(html, txt)
Функция: CONS
Аргументы: ((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))
Значением такого вычисления будет ((CAR (QUOTE (A . B))) . (CDR (QUOTE (C . D))))
Скорее всего это отнюдь не то, что ожидал новичок. Он рассчитывал вместо (CAR (QUOTE (A . B)) получить A и ожидал (A . D) в качестве итогового значения CONS. Кроме очевидного стирания апострофов:
(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))) )
ниже приведены еще три правильных способа записи нужной формы. Первый состоит в том, что CAR и CDR части функции задаются с помощью LAMBDA в определении функции. Второй - в переносе CONS в аргументы и вычислении их с помощью EVAL при пустом а-списке. Третий - в принудительном выполнении константных действий в представлении аргументов,
((LAMBDA (X Y) (CONS (CAR X) (CDR Y))) '(A . B) '(C . D))
Функция:
(LAMBDA (X Y) (CONS (CAR X) (CDR Y)))
Аргументы:
((A . B)(C . D))
(EVAL '(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D)))) Nil)
Функция: EVAL
Аргументы:
((CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D)))) Nil)
Значением того и другого является (A . D)
((LAMBDA (X Y) (CONS (EVAL X) (EVAL Y))) '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )
Функция:
(LAMBDA (X Y) (CONS (EVAL X) (EVAL Y)))
Аргументы:
((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))
Решения этого примера показывают, что грань между функциями и данными достаточно условна - одни и те же вычисления можно осуществить при разном распределении промежуточных вычислений внутри выражения, передвигая эту грань.
| (Defconstant Атом Форма ) | Глобальная константа |
| (Defparameter Атом Форма ) | Глобальная переменная |
| (Defun Название Параметры Форма ) | Определение функции |
| (Flet ((Название Параметры Форма) … (Спецификации … Формы …)) | Вводит локальные нерекурсивные функции |
| (Labels ( (Название Параметры Форма) … (Спецификации … Формы …) ) | Вводит локальные рекурсивные функции |
Цель этой части - помочь на первых шагах избежать некоторых общих ошибок.
(CAR '(A B)) = (CAR (QUOTE(A B)))
Пример 8.2.
Функция: CAR
Аргументы: ((A B))
Значение есть A. Заметим, что интерпретатор ожидает список аргументов. Единственным аргументом для CAR является (A B). Добавочная пара скобок возникает т.к. APPLY подается список аргументов.
Можно написать (LAMBDA(X)(CAR X)) вместо просто CAR. Это корректно, но не является необходимым.
(CONS 'A '(B . C))
Пример 8.3.
Функция: CONS
Аргументы: (A (B . C))
Результат (A . (B . C)) программа печати выведет как (A B . C)
(CONS '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )
Пример 8.4.
Функция: CONS
Аргументы: ((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))
Значением такого вычисления будет ((CAR (QUOTE (A . B))) . (CDR (QUOTE (C . D))))
Скорее всего это отнюдь не то, что ожидал новичок. Он рассчитывал вместо (CAR (QUOTE (A . B)) получить A и ожидал (A . D) в качестве итогового значения CONS. Кроме очевидного стирания апострофов:
(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))) )
ниже приведены еще три правильных способа записи нужной формы. Первый состоит в том, что CAR и CDR части функции задаются с помощью LAMBDA в определении функции. Второй - в переносе CONS в аргументы и вычислении их с помощью EVAL при пустом а-списке. Третий - в принудительном выполнении константных действий в представлении аргументов,
((LAMBDA (X Y) (CONS (CAR X) (CDR Y))) '(A . B) '(C . D))
Функция:
(LAMBDA (X Y) (CONS (CAR X) (CDR Y)))
Аргументы:
((A . B)(C . D))
(EVAL '(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D)))) Nil)
Функция: EVAL
Аргументы:
((CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D)))) Nil)
Значением того и другого является (A . D)
((LAMBDA (X Y) (CONS (EVAL X) (EVAL Y))) '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )
Функция:
(LAMBDA (X Y) (CONS (EVAL X) (EVAL Y)))
Аргументы:
((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))
Решения этого примера показывают, что грань между функциями и данными достаточно условна - одни и те же вычисления можно осуществить при разном распределении промежуточных вычислений внутри выражения, передвигая эту грань.
| (Defconstant Атом Форма ) | Глобальная константа |
| (Defparameter Атом Форма ) | Глобальная переменная |
| (Defun Название Параметры Форма ) | Определение функции |
| (Flet ((Название Параметры Форма) … (Спецификации … Формы …)) | Вводит локальные нерекурсивные функции |
| (Labels ( (Название Параметры Форма) … (Спецификации … Формы …) ) | Вводит локальные рекурсивные функции |
Чтобы выполнить вычисление на реальном
Введение в программирование на Лиспе
defun ряд_цел
( defun ряд_цел (M N) (cond ((> M N) Nil)(T(cons M (ряд_цел (1+ M) N)))))
(defun сумма (X) (cond ((= X 0) 0)
(T (+ (car X)( сумма (cdr X))))) )
с последующим их суммированием. Обычная
| (defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M (ряд_цел (1+ M) N))))) (defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( сумма (cdr X))))) ) |
| Пример 9.1. Построение ряда целых от M до N с последующим их суммированием. Обычная формула: |
| Закрыть окно |
Функция над целыми, начиная
| (defun цел (M) (cons M ( || (цел (1+ M) )))) |
| Пример 9.2. Функция над целыми, начиная с М: |
| Закрыть окно |
в которой возможно данное
(Defun super () ; Внешний уровень – обработчик внутренних событий(catch 'abort ; Имя обрабатваемого внутреннего события
(sub) ; Вызов формы, в которой возможно данное событие
(print "It is impossible") ; Реакция на событие
) )
(Defun sub () ; Внутренний уровень
(throw 'abort 99) ; Вызов события
)
(super) ; Вызов формы, контролирующей внутренние события.
в которой возможно данное событие
| (Defun super () ; Внешний уровень – обработчик внутренних событий (catch 'abort ; Имя обрабатваемого внутреннего события (sub) ; Вызов формы, в которой возможно данное событие (print "It is impossible") ; Реакция на событие ) ) (Defun sub () ; Внутренний уровень (throw 'abort 99) ; Вызов события ) (super) ; Вызов формы, контролирующей внутренние события. |
| Пример 9.3. Обработка событий при взаимодействии функций |
| Закрыть окно |
Работа с событиями
Наиболее общая модель организации процессов сводится к определению реакций на происходящие события. Событий конечное число. Работа с событиями в системе Clisp обеспечивается парой функций:Throw – вызов события.
Catch – обработка события (реакция на событие).
Процесс с событиями проиллюстрирован следующим примером Грехема [ 10 ] как взаимодействие функций, работающих на разных уровнях:
(Defun super () ; Внешний уровень – обработчик внутренних событий (catch 'abort ; Имя обрабатваемого внутреннего события (sub) ; Вызов формы, в которой возможно данное событие (print "It is impossible") ; Реакция на событие ) ) (Defun sub () ; Внутренний уровень (throw 'abort 99) ; Вызов события ) (super) ; Вызов формы, контролирующей внутренние события.
Пример 9.3. Обработка событий при взаимодействии функций (html, txt)
| (And Форма … ) | Вычисляет формы, пока не наткнетсяя на Nil |
| (Case Значение ( Ключ Форма) … ) | По значению, совпадающему с Ключем, выбирает форму, которую вычисляет |
| (Catch Атом Форма …) | Работает в паре с throw. Устанавливает ловушку, идентифицируемую Атомом внутри Форм. |
| (Cond (Предикат Форма) … ) | Ветвление |
| (If Предикат Да-форма Нет-форма ) | Обычное условное выражение |
| (Or Форма … ) | Вычисляет формы , пока не найдет отличную от Nil/ |
| (Throw Атом Форма ) | Работает в паре с Catch. Форма задает реакцию на обнаруженную ловушку Атом. |
| (Unless Предикат Форма … ) | Вычисляет формы если предикат имеет значение Nil |
| (When Предикат Форма … ) | Вычисляет формы при истином значении предиката. |
Замедленные вычисления могут быть результативнее
Замедленные вычисления (lazy evaluation)
Интуитивное представление о вычислении выражений, согласно которому функция применяется к заранее вычисленным аргументам, не всегда гарантирует получение результата. Ради полноты вычислений, гибкости программ и результативности процессов такое представление можно расширить и ввести категорию специальных функций, которые "сами знают", когда и что из их аргументов следует вычислить. Примеры таких функций - специальные функции QUOTE и COND, которые могут анализировать и варьировать условия, при которых вычисление необходимо. Такие функции манипулируют данными, представляющими выражения, и явно определяют в программах позиции обращения к интерпретатору.Источником неэффективности стандартных "прямолинейных" вычислений может быть целостность больших сложных данных, избыточное вычисление бесполезных выражений, синхронизация формально независимых действий. Такую неэффективность можно смягчить простыми методами замедленных вычислений (lazy evaluation). Необходимо лишь вести учет дополнительных условий для их фактического выполнения, таких как востребованность результата вычислений. Такие соображения по обработке параметров функций называют "вызов по необходимости".
Любое большое сложное данное можно вычислять "по частям". Вместо вычисления списка
(x1 x2 x3 ... )
можно вычислить x1 и построить структуру
(x1 (рецепт вычисления остальных элементов))
Получается принципиальная экономия памяти ценой незначительного расхода времени на вспомогательное построение. Рецепт - это ссылка на уже существующую программу, связанную с контекстом ее исполнения, т.е. с состоянием ассоциативного списка в момент построения рецепта.
(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M (ряд_цел (1+ M) N))))) (defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( сумма (cdr X))))) )
Пример 9.1. Построение ряда целых от M до N с последующим их суммированием. Обычная формула: (html, txt)
Введем специальные операции || - приостановка вычислений и @ - возобновление ранее отложенных вычислений.
Приостановка сводится к запоминанию символьного представления программы, которая временно не вычисляется, но можно вернуться к ее вычислению с помощью операции возобновления. Отложенная программа преобразуется в так называемый рецепт вычисления, который можно хранить как данное и выполнять в любой момент.
В рецепте хранится не только вычисляемая форма, но и контекст, в котором первоначально было предусмотрено ее вычисление. Таким образом, гарантируется, что переход от обычной программы к программе с отложенными действиями не нарушает общий результат.
Избежать целостного представления большого и возможно бесконечного ряда чисел можно небольшим изменением формулы, отложив вычисление второго аргумента CONS "до лучших времен" – когда его значение действительно понадобится более внешней функции:
(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M ( || (ряд_цел (1+ M) N))))))
(defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( @ ( сумма (cdr X))))) ))
Можно исключить повторное вычисление совпадающих рецептов. Для этого во внутренне представление рецепта вводится флаг, имеющий значение T - истина для уже выполненных рецептов, Nil - ложь для невыполненных.
Таким образом рецепт имеет вид (Nil e AL ) или ( T X ), где X = (eval e AL ) для произвольного e, в зависимости от того, понадобилось ли уже значение рецепта или еще не было в нем необходимости.
Это заодно дает возможность понятие данных распространить на бесконечные множества. Вместо привычного оперирования отрезками целых, не превосходящий заданное число М, можно манипулировать рядом целых, превосходящих M.
(defun цел (M) (cons M ( || (цел (1+ M) ))))
Пример 9.2. Функция над целыми, начиная с М: (html, txt)
Можно из таким образом организованного списка выбирать нужное количество элементов, например, первые K элементов можно получить по формуле:
(defun первые (K Int) (cond ((= Int Nil) Nil) ((= K 0) Nil) (T (cons (car Int)( первые ( @ (cdr Int))) )) ))
Формально эффект таких приостанавливаемых и возобновляемых вычислений получается следующей реализацией операций || и @:
||e = > (lambda () e ) @e = > (e ),
что при интерпретации дает связывание функционального аргумента с ассоциативным списком для операции || - приостановка и вызов функции EVAL для операции @ - возобновление вычислений.
Обычно в языках программирования различают вызовы по значению, по имени, по ссылке. Техника приостановки и возобновления функций может быть названа вызовом по необходимости.
При небольшом числе значений заданного типа, например, для истиностных значений, возможны вычисления с вариантами значений с последующим выбором реальной альтернативы пользователем, но это удобнее обсудить позднее, при изучении вариантов и недетерминированных вычислений.
Техника замедленных вычислений позволяет выполнять декомпозицию программы на обязательно выполнимые и возможно невыполнимые действия. Выполнимые действия в тексте определения замещаются на их результат, а невыполнимые преобразуются в остаточные, которые будут выполнены по мере появления дополнительной информации.
Многие выражения по смыслу используемых в них операций иногда определены при частичной определенности их операндов, что часто используется при оптимизации кода программ (умножение на 0, разность или частное от деления совпадающих форм и т.п.)
Отложенные действия - естественный механизм управления заданиями в операционных системах, а также программирования асинхронных и параллельных процессов.
Введение в программирование на Лиспе
Деструктивные (разрушающие) операции
Идеальный Лисп универсален в смысле теории вычислимых функций от символьных выражений. Но для практичности системы программирования Лиспу требуется дополнительный инструмент, увеличивающий выразительную силу и эффективность языка.В частности, идеальный Лисп не имеет возможности модифицировать структуру списка. Единственная базисная функция, влияющая на структуру списка - это cons, а она не изменяет существующие списки, а создает все новые и новые. Функции, описанные в чистом Лиспе, такие как subst, в действительности не модифицируют свои аргументы, но делают модифицированную копию оригинала.
Идеальный Лисп работает как расширяемая система, в которой информация как бы никогда не пропадает. Set внутри Prog лишь формально смягчает это свойство, сохраняя ассоциативный список и моделируя присваивания теми же CONS.
Теперь же Лисп обобщается с точки зрения структуры списка добавлением разрушающих средств - деструктивных базисных операций над списками rplaca и rplacd. Эти операции могут применяться для замены адреса или декремента любого узла в списке подобно стандартным присваиваниям. Они используются ради их воздействия на память и относятся к категории псевдо-функций.
(rplaca x y) заменяет адресную часть x на y. Ее значение - x, но x, отличное от того, что было раньше. На языке значений rplaca можно описать равенством
(rplaca x y) = (cons y (cdr x))
Но действие совершенно различно: никакие cons не вызываются и новые слова не создаются.
(rplacd x y) заменяет декремент x на y.
Деструктивные операции должно применять с осторожностью! Они могут совершенно преобразить существующие определения и основную память. Их применение может породить циклические списки, возможно, влекущие бесконечную печать или выглядящие бесконечными для таких функций как equal и subst.
Такие функции используются при реализации списков свойств атома и ряда эффективных, но небезопасных, функций Clisp-а, таких как nconc, mapc и т.п.
Для примера вернемся к функции grp. Это преобразующая список функция, которая преобразует копию своего аргумента, реорганизуя подструктуру
в структуру из тех же атомов:
Выше приведенное определение функции делает это созданием новой структуры и использует для этого четыре cons. Из-за того, что в оригинале только три слова, по крайней мере один cons необходим, а grp можно переписать с помощью rplaca и rplacd.
Изменение состоит в следующем:
Пусть новое машинное слово строится как (cons (cadr x) (cddr x)) . Тогда указатель на него заготавливает форма:
(rplaca (cdr x) (cons (cadr x) (cddr x)))
Другое изменение состоит из удаления указателя из второго слова на третье. Оно делается как (rplaca (cdr x) NIL).
Новое определение функции pgrp можно определить как соотношение:
(pgrp x)=(rplacd(rplaca(cdr x)(cons(cadr x)(cddr )x)))NIL)
Функция pgrp используется в сущности ради ее действия. Ее значением, неиспользуемым, является подструктура ((B C)). Поэтому необходимо, чтобы pgrp выполнялось, а ее значение игнорировалось.
Расширенный деструктивными функциями Лисп хорошо приспособлен к оптимизации программ. Любые совпадающие подвыражения можно локализовать и вынести за скобки.
"Сборка мусора" - повторное распределение памяти
Самым интересным, можно сказать революционным, механизмом работы с памятью в Лиспе бесспорно явилась "сборка мусора". С начала 60-ых годов методам такой работы посвящены многочисленные исследования, продолжающиеся до наших дней и сильно активизировавшиеся в связи с включением похожего механизма в реализацию языка Java.Общая идея всех таких методов достаточно проста:
Специальная программа "сборка мусора" выполняет анализ достижимости всех блоков памяти просто пометкой узлов, видимых из конечного числа рабочих регистров системы программирования. К таким регистрам относятся промежуточные результаты вычислений, активная часть стека, ассоциативный список, таблица атомов и др. После пометки все непомеченные узлы объединяются в список свободной памяти, передающий их для повторного использования новым вызовам функции CONS. Такая автоматизация не лишена недостатков, но они обнаруживаются лишь в сравнительно сложных процессах, требования которых мы сейчас сознательно не рассматриваем.
| (Gensym ) | Создает новый уникальный атом |
| (Get Атом Индикатор) | Выдает адрес свойства Атома, помеченного заданным Индикатором. |
| (Set Форма Данное ) | Устанавливает значение переменной, одноименной с атомом, полученным при вычислении Формы. |
| Setf | |
| (Setq Атом Данное ) | Устанавливает значение Атома-переменной |
| Symbol-function | |
| Symbol-plist | |
| Symbol-value | |
| Remprop | |
| (Nconc Список … ) | Сцепляет списки без копирования, т.е. заменяя последний Nil очередного списка на указатель следующего списка. |
| (Rplaca Пара Объект ) | Заменяет левый элемент Пары на Объект. |
| (Rplacd Пара Объект ) | Заменяет правый элемент Пары на Объект. |
Списки свойств атомов
До сих пор атом рассматривался как уникальный указатель, обеспечивающий быстрое выяснение различимости имен, названий или символов. В настоящем разделе описываются списки свойств, начинающиеся в указанных ячейках. (Образно говоря, переходим от химии к физике.)Каждый атом имеет список свойств. Как только атом появляется (вводится) впервые, так сразу для него создается список свойств. Список свойств характеризуется специальной структурой, подобной записям в Паскале, но поля в такой записи сопровождаются индикаторами, символизирующими смысл или назначение хранимой информации. Первый элемент этой структуры расположен по адресу, который задан в указателе атома. Остальные элементы доступны по этому же указателю с помощью ряда специальных функций. Элементы структуры содержат различные свойства атома. Каждое свойство помечается атомом, называемым индикатором, или расположено в фиксированном поле структуры.
Согласно стандарту Common Lisp глобальные значения переменных и определения функций хранятся в фиксированных полях структуры атома. Они доступны с помощью специальных функций symbol-value и symbol-function соответственно. Полный список свойств можно получить функцией symbol-plist. Функция remprop в Clisp удаляет первое вхождение заданного индикатором свойства атома. Новое свойство атома можно ввести формой вида:
(setf (get Атом Индикатор ) Свойство)
Числа представляются в Лиспе как специальный тип атома без списка свойств. Атом такого типа состоит из указателя с тэгом, специфицирующим слово как число, тип числа (целые, дробные, вещественные), и адрес собственно числа, код которого может быть произвольной длины. В отличие от обычного атома одинаковые числа не совмещаются при хранении
| (get Атом Индикатор ) | Дает адрес свойства атома, соответсвующее индикатору |
| (remprop атом индикатор) | удаляет первое вхождение заданного индикатором свойства атома |
| (setf адрес свойство) | Размещает новое значение свойства по заданному адресу |
| (symbol-function атом) | Выдает определение функции |
| (symbol-plist атом) | Список всех свойств атома |
| (symbol-value атом) | глобальное значение переменной |
Структура списков и памяти
До этого момента списки рассматривались на уровне текстового диалога человека с Лисп-системой. В настоящем разделе рассматривается кодовое представление списков внутри памяти машины и механизм "сборки мусора", обеспечивающий повторное использование памяти.В памяти машины списки хранятся не как последовательности символов, а в виде структурных форм, построенных из машинных слов как частей деревьев, подобно записям в Паскале при реализации односвязных списков. Адреса в таких записях сопровождаются так называемыми тегами, специфицирующими тип данного, расположенного по указателю. При схематичном изображении структуры списка в виде диаграммы машинное слово рисуется как прямоугольник, разделенный на две части: адрес и декремент.
Теперь можно дать правило представления S-выражений в машине. Представление атомов будет пояснено ниже.
Преимущества структур списков для хранения S -выражений в памяти:
Для примера рассмотрим типичную двухуровневую структуру (A (B C)).
Она может быть построена из A, B и C с помощью
(cons 'A (cons (cons 'B(cons 'C NIL))NIL))
или, используя функцию list,1) можно то же самое записать как
(list 'A (list 'B 'C))
Если дан список x из трех атомов x = (A B C), то аргументы A, B и C, используемые в предыдущем построении, можно найти как
A = (car x) B = (cadr x) C = (caddr x)
Исходную структуру из такого списка можно получить функцией grp, строящей (X (Y Z)) из списка вида (X Y Z).
(grp x)=(list(car x)(list(cadr x)(caddr x)))
Здесь grp применяется к списку X в предположении, что он заданного вида.
Списки свойств атомов обеспечивают прямой
Введение в программирование на Лиспе
Циклы
Работа с циклами обеспечена в Лиспе достаточно традиционно.(loop <форма>...)
Базовая форма цикла, представляющая собой встроенную функцию, многократно вычисляющую свои аргументы – тело цикла – до тех пор, пока на будет выполнен какой-либо явный выход из цикла, такой как RETURN.
(do(<параметры>...)(<предикат > < результат >...) < форма >...) (do*(<параметры >...)(<предикат > < результат >...) < форма >...)
Обобщенные формы цикла, отличающиеся правилом связывания параметров цикла – независимо и последовательно.
(dolist (<переменная > < список > [<результат >] ) < форма >...)
Цикл, перебирающий список выражений, поочередно присваиваемых переменной цикла.
(dotimes (<переменная > < число > [<результат >] ) < форма >...)
Цикл, работающий заданное число шагов от 0 до N-1
< параметры > задаются как списки вида
(<переменная> <начальное_значение> [<шаг>] ) в котором: < переменная > - символ с исходным значением Nil. < начальное_значение > - начальное значение параметра. < шаг > - выражение для вычисления параметра на каждом шаге цикла <предикат> - ограничитель цикла <результат> - результирующее выражение (при отсутствии - NIL) <форма> - тело цикла, работает как неяная форма prog.
Значение дает последнее результирующее выражение.
Императивное программирование
Противопоставление функционального и императивного (операторно-процедурного) стилей программирования порой напоминает свифтовские бои остроконечников с тупоконечниками. Впрочем, переписать функциональную программу в императивную проще, чем наоборот.С практической точки зрения любые конструкции стандартных языков программирования могут быть введены как функции. Это делает их вполне легальными средствами в рамках функционального подхода. Надо лишь четко уяснить цену такого дополнения и его преимущества, обычно связанные с наследованием решений или с привлечением пользователей. В первых реализациях Лиспа были сразу предложены специальные формы и структуры данных, служащие мостом между разными стилями программирования. Они заодно смягчали на практике недостатки упрощенной схемы интерпретации S-выражений, выстроенной для учебных и исследовательских целей. Важнейшие средства такого рода, выдержавшее испытание временем, - prog-форма, списки свойств атома и деструктивные операции. В результате язык программирования расширяется так, что становятся возможными оптимизирующие преобразования структур данных, программ и процессов и раскрутка систем программирования.
и все подсписки, столь же
| Пример 11.1. Функция REV, обращающая список и все подсписки, столь же естественно пишется с помощью рекурсивной Prog-формы. |
| Закрыть окно |
Пример (setq x 'y)
(setq x 'y)(set x 'NEW)
(print x)
(print y)
Побочный эффект присваиваний
| (setq x 'y) (set x 'NEW) (print x) (print y) |
| Пример 11.2. Побочный эффект присваиваний с вычисляемой левой частью |
| Закрыть окно |
явный выход из цикла при
(defun first-a (la);; самый левый атом
(setq x la)
(loop
(setq x (car x)) ; левый элемент структуры
(cond ((atom x)(return x)) )
; явный выход из цикла при обнаружении атома
) )
(print (first-a '(((123) 46) 5) ))
явный выход из цикла при
|
(defun first-a (la) ;; самый левый атом (setq x la) (loop (setq x (car x)) ; левый элемент структуры (cond ((atom x)(return x)) ) ; явный выход из цикла при обнаружении атома ) ) (print (first-a '(((123) 46) 5) )) |
| Пример 11.3. Выбор самого левого атома из произвольной структуры данных |
| Закрыть окно |
выход из цикла при пустом
(defun len-do (ld);; длина списка
(do
((x ld (cdr x)); на каждом шаге переход к хвосту списка
(N 0 (1+ N))) ; подсчет числа шагов
((null x) N)) ; выход из цикла при пустом списке
)
(print (len-do '(1 2 3 4 5)))
выход из цикла при пустом
|
(defun len-do (ld) ;; длина списка (do ((x ld (cdr x)); на каждом шаге переход к хвосту списка (N 0 (1+ N))) ; подсчет числа шагов ((null x) N)) ; выход из цикла при пустом списке ) (print (len-do '(1 2 3 4 5))) |
| Пример 11.4. Вычисление длины списка |
| Закрыть окно |
el lp rl)
(defun list-pa (lp)(setq rl nil)
(dolist
( el lp rl) ; параметры перебора и результат
(setq rl (cons (cons el el) rl))
))
(print (list-pa '(a b c d))) ; = ((A . A)(B . B)(C . C)(D . D))
setq rl nil)
|
(defun list-pa (lp) ( setq rl nil) (dolist (el lp rl) ; параметры перебора и результат (setq rl (cons (cons el el) rl)) )) (print (list-pa '(a b c d))) ; = ((A . A)(B . B)(C . C)(D . D)) |
| Пример 11.5. |
| Закрыть окно |
setq bl ln)
(defun ind-n (ln n)( setq bl ln)
(setq ind nil)
(dotimes (i n ind)
(setq ind (cons (- n i) (cons (car bl ) ind )))
(setq bl (cdr bl))
))
(print (ind-n '(a b c d e f g) 4)) ; = D
Индексный выбор элемента из
| (defun ind-n (ln n) (setq bl ln) (setq ind nil) (dotimes (i n ind) (setq ind (cons (- n i) (cons (car bl ) ind ))) (setq bl (cdr bl)) )) (print (ind-n '(a b c d e f g) 4)) ; = D |
| Пример 11.6. Индексный выбор элемента из списка |
| Закрыть окно |
Примеры программ с циклами
(defun first-a (la) ;; самый левый атом (setq x la) (loop (setq x (car x)) ; левый элемент структуры (cond ((atom x)(return x)) ) ; явный выход из цикла при обнаружении атома ) )(print (first-a '(((123) 46) 5) ))
Пример 11.3. Выбор самого левого атома из произвольной структуры данных (html, txt)
(defun len-do (ld) ;; длина списка (do ((x ld (cdr x)); на каждом шаге переход к хвосту списка (N 0 (1+ N))) ; подсчет числа шагов ((null x) N)) ; выход из цикла при пустом списке )
(print (len-do '(1 2 3 4 5)))
Пример 11.4. Вычисление длины списка (html, txt)
(defun list-pa (lp) (setq rl nil) (dolist (el lp rl) ; параметры перебора и результат (setq rl (cons (cons el el) rl)) ))
(print (list-pa '(a b c d))) ; = ((A . A)(B . B)(C . C)(D . D))
Пример 11.5.
(html, txt)
(defun ind-n (ln n) (setq bl ln) (setq ind nil) (dotimes (i n ind) (setq ind (cons (- n i) (cons (car bl ) ind ))) (setq bl (cdr bl)) )) (print (ind-n '(a b c d e f g) 4)) ; = D
Пример 11.6. Индексный выбор элемента из списка (html, txt)
| (Go Атом ) | Безусловный переход на оператор, помеченный Атомом |
| (Prog Атомы-или-Формы …) | Вычисляет последовательность форм в императивном стиле |
| (Prog1 Форма …) | Вычисляет формы, формальный результат – значение первой из них. |
| (Prog2 Форма …) | Вычисляет формы, формальный результат – значение второй из них. |
| (Progn Форма …) | Вычисляет формы, формальный результат – значение последней из них. |
| (Return Форма ) | Результат и завершение формы Prog |
| (Do (var ...) ( expr rez ...) expr ...) | Цикл с последовательным заданием параметров и выходом по заданному условию |
| (Do* (var ...) ( expr rez ...) expr ...) | Цикл с параллельным заданием параметров и выходом по заданному условию |
| (Dolist (var list [rez] ) expr ...) | Цикл перебора значений параметра из списка |
| (Dotimes (var number [rez] ) expr ...) | Цикл, работающий заданное число раз |
| (Loop expr ...) | Цикл работающий до внутреннего Return |
Присваивания
Для присваивания переменной применяется форма SET. Чтобы присвоить переменной pi значение 3.14 пишется:(SET (QUOTE PI)3.14)
SETQ подобна SET, но она еще и блокирует вычисление первого аргумента. Поэтому
(SETQ PI 3.14)
запись того же присваивания. SETQ обычно удобнее. SET и SETQ могут изменять значения любых переменных из ассоциативного списка более внешних функций. Значением SET и SETQ является значение их второго аргумента.
GO-форма, используемая для указания перехода (GO A) указывает, что программа продолжается оператором, помеченным атомом A, причем это A может быть и из более внешнего prog.
Условные выражения в качестве операторов программы обладают полезными особенностями. Если ни один из предикатов не истинен, то программа продолжается оператором, следующим за условным выражением.
RETURN - нормальное завершение программы. Аргумент return вычисляется, что и является значением программы. Никакие последующие операторы не вычисляются.
Если программа прошла все свои операторы, не встретив Return, она завершается со значением NIL.
Но в современных версиях Лиспа их можно встретить и в других позициях.)
Атомы, выполняющие роль меток, работают как указатели помеченного блока.
Кроме того произошло уточнение механизма условных выражений, - отсутствие истинного предиката не препятствует формированию значения cond-оператора, т.к. все операторы игнорируют выработанное значение. Это позволяет считать, что при отсутствии истинного предиката значением условного выражения является Nil. Такое доопределение условного выражения давно перекочевало и в области обычных функций, где часто дает компактные формулы для рекурсии по списку. Исчезает необходимость в ветви вида "(T NIL)" .
В принципе SET и SETQ могут быть реализованы с помощью a-списка примерно также как и доступ к значению аргумента, только с копированием связей, расположенных ранее изменяемой переменной (см. функцию assign из параграфа 4). Более эффективная реализация, на основе списков свойств, будет описана ниже.
(DEFUN set (x y) (assign x y Alist))
Обратите внимание, что введенное таким образом присваивание работает разнообразнее, чем традиционное присваивание: допущена вычисляемость левой части присваивания, т.е. можно в программе вычислять имена переменных, значение которых предстоит поменять.
(setq x 'y) (set x 'NEW) (print x) (print y)
Пример 11.2. Побочный эффект присваиваний с вычисляемой левой частью
Напечатается Y и NEW.
Prog-форма
Рассмотрим предложенный МакКарти пример,1) показывающий возможности prog-формы при императивном стиле определения функции Length. Эта функция сканирует список и вычисляет число элементов на верхнем уровне списка. Значение функции Length - целое число. Алгоритм можно описать следующими словами:"Это функция одного аргумента L. Она реализуется программой с двумя рабочими переменными z и v. Записать число 0 в v. Записать аргумент L в z. A: Если z содержит NIL, то программа выполнена и значением является то, что сейчас записано в v. Записать в z cdr от того, что сейчас в z. Записать в v на единицу больше того, что сейчас записано в v. Перейти к A"
Эту программу можно записать в виде Паскаль-программы с несколькими подходящими типами данных и функциями. Строкам вышеописанной программы соответствуют строки определения функции LENGTH, в предположении, что существует библиотека Лисп-функций на Паскале:
function LENGTH (L: list) : integer;
var Z: list; V: integer; begin V := 0; Z := l; A: if null (Z) then LENGTH := V; Z := cdr (Z); V := V+1; goto A; end;
Переписывая в виде S -выражения, получаем программу:
(defun LENGTH (lambda (L) (prog (Z V) (setq V 0) (setq Z L) A (cond ((null Z)(return V))) (setq Z (cdr Z)) (setq V (+ 1 V)) (go A) ))) ))
;;=======================ТЕСТЫ============= (LENGTH '(A B C D)) (LENGTH '((X . Y) A CAR (N B) (X Y Z)))
Последние две строки содержат тесты. Их значения 4 и 5 соответственно.
Форма Prog имеет структуру, подобную определениям функций и процедур в Паскале: (PROG, список рабочих переменных, последовательность операторов и атомов ... ) Атом в последовательности выполняет роль метки, локализующей оператор, расположенный вслед за ним. В вышеприведенном примере метка A локализует оператор, начинающийся с "COND".
Первый список после символа PROG называется списком рабочих переменных. При отсутствии таковых должно быть написано NIL или (). С рабочими переменными обращаются примерно как со связанными переменными, но они не могут быть связаны ни с какими значениями через lambda. Значение каждой рабочей переменной есть NIL, до тех пор, пока ей не будет присвоено что-нибудь другое.
При реализации языка программирования происходит
Введение в программирование на Лиспе
Функциональное программирования
Стиль разработки программ на Лиспе получил название "функциональное программирование" (ФП). Основные положения этого стиля восприняты многими языками программирования с общей логикой уточнения решаемых задач и обобщения решений на основе выбранных специально базовых конструкций:Отправляясь от однозначных функций, в Lisp-е обеспечено предельно широкое толкование понятия "значение", объединяющее понятия "структура данных" и "функция":
Конструирование функций средствами чистого Лиспа доставляет интеллектуальное удовольствие, оно сродни решению математических головоломок. В этом исключительно мощном языке не только реализованы основные средства, обеспечившие практичность и результативность функционального программирования, но и впервые опробован целый ряд поразительно точных построений, ценных как концептуально, так и методически и конструктивно, понимание и осмысление которых слишком отстает от практики применения.
Понятийно-функциональный потенциал языка Lisp 1.5 в значительной мере унаследован стандартом Common Lisp, но не все идеи получили достойное развитие. Возможно это дело будущего - для нового поколения системных программистов, но это уже другая история.
По мере накопления опыта реализации Лиспа и других языков сформированы обширные библиотеки функций, весьма эффективно поддерживающих обработку основных структур данных - списков, векторов, множеств, хэш-таблиц, а также строк, файлов, директорий, гипертекстов, изображений. Существенно повысилась результативность системных решений в области работы с памятью, компиляцией, манипулирования пакетами функций и классами объектов. Все это доступно в современных системах, таких как GNU Clisp, Python, CMUCL и др., основная проблема при изучении которых – слишком много всего, разбегаются глаза, трудно выбрать первоочередное. Все это превращает любой диалект Лиспа в практичный инструментарий, обладающий интересными перспективами.
Результативность идей Лиспа подтверждена самой историей развития его диалектов и родственных ему языков программирования. (Pure Lisp, Lisp 1.5, Lisp 2, Interlisp, CommonLisp, MicroLisp, MuLisp, Sail, Hope, Miranda, Scheem, ML, GNU Clisp, CLOS, Emacs, Elisp, xLisp, Vlisp, AutoLisp, Haskell, Python, CMUCL). Стандарт Common Lisp в сравнении с Лиспом от МакКарти имеет ряд отличий, несколько влияющих на программотехнику. GNU Clisp, xLisp, CMUCL соответствуют стандарту Common Lisp.
Продуманность и методическая обоснованность первых реализаций Лиспа позволила быстро накопить опыт решения новых задач, подготовить их для прикладного и теоретического программирования. В настоящее время существуют сотни диалектов Lisp-а и языков функционального программирования на базе Lisp-а, ориентированных на разные классы задач и виды технических средств.
Идеи Лиспа выдержали многолетнюю шлифовку и заслужили достойную оценку специалистов и любителей. Универсальность Лиспа достаточна для моделирования любого стиля программирования.
Выразительная сила Лиспа обретает новое дыхание на каждом эволюционном витке развития информационных технологий. Потенциал Лиспа нам еще предстоит раскрыть. Стилистика Лиспа несколько противоречат традиционным подходам к представлению программ. Но это противоречие отступает перед обаянием строгой логики языка. Определение Лисп-систем средствами самого Лиспа дает гибкую основу для развития языка и реализующей его системы программирования. На Лиспе решение задачи выражается в терминах постановки задачи без привлечения реализационных сущностей и интерфейсных эффектов.
Базис Лиспа идеально лаконичен - атомы и простые структуры данных –девять функций и функционалов - обычные функции, которые анализируют, строят и разбирают любые структурные значения (atom, eq, cons, car, cdr,), и специальные функционалы, которые управляют обработкой структур, представляющих вычисляемые выражения (quote, cond, lambda, eval).
Синтаксис Лиспа изысканно прост. Разделитель - пробел, ограничители - круглые скобки. В скобки заключается представление функции с ее аргументами. Все остальное - вариации в зависимости от категории функций, определенности атомов и вычислимости выражений, типов значений и структур данных. Функционалы - это одна из категорий функций, используемая при организации управления вычислениями.
Лисп - язык символьной обработки информации. Методы программирования на Лиспе часто наывают "функциональное программирование". Лисп прочно утвердился как эсперанто для задач искусственного интеллекта. К середине семидесятых годов XX века на Лиспе решались наиболее сложные в практике программирования задачи из области дискретной и вычислительной математики, экспериментального программирования, лингвистики, химии, биологии, медицины и инженерного проектирования. На Лиспе реализована AutoCAD - система автоматизации инженерных расчетов, дизайна и комплектации изделий из доступного конструктива, и Emacs – весьма популярный текстовый редактор в мире UNIX/Linux. Многие созревшие на базе Лиспа системные решения постепенно обрели самостоятельность и выделились в отдельные направления и технологии.
Реализационные находки Лиспа, такие как ссылочная организация памяти, "сборка мусора" - автоматизация повторного использования памяти, частичная компиляция программ с интерпретацией промежуточного кода, длительное хранение атрибутов объектов в период их использования и др., перекочевали из области исследований и экспериментов на базе Лиспа в практику реализации операционных систем и систем программирования.
Приверженцы Лиспа ценят его не только за элегантность, гибкость, но и за способность к точному представлению программистских идей и удобной отладке. В стандартных языках программирования принята императивная организация вычислений по принципу немедленного выполнения каждой очередной команды. Это не всегда обосновано и эффективно. Неимперативные модели управления процессами позволяют прерывать и откладывать процессы, а потом их восстанавливать и запускать или отменять, что обеспечено в Лиспе средствами конструирования функций, блокировки вычислений и их явного выполнения.
История Лиспа пронизана жаркими спорами, притиворечивыми суждениями, яркими достижениями и смелыми изобретениями:
1958 - Первые публикации Джона Мак-Карти о замысле языка символьной обработки.
1962-1964 - Авторские проекты первых Лисп-систем .
1964 - Демонстрация принципиальной решаемости проблем искусственного интеллекта. (Написанная Дж.Вейценбаумом на Лиспе программа-собеседник "Элиза", имитирующая речевое поведение психоаналитика, дала положительный ответ на вопрос о возможности искусственного разума.)
1972-1974 - Разрешение теоретических парадоксов, связанных с бестиповым лямбда-исчислением.
1972-1980 - Стандартизация языка Лисп.
1978 – Появление Лисп-компьютеров.
1965-1990 - Построение специализированных диалектов Лиспа и создание практичных реализаций для широкого спектра весьма различных применений, включая инженерное проектирование и системы математической обработки информации
1992-2002 - Разработка визуальных и сверхэффективных Лисп-систем, таких как CMUCL.
В нашей стране программирование знакомство с языком Лисп состоялось из первых рук.В конце 1968 года Джон Мак-Карти лично познакомил программистов Москвы и Новосибирска с Лиспом, что побудило к реализации отечественных версий языка.
В конце 1968 года Джон Мак-Карти лично познакомил программистов Москвы и Новосибирска с Лиспом, что побудило к реализации отечественных версий языка.
Практичные расширения Лиспа
Средства и методы программирования на Лиспе образуют два слоя. Глубинный слой - локальное программирование, нацеленное на определение:Внешний слой - моделирование практичных парадигм программирования и механизмов их реализации:
Естественно, работа на внешнем слое требует своей терминологии и развития понятий, отражающего расширение класса решаемых задач, повышение уровня общности и организованности решений:
Реальные Лисп-системы обеспечивают полный спектр средств работы с числами с особым вниманием к повышенной точности вычислений и длине представления числа. Средства обработки структур данных обычно позволяют работать с векторами, строками, массивами, хэш-таблицами, деревьями, последовательностями и файлами. Имеется работа с мульти-значениями, удобная при моделировании параллельных вычислений.
Строение Лисп-системы формируется как взаимодействие интерпретатора и компилятора, что позволяет гибко сочетать достоинства того и другого подходов к обработке программ. Для нужд компиляции программа дополняется спецификациями типов данных и декларациями, указывающими направление наследования определений. Имеются средства подготовки и использования встроенной документации и системной информации относительно фактического контекста вычислений. Обстановка функционирования системы регулируется механизмом пакетов, в составе которых хранятся различные варианты определений символов, включаемых в создаваемый комплект.
Так, например, пакет CLOS (Common Lisp Object System) поддерживает ООП в терминах классов, методов, суперклассов, экземпляров и семейств функций, подчиненных механизмам инкапсуляции и наследования с управляемым полиморфизмом.
Вызов Лисп-интерпретатора и/или компилятора.
Без аргументов (опций) выполняется цикл "чтение-вычисление-печать", при котором выражения читаются поочередно из стандартного потока ввода, вычисляются Лисп-интепретатором, и полученные результаты выводятся в стандартный поток вывода. Опция –c специфицирует Лисп-файлы, предназначенные для компиляции в байт-код, который выполняется более эффективно.Формат вызова Лисп-системы:
clisp [ -h ] [ -m memsize ] [ -M memfile ] [ -L language ] [ -N directory ] [ -q ] [ -I ] [ -i initfile ... ] [ -c [ -l ] lispfile [ -o outputfile ] ... ] [ -p packagename ] [ -x expression ]2)
OPTIONS
-h Показывает формат вызова Лисп-системы
-m memsize Установливает объем памяти. Для современных версий игнорируется.
-M memfile Определяет внутреннее наполнение памяти Лисп-системы. Оно должно быть создано функцией "saveinitmem".
-L language Задает язык сообщений для взаимодействия с пользователем. (английский, немецкий, французский и др.) Влияет на тексты диагностики.
-N directoryУказывает, где искать файлы с текстами сообщений.
-q Ни заставки, ни прощального текста не выдается.
-I вариант диалога в стиле ILISP (популярный интерфейс, принятый в редакторе Emacs)
-i initfile ... Специфицирует инициализирующие файлы, которые будут загружены при запуске системы. Это должны быть исходные или компилированные Лисп-файлы,
-c lispfile ... Компилирует специфицированные Лисп-файлы в байт-код. Компилированные файлы затем загружаются вместо исходных, чтобы повысить эффективность.
-o outputfile Задает файл вывода или директорию для компиляции предшествующего лисп-файла.
-l будет выполняться листинг байткода для компилируемых файлов. Полезно только для целей отладки.
-p packagename При загрузке устанавливает начальное значение переменной *package*
-x expressions Выполняет серию произвольных выражений вместо цикла "read-eval-print". Значения выражений выводятся в стандартный поток вывода. Согласно системным соглашениям выражения должны быть заключены в скобки, а двойным кавычкам и обратным чертам следует предпослать обратную черту.
@optionfile Подставляет содержимое файла как аргумент для запуска Лисп-системы. Каждая строка воспринимается как отдельный аргумент.
При работе с Лисп-системой полезны следующие возможности:
(apropos name) перечисляет символы, включающеие "name"
(exit) or (quit) or (bye) - выход из Лисп-системы
EOF (Ctrl-Z) Покидает текуций "read-eval-print" цикл
Стрелки управления курсором позволяют построчно редактировать и просматривать историю ввода текста программы.
Соглашение об именах файлов:
lisp.exe основной исполнитель
lispinit.mem исходный/начальный образ/состояние памяти
config.lsp конфигурация и настройки
*.lsp исходные тексты на Лиспе
*.fas результат компиляции – байт-код
*.lib библиотечная информация, создаваемая и испоьзуемая компилятором
*.c Си-код, компилированный по исходному Лисп-тексту
Программирование: Языки - Технологии - Разработка
- Программирование
- Технологии программирования
- Разработка программ
- Работа с данными
- Методы программирования
- IDE интерфейс
- Графический интерфейс
- Программирование интерфейсов
- Отладка программ
- Тестирование программ
- Программирование на Delphi
- Программирование в ActionScript
- Assembler
- Basic
- Pascal
- Perl
- VBA
- VRML
- XML
- Ada
- Lisp
- Python
- UML
- Форт
- Языки программирования
