Quando podemos dizer que dois programas são diferentes?

15

Q1 Quando podemos dizer que dois programas (escritos em alguma linguagem de programação como C ++) são diferentes?

O primeiro extremo é dizer que dois programas são equivalentes se forem idênticos. O outro extremo é dizer que dois programas são equivalentes se eles computarem a mesma função (ou mostrarem o mesmo comportamento observável em ambientes semelhantes). Mas isso não é bom: nem todos os programas que verificam a primalidade são iguais. Podemos adicionar uma linha de código sem afetar o resultado e ainda a consideraríamos o mesmo programa.

Q2 Programas e algoritmos são o mesmo tipo de objeto? Caso contrário, qual é a definição de um algoritmo e como ela difere da definição de um programa? Quando podemos dizer que dois algoritmos são equivalentes?

Anônimo
fonte
O problema do isomorfismo do programa? Não se pode perguntar "este programa é isomórfico para o programa que sempre pára?" e recuperar o problema de parada? Se nos restringirmos ao Problema do Programa de Parada Limitada, isso não é apenas isomorfismo gráfico?
user834
5
Quando dois algoritmos são iguais? arxiv.org/abs/0811.0811
sdcvvc
1
Não dependeria inteiramente do contexto? Ficando um pouco filosófico aqui, mas uma cadeira aparafusada e uma cadeira aparafusada de cabeça para baixo são a mesma coisa fisicamente, mas não é a mesma em termos da idéia de uma cadeira.
Rei Miyasaka
Ligeiramente off-topic, mas, uma vez que as provas são programas ... gowers.wordpress.com/2007/10/04/...
Radu Grigore
1
O artigo a seguir é muito relacionado. Eu só passei por isso há algum tempo, mas Blass e Gurevic geralmente escrevem muito bem (não me lembro de ler mais nada de Dershowitz, sem dizer que geralmente não é muito legível). research.microsoft.com/en-us/um/people/gurevich/Opera/192.pdf QUANDO SÃO DOIS ALGORITMOS O MESMO? ANDREAS BLASS, NACHUM DERSHOWITZ E YURI GUREVICH
kasterma

Respostas:

18

Q1: Existem muitas noções de equivalência de programas (equivalência de rastreio, equivalência contextual, equivalência observacional, bisimilaridade) que podem ou não levar em consideração itens como tempo, uso de recursos, não-determinismo e rescisão. Muito trabalho foi feito para encontrar noções utilizáveis ​​de equivalência de programas. Por exemplo: Teorias de equivalência de programas com base operacional de Andy Pitts . Mas isso mal arranha a superfície. Isso deve ser útil mesmo se você estiver interessado quando dois programas não são equivalentes. Pode-se até raciocinar sobre programas sem interrupção (usando bisimulação e coindução).

P2: Uma resposta possível para parte dessa pergunta é que os programas interativos não são algoritmos (supondo que se considere um algoritmo receber todas as suas entradas de uma só vez, mas essa definição restrita exclui os algoritmos online). Um programa pode ser uma coleção de processos de interação que também interagem com seu ambiente. Isso certamente não corresponde à noção de algoritmo da máquina de Turing / Recursão.

Dave Clarke
fonte
IO e efeitos colaterais em geral não são cobertos por noções clássicas de algoritmo.
Raphael
15

O outro extremo é dizer que dois programas são equivalentes se eles computarem a mesma função (ou mostrarem o mesmo comportamento observável em ambientes semelhantes). Mas isso não é bom: nem todos os programas que verificam a primalidade são iguais. Podemos adicionar uma linha de código sem afetar o resultado e ainda a consideraríamos o mesmo programa.

Isso não é extremo: a equivalência do programa deve ser definida em relação a uma noção de observação.

A definição mais comum na pesquisa em PL é equivalência contextual. Na equivalência contextual, a ideia é que observemos programas usando-os como componentes de programas maiores (o contexto). Portanto, se dois programas calculam o mesmo valor final para todos os contextos, eles são considerados iguais. Como essa definição quantifica todos os contextos possíveis do programa, é difícil trabalhar diretamente. Portanto, um programa de pesquisa típico em PL é encontrar princípios de raciocínio composicional que impliquem equivalência contextual.

No entanto, essa não é a única noção possível de observação. Por exemplo, podemos dizer facilmente que o comportamento da memória, hora ou potência de um programa é observável. Nesse caso, menos equivalências de programas são válidas, pois podemos distinguir mais programas (por exemplo, mergesort agora é distinguível de quicksort). Se você deseja (digamos) projetar linguagens imunes a ataques de canal de temporização ou projetar linguagens de programação com espaço limitado, esse é o tipo de ação que você deve fazer.

Além disso, podemos optar por julgar alguns dos estados intermediários de uma computação como observáveis. Isso sempre acontece para idiomas concorrentes, devido à possibilidade de interferência. Mas você pode considerar essa visão mesmo em idiomas seqüenciais - por exemplo, se quiser garantir que nenhum cálculo armazene dados não criptografados na memória principal, você deve considerar as gravações na memória principal como observáveis.

Basicamente, não existe uma noção única de equivalência de programa; é sempre relativo à noção de observação que você escolhe, e isso depende da aplicação que você tem em mente.

Neel Krishnaswami
fonte
1
Vale ressaltar que também não existe uma noção única de equivalência contextual (ou congruência contextual), por exemplo, se a linguagem de programação em questão é interativa (ou seja, não gera um valor).
Martin Berger
α
1
αα
1
@ SamTobin-Hochstadt. Ok, vamos esquecer o "habitual". A sensação que sinto é que você está dizendo a mesma coisa que Neel disse, o que foi bem pensado na minha opinião. Sua idéia, que ainda é vaga para mim, pode ser formalizada na estrutura de Neel, escolhendo o tipo certo de observação e o tipo certo de contexto do programa.
quer
1
λλx.xλy.y
2

P2: Eu acho que as definições teóricas usuais não distinguem realmente algoritmos e programas, mas o "algoritmo", como comumente usado, é mais como uma classe de programas. Para mim, um algoritmo é como um programa com algumas sub-rotinas deixadas não totalmente especificadas (ou seja, seu comportamento desejado é definido, mas não sua implementação). Por exemplo, o algoritmo de eliminação gaussiano não especifica realmente como a multiplicação de números inteiros deve ser realizada.

Sinto muito se isso é ingênuo. Eu não faço pesquisa PL.

Sasho Nikolov
fonte
A idéia é provavelmente que existem várias implementações para essas sub-rotinas e você não se importa com o que é escolhido, desde que seja executado de acordo com sua especificação.
Raphael