Estratégia de avaliação - Evaluation strategy

Estratégias de avaliação

Em uma linguagem de programação , uma estratégia de avaliação é um conjunto de regras para avaliar expressões. O termo é frequentemente usado para se referir à noção mais específica de uma estratégia de passagem de parâmetro que define se avaliar os parâmetros de uma chamada de função e, em caso afirmativo, em que ordem (a ordem de avaliação ) e o tipo de valor que é passado para a função para cada parâmetro (a estratégia de ligação ). A noção de estratégia de redução é distinta, embora alguns autores confundam os dois termos e a definição de cada termo não seja amplamente aceita.

Para ilustrar, um aplicativo de função pode avaliar o argumento antes de avaliar o corpo da função e passar o endereço, dando à função a capacidade de pesquisar o valor atual do argumento e modificá-lo por meio de atribuição .

A estratégia de avaliação é especificada pela definição da linguagem de programação e não é função de nenhuma implementação específica. A convenção de chamada define detalhes de passagem de parâmetro específicos da implementação.

Mesa

Esta é uma tabela de estratégias de avaliação e idiomas representativos introduzidos por ano. Os idiomas representativos são listados em ordem cronológica, começando com os idiomas que introduziram a estratégia (se houver) e seguidos pelos idiomas proeminentes que usam a estratégia.

Estratégia de avaliação Linguagens Representativas Ano introduzido pela primeira vez
Chamada por referência FORTRAN II , PL / I 1958
Chamada por valor ALGOL , C , Scheme 1960
Chamada pelo nome ALGOL 60 , Simula 1960
Chamada por cópia-restauração Fortran IV , Ada 1962
Ligue por necessidade Haskell , R 1971
Parâmetros de chamada por referência C ++ , PHP , C # , Visual Basic .NET ?
Chamada por referência a const C , C ++ ?
Ligar compartilhando Java, Python, Ruby ?

Ordens de avaliação

Enquanto a ordem das operações define a árvore de sintaxe abstrata da expressão, a ordem de avaliação define a ordem em que as expressões são avaliadas. Por exemplo, o programa Python 

def f(x):
    print(x)
    return x

f(1) + f(2)

saídas 1 2devido à ordem de avaliação da esquerda para a direita do Python, mas um programa semelhante em OCaml: 

let f x =  print_string (string_of_int x); x ;;
f 1 + f 2

saídas 2 1devido à ordem de avaliação da direita para a esquerda do OCaml.

A ordem de avaliação é principalmente visível no código com efeitos colaterais , mas também afeta o desempenho do código porque uma ordem rígida inibe o agendamento de instruções . Por esse motivo, os padrões de linguagem como C ++ tradicionalmente deixam a ordem indefinida, embora linguagens como Java e C # definam a ordem de avaliação como da esquerda para a direita e o padrão C ++ 17 tenha adicionado restrições à ordem de avaliação.

Avaliação rigorosa

Ordem de aplicação é uma família de ordens de avaliação na qual os argumentos de uma função são avaliados completamente antes que a função seja aplicada. Isso tem o efeito de tornar a função estrita , ou seja, o resultado da função é indefinido se algum dos argumentos for indefinido, portanto, a avaliação de pedido de aplicativo é mais comumente chamada de avaliação estrita . Além disso, uma chamada de função é realizada assim que é encontrada em um procedimento, por isso também é chamada de avaliação ansiosa ou avaliação gananciosa . Alguns autores referem-se à avaliação estrita como "chamada por valor" devido à estratégia de ligação chamada por valor que exige avaliação estrita.

Common Lisp, Eiffel e Java avaliam os argumentos da função da esquerda para a direita. C deixa a ordem indefinida. O esquema requer que a ordem de execução seja a execução sequencial de uma permutação não especificada dos argumentos. OCaml da mesma forma deixa a ordem não especificada, mas na prática avalia os argumentos da direita para a esquerda devido ao design de sua máquina abstrata . Todas essas são avaliações rigorosas.

Avaliação não rigorosa

