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

         

Циклы


Работа с циклами обеспечена в Лиспе достаточно традиционно.

(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)

Таблица 11.1. Clisp: Функции, моделирующие императивный стиль

(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, до тех пор, пока ей не будет присвоено что-нибудь другое.



При реализации языка программирования происходит


При реализации языка программирования происходит его расширение с целью повышения практичности программирования.Стандартные, операторно-процедурные построения моделируются с помощью функций.