-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-13.html
50 lines (35 loc) · 12.8 KB
/
book-Z-H-13.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
<?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="%_chap_2" id="%_chap_2"/>
<h1 class="chapter">
<div class="chapterheading"><a href="book-Z-H-4.html#%_toc_%_chap_2">Capítulo 2</a></div></h1><p>
<a href="book-Z-H-4.html#%_toc_%_chap_2">Construindo abstrações com dados</a></p><p>
</p><p>
</p><div align="right">
<table width="60%"><tr><td>
<span class="epigraph">
<p>Chegamos agora ao passo decisivo da abstração matemática: esquecemos o que os símbolos representam. <tt>…</tt>[O matemático] não precisa ficar ocioso; há muitas operações que ele pode realizar com esses símbolos, sem precisar olhar para objetos que eles representam.</p><p>
<a name="%_idx_1254" id="%_idx_1254"/>Hermann Weyl, <em>O modo de pensar matemático</em></p><p>
</p></span>
</td></tr></table></div>
<p/><p>
<a name="%_idx_1256" id="%_idx_1256"/><a name="%_idx_1258" id="%_idx_1258"/>Concentramos no capítulo 1 em processos computacionais e no papel dos procedimentos no projeto de programas. Vimos como usar dados primitivos (números) e operações primitivas (operações aritméticas), como combinar procedimentos para formar procedimentos compostos por meio de composição, condicionais e uso de parâmetros e como abstrair procedimentos usando <tt>define</tt>. Vimos que um procedimento pode ser considerado como um padrão para a evolução local de um processo e classificamos, raciocinamos e executamos análises algorítmicas simples de alguns padrões comuns de processos, conforme incorporados nos procedimentos. Também vimos que procedimentos de ordem superior aumentam o poder de nossa linguagem, permitindo-nos manipular e, portanto, raciocinar em termos de métodos gerais de computação. Isso é a maior parte da essência da programação.</p><p>Neste capítulo, examinaremos dados mais complexos. Todos os procedimentos do capítulo 1 operam com dados numéricos simples, e dados simples não são suficientes para muitos dos problemas que desejamos resolver usando a computação. Os programas são tipicamente projetados para modelar fenômenos complexos e, na maioria das vezes, é preciso construir objetos computacionais que tenham várias partes para modelar fenômenos do mundo real que tenham vários aspectos. Assim, enquanto nosso foco no capítulo 1 estava na construção de abstrações combinando procedimentos para formar procedimentos compostos, passamos neste capítulo para outro aspecto principal de qualquer linguagem de programação: os meios que ele fornece para criar abstrações combinando objetos de dados para formar <em>dados compostos</em>.</p><p>Por que queremos dados compostos em uma linguagem de programação? Pelas mesmas razões que queremos procedimentos compostos: elevar o nível conceitual no qual podemos projetar nossos programas, aumentar a modularidade de nossos projetos e aprimorar o poder expressivo de nossa linguagem. Assim como a capacidade de definir procedimentos nos permite lidar com processos em um nível conceitual mais alto do que o das operações primitivas da linguagem, a capacidade de construir objetos de dados compostos nos permite lidar com os dados em um nível conceitual mais alto do que o do objetos de dados primitivos da linguagem.</p><p>
<a name="%_idx_1260" id="%_idx_1260"/>Considere a tarefa de projetar um sistema para executar aritmética com números racionais. Poderíamos imaginar uma operação <tt>add-rat</tt> que pega dois números racionais e produz sua soma. Em termos de dados simples, um número racional pode ser considerado como dois números inteiros: um numerador e um denominador. Assim, poderíamos projetar um programa no qual cada número racional seria representado por dois números inteiros (um numerador e um denominador) e onde <tt>add-rat</tt> seria implementado por dois procedimentos (um produzindo o numerador do soma e uma que produz o denominador). Mas isso seria estranho, pois precisaríamos acompanhar explicitamente quais numeradores correspondiam a quais denominadores. Em um sistema destinado a executar muitas operações com muitos números racionais, esses detalhes da contabilidade atrapalhariam substancialmente os programas, sem dizer o que fariam em nossas mentes. Seria muito melhor se pudéssemos “colar” um numerador e denominador para formar um par – um <em>objeto de dados composto</em> – que nossos programas pudessem manipular de uma maneira que fosse consistente com o número racional como uma única unidade conceitual.</p><p>O uso de dados compostos também nos permite aumentar a modularidade de nossos programas. Se podemos manipular números racionais diretamente como objetos por si mesmos, podemos separar a parte do nosso programa que lida com números racionais per se dos detalhes de como os números racionais podem ser representados como pares de números inteiros. A técnica geral de isolar as partes de um programa que lidam com a forma como os objetos de dados são representados das partes de um programa que lidam com a forma como os objetos de dados são usados é uma poderosa metodologia de projeto chamada <a name="%_idx_1262" id="%_idx_1262"/><em>abstração de dados</em>. Veremos como a abstração de dados torna os programas muito mais fáceis de projetar, manter e modificar.</p><p>O uso de dados compostos leva a um aumento real no poder expressivo da nossa linguagem de programação. Considere a ideia de formar uma “combinação linear” <em>a</em> <em>x</em> + <em>b</em><em>y</em>. Podemos escrever um procedimento que aceite <em>a</em>, <em>b</em>, <em>x</em> e <em>y</em> como argumentos e retorne o valor de <em>a</em><em>x</em> + <em>b</em><em>e</em>. Isso não apresenta dificuldade se os argumentos forem números, pois podemos definir rapidamente o procedimento</p><p>
</p><p/><p><tt>(define (linear-combination a b x y) <br/>
(+ (* a x) (* b y)))<br/></tt></p><p/><p>Mas suponha que não estamos preocupados apenas com números. Suponha que gostaríamos de expressar, em termos processuais, a ideia de que se pode formar combinações lineares sempre que adição e multiplicação forem definidas – para números racionais, números complexos ou polinômios. Poderíamos expressar isso como um procedimento na forma</p><p>
</p><p/><p><tt>(define (linear-combination a b x y) <br/>
(add (mul a x) (mul b y))) <br/></tt></p><p/><p>onde <tt>add</tt> e <tt>mul</tt> não são os procedimentos primitivos <tt>+</tt> e <tt>*</tt>, mas objetos bastante mais complexos que executarão o procedimento das apropriadas operações para quaisquer tipos de dados que transmitimos como argumentos <tt>a</tt>, <tt>b</tt>, <tt>x</tt> e <tt>y</tt>. O ponto principal é que <tt>linear-combination</tt> somente precisa saber sobre <tt>a</tt>, <tt>b</tt>, <tt>x</tt>, e <tt>y</tt> é que os procedimentos <tt>add</tt> e <tt>mul</tt> executam as manipulações apropriadas. Do ponto de vista do procedimento de <tt>linear-combination</tt>, é irrelevante o que <tt>a</tt>, <tt>b</tt>, <tt>x</tt> e <tt>y</tt> são e ainda mais irrelevantes como eles podem ser representados em termos de dados mais primitivos. Este mesmo exemplo mostra por que é importante que nossa linguagem de programação forneça a capacidade de manipular objetos compostos diretamente: sem isso, não há como um procedimento como <tt>linear-combination</tt> transmitir seus argumentos para <tt>add</tt> e <tt>mul</tt> sem precisar conhecer sua estrutura detalhada.<a name="call_footnote_Temp_131" href="#footnote_Temp_131" id="call_footnote_Temp_131"><sup><small>1</small></sup></a> Começamos este capítulo implementando o sistema aritmético de número racional mencionado acima. Isso formará o pano de fundo para nossa discussão sobre dados compostos e abstração de dados. Assim como nos procedimentos compostos, o principal problema a ser abordado é o da abstração como uma técnica para lidar com a complexidade, e veremos como a abstração de dados nos permite erguer <a name="%_idx_1264" id="%_idx_1264"/><em>barreiras de abstração adequadas</em> entre diferentes partes de um programa.</p><p>Veremos que a chave para formar dados compostos é que uma linguagem de programação forneça algum tipo de “cola” para que os objetos de dados possam ser combinados para formar objetos de dados mais complexos. Existem muitos tipos possíveis de cola. De fato, descobriremos como formar dados compostos usando nenhuma operação especial de “dados”, apenas procedimentos. Isso obscurecerá ainda mais a distinção entre “procedimento” e “dados”, que já tornava se tênue no final do capítulo 1. Também exploraremos algumas técnicas convencionais para representar sequências e árvores. Uma ideia-chave ao lidar com dados compostos é a noção de <a name="%_idx_1266" id="%_idx_1266"/><em>fechamento</em>- de que a cola que usamos para combinar objetos de dados deve permitir combinar não apenas objetos de dados primitivos, mas objetos de dados compostos como bem. Outra ideia-chave é que objetos de dados compostos podem servir como <a name="%_idx_1268" id="%_idx_1268"/><em>interfaces convencionais</em> para combinar módulos de programa de maneiras combinadas. Ilustramos algumas dessas ideias, apresentando uma linguagem gráfica simples que explora o fechamento.</p><p>Incrementamos o poder representacional de nossa linguagem, introduzindo <a name="%_idx_1270" id="%_idx_1270"/><a name="%_idx_1272" id="%_idx_1272"/><em>expressões simbólicas</em> – dados cujas partes elementares podem ser símbolos arbitrários, e não apenas números. Exploramos várias alternativas para representar conjuntos de objetos. Descobriremos que, assim como uma determinada função numérica pode ser calculada por muitos processos computacionais diferentes, existem muitas maneiras pelas quais uma determinada estrutura de dados pode ser representada em termos de objetos mais simples, e a escolha da representação pode ter um impacto significativo nos requisitos de tempo e espaço de processos que manipulam os dados. Investigaremos essas ideias no contexto da diferenciação simbólica, da representação de conjuntos e da codificação de informações.</p><p>Em seguida, abordaremos o problema de trabalhar com dados que podem ser representados de maneira diferente por diferentes partes de um programa. Isso leva à necessidade de implementar <a name="%_idx_1274" id="%_idx_1274"/><a name="%_idx_1276" id="%_idx_1276"/><em>operações genéricas</em>, que devem lidar com muitos tipos diferentes de dados. Manter a modularidade na presença de operações genéricas requer barreiras de abstração mais poderosas do que podem ser erguidas apenas com a abstração de dados simples. Em particular, introduzimos a <em>programação orientada a dados</em> como uma técnica que permite que representações de dados individuais sejam projetadas isoladamente e depois combinadas <a name="%_idx_1278" id="%_idx_1278"/><em>aditivamente</em> (ou seja, sem modificação). Para ilustrar o poder dessa abordagem ao projeto do sistema, encerramos o capítulo aplicando o que aprendemos à implementação de um pacote para executar aritmética simbólica em polinômios, nos quais os coeficientes dos polinômios podem ser números inteiros, números racionais, números complexos e até outros polinômios.</p><p>
</p><p/><div class="smallprint"><hr/></div><p>
</p><div class="footnote"><p><a name="footnote_Temp_131" href="#call_footnote_Temp_131" id="footnote_Temp_131"><sup><small>1</small></sup></a> A capacidade de manipular procedimentos diretamente fornece um aumento análogo no poder expressivo de uma linguagem de programação. Por exemplo, na seção <a href="book-Z-H-12.html#%_sec_1.3.1">1.3.1</a>, introduzimos o procedimento <tt>sum</tt>, que usa o procedimento <tt>term</tt> como argumento e calcula a soma dos valores do <tt>term</tt> em algum intervalo especificado. Para definir <tt>sum</tt>, é crucial que possamos falar de um procedimento como o <tt>term</tt> como uma entidade por si só, sem levar em consideração como <tt>term</tt> pode ser expresso com operações mais primitivas. De fato, se não tivéssemos a noção de “um procedimento”, é duvidoso que sequer pensássemos na possibilidade de definir uma operação como <tt>sum</tt>. Além disso, no que diz respeito à realização da soma, os detalhes de como o <tt>term</tt> pode ser construído a partir de operações mais primitivas são irrelevantes.</p></div>
</body>
</html>