Uma ordem de avaliação não estrita é uma ordem de avaliação que não é estrita, ou seja, uma função pode retornar um resultado antes que todos os seus argumentos sejam totalmente avaliados. O exemplo prototípico é a avaliação de ordem normal , que não avalia nenhum dos argumentos até que eles sejam necessários no corpo da função. A avaliação de pedido normal tem a propriedade de terminar sem erro sempre que qualquer outro pedido de avaliação terminar sem erro. Observe que a avaliação preguiçosa é classificada neste artigo como uma técnica de ligação em vez de uma ordem de avaliação. Mas essa distinção nem sempre é seguida e alguns autores definem avaliação preguiçosa como avaliação de ordem normal ou vice-versa, ou confundem não rigor com avaliação preguiçosa.

Expressões booleanas em muitas linguagens usam uma forma de avaliação não estrita chamada avaliação de curto-circuito , onde a avaliação retorna assim que pode ser determinado que um booleano inequívoco resultará - por exemplo, em uma expressão disjuntiva (OR) onde truefor encontrada, ou em uma expressão conjuntiva (AND) onde falseé encontrado, e assim por diante. Expressões condicionais usam avaliação não estrita de maneira semelhante - apenas uma das ramificações é avaliada.

Comparação de pedido de aplicativo e avaliação de pedido normal

Com a avaliação de pedido normal, expressões contendo um cálculo caro, um erro ou um loop infinito serão ignoradas se não forem necessárias, permitindo a especificação de construções de fluxo de controle definidas pelo usuário, um recurso não disponível na avaliação de pedido de aplicativo. A avaliação de pedido normal usa estruturas complexas, como thunks para expressões não avaliadas, em comparação com a pilha de chamadas usada na avaliação de pedido de aplicativo. A avaliação de pedido normal tem historicamente uma falta de ferramentas de depuração utilizáveis ​​devido à sua complexidade.

Estratégias de ligação estrita

Chamada por valor

Na chamada por valor, o valor avaliado da expressão do argumento é vinculado à variável correspondente na função (frequentemente copiando o valor em uma nova região da memória). Se a função ou procedimento é capaz de atribuir valores a seus parâmetros, apenas sua variável local é atribuída - ou seja, qualquer coisa passada em uma chamada de função permanece inalterada no escopo do chamador quando a função retorna.

Limitações implícitas

Em alguns casos, o termo "chamada por valor" é problemático, pois o valor que é passado não é o valor da variável conforme entendido pelo significado comum de valor, mas uma referência específica de implementação para o valor. O efeito é que o que sintaticamente parece chamada por valor pode acabar se comportando como chamada por referência ou chamada por compartilhamento , geralmente dependendo de aspectos muito sutis da semântica da linguagem.

A razão para passar uma referência é frequentemente que a linguagem tecnicamente não fornece uma representação de valor de dados complicados, mas em vez disso os representa como uma estrutura de dados enquanto preserva alguma aparência de valor no código-fonte. Exatamente onde o limite é traçado entre os valores apropriados e as estruturas de dados disfarçadas como tal costuma ser difícil de prever. Em C , um array (dos quais strings são casos especiais) é uma estrutura de dados, mas o nome de um array é tratado como (tem como valor) a referência ao primeiro elemento do array, enquanto o nome de uma variável de estrutura se refere a um valor mesmo se tiver campos que são vetores. No Maple , um vetor é um caso especial de uma tabela e, portanto, uma estrutura de dados, mas uma lista (que é renderizada e pode ser indexada exatamente da mesma maneira) é um valor. Em Tcl , os valores são "portados em duas portas" de forma que a representação do valor seja usada no nível do script e a própria linguagem gerencia a estrutura de dados correspondente, se for necessária. As modificações feitas por meio da estrutura de dados são refletidas de volta para a representação do valor e vice-versa.

