Циклы
Работа с циклами обеспечена в Лиспе достаточно традиционно.
(loop <форма>...)
Базовая форма цикла, представляющая собой встроенную функцию, многократно вычисляющую свои аргументы – тело цикла – до тех пор, пока на будет выполнен какой-либо явный выход из цикла, такой как RETURN.
(do(<параметры>...)(<предикат > < результат >...) < форма >...) (do*(<параметры >...)(<предикат > < результат >...) < форма >...)
Обобщенные формы цикла, отличающиеся правилом связывания параметров цикла – независимо и последовательно.
(dolist (<переменная > < список > [<результат >] ) < форма >...)
Цикл, перебирающий список выражений, поочередно присваиваемых переменной цикла.
(dotimes (<переменная > < число > [<результат >] ) < форма >...)
Цикл, работающий заданное число шагов от 0 до N-1
< параметры > задаются как списки вида
(<переменная> <начальное_значение> [<шаг>] ) в котором: < переменная > - символ с исходным значением Nil. < начальное_значение > - начальное значение параметра. < шаг > - выражение для вычисления параметра на каждом шаге цикла <предикат> - ограничитель цикла <результат> - результирующее выражение (при отсутствии - NIL) <форма> - тело цикла, работает как неяная форма prog.
Значение дает последнее результирующее выражение.
Императивное программирование
Противопоставление функционального и императивного (операторно-процедурного) стилей программирования порой напоминает свифтовские бои остроконечников с тупоконечниками. Впрочем, переписать функциональную программу в императивную проще, чем наоборот.
С практической точки зрения любые конструкции стандартных языков программирования могут быть введены как функции. Это делает их вполне легальными средствами в рамках функционального подхода. Надо лишь четко уяснить цену такого дополнения и его преимущества, обычно связанные с наследованием решений или с привлечением пользователей. В первых реализациях Лиспа были сразу предложены специальные формы и структуры данных, служащие мостом между разными стилями программирования. Они заодно смягчали на практике недостатки упрощенной схемы интерпретации S-выражений, выстроенной для учебных и исследовательских целей. Важнейшие средства такого рода, выдержавшее испытание временем, - prog-форма, списки свойств атома и деструктивные операции. В результате язык программирования расширяется так, что становятся возможными оптимизирующие преобразования структур данных, программ и процессов и раскрутка систем программирования.
и все подсписки, столь же
|
Пример 11.1. Функция REV, обращающая список и все подсписки, столь же естественно пишется с помощью рекурсивной Prog-формы. |
| Закрыть окно |
Побочный эффект присваиваний
| (setq x 'y) (set x 'NEW) (print x) (print y) |
| Пример 11.2. Побочный эффект присваиваний с вычисляемой левой частью |
| Закрыть окно |
Пример (setq x 'y)
(setq x 'y)
(set x 'NEW)
(print x)
(print y)
явный выход из цикла при
|
(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 first-a (la)
;; самый левый атом
(setq x la)
(loop
(setq x (car x)) ; левый элемент структуры
(cond ((atom x)(return x)) )
; явный выход из цикла при обнаружении атома
) )
(print (first-a '(((123) 46) 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. Вычисление длины списка |
| Закрыть окно |
выход из цикла при пустом
(defun len-do (ld)
;; длина списка
(do
((x ld (cdr x)); на каждом шаге переход к хвосту списка
(N 0 (1+ N))) ; подсчет числа шагов
((null x) N)) ; выход из цикла при пустом списке
)
(print (len-do '(1 2 3 4 5)))
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. |
| Закрыть окно |
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))
Индексный выбор элемента из
| (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. Индексный выбор элемента из списка |
| Закрыть окно |
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 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, до тех пор, пока ей не будет присвоено что-нибудь другое.
При реализации языка программирования происходит
При реализации языка программирования происходит его расширение с целью повышения практичности программирования.Стандартные, операторно-процедурные построения моделируются с помощью функций.
