-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbook-Z-H-14.html
More file actions
264 lines (184 loc) · 43.3 KB
/
book-Z-H-14.html
File metadata and controls
264 lines (184 loc) · 43.3 KB
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
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:ops="http://www.idpf.org/2007/ops">
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta http-equiv="Content-Type: text/html; charset=utf-8"/>
<title>Estrutura e Interpretação de Programas de Computador</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title="default"/>
</head>
<body>
<a name="%_sec_2.1" id="%_sec_2.1"/>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_2.1">2.1 Introdução à abstração de dados</a></h2><p>Na seção <a href="book-Z-H-10.html#%_sec_1.1.8">1.1.8</a>, observamos que um procedimento usado como elemento na criação de um procedimento mais complexo pode ser considerado não apenas como uma coleção de operações específicas, mas também como uma abstração processual. Ou seja, os detalhes de como o procedimento foi implementado podem ser suprimidos e o próprio procedimento específico pode ser substituído por qualquer outro procedimento com o mesmo comportamento geral. Em outras palavras, poderíamos fazer uma abstração que separasse a maneira como o procedimento seria usado dos detalhes de como o procedimento seria implementado em termos de procedimentos mais primitivos. A noção análoga para dados compostos é chamada <a name="%_idx_1280" id="%_idx_1280"/><em>abstração de dados</em>. A abstração de dados é uma metodologia que nos permite isolar como um objeto de dados composto é usado a partir dos detalhes de como é construído a partir de objetos de dados mais primitivos.</p><p>A ideia básica da abstração de dados é estruturar os programas que devem usar objetos de dados compostos para que operem com <a name="%_idx_1282" id="%_idx_1282"/><a name="%_idx_1284" id="%_idx_1284"/>“dados abstratos”. Ou seja, nossos programas devem usar dados de forma a não fazer suposições sobre os dados que não são estritamente necessários para a execução da tarefa em questão. Ao mesmo tempo, uma representação de dados <a name="%_idx_1286" id="%_idx_1286"/><a name="%_idx_1288" id="%_idx_1288"/>“concreta” é definida independentemente dos programas que usam os dados. A interface entre essas duas partes do nosso sistema será um conjunto de procedimentos, chamados <a name="%_idx_1290" id="%_idx_1290"/><em>seletores</em> e <a name="%_idx_1292" id="%_idx_1292"/><em>construtores</em>, que implementam os dados abstratos em termos da representação concreta. Para ilustrar essa técnica, consideraremos como projetar um conjunto de procedimentos para manipular números racionais.</p><p>
<a name="%_sec_2.1.1" id="%_sec_2.1.1"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_2.1.1">2.1.1 Exemplo: operações aritméticas para números racionais</a></h3><p>
</p><p>
<a name="%_idx_1294" id="%_idx_1294"/><a name="%_idx_1296" id="%_idx_1296"/><a name="%_idx_1298" id="%_idx_1298"/>Suponha que queremos fazer aritmética com números racionais. Queremos poder adicionar, subtrair, multiplicar e dividi-los e testar se dois números racionais são iguais.</p><p>Começaremos assumindo que já temos uma maneira de construir um número racional a partir de um numerador e um denominador. Também assumimos que, dado um número racional, temos uma maneira de extrair (ou selecionar) seu numerador e denominador. Assumiremos ainda que o construtor e os seletores estão disponíveis como procedimentos:</p><p>
</p><p/><ul><a name="%_idx_1300" id="%_idx_1300"/><li><tt>(make-rat <<em>n</em>> <<em>d</em>>)</tt> retorna o número racional cujo numerador é o número inteiro <tt><<em>n</em>></tt> e cujo denominador é o número inteiro <tt><<em>d</em>></tt>.<p>
<a name="%_idx_1302" id="%_idx_1302"/></p></li><li><tt>(numer <<em>x</em>>)</tt> retorna o numerador do número racional <tt><<em>x</em>></tt>.<p>
<a name="%_idx_1304" id="%_idx_1304"/></p></li><li><tt>(denom <<em>x</em>>)</tt> retorna o denominador do número racional <tt><<em>x</em>></tt>.</li></ul><p/><p>usamos aqui uma poderosa estratégia de síntese: <a name="%_idx_1306" id="%_idx_1306"/><em>pensamento positivo</em>. Ainda não dissemos como um número racional é representado ou como os procedimentos <tt>numer</tt>, <tt>denom</tt> e <tt>make-rat</tt> devem ser implementados. Mesmo assim, se tivéssemos esses três procedimentos, poderíamos adicionar, subtrair, multiplicar, dividir e testar a igualdade usando as seguintes relações:</p><p>
</p><p/><div align="left"><img src="images/ch2-Z-G-1.gif" border="0"/></div><p/><p>
</p><p/><div align="left"><img src="images/ch2-Z-G-2.gif" border="0"/></div><p/><p>
</p><p/><div align="left"><img src="images/ch2-Z-G-3.gif" border="0"/></div><p/><p>
</p><p/><div align="left"><img src="images/ch2-Z-G-4.gif" border="0"/></div><p/><p>
</p><p/><div align="left"><img src="images/ch2-Z-G-5.gif" border="0"/></div><p/><p>Podemos expressar essas regras como procedimentos:</p><p>
</p><p/><p><tt><a name="%_idx_1308" id="%_idx_1308"/>(define (add-rat x y)<br/>
(make-rat (+ (* (numer x) (denom y))<br/>
(* (numer y) (denom x)))<br/>
(* (denom x) (denom y))))<br/><a name="%_idx_1310" id="%_idx_1310"/>(define (sub-rat x y)<br/>
(make-rat (- (* (numer x) (denom y))<br/>
(* (numer y) (denom x)))<br/>
(* (denom x) (denom y))))<br/><a name="%_idx_1312" id="%_idx_1312"/>(define (mul-rat x y)<br/>
(make-rat (* (numer x) (numer y))<br/>
(* (denom x) (denom y))))<br/><a name="%_idx_1314" id="%_idx_1314"/>(define (div-rat x y)<br/>
(make-rat (* (numer x) (denom y))<br/>
(* (denom x) (numer y))))<br/><a name="%_idx_1316" id="%_idx_1316"/>(define (equal-rat? x y)<br/>
(= (* (numer x) (denom y))<br/>
(* (numer y) (denom x))))<br/></tt></p><p/><p/><p>Agora, temos as operações sobre números racionais definidas em termos dos procedimentos seletor e construtor <tt>numer</tt>, <tt>denom</tt> e <tt>make-rat</tt>. Mas ainda não os definimos. O que precisamos é de uma maneira de colar um numerador e um denominador para formar um número racional.</p><p>
<a name="%_sec_Temp_132" id="%_sec_Temp_132"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_132">Pares</a></h4><p>Para nos permitir implementar o nível concreto de nossa abstração de dados, nossa linguagem fornece uma estrutura composta chamada <a name="%_idx_1318" id="%_idx_1318"/><em>pair</em>, que pode ser construída com o procedimento primitivo <a name="%_idx_1320" id="%_idx_1320"/><a name="%_idx_1322" id="%_idx_1322"/><tt>cons</tt>. Este procedimento utiliza dois argumentos e retorna um objeto de dados composto que contém os dois argumentos como partes. Dado um par, podemos extrair as peças usando os procedimentos primitivos <a name="%_idx_1324" id="%_idx_1324"/><a name="%_idx_1326" id="%_idx_1326"/><tt>car</tt> e<a name="%_idx_1328" id="%_idx_1328"/><a name="%_idx_1330" id="%_idx_1330"/><tt>cdr</tt>.<a name="call_footnote_Temp_133" href="#footnote_Temp_133" id="call_footnote_Temp_133"><sup><small>2</small></sup></a> Assim, podemos usar <tt>cons</tt>, <tt>car</tt>, e <tt>cdr</tt> da seguinte forma:</p><p>
</p><p/><p><tt>(define x (cons 1 2))<br/><br/>
(car x)<br/><i>1</i><br/><br/>
(cdr x)<br/><i>2</i><br/></tt></p><p/><p>Observe que um par é um objeto de dados que pode receber um nome e ser manipulado, assim como um objeto de dados primitivo. Além disso, <tt>cons</tt> podem ser usados para formar pares cujos elementos são pares, e assim por diante:</p><p>
</p><p/><p><tt>(define x (cons 1 2))<br/><br/>
(define y (cons 3 4))<br/><br/>
(define z (cons x y))<br/><br/>
(car (car z))<br/><i>1</i><br/><br/>
(car (cdr z))<br/><i>3</i><br/></tt></p><p/><p>Na seção <a href="book-Z-H-15.html#%_sec_2.2">2.2</a>, veremos como essa capacidade de combinar pares significa que os pares podem ser usados como blocos de construção de uso geral para criar todos os tipos de estruturas de dados complexas. O único <em>par</em> primitivo de dados compostos, implementado pelos procedimentos <tt>cons</tt>, <tt>car</tt>, e <tt>cdr</tt>, é a única cola que precisamos. Os objetos de dados construídos a partir de pares são chamados de <a name="%_idx_1342" id="%_idx_1342"/><a name="%_idx_1344" id="%_idx_1344"/><em>dados estruturados em lista</em>.</p><p>
<a name="%_sec_Temp_134" id="%_sec_Temp_134"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_134">Representando números racionais</a></h4><p>
<a name="%_idx_1346" id="%_idx_1346"/>Os pares oferecem uma maneira natural de completar o sistema de números racionais. Simplesmente represente um número racional como um par de dois números inteiros: um numerador e um denominador. Em seguida, <tt>make-rat</tt>, <tt>numer</tt>, e <tt>denom</tt> são prontamente implementados da seguinte forma:<a name="call_footnote_Temp_135" href="#footnote_Temp_135" id="call_footnote_Temp_135"><sup><small>3</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_1348" id="%_idx_1348"/>(define (make-rat n d) (cons n d))<br/><br/><a name="%_idx_1350" id="%_idx_1350"/>(define (numer x) (car x))<br/><br/><a name="%_idx_1352" id="%_idx_1352"/>(define (denom x) (cdr x))<br/></tt></p><p/><p>Além disso, para exibir os resultados de nossos cálculos, podemos <a name="%_idx_1354" id="%_idx_1354"/>imprimir números racionais imprimindo o numerador, uma barra e o denominador:<a name="call_footnote_Temp_136" href="#footnote_Temp_136" id="call_footnote_Temp_136"><sup><small>4</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_1370" id="%_idx_1370"/>(define (print-rat x)<br/>
(newline)<br/>
(display (numer x))<br/>
(display "/")<br/>
(display (denom x)))<br/></tt></p><p/><p>Agora podemos tentar nossos procedimentos de número racional:</p><p>
</p><p/><p><tt>(define one-half (make-rat 1 2))<br/><br/>
(print-rat one-half)<br/><i>1/2</i><br/><br/>
(define one-third (make-rat 1 3))<br/>
(print-rat (add-rat one-half one-third))<br/><i>5/6</i><br/><br/>
(print-rat (mul-rat one-half one-third))<br/><i>1/6</i><br/><br/>
(print-rat (add-rat one-third one-third))<br/><i>6/9</i><br/></tt></p><p/><p/><p>
<a name="%_idx_1372" id="%_idx_1372"/><a name="%_idx_1374" id="%_idx_1374"/>Como mostra o exemplo final, nossa implementação de número racional não reduz números racionais aos termos mais baixos. Podemos remediar isso alterando <tt>make-rat</tt>. Se tivermos um procedimento <a name="%_idx_1376" id="%_idx_1376"/><tt>gcd</tt> como o da seção <a href="book-Z-H-11.html#%_sec_1.2.5">1.2.5</a> que produz o maior divisor comum de dois números inteiros, podemos usar <tt>gcd</tt> para reduzir o numerador e o denominador para os termos mais baixos antes de construir o par:</p><p>
</p><p/><p><tt><a name="%_idx_1378" id="%_idx_1378"/>(define (make-rat n d)<br/>
(let ((g (gcd n d)))<br/>
(cons (/ n g) (/ d g))))<br/></tt></p><p/><p>Agora temos</p><p>
</p><p/><p><tt>(print-rat (add-rat one-third one-third))<br/><i>2/3</i><br/></tt></p><p/><p>como desejado. Essa modificação foi realizada alterando o construtor <tt>make-rat</tt> sem alterar nenhum dos procedimentos (como <tt>add-rat</tt> e <tt>mul-rat</tt>) implementar as operações reais.</p><p>
</p><p><a name="%_thm_2.1" id="%_thm_2.1"/>
<b>Exercício 2.1.</b> Defina uma versão melhor de <tt>make-rat</tt> que lide com argumentos positivos e negativos. <tt>Make-rat</tt> deve normalizar o sinal para que, se o número racional for positivo, o numerador e o denominador sejam positivos, e se o número racional for negativo, apenas o numerador será negativo.</p><p>
<a name="%_sec_2.1.2" id="%_sec_2.1.2"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_2.1.2">2.1.2 Barreiras de abstração</a></h3><p>
</p><p>
<a name="%_idx_1380" id="%_idx_1380"/>Antes de continuar com mais exemplos de dados compostos e abstração de dados, consideraremos algumas das questões levantadas pelo exemplo de número racional. Definimos as operações de número racional em termos de um construtor <tt>make-rat</tt> e seletores <tt>numer</tt> e <tt>denom</tt>. Em geral, a ideia subjacente da abstração de dados é identificar para cada tipo de objeto de dados um conjunto básico de operações em termos dos quais todas as manipulações de objetos de dados desse tipo serão expressas e, em seguida, usar apenas essas operações na manipulação dos dados.</p><p>Podemos imaginar a estrutura do sistema de números racionais, como mostra a figura <a href="#%_fig_2.1">2.1</a>. As linhas horizontais representam <em>barreiras de abstração</em> que isolam diferentes “níveis” do sistema. Em cada nível, a barreira separa os programas (acima) que usam a abstração de dados dos programas (abaixo) que implementam a abstração de dados. Os programas que usam números racionais os manipulam apenas em termos dos procedimentos fornecidos “para uso público” pelo pacote de números racionais: <tt>add-rat</tt>, <tt>sub-rat</tt>, <tt>mul-rat</tt>, <tt>div-rat</tt> e <tt>equal-rat?</tt>. Estes, por sua vez, são implementados apenas em termos do construtor e dos seletores <a name="%_idx_1382" id="%_idx_1382"/><a name="%_idx_1384" id="%_idx_1384"/><tt>make-rat</tt>, <tt>numer</tt> e <tt>denom</tt>, que são implementados em termos de pares. Os detalhes de como os pares são implementados são irrelevantes para o restante do pacote de números racionais, desde que os pares possam ser manipulados pelo uso de <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt>. De fato, os procedimentos em cada nível são as interfaces que definem as barreiras de abstração e conectam os diferentes níveis.</p><p>
<a name="%_fig_2.1" id="%_fig_2.1"/></p><p/><div align="left"><table width="100%"><tr><td><div align="left"><img src="images/ch2-Z-G-6.gif" border="0"/> </div>
</td></tr><caption align="bottom"><div align="left"><b>Figura 2.1:</b> Barreiras de abstração de dados no pacote de número racional.</div></caption><tr><td>
</td></tr></table></div><p/><p>Essa ideia simples tem muitas vantagens. Uma vantagem é que torna os programas muito mais fáceis de manter e modificar. Qualquer estrutura de dados complexa pode ser representada de várias maneiras com as estruturas de dados primitivas fornecidas por uma linguagem de programação. Obviamente, a escolha da representação influencia os programas que nela operam; portanto, se a representação precisar ser alterada posteriormente, todos esses programas deverão ser modificados de acordo. Essa tarefa pode ser demorada e cara no caso de programas grandes, a menos que a dependência da representação deva ser confinada pelo projeto a muito poucos módulos de programa.</p><p>
<a name="%_idx_1386" id="%_idx_1386"/><a name="%_idx_1388" id="%_idx_1388"/>Por exemplo, uma maneira alternativa de resolver o problema de reduzir números racionais para termos mais baixos é realizá-la sempre que acessamos as partes de um número racional, e não quando o construímos. Isso leva a diferentes procedimentos de construtor e seletor:</p><p>
</p><p/><p><tt><a name="%_idx_1390" id="%_idx_1390"/>(define (make-rat n d)<br/>
(cons n d))<br/><a name="%_idx_1392" id="%_idx_1392"/>(define (numer x)<br/>
(let ((g (gcd (car x) (cdr x))))<br/>
(/ (car x) g)))<br/><a name="%_idx_1394" id="%_idx_1394"/>(define (denom x)<br/>
(let ((g (gcd (car x) (cdr x))))<br/>
(/ (cdr x) g)))<br/></tt></p><p/><p>A diferença entre esta implementação e a anterior reside em quando computamos o <tt>gcd</tt>. Se em nosso uso típico de números racionais acessamos os numeradores e denominadores dos mesmos números racionais muitas vezes, seria preferível calcular o <tt>gcd</tt> quando os números racionais são construídos. Caso contrário, é melhor esperarmos até o tempo de acesso para calcular o <tt>gcd</tt>. De qualquer forma, quando mudamos de uma representação para outra, os procedimentos <tt>add-rat</tt>, <tt>sub-rat</tt> e assim por diante não precisam ser modificados.</p><p>Restringir a dependência da representação a alguns procedimentos de interface nos ajuda a projetar programas e a modificá-los, pois nos permite manter a flexibilidade de considerar implementações alternativas. Para continuar com nosso exemplo simples, suponha que projetamos um pacote de número racional e não podemos decidir inicialmente se deve executar o <tt>gcd</tt> no tempo de construção ou no tempo de seleção. A metodologia de abstração de dados nos permite adiar essa decisão sem perder a capacidade de progredir no restante do sistema.</p><p>
</p><p><a name="%_thm_2.2" id="%_thm_2.2"/>
<b>Exercício 2.2.</b> Considere o problema de representar <a name="%_idx_1396" id="%_idx_1396"/>segmentos de linha em um plano. Cada segmento é representado como um par de pontos: um ponto inicial e um ponto final. Defina um construtor <a name="%_idx_1398" id="%_idx_1398"/><tt>make-segment</tt> e seletores <a name="%_idx_1400" id="%_idx_1400"/><tt>start-segment</tt> e <a name="%_idx_1402" id="%_idx_1402"/><tt>end-segment</tt> que definem a representação de segmentos em termos de pontos. Além disso, um ponto <a name="%_idx_1404" id="%_idx_1404"/>pode ser representado como um par de números: a coordenada <em>x</em> e a coordenada <em>y</em>. Assim, especifique um construtor <a name="%_idx_1406" id="%_idx_1406"/><tt>make-point</tt> e seletores <tt>x-point</tt> e <tt>y-point</tt> que definam essa representação. Por fim, usando seus seletores e construtores, defina um procedimento <a name="%_idx_1408" id="%_idx_1408"/><tt>midpoint-segment</tt> que use um segmento de linha como argumento e retorne seu ponto médio (o ponto cujas coordenadas são a média das coordenadas dos pontos finais) Para testar seus procedimentos, você precisará de uma maneira de imprimir pontos:</p><p>
</p><p/><p><tt><a name="%_idx_1410" id="%_idx_1410"/>(define (print-point p)<br/>
(newline)<br/>
(display "(")<br/>
(display (x-point p))<br/>
(display ",")<br/>
(display (y-point p))<br/>
(display ")"))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_2.3" id="%_thm_2.3"/>
<b>Exercício 2.3.</b> <a name="%_idx_1412" id="%_idx_1412"/>Implemente uma representação para retângulos em um plano. (Dica: você pode usar o exercício <a href="#%_thm_2.2">2.2</a>). Em termos de construtores e seletores, crie procedimentos que calculem o perímetro e a área de um determinado retângulo. Agora implemente uma representação diferente para retângulos. Você pode projetar seu sistema com barreiras de abstração adequadas, para que os mesmos procedimentos de perímetro e área funcionem usando qualquer uma das representações?</p><p>
</p><p>
<a name="%_sec_2.1.3" id="%_sec_2.1.3"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_2.1.3">2.1.3 O que se entende por dados?</a></h3><p>
<a name="%_idx_1414" id="%_idx_1414"/>Iniciamos a implementação do número racional na seção <a href="#%_sec_2.1.1">2.1.1</a> implementando as operações de número racional <tt>add-rat</tt>, <tt>sub-rat</tt> e assim por diante em termos de três procedimentos não especificados: <tt>make-rat</tt>, <tt>numer</tt> e <tt>denom</tt>. Nesse ponto, poderíamos pensar nas operações como sendo definidas em termos de objetos de dados – numeradores, denominadores e números racionais – cujo comportamento foi especificado pelos três últimos procedimentos.</p><p>Mas exatamente o que se entende por <em>dados</em>? Não basta dizer “o que quer que seja implementado pelos determinados seletores e construtores”. Claramente, nem todo conjunto arbitrário de três procedimentos pode servir como base apropriada para a implementação do número racional. Precisamos garantir que, <a name="%_idx_1416" id="%_idx_1416"/><a name="%_idx_1418" id="%_idx_1418"/><a name="%_idx_1420" id="%_idx_1420"/>se construirmos um número racional <tt>x</tt> a partir de um par de números inteiros <tt>n</tt> e <tt>d</tt>, extrair o <tt>numer</tt> e o <tt>denom</tt> de <tt>x</tt> e dividi-los deve gerar o mesmo resultado que a divisão <tt>n</tt> por <tt>d</tt>. Em outras palavras, <tt>make-rat</tt>, <tt>numer</tt> e <tt>denom</tt> devem atender à condição de que, para qualquer número inteiro <tt>n</tt> e qualquer número inteiro diferente de zero <tt>d</tt>, se <tt>x</tt> for (<tt>make-rat n d</tt>), então</p><p>
</p><p/><div align="left"><img src="images/ch2-Z-G-7.gif" border="0"/></div><p/><p>De fato, esta é a única condição que <tt>make-rat</tt>, <tt>numer</tt> e <tt>denom</tt> devem ser preenchidos para formar uma base adequada para uma representação racional numérica. Em geral, podemos pensar nos dados como definidos por alguma coleção de seletores e construtores, com condições especificadas que esses procedimentos devem cumprir para serem uma representação válida.<a name="call_footnote_Temp_140" href="#footnote_Temp_140" id="call_footnote_Temp_140"><sup><small>5</small></sup></a></p><p>
<a name="%_idx_1446" id="%_idx_1446"/><a name="%_idx_1448" id="%_idx_1448"/>Esse ponto de vista pode servir para definir não apenas objetos de dados de “alto nível”, como números racionais, mas também objetos de nível mais baixo. <a name="%_idx_1450" id="%_idx_1450"/> Considere a noção de um par, que usamos para definir nossos números racionais. Na verdade, nunca dissemos o que era um par, apenas que a linguagem fornecia os procedimentos <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt> para operar em pares. Mas a única que somente precisamos saber sobre essas três operações <a name="%_idx_1452" id="%_idx_1452"/><a name="%_idx_1454" id="%_idx_1454"/><a name="%_idx_1456" id="%_idx_1456"/><a name="%_idx_1458" id="%_idx_1458"/>é que, se colarmos dois objetos usando <tt>cons</tt>, podemos recuperar os objetos usando <tt>car</tt> e <tt>cdr</tt>. Ou seja, as operações satisfazem a condição de que, para qualquer objeto <tt>x</tt> e <tt>y</tt>, se <tt>z</tt> for <tt>(cons x y)</tt> então <tt>(car z)</tt> é <tt>x</tt> e <tt>(cdr z)</tt> é <tt>y</tt>. De fato, mencionamos que esses três procedimentos estão incluídos como primitivos em nossa linguagem. No entanto, qualquer tripla do procedimento que atenda à condição acima pode ser usado como base para a implementação de pares. Este ponto é ilustrado de maneira impressionante pelo fato de podermos implementar <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt> sem usar nenhuma estrutura de dados, mas usando apenas procedimentos. Aqui estão as definições:</p><p>
</p><p/><p><tt><a name="%_idx_1460" id="%_idx_1460"/>(define (cons x y)<br/>
(define (dispatch m)<br/>
(cond ((= m 0) x)<br/>
((= m 1) y)<br/>
(else (error "Argument not 0 or 1 -- CONS" m))))<br/>
dispatch)<br/><br/><a name="%_idx_1462" id="%_idx_1462"/>(define (car z) (z 0))<br/><br/><a name="%_idx_1464" id="%_idx_1464"/>(define (cdr z) (z 1))<br/></tt></p><p/><p>Esse uso de procedimentos não corresponde a nossa noção intuitiva o que os dados devem ser. No entanto, tudo o que precisamos fazer para mostrar que essa é uma maneira válida de representar pares é verificar se esses procedimentos atendem à condição fornecida acima.</p><p>O ponto sutil a ser observado é que o valor retornado por <tt>(cons x y)</tt> é um procedimento – ou seja, o procedimento definido internamente <tt>dispatch</tt>, que usa um argumento e retorna <tt>x</tt> ou <tt>y</tt> dependendo de o argumento ser 0 ou 1. Correspondentemente, <tt>(car z)</tt> está definido para aplicar <tt>z</tt> a 0. Portanto, se <tt>z</tt> é o procedimento formado por <tt>(cons x y)</tt>, então <tt>z</tt> aplicado a 0 produzirá <tt>x</tt>. Assim, mostramos que <tt>(car (cons x y))</tt> produz <tt>x</tt>, conforme desejado. Da mesma forma, <tt>(cdr (cons x y))</tt> aplica o procedimento retornado por <tt>(cons x y)</tt> para 1, que retorna <tt>y</tt>. Portanto, essa implementação procedural de pares é válida, e se acessarmos pares usando apenas <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt>, não poderemos distinguir isso da implementação de uma que use estruturas de dados “reais”.</p><p>O objetivo de exibir a representação procedural de pares não é que nossa linguagem funcione dessa maneira (sistemas Scheme e Lisp em geral, implementam pares diretamente, por razões de eficiência), mas que poderia funcionar dessa maneira. A representação processual, embora obscura, é uma maneira perfeitamente adequada de representar pares, uma vez que preenche as únicas condições que os pares precisam cumprir. Este exemplo também demonstra que a capacidade de manipular procedimentos como objetos fornece automaticamente a capacidade de representar dados compostos. Isso pode parecer uma curiosidade agora, mas representações procedurais de dados desempenharão um papel central em nosso repertório de programação. Esse estilo de programação costuma ser chamado de <a name="%_idx_1466" id="%_idx_1466"/><em>passagem de mensagem</em>, e o usaremos como uma ferramenta básica no capítulo 3 quando abordarmos os problemas de modelagem e simulação.</p><p>
</p><p><a name="%_thm_2.4" id="%_thm_2.4"/>
<b>Exercício 2.4.</b> Aqui está uma representação processual alternativa de pares. Para esta representação, verifique se <tt>(car (cons x y))</tt> produz <tt>x</tt> para qualquer objeto <tt>x</tt> e <tt>y</tt>.</p><p>
</p><p/><p><tt><a name="%_idx_1468" id="%_idx_1468"/>(define (cons x y)<br/>
(lambda (m) (m x y)))<br/><br/><a name="%_idx_1470" id="%_idx_1470"/>(define (car z)<br/>
(z (lambda (p q) p)))<br/></tt></p><p/><p>
<a name="%_idx_1472" id="%_idx_1472"/>Qual é a definição correspondente de <tt>cdr</tt>? (Dica: para verificar se isso funciona, use o modelo de substituição da seção <a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a>).</p><p/><p>
</p><p><a name="%_thm_2.5" id="%_thm_2.5"/>
<b>Exercício 2.5.</b> Mostre que podemos representar pares de números inteiros não negativos usando apenas números e operações aritméticas se representarmos o par <em>a</em> e <em>b</em> como o número inteiro esse é o produto 2<sup><em>a</em></sup> 3<sup><em>b</em></sup>. Forneça as definições correspondentes dos procedimentos <tt>cons</tt>, <tt>car</tt>, e <tt>cdr</tt>.</p><p>
</p><p><a name="%_thm_2.6" id="%_thm_2.6"/>
<b>Exercício 2.6.</b> No caso de representar pares como procedimentos não ser incompreensível o suficiente, considere que, em uma linguagem que pode manipular procedimentos, podemos sobreviver sem números (pelo menos, no que diz respeito a números inteiros não negativos)) implementando 0 e a operação de adicionar 1 como</p><p>
</p><p/><p><tt>(define zero (lambda (f) (lambda (x) x)))<br/><br/>
(define (add-1 n)<br/>
(lambda (f) (lambda (x) (f ((n f) x)))))<br/></tt></p><p/><p>Essa representação é conhecida como <a name="%_idx_1474" id="%_idx_1474"/><em>Numerais de Church</em>, após seu inventor, <a name="%_idx_1476" id="%_idx_1476"/>Alonzo Church, o lógico que inventou o cálculo λ.</p><p>Defina <tt>one</tt> e <tt>two</tt> diretamente (não em termos de <tt>zero</tt> e <tt>add-1</tt>). (Dica: use a substituição para avaliar <tt>(add-1 zero)</tt>). Dê uma definição direta do procedimento de adição <tt>+</tt> (não em termos de aplicação repetida de <tt>add-1</tt>).</p><p>
<a name="%_sec_2.1.4" id="%_sec_2.1.4"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_2.1.4">2.1.4 Exercício estendido: aritmética de intervalo</a></h3><p>
<a name="%_idx_1478" id="%_idx_1478"/><a name="%_idx_1480" id="%_idx_1480"/>Alyssa P. Hacker projeta um sistema para ajudar as pessoas a resolver problemas de engenharia. Um recurso que ela deseja fornecer em seu sistema é a capacidade de manipular quantidades inexatas (como parâmetros medidos de dispositivos físicos) com precisão conhecida, de modo que, quando os cálculos são feitos com quantidades aproximadas, os resultados serão números de precisão conhecida.</p><p>Os engenheiros elétricos usarão o sistema da Alyssa para calcular quantidades elétricas. Às vezes, é necessário calcular o valor de uma resistência equivalente paralela <em>R</em><sub><em>p</em></sub> de dois resistores <em>R</em><sub>1</sub> e <em>R</em><sub>2</sub> usando a fórmula<a name="%_idx_1482" id="%_idx_1482"/>
</p><p/><div align="left"><img src="images/ch2-Z-G-8.gif" border="0"/></div><p/><p>Os valores de resistência são geralmente conhecidos apenas até uma tolerância <a name="%_idx_1484" id="%_idx_1484"/>garantida pelo fabricante do resistor. Por exemplo, se você comprar um resistor rotulado como “6,8 ohms com 10% de tolerância”, poderá ter certeza de que o resistor possui uma resistência entre 6,8 - 0,68 = 6,12 e 6,8 + 0,68 = 7,48 ohms. Assim, se você tiver um resistor de 6,8 ohms a 10% em paralelo com um resistor de 4,7 ohms a 5%, a resistência da combinação poderá variar de cerca de 2,58 ohms (se os dois resistores estiverem nos limites inferiores) a cerca de 2,97 ohms (se os dois resistores estiverem nos limites superiores).</p><p>A ideia de Alyssa é implementar “aritmética de intervalo” como um conjunto de operações aritméticas para combinar “intervalos” (objetos que representam a faixa de valores possíveis de uma quantidade inexata). O resultado da adição, subtração, multiplicação ou divisão de dois intervalos é, ele próprio, um intervalo, representando o intervalo do resultado.</p><p>Alyssa postula a existência de um objeto abstrato chamado “intervalo” que possui dois pontos finais: um limite inferior e um superior. Ela também presume que, dados os pontos finais de um intervalo, ela pode construir o intervalo usando o construtor de dados <a name="%_idx_1486" id="%_idx_1486"/><tt>make-interval</tt>. Alyssa primeiro escreve um procedimento para adicionar dois intervalos. Ela argumenta que o valor mínimo que a soma poderia ser é a soma dos dois limites inferiores e o valor máximo que poderia ser é a soma dos dois limites superiores:</p><p>
</p><p/><p><tt><a name="%_idx_1488" id="%_idx_1488"/>(define (add-interval x y)<br/>
(make-interval (+ (lower-bound x) (lower-bound y))<br/>
(+ (upper-bound x) (upper-bound y))))<br/></tt></p><p/><p>Alyssa também elabora o produto de dois intervalos, encontrando o mínimo e o máximo dos produtos dos limites e usando-os como os limites do intervalo resultante. (<tt>Min</tt> e <tt>max</tt> são <a name="%_idx_1490" id="%_idx_1490"/><a name="%_idx_1492" id="%_idx_1492"/><a name="%_idx_1494" id="%_idx_1494"/><a name="%_idx_1496" id="%_idx_1496"/>primitivas que encontram o mínimo ou o máximo de qualquer número de argumentos).</p><p>
</p><p/><p><tt><a name="%_idx_1498" id="%_idx_1498"/>(define (mul-interval x y)<br/>
(let ((p1 (* (lower-bound x) (lower-bound y)))<br/>
(p2 (* (lower-bound x) (upper-bound y)))<br/>
(p3 (* (upper-bound x) (lower-bound y)))<br/>
(p4 (* (upper-bound x) (upper-bound y))))<br/>
(make-interval (min p1 p2 p3 p4)<br/>
(max p1 p2 p3 p4))))<br/></tt></p><p/><p>Para dividir dois intervalos, Alyssa multiplica o primeiro pelo recíproco do segundo. Observe que os limites do intervalo recíproco são o recíproco do limite superior e o recíproco do limite inferior, nessa ordem.</p><p>
</p><p/><p><tt><a name="%_idx_1500" id="%_idx_1500"/>(define (div-interval x y)<br/>
(mul-interval x <br/>
(make-interval (/ 1.0 (upper-bound y))<br/>
(/ 1.0 (lower-bound y)))))<br/></tt></p><p/><p/><p>
</p><p><a name="%_thm_2.7" id="%_thm_2.7"/>
<b>Exercício 2.7.</b> O programa de Alyssa está incompleto, pois ela não especificou a implementação da abstração de intervalo. Aqui está uma definição do construtor de intervalo:</p><p>
</p><p/><p><tt><a name="%_idx_1502" id="%_idx_1502"/>(define (make-interval a b) (cons a b))<br/></tt></p><p/><p>Defina os seletores <a name="%_idx_1504" id="%_idx_1504"/><tt>upper-bound</tt> e <a name="%_idx_1506" id="%_idx_1506"/><tt>lower-bound</tt> para concluir a implementação.</p><p/><p>
</p><p><a name="%_thm_2.8" id="%_thm_2.8"/>
<b>Exercício 2.8.</b> Usando raciocínio análogo ao de Alyssa, descreva como a diferença de dois intervalos pode ser calculada. Defina um procedimento de subtração correspondente, chamado <a name="%_idx_1508" id="%_idx_1508"/><tt>sub-interval</tt>.</p><p/><p>
</p><p><a name="%_thm_2.9" id="%_thm_2.9"/>
<b>Exercício 2.9.</b> <a name="%_idx_1510" id="%_idx_1510"/>A <em>largura</em> de um intervalo é metade da diferença entre seus limites superior e inferior. A largura é uma medida da incerteza do número especificado pelo intervalo. Para algumas operações aritméticas, a largura do resultado da combinação de dois intervalos é uma função apenas das larguras dos intervalos de argumento, enquanto para outros a largura da combinação não é uma função das larguras dos intervalos de argumento. Mostre que a largura da soma (ou diferença) de dois intervalos é uma função apenas das larguras dos intervalos que são adicionados (ou subtraídos). Dê exemplos para mostrar que isso não é verdade para multiplicação ou divisão.</p><p/><p>
</p><p><a name="%_thm_2.10" id="%_thm_2.10"/>
<b>Exercício 2.10.</b> <a name="%_idx_1512" id="%_idx_1512"/>Ben Bitdiddle, um programador especialista em sistemas, olha por cima do ombro de Alyssa e comenta que não está claro o que significa dividir por um intervalo que ultrapassa zero. Modifique o código da Alyssa para verificar esta condição e sinalizar um erro, se ocorrer.</p><p/><p>
</p><p><a name="%_thm_2.11" id="%_thm_2.11"/>
<b>Exercício 2.11.</b> <a name="%_idx_1514" id="%_idx_1514"/>De passagem, Ben também comenta enigmaticamente: “Testando os sinais dos pontos finais dos intervalos, é possível dividir <tt>mul-interval</tt> em nove casos, apenas um deles requer mais de duas multiplicações”. Reescreva esse procedimento usando a sugestão de Ben.</p><p/><p>
</p><p/><p>Após depurar seu programa, Alyssa o mostra a um usuário em potencial, que reclama que seu programa resolve o problema errado. Ele quer um programa que possa lidar com números representados como um valor central e uma tolerância aditiva; por exemplo, ele deseja trabalhar com intervalos como 3,5 ± 0,15, em vez de [3,35, 3,65]. Alyssa retorna à sua mesa e resolve esse problema fornecendo um construtor alternativo e seletores alternativos:</p><p>
</p><p/><p><tt><a name="%_idx_1516" id="%_idx_1516"/>(define (make-center-width c w)<br/>
(make-interval (- c w) (+ c w)))<br/><a name="%_idx_1518" id="%_idx_1518"/>(define (center i)<br/>
(/ (+ (lower-bound i) (upper-bound i)) 2))<br/><a name="%_idx_1520" id="%_idx_1520"/>(define (width i)<br/>
(/ (- (upper-bound i) (lower-bound i)) 2))<br/></tt></p><p/><p/><p>Infelizmente, a maioria dos usuários de Alyssa são engenheiros. Situações reais de engenharia geralmente envolvem medições com apenas uma pequena incerteza, medida como a razão entre a largura do intervalo e o ponto médio do intervalo. Os engenheiros geralmente especificam tolerâncias percentuais nos parâmetros dos dispositivos, como nas especificações de resistores fornecidas anteriormente.</p><p>
</p><p><a name="%_thm_2.12" id="%_thm_2.12"/>
<b>Exercício 2.12.</b> Defina um construtor <a name="%_idx_1522" id="%_idx_1522"/><tt>make-center-percent</tt> que aceita um centro e uma porcentagem de tolerância e produz o intervalo desejado. Você também deve definir um seletor <tt>percent</tt> que produza a tolerância percentual para um determinado intervalo. O seletor <tt>center</tt> é igual ao mostrado acima.</p><p/><p>
</p><p><a name="%_thm_2.13" id="%_thm_2.13"/>
<b>Exercício 2.13.</b> Mostre que, sob a hipótese de pequenas tolerâncias percentuais, existe uma fórmula simples para a tolerância percentual aproximada do produto de dois intervalos em termos de tolerâncias dos fatores. Você pode simplificar o problema assumindo que todos os números são positivos.</p><p/><p>
</p><p/><p>Após um trabalho considerável, Alyssa P. Hacker entrega seu sistema finalizado. Vários anos depois, depois de ter esquecido tudo, ela recebe uma ligação frenética de um usuário irado, Lem E. Tweakit. Parece que Lem notou que a fórmula para resistores paralelos pode ser escrita de duas maneiras <a name="%_idx_1524" id="%_idx_1524"/>algébricas equivalentes:</p><p>
</p><p/><div align="left"><img src="images/ch2-Z-G-9.gif" border="0"/></div><p/><p>e</p><p>
</p><p/><div align="left"><img src="images/ch2-Z-G-10.gif" border="0"/></div><p/><p>Ele escreveu os dois programas a seguir, cada um dos quais calcula a fórmula de resistores paralelos de maneira diferente:</p><p>
</p><p/><p><tt>(define (par1 r1 r2)<br/>
(div-interval (mul-interval r1 r2)<br/>
(add-interval r1 r2)))<br/>
(define (par2 r1 r2)<br/>
(let ((one (make-interval 1 1))) <br/>
(div-interval one<br/>
(add-interval (div-interval one r1)<br/>
(div-interval one r2)))))<br/></tt></p><p/><p>Lem reclama que o programa de Alyssa fornece respostas diferentes para as duas formas de computação. Esta é uma queixa séria.</p><p>
</p><p><a name="%_thm_2.14" id="%_thm_2.14"/>
<b>Exercício 2.14.</b> Demonstre que Lem está certo. Investigue o comportamento do sistema em uma variedade de expressões aritméticas. Faça alguns intervalos <em>A</em> e <em>B</em> e use-os para calcular as expressões <em>A</em>/<em>A</em> e <em>A</em>/<em>B</em>. Você obterá mais informações usando intervalos cuja largura é uma pequena porcentagem do valor central. Examine os resultados da computação na forma de porcentagem central (consulte o exercício <a href="#%_thm_2.12">2.12</a>).</p><p/><p>
</p><p><a name="%_thm_2.15" id="%_thm_2.15"/>
<b>Exercício 2.15.</b> Eva Lu Ator, outro usuário, também notou os diferentes intervalos calculados por expressões diferentes, mas algebricamente equivalentes. Ela diz que uma fórmula para calcular intervalos usando o sistema de Alyssa produzirá limites de erro mais apertados se puder ser escrita de tal forma que nenhuma variável que represente um número incerto seja repetida. Assim, ela diz, <tt>par2</tt> é um programa “melhor” para resistências paralelas que <tt>par1</tt>. Ela está certa? Por quê?</p><p/><p>
</p><p><a name="%_thm_2.16" id="%_thm_2.16"/>
<b>Exercício 2.16.</b> Explique, em geral, pois expressões algébricas equivalentes podem levar a respostas diferentes. Você pode criar um pacote aritmético intervalado que não tenha essa deficiência ou essa tarefa é impossível? (Aviso: esse problema é muito difícil).</p><p>
</p><p>
</p><p/><div class="smallprint"><hr/></div><p>
</p><div class="footnote"><p><a name="footnote_Temp_133" href="#call_footnote_Temp_133" id="footnote_Temp_133"><sup><small>2</small></sup></a> O nome <a name="%_idx_1332" id="%_idx_1332"/><tt>cons</tt> significa “construção”. Os nomes <a name="%_idx_1334" id="%_idx_1334"/><tt>car</tt> e <a name="%_idx_1336" id="%_idx_1336"/><tt>cdr</tt> derivam da implementação original do Lisp no <a name="%_idx_1338" id="%_idx_1338"/><a name="%_idx_1340" id="%_idx_1340"/>IBM 704. Essa máquina possuía um esquema de endereçamento que permitia referenciar as partes “endereço” e “decremento” de um local de memória. <tt>Car</tt> significa “Conteúdo do Endereço parte do Registrador” e <tt>cdr</tt> significa “Conteúdo de Decremento da parte de Registrador”.</p><p><a name="footnote_Temp_135" href="#call_footnote_Temp_135" id="footnote_Temp_135"><sup><small>3</small></sup></a> Outra maneira de definir os seletores e o construtor é</p><p/><p><tt>(define make-rat cons)<br/>
(define numer car)<br/>
(define denom cdr)<br/></tt></p><p/><p>A primeira definição associa o nome <tt>make-rat</tt> ao valor da expressão <tt>cons</tt>, que é o procedimento primitivo que constrói pares. Assim, <tt>make-rat</tt> e <tt>cons</tt> são nomes para o mesmo construtor primitivo.</p><p>Definir seletores e construtores dessa maneira é eficiente: em vez de <tt>make-rat</tt> <em>calling</em> <tt>cons</tt>, <tt>make-rat</tt> <em>é</em> <tt>cons</tt>, portanto, existe apenas um procedimento chamado, não dois, quando <tt>make-rat</tt> é chamado. Por outro lado, fazer isso anula os auxílios de depuração que rastreiam chamadas de procedimento ou colocam pontos de interrupção em chamadas de procedimento: você pode ver <tt>make-rat</tt> sendo chamado, mas certamente não deseja ver a todas as chamadas para <tt>cons</tt>.</p><p>Optamos por não usar esse estilo de definição neste livro.</p><p><a name="footnote_Temp_136" href="#call_footnote_Temp_136" id="footnote_Temp_136"><sup><small>4</small></sup></a> <a name="%_idx_1356" id="%_idx_1356"/><a name="%_idx_1358" id="%_idx_1358"/><a name="%_idx_1360" id="%_idx_1360"/><a name="%_idx_1362" id="%_idx_1362"/><a name="%_idx_1364" id="%_idx_1364"/><tt>Display</tt> é a primitiva do Scheme para imprimir dados. A primitiva do Scheme <tt>newline</tt> inicia uma nova linha para impressão. <a name="%_idx_1366" id="%_idx_1366"/> <a name="%_idx_1368" id="%_idx_1368"/>Nenhum desses procedimentos retorna um valor útil, portanto, nos usos de <tt>print-rat</tt> abaixo, mostramos apenas o que <tt>print-rat</tt> imprime, não o que o interpretador imprime como o valor retornado por <tt>print-rat</tt>.</p><p><a name="footnote_Temp_140" href="#call_footnote_Temp_140" id="footnote_Temp_140"><sup><small>5</small></sup></a> Surpreendentemente, essa ideia é muito difícil de formular rigorosamente. Existem duas abordagens para dar essa formulação. Um, criada por <a name="%_idx_1422" id="%_idx_1422"/>C. A. R. Hoare (1972), é conhecido como o método de <a name="%_idx_1424" id="%_idx_1424"/><a name="%_idx_1426" id="%_idx_1426"/><em>modelos abstratos</em>. Formaliza a especificação de “procedimentos mais condições”, conforme descrito no exemplo de número racional acima. Observe que a condição na representação do número racional foi declarada em termos de fatos sobre números inteiros (igualdade e divisão). Em geral, modelos abstratos definem novos tipos de objetos de dados em termos de tipos de objetos de dados definidos anteriormente. Portanto, asserções sobre objetos de dados podem ser verificadas, reduzindo-as a asserções sobre objetos de dados definidos anteriormente. Outra abordagem, introduzida por <a name="%_idx_1428" id="%_idx_1428"/>Zilles no MIT, por <a name="%_idx_1430" id="%_idx_1430"/>Goguen, <a name="%_idx_1432" id="%_idx_1432"/>Thatcher, <a name="%_idx_1434" id="%_idx_1434"/>Wagner e <a name="%_idx_1436" id="%_idx_1436"/>Wright na IBM (consulte Thatcher, Wagner e Wright 1978) e por <a name="%_idx_1438" id="%_idx_1438"/>Guttag em Toronto (consulte Guttag 1977), é chamado <a name="%_idx_1440" id="%_idx_1440"/><a name="%_idx_1442" id="%_idx_1442"/><em>especificação algébrica</em>. Ele considera os “procedimentos” como elementos de um sistema algébrico abstrato cujo comportamento é especificado por axiomas que correspondem às nossas “condições” e usa as técnicas da álgebra abstrata para verificar afirmações sobre objetos de dados. Ambos os métodos são pesquisados no artigo por <a name="%_idx_1444" id="%_idx_1444"/>Liskov e Zilles (1975).</p></div>
</body>
</html>