1.1Os Elementos da Programação

Uma linguagem de programação poderosa é mais do que apenas um meio para instruir um computador a realizar tarefas. A linguagem também serve como uma estrutura dentro da qual organizamos nossas ideias sobre processos. Assim, ao descrever uma linguagem, devemos prestar atenção especial aos meios que a linguagem fornece para combinar ideias simples e formar ideias mais complexas. Toda linguagem poderosa possui três mecanismos para realizar isso:

• expressões primitivas, que representam as entidades mais simples com as quais a linguagem se preocupa,
• meios de combinação, pelos quais elementos compostos são construídos a partir de elementos mais simples, e
• meios de abstração, pelos quais elementos compostos podem ser nomeados e manipulados como unidades.

Na programação, lidamos com dois tipos de elementos: procedimentos e dados. (Mais tarde, descobriremos que eles não são tão distintos.) Informalmente, dados são "coisas" que queremos manipular, e procedimentos são descrições das regras para manipular os dados. Assim, qualquer linguagem de programação poderosa deve ser capaz de descrever dados primitivos e procedimentos primitivos e deve ter métodos para combinar e abstrair procedimentos e dados.

Neste capítulo, lidaremos apenas com dados numéricos simples para que possamos nos concentrar nas regras para construir procedimentos.⁴ Nos capítulos posteriores, veremos que essas mesmas regras nos permitem construir procedimentos para manipular dados compostos também.

1.1.1Expressões

Uma maneira fácil de começar a programar é examinar algumas interações típicas com um interpretador para o dialeto Scheme de Lisp. Imagine que você está sentado em um terminal de computador. Você digita uma expressão, e o interpretador responde exibindo o resultado da avaliação dessa expressão.

Um tipo de expressão primitiva que você pode digitar é um número. (Mais precisamente, a expressão que você digita consiste nos numerais que representam o número na base 10.) Se você apresentar ao Lisp um número:

486
      

o interpretador responderá imprimindo:⁵

486
      

Expressões que representam números podem ser combinadas com uma expressão que representa um procedimento primitivo (como + ou *) para formar uma expressão composta que representa a aplicação do procedimento a esses números. Por exemplo:

(+ 137 349)
486

(- 1000 334)
666

(* 5 99)
495

(/ 10 5)
2

(+ 2.7 10)
12.7        
      

Expressões como essas, formadas delimitando uma lista de expressões entre parênteses para denotar a aplicação de um procedimento, são chamadas de combinações. O elemento mais à esquerda na lista é chamado de operador, e os outros elementos são chamados de operandos. O valor de uma combinação é obtido aplicando o procedimento especificado pelo operador aos argumentos que são os valores dos operandos.

A convenção de colocar o operador à esquerda dos operandos é conhecida como notação prefixa, e pode ser um pouco confusa no início porque difere significativamente da convenção matemática usual. No entanto, a notação prefixa tem várias vantagens. Uma delas é que pode acomodar procedimentos que podem receber um número arbitrário de argumentos, como nos exemplos a seguir:

(+ 21 35 12 7)
75

(* 25 4 12)
1200
      

Não pode haver ambiguidade, porque o operador é sempre o elemento mais à esquerda e toda a combinação é delimitada pelos parênteses.

Uma segunda vantagem da notação prefixa é que ela se estende de maneira direta para permitir que combinações sejam aninhadas, ou seja, que tenham combinações cujos elementos são eles próprios combinações:

(+ (* 3 5) (- 10 6))
19        
      

Não há limite (em princípio) para a profundidade desse aninhamento e para a complexidade geral das expressões que o interpretador Lisp pode avaliar. Somos nós, humanos, que nos confundimos com expressões ainda relativamente simples, como:

(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))
      

que o interpretador avaliaria prontamente como 57. Podemos nos ajudar escrevendo essa expressão na forma:

(+ (* 3
(+ (* 2 4)
   (+ 3 5)))
(+ (- 10 7)
6))
      

seguindo uma convenção de formatação conhecida como pretty-printing, na qual cada combinação longa é escrita de forma que os operandos sejam alinhados verticalmente. Os recuos resultantes mostram claramente a estrutura da expressão.⁶

Mesmo com expressões complexas, o interpretador sempre opera no mesmo ciclo básico: ele lê uma expressão do terminal, avalia a expressão e imprime o resultado. Esse modo de operação é frequentemente expresso dizendo que o interpretador funciona em um loop de leitura-avaliação-impressão. Observe, em particular, que não é necessário instruir explicitamente o interpretador a imprimir o valor da expressão.⁷

1.1.2Nomes e o Ambiente

Um aspecto crítico de uma linguagem de programação é o meio que ela fornece para usar nomes para se referir a objetos computacionais. Dizemos que o nome identifica uma variável cujo valor é o objeto.

No dialeto Scheme de Lisp, nomeamos coisas com define. Digitando:

(define size 2)
      

o interpretador associa o valor 2 ao nome size.⁸ Uma vez que o nome size foi associado ao número 2, podemos nos referir ao valor 2 pelo nome:

size
2

(* 5 size)
10
      

Aqui estão mais exemplos do uso de define:

(define pi 3.14159)
(define radius 10)

