Estratégia de avaliação

Em ciência da computação, estratégia de avaliação é um conjunto de regras para determinar a avaliação de expressões em uma linguagem de programação. A ênfase é colocada, tipicamente, em funções ou operadores. Uma estratégia de avaliação define quando e em que ordem os parâmetros para uma função são avaliados, quando eles são substituídos dentro da função, e de que forma tal substituição ocorre. O cálculo lambda, um sistema formal para o estudo de funções, tem sido freqüentemente usado para modelar estratégias de avaliação, onde são habitualmente chamadas de estratégias de redução. Estratégias de avaliação são divididas em dois grupos básicos, estrito e não-estrito, baseado em como os argumentos para cada função são tratados. Uma linguagem pode combinar várias estratégias de avaliação; por exemplo, C++, combina chamada-por-valor com chamada-por-referência. A maiorias das linguagens que são predominantemente estrita usam algumas formas de avaliação não-estrita para expressões booleanas e condicionais (if-else).

Avaliação estrita

Em uma avaliação estrita os argumentos de uma função são sempre avaliados completamente antes da função ser aplicada.

Sob a codificação de Church, a avaliação estrita de operadores é mapeada para avaliação estrita de funções. Por esta razão, avaliação estrita é também chamada de eager ("ansiosa"). A maioria das linguagens de programação usam avaliação estrita para suas funções.

Applicative order

Applicative order se refere a uma estratégia de avaliação em que os argumentos de uma função são avaliados da esquerda para a direita em uma ordem transversal posterior (post-order traversal) de expressões que podem ser reduzidas (redexes). Diferentemente de chamada-por-valor, este tipo de avaliação reduz os termos dentro de uma função, antes da função ser aplicada.

Chamada por valor

Chamada por valor é uma das estratégias de avaliação mais comuns, usada em linguagens como C e Scheme. Na chamada por valor, o argumento é avaliado e o valor de resultado é vinculado à variável correspondente na função, copiando o valor em uma nova região de memória. Se a função ou procedimento é capaz de atribuir valores a seus parâmetros, apenas a cópia local é atribuída, ou seja, nada que for passado como argumento de uma chamada de função é modificado, após o valor de retorno da função.

Chamada por valor não é uma simples estratégia de avaliação, mas sim uma família de estratégias de avaliação onde o argumento de uma função é avaliado antes se ser passado para a função.

Chamada por referência

Na avaliação de chamada por referência, uma função recebe uma referência implícita como argumento, em vez de uma cópia do seu valor. Isto significa que a função pode modificar o argumento. A chamada por referência tem a vantagem de ter um maior espaço de tempo e de eficiência, bem como o potencial de maior comunicação entre a função e quem a executou. Apesar disto, a desvantagem da chamada por referência é que a função necessita de passos especiais para proteger os valores que pretende passar a outras funções.

Várias linguagens suportam chamada por referência de uma forma ou de outra, mas apenas algumas usam isto como padrão. Perl e Visual Basic são duas linguagens que usam a passagem de referência como padrão, embora o Visual Basic também ofereça uma sintaxe especial para a chamada por valor de parâmetros. Poucas linguagens como C++, tem como padrão chamada por valor, apesar de oferecer recursos para a chamada por referência de parâmetros. Em linguagens funcionais puras não existe semântica diferente entre as duas estratégias, estas são geralmente descritas como chamada por valor, apesar de suas implementações utilizarem chamada por referência em nível interno. Isso ocorre uma vez que as suas estruturas de dados sejam imutáveis, pelo que não há possibilidade de uma função modificar qualquer um dos seus argumentos.

Chamada por compartilhamento

Também conhecida como chamada por objeto ou chamada por compartilhamento de objetos é uma estratégia de avaliação definida por Barbara Liskov para a linguagem CLU em 1974 [1]. Este tipo de avaliação é usada em linguagens como Python [2] e Iota e ([3]) Java, apesar deste termo não ser comum entre a comunidade Java. Chamada por compartilhamento implica que valores na linguagem são baseados em objetos, em vez de tipos primitivos, apesar de que estas linguagens definem tipos de dados primitivos como (int, float, double, boolean, char e byte).

A semântica desta avaliação difere da chamada por referência na passagem dos argumentos da função, onde estas não são visíveis para quem executou. Apesar da função ter acesso ao mesmo objeto de quem a chamou (não é feito cópia), as mudanças neste objeto dentro da função são visíveis no escopo de quem chamou a função, que difere também da semântica da chamada por valor.

Embora este termo tenha uma grande utilização na comunidade Python, esta semântica, em outras linguagens como Java e Visual Basic, são frequêntemente descritas como chamada por valor, onde o valor é apenas uma referência para o objeto.

Chamada por copia e restauração (copy-restore)

Chamada por copia e restauração, chamada por resultado ou chamada por retorno é um caso especial de chamada por referência desde que a referência seja única para quem executou a função. Se um parâmetro de uma função a ser chamada é a referência que deve ser acessada por um processo em execução, seu conteúdo é copiado para uma nova referência. Quando a função chamada retorna um valor, os conteúdos atualizados da nova referência são copiados de volta para a referência original. Por este motivo este tipo de avaliação é chamada de copy-restore.

A semântica deste tipo de avaliação também difere de outras, como a chamada por referência onde dois ou mais argumentos de uma função servem como pseudônimo de um outro, isto é, apontam para a mesma variável no ambiente de avaliação da função que efetuou a chamada. Sob chamada por referência, escrever usando um. afetará o outro. Chamada por copia e restauração evita que uma função tenha distinta cópias, contudo, o resultado fica no contexto de quem chamou a função.

Quando a referência é passada para o receptor sem inicialização, esta estratéria de avaliação pode ser chamada de chamada por resultado.

Avaliação Parcial

Na avaliação parcial , a avaliação pode continuar dentro do corpo de uma função que não tem sido aplicada. Qualquer sub-expressão que não contenha variáveis são avaliadas, e aplicações cujos valores dos argumentos das função são conhecidos podem ser reduzidos. Na presença de efeitos colaterais (side-effects), a avaliação parcial pode produzir resultados indesejados. Por esta razão, sistemas que suportam avaliação parcial tendem a fazer a avaliação apenas para expressões puras (expressões sem efeito colateral) com funções.

Avaliação Não-estrita

Em uma avaliação não-estrita, os argumentos para uma determinada função não são avaliados a menos que sejam utilizados na avaliação do corpo da função.

Sob a codificação Church, uma avaliação preguiçosa (lazy) de operadores é mapeada para uma avaliação não-estrita de funções; por esta razão, avaliação não-estrita é frequentemente referenciada como lazy. Expressões booleanas em várias linguagens usa avaliação preguiçosa. Neste contexto isto é chamado de curto circuito. Em Java, expressões booleanas de curto circuito são definidas com dupla referência de operadores (&&, ||). Expressões condicionais também usam avaliação preguiçosa.

Ordem normal

Avaliação de ordem normal é uma estratégia onde as expressões mais externas à esquerda (redexes) são sempre reduzidas em primeiro lugar, aplicando funções antes da avaliação dos argumentos. Isto diferencia ordem normal de chamada por nome, pois a chamada por nome não avalia o corpo da função.

Chamada por nome

Nesta avaliação, os argumentos não são avaliados de maneira completa, tais argumentos são substituídos diretamente dentro do corpo da função usando substituição do tipo capture-avoiding. Se um parâmetro não é usado na avaliação da função, este nunca será avaliado, e se o parâmetro é usado várias vezes, este é reavaliado a cada vez.

Esta avaliação pode ser preferível durante a avaliação de chamada por valor porque a avaliação por nome sempre retorna um valor quando este existe. A avaliação de chamada por nome pode ser preferível ao longo de chamadas, pelo valor de avaliação porque esta avaliação sempre retorna um valor, quando existe um valor, considerando que a chamada por valor poder não terminar se a avaliação do argumento da função pode não terminar computacionalmente.

Avaliação de chamada por nome é raramente implementada, mas é frequentemente utilizada em linguagens de programação. Linguagens do mundo real com semântica de chamada por nome são, geralmente, implementadas usando a avaliação de chamada por necessidade.

Chamada por necessidade

Chamada por necessidade é uma versão da chamada por nome, se o argumento da função é avaliado, seu valor é gravado para uso posterior. Em uma configuração pura, livre de efeitos colaterais, isto produz o mesmo resultado da avaliação da chamada por nome, contudo, quanto os argumentos das funções são usados duas ou mais vezes, a chamada por necessidade é quase sempre mais rápida.

Pelo fato da avaliação de expressões acorrer arbitrariamente durante a execução, linguagens que usam chamada por necessidade geralmente não suportam efeitos computacionais, como mutação. Isto elimina qualquer comportamento indesejado da variáveis cujos valores mudam antes da sua avaliação. Este é um tipo de avaliação pregiçosa (Lazy). Haskell é a linguagem mais conhecida que usa avaliação de chamada por necessidade.

Chamada por expansão de macro

Chamada por expansão de macro é similar a Camada por nome, mas usa substituição textual em vez de substituição capture-avoiding.

Estratégias Não-determinísticas

Redução-β

Em uma redução-β completa qualquer aplicação de função pode ser reduzida a qualquer momento. Isto ocorre pela substituição dos argumentos da função dentro do corpo da função usando substituição do tipo capture-avoiding. Uma substituição do tipo capture-avoiding é uma meta-função.

Chamada por futuro

Chamada por futuro é como a Chamada por necessidade em paralelo, exceto quando o argumento da função deve ser avaliado em paralelo com o corpo da função. As duas threads de execução sincronizam quando é necessário o uso do argumento para avaliação do corpo da função. Se o argumento nunca for usado, a thread deve ser excluída.

Avaliação Otimista

Avaliação otimista é uma variante da chamada por necessidade onde o argumento da função é parcialmente avaliado por um período de tempo, depois esta avaliação é abortada e a função é aplicada usando chamada por necessidade. Esta abordagem evita algumas das execuções caras da chamada por necessidade, mantendo as características de terminação desejadas.

Ver também

Referências

Harold Abelson and Gerald Jay Sussman. Structure and Interpretation of Computer Programs, Second Edition. MIT Press, 1996. ISBN 0-262-01153-0.
Henry G. Baker, Jr. "The Incremental Garbage Collection of Processes", with Carl Hewitt, ACM Sigplan Notices 12. August 8, 1977. Pages 55–59.
Clem Baker-Finch, Clem, David King, Jon Hall, and Phil Trinder. "An Operational Semantics for Parallel Call-by-Need", Research report 99/1. Faculty of Mathematics & Computing, The Open University, 1999.
Robert Ennals and Simon Peyton Jones. "Optimistic Evaluation: a fast evaluation strategy for non-strict programs", in ICFP'03. ACM Press, 2003.
Bertram Ludäscher. CSE 130 lecture notes. January 24, 2001.
Pierce, Benjamin C. (2002). Types and Programming Languages. [S.l.]: MIT Press. ISBN 0-262-16209-1
P. Sestoft. "Demonstrating Lambda Calculus Reduction", in T. Mogensen, D. Schmidt, I. H. Sudburough : The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones. Lecture Notes in Computer Science 2566. Springer-Verlag, 2002. Pages 420-435. ISBN 3-540-00326-6