Последовательности вычислений

В языке Lisp существует возможность организации последовательностей вычислений, вплоть до поддержки процедурного стиля программирования. Для этого служат различные специфичные конструкции, часть из которых будут описана в этом разделе.

let

(LET ( (локальная_переменная1 значение1) ( локалная_переменная2_значение2 )… ) форма1 форма2 … ) Создаёт локальную связь. Содержит в своём первом параметре список, каждый элемент которого представляет собой пару "локальная переменная - значение" и выполняется в начале вычисления оператора. Остальными параметрами LET являются вычисляемые формы, значение последней из которых возвращается в качестве результата. Необходимо отметить, что результат модификации локальных переменных по завершении оператора не сохраняется.

>(SETQ A 1) >(LET ((A 2)) (+ A 1)) >A

Отметим, что в данном случае оператор LET содержал в себе одну форму (+ A 1) и, в то же время, естественно, сам являлся формой. В качестве параметра-формы LET вполне мог использоваться другой оператор LET или любой другой оператор.

prog1 prog2 prong

(progn форма1 форма2 форма3…) Позволяет выполнять последовательные вычисления форм. Возвращается значение, соответственно, первой, второй и последней формы.

>(PROG1 1 2 3) >(PROG2 1 2 3) >(PROGN 1 2 3)

Естественно, применение этой конструкции может быть и более сложным:

>(progn (setq A 5) (setq B 7)) >A >B

Условные операторы и циклы

Для того, чтобы решать задачи, необходимо обеспечивать разветвление алгоритмов, в частности, языку особенно необходимы условные конструкции и циклы. Здесь мы рассмотрим некоторые из них, имеющие наиболее частое применение, и начнём с операторов условия.

cond

(cond (условие1 форма1) (условие форма2)…) Реализует таблицу решений. В зависимости от выполняемого условия возвращает сопоставленное ему выражение. Аргументами COND являются списки из двух элементов, первый из которых указывает на условие, а второй определяет, какое значение при выполнении этого условия должен вернуть COND. Если ни одно условие не подойдёт, возвращается NIL. Ветви просматриваются последовательно, и как только одно из условий оказывается истинным, выполнение COND завершается

COND является наиболее общей формой условного оператора. Все остальные условные операторы могут быть выражены через него. Примером использования может быть некая таблица решений, например, вывести день недели по его номеру:

>(SETQ DAY 3) >(COND ((EQL DAY 1) "Monday") ((EQL DAY 2) "Tuesday") ((EQL DAY 3) "Wednesday") ((EQL DAY 4) "Thursday") ((EQL DAY 5) "Friday") ((EQL DAY 6) "Saturday") ((EQL DAY 7) "Sunday") (T "Check your calendar") ) "Wednesday"

При попытке выполнить пример необходимо обратить внимание, что дни недели, написанные по-русски, некоторые интерпретаторы не понимают. Также заметим, что последним условием является T - это условие по умолчанию, оно всегда выполнится, если только до него не выполнилось уже какое-то другое. Естественно, условие NIL бессмысленно.

if	(if условие форма-для-истинности форма-для-ложности) Реализует простой условный оператор. Содержит три аргумента - условие, результат, если условие истинно, результат, если условие ложно. Соответствует оператору (cond (Условие результат-при-истинном-условии) (T результат-при-ложном-условии))

В качестве примера приведём следующий код, пытающийся определить, является ли число натуральным:

>(SETQ NUMBER 100) >(IF (> NUMBER 0) "Natural" "Not Natural") "Natural" >( SETQ NUMBER -100) -100 >(IF (> NUMBER 0) "Natural" "Not Natural") "Not Natural"

Наконец, можно использовать также дополнительные виды условных операторов, такие как WHEN, UNLESS, CASE.

when	(when условие значение-при-истинности) Модифицированный вариант оператора COND, содержит в качестве параметров одно условие (первый параметр) и несколько форм, которые вычисляются последовательно при истинности условия. Возвращается значение последней вычисленной формы.

unless

(unless значение-при-ложности) То же самое, что и WHEN, однако формы вычисляются, если условие ложно.

case

(case ключ (список-ключей форма1 форма2…) (список-ключей форма1 форма2…)…) Традиционная таблица решений (сходна с соответствующим оператором языка Pascal). Содержит первый параметр - ключ, который вычисляется перед обработкой всех остальных параметров. Остальные параметры состоят каждый из списка ключей и последовательности вычисляемых форм, причём вычисляются формы (и возвращается последняя из них) в том случае, если значение ключа CASE было найдено в списке ключей одного из параметров.

Приведём примеры использования соответствующих функций. Используем наш старый пример с определением того, является ли число натуральным (в противном случае возвращается NIL):

>(SETQ NUMBER 100) >(SETQ NUMBER 100) >(WHEN (> NUMBER 0) "Natural") "Natural" >(UNLESS (> NUMBER 0) "Not Natural") NIL >( SETQ NUMBER -100) -100 >(WHEN (> NUMBER 0) "Natural") NIL >(UNLESS (> NUMBER 0) "Not Natural") "Not Natural"

А также модифицированная версия таблицы решений относительно дней недели:

>(SETQ DAY 3) >(CASE DAY (1 "Monday") (2 "Tuesday") (3 "Wednesday") (4 "Thursday") (5 "Friday") (6 "Saturday") (7 "Sunday") (T "Check your calendar") ) "Wednesday"

Теперь рассмотрим операторы циклов

do

(do ((переменная начальное-значение приращение)…) (условие-окончания форма1 форма2 …) форма 11 форма12…) Функция является наиболее общим вариантом организации циклов. Реализуется в форме DO Инициализация Условие Тело цикла. Инициализация является списком правил, каждое из которых состоит из имени переменной, начального значения и приращения, Условие состоит из собственно условия выхода и вычисляемых форм, которые вычисляются при возврате функцией значения (как обычно, возвращается последняя). Наконец тело представляет собой последовательность вычисляемых форм, которые выполняются каждый раз при новой итерации. К сожалению, не во всех версиях Lisp поддерживается приращение итератора. В таких слуяаях необходимо выполнять её приращение отдельным кодом.

Примером работы с оператором DO может служить программа, вычисляющая факториал числа (этот пример достаточно показателен в следствие последующего изложения эквивалентности решений с помощью циклов и рекурсии).

>(defun f1 (x) (do ((res 1) (rs 1)) ((eql x 0) rs) (setq rs (* res rs)) (setq x (- x 1)) (setq res (+ res 1)) )) F1 >(f1 5)

Существует и более простой в обращении цикл LOOP:

loop	(loop форма 1 форма2…) Функция повторяет вычисление своих форм до тех пор, пока среди них не встретится оператор RETURN

return

(return результат) Функция позволяет выйти из цикла и вернуть значение для операторов LOOP и PROG.

Модифицируем факториал с помощью LOOP:

>(defun f1 (x) (progn (setq res 1) (loop (setq res (* res x)) (setq x (- x 1)) (if (eql x 0) (return res)) ))) F1 >(f1 5)

Наконец, последним алгоритмическим средством, рассматриваемым в этом разделе, является оператор PROG, позволяющий выполнять программирование в традиционном процедурном стиле. Сразу отметим, что оператор PROG не имеет почти ничего общего с PROG1 и PROGN.

prog	(prog(переменная1 переменная2… ) оператор1 оператор2…) позволяет программировать в традиционном процедурном стиле, используя передачу управления между последовательными операторами. Позволяет использовать в качестве своих форм операторы GO и RETURN

go	(go метка) Функция позволяет выполнить внутри оператора PROG переход на некоторую метку. Форма считается меткой если она является символом или числом.

Приведём в качестве примера работы с функцией PROG следующий код, вычисляющий степень некоторого числа.

>(defun exp1 (x n) (prog (res) (setq res x) loop (if (= n 1) (return res)) (setq res (* res x)) (setq n (- n 1)) (go loop) ) ) EXP1 >(exp1 2 3)