(* pi (* radius radius))
314.159

(define circumference (* 2 pi radius))

circumference
62.8318
      

Define é o meio mais simples de abstração em nossa linguagem, pois nos permite usar nomes simples para nos referir aos resultados de operações compostas, como a circumference calculada acima. Em geral, objetos computacionais podem ter estruturas muito complexas, e seria extremamente inconveniente ter que lembrar e repetir seus detalhes cada vez que quisermos usá-los. De fato, programas complexos são construídos passo a passo, criando objetos computacionais de complexidade crescente. O interpretador torna essa construção passo a passo particularmente conveniente, pois as associações nome-objeto podem ser criadas incrementalmente em interações sucessivas. Esse recurso incentiva o desenvolvimento e teste incremental de programas e é em grande parte responsável pelo fato de que um programa Lisp geralmente consiste em um grande número de procedimentos relativamente simples.

Deve ficar claro que a possibilidade de associar valores a símbolos e recuperá-los posteriormente significa que o interpretador deve manter algum tipo de memória que acompanhe os pares nome-objeto. Essa memória é chamada de ambiente (mais precisamente, o ambiente global, pois veremos mais tarde que uma computação pode envolver vários ambientes diferentes).⁹

1.1.3Avaliando Combinações

Um de nossos objetivos neste capítulo é isolar questões sobre o pensamento procedural. Como um exemplo, vamos considerar que, ao avaliar combinações, o interpretador está seguindo um procedimento.

Para avaliar uma combinação, faça o seguinte:

1. Avalie as subexpressões da combinação.
2. Aplique o procedimento que é o valor da subexpressão mais à esquerda (o operador) aos argumentos que são os valores das outras subexpressões (os operandos).

Mesmo essa regra simples ilustra alguns pontos importantes sobre processos em geral. Primeiro, observe que o primeiro passo determina que, para realizar o processo de avaliação para uma combinação, devemos primeiro realizar o processo de avaliação em cada elemento da combinação. Assim, a regra de avaliação é recursiva por natureza; ou seja, ela inclui, como um de seus passos, a necessidade de invocar a própria regra.¹⁰

Observe como a ideia de recursão pode ser usada de forma sucinta para expressar o que, no caso de uma combinação profundamente aninhada, seria visto como um processo bastante complicado. Por exemplo, avaliar:

(* (+ 2 (* 4 6)) (+ 3 5 7))
      

exige que a regra de avaliação seja aplicada a quatro combinações diferentes. Podemos obter uma imagem desse processo representando a combinação na forma de uma árvore, como mostrado na Figura 1.1. Cada combinação é representada por um nó com ramos correspondentes ao operador e aos operandos da combinação saindo dele. Os nós terminais (ou seja, nós sem ramos saindo deles) representam operadores ou números. Visualizando a avaliação em termos da árvore, podemos imaginar que os valores dos operandos percolam para cima, começando nos nós terminais e depois se combinando em níveis cada vez mais altos. Em geral, veremos que a recursão é uma técnica muito poderosa para lidar com objetos hierárquicos, semelhantes a árvores. De fato, a forma "percolar valores para cima" da regra de avaliação é um exemplo de um tipo geral de processo conhecido como acumulação em árvore.

Em seguida, observe que a aplicação repetida do primeiro passo nos leva ao ponto onde precisamos avaliar, não combinações, mas expressões primitivas, como numerais, operadores embutidos ou outros nomes. Cuidamos dos casos primitivos estipulando que:

• os valores dos numerais são os números que eles nomeiam,
• os valores dos operadores embutidos são as sequências de instruções da máquina que realizam as operações correspondentes, e
• os valores de outros nomes são os objetos associados a esses nomes no ambiente.

Podemos considerar a segunda regra como um caso especial da terceira, estipulando que símbolos como + e * também estão incluídos no ambiente global e são associados às sequências de instruções da máquina que são seus "valores". O ponto chave a ser observado é o papel do ambiente na determinação do significado dos símbolos nas expressões. Em uma linguagem interativa como Lisp, não faz sentido falar do valor de uma expressão como (+ x 1) sem especificar qualquer informação sobre o ambiente que forneceria um significado para o símbolo x (ou mesmo para o símbolo +). Como veremos no Capítulo 3, a noção geral do ambiente como fornecedor de um contexto no qual a avaliação ocorre desempenhará um papel importante em nossa compreensão da execução de programas.

Observe que a regra de avaliação dada acima não lida com definições. Por exemplo, avaliar (define x 3) não aplica define a dois argumentos, um dos quais é o valor do símbolo x e o outro é 3, pois o propósito do define é precisamente associar x a um valor. (Ou seja, (define x 3) não é uma combinação.)

Tais exceções à regra geral de avaliação são chamadas de formas especiais. Define é o único exemplo de forma especial que vimos até agora, mas encontraremos outras em breve. Cada forma especial tem sua própria regra de avaliação. Os vários tipos de expressões (cada um com sua regra de avaliação associada) constituem a sintaxe da linguagem de programação. Em comparação com a maioria das outras linguagens de programação, Lisp tem uma sintaxe muito simples; ou seja, a regra de avaliação para expressões pode ser descrita por uma regra geral simples, juntamente com regras especializadas para um pequeno número de formas especiais.¹¹

1.1.4Procedimentos Compostos

Identificamos em Lisp alguns dos elementos que devem aparecer em qualquer linguagem de programação poderosa:

• Números e operações aritméticas são dados e procedimentos primitivos.
• O aninhamento de combinações fornece um meio de combinar operações.
• Definições que associam nomes a valores fornecem um meio limitado de abstração.

Agora aprenderemos sobre definições de procedimentos, uma técnica de abstração muito mais poderosa pela qual uma operação composta pode receber um nome e ser referida como uma unidade.

Começamos examinando como expressar a ideia de "quadrado". Poderíamos dizer: "Para elevar algo ao quadrado, multiplique-o por si mesmo." Isso é expresso em nossa linguagem como:

(define (square x) (* x x))
      

Podemos entender isso da seguinte maneira:

(define  (square          x)    (*         x      x))
  |        |              |      |         |      |
 Para ao quadrado elevar algo, multiplique-o por si mesmo.
      

Temos aqui um procedimento composto, que recebeu o nome square. O procedimento representa a operação de multiplicar algo por si mesmo. A coisa a ser multiplicada recebe um nome local, x, que desempenha o mesmo papel que um pronome desempenha na linguagem natural. Avaliar a definição cria esse procedimento composto e o associa ao nome square.¹²

A forma geral de uma definição de procedimento é:

(define (⟨name⟩ ⟨formal parameters⟩) ⟨body⟩)
      

O ⟨name⟩ é um símbolo a ser associado à definição do procedimento no ambiente.¹³ Os ⟨formal parameters⟩ são os nomes usados dentro do corpo do procedimento para se referir aos argumentos correspondentes do procedimento. O ⟨body⟩ é uma expressão que produzirá o valor da aplicação do procedimento quando os parâmetros formais forem substituídos pelos argumentos reais aos quais o procedimento é aplicado.¹⁴ O ⟨name⟩ e os ⟨formal parameters⟩ são agrupados entre parênteses, assim como seriam em uma chamada real ao procedimento que está sendo definido.

Após definir square, podemos agora usá-lo:

(square 21)
441

(square (+ 2 5))
49

(square (square 3))
81
      

Também podemos usar square como um bloco de construção na definição de outros procedimentos. Por exemplo, $x^2+y^2$ pode ser expresso como:

(+ (square x) (square y))
      

Podemos facilmente definir um procedimento sum-of-squares que, dados quaisquer dois números como argumentos, produz a soma de seus quadrados:

(define (sum-of-squares x y)
(+ (square x) (square y)))

(sum-of-squares 3 4)
25
      

Agora podemos usar sum-of-squares como um bloco de construção na construção de outros procedimentos:

(define (f a)
(sum-of-squares (+ a 1) (* a 2)))

(f 5)
136
      

Procedimentos compostos são usados exatamente da mesma maneira que procedimentos primitivos. De fato, não se pode dizer, olhando para a definição de sum-of-squares dada acima, se square foi embutido no interpretador, como + e *, ou definido como um procedimento composto.

1.1.5O Modelo de Substituição para Aplicação de Procedimentos

Para avaliar uma combinação cujo operador nomeia um procedimento composto, o interpretador segue um processo muito semelhante ao das combinações cujos operadores nomeiam procedimentos primitivos, que descrevemos em 1.1.3. Ou seja, o interpretador avalia os elementos da combinação e aplica o procedimento (que é o valor do operador da combinação) aos argumentos (que são os valores dos operandos da combinação).

Podemos assumir que o mecanismo para aplicar procedimentos primitivos a argumentos é embutido no interpretador. Para procedimentos compostos, o processo de aplicação é o seguinte:

Para aplicar um procedimento composto a argumentos, avalie o corpo do procedimento com cada parâmetro formal substituído pelo argumento correspondente.

Para ilustrar esse processo, vamos avaliar a combinação:

(f 5)
      

onde f é o procedimento definido em 1.1.4. Começamos recuperando o corpo de f:

(sum-of-squares (+ a 1) (* a 2))
      

Então substituímos o parâmetro formal a pelo argumento 5:

(sum-of-squares (+ 5 1) (* 5 2))
      

Assim, o problema se reduz à avaliação de uma combinação com dois operandos e um operador sum-of-squares. Avaliar essa combinação envolve três subproblemas. Devemos avaliar o operador para obter o procedimento a ser aplicado e avaliar os operandos para obter os argumentos. Agora (+ 5 1) produz 6 e (* 5 2) produz 10, então devemos aplicar o procedimento sum-of-squares a 6 e 10. Esses valores são substituídos pelos parâmetros formais x e y no corpo de sum-of-squares, reduzindo a expressão a:

(+ (square 6) (square 10))
      

Se usarmos a definição de square, isso se reduz a:

(+ (* 6 6) (* 10 10))
      

que se reduz por multiplicação a:

(+ 36 100)
      

e finalmente a:

136
      

O processo que acabamos de descrever é chamado de modelo de substituição para aplicação de procedimentos. Ele pode ser tomado como um modelo que determina o "significado" da aplicação de procedimentos, na medida em que os procedimentos neste capítulo estão em questão. No entanto, há dois pontos que devem ser enfatizados:

• O propósito da substituição é nos ajudar a pensar sobre a aplicação de procedimentos, não para fornecer uma descrição de como o interpretador realmente funciona. Interpretadores típicos não avaliam aplicações de procedimentos manipulando o texto de um procedimento para substituir valores pelos parâmetros formais. Na prática, a "substituição" é realizada usando um ambiente local para os parâmetros formais. Discutiremos isso mais detalhadamente no Capítulo 3 e Capítulo 4 quando examinarmos a implementação de um interpretador em detalhes.
• Ao longo deste livro, apresentaremos uma sequência de modelos cada vez mais elaborados de como os interpretadores funcionam, culminando com uma implementação completa de um interpretador e compilador no Capítulo 5. O modelo de substituição é apenas o primeiro desses modelos—uma maneira de começar a pensar formalmente sobre o processo de avaliação. Em geral, ao modelar fenômenos em ciência e engenharia, começamos com modelos simplificados e incompletos. À medida que examinamos as coisas em maior detalhe, esses modelos simples se tornam inadequados e devem ser substituídos por modelos mais refinados. O modelo de substituição não é exceção. Em particular, quando abordarmos no Capítulo 3 o uso de procedimentos com "dados mutáveis", veremos que o modelo de substituição se quebra e deve ser substituído por um modelo mais complicado de aplicação de procedimentos.¹⁵

Ordem aplicativa versus ordem normal

De acordo com a descrição da avaliação dada em 1.1.3, o interpretador primeiro avalia o operador e os operandos e então aplica o procedimento resultante aos argumentos resultantes. Essa não é a única maneira de realizar a avaliação. Um modelo alternativo de avaliação não avaliaria os operandos até que seus valores fossem necessários. Em vez disso, ele primeiro substituiria as expressões dos operandos pelos parâmetros até obter uma expressão envolvendo apenas operadores primitivos e então realizaria a avaliação. Se usássemos esse método, a avaliação de (f 5) procederia de acordo com a sequência de expansões:

(sum-of-squares (+ 5 1) (* 5 2))

(+ (square (+ 5 1)) 
   (square (* 5 2)))

(+ (* (+ 5 1) (+ 5 1)) 
   (* (* 5 2) (* 5 2)))
      

seguido pelas reduções:

(+ (* 6 6) 
(* 10 10))

(+ 36 100)

136
      

Isso dá a mesma resposta que nosso modelo anterior de avaliação, mas o processo é diferente. Em particular, as avaliações de (+ 5 1) e (* 5 2) são realizadas duas vezes aqui, correspondendo à redução da expressão (* x x) com x substituído respectivamente por (+ 5 1) e (* 5 2).

Esse método alternativo de avaliação "expandir completamente e depois reduzir" é conhecido como avaliação em ordem normal, em contraste com o método "avaliar os argumentos e depois aplicar" que o interpretador realmente usa, que é chamado de avaliação em ordem aplicativa. Pode-se mostrar que, para aplicações de procedimentos que podem ser modeladas usando substituição (incluindo todos os procedimentos nos dois primeiros capítulos deste livro) e que produzem valores legítimos, a avaliação em ordem normal e em ordem aplicativa produzem o mesmo valor. (Veja Exercício 1.5 para um exemplo de um valor "ilegítimo" onde a avaliação em ordem normal e em ordem aplicativa não dão o mesmo resultado.)

Lisp usa avaliação em ordem aplicativa, em parte devido à eficiência adicional obtida ao evitar múltiplas avaliações de expressões como as ilustradas com (+ 5 1) e (* 5 2) acima e, mais significativamente, porque a avaliação em ordem normal se torna muito mais complicada de lidar quando saímos do domínio dos procedimentos que podem ser modelados por substituição. Por outro lado, a avaliação em ordem normal pode ser uma ferramenta extremamente valiosa, e investigaremos algumas de suas implicações no Capítulo 3 e Capítulo 4.¹⁶

1.1.6Expressões Condicionais e Predicados

O poder expressivo da classe de procedimentos que podemos definir neste ponto é muito limitado, porque não temos como fazer testes e realizar operações diferentes dependendo do resultado de um teste. Por exemplo, não podemos definir um procedimento que calcule o valor absoluto de um número testando se o número é positivo, negativo ou zero e tomando ações diferentes nos diferentes casos de acordo com a regra:

Esse constructo é chamado de análise de casos, e há uma forma especial em Lisp para notar tal análise de casos. Ela é chamada de cond (que significa "condicional") e é usada da seguinte forma:

(define (abs x)
(cond ((> x 0) x)
      ((= x 0) 0)
      ((< x 0) (- x))))
      

A forma geral de uma expressão condicional é:

(cond (⟨p₁⟩ ⟨e₁⟩)
      (⟨p₂⟩ ⟨e₂⟩)
      …
      (⟨pₙ⟩ ⟨eₙ⟩))  
      

consistindo do símbolo cond seguido por pares de expressões entre parênteses:

(⟨p⟩ ⟨e⟩)
      

