Provando a Correção de Memorização em Lean: Um Estudo de Caso

Esta postagem de blog demonstra como resolver um problema de programação dinâmica usando memorização no demonstrador de teoremas Lean e verificar formalmente sua correção. O autor aborda o problema das Moedas de Ouro Bytelandianas, apresentando inicialmente uma solução memorizada usando um HashMap. A dificuldade de provar diretamente sua correção é destacada devido aos desafios em raciocinar sobre invariantes de estrutura de dados. A solução utiliza subtipos e pares dependentes para criar um `PropMap`, uma tabela de memorização que armazena não apenas valores calculados, mas também provas de sua correção. A correção do algoritmo é então provada incrementalmente dentro da própria implementação recursiva, culminando em uma prova de nível superior trivial. Essa abordagem interliga elegantemente código e prova, mostrando uma técnica poderosa para verificar formalmente algoritmos de programação dinâmica.