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

         

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



Содержание раздела