chamados de cláusulas. A primeira expressão em cada par é um predicado—ou seja, uma expressão cujo valor é interpretado como verdadeiro ou falso.¹⁷

Expressões condicionais são avaliadas da seguinte forma. O predicado $⟨p_1⟩$ é avaliado primeiro. Se seu valor for falso, então $⟨p_2⟩$ é avaliado. Se o valor de $⟨p_2⟩$ também for falso, então $⟨p_3⟩$ é avaliado. Esse processo continua até que um predicado seja encontrado cujo valor seja verdadeiro, caso em que o interpretador retorna o valor da expressão consequente correspondente $⟨e⟩$ da cláusula como o valor da expressão condicional. Se nenhum dos $⟨p⟩$ for encontrado como verdadeiro, o valor do cond é indefinido.

A palavra predicado é usada para procedimentos que retornam verdadeiro ou falso, bem como para expressões que avaliam para verdadeiro ou falso. O procedimento de valor absoluto abs faz uso dos predicados primitivos >, < e =.¹⁸ Eles recebem dois números como argumentos e testam se o primeiro número é, respectivamente, maior que, menor que ou igual ao segundo número, retornando verdadeiro ou falso de acordo.

Outra maneira de escrever o procedimento de valor absoluto é:

(define (abs x)
(cond ((< x 0) (- x))
      (else x)))
      

que poderia ser expresso em português como "Se $x$ for menor que zero, retorne $-x$; caso contrário, retorne $x$." Else é um símbolo especial que pode ser usado no lugar do $⟨p⟩$ na cláusula final de um cond. Isso faz com que o cond retorne como seu valor o valor da expressão $⟨e⟩$ correspondente sempre que todas as cláusulas anteriores tiverem sido ignoradas. Na verdade, qualquer expressão que sempre avalie para um valor verdadeiro poderia ser usada como o $⟨p⟩$ aqui.

Aqui está mais uma maneira de escrever o procedimento de valor absoluto:

(define (abs x)
(if (< x 0)
    (- x)
    x))
      

Isso usa a forma especial if, um tipo restrito de condicional que pode ser usado quando há exatamente dois casos na análise de casos. A forma geral de uma expressão if é:

(if ⟨predicate⟩ ⟨consequent⟩ ⟨alternative⟩) 
      

Para avaliar uma expressão if, o interpretador começa avaliando a parte ⟨predicate⟩ da expressão. Se o ⟨predicate⟩ avaliar para um valor verdadeiro, o interpretador então avalia o ⟨consequent⟩ e retorna seu valor. Caso contrário, ele avalia o ⟨alternative⟩ e retorna seu valor.¹⁹

Além dos predicados primitivos como <, = e >, existem operações de composição lógica, que nos permitem construir predicados compostos. As três mais frequentemente usadas são:

• (and ⟨e₁⟩ … ⟨eₙ⟩)

  O interpretador avalia as expressões ⟨e⟩ uma a uma, em ordem da esquerda para a direita. Se qualquer ⟨e⟩ avaliar para falso, o valor da expressão and é falso, e o restante das ⟨e⟩ não é avaliado. Se todas as ⟨e⟩ avaliarem para valores verdadeiros, o valor da expressão and é o valor da última.

• (or ⟨e₁⟩ … ⟨eₙ⟩)

  O interpretador avalia as expressões ⟨e⟩ uma a uma, em ordem da esquerda para a direita. Se qualquer ⟨e⟩ avaliar para um valor verdadeiro, esse valor é retornado como o valor da expressão or, e o restante das ⟨e⟩ não é avaliado. Se todas as ⟨e⟩ avaliarem para falso, o valor da expressão or é falso.

• (not ⟨e⟩)

  O valor de uma expressão not é verdadeiro quando a expressão ⟨e⟩ avalia para falso, e falso caso contrário.

Observe que and e or são formas especiais, não procedimentos, porque as subexpressões não são necessariamente todas avaliadas. Not é um procedimento ordinário.

Como exemplo de como esses são usados, a condição de que um número $x$ esteja no intervalo $5<x<10$ pode ser expressa como:

(and (> x 5) (< x 10))
      

Como outro exemplo, podemos definir um predicado para testar se um número é maior ou igual a outro como:

(define (>= x y) 
(or (> x y) (= x y)))
      

ou alternativamente como:

(define (>= x y) 
(not (< x y)))
      

Exercício 1.1: Abaixo está uma sequência de expressões. Qual é o resultado impresso pelo interpretador em resposta a cada expressão? Suponha que a sequência seja avaliada na ordem em que é apresentada.

10
(+ 5 3 4)
(- 9 1)
(/ 6 2)
(+ (* 2 4) (- 4 6))
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
(= a b)
(if (and (> b a) (< b (* a b)))
    b
    a)
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
(+ 2 (if (> b a) b a))
(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))
        

Exercício 1.2: Traduza a seguinte expressão para a forma prefixa:

$$\frac{5+4+(2-(3-(6+\frac{4}{5})))}{3(6-2)(2-7)}.$$

Exercício 1.3: Defina um procedimento que receba três números como argumentos e retorne a soma dos quadrados dos dois maiores números.

Exercício 1.4: Observe que nosso modelo de avaliação permite combinações cujos operadores são expressões compostas. Use essa observação para descrever o comportamento do seguinte procedimento:

(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
        

Exercício 1.5: Ben Bitdiddle inventou um teste para determinar se o interpretador que ele enfrenta está usando avaliação em ordem aplicativa ou em ordem normal. Ele define os seguintes dois procedimentos:

(define (p) (p))

(define (test x y) 
  (if (= x 0) 
      0 
      y))
        

Então ele avalia a expressão:

(test 0 (p))
        

Que comportamento Ben observará com um interpretador que usa avaliação em ordem aplicativa? Que comportamento ele observará com um interpretador que usa avaliação em ordem normal? Explique sua resposta. (Suponha que a regra de avaliação para a forma especial if seja a mesma, independentemente de o interpretador estar usando ordem normal ou aplicativa: A expressão predicada é avaliada primeiro, e o resultado determina se a expressão consequente ou alternativa será avaliada.)

1.1.7Exemplo: Raízes Quadradas pelo Método de Newton

Procedimentos, como introduzidos acima, são muito semelhantes a funções matemáticas comuns. Eles especificam um valor que é determinado por um ou mais parâmetros. Mas há uma diferença importante entre funções matemáticas e procedimentos de computador. Procedimentos devem ser eficazes.

Como um exemplo, considere o problema de calcular raízes quadradas. Podemos definir a função raiz quadrada como:

Isso descreve uma função matemática perfeitamente legítima. Poderíamos usá-la para reconhecer se um número é a raiz quadrada de outro ou para derivar fatos sobre raízes quadradas em geral. Por outro lado, a definição não descreve um procedimento. De fato, ela quase não nos diz nada sobre como realmente encontrar a raiz quadrada de um número dado. Não ajudará reformular essa definição em pseudo-Lisp:

(define (sqrt x)
(the y (and (>= y 0) 
            (= (square y) x))))
      

Isso apenas levanta a questão.

O contraste entre função e procedimento é um reflexo da distinção geral entre descrever propriedades das coisas e descrever como fazer coisas, ou, como às vezes é referido, a distinção entre conhecimento declarativo e conhecimento imperativo. Em matemática, geralmente estamos preocupados com descrições declarativas (o que é), enquanto em ciência da computação geralmente estamos preocupados com descrições imperativas (como fazer).²⁰

Como se calcula raízes quadradas? A maneira mais comum é usar o método de Newton de aproximações sucessivas, que diz que sempre que temos um palpite $y$ para o valor da raiz quadrada de um número $x$, podemos realizar uma manipulação simples para obter um palpite melhor (mais próximo da raiz quadrada real) calculando a média de $y$ com $x/y$.²¹ Por exemplo, podemos calcular a raiz quadrada de 2 da seguinte forma. Suponha que nosso palpite inicial seja 1:

Palpite     Quociente      Média

1         (2/1)  = 2    ((2 + 1)/2)  = 1.5

1.5       (2/1.5)       ((1.3333 + 1.5)/2)
            = 1.3333      = 1.4167

1.4167    (2/1.4167)    ((1.4167 + 1.4118)/2) 
            = 1.4118      = 1.4142  

1.4142    ...           ...

Continuando esse processo, obtemos aproximações cada vez melhores para a raiz quadrada.

Agora vamos formalizar o processo em termos de procedimentos. Começamos com um valor para o radicando (o número cuja raiz quadrada estamos tentando calcular) e um valor para o palpite. Se o palpite for bom o suficiente para nossos propósitos, terminamos; caso contrário, devemos repetir o processo com um palpite melhorado. Escrevemos essa estratégia básica como um procedimento:

(define (sqrt-iter guess x)
(if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x) x)))
      

Um palpite é melhorado calculando a média dele com o quociente do radicando e o palpite antigo:

(define (improve guess x)
  (average guess (/ x guess)))
      

onde:

(define (average x y) 
(/ (+ x y) 2))
      

Também temos que dizer o que queremos dizer com "bom o suficiente". O seguinte servirá para ilustração, mas não é realmente um teste muito bom. (Veja Exercício 1.7.) A ideia é melhorar a resposta até que ela esteja próxima o suficiente para que seu quadrado difira do radicando por menos de uma tolerância predeterminada (aqui 0.001):²²

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))
      

Finalmente, precisamos de uma maneira de começar. Por exemplo, podemos sempre adivinhar que a raiz quadrada de qualquer número é 1:²³

(define (sqrt x)
  (sqrt-iter 1.0 x))
      

Se digitarmos essas definições para o interpretador, podemos usar sqrt como qualquer outro procedimento:

(sqrt 9)
3.00009155413138

(sqrt (+ 100 37))
        11.704699917758145

(sqrt (+ (sqrt 2) (sqrt 3)))
1.7739279023207892

(square (sqrt 1000))
1000.000369924366
      

O programa sqrt também ilustra que a linguagem procedural simples que introduzimos até agora é suficiente para escrever qualquer programa puramente numérico que se poderia escrever em, por exemplo, C ou Pascal. Isso pode parecer surpreendente, já que não incluímos em nossa linguagem nenhum constructo iterativo (de loop) que direcione o computador a fazer algo repetidamente. Sqrt-iter, por outro lado, demonstra como a iteração pode ser realizada sem nenhum constructo especial, além da capacidade comum de chamar um procedimento.²⁴

