-
Notifications
You must be signed in to change notification settings - Fork 8
/
chapter-04.tex
770 lines (649 loc) · 74.2 KB
/
chapter-04.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
\chapter{Синтаксис и семантика}
\label{ch:04}
\thispagestyle{empty}
После столь стремительного тура мы угомонимся на несколько глав, чтобы подробнее
рассмотреть возможности, которые использовали до сих пор. Я начну с обзора базовых
элементов синтаксиса и семантики Lisp, что, конечно же, означает, что я должен сначала
ответить на неотложный вопрос...
\section{Зачем столько скобок?}
Синтаксис Lisp немного отличается от синтаксиса языков, произошедших от Algol. Две
наиболее очевидные черты~-- это обширное использование скобок и префиксная нотация. По
непонятной причине такой синтаксис отпугивает многих людей. Противники Lisp склонны
описывать его синтаксис как <<запутанный>> и <<раздражающий>>. Название <<Lisp>>, по их словам,
должно обозначать <<Множество раздражающих ненужных скобок>> (Lots of Irritating Superfluous
Parentheses). С другой стороны, люди, исполь\-зую\-щие Lisp, склонны рассматривать его
синтаксис как одно из главных его достоинств. Как может быть то, что так не нравится одной
группе, быть предметом восхищения другой?
Я не смогу исчерпывающе обосновать необходимость такого синтаксиса, до тех пор, пока не
рассказано подробнее о макросах Lisp. Но я могу начать с интересной предыстории, которая
намекает, что, возможно, стоит остаться непредвзятым: когда John McCarthy изобрёл Lisp, он
собирался реализовать его в более Algol-подобном синтаксисе, который он называл
M-выражения. Однако он так не и сделал этого. Причину он объясняет в своей статье
\pclURL{http://www-formal.stanford.edu/jmc/history/lisp/node3.html}{<<История Lisp>>}\hspace{-0.25em}.
\begin{quote}
Проект по точному определению М-выражений и их компиляции или хотя бы трансляции их в
S-выражения не был ни завершён, ни явно заброшен. Он просто был отложен на
неопределённое будущее, а тем временем появилось новое поколение программистов, которые
предпочитали S-выражения любой Fortran- или Algol-подобной нотации, которая только может
быть выдумана.
\end{quote}
Другими словами, люди, которые действительно использовали Lisp на протяжении последних
45~лет, \textit{полюбили} синтаксис и нашли, что он делает язык более мощным. По прочтении
последующих глав вы начнёте понимать, почему.
\section{Вскрытие чёрного ящика}
Перед тем как мы рассмотрим специфику синтаксиса и семантики Lisp, будет полезно уделить
внимание тому, как они определены и чем отличаются от множества других языков.
В~большинстве языков программирования транслятор языка (интерпретатор или компилятор)
работает как чёрный ящик: вы передаёте последовательность символов, представляющих собой
текст программы, в чёрный ящик, и он (в зависимости от того, является он интерпретатором
или компилятором) либо выполняет указанные инструкции, либо создаёт скомпилированную
версию программы, которая выполняет инструкции после запуска.
Внутри чёрного ящика, конечно, трансляторы обычно разделяются на подсистемы, каждая из
которых ответственна за одну из частей задачи трансляции текста программы в
последовательность инструкций или объектный код. Типичное разделение~-- это разбиение
работы процессора на три фазы, каждая из которых предоставляет данные следующей:
лексический анализатор разделяет поток знаков на лексемы и передаёт их синтаксическому
анализатору, который строит дерево, представляющее выражения программы в соответствии с
грамматикой языка. Это дерево (называемое абстрактным синтаксическим деревом, AST) далее
передаётся процедуре вычисления, которая либо напрямую интерпретирует его, либо
компилирует его в какой-то другой язык; например в машинный код. Так как транслятор
является чёрным ящиком, то используемые им структуры данных, такие как лексемы или
абстрактные синтаксические деревья, интересуют только создателя реализации языка.
В~Common Lisp разбивка на фазы осуществлена немного иначе, и это влияет как на реализацию
языка, так и на его описание. Вместо одного чёрного ящика, который осуществляет переход от
текста программы к её поведению за один шаг, Common Lisp определяет два чёрных ящика,
первый из которых транслирует текст в объекты Lisp, а другой реализует семантику языка в
терминах этих объектов. Первый ящик называется процедурой чтения, а второй~-- процедурой
вычисления\pclfootnote{При реализации Lisp, как и при
реализации любого языка, существует множество способов реализации процедуры вычисления,
начиная от настоящих интерпретаторов, которые напрямую интерпретируют объекты,
переданные процедуре вычисления, до компиляторов, транслирующих объекты в машинный код,
который затем выполняется. Промежуточным решением являются реализации, в которых ввод
компилируется в промежуточную форму, такую как байт-код для виртуальной машины, а затем
происходит интерпретация этого байт-кода. Большинство современных реализаций Common Lisp
использует какую-либо форму компиляции, даже если вычисляют код во время выполнения}.
Каждый чёрный ящик определяет один уровень синтаксиса. Процедура чтения определяет, как
строки знаков могут транслироваться в объекты, называемые s-выражениями\pclfootnote{Иногда
фраза s-выражение относится к текстовому представлению, а иногда~-- к объектам, которые
являются результатом чтения текстового представления. Обычно либо понятно из контекста,
какое именно значение используется, либо разница не важна.}. Так как синтаксис
s-выражений включает синтаксис для списков произвольных объектов, включая другие списки,
s-выражения могут представлять произвольные древовидные выражения (\textit{tree
expressions}), очень похожие на абстрактные синтаксические деревья, генерируемые
синтаксическими анализаторами не Lisp-языков.
В~свою очередь, процедура вычисления определяет синтаксис форм Lisp, которые могут быть
построены из s-выражений. Не все s-выражения являются допустимыми формами Lisp, также как и
не все последовательности знаков являются допустимыми s-выражениями. Например, и
\lstinline{(foo 1 2)}, и \lstinline{("foo" 1 2)} являются s-выражениями, но только первое может быть
формой Lisp, так как список, который начинается со строки, не имеет смысла с точки зрения
вычисления форм.
Это разделение чёрного ящика имеет несколько следствий. Одно из них состоит в том, что вы
можете использовать s-выражения, как вы видели в главе~\ref{ch:03}, в качестве внешнего формата для
данных, не являющихся исходным кодом, используя \lstinline{READ} для их чтения и
\lstinline{PRINT} для их записи\pclfootnote{Не все объекты Lisp могут быть записаны таким
образом, чтобы их можно было снова прочитать. Но все, что вы можете прочитать с помощью
\lstinline{READ}, может быть записано с помощью \lstinline{PRINT} так, чтобы это можно было
впоследствии прочитать}. Другое следствие состоит в том, что так как семантика языка
определена в терминах деревьев объектов, а не в терминах строк знаков, то генерировать код
внутри языка становится легче, чем это можно было бы сделать, если бы код генерировался
как текст. Генерирование кода полностью с нуля не намного легче: и построение списков, и
построения строк являются примерно одинаковыми по сложности работами. Однако реальный
выигрыш в том, что вы можете генерировать код, манипулируя существующими данными. Это
является базой для макросов Lisp, которые я опишу гораздо подробнее в будущих
главах. Сейчас я сфокусируюсь на двух уровнях синтаксиса, определённых Common Lisp: это
синтаксис s-выражений, понимаемый процедурой чтения, и синтаксис форм Lisp, понимаемый
процедурой вычисления.
\section{S-выражения}
Базовыми элементами s-выражения являются списки и атомы. Списки ограничиваются скобками и
могут содержать любое число разделённых пробелами элементов. Все, что не список, является
атомом\pclfootnote{Пустой список, \lstinline{()}, который также может быть записан как
\lstinline{NIL}, является одновременно и списком, и атомом.}. Элементами списков, в свою
очередь, также являются s-выражения (другими словами, атомы или вложенные
списки). Комментарии (которые, строго говоря, не являются s-выражениями) начинаются с
точки с запятой, распространяются до конца строки и трактуются как пробел.
И это почти все. Так как списки синтаксически просты, то те оставшиеся синтаксические
правила, которые вам необходимо знать, касаются только различных типов атомов. В~этом
разделе я опишу правила для большинства часто используемых типов атомов: чисел, строк и
имён. После этого я расскажу, как s-выражения, составленные из этих элементов, могут быть
вычислены как формы Lisp.
С числами все довольно очевидно: любая последовательность цифр (возможно, начинающаяся со
знака (\lstinline{+} или \lstinline{-}), содержащая десятичную точку или знак деления и, возможно,
заканчивающаяся меткой показателя степени) трактуется как число. Например:
\begin{myverb}
123 ; целое число "сто двадцать три"
3/7 ; отношение "три седьмых"
1.0 ; число с плавающей точкой "один" с точностью,
; заданной по умолчанию
1.0e0 ; другой способ записать то же самое число с
; плавающей точкой
1.0d0 ; число с плавающей точкой "один" двойной точности
1.0e-4 ; эквивалент с плавающей точкой числа
; "одна десятитысячная"
+42 ; целое число "сорок два"
-42 ; целое отрицательное число "минус сорок два"
-1/4 ; отношение "минус одна четвёртая"
-2/8 ; другой способ записать то же отношение
246/2 ; другой способ записать целое "сто двадцать три"
\end{myverb}
Эти различные формы представляют различные типы чисел: целые, рациональные, числа с
плавающей точкой. Lisp также поддерживает комплексные числа, которые имеют свою
собственную нотацию и которые мы рассмотрим в главе~\ref{ch:10}.
Как показывают некоторые из этих примеров, вы можете задать одно и то же число множеством
различных способов. Но независимо от того, как вы запишете их, все рациональные числа
(целые и отношения) внутри Lisp представляются в <<упрощённой>> форме. Другими словами,
объекты, которые представляют числа $-2/8$ и $246/2$, не отличаются от объектов, которые
представляют числа $-1/4$ и 123. Таким же образом, 1.0 и 1.0e0~-- просто два разных способа
записать одно число. С другой стороны, 1.0, 1.0d0 и 1 могут представлять различные
объекты, так как различные представления чисел с плавающей точкой и целых чисел являются
различными типами. Мы рассмотрим детально характеристики различных типов чисел в главе~\ref{ch:10}.
Строковые литералы, как вы видели в предыдущей главе, заключаются в двойные
кавычки. Внутри строки обратный слэш (\bslash) экранирует следующий знак, что
вызывает включение этого знака в строку <<как есть>>. Только два знака должны быть
экранированы в строке: двойная кавычка и сам обратный слэш. Все остальные знаки могут быть
включены в строковый литерал без экранирования, не обращая внимания на их значение вне
строки. Несколько примеров строковых литералов:
\begin{myverb}
"foo" ; строка, содержащая знаки 'f', 'o' и 'o'.
"fo\bslash{}o" ; такая же строка.
"fo\bslash{}\bslash{}o" ; строка, содержащая знаки 'f', 'o', '\bslash{}' и 'o'.
"fo\bslash{}"o" ; строка, содержащая знаки 'f', 'o', '"' и 'o'.
\end{myverb}
Имена, использующиеся в программах на Lisp, такие как \lstinline{FORMAT}, \lstinline{hello-world}
и \lstinline{*db*}, представляются объектами, называющимися \textit{символами}. Процедура чтения
ничего не знает о том, как данное имя будет использоваться~-- является ли оно именем
переменной, функции или чем-то ещё. Она просто читает последовательность знаков и создаёт
объект, представляющий имя\pclfootnote{Фактически, как вы увидите далее, имена не
связаны ни с какими вещами. Вы можете использовать одинаковое имя, в зависимости от
контекста, для ссылки и на переменную, и на функцию, не говоря уже о некоторых других
возможностях.}. Почти любой знак может входить в имя. Однако это не может быть
пробельный знак, так как пробелом разделяются элементы списка. Цифры могут входить в
имена, если имя целиком не сможет интерпретироваться как число. Схожим образом имена
могут содержать точки, но процедура чтения не может прочитать имя, состоящее только из
точек. Существует десять знаков, которые не могут входить в имена, так как предназначены
для других синтаксических целей: открывающая и закрывающая скобки, двойные и одинарные
кавычки, обратный апостроф, запятая, двоеточие, точка с запятой, обратная косая черта
(слэш) и вертикальная черта. Но даже эти знаки могут входить в имена, если их экранировать
обратной косой чертой или окружить часть имени, содержащую знаки, которые нужно
экранировать, с помощью вертикальных линий.
Две важные характерные черты того, каким образом процедура чтения переводит имена в
символьные объекты, касаются того, как она трактует регистр букв в именах и как она
обеспечивает то, чтобы одинаковые имена всегда читались как одинаковые символы. Во время
чтения имён процедура чтения конвертирует все неэкранированные знаки в именах в их
эквивалент в верхнем регистре. Таким образом, процедура чтения прочитает \lstinline{foo},
\lstinline{Foo} и \lstinline{FOO} как одинаковый символ: \lstinline{FOO}. Однако
\lstinline!\f\o\o! и \lstinline!|foo|! оба
будут прочитаны как foo, что будет отличным от символа FOO объектом. Это как раз и
является причиной, почему при определении функции в REPL он печатает имя функции,
преобразованное к верхнему регистру. Сейчас стандартным стилем является написание кода в
нижнем регистре, позволящее процедуре чтения преобразовывать имена к верхнему\pclfootnote{На
самом деле поведение процедуры чтения по конвертации регистра знаков может быть
нас\-трое\-но, но понимание того, что и где изменять, требует гораздо более глубокого
обсуждения отношений между именами, символами и другими элементами программы, чем
я пока готов вам дать.}.
Чтобы быть уверенным в том, что одно и то же текстовое имя всегда читается как один и тот
же символ, процедура чтения хранит все символы~-- после того как она прочитала имя и
преобразовала его к верхнему регистру, процедура чтения ищет в таблице, называемой
\textit{пакетом} (\textit{package}), символ с таким же именем. Если она не может найти
такой, то она создаёт новый символ и добавляет его к таблице. Иначе она возвращает символ,
уже хранящийся в таблице. Таким образом, где бы одно и то же имя не появлялось в любых
s-выражениях, оно будет представлено одним и тем же объектом\pclfootnote{Более детально
отношения между символами и пакетами я опишу в главе~\ref{ch:21}.}.
Так как имена в Lisp могут содержать намного большее множество знаков, чем в языках,
произошедших от Algol, в Lisp существуют определённые соглашения по именованию, такие как
использование дефисов в именах наподобие \lstinline{hello-world}. Другое важное соглашение
состоит в том, что глобальным переменным дают имена, начинающиеся и заканчивающиеся знаком
\lstinline{*}. Подобным образом константам дают имена, начи\-наю\-щие\-ся и заканчивающиеся знаком
\lstinline{+}. Также некоторые программисты называют очень низкоуровневые функции именами,
начинающимися с \lstinline!%! или даже \lstinline!%%!. Имена, определённые в стандарте
языка, используют только алфавитные знаки (A--Z), а также \lstinline{*}, \lstinline{+}, \lstinline{-},
\lstinline{/}, \lstinline{1}, \lstinline{2}, \lstinline{<}, \lstinline{=}, \lstinline{>}, \lstinline{&}.
Синтаксис для списков, чисел, строк и символов описывает б\'{о}льшую часть Lisp-программ.
Другие правила описывают нотацию для векторных литералов, отдельных знаков, массивов,
которые я опишу в главах~\ref{ch:10} и~\ref{ch:11}, когда мы будем говорить об этих типах
данных. Сейчас главным является понимание того, как комбинируются числа, строки и символы
с разделёнными скобками списками для построения s-выражений, представляющих произвольные
деревья объектов. Несколько простых примеров:
\begin{myverb}
x ; символ X
() ; пустой список
(1 2 3) ; список из трёх элементов
("foo" "bar") ; список из двух строк
(x y z) ; список из трёх символов
(x 1 "foo") ; список из символа, числа и строки
(+ (* 2 3) 4) ; список из символа, списка и числа
\end{myverb}
Еще одним чуть более сложным примером является четырёхэлементный список, содержащий два
символа, пустой список и другой список, в свою очередь, содержащий два символа и строку:
\begin{myverb}
(defun hello-world ()
(format t "hello, world"))
\end{myverb}
\section{S-выражения как формы Lisp}
После того как процедура чтения преобразует текст в s-выражения, эти s-выражения
могут быть вычислены как код Lisp. Точнее, некоторые из них могут~-- не каждое s-выражение,
которое процедура чтения может прочитать, обязательно может быть вычислено как код
Lisp. Правила вычислений Common Lisp определяют второй уровень синтаксиса, который
определяет, какие s-выражения могут трактоваться как формы Lisp\pclfootnote{Конечно, в Lisp
существуют и иные уровни проверки корректности, как и в других языках. Например,
s-выражение, являющееся результатом чтения \lstinline{(foo 1 2)}, синтаксически правильно, но
может быть вычислено, только если foo является именем функции или
макроса.}. Синтаксические правила на этом уровне очень просты. Любой атом (не список или
пустой список) является допустимой формой Lisp, а также любой список, который содержит
символ в качестве своего первого элемента, также является до\-пус\-ти\-мой формой
Lisp\pclfootnote{Другой, редко используемый тип форм Lisp~-- это список, первый элемент
которого является лямбда-формой. Я буду обсуждать этот тип форм в главе~\ref{ch:05}.}.
Конечно, интересным является не синтаксис форм Lisp, а то, как эти формы вычисляются. Для
целей дальнейшего обсуждения вам достаточно думать о процедуре вычисления как о функции,
которая получает в качестве аргумента синтаксически правильную форму Lisp и возвращает
значение, которое мы можем назвать \textit{значением} (\textit{value}) формы. Конечно,
когда процедура вычисления выступает в роли компилятора, это является небольшим упрощением~-- в
этом случае процедура вычисления получает выражение и генерирует код, который, будучи
запущенным, вычислит соответствующее значение. Но это упрощение позволит мне описать
семантику Common Lisp в терминах того, как различные типы форм Lisp вычисляются с помощью
этой воображаемой функции.
Простейшие формы Lisp, атомы, могут быть разделены на две категории: символы и всё
остальное. Символ, вычисляемый как форма, трактуется как имя переменной и вычисляется в её
текущее значение\pclfootnote{Существует одна иная возможность~-- можно определить
\textit{символьный} макрос (\textit{symbol macros}), который вычисляется немного
по-другому. Мы не должны беспокоиться об этом.}. Я обсужу в главе~\ref{ch:06}, как
переменные получают свои значения впервые. Также следует заметить, что некоторые
<<переменные>> являются старым программистским оксюмороном: <<константными
переменными>>. Например, символ \lstinline{PI} именует константную переменную, чьё
значение~-- число с плавающей точкой, являющееся наиболее близкой аппроксимацией
математической константы $\pi$.
Все остальные атомы (числа и строки) являются типом объектов, который вы уже
рассмотрели,~-- это \textit{самовычисляемые объекты} (\textit{self-evaluating
objects}). Это означает, что когда выражение передаётся в воображаемую функцию
вычисления, оно просто возвращается. Вы видели примеры самовычисляемости объектов в
главе~\ref{ch:02}, когда набирали 10 и \lstinline{"hello, world"} в REPL.
Символы также могут быть самовычисляемыми в том смысле, что переменной, которую именует
такой символ, может быть присвоено значение самого этого символа. Две важные константы
определены таким образом: \lstinline{T} и \lstinline{NIL}, стандартные истинное и ложное
значения. Я обсужу их роль как логических выражений в разделе <<Истина, ложь и равенство>>.
Еще один класс самовычисляемых символов~-- это \textit{символы-ключи} (\textit{keyword
symbols})~-- символы, чьи имена начинаются с :. Когда процедура чтения обрабатывает
такое имя, она автоматически определяет константную переменную с таким именем и таким
символом в качестве значения.
Всё становится гораздо интереснее при рассмотрении того, как вычисляются списки. Все
допустимые формы списков начинаются с символа, но существуют три разновидности форм
списков, которые вычисляются тремя различными способами. Для определения того, какую
разновидность формы представляет из себя данный список, процедура вычисления должна
определить, чем является первый символ списка: именем функции, макросом или специальным
оператором. Если символ ещё не был определён (такое может быть в случае, если вы
компилируете код, который содержит ссылки на функции, которые будут определены позднее)~--
предполагается, что он является именем функции\pclfootnote{В~Common Lisp символ может
именовать как оператор (функцию, макрос или специальную форму), так и переменную. Это
одно из главных отличий между Common Lisp и Scheme. Эта разница иногда описывается как
то, что Common Lisp является Lisp-2, а Scheme~-- Lisp-1. Lisp-2 имеет два пространства
имён, одно для операторов и одно для переменных, а Lisp-1 использует единое пространство
имён. Оба подхода имеют свои преимущества, и их поборники ведут нескончаемые споры, что
же все-таки лучше.}. Я буду ссылаться на эти три разновидности форм как на \textit{формы
вызова функции} (\textit{function call forms}), \textit{формы макросов} (\textit{macro
forms}) и \textit{специальные формы} (\textit{special forms}).
\section{Вызовы функций}
Правило вычисления для форм вызова функции просто: вычисление элементов списка, начиная со
второго, как форм Lisp и передача результатов в функцию, именованную первым элементом. Это
правило явно добавляет несколько дополнительных синтаксических ограничений на форму вызова
функции: все элементы списка после первого должны также быть правильными формами
Lisp. Другими словами, базовый синтаксис формы вызова функции следующий (каждый аргумент
также является формой Lisp):
\begin{myverb}
(function-name argument*)
\end{myverb}
Таким образом, следующее выражение вычисляется путём первоначального вычисления~1,
затем~2, а потом передачи результатов вычислений в функцию~+, которая возвращает~3:
\begin{myverb}
(+ 1 2)
\end{myverb}
Более сложное выражение, такое как следующее, вычисляется схожим образом, за исключением
того, что вычисление аргументов \lstinline{(+ 1 2)} и \lstinline{(- 3 4)} влечёт за собой
вычисление аргументов этих форм и применение соответствующих функций к ним:
\begin{myverb}
(* (+ 1 2) (- 3 4))
\end{myverb}
В~итоге значения $3$ и $-1$ передаются в функцию \lstinline{*}, которая возвращает~$-3$.
Как показывают эти примеры, функции используются для многих вещей, которые требуют
специального синтаксиса в других языках. Это помогает сохранять синтаксис Lisp регулярным.
\section{Специальные операторы}
Нужно сказать, что не все операции могут быть определены как функции. Так как все
аргументы функции вычисляются перед её вызовом, не существует возможности написать
функцию, которая ведёт себя как оператор \lstinline{IF}, который вы использовали в
главе~\ref{ch:03}. Для того чтобы увидеть, почему, рассмотрим такую форму:
\begin{myverb}
(if x (format t "yes") (format t "no"))
\end{myverb}
Если IF является функцией, процедура вычисления будет вычислять аргументы выражения слева
направо. Символ x будет вычислен как переменная, возвращающая своё значение; затем как
вызов функции будет вычислена \lstinline{(format t "yes")}, возвращающая \lstinline{NIL} после
печати <<yes>> на стандартный вывод; и потом будет вычислена \lstinline{(format t "no")}, печатающая
<<no>> и возвращающая \lstinline{NIL}. Только после того как эти три выражения будут
вычислены, их результаты будут переданы в \lstinline{IF}, слишком поздно для того, чтобы
проконтролировать, какое из двух выражений \lstinline{FORMAT} будет вычислено.
Для решения этой проблемы Common Lisp определяет небольшое количество так называемых
специальных операторов (и один из них \lstinline{IF}), которые делают те вещи, которые
функции сделать не могут. Всего их 25, но только малая их часть напрямую используется в
ежедневном программировании\pclfootnote{Остальные предоставляют полезные, но в некотором роде
эзотерические возможности. Я буду обсуждать их, когда эти возможности нам понадобятся.}.
Если первый элемент списка является символом, именующим специальный оператор, остальная
часть выражения вычисляется в соответствии с правилом для этого оператора.
Правило для \lstinline{IF} очень просто: вычисление первого выражения. Если оно вычисляется
не в \lstinline{NIL}, то вычисляется следующее выражение и возвращается его результат. Иначе
возвращается значение вычисления третьего выражения или \lstinline{NIL}, если третье
выражение не задано. Другими словами, базовая форма выражения \lstinline{IF} следующая:
\begin{myverb}
(if test-form then-form [ else-form ])
\end{myverb}
\noindent{}\lstinline{test-form} вычисляется всегда, а затем только одна из \lstinline{then-form} и
\lstinline{else-form}.
Еще более простой специальный оператор~-- это \lstinline{QUOTE}, который получает одно
выражение как аргумент и просто возвращает его, не вычисляя. Например, следующая форма
вычисляется в список \lstinline{(+ 1 2)}, а не в значение 3:
\begin{myverb}
(quote (+ 1 2))
\end{myverb}
Этот список не отличается ни от какого другого, вы можете манипулировать им так же, как и
любым другим, который вы можете создать с помощью функции
\lstinline{LIST}\pclfootnote{Хорошо, одно отличие существует~-- объекты-литералы, такие как
закавыченные списки, литералы строк, массивов и векторов (синтаксис которых мы рассмотрим
позднее), не должны модифицироваться. Поэтому любые списки, которыми вы собираетесь
манипулировать, вы должны создавать с помощью функции \lstinline{LIST}.}.
\lstinline{QUOTE} используется достаточно часто, поэтому для него в процедуру чтения был
встроен специальный синтаксис. Вместо написания такого:
\begin{myverb}
(quote (+ 1 2))
\end{myverb}
\noindent{}вы можете написать это:
\begin{myverb}
'(+ 1 2)
\end{myverb}
Этот синтаксис является небольшим расширением синтаксиса s-выражений, понимаемым
процедурой чтения. С этой точки зрения для процедуры вычисления оба этих выражения
выглядят одинаково: список, чей первый элемент является символом \lstinline{QUOTE}, а второй
элемент~-- список \lstinline{(+ 1 2)}\pclfootnote{Этот синтаксис является примером макроса
процедуры чтения. Эти макросы используются для модификации синтаксиса процедуры чтения,
который используется для трансляции текста в объекты Lisp. Фактически можно
определить собственный макрос процедуры чтения, но это редко используемая возможность
языка. Когда большинство лисперов говорят о <<расширении синтаксиса>> языка, они говорят
об обычных макросах, которые я скоро буду обсуждать.}.
В~общем, специальные операторы реализуют возможности языка, которые требуют специальной
обработки процедурой вычисления. Например, некоторые специальные операторы манипулируют
окружением, в котором вычисляются другие формы. Один из них, который я буду обсуждать детально в
главе~\ref{ch:06},~-- \lstinline{LET}, который используется для создания новой \textit{привязки
переменной} (\textit{variable binding}). Следующая форма вычисляется в 10, так как
второй x вычисляется в окружении, где он именует переменную, связанную оператором
\lstinline{LET} со значением 10:
\begin{myverb}
(let ((x 10)) x)
\end{myverb}
\section{Макросы}
В~то время как специальные операторы расширяют синтаксис Common Lisp, выходя за пределы
того, что может быть выражено простыми вызовами функций, множество специальных операторов
ограничено стандартом языка. С другой стороны, макросы дают пользователям языка способ
расширения его синтаксиса. Как вы увидели в главе~\ref{ch:03}, макрос~-- это функция, которая
получает в качестве аргументов s-выражения и возвращает форму Lisp, которая затем
вычисляется на месте формы макроса. Вычисление формы макроса происходит в две фазы:
сначала элементы формы макроса передаются, не вычисляясь, в функцию макроса, а затем
форма, возвращённая функцией макроса (называемая её \textit{раскрытием}
(\textit{expansion})), вычисляется в соответствии с обычными правилами вычисления.
Очень важно понимать обе фазы вычисления форм макросов. Очень легко запутаться, когда вы
печатаете выражения в REPL, так как эти две фазы происходят одна за одной и значение
второй фазы немедленно возвращается. Но, когда код Lisp компилируется, эти две фазы
выполняются в разное время, и очень важно понимать, что и когда происходит. Например,
когда вы компилируете весь файл с исходным кодом с помощью функции \lstinline{COMPILE-FILE},
все формы макросов в файле рекурсивно раскрываются, пока код не станет содержать ничего,
кроме форм вызова функций и специальных форм. Этот не содержащий макросов код затем
компилируется в файл FASL, который функция \lstinline{LOAD} знает, как
загрузить. Скомпилированный код, однако, не выполняется, пока файл не будет загружен. Так
как макросы раскрываются во время компиляции, они могут проделывать довольно
большой объём работы, генерируя свои раскрытия, без платы за это во время загрузки файла
или при вызове функций, определённых в этом файле.
Так как процедура вычисления не вычисляет элементы формы макроса перед передачей их в
функцию макроса, они не обязательно должны быть правильными формами Lisp. Каждый макрос
назначает смысл s-выражениям, используемым в \textit{форме} этого макроса (macro form),
посредством того, как он использует эти s-выражения для своего раскрытия. Другими словами,
каждый макрос определяет свой собственный локальный синтаксис. Например, макрос
переворачивания списка задом наперёд из главы~\ref{ch:03} определяет синтаксис, в котором
выражение является допустимой перевёрнутой формой, если её список, будучи перевёрнутым,
является допустимой формой Lisp.
Я расскажу больше о макросах в этой книге. А сейчас вам важно понимать, что макросы,
несмотря на то, что синтаксически похожи на вызовы функции, служат иной цели, предоставляя
добавочный уровень к компилятору\pclfootnote{Люди, не имеющие опыта использования макросов
Lisp или, хуже того, испорченные препроцессором C, часто нервничают, когда понимают, что
вызовы макросов выглядят так же, как обычные вызовы функций. Но на практике это не
является проблемой по нескольким причинам. Одной из них является то, что формы макросов
обычно форматируются не так, как вызовы функций. Например, вы пишете так:
\begin{myverb}
(dolist (x foo)\\
\hphantom{(d}(print x))
\end{myverb}
\noindent{}а не так
\begin{myverb}
(dolist (x foo) (print x))
\end{myverb}
\noindent{}или
\begin{myverb}
(dolist (x foo)\\
\hphantom{(dolist}(print x))
\end{myverb}
\noindent{}как в случае, если бы \lstinline{DOLIST} была функцией. Хорошая Lisp-среда автоматически
форматирует вызовы макросов, в том числе макросы, определённые пользователем.
И даже если форма \lstinline{DOLIST} была записана в одной строке, есть несколько вещей,
указывающих на то, что это макрос. Одной из них является то, что выражение (\lstinline{x}
\lstinline{foo}) имеет смысл, только если \lstinline{x} является именем функции или макроса. Если
учитывать то, что до этого \lstinline{x} использовалась как переменная, то становится
очевидным, что \lstinline{DOLIST}~-- это макрос, который связывает переменную \lstinline{x} с
какими-то значениями. Соглашение по именованию также помогает~-- конструкции циклов,
являю\-щие\-ся макросами, часто называют именами, начинающимися с \textit{do}.}.
\section{Истина, ложь и равенство}
Оставшейся частью базовых знаний, которые вам необходимо получить, являются понятия
истины, лжи и равенства объектов в Common Lisp. Понятия истины и лжи очень просты: символ
\lstinline{NIL} является единственным ложным значением, а все остальное является
истиной. Символ \lstinline{T} является каноническим истинным значением и может быть
использован, когда вам нужно вернуть не \lstinline{NIL}-значение, но само значение не
важно. Единственной хитростью является то, что \lstinline{NIL} также является единственным
объектом, который одновременно является и атомом, и списком: вдобавок к представлению
ложного значения он также используется для представления пустого
списка\pclfootnote{Использование пустого списка как ложного значения является отражением
наследия Lisp как языка обработки списков, аналогично использованию целочисленного 0, в
качестве ложного значения в С, что является отражением С как языка, предназначенного в
том числе для манипуляций на уровне битов. Не все Lisp'ы оперируют булевыми значениями
таким образом. Ещё одним из многочисленных отличий, из-за которого хороший флейм Common
Lisp vs Scheme может не утихать целыми днями, является наличие в Scheme отдельного
ложного значения \lstinline{#f}, что не является тем же значением, что \lstinline{nil} или пустой
список, которые также отличны друг от друга.}. Эта равнозначность \lstinline{NIL} и пустого
списка встроена в процедуру чтения: если процедура чтения видит \lstinline{()}, она считывает
это как символ \lstinline{NIL}. Обе записи полностью взаимозаменяемые. И так как
\lstinline{NIL}, как я уже упоминал раньше, является именем константной переменной, значением
которой является символ \lstinline{NIL}, то выражения \lstinline{nil}, \lstinline{()}, \lstinline{ 'nil} и
\lstinline{ '()} вычисляются в одинаковый объект: unquoted-формы вычисляются как ссылка на
константную переменную, значение которой~-- символ \lstinline{NIL}, а quoted-формы, при
помощи оператора \lstinline{QUOTE}, вычисляются в символ \lstinline{NIL} напрямую. По этим же
причинам и \lstinline{t}, и \lstinline{'t} будут вычислены в одинаковый объект: символ \lstinline{T}.
Использование фраз, таких как <<то же самое>>, конечно, рождает вопрос о том, что для двух
значений значит <<то же самое>>. Как вы увидите в следующих главах, Common Lisp
предоставляет ряд типозависимых предикатов равенства: \lstinline{=} используется для сравнения
чисел; \lstinline{CHAR=} для сравнения знаков и т.~д. В~этом разделе мы рассмотрим четыре <<общих>>
(<<generic>>) предиката равенства~-- функции, которым могут быть переданы два Lisp-объекта
и которые возвратят истину, если эти объекты эквивалентны, и ложь в противном случае. Вот
они в порядке ослабления понятия <<различности>>: \lstinline{EQ}, \lstinline{EQL}, \lstinline{EQUAL},
и \lstinline{EQUALP}.
\lstinline{EQ} проверяет <<идентичность объектов>>: она возвращает истинное значение, если
два объекта идентичны. К сожалению, понятие идентичности таких объектов, как числа и
знаки, зависит от того, как эти типы данных реализованы в конкретной реализации
Lisp. Таким образом, \lstinline{EQ} может считать два числа или два знака с одинаковым
значением как эквивалентными, так и нет. Стандарт языка оставляет реализациям достаточную
свободу действий в этом вопросе, что приводит к тому, что выражение \lstinline{(EQ 3 3)}
может вполне законно вычисляться как в истинное, так и в ложное значение. Таким же образом
\lstinline{(EQ x x)} может вычисляться как в истинное, так и в ложное значение в различных
реализациях, если значением x является число или знак.
Поэтому вы никогда не должны использовать \lstinline{EQ} для сравнения значений, которые
могут оказаться числами или знаками. Может показаться, что она вполне предсказуемо
работает для некоторых значений в конкретной реализации, но вы не можете гарантировать,
что она будет работать таким же образом, если вы смените реализацию. К~тому же смена
реализации может означать просто обновление вашей реализации до новой версии: если
конструкторы вашей реализации изменили внутреннее представление чисел или знаков, то
поведение \lstinline{EQ} вполне могло измениться.
Поэтому Common Lisp определяет \lstinline{EQL}, работающую аналогично \lstinline{EQ}, за
исключением того, что она также гарантирует рассмотрение эквивалентными двух объектов
одного класса, представляющих одинаковое числовое или знаковое (character)
значение. Поэтому \lstinline{(EQL 1 1)} гарантированно будет истиной. А \lstinline{(EQL 1 1.0)}
гарантированно будет ложью, так как целое значение~1 и значение с плавающей точкой~1.0
являются представителями различных классов.
Существуют два лагеря по отношению к вопросу, где использовать \lstinline{EQ} и где
использовать \lstinline{EQL}: сторонники <<когда возможно, всегда используйте \lstinline{EQ}>>
убеждают вас использовать \lstinline{EQ}, когда вы уверены, что не будете сравнивать числа
или знаки, так как:
\begin{enumerate}
\item это способ указать, что вы не собираетесь сравнивать числа и знаки;
\item это будет немного эффективнее, поскольку \lstinline{EQ} не нужно проверять, являются
ли её аргументы числами или знаками.
\end{enumerate}
Сторонники <<всегда используйте \lstinline{EQL}>> советуют вам никогда не использовать
\lstinline{EQ}, так как:
\begin{enumerate}
\item потенциальный выигрыш в ясности теряется, поскольку каждый раз, когда кто-либо
будет читать ваш код (включая вас) и увидит \lstinline{EQ}, он должен будет остановиться и
проверить, корректно ли эта функция используется (другими словами, проверить, что она
никогда не вызывается для сравнения цифр или знаков), и
\item различие в эффективности между \lstinline{EQ} и \lstinline{EQL} очень мало, по
сравнению с производительностью в действительно узких местах.
\end{enumerate}
Код в этой книге написан в стиле <<всегда используйте \lstinline{EQL}>>\pclfootnote{Даже стандарт
языка немного неоднозначен, \lstinline{EQ} или \lstinline{EQL} отдать предпочтение. Тождество
объектов определяется с помощью \lstinline{EQ}, но стандарт определяет фразу <<такой же>>,
говоря об объектах, имея в~виду \lstinline{EQL}, если другой предикат явно не
упомянут. Поэтому, если вы хотите быть НА 100\% технически корректны, вы можете говорить,
что \lstinline{(- 3 2)} и \lstinline{(- 4 3)} вычисляются в <<такой же>> объект, но не то, что они
вычисляюся в <<идентичные>> объекты. Это, по общему признанию, вопрос из разряда <<сколько
ангелов разместится на острие булавки>>.}.
Другие два предиката равенства \lstinline{EQUAL} и \lstinline{EQUALP} являются общими в том
смысле, что они могут оперировать всеми типами объектов, но они не настолько
фундаментальные, как \lstinline{EQ} или \lstinline{EQL}. Каждый из них определяет несколько
более слабое понятие <<различности>>, чем \lstinline{EQL}, позволяя другим объектам считаться
эквивалентным. Нет ничего особенного в тех конкретных понятиях эквивалентности, что
реализуют эти функции, за исключением того, что они оказались полезными Lisp-программистам
прошлого. Если эти предикаты не подходят вам, вы всегда можете определить свой собственный
предикат для сравнения объектов других типов нужным вам способом.
\lstinline{EQUAL} ослабляет понятие <<различности>> между \lstinline{EQL}, считая списки
эквивалентными, если они рекурсивно, согласно тому же \lstinline{EQUAL}, имеют одинаковую
структуру и содержимое. \lstinline{EQUAL} также считает строки эквивалентными, если они
содержат одинаковые знаки. \lstinline{EQUAL} также ослабляет понятие <<различности>>, по
сравнению с \lstinline{EQL}, для битовых векторов (bit vectors) и путей~-- двух типов, о
которых я расскажу в следующих главах. Для всех остальных типов он аналогичен
\lstinline{EQL}.
\lstinline{EQUALP} аналогична \lstinline{EQUAL}, за исключением ещё большего ослабления понятия
<<различности>>. \lstinline{EQUALP} считает две строки эквивалентными, если они имеют
одинаковые знаки, игнорируя разницу в регистре. Два знака также считаются эквивалентными,
если они отличаются только регистром. Числа эквивалентны по \lstinline{EQUALP}, если они
представляют одинаковое математическое значение. Например, \lstinline{(equalp 1 1.0)} вернёт
истину. Списки, элементы которых попарно эквивалентны по \lstinline{EQUALP}, считаются
эквивалентными; подобным же образом массивы с элементами, эквивалентными по
\lstinline{EQUALP}, также считаются эквивалентными. Как и в случае с \lstinline{EQUAL},
существует несколько других типов данных, которые я пока не рассмотрел, для которых
\lstinline{EQUALP} может рассмотреть два объекта эквивалентными, в то время как \lstinline{EQL}
и \lstinline{EQUAL} будут считать их различными. Для всех остальных типов данных
\lstinline{EQUALP} аналогична \lstinline{EQL}.
\section{Форматирование кода Lisp}
Хотя форматирование кода, строго говоря, не имеет ни синтаксического, ни семантического
значения, хорошее форматирование важно для лёгкого чтения и написания кода. Ключевым
моментом в форматировании кода Lisp является правильная расстановка отступов. Отступы
должны отражать структуру кода так, чтобы вам не пришлось считать скобки для его
понимания. Вообще, каждый новый уровень вложенности должен иметь больший отступ, а если
нужен перенос строки, то элементы следующей строки имеют тот же уровень вложенности, что и
предыдущей. Таким образом, вызов функции, который должен быть разбит на несколько строк,
может быть записан следующим образом:
\begin{myverb}
(some-function arg-with-a-long-name
another-arg-with-an-even-longer-name)
\end{myverb}
Расстановка отступов в макросах и специальных формах, которые реализуют структуры
контроля, обычно немного отличается: элементы <<тела>> отступаются на два пробела
относительно открывающей скобки формы. Таким образом:
\begin{myverb}
(defun print-list (list)
(dolist (i list)
(format t "item: ~a~%" i)))
\end{myverb}
Однако вам не нужно сильно беспокоиться на счёт этих правил, так как хорошая среда Lisp,
такая как SLIME, возьмёт эту заботу на себя. Фактически одним из преимуществ регулярного
синтаксиса Lisp является то, что программному обеспечению, такому как текстовые редакторы,
очень легко расставлять отступы. Поскольку расстановка отступов нужна для отражения
структуры кода, а структура определяется скобками, легко позволить редактору расставить
отступы вместо вас.
В~SLIME нажатие Tab в начале каждой строки приводит к тому, что строка будет правильно
выровнена; также вы можете перевыровнять целое выражение, поставив курсор на открывающую
скобку и набрав C-M-q. Или вы можете перевыровнять все тело функции, набрав C-c M-q,
находясь где угодно в теле функции.
На самом деле опытный Lisp-программист предпочитает полагаться на текстовый редактор,
который обработает отступы автоматически, не только для того, чтобы код выглядел красиво,
но и для обнаружения опечаток: как только вы привыкнете к правильной расстановке отступов
в коде, так сразу начнёте легко обнаруживать пропуск необходимой скобки по странной
расстановке отступов вашим редактором. Например, предположим, что вы написали следующую
функцию:
\begin{myverb}
(defun foo ()
(if (test)
(do-one-thing)
(do-another-thing)))
\end{myverb}
Теперь предположим, что вы случайно не поставили закрывающую скобку после
\lstinline{test}. Поскольку вы не обеспокоены подсчётом скобок, вы просто добавите ещё одну в
конец формы \lstinline{DEFUN}, получив следующий код:
\begin{myverb}
(defun foo ()
(if (test
(do-one-thing)
(do-another-thing))))
\end{myverb}
Однако, если вы выравнивали код, нажимая Tab в начале каждой строки, вы не получите
вышеприведённого кода. Вместо него вы получите это:
\begin{myverb}
(defun foo ()
(if (test
(do-one-thing)
(do-another-thing))))
\end{myverb}
Выравнивание веток \lstinline{then} и \lstinline{else}, перенесённых под условие, вместо того чтобы
находиться чуть правее \lstinline{IF}, немедленно говорит нам, что что-то не так.
Другое важное правило форматирования заключается в том, что закрывающие скобки всегда
помещаются в той же строке, что и последний элемент списка, который они закрывают. Так что
не пишите так:
\begin{myverb}
(defun foo ()
(dotimes (i 10)
(format t "~d. hello~%" i)
)
)
\end{myverb}
\noindent{}Правильный вариант:
\begin{myverb}
(defun foo ()
(dotimes (i 10)
(format t "~d. hello~%" i)))
\end{myverb}
Строка \lstinline{)))} в конце может казаться некрасивой, но когда ваш код имеет правильные
отступы, скобки должны уходить на второй план. Не нужно привлекать к ним несвоевременное
внимание, располагая их на нескольких строках.
И наконец, комментарии должны предваряться от одной до четырёх точек с запятой, в
зависимости от контекста появления этого комментария:
\begin{myverb}
;;;; Четыре точки с запятой для комментария в начале файла
;;; Комментарий из трёх точек с запятой обычно является параграфом комментариев,
;;; который предваряет большую секцию кода
(defun foo (x)
(dotimes (i x)
;; Две точки с запятой показывают, что комментарий применён к последующему коду.
;; Заметьте, что этот комментарий имеет такой же отступ, как и последующий код.
(some-function-call)
(another i) ; этот комментарий применим только к этой строке
(and-another) ; а этот для этой строки
(baz)))
\end{myverb}
Теперь вы готовы начать более детально рассматривать важнейшие строительные блоки программ
Lisp: функции, переменные и макросы. Следующим шагом станут функции.
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "pcl-ru"
%%% TeX-open-quote: "<<"
%%% TeX-close-quote: ">>"
%%% End: