Точно Не проект 2 / Не books / Источник_1
.pdf230 |
Глава 5 |
|
|
перед которым стоит двоеточие. Ключевые параметры удобны тем, что при вызове функции их можно перечислять в любом порядке:
(defun print_arg_key (&key x y (z 5 ))
(print x ) (print y ) z )
(print_arg_key :y 4 x: 6 )
6
4
5
(print_arg_key :y 2 :z 1 :x 0 )
0
2
1
Ключевые параметры являются необязательными, поэтому в первом вызове Z получает значение, равное пяти.
Рассмотренные виды параметров функций часто используют в справочниках при описании форматов функций. Например, если хотят подчеркнуть, что функция имеет произвольное количество аргументов, то пишут
(+ &REST числа )
или
( LIST &REST элементы )
Если функция имеет ключевые управляющие параметры, то в формат ее описания могут включаться имена этих параметров [48]:
(MEMBER элемент список
&KEY : TEST
:TEST-NOT
:KEY )
Значения некоторых ключевых слов, используемые во встроенных функциях, будут рассмотрены позже.
5.9. Связывание и область действия переменных
Ранее были рассмотрены формы, присваивающие значения переменным (SET, SETQ, SETF). Значения, присвоенные переменным с помощью этих форм, остаются действующими до тех пор, пока не будет сделаны новые назначения. Процесс назначения переменной определенного значения на определенном участке программы называется связыванием (binding).
Язык Лисп |
231 |
|
|
Формы группы SET выполняют связывание в результате побочных эффектов. Возникающие при этом связи значений и переменных остаются в силе после завершения SET-вызовов. В Лиспе имеются и другие средства, выполняющие связывание. Область действия устанавливаемых связей определяется рядом обстоятельств.
Если требуется установить локальные связи, то используется форма
LET:
(let ({( переменная форма-инициализатор )}*){ форма }*)
Здесь форма-инициализатор задает новое значение переменной, которое доступно только в переделах LET. По окончании LET-вызова восстанавливается старое значение переменной в соответствии со связями, которые имела переменная во внешнем окружении LET. Значение, возвращаемое LET-вызовом, соответствует последней вычисленной форме, входящей в LET. Например,
(setf |
x |
5) 5 |
(set |
y |
7) 7 |
let (( x |
10) (z 6)) ( + x y z)) 23 |
|
х 5
zError: UNBOUND-VARIABLE
Вэтом примере в LET-вызове устанавливаются локальные связи для переменных X и Z. Переменная У в LET-вызове является свободной. Значение свободной переменной определяется связями внешнего окружения LET, т.е. У=7. После завершения LET-вызова переменная Х восстанавливает
свое значение, так как была ранее связана с помощью SETF. Переменная Z не имела связей во внешнем окружении LET, поэтому попытка определить ее значение за пределами LET завершается ошибкой – UNBOUND VARIABLE (несвязанная переменная).
Связывание переменных внутри формы LET выполняется параллельно. Поэтому в следующем примере результат LET-вызова будет пять, а не три:
(setf a 3) 3
(let (( a 1 ) ( b ( + a 2 )) b) 5
Иными словами, при связывании переменной В здесь используется не локальное значение переменной А, а глобальное, присвоенное вызовом
SETF.
Если необходимо, чтобы связи локальных переменных устанавливались последовательно, то применяется форма LET*. Определим функцию, вычисляющую выражение
232 |
Глава 5 |
|
|
x |
y z / 2 |
|
|
|
|
||
y 2 |
y z. |
|
|
|
|
||
Воспользуемся формой LET*:
(defun f1 (y z) |
|
|
|
||
(let* (( a ( sqrt |
( + y z |
))) |
|||
( b ( + (* |
y |
y ) |
a )) |
||
( c |
( + |
y |
( / |
z |
2 ))) |
( x |
(/ c |
b ))) |
; Конец списка инициализаторов |
||
x )) ; возвращаемое значение
Здесь переменная В получает значение после связывания переменной А, переменная С – после связывания В и т.д. Поэтому присваивание значения переменной В происходит, когда переменная А уже получила значение, равное 
y z.
Форма LET представляет собой видоизмененный лямбда-вызов:
(let (( x1 a1 ) (x2 a2) … |
( xn an )) { форма }*) |
((lambda (x1 x2 … xn) |
; формальные параметры |
{форма }*) |
|
a1 a2 … аn) |
; фактические параметры |
Отсюда следует, что в LET-форме формальные параметры представляются переменными x1, x2,…, xn, а фактические параметры a1, a2,…,аn задают значения этих переменных. Связь формальных и фактических параметров является локальной и действует только в пределах этих форм. Так как лямбда-выражение подставляется вместо имени функции, то и при обычном вызове функции устанавливается связь фактических и формальных параметров, которая действительна только в пределах вызываемой функции. Так, в рассмотренной выше функции F1 значения формальных параметров У и Z будут локальными. Их начальные значения будут соответствовать значениям фактических параметров, переданных в момент вызова функции. Никакие изменения значений формальных параметров внутри функции не могут отразиться на значениях фактических параметров, так как их связь является локальной. Иными словами, передача значений от фактических параметров к формальным выполняется копированием (т.е. по значению).
Переменные, имеющие локальные связи, в Коммон Лиспе называются лексическими или статическими. Область действия такой переменной ограничивается той формой, в которой переменная определена, т.е. связи лексической переменной действительны в некотором фиксированном текстуальном (лексическом) окружении. Эти связи не действуют вне тексту-
Язык Лисп |
233 |
|
|
ального окружения, а также в функциях, которые вызываются в этом окружении, но описаны за его пределами. Например,
(setf |
x |
’(a b )) (A B) |
(defun |
print_car ( ) |
|
|
|
(print (car x ))) PRINT_CAR |
(let |
( ( x ’( c d ))) ( print (car x )) |
|
|
|
( print_car)) |
С
А
А
Здесь свободная переменная Х в функции PRINT_CAR связана с глобальным значением (А В). Эта связь сохраняется также в том случае, когда функция PRINT_CAR вызывается в LET-форме после локального (лексического) связывания переменной Х со списком (С D). Таким образом, лексическим окружением, в котором переменная Х имеет значение списка (С D), является форма LET, за исключением вызываемой функции PRINT_CAR.
Область действия лексических переменных статическая, т.е. она не изменяется в ходе выполнения программы. Например, формальные параметры функций, являющиеся лексическими переменными, могут при выполнении функции получать новые значения. Однако областью действия (областью видимости) этих значений будет только форма, определяющая функцию:
(setf x 5 ) 5 (defun inc_x ( x )
(setq x ( + x 1 ))) INC_X
(inc_x x) 6
х 5
Альтернативой лексическим переменным являются динамические или специальные переменные.
Область действия такой переменной определяется не текстуальным окружением, в котором переменная используется, а динамическим окружением, возникающим в процессе выполнения программы.
Динамические переменные создаются с помощью формы
(defvar имя [ начальное значение ] )
Чтобы отличать такие переменные, им дают особые имена. Обычная практика состоит в том, чтобы такие имена начинались и заканчивались знаком “ * ”. Значение динамической переменной определяется по последней связи:
234 |
Глава 5 |
|
|
( defvar |
* х *) * х * |
|
( setf |
* х * ’( a b )) (А В) |
|
( defun |
print_car ( ) |
|
|
|
(print ( car * х *))) PRINT_CAR |
( let |
(( * x * ’( c d ))) ( print ( car * x *)) |
|
С |
|
( print_car )) |
|
|
|
С
С
При вызове функция PRINT_CAR обрабатывает значение переменной *х*, связанное не в форме SETF, а в форме LET. Именно оно было связано последним.
В связи с введением лексических и динамических переменных возникают интересные особенности в работе функции SET. Функция SET не может изменить значение лексической переменной:
(set x 100) 100
(defun f ( x ) (set ’x 5 ) (print x )) F (f 3)
3
3
х5
Как видно из примера, при вызове функции F печатается значение 3, соответствующее лексической связи переменной Х. В то же время функция SET изменила глобальное значение переменной Х, т.е. первым аргументом функции SET является не лексическая переменная, а динамическая.
Применение динамических и свободных переменных в функциях может приводить к путанице и затруднять отладку программ. Поэтому предпочтение следует отдавать лексическим переменным.
Важно, чтобы с символом были связаны значения. Попытка вычисления значения несвязанного символа приводит к ошибке. Для того чтобы проверить наличие значения у символа применяется предикат BOUNDP. Само значение символа можно определить при помощи функции
VALUE .
5.10. Последовательные и условные вычисления
Последовательные вычисления в Лиспе выполняются с помощью форм PROG1, PROG2, PROGN. Данные формы соответствуют составным операторам алгоритмических языков и имеют схожий формат вызова:
Язык Лисп |
235 |
|
|
(progn {форма}*)
(prog1 форма1 {форма}*)
(prog2 форма1 форма2 {форма}*)
Здесь формы, выступающие в роли аргументов PROG-вызовов, вычисляются последовательно, и в качестве результата возвращается значение последней формы (PROGN), первой формы (PROG1) или второй формы (PROG2). Рассмотрим пример моделирования стекового механизма:
(setf stack ‘(a b c d e f)) (A B C D E F)
(prog1 (first stack) (setf stack (rest stack))) A stack (B C D E F )
Последовательные вычисления можно также выполнять с помощью рассмотренной выше формы LET*. Эта форма позволяет использовать локальные переменные и в качестве результата возвращает значение последней вычисленной формы, входящей в LET-вызов.
Для выполнения условных вычислений в Лиспе могут применяться формы COND, IF, WHEN, UNLESS и др. Форма COND представляет собой макрос и позволяет выбрать одну из n-ветвей алгоритма. Формат вызова формы COND:
(cond {( тест-форма { форма }*)}+)
В этой записи тест-форма представляет собой логическое выражение, построенное с помощью различных предикатов и логических функций: AND (логическое И), OR (логическое ИЛИ), NOT (логическое отрицание). Конструкцию (тест-форма {форма}*) называют клозом (clause). Клоз представляет собой список форм.
Приведенный формат вызова формы COND является обобщением следующей записи:
(cond (тест-1 форма-11 форма-12 … ) (тест-2 форма-21 форма-22 … )
…
(тест-i форма-i1 форма-i2 … )
…
(тест-N форма-N1 форма-N2…))
Значение, возвращаемое формой COND, определяется следующими правилами. Последовательно вычисляются значения тест-форм, пока не встретится тест-форма, например тест-i, значением которой является Т. Затем последовательно вычисляются формы, соответствующего клоза, т.е. форма-i1, форма-i2 и т.д. Значение последней вычисленной формы клоза
236 |
Глава 5 |
|
|
будет представлять результат, возвращаемый формой COND в точку вызова. Если ни одна из тест-форм не получила значение Т, то результатом вызова формы COND будет NIL.
Обычно в качестве последней тест-формы используется символ T. Соответствующие ей формы клоза будут вычисляться, когда ни одна из предшествующих тест-проверок не выполняется. Рассмотрим простой пример:
(cond ((eq x ’Bern) ’Switzerland) ((eq x ’Paris) ’France) ((eq x ’Berlin) ’Germany) ((eq x ’Kiev) ’Ukraine)
(t ’unknown))
Здесь тест-формы реализованы с помощью предиката EQ. Если значением Х является атом, представляющий название одной из указанных столиц, то в качестве результата возвращается название соответствующего государства. Во всех остальных случаях возвращается значение
UNKNOWN.
В рассмотренном примере выбиралась одна из пяти ветвей алгоритма. Когда требуется выбрать одну из двух ветвей алгоритма, то используют специальную форму IF. Формат вызова формы:
(if тест-форма then-форма [else-форма] )
Если результатом вычисления тест-формы является значение Т, то IF возвращает значение, определяемое then-формой, иначе – else-формой, которая может отсутствовать. Пусть требуется вычислить абсолютное значение:
|
x, |
x 0, |
y |
|
x 0. |
x, |
||
Соответствующее выражение на языке Лисп будет иметь вид:
(if ( >= x 0) x ( - x ) )
Условные вычисления можно также организовать с помощью макроформ WHEN и UNLESS. Форма WHEN имеет следующий формат вызова:
( when тест-форма { форма }*)
Язык Лисп |
237 |
|
|
Здесь формы вычисляются лишь в том случае, если результат вычисления тест-формы – Т. Результатом вызова макроса WHEN является значение последней вычисленной формы. Например,
(setq x 3) 3
(when ( > x 0 ) (setf a 5) (setf b 6)) 6
Если тест-форма имеет значение NIL, то и вызов макроса WHEN возвращает NIL. Формат макровызова UNLESS аналогичен формату WHEN, но формы будут вычисляться лишь в том случае, если результат вычисления тест-формы – NIL.
Рассмотренные вызовы форм
ловными предложениями.
5.11.Итерационные циклические вычисления
ВЛиспе имеется большой арсенал средств для организации циклических вычислений. Одним из самых старых средств организации итерационных циклов является макроформа LOOP. Различают два варианта записи вызова LOOP – простой и расширенный. Рассмотрим простой вызов
LOOP:
(loop {форма}*)
Здесь конструкция {форма}* образует тело цикла. Формы, входящие в тело цикла, вычисляются циклически. Цикл завершается, когда управление, в одной из форм, передается макровызову возврата RETURN. При этом RETURN вычисляет значение, возвращаемое в точку вызова
LOOP.
Рассмотрим пример. Пусть требуется найти сумму чисел от 1 до n. Ниже приведен текст функции, решающий эту задачу, с помощью макровызова LOOP:
(defun nsum (n) (setf sum 0)
(loop (cond ((zerop n) (return sum))
(t (setf sum (+ sum n)) (setf n (- n 1)) ) )))
Другая конструкция, применяемая для организации итерационных циклов, – макроформа DО. Эта форма позволяет задавать: локальные (лексические) переменные цикла, их начальные значения и правила обновления; условие окончания цикла и значение, которое возвращает форма DО; формы, образующие тело цикла.
Общий формат макровызова DO:
238 |
Глава 5 |
|
|
(do (({переменная} [начальное_значение [обновление] ] )}*) (условие_окончания {форма}*)
{форма}*)
Первый аргумент DO-вызова представляет собой список, состоящий из подсписков. Элементами подсписков являются: переменные цикла; формы, задающие начальные значения переменных; выражения, определяющие правила обновления переменных. Если форма, устанавливающая начальное значение переменной, не задана, то значение переменной равно NIL. Если не задана форма обновления, то значение переменной может обновляться в теле цикла.
На каждой итерации вычисляется условие окончания цикла. Когда условие окончания цикла получает значение “истина“, то последовательно вычисляются формы, входящие во второй список DO-вызова. Значение последней вычисленной формы и будет результатом. Если условие окончания цикла ложно, то вычисляются формы, образующие тело цикла.
Пусть требуется вычислить факториал числа N. Определим для этого функцию FACTORIAL-DO:
(defun factorial-do (n) |
|
(do ((counter 1 (+ counter 1)) |
; управление counter |
(result 1 (* result counter))) |
; управление result |
((= counter (+ n 1)) result))) |
; условие окончания |
В этом примере для вычисления факториала используется формула n!=(n-1)! n, т.е. факториал каждого следующего числа вычисляется через факториал предыдущего числа. Результаты вычислений на каждом шаге сохраняются в локальной переменной RESULT. Количество выполненных итераций запоминается в счетчике COUNTER. Выход из цикла происходит при условии COUNTER = (N+1).
Присваивание значений переменным цикла в DO-вызове выполняется параллельно. Если необходимо последовательное присваивание, то применяется макровызов DO*.
Определим функцию MY-INTERSECTION, которая формирует список общих элементов двух списков:
(defun my-intersection (a b) |
|
(do* ((aa a (rest aa)) |
; управление переменной аа |
(e (first a) (first aa)) |
; управление переменной е |
(inter ( )) ) |
; управление переменной inter |
((null aa) inter) |
; условие окончания цикла |
(if (member e b) |
; тело цикла |
(setf inter (cons e inter))) ))
Язык Лисп |
239 |
|
|
В цикле сначала вычисляется значение переменной АА, а затем Е. При этом переменная Е соответствует первому элементу очередного хвоста списка АА, т.е. Е – это очередной элемент входного списка, представленного формальным параметром А. В переменной INTER накапливается результат. Её начальное значение равно ( ). Когда список АА будет исчерпан, то функция вернет в качестве результата значение переменной INTER.
Часто необходимо выполнять циклическую обработку каждого элемента списка. В этом случае применяется макроформа DOLIST:
(dolist (переменная список [результат] ) { форма }*)
Если требуется выполнить некоторые действия N раз, то используется макроформа DOTIMES:
(dotimes ( переменная счетчик [ результат] ) {форма}*)
Здесь действия выполняются для целочисленных значений переменной, задаваемых формой счетчик и лежащих в диапазоне от 0 до N-1. Когда переменная цикла станет равной N, цикл завершится, возвратив значе-
ние формы результат.
Циклические вычисления, использующие передачу управления операторам с метками, можно выполнить с помощью макроформы PROG. Упрощенный формат PROG-вызова имеет вид:
(prog ({переменная}*) {форма}*)
Указанные в начале PROG-вызова переменные являются локальными. Их начальные значения равны NIL. При необходимости они могут быть инициализированы другими значениями аналогично LET-вызову. Даже если список переменных PROG-вызова пустой, его необходимо всё равно задавать.
Формы, записываемые внутри PROG-вызова, называются операторами. Если какая-либо форма представлена символом или числом, то она рассматривается как метка. Передать управление на метку можно с помощью оператора GO:
(go метка)
Для окончания вычислений и возврата результатов из PROG-вызова применяется форма RETURN.
В следующем примере факториала: