É possível calcular se duas funções são extensional iguais?

9

Se você tem duas funções implementando um algoritmo de classificação diferente, é possível inferir pelo código-fonte que ambas possuem as mesmas propriedades externas? Significando que ambos terão uma sequência não classificada possível como entrada e uma sequência classificada como saída? De que maneira essas propriedades externas podem ser determinadas pelo código fonte? E como você descreveria essas propriedades externas? Que notação seria usada?

As propriedades externas podem ser conhecidas, definindo-as explicitamente, por exemplo, dentro de um sistema de tipos, mas estou imaginando se isso poderia ser feito implicitamente. Ou é de alguma forma teoricamente impossível inferir esse tipo de semântica? Estou interessado em saber se isso é possível para funções arbitrárias, não apenas para algoritmos de classificação, assumindo que coisas como funções sempre parem e não tenham efeitos colaterais.

Devo olhar para a semântica denotacional ou não está relacionada?

Estou interessado em indicadores para pesquisar nesta área e em termos diferentes usados ​​para descrever o assunto que pode ajudar na minha pesquisa bibliográfica.

Matthijs Steen
fonte

Respostas:

8

Sim. Se você pode verificar se são iguais, o mesmo ocorre com um computador.

Aqui está uma especificação rápida para uma classificação inteira no Coq:

Inductive natlist : Type :=
| nil : natlist
| cons : nat → natlist → natlist.

Fixpoint is_sorted (l : natlist ) : bool :=
    match l with
    |  nil => true
    |  (cons x nil) => true
    |  (cons x (cons y r)) => if x <= y then is_sorted (cons y r) else false
    end.

...

Theorem sort_spec : forall l, is_sorted (sort_list l).

Uma especificação pode ser codificada diretamente na declaração de classificação usando tipos dependentes.

Para esse problema em particular, John Darlington demonstrou nos anos 70 que 6 famílias de algoritmos de classificação podem ser derivadas transformando mecanicamente a especificação de um tipo em uma implementação; Eu acredito que isso se chama "derivação de programa baseado em semântica".

No mundo da engenharia de software, encontrar funções extensionalmente equivalentes é conhecido como "detecção de clone semântico".

Dave Clarke também deu uma boa resposta a esta pergunta no CS StackExchange: /cs/2059/how-do-you-check-if-two-algorithms-return-the-same-result -for-any-input

Tudo isso se enquadra nos métodos formais e nas linguagens de programação . A semântica denotacional é uma classe de técnicas para modelar a semântica, mas caiu em desuso por ser difícil de usar em comparação com a semântica operacional.

James Koppel
fonte
Obrigado pela resposta! Era exatamente isso que eu estava procurando.
Matthijs Steen
4
Discordo totalmente da afirmação de que a semântica denotacional "caiu em desuso". Isso depende em grande parte de quem você pergunta.
21311 Andrej Bauer
5

A igualdade extensional em Turing linguagens de programação completas é indecidível em geral, mas isso não deve impedir você de verificar ou falsificar se duas funções específicas são extensionalmente iguais.

f=gxα.f(x)=g(x)fgαβ

Martin Berger
fonte
Obrigado pela resposta. Vou analisar a lógica de Hoare. A semântica denotacional é difícil de definir em comparação com a lógica Hoare, ou é apenas menos adequada para a maioria dos idiomas? A igualdade extensional é indecidível em geral por causa do problema da parada? Então, se as funções sempre parassem, como nas linguagens funcionais totais, não seria decidível em geral? Ou há outras razões para ser indecidível em geral?
Matthijs Steen
P0 0
... tem uma igualdade contextual decidível. Mas observe que R. Loader mostrou que mesmo o PCF financeiro possui uma equivalência contextual indecidível.
Martin Berger
-2

Uma resposta rápida (admito que não gastei muito tempo ...) O teorema de Rice diz que, para qualquer questão não trivial, é indecidível dizer se a função calculada por um programa terá a propriedade ou não. Portanto, a questão aqui é indecidível

cara normal
fonte
11
Não afirma que "... para qualquer propriedade não trivial de funções parciais ...", então não seria possível decidir por funções totais?
Matthijs Steen