forked from alexott/sicp-ru
-
Notifications
You must be signed in to change notification settings - Fork 0
/
chapter-2.tex
8338 lines (7358 loc) · 553 KB
/
chapter-2.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{Построение абстракций с помощью данных}
\thispagestyle{empty}
\label{BUILDING-ABSTRACTIONS-WITH-DATA}
%\markboth{Глава 2 \qquad Построение абстракций с помощью данных}{}
\epigraph{
Теперь мы подходим к решающему шагу в математической
абстракции: мы забываем, что обозначают наши символы. ...[Математик]
не должен стоять на месте: есть много операций, которые он может
производить с этими символами, не обращая внимания на те вещи, которые
они обозначают.
\index{ru}{Вейль, Герман||Hermann Weyl||n|}\index{en}{Hermann Weyl||Вейль, Герман||n|}}{Герман Вейль. \\ <<Математический способ мышления>>}
\index{ru}{данные|составные||||} В главе~\ref{BUILDING-ABSTRACTIONS-WITH-PROCEDURES}
мы сконцентрировали внимание на вычислительных процессах и роли
процедур в проектировании программ. Мы рассмотрели, как использовать
простейшие данные (числа) и простейшие операции (арифметические), как
сочетать процедуры и получать составные процедуры с помощью
композиции, условных выражений и использования параметров, а
также как строить абстрактные процедуры при помощи
{\tt define}. Мы убедились, что процедуру можно рассматривать
как схему локального развития процесса; мы классифицировали некоторые
общие схемы процессов, воплощенные в процедурах,
строили о них умозаключения и производили их простейший алгоритмический
анализ. Кроме того,
мы увидели, что процедуры высших порядков увеличивают выразительную
силу нашего
языка, позволяя оперировать общими методами вычисления, а
следовательно, и проводить рассуждения в их терминах. Это во многом и
составляет сущность программирования.
В этой главе мы будем рассматривать более сложные
данные.
Все процедуры главы~\ref{BUILDING-ABSTRACTIONS-WITH-PROCEDURES} работают с
простыми численными данными, а простых численных данных часто бывает
недостаточно для тех задач, которые мы хотим решать с помощью
вычислений. Программы, как правило, пишут, чтобы моделировать сложные
явления, и чаще всего приходится строить вычислительные объекты,
состоящие из нескольких частей, чтобы смоделировать многосторонние
явления реального мира. Таким образом, в отличие от главы~\ref{BUILDING-ABSTRACTIONS-WITH-PROCEDURES}, где наше внимание
было в основном направлено на создание абстракций с помощью
сочетания процедур и построения составных процедур, в этой главе мы
обращаемся к другой важной характеристике всякого языка
программирования: тем средствам, которые он предоставляет для создания
абстракций с помощью сочетания объектов данных и построения
\index{ru}{составные данные, их необходимость||compound data, need for|||}\index{en}{compound data, need for||составные данные, их необходимость|||}{\em составных данных} (compound data).
Для чего в языке программирования нужны составные данные? По
тем же причинам, по которым нужны составные процедуры: мы хотим
повысить понятийный уровень, на котором мы проектируем
программы, хотим сделать наши проекты более модульными и увеличить
выразительную силу языка. Точно так же, как способность
определять процедуры дает возможность работать с процессами на
более высоком содержательном уровне, чем уровень элементарных операций
языка, способность конструировать составные объекты данных
позволяет работать с данными на более высоком понятийном уровне,
чем уровень элементарных данных нашего языка.
\index{ru}{рациональная арифметика|необходимость составных данных|rational-number arithmetic|||}\index{en}{rational-number arithmetic||рациональная арифметика|необходимость составных данных||}%
Рассмотрим задачу проектирования системы для арифметических
вычислений с рациональными числами. Мы можем представить себе
операцию {\tt add-rat}, которая принимает два рациональных
числа и вычисляет их сумму. В терминах простейших данных, рациональное
число можно рассматривать как два целых числа: числитель и
знаменатель. Таким образом, мы могли бы сконструировать программу, в
которой всякое рациональное число представлялось бы как пара целых
(числитель и знаменатель) и {\tt add-rat} была бы реализована
как две процедуры (одна из которых вычисляла бы числитель суммы, а
другая знаменатель). Однако это было бы крайне неудобно, поскольку
нам приходилось бы следить, какие числители каким знаменателям
соответствуют. Если бы системе требовалось производить
большое количество операций над большим количеством рациональных
чисел, такие служебные детали сильно затемняли бы наши
программы, не говоря уже о наших мозгах. Было бы намного проще,
если бы мы могли <<склеить>> числитель со знаменателем и получить пару
--- \index{ru}{составной объект данных||compound data object|||}\index{en}{compound data object||составной объект данных|||}{\em составной объект
данных} (compound data object),~--- с которой наши программы могли бы обращаться
способом, соответствующим нашему представлению о рациональном числе как о
едином понятии.
Кроме того, использование составных данных позволяет
увеличить модульность программ. Если бы мы могли обрабатывать
рациональные числа непосредственно как объекты, то можно было бы отделить ту
часть программы, которая работает собственно с рациональными
числами, от деталей представления рационального числа в
виде пары целых. Общий метод отделения частей программы, которые
имеют дело с представлением объектов данных, от тех частей,
где эти объекты данных используются,~--- это мощная методология
проектирования, называемая \index{ru}{абстракция данных||data abstraction|||}\index{en}{data abstraction||абстракция данных|||}{\em абстракция
данных} (data abstraction). Мы увидим, как с помощью абстракции данных программы
становится легче проектировать, поддерживать и изменять.
Использование составных данных ведет к настоящему увеличению
выразительной силы нашего языка программирования. Рассмотрим идею
порождения <<линейной комбинации>> $ax + by$. Нам может
потребоваться процедура, которая принимала бы как аргументы
$a$, $b$, $x$ и $y$ и
возвращала бы значение $ax + by$. Если аргументы являются
числами, это не представляет никакой трудности, поскольку мы сразу
можем определить процедуру
\begin{Verbatim}[fontsize=\small]
(define (linear-combination a b x y)
(+ (* a x) (* b y)))
\end{Verbatim}
Предположим, однако, что нас интересуют не только числа. Предположим,
что нам хотелось бы выразить в процедурных терминах идею о том, что
можно строить линейные комбинации всюду, где определены сложение и
умножение~--- для рациональных и комплексных чисел, многочленов и
многого другого. Мы могли бы выразить это как процедуру в следующей форме:
\begin{Verbatim}[fontsize=\small]
(define (linear-combination a b x y)
(add (mul a x) (mul b y)))
\end{Verbatim}
где {\tt add} и {\tt mul}~--- не элементарные процедуры
{\tt +} и {\tt *}, а более сложные устройства, которые
проделывают соответствующие операции, какие бы типы данных мы ни
передавали как аргументы {\tt a}, {\tt b},
{\tt x} и {\tt y}. Здесь важнейшая деталь состоит в
том, что единственное, что требуется знать процедуре
{\tt linear-combination} об {\tt a}, {\tt b},
{\tt x} и {\tt y}~--- это то, что процедуры
{\tt add} и {\tt mul} проделывают соответствующие
действия. С точки зрения процедуры
{\tt linear-combination} несущественно, что такое
{\tt a}, {\tt b}, {\tt x} и {\tt y}, и еще
менее существенно, как они могут быть представлены через более
простые данные. Этот же пример показывает, почему так важно, чтобы в
нашем языке программирования была возможность прямо работать с
составными объектами: иначе у процедур, подобных
{\tt linear-combination}, не было бы способа передать аргументы
в {\tt add} и {\tt mul}, не зная деталей их устройства\footnote{Способность прямо оперировать процедурами увеличивает
выразительную силу нашего языка программирования подобным же образом.
Например, в разделе~\ref{PROCEDURES-AS-ARGUMENTS} мы
ввели процедуру {\tt sum}, которая принимает в качестве
аргумента процедуру {\tt term} и вычисляет сумму значений
{\tt term} на некотором заданном интервале. Чтобы определить
{\tt sum}, нам необходимо иметь возможность говорить о процедуре
типа {\tt term} как о едином целом, независимо от того, как она
выражена через более простые операции. Вообще говоря,
не имей мы понятия <<процедуры>>, вряд ли мы и думать могли бы
о возможности определения такой операции, как
{\tt sum}. Более того, пока мы размышляем о суммировании,
детали того, как {\tt term} может быть составлен из более
простых операций, несущественны.
}.
Мы начинаем эту главу с реализации описанной выше системы
арифметики рациональных чисел. Это послужит основанием для
обсуждения составных данных и абстракции данных. Как и в
случае с составными процедурами, основная мысль состоит в том, что
абстракция является методом ограничения сложности, и мы увидим, как
абстракция данных позволяет нам возводить полезные
\index{ru}{барьеры абстракции||abstraction barriers|||}\index{en}{abstraction barriers||барьеры абстракции|||}{\em барьеры абстракции} (abstraction barriers) между разными
частями программы.
Мы увидим, что главное в работе с составными данными~--- то,
что язык программирования должен предоставлять нечто вроде <<клея>>,
так, чтобы объекты данных могли сочетаться, образуя более сложные
объекты данных. Существует множество возможных типов клея.
На самом деле мы обнаружим, что составные данные можно порождать
вообще без использования каких-либо специальных операций, относящихся к
<<данным>>~--- только с помощью процедур. Это еще больше размоет границу между
<<процедурами>> и <<данными>>, которая уже к концу главы~\ref{BUILDING-ABSTRACTIONS-WITH-PROCEDURES} оказалась
весьма тонкой. Мы также исследуем некоторые общепринятые методы
представления последовательностей и деревьев. Важная идея в работе с
составными данными~--- понятие \index{ru}{замыкание||closure|||}\index{en}{closure||замыкание|||}{\em замыкания} (closure): клей для
сочетания объектов данных должен позволять нам склеивать не только
элементарные объекты данных, но и составные. Еще одна важная идея
состоит в том, что составные объекты данных могут служить
\index{ru}{стандартный интерфейс||conventional interface|||}\index{en}{conventional interface||стандартный интерфейс|||}{\em стандартными интерфейсами} (conventional interfaces), так,
чтобы модули программы могли сочетаться методом подстановки.
Некоторые из этих идей мы продемонстрируем с помощью простого
графического языка, использующего замыкание.
Затем мы увеличим выразительную мощность нашего языка путем
введения \index{ru}{выражение|символьное||||} \index{ru}{символьное выражение||symbolic expression|||}\index{en}{symbolic expression||символьное выражение|||}{\em символьных выражений} (symbolic expressions)~--- данных,
элементарные части которых могут быть произвольными символами, а не
только числами. Мы рассмотрим различные варианты представления
множеств объектов. Мы обнаружим, что, подобно тому, как одна и та же
числовая функция может вычисляться различными вычислительными
процессами, существует множество способов представить некоторую
структуру данных через элементарные объекты, и выбор представления
может существенно влиять на запросы манипулирующих
этими данными процессов к памяти и ко времени. Мы исследуем эти идеи в
контексте символьного дифференцирования, представления множеств и
кодирования информации.
\looseness=-1
После этого мы обратимся к задаче работы с данными, которые
по-разному могут быть представлены в различных частях программы. Это
ведет к необходимости ввести \index{ru}{операция|обобщенные|operation|||}\index{en}{operation||операция|обобщенные||}
\index{ru}{обобщенные операции||generic operations|||}\index{en}{generic operations||обобщенные операции|||}{\em обобщенные операции} (generic operations), которые обрабатывают много различных
типов данных. Поддержка модульности в присутствии обобщенных операций
требует более мощных барьеров абстракции, чем тех, что получаются
с помощью простой абстракции данных. А именно, мы вводим
\index{ru}{программирование, управляемое данными||data-directed programming|||}\index{en}{data-directed programming||программирование, управляемое данными|||}{\em программирование,
управляемое данными} (data-directed programming) как метод, который позволяет проектировать
представления данных отдельно, а затем сочетать их
\index{ru}{аддитивность||additivity|||}\index{en}{additivity||аддитивность|||}{\em аддитивно} (additively) (т. е., без модификации).
Чтобы про\-иллюстрировать силу этого подхода к проектированию систем, в
завершение главы мы применим то, чему в ней научились, к реализации
пакета символьной арифметики многочленов, коэффициенты которых
могут быть целыми, рациональными числами, комплексными
числами и даже другими многочленами.
%\looseness=-1
\section{Введение в абстракцию данных}
\label{INTRODUCTION-TO-DATA-ABSTRACTION}
В разделе~\ref{PROCEDURES-AS-BLACK-BOX-ABSTRACTIONS} мы заметили,
что процедура, которую мы используем как элемент при создании более
сложной процедуры, может рассматриваться не только как
последовательность определенных операций, но и как процедурная
абстракция: детали того, как процедура реализована, могут
быть скрыты, и сама процедура может быть заменена на другую с подобным
поведением. Другими словами, мы можем использовать
абстракцию для отделения способа использования процедуры от того, как
эта процедура реализована в терминах более простых процедур.
Для составных данных подобное понятие называется
\index{ru}{абстракция данных||data abstraction|||}\index{en}{data abstraction||абстракция данных|||}{\em абстракция данных} (data abstraction). Абстракция
данных~--- это методология, которая позволяет
отделить способ использования составного объекта данных от деталей того, как
он составлен из элементарных данных.
Основная идея абстракции данных состоит в том, чтобы строить
программы, работающие с составными данными, так, чтобы
иметь дело с \index{ru}{данные|абстрактные||||}\index{ru}{абстрактные
данные||abstract data|||}\index{en}{abstract data||абстрактные
данные|||}<<абстрактными данными>>. То есть, используя данные, наши
программы не должны делать о них никаких
предположений, кроме абсолютно необходимых для
выполнения поставленной задачи. В то же время
\index{ru}{конкретное представление данных||concrete data
representation|||}\index{en}{concrete data
representation||конкретное представление
данных|||}\index{ru}{данные|<<конкретное
представление>>||||}<<конкретное>>
представление данных определяется независимо от программ, которые эти
данные используют. Интерфейсом между двумя этими частями системы
служит набор процедур, называемых \index{ru}{селектор||selector|||}\index{en}{selector||селектор|||}{\em селекторами} (selectors)
и \index{ru}{конструктор||constructor|||}\index{en}{constructor||конструктор|||}{\em конструкторами} (constructors), реализующих
абстрактные данные в терминах конкретного представления. Чтобы
проиллюстрировать этот метод, мы рассмотрим, как построить набор
процедур для работы с рациональными числами.
\subsection{Пример: арифметические операции над рациональными числами}
\label{EXMP-ARITH-OPER-FOR-RAT-NUMBERS}
\index{ru}{рациональные числа|арифметические операции|rational numbers|||}\index{en}{rational numbers||рациональные числа|арифметические операции||}Допустим, нам нужно работать с
рациональной арифметикой.\index{ru}{арифметика|рациональная||||}\index{ru}{рациональная арифметика|||||}
Нам требуется складывать, вычитать, умножать и делить рациональные
числа, а также проверять, равны ли два рациональных числа друг
другу.
Для начала предположим, что у нас уже есть способ построить
рациональное число из его числителя и знаменателя. Кроме того, мы
предполагаем, что имея рациональное число, мы можем получить его
числитель и знаменатель. Допустим также, что эти конструктор и два
селектора доступны нам в виде процедур:
\begin{plainlist}
\item
{\tt (make-rat {\it $\langle$n$\rangle$}
{\it $\langle$d$\rangle$})}
\index{ru}{make-rat||||p|}
возвращает рациональное число, числитель
которого целое {\it $\langle$n$\rangle$}, а знаменатель~--- целое {\it $\langle$d$\rangle$}.
\item
{\tt (numer {\it $\langle$x$\rangle$})}
\index{ru}{numer||||p|}
возвращает числитель рационального числа {\it $\langle$x$\rangle$}.
\item
{\tt (denom {\it $\langle$x$\rangle$})}
\index{ru}{denom||||p|}
возвращает знаменатель рационального числа {\it $\langle$x$\rangle$}.
\end{plainlist}
Здесь мы используем мощную стратегию синтеза:
\index{ru}{мечтать не вредно||wishful thinking|||}\index{en}{wishful thinking||мечтать не вредно|||}{\em мечтать не вредно} (wish\-ful thin\-king). Пока что мы не
сказали, как представляется рациональное число и как должны
реализовываться процедуры {\tt numer}, {\tt denom} и
{\tt make-rat}. Тем не менее, если бы эти процедуры у нас
были, мы могли бы складывать, вычитать, умножать, делить и проверять
на равенство с помощью следующих отношений:
$$
\frac{n_1}{d_1} + \frac{n_2}{d_2}
= \frac{n_1 d_2 + n_2 d_1}{d_1 d_2}
$$
$$
\frac{n_1}{d_1} - \frac{n_2}{d_2}
= \frac{n_1 d_2 - n_2 d_1}{d_1 d_2}
$$
$$
\frac{n_1}{d_1} \cdot \frac{n_2}{d_2}
= \frac{n_1 n_2}{d_1 d_2}
$$
$$
\frac{n_1 / d_1}{n_2 / d_2}
= \frac{n_1 d_2}{d_1 n_2}
$$
$$
\frac{n_1}{d_1} = \frac{n_2}{d_2} \mbox{ тогда и только тогда,
когда } n_1 d_2 = n_2 d_1
$$
Мы можем выразить эти правила в процедурах:
\begin{Verbatim}[fontsize=\small]
(define (add-rat x y)\index{ru}{add-rat||||pd|}
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (sub-rat x y)\index{ru}{sub-rat||||pd|}
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (mul-rat x y)\index{ru}{mul-rat||||pd|}
(make-rat (* (numer x) (numer y))
(* (denom x) (denom y))))
(define (div-rat x y)\index{ru}{div-rat||||pd|}
(make-rat (* (numer x) (denom y))
(* (denom x) (numer y))))
(define (equal-rat? x y)\index{ru}{equal-rat?||||pd|}
(= (* (numer x) (denom y))
(* (numer y) (denom x))))
\end{Verbatim}
Теперь у нас есть операции над рациональными числами,
определенные в терминах процедур~--- селекторов и конструкторов
{\tt numer}, {\tt denom} и {\tt make-rat}.
Однако сами эти процедуры мы еще не написали. Нам нужен какой-нибудь
способ склеить вместе числитель и знаменатель, чтобы получить
рациональное число.
\paragraph{Пары}
Для реализации конкретного уровня
абстракции данных в нашем языке имеется составная структура, называемая
\index{ru}{пара (пары)||pair(s)|||}\index{en}{pair(s)||пара (пары)|||}{\em парой} (pair), и она создается с помощью
элементарной процедуры {\tt cons}. Эта\index{ru}{cons (элементарная
процедура)||||p|}\index{ru}{элементарные процедуры|{\tt cons}||||}
процедура принимает два аргумента и возвращает объект данных, который
содержит эти два аргумента в качестве частей. Имея пару, мы можем
получить ее части с помощью элементарных процедур {\tt
car}\index{ru}{car (элементарная процедура)||||p|}
\index{ru}{элементарные процедуры|{\tt car}||||}\index{ru}{cdr
(элементарная процедура)||||p|}\index{ru}{элементарные
процедуры|{\tt cdr}||||} и {\tt cdr}\footnote{{\tt Cons} означает
{\em construct}\index{ru}{cons (элементарная
процедура)|происхождение имени|||p|п}
(построить, сконструировать, собрать). Имена {\tt car} и {\tt cdr}
происходят из исходной\index{ru}{Lisp (Лисп)|исходная реализация на IBM 704||||п}
реализации Лиспа на\index{ru}{IBM 704|||||п} IBM 704. Схема адресации
этой машины позволяла обращаться к <<адресной>> и
<<декрементной>> частям ячейки памяти. {\tt Car}
означает\index{ru}{car (элементарная процедура)|происхождение
имени|||p|п}
{\em Contents of Address Part of Register} (содержимое адресной
части регистра), а {\tt cdr} (произносится <<куддер>>)
означает\index{ru}{cdr (элементарная процедура)|происхождение
имени|||p|п}
{\em Contents of Decrement Part of Register} (содержимое
декрементной части регистра).}.
Таким образом, использовать {\tt cons},
{\tt car} и {\tt cdr} можно так:
\begin{Verbatim}[fontsize=\small]
(define x (cons 1 2))
(car x)
\textit{1}
(cdr x)
\textit{2}
\end{Verbatim}
Заметим, что пара является объектом, которому можно дать имя и
работать с ним, подобно элементарному объекту данных. Более того, можно
использовать {\tt cons} для создания пар, элементы которых сами
пары, и так далее:
\begin{Verbatim}[fontsize=\small]
(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
(car (car z))
\textit{1}
(car (cdr z))
\textit{3}
\end{Verbatim}
В разделе~\ref{HIERARCHICAL-DATA-AND-THE-CLOSURE-PROPERTY}
мы увидим, что из этой возможности сочетать пары следует возможность
их использовать как строительные блоки общего назначения при создании
любых сложных структур данных. Один-единственный примитив составных
данных {\em пара}, реализуемый процедурами {\tt cons},
{\tt car} и {\tt cdr},~--- вот и весь клей, который нам
нужен. Объекты данных, составленные из пар, называются
\index{ru}{списковая структура|||||}\index{ru}{данные|со списковой
структурой||||}\index{ru}{данные|со списковой
структурой||list-structured||}\index{en}{|list-structured|данные|со
списковой структурой||}{\em данные со списковой структурой}
(list-structured data).
\paragraph{Представление рациональных чисел}
Пары позволяют нам естественным образом завершить построение
системы рациональных чисел.\index{ru}{рациональные числа|представление в виде пар||||} Будем просто представлять рациональное
число в виде пары двух целых чисел: числителя и знаменателя. Тогда
{\tt make-rat}, {\tt numer} и {\tt denom}
немедленно реализуются следующим образом\footnote{Другой способ определить селекторы и конструктор был
бы
\begin{Verbatim}
(define make-rat cons)
(define numer car)
(define denom cdr)
\end{Verbatim}
Первое определение связывает имя {\tt make-rat} со значением
выражения {\tt cons}, то есть элементарной процедурой, которая
строит пары. Таким образом, {\tt make-rat} и {\tt cons}
становятся именами для одного и того же элементарного конструктора.
Такое определение конструкторов и селекторов
эффективно: вместо того, чтобы заставлять {\tt make-rat}
{\em вызывать} {\tt cons}, мы делаем
{\tt make-rat} и {\tt cons} {\em одной и той же
процедурой}, так что когда вызывается {\tt make-rat},
происходит вызов только одной процедуры, а не двух. С другой стороны,
это не дает работать отладочным средствам, которые отслеживают вызовы процедур
или устанавливают на них контрольные точки: Вам может потребоваться
следить за вызовами {\tt make-rat}, но Вы уж точно никогда не
захотите отслеживать каждый вызов {\tt cons}.
В этой книге мы решили не использовать такой стиль
определений.}.
\begin{Verbatim}[fontsize=\footnotesize]
(define (make-rat n d) (cons n d))\index{ru}{make-rat||||pd|}
(define (numer x) (car x))\index{ru}{numer||||pd|}
(define (denom x) (cdr x))\index{ru}{denom||||pd|}
\end{Verbatim}
Кроме того, когда нам требуется выводить результаты вычислений,
мы \index{ru}{рациональные числа|печать||||}
печатаем рациональное число, сначала выводя его числитель, затем
косую черту и затем знаменатель\footnote{\index{ru}{печать,
элементарные процедуры||primitives for
printing|||п}\index{en}{primitives for printing||печать,
элементарные процедуры|||п}{\tt Display}\index{ru}{display
(элементарная процедура)||||pd|п}\index{ru}{элементарные
процедуры|{\tt display}||||п}\index{ru}{неопределенные
значения|\texttt{display}||||п}
--- элементарная процедура языка
Scheme для печати данных. Другая элементарная процедура,
{\tt newline},\index{ru}{newline (элементарная
процедура)||||pd|п}\index{ru}{элементарные процедуры|{\tt
newline}||||п}\index{ru}{неопределенные
значения|\texttt{newline}||||п}
переводит строку при печати. Эти
процедуры не возвращают никакого полезного значения, так что в примерах
использования {\tt print-rat} ниже, мы показываем только то,
что печатает {\tt print-rat}, а не то, что интерпретатор
выводит как значение {\tt print-rat}.}:%fontsize in footnote: small>fnsize--MR
\begin{Verbatim}[fontsize=\small]
(define (print-rat x) \index{ru}{print-rat||||pd|}
(newline)
(display (numer x))
(display "/")
(display (denom x)))
\end{Verbatim}
Теперь мы можем опробовать процедуры работы с рациональными
числами:
\begin{Verbatim}[fontsize=\small]
(define one-half (make-rat 1 2))
(print-rat one-half)
\textit{1/2}
(define one-third (make-rat 1 3))
(print-rat (add-rat one-half one-third))
\textit{5/6}
(print-rat (mul-rat one-half one-third))
\textit{1/6}
(print-rat (add-rat one-third one-third))
\textit{6/9}
\end{Verbatim}
Как показывает последний пример, наша реализация
рациональных чисел не приводит их к наименьшему знаменателю.
\index{ru}{рациональные числа|приведение к наименьшему знаменателю||||}
\index{ru}{приведение к наименьшему знаменателю||reducing to lowest terms|||}\index{en}{reducing to lowest terms||приведение к наименьшему знаменателю|||}
Мы можем исправить это упущение, изменив
{\tt make-rat}. Если у нас
есть процедура {\tt gcd}\index{ru}{наибольший общий
делитель|используемый в арифметике рациональных чисел||||},
вычисляющая наибольший общий делитель
двух целых чисел, вроде той, которая описана в
разделе~\ref{GREATEST-COMMON-DIVISORS}, мы можем с помощью
{\tt gcd} сокращать числитель и знаменатель, прежде, чем
построить пару:
\begin{Verbatim}[fontsize=\small]
(define (make-rat n d)\index{ru}{make-rat|приведение к наименьшему знаменателю|||pd|}
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
\end{Verbatim}
Теперь мы имеем
\begin{Verbatim}[fontsize=\small]
(print-rat (add-rat one-third one-third))
\textit{2/3}
\end{Verbatim}
как нам того и хотелось. Эта модификация была произведена путем
изменения конструктора {\tt make-rat}, и мы не тронули ни одну
из процедур (скажем, {\tt add-rat} или {\tt mul-rat}),
которые реализуют сами операции.
\begin{exercise}{2.1}\label{EX2.1}%
Определите улучшенную версию {\tt make-rat},
которая принимала бы как положительные, так и отрицательные
аргументы. {\tt Make-rat} должна нормализовывать знак так,
чтобы в случае, если рациональное число положительно, то и его числитель, и
знаменатель были бы положительны, а если оно отрицательно, то чтобы только его
числитель был отрицателен.
\end{exercise}
\subsection{Барьеры абстракции}
\label{ABSTRACTION-BARRIERS}
\index{ru}{барьеры абстракции|||||}
Прежде чем мы перейдем к другим примерам работы с
составными данными и абстракцией данных, рассмотрим несколько
вопросов, относящихся к примеру с рациональными числами. Мы
определили операции над рациональными числами через конструктор
{\tt make-rat} и селекторы {\tt numer} и
{\tt denom}. В общем случае основная идея абстракции данных
состоит в том, чтобы определить для каждого типа объектов данных набор
базовых операций, через которые будут выражаться все действия с
объектами этого типа, и затем при работе с данными использовать только
этот набор операций.
\begin{cntrfig}
\begin{tabular}{rcl}
\rule{1cm}{0,5pt} & \hspace{-1,2em}\fbox{\parbox{8cm}{Программы, использующие рациональные числа}}
&\hspace{-1,55em} \rule{1cm}{0,5pt} \\[7pt]
\multicolumn{3}{c}{Рациональные числа в предметной области}\\[9pt]
\rule{1cm}{0,5pt} & \hspace{-1,2em}\fbox{\parbox{8cm}{\centering{\tt add-rat sub-rat ...}}}
&\hspace{-1,55em} \rule{1cm}{0,5pt} \\[7pt]
\multicolumn{3}{c}{Рациональные числа как числители со знаменателями}\\[9pt]
\rule{1cm}{0,5pt} & \hspace{-1,2em}\fbox{\parbox{8cm}{\centering{\tt make-rat numer denom}}}
&\hspace{-1,55em} \rule{1cm}{0,5pt} \\[7pt]
\multicolumn{3}{c}{Рациональные числа как пары}\\[9pt]
\rule{1cm}{0,5pt} & \hspace{-1,2em}\fbox{\parbox{8cm}{\centering{\tt cons car cdr}}}
&\hspace{-1,55em} \rule{1cm}{0,5pt} \\[7pt]
\multicolumn{3}{c}{То, как реализуются пары}\\
\end{tabular}
\caption{Барьеры абстракции данных в пакете для
работы с рациональными числами.}
\label{P2.1}
\end{cntrfig}
Мы можем представить себе структуру системы работы с
рациональными числами так, как это показано на рис.~\ref{P2.1}. Горизонтальные линии обозначают
\index{ru}{барьеры абстракции||abstraction barrier|||}\index{en}{abstraction barrier||барьеры абстракции|||}{\em барьеры абстракции} (abstraction barriers), которые
отделяют различные <<уровни>> системы друг от друга. На каждом из
этих уровней барьер отделяет программы, которые используют абстрактные
данные (сверху) от программ, которые реализуют эту абстракцию данных
(внизу). Программы, использующие рациональные числа, работают с ними
исключительно в терминах процедур, которые пакет работы с
рациональными числами предоставляет <<для общего пользования>>:
{\tt add-rat}, {\tt sub-rat}, {\tt mul-rat},
{\tt div-rat} и {\tt equal-rat?}. В свою очередь, эти
процедуры используют только \index{ru}{конструктор|как барьер абстракции||||}конструктор и \index{ru}{селектор|как барьер абстракции||||}селекторы
{\tt make-rat}, {\tt numer} и
{\tt denom}, которые сами реализованы при помощи пар. Детали
реализации пар не имеют значения для остальной части
пакета работы с рациональными числами; существенно только, что с
парами можно работать при помощи {\tt cons}, {\tt car} и
{\tt cdr}. По существу, процедуры на каждом уровне являются
интерфейсами, которые определяют барьеры абстракции и связывают
различные уровни.
\looseness=-1
У этой простой идеи много преимуществ. Одно из них
состоит в том, что программы становится намного проще поддерживать и
изменять. Любая сложная структура может быть представлена через
элементарные структуры данных языка программирования многими
способами. Разумеется, выбор представления влияет на программы,
работающие с этим представлением; так что, если когда-нибудь позднее
его нужно будет изменить, соответственно придется изменить и
все эти программы. В случае больших программ эта задача может быть
весьма трудоемкой и дорогой, если зависимость от представления не
будет при проектировании ограничена несколькими программными
модулями.
\looseness=-1
\index{ru}{рациональные числа|приведение к наименьшему знаменателю||||}%
\index{ru}{приведение к наименьшему знаменателю|||||}%
Например, другим
способом решения задачи приведения
рациональных чисел к наименьшему знаменателю было бы производить
сокращение не тогда, когда мы конструируем число, а каждый раз, как мы
к нему обращаемся. При этом потребуются другие конструктор и
селекторы:
\begin{Verbatim}[fontsize=\small]
\samepage
(define (make-rat n d)\index{ru}{make-rat||||pd|}
(cons n d))
(define (numer x)\index{ru}{numer|с приведением к наименьшему знаменателю|||pd|}
(let ((g (gcd (car x) (cdr x))))
(/ (car x) g)))
(define (denom x)\index{ru}{denom|с приведением к наименьшему знаменателю|||pd|}
(let ((g (gcd (car x) (cdr x))))
(/ (cdr x) g)))
\end{Verbatim}
Разница между этой реализацией и предыдущей состоит в том, когда мы
вычисляем НОД с помощью {\tt gcd}. Если при типичном использовании
рациональных чисел к числителю и знаменателю одного и того же
рационального числа мы обращаемся по многу раз, вычислять НОД лучше
тогда, когда рациональное число конструируется. Если нет, нам может
быть выгодно подождать с его вычислением до времени обращения. В любом
случае, когда мы переходим от одной реализации к другой, нам ничего не
нужно менять в процедурах {\tt add-rat}, {\tt sub-rat} и
прочих.
То, что мы ограничиваем зависимость от представления
несколькими интерфейсными процедурами, помогает нам и проектировать
программы, и изменять их, поскольку таким образом мы сохраняем
гибкость и получаем возможность рассматривать другие реализации.
Продолжая наш простой пример, представим себе, что мы строим пакет
работы с рациональными числами и не можем сразу решить, вычислять ли
НОД при построении числа или при обращении к нему. Методология
абстракции данных позволяет нам отложить это решение, не теряя
возможности продолжать разработку остальных частей системы.
\begin{exercise}{2.2}\label{EX2.2}%
\index{ru}{отрезок|представление в виде пары точек|line segment|||(упр.~2.2)}%
\index{en}{line segment||отрезок|представление в виде пары точек||(упр.~2.2)}%
Рассмотрим задачу представления отрезков прямой на
плоскости. Каждый отрезок представляется как пара точек: начало и
конец. Определите конструктор {\tt make-seg\-ment}\index{ru}{make-segment||||p|(упр.~2.2)}
и селекторы {\tt start-segment}\index{ru}{start-segment||||p|(упр.~2.2)}
и {\tt end-segment},\index{ru}{end-segment||||p|(упр.~2.2)}
которые
определяют представление отрезков в терминах точек.\index{ru}{точка, представленная в виде пары чисел||point, represented as a pair|||(упр.~2.2)}\index{en}{point, represented as a pair||точка, представленная в виде пары чисел|||(упр.~2.2)}
Далее, точку можно представить как пару чисел: координата $x$ и
координата $y$. Соответственно, напишите конструктор
{\tt make-point}\index{ru}{make-point||||p|(упр.~2.2)}
и селекторы {\tt x-point} и
{\tt y-point}, которые определяют такое представление.
Наконец, используя свои селекторы и конструктор, напишите процедуру
{\tt midpoint-segment}, которая принимает отрезок в качестве
аргумента и возвращает его середину (точку, координаты которой
являются средним координат концов отрезка). Чтобы опробовать эти
процедуры, Вам потребуется способ печатать координаты точек:
\begin{Verbatim}[fontsize=\small]
(define (print-point p) \index{ru}{print-point||||pd|(упр.~2.2)}
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
\end{Verbatim}
\end{exercise}
\begin{exercise}{2.3}\label{EX2.3}%
\index{ru}{прямоугольники, их представление||representing rectangles|||(упр.~2.3)}%
\index{en}{representing rectangles||прямоугольники, их представление|||(упр.~2.3)}%
Реализуйте представление прямоугольников на
плоскости. (Подсказка: Вам могут потребоваться результаты
упражнения~\ref{EX2.2}.) Определите в терминах своих конструкторов и
селекторов процедуры, которые вычисляют периметр и площадь
прямоугольника. Теперь реализуйте другое представление для
прямоугольников. Можете ли Вы спроектировать свою систему с
подходящими барьерами абстракции так, чтобы одни и те же процедуры
вычисления периметра и площади работали с любым из Ваших представлений?
\end{exercise}
\subsection{Что значит слово <<данные>>?}
\label{WHAT-IS-MEANT-BY-DATA}
\index{ru}{данные|значение||||}%
Свою реализацию рациональных чисел в разделе~\ref{EXMP-ARITH-OPER-FOR-RAT-NUMBERS}
мы начали с определения операций над рациональными числами {\tt add-rat},
{\tt sub-rat} и так далее в терминах трех неопределенных
процедур: {\tt make-rat}, {\tt numer} и
{\tt denom}. В этот момент мы могли думать об операциях как
определяемых через объекты данных~--- числители, знаменатели и
рациональные числа,~--- поведение которых определялось тремя
последними про\-цедурами.
\looseness=1
Но что в точности означает слово \index{ru}{данные||data|||}\index{en}{data||данные|||}{\em данные} (data)? Здесь недостаточно просто сказать
<<то, что реализуется некоторым набором селекторов и конструкторов>>.
Ясно, что не любой набор из трех процедур может служить основой для
реализации рациональных чисел. Нам нужно быть уверенными в том, что
если мы конструируем рациональное число {\tt x} из пары целых
{\tt n} и {\tt d}, то получение {\tt numer} и
{\tt denom} от {\tt x} и деление их друг на друга должно
давать тот же результат, что и деление {\tt n} на
{\tt d}. Другими словами, {\tt make-rat},
{\tt numer} и {\tt denom} должны удовлетворять следующему условию:
для каждого целого числа {\tt n} и не равного нулю целого
{\tt d}, если {\tt x} есть {\tt (make-rat n d)},
то
$$
\frac{\texttt{(numer x)}}{\texttt{(denom x)}}
= \frac{\texttt{n}}{\texttt{d}}
$$
\index{ru}{make-rat|описывающая аксиома|||pd|}%
\index{ru}{numer|описывающая аксиома|||pd|}%
\index{ru}{denom|описывающая аксиома|||pd|}%
Это на самом деле единственное условие, которому должны удовлетворять
{\tt make-rat}, {\tt numer} и {\tt denom}, чтобы
служить основой для представления рациональных чисел. В общем случае
можно считать, что данные~--- это то, что определяется некоторым набором
селекторов и конструкторов, а также некоторыми условиями, которым эти
процедуры должны удовлетворять, чтобы быть правильным представлением\footnote{Как ни странно, эту мысль очень трудно строго
сформулировать. Существует два подхода к такой формулировке. Один,
начало которому положил Ч. А. Р. Хоар (Hoare 1972),
\index{ru}{Хоар, Чарльз Энтони Ричард||Charles Anthony Richard Hoare||n|п}\index{en}{Charles Anthony Richard Hoare||Хоар, Чарльз Энтони Ричард||n|п}
известен как метод \index{ru}{данные|абстрактные модели||||п}
\index{ru}{абстрактные модели данных||abstract models for data|||п}\index{en}{abstract models for data||абстрактные модели данных|||п}{\em абстрактных моделей} (abstract models). Он
формализует спецификацию вида <<процедуры плюс условия>> вроде
описанной выше в примере с рациональными числами. Заметим, что
условие на представление рациональных чисел было сформулировано в
терминах утверждений о целых числах (равенство и деление). В общем
случае абстрактные модели определяют новые типы объектов данных в
терминах типов данных, определенных ранее. Следовательно, утверждения
об объектах данных могут быть проверены путем сведения их к
утверждениям об объектах данных, которые были определены ранее.
Другой подход, который был введен Зиллесом из MIT, Гогеном,\index{ru}{Гоген, Джозеф||Joseph Goguen||n|п}\index{en}{Joseph Goguen||Гоген, Джозеф||n|п}
Тэтчером,\index{ru}{Тэтчер, Джеймс~У.||James~W. Thatcher||n|п}\index{en}{James~W. Thatcher||Тэтчер, Джеймс~У.||n|п}
Вагнером \index{ru}{Вагнер, Эрик~Дж.||Eric~G. Wagner||n|п}\index{en}{Eric~G. Wagner||Вагнер, Эрик~Дж.||n|п}
и Райтом из IBM (см. Thatcher, Wagner, and Wright 1978)\index{ru}{Райт, Джесси~Б.||Jesse~B. Wright||n|п}\index{en}{Jesse~B. Wright||Райт, Джесси~Б.||n|п}
и Гаттэгом из
университета Торонто (см. Guttag 1977), называется
\index{ru}{Гаттэг, Джон Фогель||John Vogel Guttag||n|п}\index{en}{John Vogel Guttag||Гаттэг, Джон Фогель||n|п}\index{ru}{алгебраическая спецификация||algebraic specification|||п}\index{en}{algebraic specification||алгебраическая спецификация|||п}\index{ru}{данные|алгебраическая спецификация||||п}{\em алгебраическая
спецификация} (algebraic specification). Этот подход рассматривает <<процедуры>> как
элементы абстрактной алгебраической системы, чье поведение
определяется аксиомами, соответствующими нашим <<условиям>>, и
использует методы абстрактной алгебры для проверки утверждений об
объектах данных. Оба этих метода описаны в статье Лисков и Зиллеса
(Liskov and Zilles~1975).\index{ru}{Лисков, Барбара Хьюберман||Barbara Huberman Liskov||n|п}\index{en}{Barbara Huberman Liskov||Лисков, Барбара Хьюберман||n|п}\index{ru}{Зиллес, Стивен~Н.||Stephen~N. Zilles||n|п}\index{en}{Stephen~N. Zilles||Зиллес, Стивен~Н.||n|п}
}.
\index{ru}{данные|процедурное представление||||}%
\index{ru}{процедурное представление данных||procedural representation of data|||}\index{en}{procedural representation of data||процедурное представление данных|||}%
Эта точка зрения может послужить для определения не только
<<высокоуровневых>> объектов данных, таких как рациональные числа, но
и объектов низкого уровня. \index{ru}{пара (пары)|процедурное представление||||}Рассмотрим понятие пары, с помощью которого
мы определили наши рациональные числа. Мы ведь ни разу
не сказали, что такое пара, и указывали только, что для работы с парами
язык дает нам процедуры {\tt cons}, {\tt car} и
{\tt cdr}. Но единственное, что нам надо
знать об этих процедурах~--- это что если мы \index{ru}{пара (пары)|аксиоматическое определение||||} склеиваем два объекта
при помощи {\tt cons}, то с помощью {\tt car} и
{\tt cdr} мы можем получить их обратно. То есть эти операции
удовлетворяют условию, что для любых объектов {\tt x} и
{\tt y}, если {\tt z} есть {\tt (cons x y)}, то
{\tt (car z)} есть {\tt x},
\index{ru}{cons (элементарная процедура)|описывающие аксиомы|||p|}%
\index{ru}{car (элементарная процедура)|описывающая аксиома|||p|}%
а {\tt (cdr z)} есть
\index{ru}{cdr (элементарная процедура)|описывающая аксиома|||p|}%
{\tt y}. Действительно, мы упомянули, что три эти процедуры
включены в наш язык как примитивы. Однако любая тройка процедур,
которая удовлетворяет вышеуказанному условию, может использоваться как
основа реализации пар. Эта идея ярко иллюстрируется тем, что мы могли
бы реализовать {\tt cons}, {\tt car} и
{\tt cdr} без использования каких-либо структур данных, а
только при помощи одних процедур. Вот эти определения:
%\pagebreak
\begin{Verbatim}[fontsize=\small]
(define (cons x y)\index{ru}{cons (элементарная процедура)|процедурная реализация|||pd|}
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Аргумент не 0 или 1 -- CONS" m))))
dispatch)
(define (car z) (z 0))\index{ru}{car (элементарная процедура)|процедурная реализация|||pd|}
(define (cdr z) (z 1))\index{ru}{cdr (элементарная процедура)|процедурная реализация|||pd|}
\end{Verbatim}
Такое использование процедур совершенно не соответствует нашему
интуитивному понятию о том, как должны выглядеть данные. Однако для
того, чтобы показать, что это законный способ представления
пар, требуется только проверить, что эти процедуры удовлетворяют вышеуказанному
условию. %Юре: между этим местом и началом упр. убрать одну
%строчку -- сократить текст!
Тонкость здесь состоит в том, чтобы заметить, что значение,
возвращаемое {\tt cons}, есть процедура,~--- а именно процедура
{\tt dispatch}, определенная внутри {\tt cons}, которая
принимает один аргумент и возвращает либо {\tt x}, либо
{\tt y} в зависимости от того, равен ли ее аргумент 0 или 1.
Соответственно, {\tt (car z)} определяется как применение
{\tt z} к 0. Следовательно, если {\tt z} есть
процедура, полученная из {\tt (cons x y)}, то {\tt z},
примененная к 0, вернет {\tt x}. Таким образом, мы показали,
что {\tt (car (cons x y))} возвращает {\tt x}, как нам и
хотелось. Подобным образом {\tt (cdr (cons x y))} применяет
процедуру, возвращаемую {\tt (cons x y)}, к 1, что дает нам
{\tt y}. Следовательно, эта процедурная реализация пар
законна, и если мы обращаемся к парам только с помощью
{\tt cons}, {\tt car} и
{\tt cdr}, то мы не сможем отличить эту реализацию от такой,
которая использует <<настоящие>> структуры данных.
Демонстрировать процедурную реализацию имеет смысл не для того,
чтобы показать, как работает наш язык (Scheme,
и вообще Лисп-системы, реализуют пары напрямую из соображений
эффективности), а в том, чтобы показать, что он мог бы работать и
так. Процедурная реализация, хотя она и выглядит трюком,~--- совершенно
адекватный способ представления пар, поскольку она удовлетворяет
единственному условию, которому должны соответствовать пары. Кроме
того, этот пример показывает, что способность работать с процедурами
как с объектами автоматически дает нам возможность представлять
составные данные. Сейчас это может показаться курьезом, но в нашем
программистском репертуаре процедурные представления данных будут
играть центральную роль. Такой стиль программирования часто называют
\index{ru}{передача сообщений||message passing|||}\index{en}{message passing||передача сообщений|||}{\em передачей
сообщений} (message passing),
и в главе~\ref{MODULARITY-OBJECTS-AND-STATE},
при рассмотрении вопросов моделирования, он будет нашим основным инструментом.
\begin{exercise}{2.4}\label{EX2.4}%
Вот еще одно процедурное представление для пар.
Проверьте для этого представления, что при любых двух объектах
{\tt x} и {\tt y} {\tt (car (cons x y))}
возвращает {\tt x}.
\begin{Verbatim}[fontsize=\small]
(define (cons x y)\index{ru}{cons (элементарная процедура)|процедурная реализация|||pd|(упр.~2.4)}
(lambda (m) (m x y)))
(define (car z)\index{ru}{car (элементарная процедура)|процедурная реализация|||pd|(упр.~2.4)}
(z (lambda (p q) p)))
\end{Verbatim}
Каково соответствующее определение {\tt cdr}?
\index{ru}{cdr (элементарная процедура)|процедурная реализация|||p|(упр.~2.4)}(Подсказка: Чтобы
проверить, что это работает, используйте подстановочную модель из
раздела~\ref{SUBST-MODEL-FOR-PROC-APPL}.)
\end{exercise}
\begin{exercise}{2.5}\label{EX2.5}%
Покажите, что можно представлять пары неотрицательных
целых чисел, используя только числа и арифметические операции, если
представлять пару $a$ и $b$ как
произведение $2^a 3^b$. Дайте соответствующие определения
процедур {\tt cons}, {\tt car} и
{\tt cdr}.
\end{exercise}
\begin{exercise}{2.6}\label{EX2.6}%
Если представление пар как процедур было для Вас
еще недостаточно сумасшедшим, то заметьте, что в языке, который
способен манипулировать
процедурами, мы можем обойтись и без чисел (по крайней мере, пока речь
идет о неотрицательных числах), определив 0 и операцию прибавления 1
так:
\begin{Verbatim}[fontsize=\small]
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
\end{Verbatim}
Такое представление известно как \index{ru}{Чёрча числа||Church numerals|||(упр.~2.6)}\index{en}{Church numerals||Чёрча числа|||(упр.~2.6)}{\em числа
Чёрча} (Church numerals), по имени его изобретателя, Алонсо
Чёрча,\index{ru}{Чёрч, Алонсо||Alonzo
Church||n|(упр.~2.6)}\index{en}{Alonzo Church||Чёрч,
Алонсо||n|(упр.~2.6)}
того самого логика, который придумал
$\lambda$-исчисление.
Определите {\tt one} (единицу) и {\tt two}
(двойку) напрямую (не через {\tt zero} и
{\tt add-1}). (Подсказка: вычислите {\tt (add-1 zero)} с
помощью подстановки.) Дайте прямое определение процедуры сложения
{\tt +} (не в терминах повторяющегося применения {\tt add-1}).
\end{exercise}
\subsection{Расширенный пример: интервальная арифметика}
\label{EXTENDED-EXERCISE-INTERVAL-ARITHMETIC}
\index{ru}{арифметика|интервальная||||}%
Лиза П. Хакер проектирует систему, которая помогала бы в
решении технических задач. Одна из возможностей, которые она хочет
реализовать в своей системе,~--- способность работать с неточными
величинами (например, измеренные параметры физических устройств),
обладающими известной погрешностью, так что когда с такими
приблизительными величинами производятся вычисления, результаты также
представляют собой числа с известной погрешностью.
Инженеры-электрики будут с помощью Лизиной системы
вычислять электрические величины. Иногда им требуется вычислить
сопротивление $R_p$ параллельного соединения двух
резисторов $R_1$ и $R_2$ по формуле\index{ru}{сопротивление|формула для параллельных резисторов||||}
$$
R_p = \frac{1}{1 / R_1 + 1 / R_2}
$$
Обычно сопротивления резисторов известны только с некоторой точностью,
которую гарантирует их производитель.
\index{ru}{сопротивление|погрешность|resistance|||}\index{en}{resistance||сопротивление|погрешность||}Например,
покупая резистор с надписью <<6.8 Ом с погрешностью 10\%>>, Вы знаете только
то, что сопротивление резистора находится между $6.8 - 0.68 =
6.12$ и $6.8 + 0.68 = 7.48$ Ом. Так что если
резистор в 6.8 Ом с погрешностью 10\% подключен параллельно
резистору в 4.7 Ом с погрешностью 5\%, то сопротивление этой
комбинации может быть примерно от 2.58 Ом (если оба резистора
находятся на нижней границе интервала допустимых значений) до 2.97 Ом
(если оба резистора находятся на верхней границе).
Идея Лизы состоит в том, чтобы реализовать
<<интервальную арифметику>> как набор арифметических операций над
<<интервалами>> (объектами, которые представляют диапазоны возможных
значений неточной величины). Результатом сложения, вычитания,
умножения или деления двух интервалов также будет интервал, который
представляет диапазон возможных значений результата.
Лиза постулирует существование абстрактного объекта,
называемого <<интервал>>, у которого есть два конца: верхняя и нижняя
границы. Кроме того, она предполагает, что имея два конца интервала,
мы можем сконструировать его при помощи конструктора
{\tt make-interval}.\index{ru}{make-interval||||p|}
Сначала Лиза пишет процедуру сложения двух
интервалов. Она рассуждает так: минимальное возможное значение суммы
равно сумме нижних границ интервалов, а максимальное возможное
значение сумме верхних границ интервалов.
\begin{Verbatim}[fontsize=\small]
(define (add-interval x y)\index{ru}{add-interval||||pd|}
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
\end{Verbatim}
Кроме того, она вычисляет произведение двух интервалов путем
нахождения минимума и максимума произведений концов интервалов и
использования в качестве границ
интервала-результата. ({\tt min}\index{ru}{min (элементарная
процедура)||||pd|}\index{ru}{элементарные процедуры|{\tt min}||||}
и {\tt max} ---\index{ru}{max (элементарная
процедура)||||pd|}\index{ru}{элементарные процедуры|{\tt max}||||}
примитивы, которые находят минимум и максимум при любом количестве
аргументов.)
\begin{Verbatim}[fontsize=\small]
(define (mul-interval x y)\index{ru}{mul-interval||||pd|}
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
\end{Verbatim}
При делении двух интервалов Лиза умножает первый из них на интервал,
обратный второму. Заметим, что границами обратного интервала являются
числа, обратные верхней и нижней границе исходного интервала, именно в
таком порядке.
\begin{Verbatim}[fontsize=\small]
(define (div-interval x y)\index{ru}{div-interval||||pd|}
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
\end{Verbatim}
\begin{exercise}{2.7}\label{EX2.7}%
Программа Лизы неполна, поскольку она не определила,