-
Notifications
You must be signed in to change notification settings - Fork 9
/
chapter-1.tex
5125 lines (4603 loc) · 352 KB
/
chapter-1.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
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%43
\chapter{Построение абстракций~с помощью процедур}
\label{BUILDING-ABSTRACTIONS-WITH-PROCEDURES}
%\markboth{Глава 1 \qquad Построение абстракций~с помощью процедур}{}
\thispagestyle{empty}
\epigraph{
Действия, в которых ум проявляет свои способности в отношении
своих простых идей, суть главным образом следующие три: 1)~Соединение
нескольких простых идей в одну сложную; так образовались все сложные
идеи, 2)~Сведение вместе двух идей, все равно, простых или сложных, и
сопоставление их друг с другом так, чтобы обозревать их сразу, но не
соединять в одну; так ум приобретает все свои идеи отношений, 3)~Обособление
идей от всех других идей, сопутствующих им в реальной
действительности; это действие называется <<абстрагированием>>, и при
его помощи образованы все общие идеи в уме.
\index{ru}{Локк, Джон||John Locke||n|}%
\index{en}{John Locke||Локк, Джон||n|}%
\index{ru}{Савин,~А.Н.||||n|}}%
{Джон Локк. \\
%\textit{
<<Опыт~о человеческом разуме>> (1690) \\ %}
(Перевод А.Н.~Савина)}
Мы собираемся изучать понятие
\index{ru}{процесс||process|||}\index{en}{process||процесс|||}%
\index{ru}{вычислительный процесс||computational process|||}\index{en}{computational process||вычислительный процесс|||}{\em вычислительного процесса} (com\-pu\-ta\-ti\-o\-nal process).
Вычислительные процессы --- это абстрактные
существа, которые живут~в компьютерах. Развиваясь, процессы
манипулируют абстракциями другого типа, которые называются
\index{ru}{данные||data|||}\index{en}{data||данные|||}{\em дан\-ными} (data). Эволюция процесса направляется набором
правил, называемым \index{ru}{программа||program|||}\index{en}{program||программа|||}{\em программой} (program).~В сущности, мы
заколдовываем духов компьютера~с помощью своих чар.
Вычислительные процессы~и вправду вполне соответствуют представлениям
колдуна~о д\'{у}хах. Их нельзя увидеть или
потрогать. Они вообще сделаны не из вещества. В то же время они
совершенно реальны. Они могут выполнять умственную работу, могут
отвечать на вопросы. Они способны воздействовать на внешний мир,
оплачивая счета~в банке или управляя рукой робота на заводе.
Программы, которыми мы пользуемся для заклинания процессов, похожи
на чары колдуна. Они тщательно составляются из символических
выражений на сложных~и немногим известных \index{ru}{язык программирования||programming language|||}\index{en}{programming language||язык программирования|||}{\em языках
программирования} (programming languages), описывающих задачи, которые мы хотим
поручить процессам.
На исправно работающем компьютере вычислительный процесс
выполняет программы точно~и безошибочно. Таким образом, подобно
ученику чародея, про\-грам\-мис\-ты-но\-вич\-ки должны научиться понимать и
предсказывать последствия своих заклинаний. Даже мелкие ошибки
(их обычно называют\index{ru}{блоха||bug|||}\index{en}{bug||блоха|||} {\em блохами} (bugs)
или {\em глюками} (glitches))\index{ru}{глюк||glitch|||}\index{en}{glitch||глюк|||}, могут привести~к сложным~и
непредсказуемым последствиям.
К счастью, обучение программированию не так опасно, как
обучение колдовству, поскольку духи,~с которыми мы имеем дело, надежно
связаны. В то же время программирование~в реальном мире
требует осторожности, профессионализма~и мудрости. Например, мелкая
ошибка в программе автоматизированного проектирования может привести~к
катастрофе самолета, прорыву плотины или самоуничтожению промышленного
робота.
Специалисты по программному обеспечению умеют организовывать
программы так, чтобы быть потом обоснованно уверенными:
получившиеся процессы будут выполнять те задачи, для которых они
предназначены. Они могут изобразить поведение системы заранее. Они
знают, как построить программу так, чтобы непредвиденные проблемы не
привели~к катастрофическим последствиям,~а когда эти проблемы
возникают, программисты умеют \index{ru}{отладка||debugging|||}\index{en}{debugging||отладка|||}{\em отлаживать} (debug) свои
программы.
Хорошо спроектированные вычислительные системы, подобно хорошо
спроектированным автомобилям или ядерным реакторам, построены модульно,
так что их части могут создаваться, заменяться~и отлаживаться по
отдельности.
\paragraph{Программирование на Лиспе}
Для описания процессов нам нужен подходящий язык,~и~с этой
целью мы используем язык программирования Лисп. Точно так же, как
обычные наши мысли чаще всего выражаются на естественном языке
(например, английском, французском или японском),~а описания
количественных явлений выражаются языком математики, наши процедурные
мысли будут выражаться на Лиспе. \index{ru}{Lisp (Лисп)|история||||} Лисп был изобретен~в конце 1950-х как
формализм для рассуждений об определенном типе логических выражений,
называемых \index{ru}{уравнения рекурсии||recursion equations|||}\index{en}{recursion equations||уравнения рекурсии|||}{\em уравнения рекурсии} (recursion equations), как~о модели
вычислений. Язык был придуман Джоном Маккарти
\index{ru}{Маккарти, Джон||John McCarthy||n|}\index{en}{John McCarthy||Маккарти, Джон||n|}
и основывается на его
статье <<Рекурсивные функции над символьными выражениями~и их
вычисление~с помощью машины>> (McCarthy 1960).
Несмотря на то, что Лисп возник как математический
формализм, это практический язык программирования.
\index{ru}{интерпретатор||interpreter|||}\index{en}{interpreter||интерпретатор|||}{\em Интерпретатор} (interpreter) Лиспа представляет
собой машину,
которая выполняет процессы, описанные на языке Лисп.
Первый интерпретатор Лиспа написал сам Маккарти~с помощью
коллег~и студентов из Группы по Искусственному Интеллекту
\index{ru}{MIT|Исследовательская лаборатория по Электронике||||} Исследовательской лаборатории по Электронике MIT и
Вычислительного центра MIT\footnote{{\em Руководство программиста по Лиспу 1} появилось~в 1960 году,~а {\em Руководство
программиста по Лиспу~1.5} (McCarthy 1965)\index{ru}{Маккарти, Джон||John McCarthy||n|п}\index{en}{John McCarthy||Маккарти, Джон||n|п} в 1965 году. Ранняя история Лиспа описана~в
McCarthy 1978.
}.
\index{ru}{Lisp (Лисп)|сокращение от LISt Processing||||}%
Лисп, чье название происходит от сокращения английских слов LISt
Processing (обработка списков), был создан~с целью обеспечить
возможность символьной обработки для решения таких программистских
задач, как символьное дифференцирование~и интегрирование
алгебраических выражений.~С этой целью он содержал новые объекты данных,
известные под названием атомов~и списков, что резко отличало его от
других языков того времени.
Лисп не был результатом срежиссированного проекта.
Он развивался не\-фор\-маль\-но, экспериментальным путем,~с учетом
запросов пользователей~и прагматических соображений реализации.
Неформальная эволюция Лиспа продолжалась долгие годы,~и сообщество
пользователей Лиспа традиционно отвергало попытки провозгласить
какое-либо <<официальное>> описание языка. Вместе~с гибкостью и
изяществом первоначального замысла такая эволюция позволила Лиспу,
который сейчас по возрасту второй из широко используемых языков (старше только
\index{ru}{Fortran (Фортран)|||||}Фортран), непрерывно адаптироваться~и вбирать~в себя
наиболее современные идеи~о проектировании программ. Таким образом,
сегодня Лисп представляет собой семью диалектов, которые, хотя и
разделяют большую часть изначальных свойств, могут существенным
образом друг от друга отличаться. Тот диалект, которым мы пользуемся~в
этой книге, называется
\index{ru}{диалекты Лиспа|Scheme (Схема)|Lisp
dialects|||}\index{en}{Lisp dialects||диалекты Лиспа|Scheme
(Схема)||}\index{ru}{Scheme (Схема)|||||}Scheme
(Схема)\footnote{Большинство крупных
Лисп-программ 1970х, были написаны на одном из двух диалектов:
\index{ru}{диалекты Лиспа|MacLisp (МакЛисп)||||п}\index{ru}{MacLisp (МакЛисп)|||||п}MacLisp
(Moon 1978;\index{ru}{Мун, Дэвид~А.||David~A. Moon||n|п}\index{en}{David~A. Moon||Мун, Дэвид~А.||n|п} Pitman 1983),\index{ru}{Питман, Кент||Kent Pitman||n|п}\index{en}{Kent Pitman||Питман, Кент||n|п}
разработанный~в рамках
\index{ru}{MIT|проект MAC||||п}проекта MAC~в MIT, и
\index{ru}{диалекты Лиспа|InterLisp (ИнтерЛисп)||||п}\index{ru}{InterLisp (ИнтерЛисп)|||||п}%
InterLisp (Teitelman 1974),\index{ru}{Тейтельман, Уоррен||Warren
Teitelman||n|п}\index{en}{Warren Teitelman||Тейтельман, Уоррен||n|п}
разработанный~в компании <<Болт, Беранек~и Ньюман>>\index{ru}{<<Болт,
Беранек~и Ньюман>>||Bolt, Beranek and Newman,
inc.||n|п}\index{en}{Bolt, Beranek and Newman, inc.||<<Болт, Беранек
и Ньюман>>||n|п}
и~в
\index{ru}{Xerox, исследовательский центр~в Пало Альто||Xerox Palo
Alto Research Center|||п}\index{en}{Xerox Palo Alto Research
Center||Xerox, исследовательский центр~в Пало
Альто|||п}Исследовательском центре компании Xerox~в Пало
Альто. Диалект
\index{ru}{диалекты Лиспа|Portable Standard Lisp (Переносимый
Стандартный Лисп)||||п}\index{ru}{Portable Standard Lisp
(Переносимый Стандартный Лисп)|||||п}Portable Standard Lisp
(Переносимый Стандартный Лисп,
Hearn 1969; Griss 1981)\index{ru}{Грисс, Мартин Льюис||Martin Lewis
Griss||n|п}\index{en}{Martin Lewis Griss||Грисс, Мартин
Льюис||n|п}\index{ru}{Херн,
Энтони~К.||Anthony~C. Hearn||n|п}\index{en}{Anthony~C. Hearn||Херн,
Энтони~К.||n|п}
был спроектирован так, чтобы его легко было переносить на разные
машины. MacLisp породил несколько поддиалектов, например
\index{ru}{диалекты Лиспа|Franz Lisp (Франц
Лисп)||||п}\index{ru}{Franz Lisp (Франц Лисп)|||||п}Franz Lisp, разработанный~в
\index{ru}{Калифорнийский университет~в Беркли||University of
California at Berkeley|||п}\index{en}{University of California at
Berkeley||Калифорнийский университет~в Беркли|||п}Калифорнийском университете~в Беркли,~и
\index{ru}{диалекты Лиспа|Zetalisp (Зеталисп)||||п}\index{ru}{Zetalisp
(Зеталисп)|||||п}Zetalisp (Moon 1981), который основывался на
специализированном процессоре, спроектированном~в
\index{ru}{MIT|лаборатория Искусственного Интеллекта||||п}лаборатории
Искусственного Интеллекта~в MIT для наиболее эффективного
выполнения программ на Лиспе. Диалект Лиспа, используемый~в этой книге,
называется
\index{ru}{Scheme (Схема)|история||||п}Scheme (Steele 1975). Он был изобретен в
1975 году Гаем Льюисом Стилом мл.~и Джеральдом Джеем
Сассманом\index{ru}{Стил, Гай Льюис мл.||Guy Lewis Steele
Jr.||n|п}\index{en}{Guy Lewis Steele Jr.||Стил, Гай Льюис
мл.||n|п}\index{ru}{Сассман, Джеральд Джей||Gerald Jay
Sussman||n|п}\index{en}{Gerald Jay Sussman||Сассман, Джеральд
Джей||n|п}
в лаборатории Искусственного Интеллекта MIT,~а затем заново реализован
для использования~в учебных целях~в MIT. Scheme стала стандартом IEEE
в 1990 году (IEEE 1900). Диалект
\index{ru}{диалекты Лиспа|Common Lisp||||п}\index{ru}{Common
Lisp|||||п}Common Lisp (Steele 1982; Steele 1990)
был специально разработан Лисп-сообществом так, чтобы сочетать свойства более
ранних диалектов Лиспа~и стать промышленным стандартом Лиспа. Common
Lisp стал стандартом ANSI~в 1994 году (ANSI 1994).
}.
Из-за своего экспериментального характера~и внимания к
символьной обработке первое время\index{ru}{Lisp (Лисп)|эффективность||||}\index{ru}{эффективность|Лиспа||||} Лисп был весьма неэффективен при решении вычислительных задач, по крайней мере по сравнению~с
\index{ru}{Lisp (Лисп)|vs. Фортран||||} Фортраном.
Однако за прошедшие годы были разработаны компиляторы Лиспа, которые
переводят программы~в машинный код, способный производить численные
вычисления~с разумной эффективностью. А для специализированных
приложений Лисп удавалось использовать весьма эффективно\footnote{Одним из таких приложений был пионерский эксперимент,
имевший научное значение --- интегрирование движения Солнечной системы,
которое превосходило по точности предыдущие результаты примерно на два
порядка~и продемонстрировало, что
\index{ru}{хаос~в динамике Солнечной системы||chaos in Solar
system|||п}\index{en}{chaos in Solar system||хаос~в динамике
Солнечной системы|||п}динамика Солнечной системы хаотична.
Это вычисление стало возможным благодаря новым алгоритмам
интегрирования, специализированному компилятору~и специализированному
компьютеру; причем все они были реализованы~с помощью программных
средств, написанных на Лиспе (Abelson et al. 1992;
Sussman and Wisdom 1992).\index{ru}{Абельсон, Харольд||Harold
Abelson||n|п}\index{en}{Harold Abelson||Абельсон,
Харольд||n|п}\index{ru}{Сассман, Джеральд Джей||Gerald Jay
Sussman||n|п}\index{en}{Gerald Jay Sussman||Сассман, Джеральд
Джей||n|п}\index{ru}{Уиздом, Джек||Jack Wisdom||n|п}\index{en}{Jack
Wisdom||Уиздом, Джек||n|п}
}.
Хотя Лисп~и не преодолел пока свою старую репутацию безнадежно
медленного языка,~в наше время он используется во многих
приложениях, где эффективность не является главной заботой. Например,
Лисп стал любимым языком для оболочек операционных систем,~а также в
качестве языка расширения для редакторов~и систем автоматизированного
проектирования\-.
Но коль скоро Лисп не похож на типичные языки, почему же мы тогда
используем его как основу для нашего разговора~о программировании?
\index{ru}{Lisp (Лисп)|уникальные свойства||||}
Потому что этот язык обладает уникальными свойствами, которые делают
его замечательным средством для изучения важнейших конструкций
программирования~и структур данных,~а также для соотнесения их с
деталями языка, которые их поддерживают. Самое существенное из этих свойств~--- то, что лисповские описания процессов, называемые
\index{ru}{процедура||procedure|||}\index{en}{procedure||процедура|||}{\em процедурами} (procedures)\index{ru}{процедура|как данные||||}, сами по себе могут
представляться~и
обрабатываться как данные Лиспа.
Важность этого~в том, что существуют мощные методы проектирования
программ, которые опираются на возможность сгладить традиционное
различение <<пассивных>> данных~и <<активных>> процессов.
Как мы обнаружим, способность Лиспа рассматривать процедуры~в качестве
данных делает его одним из самых удобных языков для исследования этих
методов. Способность представлять процедуры~в качестве данных делает Лисп
еще~и замечательным языком для написания программ, которые должны
манипулировать другими программами~в качестве данных, таких как
интерпретаторы~и компиляторы, поддерживающие компьютерные языки. А
помимо~и превыше всех этих соображений, писать программы на Лиспе~---
громадное удовольствие.
\section{Элементы программирования}
\label{THE-ELEMENTS-OF-PROGRAMMING}
\index{ru}{программирование|элементы||||}
Мощный язык программирования~--- это нечто большее. чем
просто средство,~с помощью которого можно учить компьютер решать
задачи. Язык также служит средой,~в которой мы организуем свое
мышление~о процессах. Таким образом, когда мы описываем язык, мы
должны уделять особое внимание тем средствам, которые в нем имеются
для того, чтобы комбинировать простые понятия~и получать
из них сложные. Всякий язык программирования обладает тремя
предназначенными для этого механизмами:
\begin{description}
\item[элементарные выражения,]\index{ru}{элементарные выражения||primitive expressions|||}\index{en}{primitive expressions||элементарные выражения|||}
представляющие минимальные сущности,~с
которыми язык имеет дело;
{\sloppy
}%HERE!
\item[средства комбинирования,]\index{ru}{средства комбинирования||means of cvombination|||}\index{en}{means of cvombination||средства комбинирования|||}
с помощью которых из простых объектов
составляются сложные;
\item[средства абстракции,]\index{ru}{средства абстракции||means of abstraction|||}\index{en}{means of abstraction||средства абстракции|||}
с помощью которых сложные объекты можно называть~и
обращаться~с ними как~с единым целым.
\sloppy
\end{description}
В программировании мы имеем дело~с двумя типами объектов:
\index{ru}{процедура|||||}процедурами~и\index{ru}{данные|||||} данными. (Впоследствии мы обнаружим, что на самом деле большой
разницы между ними нет.) Говоря неформально, данные~--- это
<<материал>>, который мы хотим обрабатывать, а процедуры~--- это
описания правил обработки данных. Таким образом, от любого мощного языка
программирования требуется способность описывать простые данные и
элементарные процедуры, а также наличие средств
комбинирования и абстракции процедур и данных.
В этой главе мы будем работать только~с простыми
\index{ru}{данные|численные||||}
\index{ru}{численные данные||numerical data|||}\index{en}{numerical data||численные данные|||}
численными данными, так что мы сможем сконцентрировать внимание на
правилах построения процедур\footnote{Называть числа <<простыми данными>>~--- это бесстыдный
блеф. На самом деле работа~с числами является одной из самых сложных
и запутанных сторон любого языка программирования. Вот некоторые из
возникающих при этом вопросов: Некоторые компьютеры отличают
\index{ru}{числа|целые vs. вещественные||||п}\index{ru}{целые
числа||integers|||п}\index{en}{integers||целые
числа|||п}\index{ru}{числа|целые|numbers|integer||п}\index{en}{numbers|integer|числа|целые||п}{\em целые числа} (integers), вроде 2, от
\index{ru}{числа|вещественные|numbers|real||п}\index{en}{numbers|real|числа|вещественные||п}{\em вещественных} (real numbers), вроде 2.71.
Отличается ли вещественное число 2.00 от целого 2? Используются ли
одни~и те же арифметические операции для целых~и для вещественных
чисел? Что получится, если 6 поделить на 2: 3 или 3.0? Насколько
большие числа мы можем представить? Сколько десятичных цифр после
запятой мы можем хранить? Совпадает ли диапазон целых чисел с
диапазоном вещественных? И помимо этих вопросов, разумеется,
существует множество проблем, связанных~с
\index{ru}{ошибка округления||roundoff error|||п}\index{en}{roundoff error||ошибка округления|||п}
ошибками округления --- целая наука
\index{ru}{численный анализ||numerical analysis|||п}\index{en}{numerical analysis||численный анализ|||п}
численного анализа.
Поскольку~в этой книге мы говорим о
проектировании больших программ,~а не~о численных методах, все эти
проблемы мы будем игнорировать. Численные примеры~в этой главе будут
демонстрировать такое поведение при округлении, какое можно наблюдать,
если использовать арифметические операции, сохраняющие при работе с
вещественными числами ограниченное число десятичных цифр после
запятой.
}.
В последующих главах мы увидим, что те же самые правила позволяют
нам строить процедуры для работы со сложными данными.
\subsection{Выражения}
\label{EXPRESSIONS}
Самый простой способ начать обучение
программированию --- рассмотреть несколько типичных
примеров работы~с интерпретатором диалекта Лиспа Scheme.
Представьте, что Вы сидите за терминалом компьютера. Вы печатаете
\index{ru}{выражение||expression|||}\index{en}{expression||выражение|||}{\em выражение} (expression),~а интерпретатор отвечает, выводя
результат \index{ru}{вычисление||evaluation|||}\index{en}{evaluation||вычисление|||}{\em вычисления} (evaluation) этого выражения.
\index{ru}{числа|в Лиспе|numbers|||}\index{en}{numbers||числа|в Лиспе||}
Один из типов\index{ru}{элементарные выражения|числа||||} элементарных выражений, которые Вы можете вводить ---
это числа. (Говоря точнее, выражение, которое Вы печатаете, состоит
из цифр, представляющих число по основанию 10.) Если Вы дадите Лиспу
число
\begin{Verbatim}[fontsize=\small]
486
\end{Verbatim}
интерпретатор ответит Вам, напечатав\footnote{\index{ru}{нотация в
настоящей книге|наклонный шрифт для ответов
интерпретатора|notation in this book|||п}\index{en}{notation
in this book||нотация~в настоящей книге|наклонный шрифт для
ответов интерпретатора||п}Здесь~и далее, когда нам нужно
будет
подчеркнуть разницу между вводом, который набирает на терминале пользователь,~и выводом,
который производит компьютер, мы будем изображать последний наклонным
шрифтом.
}
\begin{Verbatim}[fontsize=\small]
\textit{486}
\end{Verbatim}
Выражения, представляющие числа, могут сочетаться
\index{ru}{комбинация|||||}с
\index{ru}{элементарные выражения|имя элементарной
процедуры||||}выражением, представляющим
\index{ru}{арифметика|элементарные
процедуры|arithmetic|||}\index{en}{arithmetic||арифметика|элементарные процедуры||}элементарную
процедуру (скажем,
{\tt +\index{ru}{+ (элементарная процедура сложения)||||pd|}\index{ru}{элементарные процедуры|{\tt +}||||}} или
{\tt *\index{ru}{элементарные процедуры|{\tt *}||||}\index{ru}{*
(элементарная процедура умножения)||||pd|}}), так что
получается\index{ru}{составное выражение||compound
expression|||}\index{en}{compound expression||составное
выражение|||}
составное выражение, представляющее собой применение процедуры~к этим
числам. Например:
{\sloppy
}
\begin{Verbatim}[fontsize=\small]
(+ 137 349)
\textit{486}
(- 1000 334)\index{ru}{элементарные процедуры|{\tt -}||||}
\textit{666}
(* 5 99)
\textit{495}
(/ 10 5)\index{ru}{элементарные процедуры|{\tt /}||||}
\textit{2}
(+ 2.7 10)
\textit{12.7}
\end{Verbatim}
\index{ru}{- (элементарная процедура вычитания)||||pd|}
\index{ru}{/ (элементарная процедура деления)||||pd|}
Выражения такого рода, образуемые путем заключения
списка выражений~в\index{ru}{скобки|обозначение применения функции~к аргументам||||} скобки~с целью обозначить применение
функции~к аргументам, называются
\index{ru}{применение процедур|обозначение комбинаций||||}
\index{ru}{комбинация||combination|||}\index{en}{combination||комбинация|||}{\em комбинациями} (combi\-na\-tions).
Самый левый элемент~в списке называется \index{ru}{оператор
комбинации|||||}\index{ru}{оператор комбинации||operator of a
combination|||}\index{en}{operator of a combination||оператор
комбинации|||}{\em оператором} (operator),~а остальные элементы~---
\index{ru}{операнды комбинации||operands of a
combination|||}\index{en}{operands of a combination||операнды
комбинации|||}{\em операндами} (operands).
\index{ru}{значение|комбинации|value|||}\index{en}{value||значение|комбинации||}Значение
комбинации вычисляется путем применения процедуры, задаваемой
оператором,~к \index{ru}{аргумент(ы)||argument(s)|||}\index{en}{argument(s)||аргумент(ы)|||}{\em аргументам} (arguments), которые являются
значениями операндов.
Соглашение, по которому оператор ставится слева от
операндов, известно как \index{ru}{префиксная нотация||prefix notation|||}\index{en}{prefix notation||префиксная нотация|||}{\em пре\-фикс\-ная нотация} (prefix notation), и
поначалу оно может сбивать~с толку, поскольку существенно
отличается от общепринятой математической записи. Однако~у префиксной нотации есть несколько преимуществ. Одно из них состоит~в том, что
префиксная запись может распространяться на процедуры~с
\index{ru}{аргумент(ы)|произвольное
количество||||}\index{ru}{процедура|произвольное количество
аргументов||||}произвольным количеством аргументов, как~в следующих
примерах:
\begin{Verbatim}[fontsize=\small]
(+ 21 35 12 7)
\textit{75}
(* 25 4 12)
\textit{1200}
\end{Verbatim}
Не возникает никакой неоднозначности, поскольку оператор
всегда находится слева,~а вся комбинация ограничена скобками.
Второе преимущество префиксной нотации состоит~в том,
что она естественным образом расширяется, позволяя комбинациям
\index{ru}{вложение комбинаций||nested
combinations|||}\index{en}{nested combinations||вложение
комбинаций|||}{\em вкладываться} (nest) друг~в друга, то есть
допускает
комбинации, элементы которых сами являются комбинациями:
\begin{Verbatim}[fontsize=\small]
(+ (* 3 5) (- 10 6))
\textit{19}
\end{Verbatim}
Не существует (в принципе) никакого предела для глубины
такого вложения~и общей сложности выражений, которые может вычислять
интерпретатор Лиспа. Это мы, люди, путаемся даже~в довольно простых
выражениях, например
\begin{Verbatim}[fontsize=\small]
(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))
\end{Verbatim}
а интерпретатор~с готовностью вычисляет его~и дает ответ 57. Мы
можем облегчить себе задачу, записывая такие выражения~в форме
\begin{Verbatim}[fontsize=\small]
(+ (* 3
(+ (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6))
\end{Verbatim}
Эти правила форматирования называются \index{ru}{красивая печать||pretty printing|||}\index{en}{pretty printing||красивая печать|||}{\em красивая
печать} (pretty printing). Согласно им, всякая длинная комбинация
записывается так, чтобы ее операнды выравнивались вертикально.
Получающиеся отступы ясно показывают структуру
выражения\footnote{\index{ru}{печать входных выражений||typing input
expressions|||п}\index{en}{typing input expressions||печать
входных выражений|||п}Как правило, Лисп-системы содержат средства,
которые помогают пользователям\index{ru}{форматирование входных
выражений||formatting input expressions|||п}\index{en}{formatting
input expressions||форматирование входных выражений|||п}
форматировать выражения. Особенно удобны две
возможности: сдвигать курсор на правильную позицию для красивой печати
каждый раз, когда начинается новая строка~и подсвечивать нужную левую
скобку каждый раз, когда печатается правая.}.
Даже работая со сложными выражениями, интерпретатор
всегда ведет себя одинаковым образом: он считывает выражение с
терминала, вычисляет его~и печатает результат.
\index{ru}{интерпретатор|цикл чтение-вычисление-печать||||}
Этот способ работы
иногда называют \index{ru}{цикл чтение-вычисление-печать||read-eval-print loop|||}\index{en}{read-eval-print loop||цикл чтение-вычисление-печать|||}{\em циклом
чтение-вычисление-печать} (read-eval-print loop).
Обратите особое внимание на то, что не нужно специально просить
интерпретатор напечатать значение выражения\footnote{\index{ru}{Lisp
(Лисп)|эффективность||||п}Лисп следует соглашению, что~у всякого
выражения есть \index{ru}{значение|выражения||||п}значение. Это соглашение, вместе
со старой репутацией Лиспа как
неэффективного языка, послужило источником остроумного замечания Алана
Перлиса\index{ru}{Перлис, Алан~Дж.|афоризмы|Alan~J. Perlis||n|п}\index{en}{Alan~J. Perlis||Перлис, Алан~Дж.|афоризмы|n|п} (парафразы из Оскара Уайльда),\index{ru}{Уайльд, Оскар, парафраза Перлиса||Oscar Wilde||n|п}\index{en}{Oscar Wilde||Уайльд, Оскар, парафраза Перлиса||n|п} что <<Программисты на Лиспе
знают значение всего на свете, но ничему не знают цену>>.
}.
\subsection{Имена~и окружение}
\label{NAMING-AND-THE-ENVIRONMENT}
Одна из важнейших характеристик языка программирования~---
какие~в нем существуют средства
использования\index{ru}{именование|вычислительных
объектов|naming|||}\index{en}{naming||именование|вычислительных
объектов||}
имен для
указания на вычислительные объекты. Мы говорим, что имя
обозначает\index{ru}{элементарные выражения|имя переменной||||}
\index{ru}{переменная||variable|||}\index{en}{variable||переменная|||}{\em переменную} (variable), чьим
\index{ru}{переменная|значение||||}\index{ru}{значение|переменной|value|||}\index{en}{value||значение|переменной||}{\em значением} (value) является объект.
В диалекте Лиспа Scheme мы даем вещам имена~с помощью
слова {\tt define}.\index{ru}{define (особая
форма)||||pd|}\index{ru}{особые формы|\texttt{define}||||}
Предложение
\begin{Verbatim}[fontsize=\small]
(define size 2)
\end{Verbatim}
заставляет интерпретатор связать значение 2~с именем
{\tt size}\footnote{Мы не печатаем~в этой книге ответы интерпретатора
при вычислении определений, поскольку они зависят от конкретной
реализации языка.\index{ru}{неопределенные значения|\texttt{define}|unspecified values|||п}\index{en}{unspecified values||неопределенные значения|\texttt{define}||п}%
\index{ru}{define (особая форма)|значение выражения|||p|п}
}.
После того, как имя {\tt size} связано со значением 2,
мы можем указывать на значение 2~с помощью имени:
\begin{Verbatim}[fontsize=\small]
size
\textit{2}
(* 5 size)
\textit{10}
\end{Verbatim}
Вот еще примеры использования
{\tt define}:
\begin{Verbatim}[fontsize=\small]
(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))
\textit{314.159}
(define circumference (* 2 pi radius))
circumference
\textit{62.8318}
\end{Verbatim}
Слово\index{ru}{средства абстракции|\texttt{define}||||} {\tt define} служит~в нашем языке
простейшим средством абстракции, поскольку оно позволяет нам
использовать простые имена для обозначения результатов сложных
операций, как, например, вычисленная только что длина окружности~---
{\tt circumference}. Вообще говоря, вычислительные
объекты могут быть весьма сложными структурами,~и было бы очень
неудобно, если бы нам приходилось вспоминать~и повторять все их детали
каждый раз, когда нам захочется их использовать. На самом деле
сложные программы конструируются методом построения шаг за шагом
вычислительных объектов возрастающей сложности. Интерпретатор делает
такое пошаговое построение программы особенно удобным, поскольку связи
между именами~и объектами могут создаваться последовательно по мере
взаимодействия программиста~с компьютером. Это свойство
интерпретаторов облегчает\index{ru}{пошаговое написание||incremental
development|||}\index{en}{incremental development||пошаговое
написание|||}\index{ru}{программа|пошаговое написание||||}
пошаговое написание~и тестирование программ,
и во многом благодаря именно ему получается так,
что\index{ru}{программа|структура||||} программы на Лиспе
обычно состоят из большого количества относительно простых
процедур.
Ясно, что раз интерпретатор способен
ассоциировать значения~с символами~и затем вспоминать их, то
он должен иметь некоторого рода память, сохраняющую пары имя-объект.
Эта память называется
\index{ru}{окружение||environment|||}\index{en}{environment||окружение|||}{\em окружением} (environment) (а точнее,
\index{ru}{глобальное окружение||global environment|||}\index{en}{global environment||глобальное окружение|||}{\em глобальным окружением} (global environment), поскольку позже мы увидим,
что вычисление может иметь дело~с несколькими окружениями)\footnote{~В главе~\ref{MODULARITY-OBJECTS-AND-STATE}
мы увидим, что понятие окружения
необходимо как для понимания работы интерпретаторов, так~и для их
реализации.}.
\subsection{Вычисление комбинаций}
\label{EVALUATING-COMBINATIONS}
\index{ru}{вычисление|комбинации||||}
\index{ru}{комбинация|вычисление||||}
Одна из наших целей~в этой главе~--- выделить элементы
процедурного мышления. Рассуждая~в этом русле, примем во внимание, что
интерпретатор, вычисляя значение комбинации, тоже следует
процедуре:
\begin{itemize}%MLR%Arrange the list
\item
Чтобы вычислить комбинацию, требуется:
\begin{itemize}
\item Вычислить все подвыражения
комбинации.
\item Применить процедуру, которая является
значением самого левого подвыражения (оператора)~к аргументам ---
значениям остальных подвыражений (операндов).
\end{itemize}
\end{itemize}
Даже~в этом простом правиле видны несколько важных свойств
процессов~в целом. Прежде всего, заметим, что на первом шаге
для того, чтобы провести процесс вычисления для комбинации,
нужно сначала проделать процесс вычисления для каждого элемента
комбинации. Таким образом, правило вычисления
\index{ru}{рекурсия||recursion|||}\index{en}{recursion||рекурсия|||}{\em рекурсивно} (recursive) по своей природе; это означает, что в
качестве одного из своих шагов оно включает применение того же самого
правила\footnote{Может показаться странным, что правило
вычисления предписывает нам~в качестве части первого шага
вычислить самый левый элемент комбинации,~--- ведь до сих пор это мог
быть только оператор вроде {\tt +} или
{\tt *}, представляющий встроенную процедуру, например,
сложение или умножение. Позже мы увидим, что полезно иметь
возможность работать~и~с комбинациями, чьи операторы сами по себе
являются составными выражениями.
}.
\index{ru}{рекурсия|выражение сложного процесса||||}Заметьте, какую краткость понятие рекурсии придает
описанию того, что~в случае комбинации~с глубоким вложением выглядело
бы как достаточно сложный процесс. Например, чтобы вычислить
\begin{Verbatim}[fontsize=\small]
(* (+ 2 (* 4 6))
(+ 3 5 7))
\end{Verbatim}
требуется применить правило вычисления~к четырем различным
комбинациям. Картину этого процесса можно получить, нарисовав
\index{ru}{дерево|представление комбинации||||}\index{ru}{комбинация|в
виде дерева||||}комбинацию~в виде дерева, как показано на
рис.~\ref{P1.1}. Каждая комбинация
представляется~в виде\index{ru}{вершина дерева||node of a
tree|||}\index{en}{node of a tree||вершина дерева|||}вершины, а
ее оператор~и операнды~---~в виде
\index{ru}{ветвь дерева||branch of a tree|||}\index{en}{branch of a
tree||ветвь дерева|||}ветвей, исходящих из этой вершины.
\index{ru}{концевая вершина дерева||terminal node of a
tree|||}\index{en}{terminal node of a tree||концевая вершина
дерева|||}Концевые вершины (то есть те, из которых
не исходит ни одной ветви) представляют операторы или числа.
Рассматривая вычисление как дерево, мы можем представить себе, что
значения операндов распространяются от концевых вершин вверх и
затем комбинируются на все более высоких уровнях. Впоследствии мы увидим, что
рекурсия~--- это вообще очень мощный метод обработки иерархических,
древовидных объектов. На самом деле форма правила вычисления <<распространить
значения наверх>> является примером общего типа процессов, известного
как \index{ru}{накопление|по дереву|tree accumulation|||}\index{en}{tree accumulation||накопление|по дереву||}{\em накопление по дереву} (tree accumulation).
\begin{cntrfig}
%\synttree[ {\tt sqrt} [.b {\tt sqrt-iter} [ {\tt good-enough} [ {\tt square} ]%
% {\tt abs} ]][ {\tt improve} [.b {\tt average} ] ]]]
\input{xfig-mod/1-1.eepic}
\caption{Вычисление, представленное~в виде дерева.}
\label{P1.1}
\end{cntrfig}
Далее, заметим, что многократное применение
первого шага приводит нас~к такой точке, где нам нужно вычислять уже не
комбинации,~а элементарные выражения,~а именно числовые константы, встроенные
операторы или другие имена. С этими случаями мы справляемся,
положив, что:\index{ru}{вычисление|элементарных
выражений||||}\index{ru}{элементарные выражения|вычисление||||}
\begin{plainlist}
\sloppy
\item
значением числовых констант являются те
числа, которые они называют;
\item
значением встроенных операторов являются
последовательности ма\-шинных команд, которые выполняют соответствующие
операции;~и %HERE
\item
значением остальных имен являются те
объекты,~с которыми эти имена связаны~в окружении.
\end{plainlist}
Мы можем рассматривать второе правило как частный случай третьего,
постановив, что символы вроде {\tt +} и
{\tt *} тоже включены~в глобальное окружение~и связаны
с последовательностями машинных команд, которые~и есть их
<<значения>>. Главное здесь~--- это роль\index{ru}{окружение|как контекст для вычисления||||} окружения
при определении значения символов~в выражениях. В таком диалоговом
языке, как Лисп, не имеет смысла говорить~о значении выражения, скажем,
{\tt (+ x 1)}, не указывая никакой информации об
окружении, которое дало бы значение символу {\tt x} (и
даже символу {\tt +}). Как мы увидим~в
главе~\ref{MODULARITY-OBJECTS-AND-STATE}, общее
понятие окружения, предоставляющего контекст,~в котором
происходит вычисление, будет играть важную роль~в нашем понимании
того, как выполняются программы.
Заметим, что рассмотренное нами правило вычисления не
обрабатывает определений. Например, вычисление {\tt (define x
3)} не означает применение {\tt define} к
двум аргументам, один из которых значение символа
{\tt x},~а другой равен 3, поскольку смысл
{\tt define} как раз~и состоит~в том, чтобы связать
{\tt x} со значением. (Таким образом,
{\tt (define x~3)}~--- не комбинация.)\index{ru}{define (особая
форма)|почему особая форма|||p|}
Такие исключения из вышеописанного правила вычисления
называются {\em особыми формами}\index{ru}{особая форма||special form|||} (special forms).\index{en}{special form||особая форма|||}
{\tt Define}~--- пока что единственный встретившийся нам
пример\index{ru}{вычисление|особых форм||||} особой формы, но очень скоро мы познакомимся~и~с другими.
У каждой особой формы свое собственное правило вычисления.
Разные виды выражений (вместе со своими правилами вычисления)
составляют\index{ru}{синтаксис|языка программирования||||} синтаксис языка программирования. По сравнению с
большинством языков программирования,~у Лиспа очень простой синтаксис;
а именно, правило вычисления для выражений может быть описано как
очень простое общее правило плюс специальные правила для небольшого числа
особых форм\footnote{\index{ru}{Lisp
(Лисп)|vs. Паскаль||||п}\index{ru}{Pascal
(Паскаль)|||||п}\index{ru}{точка с
запятой||semicolon|||п}\index{en}{semicolon||точка с
запятой|||п}Особые синтаксические формы, которые
представляют собой просто удобное альтернативное поверхностное
представление для того, что можно выразить более унифицированным
способом, иногда называют \index{ru}{синтаксический сахар||syntactic sugar|||п}\index{en}{syntactic sugar||синтаксический сахар|||п}{\em синтаксическим сахаром} (syntactic sugar),
используя выражение Питера Ландина.\index{ru}{Ландин, Питер||Peter Landin||n|п}\index{en}{Peter Landin||Ландин, Питер||n|п}
По сравнению~с пользователями других языков,
программистов на Лиспе, как правило, мало волнует синтаксический
сахар. (Для контраста возьмите руководство по Паскалю~и посмотрите, сколько места
там уделяется описанию синтаксиса). Такое презрение~к синтаксису
отчасти происходит от гибкости Лиспа, позволяющего легко изменять
поверхностный синтаксис,~а отчасти из наблюдения, что многие
<<удобные>> синтаксические конструкции, которые делают язык менее
последовательным, приносят~в конце концов больше вреда, чем пользы,
когда программы становятся большими~и сложными. По словам Алана
Перлиса, <<Синтаксический сахар вызывает\index{ru}{рак точки с
запятой||cancer of the semicolon|||п}\index{en}{cancer of the
semicolon||рак точки~с запятой|||п}
рак точки~с запятой>>.\index{ru}{Перлис, Алан~Дж.|афоризмы|Alan~J. Perlis||n|п}\index{en}{Alan~J. Perlis||Перлис, Алан~Дж.|афоризмы|n|п}
}.
\subsection{Составные процедуры}
\label{COMPOUND-PROCEDURES}
Мы нашли~в Лиспе некоторые из тех элементов, которые
должны присутствовать~в любом мощном языке программирования:
\begin{plainlist}
\item
Числа~и арифметические операции
представляют собой элементарные данные~и процедуры.
\item
Вложение комбинаций дает возможность комбинировать
операции.
\item
Определения, которые связывают имена со
значениями, дают ограниченные возможности абстракции.
\end{plainlist}
Теперь мы узнаем об\index{ru}{процедура|определение||||}
\index{ru}{определение процедуры||procedure definition|||}\index{en}{procedure definition||определение процедуры|||}{\em определениях процедур} (procedure definitions)~---
значительно более мощном методе абстракции,~с помощью
которого составной операции можно дать имя~и затем ссылаться на нее
как на единое целое.\index{ru}{процедура|определение||||}
Для начала рассмотрим, как выразить понятие
<<возведения~в квадрат>>. Можно сказать так: <<Чтобы возвести
что-нибудь~в квадрат, нужно умножить его само на себя>>. Вот как это
выражается~в нашем языке:
\begin{Verbatim}[fontsize=\small]
(define (square x) (* x x))\index{ru}{sqare||||pd|}
\end{Verbatim}
Это можно понимать так:
\begin{center}
\begin{tabular}{cccccl}
\tt{(define} &
\tt{(square} &
\tt{x)} &
\tt{(*} &
\tt{x} &
\tt{x))}
\\
$\uparrow$ &
$\uparrow$ &
$\uparrow$ &
$\uparrow$ &
$\uparrow$ &
$\uparrow$ \\
Чтобы &
возвести~в квадрат &
что-л. &
умножь &
это &
само на себя
\end{tabular}
\end{center}
%{\em Чтобы / возвести~в квадрат / что-то, / умножь / это / само насебя}
Здесь мы имеем \index{ru}{составная процедура||compound procedure|||}\index{en}{compound procedure||составная процедура|||}{\em составную процедуру} (compound procedure), которой мы
дали имя {\tt square}.\index{ru}{процедура|составная|procedure|compound||}\index{en}{procedure|compound|процедура|составная||}
Эта процедура представляет
операцию умножения чего-либо само на себя. Та вещь, которую нужно
подвергнуть умножению, получает здесь имя {\tt x},
которое играет ту же роль, что~в естественных языках играет
местоимение.\index{ru}{именование|процедур||||}\index{ru}{процедура|создание
с помощью \texttt{define}||||}\index{ru}{процедура|именование (с
помощью \texttt{define})||||} Вычисление этого определения создает
составную процедуру
и связывает ее~с именем {\tt square}\footnote{Заметьте, что здесь присутствуют две различные
операции: мы создаем процедуру,~и мы даем ей имя
{\tt square}. Возможно,~и на самом деле даже важно,
разделить эти два понятия: создавать процедуры, никак их не называя,~и
давать имена процедурам, уже созданным заранее. Мы увидим, как это
делается,~в разделе~\ref{CONSTRUCTING-PROCEDURES-USING-LAMBDA}.}.
Общая форма определения процедуры такова:
\index{ru}{define (особая форма)|для процедур|||pd|}
\index{ru}{особые формы|\texttt{define}||||}
\begin{Verbatim}[fontsize=\small]
(define (\textit{$\langle$имя$\rangle$} \textit{$\langle$формальные-параметры$\rangle$}) \textit{$\langle$тело$\rangle$})
\end{Verbatim}
\index{ru}{имя|процедуры||||}%
\textit{$\langle$Имя$\rangle$} --- это тот символ,~с которым нужно
связать~в окружении определение процедуры\footnote{\index{ru}{нотация~в настоящей книге|курсив~в синтаксисе выражений||||п}На всем протяжении этой книги мы будем описывать
обобщенный\index{ru}{синтаксис|выражений, описание||||п}синтаксис выражений, используя курсив в
угловых скобках --- напр. \textit{$\langle$имя$\rangle$}, чтобы обозначить <<дырки>>
в выражении, которые нужно заполнить, когда это выражение
используется~в языке.
}.
\index{ru}{имя|процедуры||||}\index{ru}{тело процедуры||body of a
procedure|||}\index{en}{body of a procedure||тело
процедуры|||}\index{ru}{формальные параметры процедуры||formal
parameters|||}\index{en}{formal parameters||формальные параметры
процедуры|||}\index{ru}{процедура|тело||||}\index{ru}{процедура|формальные параметры||||}\index{ru}{процедура|имя||||}\textit{$\langle$Формальные-параметры$\rangle$} --- это имена, которые~в теле процедуры
используются для отсылки~к соответствующим аргументам процедуры.
\index{ru}{тело процедуры|||||}\textit{$\langle$Тело$\rangle$} ---
это выражение, которое вычислит результат применения
процедуры, когда формальные параметры будут заменены аргументами, к
которым процедура будет применяться\footnote{В более общем случае тело процедуры может быть
\index{ru}{последовательность выражений|в теле процедуры|sequence
of expressions|||п}\index{en}{sequence of
expressions||последовательность выражений|в теле
процедуры||п}последовательностью выражений. В этом случае
интерпретатор вычисляет
по очереди все выражения~в этой последовательности~и возвращает в
качестве значения применения процедуры значение последнего
выражения.}.
\textit{$\langle$Имя$\rangle$}~и
\textit{$\langle$формальные-параметры$\rangle$} заключены~в
\index{ru}{скобки|в определении процедуры|parentheses|||}\index{en}{parentheses||скобки|в определении процедуры||}
скобки, как это было бы при вызове определяемой процедуры.
Теперь, когда процедура {\tt square} определена, мы можем ее
использовать:
\begin{Verbatim}[fontsize=\small]
(square 21)
\textit{441}
(square (+ 2 5))
\textit{49}
(square (square 3))
\textit{81}
\end{Verbatim}
Кроме того, мы можем использовать
{\tt square} при определении других процедур. Например,
$x^2 + y^2$ можно записать как
\begin{Verbatim}[fontsize=\small]
(+ (square x) (square y)))
\end{Verbatim}
Легко можно определить процедуру
{\tt sum-of-squares}, которая, получая~в качестве
аргументов два числа, дает~в результате сумму их квадратов:
\begin{Verbatim}[fontsize=\small]
(define (sum-of-squares x y) \index{ru}{sum-of-squares||||pd|}
(+ (square x) (square y)))
(sum-of-squares 3 4)
\textit{25}
\end{Verbatim}
Теперь~и {\tt sum-of-squares} мы можем использовать как
строительный блок при дальнейшем определении процедур:
\begin{Verbatim}[fontsize=\small]
(define (f a)
(sum-of-squares (+ a 1) (* a 2)))
(f 5)
\textit{136}
\end{Verbatim}
\index{ru}{составная процедура|использование~в качестве элементарных||||}Составные процедуры используются точно так же,
как элементарные.~В
самом деле, глядя на приведенное выше определение
{\tt sum-of-squares}, невозможно выяснить, была ли
{\tt square} встроена~в интерпретатор, подобно
{\tt +}~и {\tt *}, или ее определили
как составную процедуру.
\subsection{Подстановочная модель применения процедуры}
\label{SUBST-MODEL-FOR-PROC-APPL}
\index{ru}{подстановочная модель применения процедуры|||||}
Вычисляя комбинацию, оператор которой называет составную
процедуру, интерпретатор осуществляет, вообще говоря, тот же процесс, что~и
для комбинаций, операторы которых называют элементарные процедуры~---
процесс, описанный~в разделе~\ref{EVALUATING-COMBINATIONS}. А именно,
интерпретатор вычисляет элементы комбинации~и применяет процедуру
(значение оператора комбинации)~к аргументам (значениям операндов
комбинации).
Мы можем предположить, что механизм применения
элементарных процедур~к аргументам встроен~в интерпретатор. Для
составных процедур процесс протекает так:
\begin{plainlist}
\item Чтобы применить составную
процедуру~к аргументам, требуется вычислить тело процедуры, заменив каждый
формальный параметр соответствующим аргументом.
\end{plainlist}
Чтобы проиллюстрировать этот процесс, вычислим комбинацию
\begin{Verbatim}[fontsize=\small]
(f 5)
\end{Verbatim}
где {\tt f} --- процедура, определенная~в
разделе~\ref{COMPOUND-PROCEDURES}. Начинаем мы~с того, что
восстанавливаем тело {\tt f}:
\begin{Verbatim}[fontsize=\small]
(sum-of-squares (+ a 1) (* a 2))
\end{Verbatim}
Затем мы заменяем формальный параметр {\tt a} на
аргумент 5:
\begin{Verbatim}[fontsize=\small]
(sum-of-squares (+ 5 1) (* 5 2))
\end{Verbatim}
Таким образом, задача сводится~к вычислению комбинации~с двумя
операндами~и оператором {\tt sum-of-squares}.
Вычисление этой комбинации включает три подзадачи. Нам нужно
вычислить оператор, чтобы получить процедуру, которую требуется
применить,~а также операнды, чтобы получить аргументы. При этом
{\tt (+ 5 1)} дает 6,~а {\tt (* 5
2)} дает 10, так что нам требуется применить процедуру
{\tt sum-of-squares}~к 6~и 10. Эти значения
подставляются на место формальных параметров {\tt x} и
{\tt y}~в теле {\tt sum-of-squares},
приводя выражение к
\begin{Verbatim}[fontsize=\small]
(+ (square 6) (square 10))
\end{Verbatim}
Когда мы используем определение {\tt square}, это
приводится~к
\begin{Verbatim}[fontsize=\small]
(+ (* 6 6) (* 10 10))
\end{Verbatim}
что при умножении сводится к
\begin{Verbatim}[fontsize=\small]
(+ 36 100)
\end{Verbatim}
и, наконец, к
\begin{Verbatim}[fontsize=\small]
136
\end{Verbatim}
Только что описанный нами процесс называется
\index{ru}{подстановочная модель применения процедуры||substitution model|||}%
\index{en}{substitution model||подстановочная модель применения процедуры|||}%
{\em подстановочной моделью} (substitution model) применения процедуры.
Ее можно использовать как модель, которая определяет <<смысл>>
понятия применения процедуры, пока рассматриваются процедуры из этой
главы. Имеются, однако, две детали, которые необходимо подчеркнуть:
\begin{plainlist}
\item
Цель подстановочной модели --- помочь нам
представить, как применяются процедуры,~а не дать описание того, как на самом
деле работает интерпретатор. Как правило, интерпретаторы вычисляют
применения процедур~к аргументам без манипуляций~с текстом
процедуры, которые выражаются~в подстановке значений для формальных
параметров. На практике <<подстановка>> реализуется~с помощью
локальных окружений для формальных параметров. Более