Um ambiente de tempo de execução pode detectar um loop infinito?

Seria possível para um ambiente de tempo de execução detectar loops infinitos e subsequentemente interromper o processo associado, ou implementar essa lógica seria equivalente a resolver o problema de parada?

Para os fins desta pergunta, defino um "loop infinito" para significar uma série de instruções e dados de pilha / pilha iniciais associados que, quando executados, retornam o processo exatamente ao mesmo estado (incluindo os dados) como estava antes iniciando o loop infinito. (Em outras palavras, um programa que gera uma expansão decimal indefinidamente longa de pi não é "preso" em um "loop infinito", porque a cada iteração, há mais dígitos de pi em algum lugar na memória associada.)

(Portado de /programming//q/16250472/1858225 )

Pode ser teoricamente possível para um ambiente de tempo de execução para verificar se esses laços usando o seguinte procedimento:

Após a execução das instruções, o ambiente de tempo de execução criaria uma imagem completa do estado de um processo em execução (ou seja, toda a memória associada a ele, incluindo registradores, PC, pilha, pilha e globais), salvaria a imagem em algum lugar e, em seguida, verificaria veja se corresponde a alguma de suas imagens salvas anteriormente para esse processo. Se houver uma correspondência, o processo ficará preso em um loop infinito. Caso contrário, a próxima instrução é executada e o processo é repetido.

De fato, em vez de executar essa verificação após cada instrução, o ambiente de tempo de execução pode simplesmente pausar o processo periodicamente e criar um estado de salvamento. Se o processo estiver preso em um loop infinito envolvendo n estados, depois de no máximo n verificações, será observado um estado duplicado.

Note, é claro, que essa não é uma solução para o problema da parada; a distinção é discutida aqui .

Mas esse recurso seria um enorme desperdício de recursos ; pausar continuamente um processo para economizar toda a memória associada a ele diminuiria tremendamente e consumiria uma quantidade enorme de memória rapidamente. (Embora as imagens antigas possam ser excluídas depois de um tempo, seria arriscado limitar o número total de imagens que poderiam ser salvas porque um loop infinito grande - ou seja, um com muitos estados - pode não ser capturado se houver muito poucos Além disso, esse recurso não traria tanto benefício, pois sua capacidade de capturar erros seria extremamente limitada e porque é relativamente simples encontrar loops infinitos com outros métodos de depuração (como simplesmente percorrer o código e reconhecendo o erro lógico).

Portanto, duvido que esse ambiente de tempo de execução exista ou que jamais exista, a menos que alguém o programa apenas por diversão. (O que estou um pouco tentado a fazer agora.)

Vamos supor que o programa não interaja com o mundo exterior; portanto, é realmente possível encapsular todo o estado do programa. (Isso significa que ele não faz nenhuma entrada, pelo menos.) Além disso, vamos supor que o programa esteja sendo executado em algum ambiente determinístico para que cada estado tenha um sucessor exclusivo, o que significa que o tempo de execução não é encadeado ou que o encadeamento pode ser reduzido deterministicamente a uma sequência.

Sob essas suposições altamente improváveis, mas teoricamente não limitativas, podemos duplicar o programa e executá-lo em dois tempos de execução separados; cada um fará exatamente o mesmo cálculo.

Então vamos fazer isso. Nós o executaremos uma vez no tempo de execução do Tortoise e, ao mesmo tempo, no tempo de execução do Hare. No entanto, providenciaremos para que o tempo de execução do Hare opere exatamente duas vezes mais rápido; toda vez que o tempo de execução do Tortoise dá um passo, o tempo de execução do Hare dá dois passos.

$n$$p$$kn$$k$$kn\ge p$

O custo total do teste é um estado extra e uma comparação de estado por etapa, e terminará em não mais que três vezes o número de etapas necessárias para o programa concluir seu primeiro loop. (Uma vez na tartaruga e duas vezes na lebre, totalizando três vezes.)

Como os termos que eu usei sugerem, esse é apenas o famoso algoritmo de detecção de ciclo Tortoise e Hare de Robert Floyd .

Assim como eu sugeria o algoritmo de detecção de ciclo de Floyd, o post de rici me superou. No entanto, tudo pode ser mais prático, acelerando as comparações de estados completos.

O gargalo do algoritmo proposto estaria na comparação de estado completo. Essas comparações geralmente não terminam, mas param mais cedo - na primeira diferença. Uma otimização é lembrar onde ocorreram as diferenças passadas e verificar primeiro essas partes do estado. Por exemplo, mantenha uma lista de locais e passe por essa lista antes de fazer uma comparação completa. Quando um local desta lista expuser uma diferença, pare a comparação (com falha) e mova o local para a frente da lista.

Uma abordagem diferente (e potencialmente mais escalável) é usar o hash incremental. Escolha uma função do estado completo para que os valores de hash sejam fáceis de ajustar em O (1) quando alguma parte do estado for alterada. Por exemplo, considere uma soma ponderada de palavras de estado modificada por algum primo grande e concatenar com o mod de soma não ponderada por algum outro primo grande (também pode gerar uma soma ponderada modular de quadrados de palavras, com peso e módulo diferentes). Dessa forma, as atualizações de hash levarão O (1) tempo em cada etapa de execução, e as comparações levarão O (1) tempo até que você seja atingido. A probabilidade de um falso positivo (ou seja, os hashes correspondem enquanto os estados diferem) é muito baixa e, mesmo que isso aconteça, ele será amortizado por um grande número de negativos verdadeiros (os negativos negativos são impossíveis).

Obviamente, na prática, parece mais provável que você entre em situações como gerar dígitos do número pi - as coisas continuam mudando, mas nunca terminam. Outra possibilidade frequente é que o loop infinito aloque memória e, nesse caso, esgote rapidamente toda a memória disponível.

No meu curso sobre algoritmos e estruturas de dados, nosso autograder tem que lidar com envios de alunos que às vezes entram em loops infinitos. Isso é resolvido com um tempo limite de 30 segundos e um determinado limite de memória. Ambos são muito mais flexíveis do que os orçamentos de tempo de execução e memória que impomos como parte da classificação. Não tenho certeza se a implementação da detecção verdadeira de loop infinito faria muito sentido nesse contexto, porque esses programas serão um pouco mais lentos (é aqui que o suporte a hardware para hash de estado pode ajudar, mas, novamente, você precisará de usos adicionais para justifique isso). Quando os alunos sabem que seu programa atingiu o tempo limite, geralmente podem encontrar o loop infinito.

A ferramenta de terminação AProVE executa análise estática em sistemas de reescrita (incluindo uma subclasse de programas Haskell) que podem provar a não terminação, fornecendo um exemplo real de programa sem terminação. A técnica é bastante poderosa e funciona usando uma variante de uma técnica chamada estreitamento .

Até onde eu sei, não houve muito trabalho para detectar a não rescisão real para idiomas gerais.