Exercício 1.6: Alyssa P. Hacker não entende por que if precisa ser fornecido como uma forma especial. “Por que não posso simplesmente defini-lo como um procedimento ordinário em termos de cond?”, ela pergunta. A amiga de Alyssa, Eva Lu Ator, afirma que isso pode ser feito, e ela define uma nova versão de if:

        

(define (new-if predicate 
          then-clause 
          else-clause)
  (cond (predicate then-clause)
        (else else-clause)))
        

Eva demonstra o programa para Alyssa:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0
        

Encantada, Alyssa usa new-if para reescrever o programa de raiz quadrada:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x) x)))
        

O que acontece quando Alyssa tenta usar isso para calcular raízes quadradas? Explique.

Exercício 1.7: O teste good-enough? usado no cálculo de raízes quadradas não será muito eficaz para encontrar as raízes quadradas de números muito pequenos. Além disso, em computadores reais, as operações aritméticas são quase sempre realizadas com precisão limitada. Isso torna nosso teste inadequado para números muito grandes. Explique essas afirmações, com exemplos mostrando como o teste falha para números pequenos e grandes. Uma estratégia alternativa para implementar good-enough? é observar como guess muda de uma iteração para a próxima e parar quando a mudança é uma fração muito pequena do palpite. Projete um procedimento de raiz quadrada que use esse tipo de teste final. Isso funciona melhor para números pequenos e grandes?

Exercício 1.8: O método de Newton para raízes cúbicas é baseado no fato de que, se $y$ é uma aproximação da raiz cúbica de $x$, então uma aproximação melhor é dada pelo valor $$\frac{x/y^2+2y}{3}.$$ Use essa fórmula para implementar um procedimento de raiz cúbica análogo ao procedimento de raiz quadrada. (Em 1.3.4 veremos como implementar o método de Newton em geral como uma abstração desses procedimentos de raiz quadrada e raiz cúbica.)

1.1.8Procedimentos como Abstrações de Caixa Preta

Sqrt é nosso primeiro exemplo de um processo definido por um conjunto de procedimentos mutuamente definidos. Observe que a definição de sqrt-iter é recursiva; isto é, o procedimento é definido em termos de si mesmo. A ideia de poder definir um procedimento em termos de si mesmo pode ser perturbadora; pode parecer pouco claro como tal definição “circular” poderia fazer sentido, muito menos especificar um processo bem definido a ser executado por um computador. Isso será abordado com mais cuidado em 1.2. Mas primeiro, vamos considerar alguns outros pontos importantes ilustrados pelo exemplo sqrt.

Observe que o problema de calcular raízes quadradas se divide naturalmente em vários subproblemas: como dizer se um palpite é bom o suficiente, como melhorar um palpite, e assim por diante. Cada uma dessas tarefas é realizada por um procedimento separado. O programa sqrt inteiro pode ser visto como um conjunto de procedimentos (mostrado em Figura 1.2) que espelha a decomposição do problema em subproblemas.

A importância dessa estratégia de decomposição não é simplesmente que se está dividindo o programa em partes. Afinal, poderíamos pegar qualquer programa grande e dividi-lo em partes—as primeiras dez linhas, as próximas dez linhas, as próximas dez linhas, e assim por diante. Em vez disso, é crucial que cada procedimento realize uma tarefa identificável que possa ser usada como um módulo na definição de outros procedimentos. Por exemplo, quando definimos o procedimento good-enough? em termos de square, somos capazes de considerar o procedimento square como uma “caixa preta”. Não estamos, nesse momento, preocupados com como o procedimento calcula seu resultado, apenas com o fato de que ele calcula o quadrado. Os detalhes de como o quadrado é calculado podem ser suprimidos, para serem considerados posteriormente. De fato, no que diz respeito ao procedimento good-enough?, square não é exatamente um procedimento, mas uma abstração de um procedimento, uma chamada abstração procedural. Nesse nível de abstração, qualquer procedimento que calcule o quadrado é igualmente bom.

Assim, considerando apenas os valores que retornam, os dois procedimentos a seguir para elevar um número ao quadrado devem ser indistinguíveis. Cada um recebe um argumento numérico e produz o quadrado desse número como valor.²⁵

(define (square x) (* x x))

(define (square x) 
  (exp (double (log x))))

(define (double x) (+ x x))
      

Portanto, uma definição de procedimento deve ser capaz de suprimir detalhes. Os usuários do procedimento podem não ter escrito o procedimento eles mesmos, mas podem tê-lo obtido de outro programador como uma caixa preta. Um usuário não precisa saber como o procedimento é implementado para usá-lo.

Nomes locais

Um detalhe da implementação de um procedimento que não deve importar para o usuário do procedimento é a escolha de nomes para os parâmetros formais do procedimento. Assim, os seguintes procedimentos não devem ser distinguíveis:

(define (square x) (* x x))

(define (square y) (* y y))
      

Este princípio—que o significado de um procedimento deve ser independente dos nomes dos parâmetros usados por seu autor—parece superficialmente evidente, mas suas consequências são profundas. A consequência mais simples é que os nomes dos parâmetros de um procedimento devem ser locais ao corpo do procedimento. Por exemplo, usamos square na definição de good-enough? em nosso procedimento de raiz quadrada:

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))
      

A intenção do autor de good-enough? é determinar se o quadrado do primeiro argumento está dentro de uma tolerância dada do segundo argumento. Vemos que o autor de good-enough? usou o nome guess para se referir ao primeiro argumento e x para se referir ao segundo argumento. O argumento de square é guess. Se o autor de square usou x (como acima) para se referir a esse argumento, vemos que o x em good-enough? deve ser um x diferente daquele em square. A execução do procedimento square não deve afetar o valor de x que é usado por good-enough?, porque esse valor de x pode ser necessário por good-enough? após square terminar de calcular.

Se os parâmetros não fossem locais aos corpos de seus respectivos procedimentos, então o parâmetro x em square poderia ser confundido com o parâmetro x em good-enough?, e o comportamento de good-enough? dependeria de qual versão de square usássemos. Assim, square não seria a caixa preta que desejamos.

Um parâmetro formal de um procedimento tem um papel muito especial na definição do procedimento, pois não importa qual nome o parâmetro formal tenha. Tal nome é chamado de variável ligada, e dizemos que a definição do procedimento liga seus parâmetros formais. O significado de uma definição de procedimento é inalterado se uma variável ligada for consistentemente renomeada em toda a definição.²⁶ Se uma variável não for ligada, dizemos que ela é livre. O conjunto de expressões para as quais uma ligação define um nome é chamado de escopo desse nome. Em uma definição de procedimento, as variáveis ligadas declaradas como parâmetros formais do procedimento têm o corpo do procedimento como seu escopo.

Na definição de good-enough? acima, guess e x são variáveis ligadas, mas <, -, abs e square são livres. O significado de good-enough? deve ser independente dos nomes que escolhemos para guess e x, desde que sejam distintos e diferentes de <, -, abs e square. (Se renomeássemos guess para abs, teríamos introduzido um bug ao capturar a variável abs. Ela teria mudado de livre para ligada.) O significado de good-enough? não é independente dos nomes de suas variáveis livres, no entanto. Certamente depende do fato (externo a essa definição) de que o símbolo abs nomeia um procedimento para calcular o valor absoluto de um número. Good-enough? calculará uma função diferente se substituirmos cos por abs em sua definição.

Definições internas e estrutura de bloco

Temos um tipo de isolamento de nomes disponível até agora: Os parâmetros formais de um procedimento são locais ao corpo do procedimento. O programa de raiz quadrada ilustra outra maneira pela qual gostaríamos de controlar o uso de nomes. O programa existente consiste em procedimentos separados:

(define (sqrt x) 
  (sqrt-iter 1.0 x))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (improve guess x)
  (average guess (/ x guess)))
      

O problema com esse programa é que o único procedimento importante para os usuários de sqrt é sqrt. Os outros procedimentos (sqrt-iter, good-enough? e improve) apenas atrapalham suas mentes. Eles podem não definir nenhum outro procedimento chamado good-enough? como parte de outro programa para trabalhar junto com o programa de raiz quadrada, porque sqrt precisa dele. O problema é especialmente grave na construção de grandes sistemas por muitos programadores separados. Por exemplo, na construção de uma grande biblioteca de procedimentos numéricos, muitas funções numéricas são calculadas como aproximações sucessivas e, portanto, podem ter procedimentos chamados good-enough? e improve como procedimentos auxiliares. Gostaríamos de localizar os subprocedimentos, escondendo-os dentro de sqrt para que sqrt pudesse coexistir com outras aproximações sucessivas, cada uma tendo seu próprio procedimento privado good-enough?. Para tornar isso possível, permitimos que um procedimento tenha definições internas que são locais a esse procedimento. Por exemplo, no problema da raiz quadrada, podemos escrever:

(define (sqrt x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))
  (sqrt-iter 1.0 x))
      

Esse aninhamento de definições, chamado estrutura de bloco, é basicamente a solução correta para o problema mais simples de empacotamento de nomes. Mas há uma ideia melhor aqui. Além de internalizar as definições dos procedimentos auxiliares, podemos simplificá-las. Como x é ligado na definição de sqrt, os procedimentos good-enough?, improve e sqrt-iter, que são definidos internamente em sqrt, estão no escopo de x. Assim, não é necessário passar x explicitamente para cada um desses procedimentos. Em vez disso, permitimos que x seja uma variável livre nas definições internas, como mostrado abaixo. Então x obtém seu valor do argumento com o qual o procedimento envolvente sqrt é chamado. Essa disciplina é chamada escopo léxico.²⁷

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))
      

Usaremos a estrutura de bloco extensivamente para nos ajudar a dividir programas grandes em partes gerenciáveis.²⁸ A ideia da estrutura de bloco originou-se com a linguagem de programação Algol 60. Ela aparece na maioria das linguagens de programação avançadas e é uma ferramenta importante para ajudar a organizar a construção de programas grandes.