Trabalho de conclusão de curso sobre programação por restrições

Visão geral

Como estudante de graduação em ciência da computação, minha pesquisa partiu de uma pergunta prática: quando um simulador acumula muitas condições possíveis, como fazer com que ele pare de reconsiderar aquelas que já não podem ocorrer? Desenvolvi e avaliei um método para o HydLa que usa a direção em que um valor está mudando para retirar da busca as condições que perderam a validade. No modelo de referência, o tempo total de simulação caiu para cerca da metade.

Este trabalho é um dos primeiros alicerces da minha filosofia de design. A programação por restrições me ensinou que resultados complexos não precisam sempre ser especificados diretamente: eles podem emergir de um espaço de regras, prioridades e limites definido com cuidado. Esse modo de pensar sustenta hoje a minha maneira de projetar a partir de restrições na era da IA — projetar as condições dentro das quais um sistema generativo fica livre para agir.

Resumo

O HydLa é uma linguagem de modelagem para sistemas híbridos: sistemas em que mudança contínua e eventos discretos interagem. Seu projeto baseado em restrições permite descrever esses sistemas de forma concisa e simulá-los com alta precisão. O custo é que, em um modelo grande, o simulador pode ficar verificando um número enorme de regras condicionais, mesmo depois de algumas terem se tornado irrelevantes.

Esta pesquisa propôs reduzir essas restrições com guarda dinamicamente. Ao reconhecer um comportamento monotônico — um valor que continua se movendo em uma só direção —, o simulador pode determinar que certas guardas nunca se tornarão verdadeiras no futuro e parar de verificá-las com segurança. A abordagem foi especialmente eficaz em um modelo com muitos objetos guardados da mesma forma, no qual o tempo de execução medido caiu para aproximadamente metade do original.

1. Introdução

Um sistema híbrido combina comportamento contínuo com eventos discretos. Uma bola quicando é um exemplo simples: sua posição e sua velocidade mudam continuamente enquanto ela está no ar, mas o instante em que atinge uma superfície cria um evento discreto que muda sua direção. Termostatos, veículos e robôs contêm versões mais consequentes dessa mesma mistura.

O HydLa permite descrever esses sistemas com restrições matemáticas e lógicas, em vez de escrever uma única sequência procedural. Seu simulador, o HyLaGI, faz cálculo simbólico sem erro de arredondamento e trabalha com parâmetros incertos. Essa abordagem expressiva, no entanto, cria um problema de escala: quando um modelo contém muitas regras que se ativam apenas sob condições específicas, o simulador precisa perguntar repetidamente se cada condição pode ser a próxima a ocorrer.

2. Restrições com guarda na simulação

Uma restrição com guarda é uma regra que só se torna ativa quando sua condição de guarda é satisfeita. No modelo de referência acima, cada trecho da superfície tem sua própria regra: se a bola chega à altura zero enquanto sua posição horizontal está dentro daquele trecho, a regra do quique se aplica. Dividir a superfície em mais partes dá, portanto, ao simulador mais guardas para inspecionar.

O experimento variou o número de trechos de 10 a 200. O simulador original ficava mais lento aproximadamente com o quadrado desse número. Isso importa além do exemplo de brinquedo: um modelo maior pode representar muitos objetos físicos, regiões de contato ou eventos possíveis exatamente nessa forma guardada.

3. Localização do gargalo

A análise de desempenho mostrou que a lentidão não estava distribuída uniformemente pelo simulador. Com 100 trechos de superfície, 96% do tempo de execução medido foi gasto em FindMinTime, a operação que procura o próximo evento possível mais próximo. Ela reavaliava repetidamente as guardas de todas as restrições candidatas.

Esse resultado tornou específico o alvo da otimização: reduzir o número de guardas que o FindMinTime tem de considerar, preservando exatamente o mesmo comportamento simulado.

4. Redução das restrições com guarda

Imagine uma bola descendo uma escada aos quiques. Depois que a bola passa de um degrau e segue adiante, aquele degrau não pode mais afetá-la. Quem olha o diagrama descarta na hora os degraus que ficaram atrás; o algoritmo original continuava verificando todos eles.

A parte difícil é provar que uma guarda descartada não voltará a ser necessária depois. Removê-la apenas porque agora é falsa poderia produzir silenciosamente um resultado errado caso ela volte a ser verdadeira. Por isso a proposta se apoia na monotonicidade: se está garantido que uma variável continuará crescendo, ou continuará decrescendo, ao longo de um intervalo de tempo.

4.1 Abordagem para a monotonicidade uniforme

A primeira abordagem se aplica quando uma variável se move em uma só direção durante toda a simulação. No modelo da superfície dividida, a posição horizontal da bola sempre cresce. Depois que ela passa de um trecho, a condição daquele trecho nunca pode ser satisfeita novamente. Técnicas de verificação de modelos permitem estabelecer essa propriedade antes da simulação, de modo que as guardas obsoletas podem ser removidas com segurança conforme a execução avança.

4.2 Abordagem para a monotonicidade alternada

Muitos sistemas reais não se movem em uma só direção para sempre. Uma variável pode crescer, virar e então decrescer. O artigo esboçou, por isso, uma segunda abordagem: começar com uma direção suposta, monitorar essa suposição com asserções e reiniciar a lógica de redução a partir do ponto em que a direção muda. As guardas removidas para um intervalo monotônico são restauradas quando o intervalo seguinte começa.

5. Resultados experimentais

Implementei a abordagem da monotonicidade uniforme e a avaliei com o modelo da superfície dividida. Tanto o algoritmo original quanto o proposto continuavam levando mais tempo à medida que o número de trechos crescia, mas a versão proposta fazia consistentemente menos trabalho. Comparando as curvas ajustadas, o coeficiente principal caiu de 1,1463 para 0,6083; para este caso de referência, o tempo total de simulação caiu para cerca da metade.

O resultado não afirma que todo modelo HydLa fique duas vezes mais rápido. Ele mostra onde o método ajuda: em modelos com muitos objetos guardados e uma direção de mudança demonstrável, nos quais as guardas se tornam permanentemente irrelevantes durante a execução.

6. Conclusão e trabalhos futuros

A pesquisa demonstrou que o conhecimento sobre um modelo — e não apenas um cálculo de baixo nível mais rápido — pode tornar a simulação mais eficiente. Usando a monotonicidade para reconhecer quais possibilidades se tornaram impossíveis, o HyLaGI consegue encolher seu conjunto de restrições ativas sem alterar o resultado.

O experimento implementado cobriu a monotonicidade uniforme. O artigo deixou duas direções para depois: avaliar o método baseado em asserções para o comportamento alternado e usar invariantes além da monotonicidade para identificar mais restrições que possam ser removidas com segurança.