Minimização de Programas

10

Minimização de circuitos é o problema para minimizar o tamanho de um determinado circuito. Existe algo semelhante para programas gerais?

Em particular, minha pergunta é -

Existem algoritmos para minimizar o número de instruções para um determinado programa. Sei que é um problema indecidível, mas não estou procurando uma solução que retorne algo ideal.

Embora se possa aplicar transformações de compilador preexistentes para fazer isso, estou procurando por algo em que não precise definir um conjunto de transformações e algoritmos muito restritos para procurá-los com antecedência.

Edit: A outra pergunta que tenho é se alguém pode ter um cálculo sólido e completo que nos permita explorar todo o espaço desses programas semanticamente equivalentes ou se isso não é possível.

Optar
fonte
2
A resposta para sua outra pergunta depende da sua definição de "um cálculo". O fato de o HALT não estar em coRE torna a resposta "não" para a maioria dessas definições.
fn

Respostas:

10

Existe um algoritmo ingênuo para programas com entradas de tamanho limitado: enumere todos os programas em ordem crescente de comprimento (ou tempo de execução, que é uma função limitada do comprimento). Se você puder provar que o programa é equivalente ao original, pare; caso contrário, continue pesquisando.

Este algoritmo é sólido. Para que seja concluído, você precisa provar que todos os programas rejeitados não são equivalentes ao original. Isso é possível nos modelos de máquinas finitas, desde que você tenha um limite para o tamanho da entrada.

Observe que quando o tempo de execução do programa depende da entrada, pode não haver uma solução ideal. Se você procurar, por exemplo, um limite de pior caso, encontrará rapidamente equivalências indecidíveis ao quantificar todas as entradas ilimitadas possíveis e problemas irrecuperáveis ​​se as entradas forem limitadas.

Há uma década, “Denali: um super otimizador direcionado a objetivos” de Rajeev Joshi, Greg Nelson e Keith Randall conseguiu encontrar programas ideais de cerca de 5 instruções da máquina. Eu não olhei para resultados mais recentes.

Gilles 'SO- parar de ser mau'
fonte
5
Um de nossos alunos aqui na Universidade de Sussex usou a super otimização para reduzir o comprimento de algumas rotinas básicas do Java (como a adição). Ele queimou enormes quantidades de computação no Amazon EC2 para fazer isso. Sua dissertação está aqui . Claramente, não é uma abordagem viável para nada além de programas realmente curtos.
22878 Martin Berger #