A descrição "chamada por valor onde o valor é uma referência" é comum (mas não deve ser entendida como uma chamada por referência); outro termo é chamada por compartilhamento . Assim, o comportamento de chamada por valor Java ou Visual Basic e chamada por valor C ou Pascal são significativamente diferentes: em C ou Pascal, chamar uma função com uma estrutura grande como um argumento fará com que toda a estrutura seja copiada (exceto se for realmente uma referência a uma estrutura), podendo causar séria degradação do desempenho, e mutações na estrutura são invisíveis para o chamador. No entanto, em Java ou Visual Basic, apenas a referência à estrutura é copiada, o que é rápido, e as mutações na estrutura são visíveis para o chamador.

Chamada por referência

Chamada por referência (ou passagem por referência) é uma estratégia de avaliação em que um parâmetro é vinculado a uma referência implícita à variável usada como argumento, em vez de uma cópia de seu valor.

Isso normalmente significa que a função pode modificar (ou seja, atribuir a ) a variável usada como argumento - algo que será visto por seu chamador. Chamada por referência pode, portanto, ser usada para fornecer um canal adicional de comunicação entre a função chamada e a função chamadora. Uma linguagem chamada por referência torna mais difícil para um programador rastrear os efeitos de uma chamada de função e pode introduzir bugs sutis. Um teste de tornassol simples para saber se um idioma oferece suporte à semântica chamada por referência é se é possível escrever uma swap(a, b)função tradicional no idioma.

Chamada por referência pode ser simulada em linguagens que usam chamada por valor e não suportam exatamente chamada por referência, fazendo uso de referências (objetos que se referem a outros objetos), como ponteiros (objetos que representam os endereços de memória de outros objetos) . Linguagens como C , ML e Rust usam essa técnica. Não é uma estratégia de avaliação separada - a linguagem chama por valor - mas às vezes é chamada de "chamada por endereço" ou "passagem por endereço". Em ML, as referências são seguras quanto ao tipo e à memória , semelhantes a Rust.

Em linguagens puramente funcionais , normalmente não há diferença semântica entre as duas estratégias (uma vez que suas estruturas de dados são imutáveis, então não há possibilidade de uma função modificar qualquer um de seus argumentos), então elas são normalmente descritas como chamadas por valor, mesmo que implementações freqüentemente usa chamada por referência internamente para os benefícios de eficiência.

A seguir está um exemplo que demonstra a chamada por referência na linguagem de programação E : 

def modify(var p, &q) {
    p := 27 # passed by value: only the local parameter is modified
    q := 27 # passed by reference: variable used in call is modified
}

? var a := 1
# value: 1
? var b := 2
# value: 2
? modify(a, &b)
? a
# value: 1
? b
# value: 27

A seguir está um exemplo de chamada por endereço que simula uma chamada por referência em C : 

void modify(int p, int* q, int* r) {
    p = 27; // passed by value: only the local parameter is modified
    *q = 27; // passed by value or reference, check call site to determine which
    *r = 27; // passed by value or reference, check call site to determine which
}

int main() {
    int a = 1;
    int b = 1;
    int x = 1;
    int* c = &x;
    modify(a, &b, c); // a is passed by value, b is passed by reference by creating a pointer (call by value),
                    // c is a pointer passed by value
                    // b and x are changed
    return 0;
}

Ligar compartilhando

Chamada por compartilhamento (também conhecido como "chamada por objeto" ou "chamada por compartilhamento de objeto") é uma estratégia de avaliação observada pela primeira vez por Barbara Liskov em 1974 para a linguagem CLU . É usado por linguagens como Python , Java (para referências de objetos), Ruby , JavaScript , Scheme, OCaml, AppleScript e muitas outras. No entanto, o termo "chamada por compartilhamento" não é de uso comum; a terminologia é inconsistente em diferentes fontes. Por exemplo, na comunidade Java, eles dizem que Java é chamada por valor. Chamar por compartilhamento implica que os valores na linguagem são baseados em objetos e não em tipos primitivos , ou seja, todos os valores estão " encaixotados ". Por estarem encaixotados, pode-se dizer que passam por uma cópia de referência (onde os primitivos são encaixotados antes de passar e desempacotados na função chamada).

