Dafny es un lenguaje compilado funcional e imperativo que compila a otros lenguajes de programación , como C# , Java , JavaScript , Go y Python . Admite especificaciones formales a través de precondiciones , poscondiciones , invariantes de bucle , variantes de bucle , especificaciones de terminación y especificaciones de encuadre de lectura/escritura. El lenguaje combina ideas de los paradigmas funcional e imperativo ; incluye soporte para programación orientada a objetos . Las características incluyen clases genéricas , asignación dinámica , tipos de datos inductivos y una variación de la lógica de separación conocida como marcos dinámicos implícitos [1] para razonar sobre efectos secundarios. [2] Dafny fue creado por Rustan Leino en Microsoft Research después de su trabajo previo en el desarrollo de ESC/Modula-3, ESC/Java y Spec#.
Dafny se utiliza ampliamente en la enseñanza [ cita requerida ] porque proporciona una introducción simple e integrada a la especificación y verificación formal; aparece regularmente en competiciones de verificación de software (por ejemplo, VSTTE'08, [3] VSCOMP'10, [4] COST'11, [5] y VerifyThis'12 [6] ).
Dafny fue diseñado como un lenguaje de programación que tiene en cuenta la verificación, que requiere verificación junto con el desarrollo del código. Por lo tanto, se ajusta al paradigma de desarrollo de software "Corrección por construcción". Las pruebas de verificación están respaldadas por una caja de herramientas matemáticas que incluye números enteros y reales matemáticos, vectores de bits, secuencias, conjuntos, multiconjuntos, secuencias y conjuntos infinitos, inducción, co-inducción y pruebas de cálculo. Las obligaciones de verificación se descargan automáticamente, dada la especificación suficiente. Dafny utiliza algún análisis de programas para inferir muchas afirmaciones de especificación, lo que reduce la carga del usuario de escribir especificaciones. El marco de prueba general es el de la lógica de Hoare .
Dafny se basa en el lenguaje intermedio Boogie , que utiliza el demostrador de teoremas automatizado Z3 para cumplir con las obligaciones de prueba. [7] [8]
Dafny proporciona métodos para la implementación que pueden tener efectos secundarios y funciones para usar en la especificación que son puras . [9] Los métodos consisten en secuencias de declaraciones que siguen un estilo imperativo familiar mientras que, por el contrario, el cuerpo de una función es simplemente una expresión. Cualquier declaración con efectos secundarios en un método (por ejemplo, asignar un elemento de un parámetro de matriz) debe tenerse en cuenta al notar qué parámetros se pueden mutar, utilizando la modifiescláusula. Dafny también proporciona una gama de tipos de colección inmutablesseq<int> que incluyen: secuencias (por ejemplo, ), conjuntos (por ejemplo, set<int>), mapas ( map<int,int>), tuplas, tipos de datos inductivos y matrices mutables (por ejemplo, array<int>).
A continuación se ilustran muchas de las características de Dafny, incluido el uso de precondiciones, poscondiciones, invariantes de bucle y variantes de bucle.
método max ( arr : array < int > ) retorna ( max : int ) // El array debe tener al menos un elemento requiere arr . Length > 0 // El valor de retorno no puede ser menor que cualquier elemento del array asegura forall j : int :: j >= 0 && j < arr . Length ==> max >= arr [ j ] // El valor de retorno debe coincidir con algún elemento del array asegura que exista j : int :: j >= 0 && j < arr . Length && max == arr [ j ] { max : = arr [ 0 ] ; var i : int : = 1 ; // while ( i < arr . Length ) // Índice como máximo arr.Length (necesario para mostrar i==arr.Length después del bucle) invariante i <= arr . Longitud // Ningún elemento visto hasta ahora es mayor que max invariant forall j : int :: j >= 0 && j < i ==> max >= arr [ j ] // Algún elemento visto hasta ahora coincide con max invariant existe j : int :: j >= 0 && j < i && max == arr [ j ] // arr.Length - i disminuye en cada paso y está acotado inferiormente por 0 disminuciones arr . Length - i { // Actualizar max si se encuentra un elemento mayor if ( arr [ i ] > max ) { max : = arr [ i ] ; } // Continuar a través de la matriz i : = i + 1 ; } } Este ejemplo calcula el elemento máximo de una matriz. La condición previa y la condición posterior del método se proporcionan con las cláusulas requiresy ensures(respectivamente). Del mismo modo, la invariante de bucle y la variante de bucle se proporcionan mediante las cláusulas invarianty decreases(respectivamente).
El tratamiento de los invariantes de bucle en Dafny difiere de la lógica tradicional de Hoare . Las variables mutadas en un bucle se tratan de tal manera que (la mayor parte) de la información conocida sobre ellas antes del bucle se descarta. La información necesaria para demostrar las propiedades de dichas variables debe expresarse explícitamente en el invariante de bucle. Por el contrario, las variables no mutadas en el bucle conservan toda la información conocida sobre ellas de antemano. El siguiente ejemplo ilustra el uso de bucles:
método sumaAndZero ( arr : array < int > ) devuelve ( suma : nat ) requiere forall i :: 0 < = i < arr.Longitud == > arr [ i ] > = 0 modifica arr { var i : int : = 0 ; suma : = 0 ; // while ( i < arr.Longitud ) { suma : = suma + arr [ i ] ; arr [ i ] : = arr [ i ] ; i : = i + 1 ; } } Esto falla en la verificación porque Dafny no puede establecer que (sum + arr[i]) >= 0se cumple en la asignación. A partir de la condición previa, intuitivamente, forall i :: 0 <= i < arr.Length ==> arr[i] >= 0se cumple en el bucle ya que arr[i] := arr[i];es un NOP . Sin embargo, esta asignación hace que Dafny la trate arrcomo una variable mutable y elimine la información conocida sobre ella antes del bucle. Para verificar este programa en Dafny podemos (a) eliminar la asignación redundante arr[i] := arr[i];; o (b) agregar el invariante del bucleinvariant forall i :: 0 <= i < arr.Length ==> arr[i] >= 0
Dafny también emplea un análisis estático limitado para inferir invariantes de bucles simples cuando es posible. En el ejemplo anterior, parecería que invariant i >= 0también se requiere el invariante de bucles, ya que la variable ise muta dentro del bucle. Si bien la lógica subyacente requiere un invariante de este tipo, Dafny lo infiere automáticamente y, por lo tanto, se puede omitir en el nivel de la fuente.
Dafny incluye características que respaldan aún más su uso como asistente de pruebas . Aunque las pruebas de propiedades simples dentro de un functiono method(como se muestra arriba) no son inusuales para herramientas de esta naturaleza, Dafny también permite la prueba de propiedades entre uno functiony otro. Como es común para un asistente de pruebas , dichas pruebas son a menudo de naturaleza inductiva . Dafny es quizás inusual en el uso de la invocación de métodos como un mecanismo para aplicar la hipótesis inductiva. Lo siguiente lo ilustra:
tipo de datos Lista = Nil | Enlace ( datos : int , siguiente : Lista ) función suma ( l : Lista ): int { match l caso Nil => 0 caso Enlace ( d , n ) => d + suma ( n ) } predicado isNatList ( l : List ) { coincide con l caso Nil => caso verdadero Link ( d , n ) => d >= 0 && isNatList ( n ) } lema NatSumLemma ( l : List , n : int ) requiere isNatList ( l ) && n == sum ( l ) asegura que n >= 0 { match l case Nil => // Descargado automáticamente case Link ( data , next ) => { // Aplicar hipótesis inductiva NatSumLemma ( next , sum ( next )); // Verificar lo que sabe Dafny assert data >= 0 ; } } Aquí, NatSumLemmase demuestra una propiedad útil entre sum() y isNatList()(es decir, que isNatList(l) ==> (sum(l) >= 0)). El uso de a ghost methodpara codificar lemas y teoremas es estándar en Dafny con recursión empleada para inducción (típicamente, inducción estructural ). El análisis de casos se realiza utilizando matchdeclaraciones y los casos no inductivos a menudo se descargan automáticamente. El verificador también debe tener acceso completo al contenido de a functiono predicatepara poder desenrollarlos según sea necesario. Esto tiene implicaciones cuando se usa junto con modificadores de acceso . Específicamente, ocultar el contenido de a functionusando el protectedmodificador puede limitar qué propiedades se pueden establecer sobre él.