derivação programa - Program derivation

Em ciência da computação , programa de derivação é a derivação de um programa a partir da especificação, por meio matemáticas.

Para derivar um programa significa para escrever uma especificação formal, que geralmente é não-executável e, em seguida, aplicar as regras matematicamente corretos, a fim de obter um programa executável satisfazer essa especificação. O programa assim obtido é, em seguida, por construção correcta. Programa e correção prova são construídos em conjunto.

A abordagem geralmente tomada na verificação formal é a primeira a escrever um programa e, em seguida, fornecer uma prova de que ele está em conformidade com uma determinada especificação . Os principais problemas com isso são que

  • a prova resultante é muitas vezes longo e complicado;
  • nenhum insight é dada quanto à forma como o programa foi desenvolvido; ele aparece "como um coelho fora de um chapéu";
  • se o programa acontecerá a ser incorreta de alguma forma sutil, a tentativa de verificar isso é provável que seja longa e certo que será infrutífera.

derivação programa tenta obviar essas carências

  • mantendo provas mais curtas, pelo desenvolvimento de notações matemáticas adequadas;
  • a tomada de decisões de design através da manipulação formal da especificação.

Termos que são mais ou menos sinônimo de derivação programa são: programação transformacional, algorithmics, programação dedutivo.

O Bird-Meertens Formalismo é uma abordagem para derivação programa.

Veja também

Referências

  • Edsger Dijkstra , Wim HJ Feijen, Um Método de Programação , Addison-Wesley, 1988, 188 páginas
  • Edward Cohen, Programação na década de 1990 , Springer-Verlag, 1990
  • Anne Kaldewaij, Programação: a derivação de algoritmos , Prentice-Hall, 1990, 216 páginas
  • David Gries, The Science of Programming , Springer-Verlag, 1981, 350 páginas
  • Carroll Morgan (cientista da computação) , Programação de Especificações , Série Internacional em Ciência da Computação (2ª ed.), Prentice-Hall, 1998.
  • Eric CR Hehner , uma Teoria Prática de Programação , 2008, 235 páginas
  • AJM van Gasteren. A forma de argumentos matemáticos . Lecture Notes in Computer Science # 445, Springer-Verlag, 1990. Ensina como escrever provas com clareza e precisão.
  • Martin Rem. "Exercícios Pequenas programação", apareceu em Science of Computer Programming , Vol.3 (1983) através Vol.14 (1990).
  • Roland Backhouse. Programa de Construção: Cálculo implementações de Especificações . Wiley, 2003. ISBN  978-0-470-84882-1 .
  • Derrick G. Kourie, Bruce W. Watson. A abordagem Correção-by-Construção à programação . Springer-Verlag, 2012. ISBN  978-3-642-27919-5 . Fornece uma explicação passo-a-passo de como derivar matematicamente algoritmos corretos, utilizando pequenas e tratáveis refinamentos.