A semântica da chamada por compartilhamento difere da chamada por referência: "Em particular, não é chamada por valor porque as mutações de argumentos realizadas pela rotina chamada serão visíveis para o chamador. E não é chamada por referência porque o acesso não é concedido a as variáveis ​​do chamador, mas apenas para determinados objetos ". Assim, por exemplo, se uma variável foi passada, não é possível simular uma atribuição para aquela variável no escopo do receptor. No entanto, como a função tem acesso ao mesmo objeto que o chamador (nenhuma cópia é feita), as mutações nesses objetos, se os objetos forem mutáveis , dentro da função são visíveis para o chamador, o que pode parecer diferente da chamada por valor semântica. As mutações de um objeto mutável dentro da função são visíveis para o chamador porque o objeto não é copiado ou clonado - ele é compartilhado.

Por exemplo, em Python, as listas são mutáveis, então: 

def f(a_list):
    a_list.append(1)

m = []
f(m)
print(m)

é gerado [1]porque o appendmétodo modifica o objeto no qual é chamado.

As atribuições dentro de uma função não são perceptíveis para o chamador, porque, nessas linguagens, passar a variável significa apenas passar (acessar) o objeto real referido pela variável, não acessar a variável original (do chamador). Uma vez que a variável rebote existe apenas dentro do escopo da função, a contraparte no chamador mantém sua ligação original.

Compare a mutação Python acima com o código abaixo, que vincula o argumento formal a um novo objeto: 

def f(a_list):
    a_list = [1]

m = []
f(m)
print(m)

saídas [], porque a instrução a_list = [1]reatribui uma nova lista à variável em vez de ao local que ela faz referência.

Para objetos imutáveis , não há diferença real entre chamada por compartilhamento e chamada por valor, exceto se a identidade do objeto for visível na linguagem. O uso de chamada por compartilhamento com objetos mutáveis ​​é uma alternativa aos parâmetros de entrada / saída : o parâmetro não é atribuído a (o argumento não é substituído e a identidade do objeto não é alterada), mas o objeto (argumento) é alterado.

Chamada por cópia-restauração

Chamada por cópia-restauração - também conhecido como "cópia de entrada e saída", "chamada por resultado de valor", "chamada por retorno de valor" (como denominado na comunidade Fortran ) - é um caso especial de chamada por referência onde o a referência fornecida é única para o chamador. Esta variante ganhou atenção em contextos de multiprocessamento e chamada de procedimento remoto : se um parâmetro para uma chamada de função é uma referência que pode ser acessível por outro thread de execução, seu conteúdo pode ser copiado para uma nova referência que não é; quando a chamada de função retorna, o conteúdo atualizado desta nova referência é copiado de volta para a referência original ("restaurado").

A semântica de chamada por cópia-restauração também difere daquela de chamada por referência, onde dois ou mais argumentos de função apelidam um do outro (ou seja, apontam para a mesma variável no ambiente do chamador). Sob chamada por referência, escrever para um afetará o outro; chamada por copy-restore evita isso, dando à função cópias distintas, mas deixa o resultado no ambiente do chamador indefinido, dependendo de qual dos argumentos com alias é copiado primeiro - as cópias serão feitas na ordem da esquerda para a direita tanto na entrada e no retorno?

Quando a referência é passada para o receptor não inicializado, essa estratégia de avaliação pode ser chamada de "chamada por resultado".

Estratégias de ligação não estrita

Chamada pelo nome

Chamada pelo nome é uma estratégia de avaliação em que os argumentos para uma função não são avaliados antes que a função seja chamada - em vez disso, eles são substituídos diretamente no corpo da função (usando a substituição de evitar captura ) e, em seguida, deixados para serem avaliados sempre que aparecerem no função. Se um argumento não for usado no corpo da função, o argumento nunca será avaliado; se for usado várias vezes, será reavaliado cada vez que aparecer. (Veja o Dispositivo de Jensen .)

A avaliação chamada por nome é ocasionalmente preferível à avaliação chamada por valor. Se o argumento de uma função não for usado na função, a chamada por nome economizará tempo por não avaliar o argumento, enquanto a chamada por valor irá avaliá-lo independentemente. Se o argumento for um cálculo sem fim, a vantagem é enorme. No entanto, quando o argumento da função é usado, a chamada por nome costuma ser mais lenta, exigindo um mecanismo como uma conversão .

