-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-20.html
286 lines (213 loc) · 53.9 KB
/
book-Z-H-20.html
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
<?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_3.1" id="%_sec_3.1"/>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_3.1">3.1 Atribuição e estado local</a></h2><p>
<a name="%_idx_2836" id="%_idx_2836"/><a name="%_idx_2838" id="%_idx_2838"/>Normalmente vemos o mundo como preenchido por objetos independentes, cada um com um estado que muda com o tempo. Diz-se que um objeto “tem estado” se seu comportamento é influenciado por sua história. Uma conta bancária, por exemplo, declara que a resposta à pergunta “Posso sacar $100?” depende do histórico de transações de depósito e retirada. Podemos caracterizar o estado de um objeto por uma ou mais <a name="%_idx_2840" id="%_idx_2840"/><em>variáveis de estado</em>, que entre elas mantêm informações suficientes sobre o histórico para determinar o comportamento atual do objeto. Em um sistema bancário simples, poderíamos caracterizar o estado de uma conta por um saldo atual, em vez de lembrar todo o histórico das transações da conta.</p><p>Em um sistema composto por muitos objetos, os objetos raramente são completamente independentes. Cada um pode influenciar os estados de outros por meio de interações, que servem para acoplar as variáveis de estado de um objeto às de outros objetos. De fato, a visão de que um sistema é composto de objetos separados é mais útil quando as variáveis de estado do sistema podem ser agrupadas em subsistemas intimamente acoplados que são apenas fracamente acoplados a outros subsistemas.</p><p>Essa visão de um sistema pode ser uma estrutura poderosa para organizar modelos computacionais do sistema. Para que esse modelo seja modular, ele deve ser decomposto em objetos computacionais que modelam os objetos reais no sistema. Cada objeto computacional deve ter suas próprias <em>variáveis de estado local</em> que descrevem o estado real do objeto. Como os estados dos objetos no sistema que são modelados mudam ao longo do tempo, as variáveis de estado dos objetos computacionais correspondentes também devem mudar. Se optarmos por modelar o fluxo de tempo no sistema pelo tempo decorrido no computador, devemos ter uma maneira de construir objetos computacionais cujos comportamentos mudam à medida que nossos programas são executados. Em particular, se desejarmos modelar variáveis de estado por nomes simbólicos comuns na linguagem de programação, a linguagem deverá fornecer um <a name="%_idx_2842" id="%_idx_2842"/><em>operador de atribuição</em> para permitir a alteração do valor associado a um nome.</p><p>
<a name="%_sec_3.1.1" id="%_sec_3.1.1"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.1.1">3.1.1 Variáveis de estado local</a></h3><p>
<a name="%_idx_2844" id="%_idx_2844"/><a name="%_idx_2846" id="%_idx_2846"/>
<a name="%_idx_2848" id="%_idx_2848"/><a name="%_idx_2850" id="%_idx_2850"/>Para ilustrar o que queremos dizer com um objeto computacional com estado variável no tempo, modelaremos a situação de retirada de dinheiro de uma conta bancária. Faremos isso usando o procedimento <tt>withdraw</tt>, que assume como argumento um <tt>amount</tt> a ser retirada. Se houver dinheiro suficiente na conta para acomodar a retirada, <tt>withdraw</tt> deve devolver o saldo restante após a retirada. Caso contrário, <tt>withdraw</tt> deve retornar a mensagem <em>Insufficient funds.</em> Por exemplo, se começarmos com $100 na conta, devemos obter a seguinte sequência de respostas usando <tt>withdraw</tt>:</p><p>
</p><p/><p><tt>(withdraw 25)<br/><i>75</i><br/>
(withdraw 25)<br/><i>50</i><br/>
(withdraw 60)<br/><i>"Insufficient funds"</i><br/>
(withdraw 15)<br/><i>35</i><br/></tt></p><p/><p>Observe que a expressão <tt>(withdraw 25)</tt>, avaliada duas vezes, produz valores diferentes. Este é um novo tipo de comportamento para um procedimento. Até agora, todos os nossos procedimentos podiam ser vistos como especificações para o cálculo de funções matemáticas. Uma chamada para um procedimento calculava o valor da função aplicada aos argumentos fornecidos, e duas chamadas para o mesmo procedimento com os mesmos argumentos sempre produziam o mesmo resultado.<a name="call_footnote_Temp_321" href="#footnote_Temp_321" id="call_footnote_Temp_321"><sup><small>1</small></sup></a></p><p>Para implementar <tt>withdraw</tt>, podemos usar uma variável <tt>balance</tt> para indicar o saldo em dinheiro na conta e definir <tt>withdraw</tt> como um procedimento que acessa <tt>balance</tt>. O procedimento <tt>withdraw</tt> verifica se o <tt>balance</tt> é, pelo menos, tão grande quanto o <tt>amount</tt>. Nesse caso, <tt>withdraw</tt> diminui <tt>balance</tt> pelo <tt>amount</tt> e retorna o novo valor de <tt>balance</tt>. Caso contrário, <tt>withdraw</tt> retorna a mensagem <em>Insufficient funds</em>. Aqui estão as definições de <tt>balance</tt> e <tt>withdraw</tt>:</p><p>
</p><p/><p><tt>(define balance 100)<br/><br/><a name="%_idx_2858" id="%_idx_2858"/>(define (withdraw amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds"))<br/></tt></p><p/><p>A redução do <tt>balance</tt> é realizada pela expressão</p><p>
</p><p/><p><tt>(set! balance (- balance amount))<br/></tt></p><p/><p>
<a name="%_idx_2860" id="%_idx_2860"/><a name="%_idx_2862" id="%_idx_2862"/>Isso usa a forma especial <tt>set!</tt>, cuja sintaxe é</p><p>
</p><p/><p><tt>(set! <<em>name</em>> <<em>new-value</em>>)<br/></tt></p><p/><p>Aqui <<em>name</em>> é um símbolo e <<em>new-value</em>> é qualquer expressão. <tt>Set!</tt> altera <<em>name</em>> para que seu valor seja o resultado obtido ao avaliar <<em>new-value</em>>. No caso em questão, alteramos o <tt>balance</tt> para que seu novo valor seja o resultado da subtração do <tt>amount</tt> do valor anterior do <tt>balance</tt>. <a name="call_footnote_Temp_322" href="#footnote_Temp_322" id="call_footnote_Temp_322"><sup><small>2</small></sup></a></p><p>
<a name="%_idx_2874" id="%_idx_2874"/><a name="%_idx_2876" id="%_idx_2876"/><tt>Withdraw</tt> também usa o forma especial <tt>begin</tt> para fazer com que duas expressões sejam avaliadas no caso em que o teste <tt>if</tt> for verdadeiro: primeiro diminuindo <tt>balance</tt> e, em seguida, retorne o valor de <tt>balance</tt>. Em geral, avaliando a expressão</p><p>
</p><p/><p><tt>(begin <<em>exp<sub>1</sub></em>> <<em>exp<sub>2</sub></em>> <tt>...</tt> <<em>exp<sub><em>k</em></sub></em>>)<br/></tt></p><p/><p>faz com que as expressões <<em>exp<sub>1</sub></em>> a <<em>exp<sub><em>k</em></sub></em>> sejam avaliadas em sequência e o valor da expressão final <<em>exp<sub><em>k</em></sub></em>> a ser retornado como o valor de toda forma <tt>begin</tt>.<a name="call_footnote_Temp_323" href="#footnote_Temp_323" id="call_footnote_Temp_323"><sup><small>3</small></sup></a></p><p>Embora a <tt>withdraw</tt> funcione como desejado, a variável <tt>balance</tt> apresenta um problema. Conforme especificado acima, <tt>balance</tt> é um nome definido no ambiente global e é acessível de forma livre para ser examinado ou modificado por qualquer procedimento. Seria muito melhor se, de alguma forma, pudéssemos tornar <tt>balance</tt> interno para <tt>withdraw</tt>, para que <tt>withdraw</tt> fosse o único procedimento que poderia acessar <tt>balance</tt> diretamente e qualquer outro procedimento pode acessar o <tt>balance</tt> apenas indiretamente (através de chamadas para <tt>withdraw</tt>). Isso modelaria com mais precisão a noção de que <tt>balance</tt> é uma variável de estado local usada por <tt>withdraw</tt> para acompanhar o estado da conta.</p><p>Podemos tornar <tt>balance</tt> interno para <tt>withdraw</tt> reescrevendo a definição da seguinte maneira:</p><p>
</p><p/><p><tt><a name="%_idx_2884" id="%_idx_2884"/>(define new-withdraw<br/>
(let ((balance 100))<br/>
(lambda (amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds"))))<br/></tt></p><p/><p>O que fizemos aqui é usar <tt>let</tt> para estabelecer um ambiente com uma variável local <tt>balance</tt>, ligada ao valor inicial 100. Nesse ambiente local, usamos o <tt>lambda</tt> para criar um procedimento que considera <tt>amount</tt> como argumento e se comporta como nosso procedimento anterior <tt>withdraw</tt>. Este procedimento – retornado como resultado da avaliação da expressão <tt>let</tt> - é <tt>new-withdraw</tt>, que se comporta exatamente da mesma maneira que <tt>withdraw</tt>, mas cuja a variável <tt>balance</tt> não pode ser acessada por nenhum outro procedimento.<a name="call_footnote_Temp_324" href="#footnote_Temp_324" id="call_footnote_Temp_324"><sup><small>4</small></sup></a></p><p>Combinar <tt>set!</tt> com variáveis locais é a técnica de programação geral que usaremos para construir objetos computacionais com estado local. Infelizmente, o uso dessa técnica levanta um problema sério: quando introduzimos os procedimentos, também introduzimos o modelo de substituição de avaliação (seção <a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a>) para fornecer uma interpretação do significado da aplicação do procedimento. Dissemos que a aplicação de um procedimento deve ser interpretada como uma avaliação do corpo do procedimento com os parâmetros formais substituídos por seus valores. O problema é que, assim que introduzimos a atribuição em nossa linguagem, a substituição não é mais um modelo adequado de aplicação de procedimentos. (Veremos por que isso ocorre na seção <a href="#%_sec_3.1.3">3.1.3</a>). Como consequência, tecnicamente, neste momento, não temos como entender por que o procedimento <tt>new-withdraw</tt> se comporta como mostrado acima. Para realmente entender um procedimento como <tt>new-withdraw</tt>, precisaremos desenvolver um novo modelo de aplicação de procedimento. Na seção <a href="book-Z-H-21.html#%_sec_3.2">3.2</a>, apresentaremos esse modelo, com uma explicação do <tt>set!</tt> e das variáveis locais. Primeiro, porém, examinamos algumas variações sobre o tema estabelecido por <tt>new-withdraw</tt>.</p><p>O procedimento a seguir, <tt>make-withdraw</tt>, cria “processadores de retirada”. O parâmetro formal <tt>balance</tt> em <tt>make-withdraw</tt> especifica o valor inicial em dinheiro na conta.<a name="call_footnote_Temp_325" href="#footnote_Temp_325" id="call_footnote_Temp_325"><sup><small>5</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_2894" id="%_idx_2894"/>(define (make-withdraw balance)<br/>
(lambda (amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds")))<br/></tt></p><p/><p>
<tt>Make-withdraw</tt> pode ser usado da seguinte maneira para criar dois objetos <tt>W1</tt> e <tt>W2</tt>:</p><p>
</p><p/><p><tt>(define W1 (make-withdraw 100))<br/>
(define W2 (make-withdraw 100))<br/>
(W1 50)<br/><i>50</i><br/>
(W2 70)<br/><i>30</i><br/>
(W2 40)<br/><i>"Insufficient funds"</i><br/>
(W1 40)<br/><i>10</i><br/></tt></p><p/><p>Observe que <tt>W1</tt> e <tt>W2</tt> são objetos completamente independentes, cada um com sua própria variável de estado local <tt>balance</tt>. As retiradas de um não afetam o outro.</p><p>Também podemos criar objetos que lidam com depósitos e saques e, portanto, podemos representar contas bancárias simples. Aqui está um procedimento que retorna um “objeto de conta bancária” com um saldo inicial especificado:</p><p>
</p><p/><p><tt><a name="%_idx_2896" id="%_idx_2896"/><a name="%_idx_2898" id="%_idx_2898"/>(define (make-account balance)<br/>
(define (withdraw amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds"))<br/>
(define (deposit amount)<br/>
(set! balance (+ balance amount))<br/>
balance)<br/>
(define (dispatch m)<br/>
(cond ((eq? m 'withdraw) withdraw)<br/>
((eq? m 'deposit) deposit)<br/>
(else (error "Unknown request -- MAKE-ACCOUNT"<br/>
m))))<br/>
dispatch)<br/></tt></p><p/><p>Cada chamada para <tt>make-account</tt> configura um ambiente com uma variável de estado local <tt>balance</tt>. Nesse ambiente, <tt>make-account</tt> define os procedimentos <tt>deposit</tt> e <tt>withdraw</tt> que acessam <tt>balance</tt> e um procedimento adicional <tt>dispatch</tt> que recebe uma “mensagem” como entrada e retorna um dos dois procedimentos locais. O próprio procedimento <tt>dispatch</tt> é retornado como o valor que representa o objeto de conta bancária. Este é precisamente o estilo de programação <a name="%_idx_2900" id="%_idx_2900"/><em>de transmissão de mensagens</em> que vimos na seção <a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>, embora aqui o usaríamos em conjunto com a capacidade de modificar variáveis locais.</p><p>
<tt>Make-account</tt> pode ser usado da seguinte maneira:</p><p>
</p><p/><p><tt>(define acc (make-account 100))<br/>
((acc 'withdraw) 50)<br/><i>50</i><br/>
((acc 'withdraw) 60)<br/><i>"Insufficient funds"</i><br/>
((acc 'deposit) 40)<br/><i>90</i><br/>
((acc 'withdraw) 60)<br/><i>30</i><br/></tt></p><p/><p>Cada chamada para <tt>acc</tt> retorna o procedimento <tt>deposit</tt> ou <tt>withdraw</tt> definido localmente, que é aplicado ao valor <tt>amount</tt>. Como foi o caso com <tt>make-withdraw</tt>, outra chamada para <tt>make-account</tt></p><p>
</p><p/><p><tt>(define acc2 (make-account 100))<br/></tt></p><p/><p>produzirá um objeto de conta separado, que mantém seu próprio <tt>balance</tt> local.</p><p>
</p><p><a name="%_thm_3.1" id="%_thm_3.1"/>
<b>Exercício 3.1.</b> Um <a name="%_idx_2902" id="%_idx_2902"/><em>acumulador</em> é um procedimento chamado repetidamente com um único argumento numérico e acumula seus argumentos em uma soma. Cada vez que é chamado, ele retorna a soma acumulada no momento. Escreva um procedimento <a name="%_idx_2904" id="%_idx_2904"/><tt>make-accumulator</tt> que gere acumuladores, cada um mantendo uma soma independente. A entrada para <tt>make-accumulator</tt> deve especificar o valor inicial da soma; por exemplo</p><p>
</p><p/><p><tt>(define A (make-accumulator 5))<br/>
(A 10)<br/><i>15</i><br/>
(A 10)<br/><i>25</i><br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.2" id="%_thm_3.2"/>
<b>Exercício 3.2.</b> Em aplicativos de teste de software, é útil poder contar o número de vezes que um determinado procedimento é chamado durante o curso de um cálculo. Escreva um procedimento <a name="%_idx_2906" id="%_idx_2906"/><a name="%_idx_2908" id="%_idx_2908"/><a name="%_idx_2910" id="%_idx_2910"/><tt>make-monitored</tt> que tome como entrada um procedimento, <tt>f</tt>, que aceite uma entrada. O resultado retornado por <tt>make-monitored</tt> é um terceiro procedimento, digamos <tt>mf</tt>, que monitora o número de vezes que foi chamado mantendo um contador interno. Se a entrada para <tt>mf</tt> é o símbolo especial <tt>how-many-calls?</tt>, então <tt>mf</tt> retorna o valor do contador. Se a entrada for o símbolo especial <tt>reset-count</tt>, então <tt>mf</tt> redefine o contador para zero. Para qualquer outra entrada, <tt>mf</tt> retorna o resultado da chamada <tt>f</tt> nessa entrada e incrementa o contador. Por exemplo, poderíamos fazer uma versão monitorada do procedimento <tt>sqrt</tt>:</p><p>
</p><p/><p><tt>(define s (make-monitored sqrt))<br/><br/>
(s 100)<br/><i>10</i><br/><br/>
(s 'how-many-calls?)<br/><i>1</i><br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.3" id="%_thm_3.3"/>
<b>Exercício 3.3.</b> <a name="%_idx_2912" id="%_idx_2912"/><a name="%_idx_2914" id="%_idx_2914"/>Modifique o procedimento <tt>make-account</tt> para criar contas protegidas por senha. Ou seja, <tt>make-account</tt> deve usar um símbolo como argumento adicional, como em</p><p>
</p><p/><p><tt>(define acc (make-account 100 'secret-password))<br/></tt></p><p/><p>O objeto de conta resultante deve processar uma solicitação apenas se for acompanhado pela senha com a qual a conta foi criada e devolver uma reclamação:</p><p>
</p><p/><p><tt>((acc 'secret-password 'withdraw) 40)<br/><i>60</i><br/><br/>
((acc 'some-other-password 'deposit) 50)<br/><i>"Incorrect password"</i><br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.4" id="%_thm_3.4"/>
<b>Exercício 3.4.</b> Modifique o procedimento <tt>make-account</tt> do exercício <a href="#%_thm_3.3">3.3</a> adicionando outra variável de estado local para que, se uma conta for acessada mais de sete vezes consecutivas com uma senha incorreta, ele invoca o procedimento <tt>call-the-cops</tt>.</p><p>
</p><p>
<a name="%_sec_3.1.2" id="%_sec_3.1.2"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.1.2">3.1.2 Os benefícios da introdução de atribuição</a></h3><p>
<a name="%_idx_2916" id="%_idx_2916"/>
<a name="%_idx_2918" id="%_idx_2918"/><a name="%_idx_2920" id="%_idx_2920"/>Como veremos, a introdução de atribuições em nossa linguagem de programação nos leva a um emaranhado de questões conceituais difíceis. No entanto, visualizar sistemas como coleções de objetos com estado local é uma técnica poderosa para manter um projeto modular. Como um exemplo simples, considere o projeto de um procedimento <tt>rand</tt> que, sempre que é chamado, retorna um número inteiro escolhido aleatoriamente.</p><p>
<a name="%_idx_2922" id="%_idx_2922"/>Não está claro o que se entende por “escolhido aleatoriamente”. O que presumivelmente queremos é que chamadas sucessivas para <tt>rand</tt> produzam uma sequência de números que possua propriedades estatísticas de distribuição uniforme. Não discutiremos métodos para gerar sequências adequadas aqui. Em vez disso, assumiremos que temos um procedimento <tt>rand-update</tt> que possui a propriedade de que, se começarmos com um determinado número <em>x</em><sub>1</sub> e forma</p><p>
</p><p/><p><tt><em>x</em><sub>2</sub> = (rand-update <em>x</em><sub>1</sub>)<br/><em>x</em><sub>3</sub> = (rand-update <em>x</em><sub>2</sub>)<br/></tt></p><p/><p>então a sequência de valores <em>x</em><sub>1</sub>, <em>x</em><sub>2</sub>, <em>x</em><sub>3</sub>, <tt>…</tt>, terão as propriedades estatísticas desejadas.<a name="call_footnote_Temp_330" href="#footnote_Temp_330" id="call_footnote_Temp_330"><sup><small>6</small></sup></a></p><p>Podemos implementar <tt>rand</tt> como um procedimento com uma variável de estado local <tt>x</tt> que é iniciada com algum valor fixo <tt>random-init</tt>. Cada chamada para <tt>rand</tt> calcula <tt>rand-update</tt> do valor atual de <tt>x</tt>, retorna isso como o número aleatório e também o armazena como o novo valor de <tt>x</tt>.</p><p>
</p><p/><p><tt><a name="%_idx_2934" id="%_idx_2934"/>(define rand<br/>
(let ((x random-init))<br/>
(lambda ()<br/>
(set! x (rand-update x))<br/>
x)))<br/></tt></p><p/><p/><p>Obviamente, poderíamos gerar a mesma sequência de números aleatórios sem usar a atribuição simplesmente chamando <tt>rand-update</tt> diretamente. No entanto, isso significaria que qualquer parte do nosso programa que usasse números aleatórios teria que se lembrar explicitamente do valor atual de <tt>x</tt> a ser passado como argumento para <tt>rand-update</tt>. Para perceber o que isso seria irritante, considere o uso de números aleatórios para implementar uma técnica chamada <a name="%_idx_2936" id="%_idx_2936"/><a name="%_idx_2938" id="%_idx_2938"/><em>simulação de Monte Carlo</em>.</p><p>O método de Monte Carlo consiste em escolher experimentos de amostra aleatoriamente de um conjunto grande e, em seguida, fazer deduções com base nas probabilidades estimadas da tabulação dos resultados desses experimentos. Por exemplo, podemos aproximar <a name="%_idx_2940" id="%_idx_2940"/>π usando o fato de que 6/π<sup>2</sup> é a probabilidade de que dois números inteiros escolhidos aleatoriamente não tenham fatores em comum; isto é, que seu maior divisor comum será 1.<a name="call_footnote_Temp_331" href="#footnote_Temp_331" id="call_footnote_Temp_331"><sup><small>7</small></sup></a> Para obter a aproximação de π, realizamos um grande número de experimentos. Em cada experimento, escolhemos dois números inteiros aleatoriamente e realizamos um teste <a name="%_idx_2946" id="%_idx_2946"/>para verificar se o MDC é 1. A fração de vezes que o teste é aprovado nos dá nossa estimativa de 6/π<sup>2</sup>, e a partir disso obtemos nossa aproximação a π.</p><p>O coração do nosso programa é um procedimento <tt>monte-carlo</tt>, que usa como argumento o número de vezes para tentar um experimento, com o experimento, representado como um procedimento sem argumento que retornará verdadeiro ou falso cada vez que é executado. <tt>Monte-carlo</tt> executa o experimento para o número designado de tentativas e retorna um número informando a fração das tentativas nas quais o experimento foi considerado verdadeiro.</p><p>
</p><p/><p><tt><a name="%_idx_2948" id="%_idx_2948"/>(define (estimate-pi trials)<br/>
(sqrt (/ 6 (monte-carlo trials cesaro-test))))<br/><a name="%_idx_2950" id="%_idx_2950"/>(define (cesaro-test)<br/>
(= (gcd (rand) (rand)) 1))<br/><a name="%_idx_2952" id="%_idx_2952"/>(define (monte-carlo trials experiment)<br/>
(define (iter trials-remaining trials-passed)<br/>
(cond ((= trials-remaining 0)<br/>
(/ trials-passed trials))<br/>
((experiment)<br/>
(iter (- trials-remaining 1) (+ trials-passed 1)))<br/>
(else<br/>
(iter (- trials-remaining 1) trials-passed))))<br/>
(iter trials 0))<br/></tt></p><p/><p/><p>Agora tentaremos o mesmo cálculo usando <tt>rand-update</tt> diretamente, em vez de <tt>rand</tt>, da maneira que seríamos forçados a continuar se não usássemos a atribuição para modelar o estado local:</p><p>
</p><p/><p><tt><a name="%_idx_2954" id="%_idx_2954"/>(define (estimate-pi trials)<br/>
(sqrt (/ 6 (random-gcd-test trials random-init))))<br/>
(define (random-gcd-test trials initial-x)<br/>
(define (iter trials-remaining trials-passed x)<br/>
(let ((x1 (rand-update x)))<br/>
(let ((x2 (rand-update x1)))<br/>
(cond ((= trials-remaining 0) <br/>
(/ trials-passed trials))<br/>
((= (gcd x1 x2) 1)<br/>
(iter (- trials-remaining 1)<br/>
(+ trials-passed 1)<br/>
x2))<br/>
(else<br/>
(iter (- trials-remaining 1)<br/>
trials-passed<br/>
x2))))))<br/>
(iter trials 0 initial-x))<br/></tt></p><p/><p/><p>Embora o programa ainda seja simples, trai algumas violações dolorosas da modularidade. Em nossa primeira versão do programa, usando <tt>rand</tt>, podemos expressar o método Monte Carlo diretamente como um procedimento geral <tt>monte-carlo</tt> que usa como argumento um arbitrário procedimento <tt>experiment</tt>. Em nossa segunda versão do programa, sem estado local para o gerador de números aleatórios, o <tt>random-gcd-test</tt> deve manipular explicitamente os números aleatórios <tt>x1</tt> e <tt>x2</tt> e recicle <tt>x2</tt> através do laço iterativo como a nova entrada para <tt>rand-update</tt>. Esse tratamento explícito dos números aleatórios entrelaça a estrutura de acumular resultados de testes com o fato de que nosso experimento específico usa dois números aleatórios, enquanto outros experimentos de Monte Carlo podem usar um número aleatório ou três. Até o procedimento de nível superior <tt>estimate-pi</tt> deve se preocupar em fornecer um número aleatório inicial. O fato de o interior do gerador de números aleatórios vazar para outras partes do programa dificulta o isolamento da ideia de Monte Carlo, para que possa ser aplicada a outras tarefas. Na primeira versão do programa, a atribuição encapsula o estado do gerador de números aleatórios dentro do procedimento <tt>rand</tt>, para que os detalhes da geração de números aleatórios permaneçam independentes do restante do programa.</p><p>O fenômeno geral ilustrado pelo exemplo de Monte Carlo é o seguinte: Do ponto de vista de uma parte de um processo complexo, as outras partes parecem mudar com o tempo. Eles ocultaram o estado local variável em tempo. Se desejamos escrever programas de computador cuja estrutura reflete essa decomposição, criamos objetos computacionais (como contas bancárias e geradores de números aleatórios) cujo comportamento muda com o tempo. Modelamos o estado com variáveis de estado local e modelamos as mudanças de estado com atribuições para essas variáveis.</p><p>É tentador concluir esta discussão dizendo que, ao introduzir a atribuição e a técnica de ocultar o estado nas variáveis locais, somos capazes de estruturar os sistemas de uma maneira mais modular do que se todo o estado tivesse que ser manipulado explicitamente, passando parâmetros adicionais. Infelizmente, como veremos, a história não é tão simples.</p><p>
</p><p><a name="%_thm_3.5" id="%_thm_3.5"/>
<b>Exercício 3.5.</b> <a name="%_idx_2956" id="%_idx_2956"/><a name="%_idx_2958" id="%_idx_2958"/><a name="%_idx_2960" id="%_idx_2960"/><em>Integração Monte Carlo</em> é um método de estimativa de integrais definidas por meio da simulação de Monte Carlo. Considere calcular a área de uma região do espaço descrita por um predicado <em>P</em>(<em>x</em>, <em>y</em>) que é verdadeiro para pontos (<em>x</em>, <em>y</em>) na região e falso para pontos que não estão na região. Por exemplo, a região contida em um círculo de raio 3 centralizado em (5, 7) é descrita pelo predicado que testa se (<em>x</em> - 5)<sup>2</sup> + (<em>y</em> - 7)<sup>2</sup><u><</u> 3<sup>2</sup>. Para estimar a área da região descrita por esse predicado, comece escolhendo um retângulo que contenha a região. Por exemplo, um retângulo com cantos diagonalmente opostos em (2, 4) e (8, 10) contém o círculo acima. A integral desejada é a área da parte do retângulo que fica na região. Podemos estimar a integral escolhendo, aleatoriamente, pontos (<em>x</em>,<em>y</em>) que estão no retângulo e testando <em>P</em>(<em>x</em>, <em>e</em>) para cada ponto para determinar se o ponto está na região. Se tentarmos isso com muitos pontos, a fração de pontos que caem na região deve fornecer uma estimativa da proporção do retângulo que fica na região. Portanto, multiplicar essa fração pela área de todo o retângulo deve produzir uma estimativa da integral.</p><p>Implemente a integração de Monte Carlo como um procedimento <a name="%_idx_2962" id="%_idx_2962"/><tt>estimate-integral</tt> que usa como argumento um predicado <tt>P</tt>, limites superior e inferior <tt>x1</tt>, <tt>x2</tt>, <tt>y1</tt>, e <tt>y2</tt> para o retângulo, e o número de tentativas a serem realizadas para produzir a estimativa. Seu procedimento deve usar o mesmo procedimento <tt>monte-carlo</tt> que foi usado acima para estimar π. Use sua <tt>estimate-integral</tt> para produzir uma estimativa de π medindo a área de um círculo unitário.</p><p>Você achará útil ter um procedimento que retorne um número escolhido aleatoriamente em um determinado intervalo. O seguinte procedimento <tt>random-in-range</tt> implementa isso em termos do procedimento <tt>random</tt> usado na seção <a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>, que retorna um número não negativo menos sua entrada.<a name="call_footnote_Temp_333" href="#footnote_Temp_333" id="call_footnote_Temp_333"><sup><small>8</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_2970" id="%_idx_2970"/>(define (random-in-range low high)<br/>
(let ((range (- high low)))<br/>
(+ low (random range))))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.6" id="%_thm_3.6"/>
<b>Exercício 3.6.</b> <a name="%_idx_2972" id="%_idx_2972"/><a name="%_idx_2974" id="%_idx_2974"/>É útil poder redefinir um gerador de números aleatórios para produzir uma sequência a partir de um determinado valor. Crie um novo procedimento <tt>rand</tt> que é chamado com um argumento que seja o símbolo <tt>generate</tt> ou o símbolo <tt>reset</tt> e se comporte da seguinte maneira: <tt>(rand 'generate)</tt> produz um novo número aleatório; <tt>((rand 'reset) <<em>new-value</em>>)</tt> redefine a variável de estado interna para o <<em>new-value</em>>. Assim, redefinindo o estado, pode-se gerar sequências repetíveis. Isso é muito útil ao testar e depurar programas que usam números aleatórios.</p><p>
</p><p>
<a name="%_sec_3.1.3" id="%_sec_3.1.3"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.1.3">3.1.3 Os custos de introdução da atribuição</a></h3><p>
<a name="%_idx_2976" id="%_idx_2976"/>Como vimos, a operação <tt>set!</tt> nos permite modelar objetos que possuem estado local. No entanto, essa vantagem tem um preço. Nossa linguagem de programação não pode mais ser interpretada em termos do modelo de substituição da aplicação de procedimento que introduzimos na seção <a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a>. Além disso, nenhum modelo simples com propriedades matemáticas “agradáveis” pode ser uma estrutura adequada para lidar com objetos e atribuição em linguagens de programação.</p><p>Enquanto não usarmos atribuições, duas avaliações do mesmo procedimento com os mesmos argumentos produzirão o mesmo resultado, para que os procedimentos possam ser vistos como funções matemáticas de computação. A programação sem o uso de atribuições, como fizemos nos dois primeiros capítulos deste livro, é, portanto, conhecida como <a name="%_idx_2978" id="%_idx_2978"/><em>programação funcional</em>.</p><p>
<a name="%_idx_2980" id="%_idx_2980"/>Para entender como a atribuição complica, considere uma versão simplificada do procedimento <tt>make-withdraw</tt> da seção <a href="#%_sec_3.1.1">3.1.1</a> que não se preocupe em verificar se há uma quantidade insuficiente:</p><p>
</p><p/><p><tt><a name="%_idx_2982" id="%_idx_2982"/>(define (make-simplified-withdraw balance)<br/>
(lambda (amount)<br/>
(set! balance (- balance amount))<br/>
balance))<br/>
(define W (make-simplified-withdraw 25))<br/>
(W 20)<br/><i>5</i><br/>
(W 10)<br/><i> - 5</i><br/></tt></p><p/><p>Compare este procedimento com o seguinte procedimento <tt>make-decrementer</tt>, que não usa <tt>set!</tt>:</p><p>
</p><p/><p><tt><a name="%_idx_2984" id="%_idx_2984"/>(define (make-decrementer balance)<br/>
(lambda (amount)<br/>
(- balance amount)))<br/></tt></p><p/><p>
<tt>Make-decrementer</tt> retorna um procedimento que subtrai sua entrada de um valor designado <tt>balance</tt>, mas não há efeito acumulado em chamadas sucessivas, como em <tt>make-simplified-withdraw</tt>:</p><p>
</p><p/><p><tt>(define D (make-decrementer 25))<br/>
(D 20)<br/><i>5</i><br/>
(D 10)<br/><i>15</i><br/></tt></p><p/><p>Podemos usar o modelo de substituição para explicar como o <tt>make-decrementer</tt> funciona. Por exemplo, analisaremos a avaliação da expressão</p><p>
</p><p/><p><tt>((make-decrementer 25) 20)<br/></tt></p><p/><p>Primeiro, simplificamos o operador da combinação substituindo 25 por <tt>balance</tt> no corpo de <tt>make-decrementer</tt>. Isso reduz a expressão para</p><p>
</p><p/><p><tt>((lambda (amount) (- 25 amount)) 20)<br/></tt></p><p/><p>Agora aplicamos o operador substituindo 20 por <tt>amount</tt> no corpo da expressão <tt>lambda</tt>:</p><p>
</p><p/><p><tt>(- 25 20)<br/></tt></p><p/><p>A resposta final é 5.</p><p>Observe, no entanto, o que acontece se tentarmos uma análise de substituição semelhante com <tt>make-simplified-withdraw</tt>:</p><p>
</p><p/><p><tt>((make-simplified-withdraw 25) 20)<br/></tt></p><p/><p>Primeiro, simplificamos o operador, substituindo 25 por <tt>balance</tt> no corpo de <tt>make-simplified-withdraw</tt>. Isso reduz a expressão para <a name="call_footnote_Temp_335" href="#footnote_Temp_335" id="call_footnote_Temp_335"><sup><small>9</small></sup></a></p><p>
</p><p/><p><tt>((lambda (amount) (set! balance (- 25 amount)) 25) 20)<br/></tt></p><p/><p>Agora aplicamos o operador substituindo 20 por <tt>amount</tt> no corpo da expressão <tt>lambda</tt>:</p><p>
</p><p/><p><tt>(set! balance (- 25 20)) 25<br/></tt></p><p/><p>Se aderirmos ao modelo de substituição, teríamos que dizer que o significado da aplicação de procedimento é primeiro definir <tt>balance</tt> como 5 e depois retornar 25 como o valor da expressão. Isso recebe a resposta errada. Para obter a resposta correta, teríamos que distinguir de alguma forma a primeira ocorrência de <tt>balance</tt> (antes do efeito de <tt>set!</tt>) da segunda ocorrência de <tt>balance</tt> (após o efeito de <tt>set!</tt>), e o modelo de substituição não pode fazer isso.</p><p>O problema aqui é que a substituição se baseia, em última análise, na noção de que os símbolos em nossa linguagem são essencialmente nomes de valores. Mas assim que introduzimos <tt>set!</tt> e a ideia de que o valor de uma variável pode mudar, uma variável não pode mais ser simplesmente um nome. Agora, de alguma forma, uma variável se refere a um local em que um valor pode ser armazenado e o valor armazenado nesse local pode ser alterado. Na seção <a href="book-Z-H-21.html#%_sec_3.2">3.2</a>, veremos como os ambientes desempenham esse papel de “lugar” em nosso modelo computacional.</p><p>
<a name="%_sec_Temp_336" id="%_sec_Temp_336"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_336">Igualdade e mudança</a></h4><p>
<a name="%_idx_2986" id="%_idx_2986"/><a name="%_idx_2988" id="%_idx_2988"/>A questão que surge aqui é mais profunda do que a mera quebra de um modelo específico de computação. Assim que introduzimos mudanças em nossos modelos computacionais, muitas noções que eram anteriormente diretas se tornam problemáticas. Considere o conceito de dois objetos sendo “iguais”.</p><p>Suponha que chamamos <tt>make-decrementer</tt> duas vezes com o mesmo argumento para criar dois procedimentos:</p><p>
</p><p/><p><tt>(define D1 (make-decrementer 25))<br/>
(define D2 (make-decrementer 25))<br/></tt></p><p/><p><tt>D1</tt> e <tt>D2</tt> são os mesmos? Uma resposta aceitável é sim, pois <tt>D1</tt> e <tt>D2</tt> possuem o mesmo comportamento computacional – cada um é um procedimento que subtrai sua entrada de 25. De fato, <tt>D1</tt> poderia ser substituído por <tt>D2</tt> em qualquer cálculo sem alterar o resultado.</p><p>Compare isso com duas chamadas para <tt>make-simplified-withdraw</tt>:</p><p>
</p><p/><p><tt>(define W1 (make-simplified-withdraw 25))<br/>
(define W2 (make-simplified-withdraw 25))<br/></tt></p><p/><p><tt>W1</tt> e <tt>W2</tt> são os mesmos? Certamente que não, pois as chamadas para <tt>W1</tt> e <tt>W2</tt> possuem efeitos distintos, como mostra a seguinte sequência de interações:</p><p>
</p><p/><p><tt>(W1 20)<br/><i>5</i><br/>
(W1 20)<br/><i> - 15</i><br/>
(W2 20)<br/><i>5</i><br/></tt></p><p/><p>Mesmo que <tt>W1</tt> e <tt>W2</tt> sejam “iguais”, no sentido de que ambos são criados avaliando a mesma expressão, <tt>(make-simplified-withdraw 25)</tt>, não é verdade que <tt>W1</tt> possa ser substituído por <tt>W2</tt> em qualquer expressão sem alterar o resultado da avaliação da expressão.</p><p>Uma linguagem que apoia o conceito de que “iguais podem ser substituídos por iguais” em uma expressão sem alterar o valor da expressão é considerada <a name="%_idx_2990" id="%_idx_2990"/><a name="%_idx_2992" id="%_idx_2992"/><a name="%_idx_2994" id="%_idx_2994"/><em>referencialmente transparente</em>. A transparência referencial é violada quando incluímos <tt>set!</tt> em nossa linguagem de computador. Isso torna difícil determinar quando podemos simplificar expressões substituindo expressões equivalentes. Consequentemente, o raciocínio sobre programas que usam atribuição se torna drasticamente mais difícil.</p><p>Uma vez que renunciamos à transparência referencial, a noção do que significa para objetos computacionais ser “o mesmo” torna-se difícil de capturar de maneira formal. De fato, o significado de “mesmo” no mundo real que o modelo de nossos programas é pouco claro por si só. Em geral, podemos determinar que dois objetos aparentemente idênticos são de fato “o mesmo” apenas modificando um objeto e depois observando se o outro objeto mudou da mesma maneira. Mas como podemos saber se um objeto “mudou” além de observar o “mesmo” objeto duas vezes e ver se alguma propriedade do objeto difere de uma observação para a seguinte? Assim, não podemos determinar “mudança” sem alguma noção <em>a priori</em> de “igualdade” e não podemos determinar a igualdade sem observar os efeitos da mudança.</p><p>
<a name="%_idx_2996" id="%_idx_2996"/>Como um exemplo de como esse problema surge na programação, considere a situação em que Peter e Paul possuem uma conta bancária com $100. Existe uma diferença substancial entre modelar isso como</p><p>
</p><p/><p><tt>(define peter-acc (make-account 100))<br/>
(define paul-acc (make-account 100))<br/></tt></p><p/><p>e modelando-o como</p><p>
</p><p/><p><tt>(define peter-acc (make-account 100))<br/>
(define paul-acc peter-acc)<br/></tt></p><p/><p>Na primeira situação, as duas contas bancárias são distintas. As transações feitas por Peter não afetarão a conta de Paul e vice-versa. Na segunda situação, no entanto, definimos <tt>paul-acc</tt> como <em>o mesmo</em> que <tt>peter-acc</tt>. Com efeito, Peter e Paul agora possuem uma conta bancária conjunta e, se Peter fizer um saque de <tt>peter-acc</tt>, Paul observará menos dinheiro em <tt>paul-acc</tt>. Essas duas situações semelhantes, mas distintas, podem causar confusão na construção de modelos computacionais. Com a conta compartilhada, em particular, pode ser especialmente confuso que exista um objeto (a conta bancária) que tenha dois nomes diferentes (<tt>peter-acc</tt> e <tt>paul-acc</tt>); se estivermos procurando por todos os lugares em nosso programa onde <tt>paul-acc</tt> pode ser alterado, devemos lembrar também de ver o que muda <tt>peter-acc</tt>.<a name="call_footnote_Temp_337" href="#footnote_Temp_337" id="call_footnote_Temp_337"><sup><small>10</small></sup></a></p><p>Com referência às observações acima sobre “igualdade” e “mudança”, observe que, se Peter e Paul pudessem examinar apenas seus saldos bancários e não pudessem realizar operações que alterassem o saldo, a questão de se as duas contas são distintas seria discutível. Em geral, desde que nunca modifiquemos objetos de dados, podemos considerar um objeto de dados composto como sendo precisamente a totalidade de suas partes. Por exemplo, um número racional é determinado dando seu numerador e seu denominador. Mas essa visão não é mais válida na presença de alterações, onde um objeto de dados composto possui uma “identidade” que é algo diferente das partes das quais é composto. Uma conta bancária ainda é “a mesma”, mesmo que alteremos o saldo efetuando uma retirada; por outro lado, poderíamos ter duas contas bancárias diferentes com as mesmas informações de estado. Essa complicação é uma consequência, não da nossa linguagem de programação, mas da nossa percepção de uma conta bancária como um objeto. Por exemplo, normalmente não consideramos um número racional como um objeto mutável com identidade, de modo que pudéssemos alterar o numerador e ainda assim ter o mesmo número racional.<a name="%_sec_Temp_338" id="%_sec_Temp_338"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_338">Armadilhas da programação imperativa</a></h4><p>Ao contrário da programação funcional, a programação que faz uso extensivo da atribuição é conhecida como <a name="%_idx_3014" id="%_idx_3014"/><a name="%_idx_3016" id="%_idx_3016"/><em>programação imperativa</em>. Além de levantar complicações sobre modelos computacionais, os programas escritos em estilo imperativo são suscetíveis a erros que não podem ocorrer em programas funcionais. Por exemplo, lembre-se do programa fatorial iterativo da seção <a href="book-Z-H-11.html#%_sec_1.2.1">1.2.1</a>:</p><p/><p><tt>(define (factorial n)<br/>
(define (iter product counter)<br/>
(if (> counter n)<br/>
product<br/>
(iter (* counter product)<br/>
(+ counter 1))))<br/>
(iter 1 1))<br/></tt></p><p/><p>Em vez de passar argumentos no laço iterativo interno, podemos adotar um estilo mais imperativo usando atribuição explícita para atualizar os valores das variáveis <tt>product</tt> e <tt>counter</tt>:</p><p/><p><tt><a name="%_idx_3018" id="%_idx_3018"/>(define (factorial n)<br/>
(let ((product 1)<br/>
(counter 1))<br/>
(define (iter)<br/>
(if (> counter n)<br/>
product<br/>
(begin (set! product (* counter product))<br/>
(set! counter (+ counter 1))<br/>
(iter))))<br/>
(iter)))<br/></tt></p><p/><p>
<a name="%_idx_3020" id="%_idx_3020"/><a name="%_idx_3022" id="%_idx_3022"/>Isso não altera os resultados produzidos pelo programa, mas introduz uma armadilha sutil. Como decidimos a ordem das atribuições? Por acaso, o programa está correto conforme escrito. Mas escrever as atribuições na ordem oposta</p><p/><p><tt>(set! counter (+ counter 1))<br/>
(set! product (* counter product))<br/></tt></p><p/><p>teria produzido um resultado diferente e incorreto. Em geral, a programação com atribuição nos obriga a considerar cuidadosamente as ordens relativas das atribuições para garantir que cada instrução usaria a versão correta das variáveis que foram alteradas. Esse problema simplesmente não surge em programas funcionais.<a name="call_footnote_Temp_339" href="#footnote_Temp_339" id="call_footnote_Temp_339"><sup><small>11</small></sup></a> A complexidade de programas imperativos se torna ainda pior se considerarmos aplicativos nos quais vários processos são executados concorrentemente. Voltaremos a isso na seção <a href="book-Z-H-23.html#%_sec_3.4">3.4</a>. Primeiro, no entanto, abordaremos a questão de fornecer um modelo computacional para expressões que envolvam atribuição e exploraremos o uso de objetos com estado local na criação de simulações.</p><p>
</p><p><a name="%_thm_3.7" id="%_thm_3.7"/>
<b>Exercício 3.7.</b> <a name="%_idx_3026" id="%_idx_3026"/>Considere os objetos de conta bancária criados por <tt>make-account</tt>, com a modificação de senha descrita no exercício <a href="#%_thm_3.3">3.3</a>. Suponha que nosso sistema bancário exija a capacidade de criar contas conjuntas. Defina um procedimento <a name="%_idx_3028" id="%_idx_3028"/><tt>make-joint</tt> que realiza isso. <tt>Make-joint</tt> deve receber três argumentos. A primeira é uma conta protegida por senha. O segundo argumento deve corresponder à senha com a qual a conta foi definida para que a operação <tt>make-joint</tt> continue. O terceiro argumento é uma nova senha. <tt>Make-joint</tt> é para criar um acesso adicional à conta original usando a nova senha. Por exemplo, se <tt>peter-acc</tt> for uma conta bancária com a senha <tt>open-sesame</tt>, então</p><p>
</p><p/><p><tt>(define paul-acc<br/>
(make-joint peter-acc 'open-sesame 'rosebud))<br/></tt></p><p/><p>permitirá que você faça transações no <tt>peter-acc</tt> usando o nome <tt>paul-acc</tt> e a senha <tt>rosebud</tt>. Você pode modificar sua solução para exercitar <a href="#%_thm_3.3">3.3</a> para acomodar esse novo recurso.</p><p/><p>
</p><p><a name="%_thm_3.8" id="%_thm_3.8"/>
<b>Exercício 3.8.</b> <a name="%_idx_3030" id="%_idx_3030"/><a name="%_idx_3032" id="%_idx_3032"/>Quando definimos o modelo de avaliação na seção <a href="book-Z-H-10.html#%_sec_1.1.3">1.1.3</a>, dissemos que o primeiro passo na avaliação de uma expressão é avaliar suas subexpressões. Mas nunca especificamos a ordem em que as subexpressões devem ser avaliadas (por exemplo, da esquerda para a direita ou da direita para a esquerda). Quando introduzimos a atribuição, a ordem na qual os argumentos de um procedimento são avaliados pode fazer a diferença no resultado. Defina um procedimento simples <tt>f</tt> para que avaliar <tt>(+ (f 0) (f 1))</tt> retorne 0 se os argumentos para <tt>+</tt> forem avaliados da esquerda para a direita, mas retornará 1 se os argumentos forem avaliados da direita para a esquerda.</p><p>
</p><p>
</p><p/><div class="smallprint"><hr/></div><p>
</p><div class="footnote"><p><a name="footnote_Temp_321" href="#call_footnote_Temp_321" id="footnote_Temp_321"><sup><small>1</small></sup></a> Na verdade, isso não é bem verdade. Uma exceção foi o gerador de números aleatórios <a name="%_idx_2852" id="%_idx_2852"/><a name="%_idx_2854" id="%_idx_2854"/>na seção <a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>. Outra exceção envolveu as tabelas de <a name="%_idx_2856" id="%_idx_2856"/>operação/tipo que introduzimos na seção <a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>, em que os valores de duas chamadas para <tt>get</tt> com os mesmos argumentos dependiam de chamadas intervenientes <tt>put</tt>. Por outro lado, até introduzirmos a atribuição, não temos como criar esses procedimentos por nós mesmos.</p><p><a name="footnote_Temp_322" href="#call_footnote_Temp_322" id="footnote_Temp_322"><sup><small>2</small></sup></a> <a name="%_idx_2864" id="%_idx_2864"/><a name="%_idx_2866" id="%_idx_2866"/>O valor de uma expressão <tt>set!</tt> depende da implementação. <tt>Set!</tt> deve ser usado apenas para seu efeito, não para seu valor.</p><p>
<a name="%_idx_2868" id="%_idx_2868"/><a name="%_idx_2870" id="%_idx_2870"/><a name="%_idx_2872" id="%_idx_2872"/>O nome <tt>set!</tt> reflete uma convenção de nomenclatura usada no Scheme: As operações que alteram os valores das variáveis (ou que alteram as estruturas de dados, como veremos na seção <a href="book-Z-H-22.html#%_sec_3.3">3.3</a>) são fornecidas nomes que terminam com um ponto de exclamação. Isso é semelhante à convenção de designar predicados por nomes que terminam com um ponto de interrogação.</p><p><a name="footnote_Temp_323" href="#call_footnote_Temp_323" id="footnote_Temp_323"><sup><small>3</small></sup></a> Já usamos <a name="%_idx_2878" id="%_idx_2878"/><tt>begin</tt> implicitamente em nossos programas, pois em Scheme o corpo de um procedimento pode ser uma sequência de expressões. Além disso, a parte <<em>consequent</em>> de cada cláusula em uma expressão <a name="%_idx_2880" id="%_idx_2880"/><a name="%_idx_2882" id="%_idx_2882"/><tt>cond</tt> pode ser uma sequência de expressões em vez de uma única expressão.</p><p><a name="footnote_Temp_324" href="#call_footnote_Temp_324" id="footnote_Temp_324"><sup><small>4</small></sup></a> No jargão da linguagem de programação, a variável <tt>balance</tt> é considerada <a name="%_idx_2886" id="%_idx_2886"/><a name="%_idx_2888" id="%_idx_2888"/><em>encapsulado</em> dentro do procedimento <tt>new-withdraw</tt>. O encapsulamento reflete o princípio geral de projeto do sistema conhecido como <a name="%_idx_2890" id="%_idx_2890"/><a name="%_idx_2892" id="%_idx_2892"/><em>princípio oculto</em>: Pode-se tornar um sistema mais modular e robusto, protegendo partes do sistema umas das outras; isto é, fornecendo acesso às informações apenas às partes do sistema que possuem uma “necessidade de saber”.</p><p><a name="footnote_Temp_325" href="#call_footnote_Temp_325" id="footnote_Temp_325"><sup><small>5</small></sup></a> Ao contrário de <tt>new-withdraw</tt> acima, não precisamos usar <tt>let</tt> tornar <tt>balance</tt> uma variável local, pois os parâmetros formais já são locais. Isso ficará mais claro após a discussão do modelo de avaliação do ambiental na seção <a href="book-Z-H-21.html#%_sec_3.2">3.2</a>. (Veja também o exercício <a href="book-Z-H-21.html#%_thm_3.10">3.10</a>).</p><p><a name="footnote_Temp_330" href="#call_footnote_Temp_330" id="footnote_Temp_330"><sup><small>6</small></sup></a> Uma maneira comum de implementar <tt>rand-update</tt> é usar a regra que <em>x</em>é atualizado para <em>a</em><em>x</em> + <em>b</em> módulo <em>m</em>, em que <em>a</em>, <em>b</em> e <em>m</em> são números inteiros escolhidos adequadamente. O capítulo 3 de <a name="%_idx_2924" id="%_idx_2924"/>Knuth 1981 inclui uma extensa discussão de técnicas para gerar sequências de números aleatórios e estabelecer suas propriedades estatísticas. Observe que o procedimento <tt>rand-update</tt> calcula uma função matemática: dada a mesma entrada duas vezes, produz a mesma saída. Portanto, a sequência numérica produzida por <tt>rand-update</tt> certamente não é “aleatória”, se por “aleatória” insistimos que cada número na sequência não está relacionado ao número anterior. A relação entre “aleatoriedade real” e as chamadas sequências pseudo-aleatórias <a name="%_idx_2926" id="%_idx_2926"/><em>pseudo-aleatórias</em>, produzidas por cálculos bem determinados e com propriedades estatísticas adequadas, é uma questão complexa que envolve questões difíceis em matemática e filosofia. <a name="%_idx_2928" id="%_idx_2928"/> <a name="%_idx_2930" id="%_idx_2930"/><a name="%_idx_2932" id="%_idx_2932"/>Kolmogorov, Solomonoff e Chaitin fizeram grandes progressos no esclarecimento dessas questões; uma discussão pode ser encontrada em Chaitin 1975.</p><p><a name="footnote_Temp_331" href="#call_footnote_Temp_331" id="footnote_Temp_331"><sup><small>7</small></sup></a> Este teorema é devido a E. <a name="%_idx_2942" id="%_idx_2942"/>Cesàro. Veja a seção 4.5.2 de <a name="%_idx_2944" id="%_idx_2944"/>Knuth 1981 para uma discussão e uma prova.</p><p><a name="footnote_Temp_333" href="#call_footnote_Temp_333" id="footnote_Temp_333"><sup><small>8</small></sup></a> <a name="%_idx_2964" id="%_idx_2964"/>O MIT Scheme fornece esse procedimento. Se <a name="%_idx_2966" id="%_idx_2966"/><a name="%_idx_2968" id="%_idx_2968"/><tt>random</tt> receber um número inteiro exato (como na seção <a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>), ele retornará um número inteiro exato, mas se for dado de um valor de um número decimal (como neste exercício), ele retorna um valor decimal.</p><p><a name="footnote_Temp_335" href="#call_footnote_Temp_335" id="footnote_Temp_335"><sup><small>9</small></sup></a> Não substituímos a ocorrência de <tt>balance</tt> na expressão <tt>set!</tt>, pois <<em>name</em>> em <tt>set!</tt> não é avaliado. Se o substituíssemos, obteríamos <tt>(set! 25 (- 25 amount))</tt>, o que não faz sentido.</p><p><a name="footnote_Temp_337" href="#call_footnote_Temp_337" id="footnote_Temp_337"><sup><small>10</small></sup></a> O fenômeno de um único objeto computacional acessado por mais de um nome é conhecido como <a name="%_idx_2998" id="%_idx_2998"/><em>aliasing</em>. A situação da conta bancária conjunta ilustra um exemplo muito simples de um alias. Na seção <a href="book-Z-H-22.html#%_sec_3.3">3.3</a>, veremos exemplos muito mais complexos, como estruturas de dados compostas “distintas” que compartilham partes. Os erros podem ocorrer em nossos programas se <a name="%_idx_3000" id="%_idx_3000"/><a name="%_idx_3002" id="%_idx_3002"/><a name="%_idx_3004" id="%_idx_3004"/>esquecemos que uma alteração em um objeto também pode, como um “efeito colateral”, alterar um objeto “diferente”, pois os dois objetos “diferentes” são, na verdade, um único objeto que aparece sob aliases diferentes. Esses chamados <em>erros de efeito colateral</em> são tão difíceis de localizar e analisar que algumas pessoas propuseram que as linguagens de programação fossem projetadas de forma a não permitir efeitos colaterais ou aliasing <a name="%_idx_3006" id="%_idx_3006"/><a name="%_idx_3008" id="%_idx_3008"/><a name="%_idx_3010" id="%_idx_3010"/><a name="%_idx_3012" id="%_idx_3012"/>(Lampson et al. 1981; Morris, Schmidt, e Wadler 1980).</p><p><a name="footnote_Temp_339" href="#call_footnote_Temp_339" id="footnote_Temp_339"><sup><small>11</small></sup></a> Em vista disso, é irônico que a programação introdutória seja mais frequentemente ensinada em um estilo altamente imperativo. Pode ser um vestígio de uma crença, comum nas décadas de 1960 e 1970, de que programas que chamam procedimentos devem ser inerentemente menos eficientes do que programas que realizam atribuições. (Steele (1977) <a name="%_idx_3024" id="%_idx_3024"/>desmascara esse argumento). Como alternativa, isso pode refletir uma visão de que a atribuição passo a passo é mais fácil para os iniciantes visualizarem do que a chamada de procedimento. Qualquer que seja o motivo, geralmente sobrecarrega os programadores iniciantes como preocupações “devo definir essa variável antes ou depois dessa” que podem complicar a programação e obscurecer as ideias importantes.</p></div>
</body>
</html>