1.1.5 O modelo de substituição para a aplicação de função
Para avaliar uma aplicação de função, o interpretador segue o processo descrito na seção 1.1.4. Ou seja, o interpretador avalia os elementos da aplicação e aplica a função (que é o valor da expressão da função da aplicação) aos argumentos (que são os valores das expressões de argumento do aplicação).
Podemos assumir que a aplicação de funções primitivas é feita pelo interpretador ou bibliotecas. Para funções compostas, o processo de aplicação é o seguinte:
- Para aplicar uma função composta a argumentos, avalie a expressão de retorno da função com cada parâmetro substituído pelo argumento correspondente.1
Para ilustrar esse processo, vamos avaliar a aplicação
onde f é a função declarada na seção 1.1.4. Começamos recuperando a expressão de retorno de f:
sum_of_squares (a + 1, a * 2)
Em seguida, substituímos o parâmetro a pelo argumento 5:
sum_of_squares (5 + 1, 5 * 2)
Assim, o problema se reduz à avaliação de uma aplicação com dois argumentos e uma expressão de função sum_of_squares. Avaliar esta aplicação envolve três subproblemas. Devemos avaliar a expressão da função para obter a função a ser aplicada e devemos avaliar as expressões de argumento para obter os argumentos. Agora 5 + 1 produz 6 e 5 * 2 produz 10, então devemos aplicar a função sum_of_squares a 6 e 10. Esses valores são substituídos pelos parâmetros x e y no corpo de sum_of_squares, reduzindo a expressão para:
square (6) + square (10)
Se usarmos a declaração de quadrado, isso se reduz a:
(6 * 6) + (10 * 10)
que reduz por multiplicação a:
36 + 100
e finalmente para:
136
O processo que acabamos de descrever é chamado de modelo de substituição para aplicação de função. Pode ser tomado como um modelo que determina o "significado" da aplicação da função, no que diz respeito às funções neste capítulo. No entanto, há dois pontos que devem ser destacados:
- O objetivo da substituição é nos ajudar a pensar sobre a aplicação da função, não fornecer uma descrição de como o interpretador realmente funciona. Os interpretadores típicos não avaliam os aplicações de função manipulando o texto de uma função para substituir os valores dos parâmetros. Na prática, a "substituição" é realizada usando um ambiente local para os parâmetros. Discutiremos isso mais detalhadamente nos capítulos 3 e 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 comece 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 com mais detalhes, esses modelos simples tornam-se inadequados e devem ser substituídos por modelos mais refinados. O modelo de substituição não é exceção. Em particular, quando abordamos no capítulo 3 o uso de funções com "dados mutáveis", veremos que o modelo de substituição falha e deve ser substituído por um modelo mais complicado de aplicação de função.2
Ordem aplicativa vs. ordem normal
De acordo com a descrição da avaliação dada na seção 1.1.4, o interpretador primeiro avalia as expressões de função e argumento e então aplica a função resultante aos argumentos resultantes. Esta não é a única forma de realizar uma avaliação. Um modelo de avaliação alternativo não avaliaria os argumentos até que seus valores fossem necessários. Em vez disso, primeiro substituiria expressões de argumento por parâmetros até obter uma expressão envolvendo apenas operadores e funções primitivas e, então, realizaria a avaliação. Se usássemos esse método, a avaliação de
f(5)
iria proceder 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çoes:
6 * 6 + 10 * 10
36 + 100
136
Isso dá a mesma resposta que nosso modelo de avaliação anterior, 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.
Este método de avaliação alternativo "expandir totalmente e então reduzir" é conhecido como avaliação de ordem normal, em contraste com o método de "avaliar os argumentos e depois aplicar" que o interpretador realmente usa, que é chamado de avaliação de ordem de aplicação. Pode-se mostrar que, para aplicações de função que podem ser modelados usando substituição (incluindo todas as funções nos primeiros dois capítulos deste livro) e que geram valores legítimos, a avaliação de ordem normal e de ordem de aplicação produzem o mesmo valor. (Consulte o exercício 1.5 para obter uma instância de um valor "ilegítimo" em que a avaliação da ordem normal e da ordem aplicativa não dá o mesmo resultado.)
JavaScript usa avaliação de ordem de aplicação, em parte por causa da eficiência adicional obtida ao evitar avaliações múltiplas de expressões como aquelas ilustradas com 5 + 1 e 5 * 2 acima e, mais significativamente, porque a avaliação de ordem normal se torna muito mais complicada de lidar quando deixamos o reino das funções que podem ser modeladas por substituição. Por outro lado, a avaliação de ordem normal pode ser uma ferramenta extremamente valiosa, e investigaremos algumas de suas implicações nos capítulos [3] e [4].3
[1] Se o corpo da função for uma sequência de instruções, o corpo será avaliado com os parâmetros substituídos e o valor da aplicação será o valor da expressão de retorno da primeira instrução de retorno encontrada.
[2] Apesar da simplicidade da ideia de substituição, é surpreendentemente complicado dar uma definição matemática rigorosa do processo de substituição. O problema surge da possibilidade de confusão entre os nomes usados para os parâmetros de uma função e os nomes (possivelmente idênticos) usados nas expressões às quais a função pode ser aplicada. Na verdade, há uma longa história de definições errôneas de substituição na literatura de lógica e semântica de programação. Veja Stoy 1977 para uma discussão cuidadosa sobre substituição.
[3] No capítulo [3], apresentaremos o processamento de fluxo, que é uma maneira de lidar com estruturas de dados aparentemente "infinitas", incorporando uma forma limitada de avaliação de ordem normal. Na seção [4.2], modificaremos o interpretador JavaScript para produzir uma variante de ordem normal do JavaScript.