As linguagens .NET de hoje podem simular chamadas por nome usando delegados ou Expression<T>parâmetros. O último resulta em uma árvore de sintaxe abstrata sendo fornecida para a função. Eiffel fornece agentes, que representam uma operação a ser avaliada quando necessário. Seed7 fornece chamada por nome com parâmetros de função. Os programas Java podem realizar avaliações lentas semelhantes usando expressões lambda e a java.util.function.Supplier<T>interface.

Ligue por necessidade

Artigo principal: Avaliação preguiçosa

Chamada por necessidade é uma variante memorizada de chamada por nome, onde, se o argumento da função for avaliado, esse valor é armazenado para uso subsequente. Se o argumento for puro (ou seja, livre de efeitos colaterais), isso produzirá os mesmos resultados que chamar pelo nome, economizando o custo de recomputar o argumento.

Haskell é uma linguagem bem conhecida que usa avaliação chamada por necessidade. Como a avaliação de expressões pode acontecer arbitrariamente em um cálculo, Haskell suporta apenas efeitos colaterais (como mutação ) por meio do uso de mônadas . Isso elimina qualquer comportamento inesperado de variáveis ​​cujos valores mudam antes de sua avaliação atrasada.

Na implementação de R de chamada por necessidade, todos os argumentos são passados, o que significa que R permite efeitos colaterais arbitrários.

A avaliação lenta é a implementação mais comum da semântica chamada por necessidade, mas existem variações como a avaliação otimista . As linguagens .NET implementam chamada por necessidade usando o tipo Lazy<T>.

A redução do gráfico é uma implementação eficiente da avaliação preguiçosa.

Chamada por expansão macro

A expansão de chamada por macro é semelhante à chamada por nome, mas usa substituição textual em vez de captura, evitando assim a substituição. Mas a substituição da macro pode causar erros, resultando na captura de variáveis , levando a um comportamento indesejado. As macros higiênicas evitam esse problema verificando e substituindo variáveis ​​sombreadas que não são parâmetros.

Ligue no futuro

Veja também: Futuros e promessas

"Chamada por futuro", também conhecida como "chamada paralela por nome", é uma estratégia de avaliação concorrente em que o valor de uma expressão futura é calculado concomitantemente com o fluxo do resto do programa com promessas, também conhecido como futuros. Quando o valor da promessa é necessário, o programa principal bloqueia até que a promessa tenha um valor (a promessa ou uma das promessas termina de ser computada, se ainda não tiver sido concluída até então).

Essa estratégia é não determinística, pois a avaliação pode ocorrer a qualquer momento entre a criação do futuro (ou seja, quando a expressão é dada) e o uso do valor futuro. É semelhante à chamada por necessidade, pois o valor é calculado apenas uma vez e o cálculo pode ser adiado até que o valor seja necessário, mas pode ser iniciado antes. Além disso, se o valor de um futuro não for necessário, como se fosse uma variável local em uma função que retorna, o cálculo pode ser encerrado no meio.

Se implementado com processos ou threads, a criação de um futuro irá gerar um ou mais novos processos ou threads (para as promessas), acessar o valor irá sincronizá-los com a thread principal, e encerrar a computação do futuro corresponde a matar as promessas computando seus valor.

Se implementado com uma co - rotina , como no .NET async / await , a criação de um futuro chama uma co-rotina (uma função assíncrona), que pode ceder ao chamador e, por sua vez, retornar quando o valor for usado, multitarefa cooperativamente.

Avaliação otimista

A avaliação otimista é outra variante chamada por necessidade em que o argumento da função é parcialmente avaliado por algum tempo (que pode ser ajustado no tempo de execução ). Após esse tempo, a avaliação é abortada e a função é aplicada usando uma chamada por necessidade. Essa abordagem evita algumas despesas de tempo de execução da estratégia de chamada por necessidade, ao mesmo tempo em que mantém as características de finalização desejadas.

Veja também

Referências


Leitura adicional

links externos