Quando foi que você se depara com o problema da parada no campo? [fechadas]
https://stackoverflow.com/questions/235984
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Quando você já pessoalmente vir sobre o problema da parada no campo? Isso pode ser quando um colega de trabalho / chefe sugeriu uma solução que violaria os limites fundamentais da computação, ou quando se percebeu que um problema que você estava tentando resolver era, de fato, impossível de resolver.
A época mais recente que veio com ele foi quando se estuda damas tipo. Nossa classe percebeu que seria impossível escrever um verificador tipo perfeito (aquele que iria aceitar todos os programas que são executados sem erros de tipo, e rejeitar todos os programas que são executados com erros de tipo), porque isso seria, de fato, resolver o problema da parada . Outra foi quando percebemos, na mesma classe, que seria impossível determinar se uma divisão nunca iria ocorrer até zero, na fase de verificação de tipo, porque verificar se um número, em tempo de execução, é zero, é também uma versão do problema da parada.
Solução
I literalmente foi atribuído o problema da parada, como em "escrever um monitor de plugin para determinar se um host está permanentemente para baixo". Seriamente? OK, então eu vou apenas dar-lhe um limite. "Não, porque ele pode voltar para cima depois."
Muita exposição teórica seguiu.
Outras dicas
Anos atrás, eu lembro de ter lido uma revisão (na revista Byte, creio eu) de um produto chamado Básico Infinite Loop Finder ou BILF. BILF deveria analisar o seu código-fonte Microsoft Basic e encontrar laços que não cessaram. Ele alegou ser capaz qualquer encontrar loops infinitos no código.
O revisor foi suficiente savvy ressaltar que para esse programa de trabalho em todos os casos, ele teria que resolver o problema da parada e foi tão longe como para fornecer uma prova matemática de por que ele não poderia trabalhar em todos os casos.
Na próxima edição, eles publicaram uma carta de um representante da empresa, explicando que o problema seria corrigido na próxima versão.
Update: deparei com uma imagem do artigo sobre imgur. Lembrei-me da revista errado. Foi criativa Computing, não Byte. Caso contrário, ele é muito bonito como eu lembrava.
Você pode ver uma versão hi-res dele em imgur .
O projeto que estou trabalhando agora tem problemas indecidíveis tudo sobre ele. É um gerador de teste de unidade, de modo em geral o que ele tenta fazer é responder à pergunta "o que este programa faz" . Que é uma instância de um problema da parada. Outro problema que surgiu durante o desenvolvimento é "são dadas duas funções (de teste) o mesmo" ? Ou mesmo "faz a ordem dessas duas chamadas (afirmações) matéria" ?
O que é interessante sobre este projeto é que, mesmo que você não pode responder a essas perguntas em todas situações, você pode encontrar soluções inteligentes que resolvam o problema de 90% dos o tempo, que para este domínio é realmente muito bom.
Outras ferramentas que tentam raciocinar sobre outros códigos, como otimização de compiladores / intérpretes, ferramentas de análise estática de código, mesmo ferramentas de refatoração, são susceptíveis de hit (assim ser forçado a encontrar soluções para) o problema da parada.
Exemplo 1. Como muitas páginas do meu relatório?
Quando eu estava aprendendo a programar eu joguei com tornando uma ferramenta para imprimir relatórios bonitas de dados. Obviamente, eu queria que fosse realmente flexível e poderosa por isso seria o gerador de relatórios para acabar com todos os geradores de relatórios.
A definição do relatório acabou sendo tão flexível que foi Turing completa. Ele podia olhar para variáveis, escolha entre alternativas, loops de uso para coisas repetidas.
I definido um built-in N variável, o número de páginas na instância de relatório, assim que você poderia colocar uma corda que dizia "página n de N" em cada página. Fiz duas passagens, a primeira a contar as páginas (durante o qual N foi definido como zero), e o segundo que realmente gerá-los, utilizando o N obtido a partir da primeira passagem.
Às vezes, o primeiro passo seria calcular N, e depois a segunda passagem geraria um número diferente de páginas (porque agora o diferente de zero N mudaria o que o relatório fez). Eu tentei fazer passes de forma iterativa até que o N se estabeleceram. Então eu percebi que isso era impossível porque o que se não se estabelecer?
Isto, então leva à pergunta: "Posso pelo menos detectar e avisar o utilizador se a iteração é nunca vai resolver em um valor estável para o número de páginas seu relatório produz?" Felizmente por esta altura eu tinha se interessado em ler sobre Turing, Godel, computability etc. e fez a ligação.
Anos mais tarde, notei que MS Access, por vezes, imprime "Page 6 de 5", que é uma coisa superiormente marcado.
O processo de compilação envolve expandir modelos. definições de modelo pode ser selecionado a partir de várias especializações (bom o suficiente para servir como um "cond") e eles também podem ser recursiva. Portanto, é um meta-sistema (funcional pura) Turing completa, em que as definições de modelo são a linguagem, os tipos são os valores, eo compilador é realmente um intérprete. Este foi um acidente.
Por conseguinte, não é possível examinar qualquer programa dado C ++ e dizer se o compilador poderia, em princípio, terminar com uma compilação bem-sucedida do programa.
Compiler fornecedores de contornar esta situação, limitando a profundidade da pilha de recursiva de modelo. Você pode ajustar a profundidade em g ++.
Muitas muitas luas atrás eu estava ajudando um consultor para a nossa empresa que foi a implementação de um sistema ferroviário muito complexo para mover cestas de peças metálicas dentro e fora de um alto-forno de 1.500 graus. A pista em si era um pouco complexa 'mini-railyard' no chão de fábrica que se cruzaram em um par de lugares. Vários paletes motorizados seria cestos de transporte de peças em torno de acordo com um cronograma. Era muito importante que as portas de fornos estavam abertos durante o tempo que um curto possível.
Uma vez que a planta estava em plena produção, o consultor foi incapaz de executar o seu software em 'tempo real' para testar seus algoritmos de escalonamento. Em vez disso, ele escreveu um simulador consideravelmente, gráfico-y. Enquanto observávamos paletes virtuais se movimentar em seu traçado na tela, eu perguntei "como você vai saber se você tem quaisquer conflitos de agenda?"
Sua resposta rápida, "Easy -. A simulação nunca vai parar"
análise estática de código sofisticado pode correr para o problema da parada.
Por exemplo, se uma máquina virtual Java pode provar que um pedaço de código nunca irá acessar um índice de matriz fora dos limites, pode omitir que o check e correr mais rápido. Por algum código isso é possível; como fica mais complexo se torna o problema da parada.
Este ainda é um problema para shaders em aplicações GPU. Se um shader tem um loop infinito (ou um tempo muito longo de cálculo), caso o driver (depois de algum limite de tempo) pará-lo, matar o fragmento, ou simplesmente deixá-lo correr? Para os jogos e outras coisas comercial, o primeiro é provavelmente o que você quer, mas para a Computação Científica / GPU, o último é o que você quer. Pior, algumas versões do Windows supor que uma vez que o driver gráfico tem sido responder por algum tempo, ele mata-lo, o que limita artificialmente o poder de computação quando se faz a computação na GPU.
Não há nenhuma API para uma aplicação para controlar como o motorista deve se comportar ou definir o tempo limite ou algo assim, e não há dúvida nenhuma maneira para que o motorista para dizer se o seu shader vai terminar ou não.
Eu não sei se esta situação melhorou recentemente, mas eu gostaria de saber.
Outra versão comum é "precisamos eliminar quaisquer bloqueios em nosso código multi-thread". Um pedido perfeitamente razoável, do ponto de vista de gestão, mas, a fim de evitar impasses no caso geral, você tem que analisar cada possível estado de bloqueio que o software pode entrar, que é, sem surpresa, equivalente ao problema da parada.
Existem maneiras de se parcialmente "resolver" impasses em um sistema complexo, impondo uma outra camada em cima do bloqueio (como uma ordem definida de aquisição), mas estes métodos nem sempre são aplicáveis.
Por que isso é equivalente ao problema da parada:
Imagine que você tem dois bloqueios, A e B, e duas linhas, X e Y. Se rosca X tem bloqueio A, e quer bloqueio B também, e linha Y tem bloqueio B e quer um também, então você tem um impasse .
Se ambos X e Y têm acesso a ambos A e B, então a única maneira de garantir que você nunca entrar em estado ruim é determinar todos os possíveis caminhos que cada thread pode tomar através do código, ea ordem em que eles podem adquirir e fechaduras de espera em todos esses casos. Então você determinar se os dois segmentos podem sempre adquirir mais de um bloqueio em uma ordem diferente.
Mas, determinar todos os possíveis caminhos que cada thread pode tomar através do código é (no caso geral) equivalente ao problema da parada.
sistema de teste do Perl mantém um contador de teste. Você quer colocar o número de testes que você vai correr no topo do programa, ou você declara que não vai segui-lo. Este guarda contra o seu teste de sair prematuramente, mas há outros guardas por isso não é tão importante.
De vez em quando tenta alguém para escrever um programa para contar o número de testes para você. Isto é, naturalmente, derrotado por um loop simples. Eles arar adiante de qualquer maneira, fazendo mais e mais elaborada truques para tentar detectar loops e adivinhar quantas iterações haverá e resolver o problema da parada. Normalmente, eles declaram que ele só tem que ser "bom o suficiente".
Certa vez eu estava trabalhando em um projeto de integração no domínio ATM (Automated Teller Machines). O cliente pediu-me para gerar um relatório do meu sistema para transações enviadas pelo switch país que não foram recebidos pelo meu sistema !!
Eu encontrei um papel Berkeley: Looper: Detecção leve de loops infinitos no tempo de execução http://www.eecs.berkeley.edu/~jburnim/pubs /BurnimJalbertStergiouSen-ASE09.pdf
LOOPER pode ser útil, pois a maioria dos loops infinitos são erros triviais. No entanto, este artigo nem sequer menciona o problema da parada!
O que eles dizem sobre as suas limitações?
[LOOPER] tipicamente não pode razão sobre loops, onde não terminação depende das indicações de mutação pilha em cada iteração. Isso é porque nossa execução simbólico é na conservadora concretizando ponteiros e nosso raciocínio simbólico insuficientemente poderoso. Acreditamos que a combinação de nossas técnicas com análise da forma e mais poderosa geração invariante e provando seria valioso trabalho futuro.
Em outras palavras, "o problema será corrigido na próxima versão".
A partir da Visão geral funcional de (Eclipse) Visual Editor de :
O Visual Editor do Eclipse (VE) pode ser usado para abrir qualquer .java arquivo. Isso então analisa o código-fonte Java procura para o feijão visuais. ...
Algumas ferramentas de edição visual só irá fornecer um modelo visual do código que que determinada ferramenta visual em si tem gerado. edição directo subsequente do código-fonte pode impedir a ferramenta visual de analisar o código e construção de um modelo.
Eclipse VE, no entanto, ... pode ser usado para editar GUIs a partir do zero, ou a partir de arquivos Java que têm sido 'Codificado' ou construído de uma forma diferente ferramenta visual. A lata arquivo de origem quer ser atualizado usando o Graphical Viewer, JavaBeans árvore ou propriedades vista ou podem ser editados diretamente por o editor de fonte.
Talvez eu devesse ficar com Matisse por agora.
Não relacionado, está aqui alguém pedindo o problema da parada dentro do Eclipse.
Para ser justo, VE de domínio é bastante limitado, e provavelmente não vai ficar louco por coisas difíceis, como reflexão. Ainda assim, a pretensão de construir GUI fora do qualquer arquivo java parece deter-ish.
"Como você pode me garantir o seu código é 100% livre de bugs?"
