Por que é determinar se uma função é pura difícil?

Question

Eu estava na convenção StackOverflow Dev Dias ontem, e um dos oradores estava falando sobre Python. Ele mostrou uma função Memoize, e eu perguntei se havia alguma maneira de mantê-lo de ser usado em uma função não-puro. Ele não disse, que é basicamente impossível, e se alguém pudesse descobrir uma maneira de fazer isso seria fazer uma grande tese de doutoramento.

Esse tipo de me confuso, porque ele não parece tão difícil para um compilador / interpretador para resolver de forma recursiva. Em pseudocódigo:

function isPure(functionMetadata): boolean;
begin
   result = true;
   for each variable in functionMetadata.variablesModified
      result = result and variable.isLocalToThisFunction;
   for each dependency in functionMetadata.functionsCalled
      result = result and isPure(dependency);
end;

Essa é a idéia básica. Obviamente, você precisa de algum tipo de seleção para evitar recursão infinita em funções mutuamente dependentes, mas que não é muito difícil de configurar.

funções

de ordem superior que levam ponteiros de função pode ser problemático, uma vez que eles não podem ser verificadas estaticamente, mas a minha pergunta pressupõe originais que o compilador tem algum tipo de restrição linguagem para designar que apenas um ponteiro de função pura pode ser passado para um determinado parâmetro. Se existisse, que poderia ser usado para satisfazer a condição.

Obviamente, isso seria mais fácil em uma linguagem compilada que uma interpretado um, uma vez que todos seria feito antes que o programa é executado e por isso não abrandar nada, mas eu realmente não vejo quaisquer problemas fundamentais que esta trituração de número torná-lo impossível avaliar.

Alguém com um pouco mais de conhecimento nesta área sabe o que eu estou perdendo?

Answer 1

É particularmente difícil em Python. Desde anObject.aFunc pode ser alterado arbitrariamente em tempo de execução, você não pode determinar em tempo de compilação que função irá anObject.aFunc() chamada ou mesmo que será uma função em tudo.

Answer 2

Você também precisa anotar cada chamada de sistema, cada FFI, ...

E, além disso, o mais ínfimo 'vazamento' tende a vazar para toda a base de código.

Não é um problema, teoricamente, intratável, mas na prática é muito, muito difícil de fazer de uma forma que todo o sistema não se sente frágil.

Como um aparte, eu não acho que isso faz uma tese boa PhD; Haskell efetivamente já tem (a versão), este, com a mônada IO.

e tenho certeza muitas pessoas continuam a olhar para esta 'na prática'. (Especulação) Em 20 anos nós podemos ter isso.

Answer 3

Além dos outros excelentes respostas aqui: Seu pseudocódigo olha apenas para se A modifica função variáveis. Mas isso não é realmente o que significa "puros". "Pure" normalmente significa algo mais próximo de "referencialmente transparente." Em outras palavras, a saída é completamente dependente da entrada. Portanto, algo tão simples como ler a hora e fazer que um fator no resultado (ou ler a partir da entrada, ou ler o estado da máquina, ou ...) faz com que a função não-puro, sem modificar quaisquer variáveis.

Além disso, você pode escrever uma função "pura" que fez variáveis ??modificar.

Answer 4

Aqui está a primeira coisa que veio à minha mente quando li a sua pergunta.

Classe hierarquias

Como determinar se uma variável é modificado inclui o ato de cavar através de cada método único que é chamado na variável para determinar se ele está em mutação. Isto é ... um pouco para a frente para um tipo selado com um método não-virtual.

Mas considere métodos virtuais. Você deve encontrar todo o tipo derivado única e verificar que cada substituição desse método não estado mutação. Determinar isso simplesmente não é possível em qualquer linguagem / framework que permite a geração de código dinâmico ou é simplesmente dinâmico (se é possível, é extremamente difícil). A razão por que é que o conjunto de tipos derivados não é fixo porque um novo pode ser gerado em tempo de execução.

Tome C # como um exemplo. Não há nada que me impeça de gerar uma classe derivada em tempo de execução que substitui esse método virtual e modifica o estado. Um estática verificada não seria capaz de detectar este tipo de modificação e, portanto, não pode validar o método era puro ou não.

Answer 5

Eu acho que o principal problema seria fazê-lo de forma eficiente.

D-língua tem funções puras, mas você tem que especificá-los a si mesmo, para que o compilador saberia para verificá-los. Acho que se você especificá-los manualmente, então seria mais fácil de fazer.

Answer 6

Decidir se uma determinada função é puro, em geral, é redutível a decidir se um determinado programa irá parar. - E é bem sabido que o Deter Problema é o tipo de problema que não pode ser resolvido de forma eficiente

Answer 7

Note que a complexidade depende da linguagem também. Para as línguas mais dinâmicas, é possível redefinir qualquer coisa a qualquer momento. Por exemplo, em Tcl

proc myproc {a b} {
    if { $a > $b } {
        return $a
    } else {
        return $b
    }
}

Cada pedaço de que poderia ser modificado a qualquer momento. Por exemplo:

• o "se" comando pode ser reescrito para usar e atualizar as variáveis ??globais
• o comando "return", nos mesmos moldes, poderia fazer a mesma coisa
• o poderia ser um traço de execução no caso de comando que, quando "se" é usado, o comando de retorno é redefinida com base nas entradas para o comando if

Na verdade, Tcl é um caso extremo; um dos mais linguagens dinâmicas existe. Dito isto, ele destaca o problema que pode ser difícil determinar a pureza de uma função, mesmo depois de ter entrado.