Рекурсия

Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя. В математике рекурсия применяется повсеместно, например, следующее определение рекурсивно: "0 является натуральным числом; натуральное число плюс единица есть натуральное число".

С точки зрения реализации различают прямую рекурсию (когда процедура содержит ссылку на себя) и косвенную (когда процедура содержит ссылку на другую процедуру, содержащую ссылку на исходную). Более подробная информация о рекурсии вообще может быть найдена в источнике (Вирт, 1986).

В большинстве процедурных языков программирования рекурсия является скорее нежелательным методом программирования (вследствие возможности переполнения стека), однако в Lisp она является не только допустимой без ограничений, но, более того, является основным инструментом организации циклов. В чистом Lisp операторы DO и LOPP, а тем более PROG отсутствуют, и должны быть заменены рекурсией. Здесь мы рассмотрим основные приёмы использования этого механизма.

Простейшая рекурсия заключается в том, что некоторая функция вызывает сама себя для проведения некоторых вычислений. Рекурсия отражает рекуррентные соотношения (когда в ряду значений каждое новое вычисляется на основании предыдущих). Простейшим примером является факториал, который задаётся в частности как n!=n* (n-1)!. В примере с функцией DO было рассмотрено вычисление факториала с помощью цикла. С помощью рекурсии можно вычислить его так:

>(defun fc2 (x) (cond ((eql x 0) 1) ((eql x 1) 1) (T (* x (fc2 (- x 1)))))) FC2 >(fc2 5)

Как видно из примера, рекурсивный вызов полностью отражает рекуррентное соотношение, описывающее факториал. Тем не менее, можно с помощью такого же метода организовывать и циклы, например, в следующем примере функция создаёт список из элементов от 1 до n

>(defun lst2 (x lst) (cond ((eql x 0) lst) (T (lst2 (- x 1) (cons x lst))))) LST2 >(LST2 5 nil) (1 2 3 4 5)

Основной проблемой, которая может возникнуть при работе с таким механизмом, является бесконечная рекурсия. Бесконечная рекурсия возникает вследствие логических ошибок в программе и приводит к зацикливанию алгоритма и исчерпанию системных ресурсов машины. Примером бесконечной рекурсии может быть следующее выражение:

>(defun err1 () (err1)) ERR1 >(err1) Error: Stack overflow (signal 1000) [condition type: SYNCHRONOUS-OPERATING-SYSTEM-SIGNAL]

В этом примере функция ERR1 выполняет свой рекурсивный вызов всегда, тем самым, вызывая переполнение стека и ошибку. Для того, чтобы избегать подобного, необходимо следовать следующим простым правилам:

· В теле функции всегда должно присутствовать правило, гарантирующее выход из рекурсии.

· Правила, гарантирующие выход из рекурсии, должны предшествовать правилам, содержащим рекурсию

Даже при соблюдении таких правил зацикливание всё равно возможно, поэтому необходимо использовать отладку. Отладка рекурсивных функций является, вообще говоря, не слишком простым делом. Для неё используется функция TRACE

trace

(trace функция) Функция позволяет выводить на экран дерево вызовов некоторой функции.

untrace

(untrace функция) Функция позволяет отменить режим вывода дерева вызовов некоторой функции, установленный функцией trace.

В качестве примера приведём всё то же вычисление факториала:

>(defun fc2 (x) (cond ((eql x 0) 1) ((eql x 1) 1) (T (* x (fc2 (- x 1)))) )) FC2 >(fc2 5) >(trace fc2) (FC2) >(fc2 5) 0: (FC2 5) 1: (FC2 4) 2: (FC2 3) 3: (FC2 2) 4: (FC2 1) 4: returned 1 3: returned 2 2: returned 6 1: returned 24 0: returned 120

Подобный механизм способен существенно упростить отладку рекурсивных функций. К сожалению, не все версии Lisp позволяют выполнять отладку нескольких функций одновременно.

В заключение обсуждения простой рекурсии рассмотрим некоторые примеры операций над списками, реализуемые с помощью рекурсии.