Pode-se automatizar a análise algorítmica?

8

Alguém já pensou na possibilidade de uma linguagem de programação e de um compilador, de modo que o compilador possa fazer automaticamente a análise assintótica do pior caso? O caso de uso que tenho em mente é uma linguagem de programação na qual escrevo código e compilo. O compilador me diz que meu código é executado em O (n ^ 2) (por exemplo). Faz isso fazendo o que as pessoas inteligentes que fazem análise algorítmica fazem, possivelmente contando loops e assim por diante.

  • Devido a problemas de interrupção de problemas, e como é possível ter programas que funcionam de maneira combinada, por exemplo, o algoritmo de Levin para SAT que é executado em tempo polinomial se P = NP, suspeito que seja necessário projetar a linguagem de programação para ser suficientemente restritiva para permitir algo assim. Existem resultados negativos, que excluem certos tipos de linguagens de programação de ter esses compiladores.

  • Eu também estaria interessado em sistemas que não fornecem uma análise assintótica exata, mas um limite superior "interessante".

  • Estou especificamente NÃO interessado em caixa preta e métodos estatísticos que amostra a partir de entradas de comprimento particular, e descobrir quanto tempo o programa leva. Esses métodos são muito interessantes, mas não são o que estou procurando. Estou interessado em métodos exatos que podem fornecer limites aproximados .

Ficaria muito grato se alguém pudesse me indicar algumas referências sobre o trabalho nessa direção.

manoj
fonte
5
Esta é uma possível duplicata da seguinte pergunta: cstheory.stackexchange.com/questions/12585/…
cody
as línguas óbvias que podem ser descartadas são Turing completas, já que o problema indecidível de interrupção ocorre em qualquer dessas línguas. então isso leva à pergunta: qual é uma linguagem mais limitada do que o completo de Turing para o qual isso é possível? mas, sem dúvida, uma linguagem não é uma "linguagem de programação", a menos que seja Turing completa. portanto, mais ou menos, tal objetivo é, basicamente, teoricamente impossível ... pode haver algumas idéias atenuantes para línguas complexidade limitada no entanto ...
vzn
A resposta é não, não podemos algorithmically distinguir mesmo entre o caso de que o programa é executado em tempo e . Consulte Os limites de tempo de execução em P são decidíveis? (supondo que a linguagem de programação seja expressiva o suficiente, ou seja, podemos simular outro programa para um determinado número de etapas). n 3n2n3
Kaveh
3
@ Kaveh Não concordo que minha pergunta seja uma duplicata de "Os limites de tempo de execução em P são decidíveis?". Eu já sabia como provar que é impossível. No entanto, obrigado por trazer esta discussão também à minha atenção! No entanto, é possível que minha pergunta seja uma pergunta duplicada, como apontado por cody.
Manoj
2
Quando eu era jovem e ingênuo, tentei escrever um analisador de complexidade usando o gcov . Dá a você o número de vezes que cada linha foi executada. :) Boa pergunta!
Pratik Deoghare

Respostas:

8

Complexidade implícita nos ensinou que (algumas) classes de complexidade podem ser classificadas por sistemas de tipos, no sentido de que existem sistemas de tipos que aceitam apenas programas polinomiais, por exemplo. Outra ramificação prática desta pesquisa é o RAML (Resource Aware ML), uma linguagem de programação funcional com um sistema de tipos que fornecerá informações precisas sobre os tempos de execução de seus programas. Na verdade, é mais preciso do que a complexidade do grande O, pois também são incluídos fatores constantes, parametrizados por um modelo de custo para as operações básicas.

Você pode pensar que isso é trapaça: certamente alguns algoritmos têm uma complexidade que é muito difícil de calcular com precisão, então como essa linguagem poderia determinar facilmente a complexidade de seus programas? O truque é que existem muitas maneiras de expressar um determinado algoritmo, algumas que o sistema de tipos rejeitará (ela rejeita alguns bons programas) e outras, talvez, que ele aceite. Portanto, o usuário não obtém o mundo de graça: ele não precisa mais calcular estimativas de custo, mas precisa descobrir como expressar o código de uma maneira que seja aceita pelo sistema.

(É sempre o mesmo truque, como nas linguagens de programação com apenas cálculos finais ou propriedades de segurança comprováveis ​​etc.)

gasche
fonte
Obrigado, esta é uma resposta muito interessante. Vou dar uma olhada em RAML.
Manoj
7

