Así se demuestra formalmente un DFA en Lean: el reto de verificar que la suma de dos filas de bits es regular

Anatomy of a Lean proof for software engineers

El autor formaliza en Lean un problema clásico de teoría de la computación: probar que el lenguaje de columnas de bits donde la fila inferior es la suma de las dos superiores es regular. Como un DFA lee de izquierda a derecha, construye un autómata que reconoce el lenguaje invertido y luego usa la propiedad de cierre del reverso. El artículo muestra paso a paso la especificación, la implementación y la prueba inductiva, ofreciendo a los ingenieros de software una idea concreta de qué implica verificar propiedades de un sistema con un asistente de pruebas.

El truco es recordar cómo sumas números a mano: trabajas desde el dígito menos significativo al más significativo. Lo único que arrastras de una columna a la siguiente es el acarreo.
  1. thom

    Entonces, todo esto está muy bien, pero dado que se nos pide aceptar pruebas Lean de más de 500 000 líneas que compilan pero que podrían tener fácilmente errores semánticos importantes ocultos en ellas, ¿cuál es el plan? Estos parecen artefactos de software singularmente frágiles, a pesar de las excelentes y robustas promesas hechas por el runtime.

  2. WalterGR

    OP: Tu artículo muestra «[Contents]» donde se supone que se debe mostrar la tabla de contenidos.

  3. fooker

    Por favor, no intentes entender Lean o los asistentes de pruebas sin antes obtener una comprensión rudimentaria de la lógica involucrada. Este artículo pasa un poco por alto eso, lo cual es razonable porque es bastante complejo.

    Incluso si has escrito una gran cantidad de pruebas matemáticas, normalmente no habrías aprendido el lenguaje o la lógica de las pruebas en sí. Y aunque seas un informático consumado, la lógica no es solo AND, OR, NOT.

    Aquí tienes algunas lecturas necesarias; siéntete libre de buscar mejores fuentes, pero Wikipedia también está bien.

    * Árboles de prueba - https://en.wikipedia.org/wiki/Method_of_analytic_tableaux

    * Lógica constructiva/intuicionista - https://en.wikipedia.org/wiki/Intuitionistic_logic

    * Pruebas y tipos - https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...

    * (In)completitud - https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...

    * Compacidad - https://en.wikipedia.org/wiki/Compactness_theorem

  4. whattheheckheck

    la interfaz entre especificación y prueba no es tan clara, ya que a menudo uno tiene que mirar la prueba para entender la especificación. Y si vemos algo raro en la prueba, eso es un buen indicio de que algo anda mal.

    Sí, esto es como si yo digo que algo es verde, ¿cómo sabes que mi verde es tu verde? La prueba del sistema modelado matemáticamente no está de ninguna manera ligada a los símbolos que lo implementan, a menos que sea el mismo programa o estés haciendo refinamiento de trazas. Y luego no hay forma de probar que el programa es correcto al servir la función de negocio a menos que lo ejecutes. Bastante irreducible computacionalmente, la máquina de estados de construir máquinas de estados.

  5. woggy

    Tengo curiosidad por saber si la gente puede usar Lean principalmente como un lenguaje de especificación de software, sin necesariamente pretender probarlo todo.

    ¿Podemos usarlo para especificar significados y leyes de módulos, para hacer el diseño preciso y verificable, y que nos permita implementar pruebas basadas en propiedades para esas leyes en nuestra implementación? Lean se convierte en una herramienta para pensar con mayor precisión sobre el diseño.

Más de este día

2026-10-02