-
Notifications
You must be signed in to change notification settings - Fork 9
/
chapter-3.tex
8329 lines (7402 loc) · 540 KB
/
chapter-3.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
\chapter{Модульность, объекты и состояние}
\label{MODULARITY-OBJECTS-AND-STATE}
%\markboth{Глава 3 \qquad Модульность, объекты и состояние}{}
\thispagestyle{empty}
\epigraph{
\textgreek{Metab'allon >anapa'uetai}
(Изменяясь, оно остается неподвижным)}{Гераклит}\index{ru}{Гераклит||||n|}
\epigraph{
Plus \c{c}a change, plus c'est la m\^eme chose\index{ru}{Карр, Альфонс||Alphonse Karr||n|}\index{en}{Alphonse Karr||Карр, Альфонс||n|}}{Альфонс Карр}
В предыдущих главах мы ввели основные элементы, из которых
строятся программы. Мы видели, как элементарные процедуры и
элементарные данные, сочетаясь, образуют составные сущности; мы
стали понимать, что без абстракции нельзя
справиться со сложностью больших систем. Однако этих инструментов
недостаточно для разработки программ. Для эффективного синтеза программ
требуются также организационные принципы, которые помогали бы нам
сформулировать общий проект программы. В частности, нам нужны
стратегии для построения больших программ по принципу
\index{ru}{модульность||modularity|||}\index{en}{modularity||модульность|||}{\em модульности} (modularity): чтобы программы
<<естественным>> образом делились на логически цельные куски, которые
можно разрабатывать и поддерживать независимо друг от друга.
\index{ru}{моделирование|как стратегия
разработки||||}\index{ru}{модульность|||||}Существует мощная
стратегия разработки, которая особенно хорошо
подходит для построения программ, моделирующих физические системы:
воспроизводить в структуре программы структуру
моделируемой системы. Для каждого объекта в системе мы строим
соответствующий ему вычислительный объект. Для каждого действия в
системе определяем в рамках нашей
вычислительной модели символьную операцию. Используя эту стратегию, мы надеемся, что
расширение нашей модели на новые объекты или действия не потребует
стратегических изменений в программе, а позволит обойтись только добавлением новых
символьных аналогов этих объектов или действий. Если наша организация
системы окажется удачной, то для добавления новых возможностей или
отладки старых нам придется работать только с ограниченной частью
системы.
Таким образом, способ, которым мы
организуем большую программу, в значительной степени диктуется нашим восприятием моделируемой
системы. В этой главе мы исследуем две важных организационных
стратегии, которые соответствуют двум достаточно различным взглядам
на мир и структуру систем. Первая из них сосредотачивается на
\index{ru}{объект(ы)||object(s)|||}\index{en}{object(s)||объект(ы)|||}{\em объектах} (objects), и большая система
рассматривается как собрание индивидуальных
объектов, поведение которых может меняться со временем.
Альтернативная стратегия строится вокруг
\index{ru}{поток(и)||stream(s)|||}\index{en}{stream(s)||поток(и)|||}{\em потоков} (streams) информации в системе, во многом
подобно тому, как в электронике рассматриваются системы обработки
сигналов.
Как подход, основанный на объектах, так и подход, основанный на
потоках, высвечивают важные вопросы, касающиеся языков
программирования. При работе с объектами нам приходится думать о том,
как вычислительный объект может изменяться и при этом сохранять свою
индивидуальность. Из-за этого нам придется отказаться от подстановочной модели
вычислений (раздел~\ref{SUBST-MODEL-FOR-PROC-APPL}) в
пользу более механистичной и в то же время менее привлекательной
теоретически \index{ru}{модель вычисления с окружениями||environment model of evaluation|||}\index{en}{environment model of evaluation||модель вычисления с окружениями|||}{\em модели с окружениями} (environment model).
Сложности, связанные с объектами, их изменением и индивидуальностью
являются фундаментальным следствием из потребности ввести понятие времени в вычислительные
модели. Эти сложности только увеличиваются, когда мы добавляем
возможность параллельного выполнения программ. Получить наибольшую
отдачу от потокового подхода удается тогда, когда
моделируемое время отделяется от порядка событий, происходящих в компьютере
в процессе вычисления. Мы достигнем этого при помощи метода,
называемого \index{ru}{задержанные вычисления||delayed evaluation|||}\index{en}{delayed evaluation||задержанные вычисления|||}{\em задержанными
вычислениями} (delayed evaluation).
\section{Присваивание и внутреннее состояние объектов}
\label{ASSIGNMENT-AND-LOCAL-STATE}
\index{ru}{присваивание||assignment|||}\index{en}{assignment||присваивание|||}
\index{ru}{внутреннее состояние||local state|||}\index{en}{local state||внутреннее состояние|||}
Обычно мы считаем, что мир состоит из отдельных объектов, и у
каждого из них есть состояние, которое изменяется со временем. Мы
говорим, что объект <<обладает состоянием>>, если на поведение объекта
влияет его история. Например, банковский счет обладает состоянием
потому, что ответ на вопрос <<Могу ли я снять 100 долларов?>> зависит от
истории занесения и снятия с него денег. Состояние объекта можно
описать набором из одной или более
\index{ru}{переменная состояния||state variable|||}\index{en}{state variable||переменная состояния|||}{\em переменных состояния} (state variables),
которые вместе содержат достаточно информации, чтобы определить
текущее поведение объекта. В простой банковской системе состояние счета можно
охарактеризовать его текущим балансом, вместо того,
чтобы запоминать всю историю транзакций с этим счетом.
Если система состоит из многих объектов, они редко совершенно
независимы друг от друга. Каждый из них может влиять на состояние
других при помощи актов взаимодействия,
связывающих переменные состояния одного объекта с переменными других
объектов. На самом деле, взгляд, согласно которому система состоит
из отдельных объектов, полезнее всего в том случае, когда ее
можно разделить на несколько подсистем, в каждой из которых внутренние
связи сильнее, чем связи с другими подсистемами.
Такая точка зрения на систему может служить мощной парадигмой для
организации вычислительных моделей системы. Чтобы такая
модель была модульной, ее требуется разделить на вычислительные
объекты, моделирующие реальные объекты системы. Каждый вычислительный
объект должен содержать собственные
\index{ru}{внутренняя переменная состояния||local state variable|||}\index{en}{local state variable||внутренняя переменная состояния|||}{\em внутренние переменные
состояния} (local state variables), описывающие состояние реального объекта. Поскольку
объекты в моделируемой системе меняются со временем, переменные
состояния соответствующих вычислительных объектов также должны
изменяться. Если мы решаем, что поток времени в системе будет
моделироваться временем, проходящим в компьютере, то нам требуется
способ строить вычислительные объекты, поведение которых меняется
по мере выполнения программы. В частности, если нам хочется
моделировать переменные состояния обыкновенными символическими именами
в языке программирования, в языке должен иметься
\index{ru}{оператор присваивания||assignment operator|||}\index{en}{assignment operator||оператор присваивания|||}{\em оператор присваивания} (assignment operator),
который позволял бы изменять значение, связанное с именем.
\subsection{Внутренние переменные состояния}
\label{LOCAL-STATE-VARIABLES}
\index{ru}{внутренняя переменная состояния|||||}
\index{ru}{переменная состояния|внутренняя||||}
Чтобы показать, что мы имеем в виду, говоря о
\index{ru}{объект(ы)|с состоянием, меняющимся во времени||||}
вычислительном объекте, состояние которого меняется со временем,
давайте промоделируем ситуацию снятия денег
с \index{ru}{банковский счет||bank account|||}\index{en}{bank account||банковский счет|||} банковского счета.
Воспользуемся для этого процедурой {\tt withdraw}, которая в
качестве аргумента принимает сумму, которую требуется снять.
Если на счету имеется достаточно средств, чтобы осуществить операцию, то
{\tt withdraw} возвращает баланс, остающийся после
снятия. В противном случае {\tt withdraw} возвращает
сообщение <<Недостаточно денег на счете>>. Например, если вначале на
счету содержится 100 долларов, мы получим следующую
последовательность результатов:
\begin{Verbatim}[fontsize=\small]
(withdraw 25)
\textit{75}
(withdraw 25)
\textit{50}
(withdraw 60)
\textit{"Недостаточно денег на счете"}
(withdraw 15)
\textit{35}
\end{Verbatim}
Обратите внимание, что выражение {\tt (withdraw 25)}, будучи
вычислено дважды, дает различные результаты. Это новый тип поведения для
процедуры. До сих пор все наши процедуры можно было рассматривать как
описания способов вычисления математических функций. Вызов процедуры
вычислял значение функции для данных аргументов, и два
вызова одной и той же процедуры с одинаковыми аргументами всегда
приводили к одинаковому результату\footnote{На самом деле это не совсем правда. Одно исключение~--- \index{ru}{random (элементарная процедура)|необходимость присваивания|||p|п}%
\index{ru}{генератор случайных чисел|||||п}генератор случайных чисел из
раздела~\ref{EXAMPLE-TESTING-FOR-PRIMALITY}. Второе связано с
\index{ru}{таблица операций и типов|необходимость присваивания||||п}таблицами
операций и типов, которые мы ввели в
разделе~\ref{DATA-DIRECTED-PROGRAMMING-AND-ADDITIVITY}, где
значения двух вызовов {\tt get} с одними и теми же аргументами
зависели от того, какие были в промежутке между ними вызовы
{\tt put}. С другой стороны, пока мы не ввели присваивание,
мы лишены возможности самим создавать такие процедуры.}.
При реализации {\tt withdraw} мы используем
переменную {\tt balance}, которая показывает остаток денег на
счете, и определяем {\tt withdraw} в виде процедуры, которая
обращается к этой переменной. Процедура {\tt withdraw}
проверяет, что значение {\tt balance} не меньше, чем значение
аргумента {\tt amount}. Если это так, {\tt withdraw}
уменьшает значение {\tt balance} на {\tt amount} и
возвращает новое значение {\tt balance}. В противном случае
она возвращает сообщение <<Недостаточно денег на счете>>. Вот
определения {\tt balance} и {\tt withdraw}:
\begin{Verbatim}[fontsize=\small]
(define balance 100)
(define (withdraw amount) \index{ru}{withdraw||||pd|}
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Недостаточно денег на счете"))
\end{Verbatim}
Значение переменной {\tt balance} уменьшается, когда мы
выполняем выражение
\begin{Verbatim}[fontsize=\small]
(set! balance (- balance amount))
\end{Verbatim}
Здесь используется особая форма \index{ru}{set! (особая
форма)||||p|}\index{ru}{особые формы|\texttt{set!}||||}{\tt set!},
синтаксис которой выглядит так:
\begin{Verbatim}[fontsize=\small]
(set! \textit{$\langle$имя$\rangle$} \textit{$\langle$новое-значение$\rangle$})
\end{Verbatim}
Здесь
\textit{$\langle$имя$\rangle$} ~--- символ, а \textit{$\langle$новое-значение$\rangle$} --
произвольное выражение. {\tt Set!} заменяет значение
\textit{$\langle$имени$\rangle$} на результат,
полученный при вычислении \textit{$\langle$нового-значения$\rangle$}. В данном
случае, мы изменяем {\tt balance} так, что его новое значение
будет результатом вычитания {\tt amount} из предыдущего
значения {\tt balance}\footnote{\index{ru}{set! (особая
форма)|значение|||p|п}\index{ru}{неопределенные
значения|\texttt{set!}||||п}Значение выражения {\tt set!} зависит
от реализации. {\tt Set!} нужно использовать только ради
эффекта, который оно оказывает, а не ради значения, которое оно
возвращает.
\index{ru}{соглашение об именах|\texttt{!} для присваиваний и
изменений|naming conventions|||п}\index{en}{naming
conventions||соглашение об именах|\texttt{!} для присваиваний и
изменений||п}Имя {\tt set!} отражает соглашение, принятое в
Scheme: операциям, которые изменяют значения переменных (или структуры
данных, как мы увидим в разделе~\ref{MODELING-WITH-MUTABLE-DATA})
даются имена с восклицательным знаком на конце. Это напоминает
соглашение называть предикаты именами, которые оканчиваются на
вопросительный знак.\index{ru}{!, в именах
процедур||||p|п}\index{ru}{восклицательный знак, в именах
процедур||exclamation
point|||п}\index{en}{exclamation point||восклицательный знак, в
именах процедур|||п}}.
Кроме того, {\tt withdraw} использует особую форму
\index{ru}{особые формы|\texttt{begin}||||}{\tt begin},
когда проверка {\tt if} выдает истину, и требуется вычислить два
выражения: сначала уменьшить
{\tt balance}, а затем вернуть его значение. В общем случае
вычисление выражения
\begin{Verbatim}[fontsize=\small]
(begin \textit{$\langle$выражение${}_{\mbox{1}}$$\rangle$} \textit{$\langle$выражение${}_{\mbox{2}}$$\rangle$} ... \textit{$\langle$выражение${}_{\mbox{k}}$$\rangle$})
\end{Verbatim}
приводит к последовательному вычислению выражений от
\textit{$\langle$выражения${}_{\mbox{1}}$$\rangle$} до
\textit{$\langle$выражения${}_{\mbox{k}}$$\rangle$}, и значение
последнего выражения
\textit{$\langle$выражение${}_{\mbox{k}}$$\rangle$} возвращается в
качестве значения всей формы
{\tt begin}\footnote{Неявно мы уже использовали в своих программах
{\tt begin}, поскольку в Scheme тело процедуры может быть
последовательностью выражений. Кроме того, в каждом подвыражении
{\tt cond} следствие может состоять не
\index{ru}{cond (особая форма)|неявный \texttt{begin} в следствиях|||p|п}
\index{ru}{процедура|неявный \texttt{begin} в теле||||п}
из одного выражения, а из нескольких.}.
Хотя процедура {\tt withdraw} и работает так, как мы
того хотели, переменная {\tt balance} представляет собой
проблему. {\tt Balance}, как она описана выше, является
переменной, определенной в глобальном окружении, и любая процедура может
прочитать или изменить ее значение. Намного лучше было бы,
если бы {\tt balance} можно было сделать внутренней
переменной для {\tt withdraw}, так, чтобы только
{\tt withdraw} имела доступ к ней напрямую, а любая
другая процедура~--- только посредством вызовов {\tt withdraw}.
Так можно будет более точно смоделировать представление о
{\tt balance} как о внутренней переменной состояния, с помощью
которой {\tt withdraw} следит за состоянием
счета.
Сделать {\tt balance} внутренней по отношению к
{\tt withdraw} мы можем, переписав определение следующим
образом:
\begin{Verbatim}[fontsize=\small]
(define new-withdraw\index{ru}{new-withdraw||||pd|}
(let ((balance 100))
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Недостаточно денег на счете"))))
\end{Verbatim}
Здесь мы, используя {\tt let}, создаем окружение с внутренней
переменной {\tt ba\-lance}, которой вначале присваивается
значение 100. Внутри этого локального окружения мы при помощи
{\tt lambda} определяем процедуру, которая берет в
качестве аргумента {\tt amount} и действует так же, как наша
старая процедура {\tt withdraw}. Эта процедура ---
возвращаемая как результат выражения
{\tt let}, --- и есть {\tt new-withdraw}. Она ведет
себя в точности так же, как, как {\tt withdraw}, но ее
переменная {\tt balance} недоступна для всех остальных
процедур\footnote{По терминологии, принятой при описании языков программирования,
переменная {\tt balance}
\index{ru}{инкапсулированное имя||encapsulated name|||п}%
\index{en}{encapsulated name||инкапсулированное имя|||п}%
\index{ru}{имя|инкапсулированное||||п}%
\index{ru}{инкапсуляция||encapsulation|||п}%
\index{en}{encapsulation||инкапсуляция|||п}%
{\em инкапсулируется} (is encapsulated) внутри процедуры
{\tt new-withdraw}. Инкапсуляция отражает общий принцип
проектирования систем, известный как
\index{ru}{модульность|принцип сокрытия||||п}%
\index{ru}{сокрытия принцип||hiding principle|||п}%
\index{en}{hiding principle||сокрытия принцип|||п}{\em принцип сокрытия} (the hiding principle): систему можно
сделать более модульной и надежной, если защищать ее части друг
от друга; то есть, разрешать доступ к информации только тем частям
системы, которым <<необходимо это знать>>.}.
{\tt Set!} в сочетании с локальными
переменными --- общая стратегия программирования, которую мы будем
использовать для построения вычислительных объектов, обладающих
внутренним состоянием. К сожалению, при использовании этой стратегии
возникает серьезная проблема: когда мы только вводили понятие процедуры, мы
ввели также подстановочную модель вычислений
(раздел~\ref{SUBST-MODEL-FOR-PROC-APPL}) для того, чтобы
объяснить, что означает применение процедуры к аргументам. Мы
сказали, что оно должно интерпретироваться как вычисление тела
процедуры, в котором формальные параметры заменяются на свои
значения. К сожалению, как только мы вводим в язык присваивание,
подстановка перестает быть адекватной моделью применения
процедуры. (Почему это так, мы поймем в
разделе~\ref{THE-COSTS-OF-INTRODUCING-ASSIGNMENT}.) В
результате,
с технической точки зрения мы сейчас не умеем объяснить, почему
процедура {\tt new-withdraw} ведет себя именно так, как описано
выше. Чтобы действительно понять процедуры, подобные
{\tt new-withdraw}, нам придется разработать новую модель
применения процедуры. В
разделе~\ref{THE-ENVIRONMENT-MODEL-OF-EVALUATION} мы введем такую
модель, попутно объяснив {\tt set!} и локальные
переменные. Однако сначала мы рассмотрим некоторые вариации на тему,
заданную {\tt new-withdraw}.
Следующая процедура, {\tt make-withdraw}, создает
<<обработчики снятия денег со счетов>>. Формальный параметр
{\tt balance}, передаваемый в {\tt make-withdraw},
указывает начальную сумму денег на счету\footnote{В отличие от предыдущей процедуры
{\tt new-withdraw}, здесь нам необязательно использовать
{\tt let},
чтобы сделать {\tt balance} локальной переменной, поскольку
формальные параметры и так локальны. Это станет яснее после
обсуждения модели вычисления с окружениями в
разделе~\ref{THE-ENVIRONMENT-MODEL-OF-EVALUATION}. (См.
также упражнение~\ref{EX3.10}.)}.
{\sloppy
}
\begin{Verbatim}[fontsize=\small]
(define (make-withdraw balance)\index{ru}{make-withdraw||||pd|}
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Недостаточно денег на счете")))
\end{Verbatim}
При помощи {\tt make-withdraw} можно следующим образом создать
два объекта {\tt W1} и {\tt W2}:
\begin{Verbatim}[fontsize=\small]
(define W1 (make-withdraw 100))
(define W2 (make-withdraw 100))
(W1 50)
\textit{50}
(W2 70)
\textit{30}
(W2 40)
\textit{"Недостаточно денег на счете" }
(W1 40)
\textit{10}
\end{Verbatim}
Обратите внимание, что
{\tt W1} и {\tt W2}~--- полностью независимые объекты,
каждый со своей локальной переменной {\tt balance}. Снятие
денег с одного счета не влияет на другой.
Мы можем создавать объекты, которые будут разрешать не только
снятие денег, но и их занесение на счет, и таким образом можно
смоделировать простые банковские счета. Вот процедура, которая
возвращает объект-<<банковский счет>> с указанным начальным балансом:
\begin{Verbatim}[fontsize=\small]
(define (make-account balance)\index{ru}{make-account||||pd|}
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Недостаточно денег на счете"))
(define (deposit amount)\index{ru}{deposit (сообщение для банковского счета)||||pd|}
(set! balance (+ balance amount))
balance)
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Неизвестный вызов -- MAKE-ACCOUNT"
m))))
dispatch)
\end{Verbatim}
Каждый вызов
{\tt make-account} создает окружение с локальной переменной
состояния {\tt balance}. Внутри этого окружения
{\tt make-account} определяет процедуры {\tt deposit} и
{\tt withdraw}, которые обращаются к {\tt balance}, а
также дополнительную процедуру {\tt dispatch}, которая
принимает <<сообщение>> в качестве ввода, и возвращает одну из двух
локальных процедур. Сама процедура {\tt dispatch} возвращается
как значение, которое представляет объект-банковский счет. Это не что
иное, как стиль программирования с
\index{ru}{передача сообщений|в банковском счете||||}
\index{ru}{передача сообщений||message passing|||}\index{en}{message passing||передача сообщений|||}{\em передачей сообщений} (message passing), который мы видели в
разделе~\ref{DATA-DIRECTED-PROGRAMMING-AND-ADDITIVITY}, но только
здесь мы его используем в сочетании с возможностью изменять локальные
переменные.
{\tt Make-account} можно использовать следующим
образом:
\begin{Verbatim}[fontsize=\small]
(define acc (make-account 100))
((acc 'withdraw) 50)
\textit{50}
((acc 'withdraw) 60)
\textit{"Недостаточно денег на счете" }
((acc 'deposit) 40)
\textit{90}
((acc 'withdraw) 60)
\textit{30}
\end{Verbatim}
Каждый вызов {\tt acc} возвращает локально определенную процедуру
{\tt deposit} или {\tt withdraw}, которая затем
применяется к указанной сумме. Точно так же, как это было с
{\tt make-withdraw}, второй вызов {\tt make-account}
\begin{Verbatim}[fontsize=\small]
(define acc2 (make-account 100))
\end{Verbatim}
создает совершенно отдельный объект-счет, который поддерживает свою
собственную переменную {\tt balance}.
\begin{exercise}{3.1}\label{EX3.1}%
\index{ru}{накопитель||accumulator|||(упр.~3.1)}%
\index{en}{accumulator||накопитель|||(упр.~3.1)}%
{\em Накопитель} (accumulator)~--- это
процедура, которая вызывается с одним численным аргументом и собирает
свои аргументы в сумму. При каждом вызове накопитель возвращает
сумму, которую успел накопить. Напишите процедуру
{\tt make-accumulator},
\index{ru}{make-accumulator||||p|(упр.~3.1)}
порождающую накопители, каждый
из которых поддерживает свою отдельную сумму. Входной параметр
{\tt make-accumulator} должен указывать начальное значение
суммы; например,
\begin{Verbatim}[fontsize=\small]
(define A (make-accumulator 5))
(A 10)
\textit{15}
(A 10)
\textit{25}
\end{Verbatim}
\end{exercise}
\begin{exercise}{3.2}\label{EX3.2}%
При тестировании программ удобно иметь
возможность подсчитывать, сколько раз за время вычислений была вызвана
та или иная процедура.\index{ru}{отслеживаемая процедура||monitored procedure|||(упр.~3.2)}%
\index{en}{monitored procedure||отслеживаемая процедура|||(упр.~3.2)}%
\index{ru}{процедура|отслеживаемая||||(упр.~3.2)} Напишите процедуру {\tt make-monitored},\index{ru}{make-monitored||||p|(упр.~3.2)} принимающую в качестве параметра процедуру {\tt f}, которая сама
по себе принимает один входной параметр. Результат, возвращаемый
{\tt make-monitored}~--- третья процедура, назовем ее
{\tt mf}, которая подсчитывает, сколько раз она была вызвана,
при помощи внутреннего счетчика. Если на входе {\tt mf}
получает специальный символ {\tt how-many-calls?}, она
возвращает значение счетчика. Если же на вход подается специальный
символ {\tt reset-count}, {\tt mf} обнуляет счетчик.
Для любого другого параметра {\tt mf} возвращает результат
вызова {\tt f} с этим параметром и увеличивает счетчик.
Например, можно было бы сделать отслеживаемую версию процедуры
{\tt sqrt}:
\begin{Verbatim}[fontsize=\small]
(define s (make-monitored sqrt))
(s 100)
\textit{10}
(s 'how-many-calls?)
\textit{1}
\end{Verbatim}
\end{exercise}
\begin{exercise}{3.3}\label{EX3.3}%
Измените процедуру {\tt make-account} так,
чтобы она создавала
\index{ru}{банковский счет|защищенный паролем||||(упр.~3.3)}%
\index{ru}{защищенный паролем банковский счет||password-protected bank account|||(упр.~3.3)}%
\index{en}{password-protected bank account||защищенный паролем банковский счет|||(упр.~3.3)}%
счета, защищенные паролем. А именно,
{\tt make-account} должна
в качестве дополнительного аргумента принимать символ, например\-
\begin{Verbatim}[fontsize=\small]
(define acc (make-account 100 'secret-password))
\end{Verbatim}
Получившийся объект-счет должен обрабатывать запросы, только если они
сопровождаются паролем, с которым счет был создан, а в противном
случае он должен жаловаться:
\begin{Verbatim}[fontsize=\small]
((acc 'secret-password 'withdraw) 40)
\textit{60}
((acc 'some-other-password 'deposit) 50)
\textit{"Неверный пароль" }
\end{Verbatim}
\end{exercise}
\begin{exercise}{3.4}\label{EX3.4}%
Модифицируйте процедуру {\tt make-account} из
упражнения~\ref{EX3.3}, добавив еще одну локальную
переменную, так, чтобы, если происходит более семи попыток доступа подряд
с неверным паролем, вызывалась процедура {\tt call-the-cops}
(вызвать полицию).
\end{exercise}
\subsection{Преимущества
присваивания}
\label{THE-BENEFITS-OF-INTRODUCING-ASSIGNMENT}
\index{ru}{присваивание|преимущества||||}
Как нам предстоит увидеть, введение присваивания в наш язык
программирования ведет к множеству сложных концептуальных проблем.
\index{ru}{модульность|через моделирование объектов||||}
\index{ru}{объект(ы)|преимущества введения в моделирование||||}Тем не менее, представление о системе как о наборе объектов, имеющих
внутреннее состояние,~--- мощное средство для обеспечения модульности
проекта. В качестве примера рассмотрим строение процедуры
{\tt rand}, которая, будучи вызванной, каждый раз возвращает
случайное целое число.
Вовсе не так просто определить, что значит <<случайное>>.
Вероятно, имеется в виду, что последовательные обращения к
{\tt rand} должны \index{ru}{генератор случайных чисел|||||}порождать последовательность чисел, которая
обладает статистическими свойствами равномерного распределения. Здесь
мы не будем обсуждать способы порождения подобных последовательностей.
Вместо этого предположим, что у нас есть процедура
{\tt rand-update}, которая обладает следующим свойством: если мы
начинаем с некоторого данного числа
$x_1$ и строим
последовательность
$$
\begin{array}{l}
x_2 = \mbox{\tt(rand-update $x_1$)}\\
x_3 = \mbox{\tt(rand-update $x_2$)}
\end{array}
$$
то последовательность величин
$x_1, x_2, x_3\ldots$
будет обладать требуемыми математическими свойствами\footnote{Один из распространенных способов реализации
{\tt rand-update} состоит в том, чтобы положить новое значение
$x$ равным $ax+b \mathop{\rm mod}
m$, где $a$, $b$ и
$m$~--- соответствующим образом подобранные целые
числа. Глава~3 книги Knuth 1981\index{ru}{Кнут,
Дональд~Э.||Donald~E. Knuth||n|п}\index{en}{Donald~E. Knuth||Кнут,
Дональд~Э.||n|п}
содержит подробное обсуждение методов порождения последовательностей
случайных чисел и обеспечения их статистических свойств. Обратите
внимание, что {\tt rand-update} вычисляет математическую
функцию: если ей дважды дать один и тот же вход, она вернет одинаковый
результат. Таким образом, последовательность чисел, порождаемая
{\tt rand-update}, никоим образом не <<случайна>>, если мы
настаиваем на том, что в последовательности <<случайных>> чисел
следующее число не должно иметь никакого отношения к предыдущему.
Отношение между <<настоящей>> случайностью и так называемыми
\index{ru}{псевдослучайная последовательность чисел||pseudo-random
sequence|||п}\index{en}{pseudo-random
sequence||псевдослучайная последовательность чисел|||п}{\em
псевдослучайными} (pseudo-random) последовательностями, которые
порождаются путем однозначно определенных вычислений и тем не менее
обладают нужными статистическими свойствами, --- непростой вопрос,
связанный со сложными проблемами математики и философии. Для
прояснения этих вопросов много сделали Колмогоров, Соломонофф и Хайтин;
обсуждение можно найти в Chaitin
1975.\index{ru}{Колмогоров,~А.Н.||||n|п}\index{ru}{Хайтин,
Грегори||Gregory Chaitin||n|п}\index{en}{Gregory Chaitin||Хайтин,
Грегори||n|п}\index{ru}{Соломонофф, Рэй||Ray
Solomonoff||n|п}\index{en}{Ray Solomonoff||Соломонофф, Рэй||n|п}}.
Мы можем реализовать {\tt rand} как процедуру с
внутренней переменной состояния {\tt x}, которая
инициализируется некоторым заранее заданным значением
{\tt random-init}. Каждый вызов {\tt rand} вычисляет
{\tt rand-update} от текущего значения {\tt x},
возвращает это значение как случайное число, и, кроме того, сохраняет
его как новое значение {\tt x}.
\begin{Verbatim}[fontsize=\small]
(define rand \index{ru}{rand||||pd|}
(let ((x random-init))
(lambda ()
(set! x (rand-update x))
x)))
\end{Verbatim}
Разумеется, ту же последовательность случайных чисел мы
могли бы получить без использования присваивания, просто напрямую
вызывая {\tt rand-up\-date}. Однако это означало бы, что всякая
часть программы, которая использует случайные числа, должна явно
запоминать текущее значение {\tt x}, чтобы передать его как
аргумент {\tt rand-update}. \index{ru}{генератор случайных чисел|в моделировании методом Монте-Карло||||}
Чтобы понять, насколько это было бы
неприятно, рассмотрим использование случайных чисел для реализации
т.~н.
\index{ru}{моделирование методом Монте-Карло||Monte Carlo simulation|||}\index{en}{Monte Carlo simulation||моделирование методом Монте-Карло|||}{\em моделирования методом
Монте-Карло} (Monte Carlo simulation).
Метод Монте-Карло состоит в том, чтобы случайным образом
выбирать тестовые точки из большого множества и затем делать выводы на
основании вероятностей, оцениваемых по результатам тестов. Например,
можно получить \index{ru}{пи ($\pi$)|оценка Чезаро||||} приближенное значение $\pi$,
используя тот факт, что для двух случайно выбранных
целых чисел вероятность отсутствия общих множителей (то есть,
вероятность того, что их наибольший
общий делитель будет равен 1) составляет
$6/\pi^2$\footnote{Эта теорема доказана Э. Чезаро. Обсуждение и
доказательство можно найти в разделе~4.5.2 книги
Knuth 1981.\index{ru}{Кнут,
Дональд~Э.||Donald~E. Knuth||n|п}\index{en}{Donald~E. Knuth||Кнут,
Дональд~Э.||n|п}\index{ru}{Чезаро, Эрнесто||Ernesto
Ces\`aro||n|п}\index{en}{Ernesto Ces\`aro||Чезаро, Эрнесто||n|п}}.
Чтобы получить приближенное значение
$\pi$, мы производим большое количество тестов.
В каждом тесте мы случайным образом выбираем два числа и проверяем, не
равен ли их НОД единице. Доля тестов, которые проходят, дает нам
\index{ru}{наибольший общий делитель|используемый для оценки $\pi$||||}
приближение к $6/\pi^2$, и отсюда мы получаем
приближенное значение $\pi$.
В центре нашей программы находится процедура
{\tt monte-carlo}, которая в качестве аргументов принимает
количество попыток тестирования, а также сам тест~---
процедуру без аргументов, возвращающую при каждом
вызове либо истину, либо ложь. {\tt Monte-carlo} запускает
тест указанное количество раз и возвращает число, обозначающее долю
попыток, в которых тест вернул истинное значение.
\begin{Verbatim}[fontsize=\small]
(define (estimate-pi trials)\index{ru}{estimate-pi||||pd|}
(sqrt (/ 6 (monte-carlo trials cesaro-test))))
(define (cesaro-test)\index{ru}{cesaro-test||||pd|}
(= (gcd (rand) (rand)) 1))
(define (monte-carlo trials experiment)\index{ru}{monte-carlo||||pd|}
(define (iter trials-remaining trials-passed)
(cond ((= trials-remaining 0)
(/ trials-passed trials))
((experiment)
(iter (- trials-remaining 1) (+ trials-passed 1)))
(else
(iter (- trials-remaining 1) trials-passed))))
(iter trials 0))
\end{Verbatim}
Теперь попробуем осуществить то же вычисление, используя
{\tt rand-update} вместо {\tt rand}, как нам
пришлось бы поступить, если бы у нас не было присваивания для
моделирования локального состояния:
\begin{Verbatim}[fontsize=\small]
(define (estimate-pi trials)
(sqrt (/ 6 (random-gcd-test trials random-init))))
(define (random-gcd-test trials initial-x)
(define (iter trials-remaining trials-passed x)
(let ((x1 (rand-update x)))
(let ((x2 (rand-update x1)))
(cond ((= trials-remaining 0)
(/ trials-passed trials))
((= (gcd x1 x2) 1)
(iter (- trials-remaining 1)
(+ trials-passed 1)
x2))
(else
(iter (- trials-remaining 1)
trials-passed
x2))))))
(iter trials 0 initial-x))
\end{Verbatim}
Хотя программа по-прежнему проста, в ней обнаруживается несколько
болезненных нарушений принципа модульности. В первой версии программы
нам удалось, используя {\tt rand}, выразить метод Монте-Карло
напрямую как обобщенную процедуру
{\tt monte-carlo}, которая в качестве аргумента принимает
произвольную процедуру {\tt experiment}. Во втором варианте
программы, где у генератора случайных чисел нет локального состояния,
{\tt random-gcd-test} приходится непосредственно возиться со случайными
числами {\tt x1} и {\tt x2} и передавать в итеративном
цикле {\tt x2} в качестве нового входа
{\tt rand-update}. Из-за того, что обработка случайных чисел
происходит явно, структура накопления результатов тестов начинает
зависеть от того, что наш тест использует именно два случайных числа,
тогда как для других тестов Монте-Карло может потребоваться, скажем, одно или три.
Даже процедура верхнего уровня {\tt estimate-pi} вынуждена
заботиться о том, чтобы предоставить начальное значение случайного
числа. Поскольку внутренности генератора случайных чисел просачиваются
наружу в другие части программы, задача изолировать
идею метода Монте-Карло так, чтобы применять ее затем к другим
задачам, осложняется. В первом варианте программы присваивание инкапсулирует
состояние генератора случайных чисел внутри
{\tt rand}, так что состояние генератора остается независимым
от остальной программы.
Общее явление, наблюдаемое на примере с методом
Монте-Карло, таково: с точки зрения одной части сложного процесса
кажется, что другие части \mbox{изменяются} со временем. Они обладают
скрытым локальным состоянием. Если мы хотим, чтобы структура
программ, которые мы пишем, отражала
такое разделение на части, мы создаем вычислительные объекты
(например, банковские счета или генераторы случайных чисел), поведение
которых изменяется со временем. Состояние мы моделируем при помощи
локальных переменных, а изменение состояния --- при помощи присваивания
этим переменным.
Здесь возникает соблазн закрыть обсуждение и сказать, что, введя
присваивание и метод сокрытия состояния в локальных переменных, мы
обретаем способность структурировать системы более модульным образом,
чем если бы нам пришлось всем состоянием манипулировать явно,
с передачей дополнительных параметров. К сожалению, как мы увидим, все
не так просто.
\begin{exercise}{3.5}\label{EX3.5}%
\index{ru}{Монте-Карло, интегрирование методом||Monte Carlo integration|||(упр.~3.5)}%
\index{en}{Monte Carlo integration||Монте-Карло, интегрировани методом|||(упр.~3.5)}%
\index{ru}{пи ($\pi$)|приближенное вычисление через интегрирование методом Монте-Карло||||(упр.~3.5)}%
{\em Интегрирование методом
Монте-Карло} (Monte Carlo integration)~--- способ приближенного
вычисления \index{ru}{определенный интеграл|приближенное вычисление
методом Монте-Карло||||(упр.~3.5)}определенных интегралов при помощи
моделирования методом Монте-Карло. Рассмотрим
задачу вычисления площади фигуры, описываемой предикатом
$P(x,y)$, который истинен для точек
$(x,y)$, принадлежащих фигуре, и ложен для
точек вне фигуры. Например, область, содержащаяся в круге с радиусом
3 и центром в точке $(5,7)$, описывается предикатом, проверяющим
$(x-5)^2 + (y-7)^2 \le 3^2$. Чтобы оценить
площадь фигуры, описываемой таким предикатом, для начала выберем
прямоугольник, который содержит нашу фигуру. Например, прямоугольник
с углами $(2,4)$ и $(8,10)$, расположенными по диагонали, содержит
вышеописанный круг. Нужный нам интеграл~--- площадь той части
прямоугольника, которая лежит внутри фигуры. Мы можем оценить
интеграл, случайным образом выбирая точки
$(x,y)$, лежащие внутри прямоугольника, и
проверяя для каждой точки $P(x,y)$, чтобы
определить, лежит ли точка внутри фигуры. Если мы проверим много
точек, доля тех, которые окажутся внутри области, даст нам
приближенное значение отношения площадей фигуры и прямоугольника.
Таким образом, домножив это значение на площадь прямоугольника, мы
получим приближенное значение интеграла.
Реализуйте интегрирование методом Монте-Карло в виде
процедуры {\tt estimate-integral},\index{ru}{estimate-integral||||p|(упр.~3.5)}
которая в качестве
аргументов принимает предикат {\tt P}, верхнюю и нижнюю границы
прямоугольника {\tt x1}, {\tt x2}, {\tt y1}
и {\tt y2}, а также число
проверок, которые мы должны осуществить, чтобы оценить отношение
площадей. Ваша процедура должна использовать ту же самую процедуру
{\tt monte-carlo}, которая выше использовалась для оценки
значения $\pi$. Оцените $\pi$ при помощи
{\tt estimate-integral}, измерив площадь единичного круга.\index{ru}{пи ($\pi$)|аппроксимация через интегрирование методом Монте-Карло||||(упр.~3.5)}
Вам может пригодиться процедура, которая выдает
число, случайно выбранное внутри данного отрезка. Нижеприведенная
процедура {\tt random-in-range} решает эту задачу, используя
процедуру {\tt random}, введенную в
разделе~\ref{EXAMPLE-TESTING-FOR-PRIMALITY}, которая возвращает
неотрицательное число меньше своего аргумента\footnote{\index{ru}{MIT
Scheme|\texttt{random}||||п}\index{ru}{элементарные процедуры|{\tt
random} {\em (нс)}||||п}\index{ru}{random (элементарная
процедура)|MIT Scheme|||p|п}В MIT Scheme есть такая процедура.
Если {\tt random} на вход дается точное целое число (как в
разделе~\ref{EXAMPLE-TESTING-FOR-PRIMALITY}), она возвращает
точное целое число, но если ей дать десятичную дробь (как в этом
примере), она и возвращает десятичную дробь.}.
\begin{Verbatim}[fontsize=\small]
(define (random-in-range low high) \index{ru}{random-in-range||||pd|(упр.~3.5)}
(let ((range (- high low)))
(+ low (random range))))
\end{Verbatim}
\end{exercise}
\begin{exercise}{3.6}\label{EX3.6}%
\index{ru}{rand|со сбрасыванием|||p|(упр.~3.6)}%
\index{ru}{генератор случайных чисел|со сбрасыванием||||(упр.~3.6)}%
Полезно иметь
возможность сбросить генератор случайных
чисел, чтобы получить последовательность, которая начинается с некоторого
числа. Постройте новую процедуру {\tt rand}, которая
вызывается с аргументом. Этот аргумент должен быть либо символом
{\tt generate}, либо символом {\tt reset}. Процедура
работает так: {\tt (rand 'generate)} порождает новое случайное
число; {\tt ((rand 'reset) \textit{$\langle$новое-значение$\rangle$})}
сбрасывает внутреннюю переменную состояния в указанное
\textit{$\langle$новое-значение$\rangle$}. Таким образом, сбрасывая значения,
можно получать повторяющиеся последовательности. Эта возможность
очень полезна при тестировании и отладке программ,
использующих случайные числа.
\end{exercise}
\subsection{Издержки, связанные с введением присваивания}
\label{THE-COSTS-OF-INTRODUCING-ASSIGNMENT}
Как мы только что видели, операция
{\tt set!} позволяет моделировать объекты, обладающие
внутренним состоянием. Однако за это преимущество приходится
\index{ru}{присваивание|расплата за||||} платить.
Наш язык программирования нельзя больше описывать при помощи
подстановочной модели применения процедур, которую мы ввели в
разделе~\ref{SUBST-MODEL-FOR-PROC-APPL}. Хуже того, не существует
простой модели с <<приятными>> математическими свойствами, которая бы
адекватно описывала работу с объектами и присваивание в
языках программирования.
Пока мы не применяем присваивание, два вычисления одной и
той же процедуры с одними и теми же аргументами всегда дают одинаковый
результат. Стало быть, можно считать, что процедуры вычисляют
математические функции. Соответственно, программирование, в котором
присваивание не используется (как у нас в первых
двух главах этой книги), известно как
\index{ru}{функциональное программирование||functional programming|||}\index{en}{functional programming||функциональное программирование|||}{\em функциональное
программирование} (functional programming).
\index{ru}{подстановочная модель применения процедуры|неадекватность||||} Чтобы понять, как присваивание усложняет ситуацию,
рассмотрим упрощенную версию {\tt make-withdraw} из
раздела~\ref{LOCAL-STATE-VARIABLES}, которая не проверяет,
достаточно ли на счете денег:
\begin{Verbatim}[fontsize=\small]
(define (make-simplified-withdraw balance)\index{ru}{make-simplified-withdraw||||pd|}
(lambda (amount)
(set! balance (- balance amount))
balance))
(define W (make-simplified-withdraw 25))
(W 20)
\textit{5}
(W 10)
\textit{-5}
\end{Verbatim}
Сравним эту процедуру со следующей процедурой
{\tt make-decrementer}, которая не использует
{\tt set!}:
\begin{Verbatim}[fontsize=\small]
(define (make-decrementer balance)\index{ru}{make-decrementer||||pd|}
(lambda (amount)
(- balance amount)))
\end{Verbatim}
{\tt make-decrementer} возвращает процедуру, которая вычитает
свой аргумент из определенного числа {\tt balance}, но при
последовательных вызовах ее действие не накапливается, как при
использовании {\tt make\--simpli\-fied\--with\-draw}:
\begin{Verbatim}[fontsize=\small]
(define D (make-decrementer 25))
(D 20)
\textit{5}
(D 10)
\textit{15}
\end{Verbatim}
Мы можем объяснить, как работает {\tt make-decrementer}, при
помощи подстановочной модели. Например, рассмотрим, как вычисляется
выражение
\begin{Verbatim}[fontsize=\small]
((make-decrementer 25) 20)
\end{Verbatim}
Сначала мы упрощаем операторную часть комбинации, подставляя в теле
{\tt make-decrementer} вместо {\tt balance} 25.
Выражение сводится к
\begin{Verbatim}[fontsize=\small]
((lambda (amount) (- 25 amount)) 20)
\end{Verbatim}
Теперь мы применяем оператор к операнду, подставляя 20 вместо
{\tt amount} в теле {\tt lambda}-выра\-же\-ния:
\begin{Verbatim}[fontsize=\small]
(- 25 20)
\end{Verbatim}
Окончательный результат равен 5.
Посмотрим, однако, что произойдет, если мы попробуем
применить подобный подстановочный анализ к
{\tt make-sim\-pli\-fied-withdraw}:
\sloppy
\begin{Verbatim}[fontsize=\small]
((make-simplified-withdraw 25) 20)
\end{Verbatim}
Сначала мы упрощаем оператор, подставляя вместо {\tt balance}
25 в теле {\tt make\-simplified-withdraw}. Таким образом, наше
выражение сводится к\footnote{Мы не производим подстановку вхождения
{\tt balance} в выражение {\tt set!}, поскольку
\textit{$\langle$имя$\rangle$} в {\tt set!} не вычисляется. Если бы мы
провели подстановку, получилось бы {\tt (set! 25 (- 25
amount))}, а это не имеет никакого смысла.}
\begin{Verbatim}[fontsize=\small]
((lambda (amount) (set! balance (- 25 amount)) 25) 20)
\end{Verbatim}
Теперь мы применяем оператор к операнду, подставляя в теле
{\tt lambda}-вы\-ра\-же\-ния 20 вместо {\tt amount}:
\begin{Verbatim}[fontsize=\small]
(set! balance (- 25 20)) 25
\end{Verbatim}
Если бы мы следовали подстановочной модели, нам пришлось бы сказать,
что вычисление процедуры состоит в том, чтобы сначала присвоить
переменной {\tt balance} значение 5, а затем в качестве
значения вернуть 25. Но это дает неверный ответ. Чтобы получить
правильный ответ, нам пришлось бы как-то отличить первое вхождение
{\tt balance} (до того, как сработает {\tt set!})
от второго (после выполнения {\tt set!}).
Подстановочная модель на это не способна.
Проблема здесь состоит в том, что подстановка предполагает,
что символы в нашем языке --- просто имена для значений. Но как только
мы вводим {\tt set!} и представление, что значение переменной
может изменяться, переменная уже не может быть всего лишь именем.
Теперь переменная некоторым образом соответствует месту, в котором
может храниться значение, и значение это может меняться. В
разделе~\ref{THE-ENVIRONMENT-MODEL-OF-EVALUATION} мы
увидим, как в нашей модели вычислений роль этого <<места>> играют
окружения.
\paragraph{Тождественность и изменение}
\index{ru}{тождественность и изменение|значение|sameness and
change|||}\index{en}{sameness and change||тождественность и
изменение|значение||}\index{ru}{изменение и
тождественность|значение|change and sameness|||}\index{en}{change
and sameness||изменение и тождественность|значение||}Проблема,
которая здесь встает, глубже, чем просто
поломка определенной модели вычислений. Как только мы вводим в наши
вычислительные модели понятие изменения, многие другие понятия,
которые до сих пор были ясны, становятся сомнительными. Рассмотрим
вопрос, что значит, что две вещи суть <<одно и то же>>.
Допустим, мы два раза зовем {\tt make-decrementer}
с одним и тем же аргументом, и получаем две процедуры:
\begin{Verbatim}[fontsize=\small]
(define D1 (make-decrementer 25))
(define D2 (make-decrementer 25))
\end{Verbatim}
Являются ли {\tt D1} и {\tt D2} одним и тем же объектом?
Можно сказать, что да, поскольку {\tt D1} и {\tt D2}
обладают одинаковым поведением~--- каждая из этих процедур вычитает
свой аргумент из 25. В сущности, в любом вычислении можно подставить
{\tt D1} вместо {\tt D2}, и результат не изменится.
Напротив, рассмотрим два вызова
{\tt make-simplified-withdraw}:
\begin{Verbatim}[fontsize=\small]
(define W1 (make-simplified-withdraw 25))
(define W2 (make-simplified-withdraw 25))
\end{Verbatim}
Являются ли {\tt W1} и {\tt W2} одним и тем же? Нет,
конечно, потому что вызовы {\tt W1} и {\tt W2} приводят
к различным результатам, как показывает следующая последовательность
вычислений:
\begin{Verbatim}[fontsize=\small]
(W1 20)
\textit{5}
(W1 20)
\textit{-15}