A ferramenta COSTA desenvolvida pelo grupo de pesquisa COSTA faz exatamente o que você deseja. Dado um programa (no formato Java bytecode), a ferramenta produz uma equação de custo com base em um modelo de custo fornecido pelo programador. O modelo de custo pode envolver entidades como tempo de execução, uso de memória ou eventos faturáveis ​​(como o envio de mensagens de texto). A equação de tempo de execução é então resolvida usando uma ferramenta dedicada para produzir um formulário fechado, o limite superior do pior caso do modelo de custo.

Naturalmente, a ferramenta não funciona em todos os casos, seja por não conseguir produzir uma equação de tempo de execução ou por não encontrar um formulário fechado. Isto não é surpreendente.

Dave Clarke
fonte
2

Na verdade, pensei na mesma pergunta há um tempo. Aqui está a linha de pensamento que eu tinha:

Como você disse, o problema da parada é um problema. Para evitar isso, precisamos de uma linguagem que permita apenas programas que sempre parem. Por outro lado, nossa linguagem precisa ser expressiva o suficiente para lidar com os problemas mais comuns (por exemplo, deve capturar pelo menos toda a classe de complexidade EXP).

Então, vamos olhar para os programas LOOP. Um programa LOOP sempre para e sua expressividade está muito além da EXP - para ter uma idéia melhor: você pode simular qualquer TM para a qual a função de tempo de execução possa ser expressa como programa LOOP.

Agora, podemos olhar para a profundidade do aninhamento e a magnitude do número de repetições para cada loop, de um ponto de vista sintático e temos um ponto de partida (não sabemos até onde isso nos leva). No entanto, considere o seguinte problema:

Queremos implementar a função :f(n)

y n y > nf(n)=y tal que é o primeiro número primo depois de comyny>n

Vamos assumir que temos uma função que nos diz se um número é primo ou não. Então, para implementar maioria de nós provavelmente escreveria algo como:n f ( n )p(n)nf(n)

y := n + 1
while not prime(y) 
    y++
return y

Agora, como vamos fazer isso apenas com loops limitados? O problema agora é pensar em um limite superior para o intervalo de números que precisamos pesquisar.

Mas era isso que queríamos que nosso compilador nos dissesse de algum modo! Então, acabamos de mudar o problema de refletir sobre a complexidade do tempo para o programador. A propósito, a frase a seguir nos dá o limite superior para o nosso problema:

 prime pa prime p:p<pp!+1

Minha intuição aqui é que a única informação que um compilador pode fornecer é a análise cuidadosa da sintaxe que, no final, é fornecida pelo programador. Portanto, permitir que o compilador faça uma declaração significativa sobre a complexidade do tempo de um programa significa forçar o programador a incorporar essas informações no programa.

No entanto, o último parágrafo é subjetivo e certamente pode haver outras abordagens possíveis que produzam resultados interessantes. Eu só queria dar uma idéia do que não esperar ao seguir esse caminho.

John D.
fonte
2
A profundidade de aninhamento de loops é a questão principal aqui, e a complexidade varia sobre as funções recursivas primitivas, consulte A complexidade dos programas de loop , Meyer & Ritchie, ACM '67 Conference, dx.doi.org/10.1145/800196.806014 .
21413 Sylvain
Obrigado. Eu acho que você faz uma boa observação aqui. Existe um problema se eu for executar loops do tipo enquanto (predicado = true) fizer alguma coisa, porque então eu tenho que discutir sobre a primeira vez que o predicado se tornar falso. Para reformular minha pergunta dentro do contexto que você definiu, pergunto-me se é possível projetar um monte de primitivas, com um tempo de execução bem definido, que pode ser composto de maneiras simples para escrever programas interessantes e obter limites de tempo de execução para eles. . Talvez o RAML já faça isso, como apontado pela primeira resposta.
Manoj
1
Para dar mais indicações desse tipo, a dificuldade computacional intrínseca de funções de Cobham é freqüentemente citada como um dos primeiros trabalhos sobre complexidade implícita: caracteriza FP por meio de esquemas de recursão. Você encontrará trabalhos mais recentes nessa linha de Bellatoni & Cook em Uma nova caracterização teórica da recursão das funções de politimo , Computational Complexity 1992. Veja também uma pesquisa de Hofmann em SIGACT News 31 (1): 31--42, 2000: dx.doi.org/10.1145/346048.346051 .
Sylvain
Obrigado Sylvain, estou dando uma olhada na pesquisa! Eu conhecia essa área da teoria da complexidade implícita, mas nunca me preocupei em estudá-la, devido à falta de apreciação do que é a pergunta básica que eles estão tentando responder. Agora tenho mais motivação para entender essas idéias!
Manoj