Síntesis del programa

En informática , la síntesis de programas es la tarea de construir un programa que satisfaga de manera demostrable una especificación formal de alto nivel dada . A diferencia de la verificación del programa , el programa debe construirse en lugar de darse; sin embargo, ambos campos utilizan técnicas de prueba formales y ambos comprenden enfoques de diferentes grados de automatización. A diferencia de las técnicas de programación automática , las especificaciones en la síntesis de programas suelen ser declaraciones no algorítmicas en un cálculo lógico apropiado . ^[1]

La aplicación principal de la síntesis de programas es aliviar al programador de la carga de escribir código correcto y eficiente que satisfaga una especificación. Sin embargo, la síntesis de programas también tiene aplicaciones para la superoptimización y la inferencia de invariantes de bucle . ^[2]

Origen

Durante el Instituto de Verano de Lógica Simbólica de la Universidad de Cornell en 1957, Alonzo Church definió el problema de sintetizar un circuito a partir de requisitos matemáticos. ^[3] Aunque el trabajo sólo se refiere a circuitos y no a programas, el trabajo se considera una de las primeras descripciones de síntesis de programas y algunos investigadores se refieren a la síntesis de programas como "El problema de la Iglesia". En la década de 1960, investigadores en inteligencia artificial exploraron una idea similar para un "programador automático". ^{[ cita necesaria ]}

Desde entonces, varias comunidades de investigación consideraron el problema de la síntesis de programas. Los trabajos notables incluyen el enfoque teórico de autómatas de 1969 de Büchi y Landweber , ^[4] y los trabajos de Manna y Waldinger (c. 1980). El desarrollo de lenguajes de programación modernos de alto nivel también puede entenderse como una forma de síntesis de programas.

Desarrollos del siglo XXI

A principios del siglo XXI se ha visto un aumento del interés práctico en la idea de la síntesis de programas en la comunidad de verificación formal y campos relacionados. Armando Solar-Lezama demostró que es posible codificar problemas de síntesis de programas en lógica booleana y utilizar algoritmos para el problema de satisfacibilidad booleana para encontrar programas automáticamente. ^[5]

Síntesis guiada por sintaxis

En 2013, investigadores de UPenn , UC Berkeley y MIT propusieron un marco unificado para problemas de síntesis de programas llamado Síntesis guiada por sintaxis (estilizado SyGuS) . ^[6] La entrada a un algoritmo SyGuS consiste en una especificación lógica junto con una gramática de expresiones libre de contexto que restringe la sintaxis de las soluciones válidas. ^[7] Por ejemplo, para sintetizar una función f que devuelve el máximo de dos números enteros, la especificación lógica podría verse así:

( f ( x , y ) = x ∨ f ( x , y ) = y ) ∧ f ( x , y ) ≥ x ∧ f ( x , y ) ≥ y

y la gramática podría ser:

< Exp >  ::= x | y | 0 | 1 | < Exp > + < Exp > | ite( < Cond > , < Exp > , < Exp > ) < Cond >  ::=  < Exp > <= < Exp >

donde "ite" significa "si-entonces-si no". La expresion

ite(x <= y, y, x)

Sería una solución válida, porque se ajusta a la gramática y la especificación.

Desde 2014 hasta 2019, el Concurso anual de síntesis guiada por sintaxis (o SyGuS-Comp) comparó los diferentes algoritmos para la síntesis de programas en un evento competitivo. ^[8] El concurso utilizó un formato de entrada estandarizado, SyGuS-IF, basado en SMT-Lib 2 . Por ejemplo, el siguiente SyGuS-IF codifica el problema de sintetizar el máximo de dos números enteros (como se presentó anteriormente):

(LIA de lógica de conjunto)(synth-fun f ((x Int) (y Int)) Int ((i Int) (c Int) (b Bool)) ((i Int (cxy (+ ii) (ite bii))) (c Ent (0 1)) (b booleano ((<= ii)))))(declarar-var x Int)(declarar-var y Int)(restricción (>= (fxy) x))(restricción (>= (fxy) y))(restricción (o (= (fxy) x) (= (fxy) y)))(control-sintetizador)

Un solucionador compatible podría devolver el siguiente resultado:

((definir-fun f ((x Int) (y Int)) Int (ite (<= xy) yx)))

El marco de Maná y Waldinger

El marco de Manna y Waldinger , publicado en 1980, ^{[9] [10]} parte de una fórmula de especificación de primer orden dada por el usuario . Para esa fórmula se construye una prueba, sintetizando así también un programa funcional a partir de sustituciones unificadoras .

El marco se presenta en forma de tabla y las columnas contienen:

• Un número de línea ("Nr") para fines de referencia
• Fórmulas que ya han sido establecidas, incluidos axiomas y condiciones previas ("Afirmaciones")
• Fórmulas aún por probar, incluidas las poscondiciones ("Objetivos"), ^{[nota 1]}
• Términos que denotan un valor de salida válido ("Programa") ^{[nota 2]}
• Una justificación para la línea actual ("Origen")

Inicialmente, se ingresan en la tabla los conocimientos previos, las condiciones previas y las condiciones posteriores. Después de eso, se aplican manualmente las reglas de prueba apropiadas. El marco ha sido diseñado para mejorar la legibilidad humana de las fórmulas intermedias: a diferencia de la resolución clásica , no requiere una forma clausal normal , pero permite razonar con fórmulas de estructura arbitraria y que contienen cualquier unión (" resolución no clausal "). La prueba está completa cuando se ha obtenido en la columna Metas o, de manera equivalente, en la columna Afirmaciones . Se garantiza que los programas obtenidos mediante este enfoque cumplirán la fórmula de especificación a partir de la cual se inició; en este sentido son correctos por construcción . ^[11] Sólo se admite un lenguaje de programación minimalista, pero completo de Turing , ^[12] puramente funcional , que consta de operadores condicionales, recursivos y aritméticos y otros ^{[nota 3]} . Los estudios de caso realizados dentro de este marco sintetizaron algoritmos para calcular, por ejemplo, división , resto , ^[13] raíz cuadrada , ^[14] unificación de términos , ^[15] respuestas a consultas de bases de datos relacionales ^[16] y varios algoritmos de clasificación . ^{[17] [18]} ${\displaystyle {\it {true}}}$ ${\displaystyle {\it {false}}}$

Reglas de prueba

Las reglas de prueba incluyen:

• Resolución no cláusulal (ver tabla).

Por ejemplo, la línea 55 se obtiene resolviendo las fórmulas de afirmación de 51 y 52, las cuales comparten alguna subfórmula común . El resolutivo se forma como la disyunción de , con reemplazado por y , con reemplazado por . Este resolutivo se deriva lógicamente de la conjunción de y . De manera más general, y necesitan tener solo dos subfórmulas unificables y , respectivamente; su resolutivo se forma entonces a partir de y como antes, donde está el unificador más general de y . Esta norma generaliza la resolución de cláusulas . ^[19] ${\displaystyle E}$ ${\displaystyle F}$ ${\displaystyle p}$ ${\displaystyle E}$ ${\displaystyle p}$ ${\displaystyle {\it {true}}}$ ${\displaystyle F}$ ${\displaystyle p}$ ${\displaystyle {\it {false}}}$ ${\displaystyle E}$ ${\displaystyle F}$ ${\displaystyle E}$ ${\displaystyle F}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle E\theta }$ ${\displaystyle F\theta }$ ${\displaystyle \theta }$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$

Los términos del programa de las fórmulas principales se combinan como se muestra en la línea 58 para formar el resultado del resolutivo. En el caso general, se aplica también a estos últimos. Dado que la subfórmula aparece en el resultado, se debe tener cuidado de resolver solo en subfórmulas correspondientes a propiedades computables . ${\displaystyle \theta }$ ${\displaystyle p}$

• Transformaciones lógicas.

Por ejemplo, se puede transformar a ) tanto en Afirmaciones como en Metas, ya que ambos son equivalentes. ${\displaystyle E\land (F\lor G)}$ ${\displaystyle (E\land F)\lor (E\land G)}$

• Escisión de afirmaciones conjuntivas y de objetivos disyuntivos.

Se muestra un ejemplo en las líneas 11 a 13 del siguiente ejemplo de juguete.

• Inducción estructural .

Esta regla permite la síntesis de funciones recursivas . Para una condición previa y posterior dada "Dado tal que , encuentre tal que ", y un buen ordenamiento apropiado del dominio de , siempre es aconsejable agregar una Aserción " ". ^[20] Resolver con esta afirmación puede introducir una llamada recursiva a en el término del Programa. ${\displaystyle x}$ ${\displaystyle {\textit {pre}}(x)}$ ${\displaystyle f(x)=y}$ ${\displaystyle {\textit {post}}(x,y)}$ ${\displaystyle \prec }$ ${\displaystyle x}$ ${\displaystyle x'\prec x\land {\textit {pre}}(x')\implies {\textit {post}}(x',f(x'))}$ ${\displaystyle f}$

Un ejemplo se da en Manna, Waldinger (1980), p.108-111, donde se sintetiza un algoritmo para calcular el cociente y el resto de dos números enteros dados, utilizando el orden definido por (p.110). ${\displaystyle (n',d')\prec (n,d)}$ ${\displaystyle 0\leq n'<n}$

Murray ha demostrado que estas reglas son completas para la lógica de primer orden . ^[21] En 1986, Manna y Waldinger agregaron reglas generalizadas de resolución E y paramodulación para manejar también la igualdad; ^[22] Más tarde, estas reglas resultaron ser incompletas (pero, sin embargo, sólidas ). ^[23]

Ejemplo

Como ejemplo de juguete, un programa funcional para calcular el máximo de dos números se puede derivar de la siguiente manera. ^{[ cita necesaria ]} ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle y}$

A partir de la descripción del requisito " El máximo es mayor o igual a cualquier número dado y es uno de los números dados ", se obtiene la fórmula de primer orden como su traducción formal. Esta fórmula debe ser demostrada. Mediante Skolemización inversa , ^{[nota 4]} se obtiene la especificación en la línea 10, una letra mayúscula y minúscula que denota una variable y una constante de Skolem , respectivamente. ${\displaystyle \forall X\forall Y\exists M:X\leq M\land Y\leq M\land (X=M\lor Y=M)}$

Después de aplicar una regla de transformación para la ley distributiva en la línea 11, el objetivo de la prueba es una disyunción y, por lo tanto, se puede dividir en dos casos, a saber. líneas 12 y 13.

Volviendo al primer caso, resolver la línea 12 con el axioma de la línea 1 conduce a la instanciación de la variable del programa en la línea 14. Intuitivamente, la última conjunción de la línea 12 prescribe el valor que debe tomar en este caso. Formalmente, la regla de resolución no cláusulal que se muestra en la línea 57 anterior se aplica a las líneas 12 y 1, con ${\displaystyle M}$ ${\displaystyle M}$

• siendo p la instancia común x=x de A=A y x=M , obtenida al unificar sintácticamente estas últimas fórmulas,
• siendo F[ p ] verdadero ∧ x=x , obtenido de la línea 1 instanciada (rellenada apropiadamente para hacer visible el contexto F[⋅] alrededor de p ), y
• Siendo G[ p ] x ≤ x ∧ y ≤ x ∧ x = x , obtenido de la línea 12 instanciada,

dando verdadero ∧ falso ) ∧ ( x ≤ x ∧ y ≤ x ∧ verdadero , que se simplifica a . ${\displaystyle \lnot (}$ ${\displaystyle )}$ ${\displaystyle x\leq x\land y\leq x}$

De manera similar, la línea 14 produce la línea 15 y luego la línea 16 por resolución. Además, el segundo caso, en la línea 13, se maneja de manera similar, dando lugar finalmente a la línea 18. ${\displaystyle x\leq M\land y\leq M\land y=M}$

En un último paso, se unen ambos casos (es decir, líneas 16 y 18), utilizando la regla de resolución de la línea 58; para que esa norma fuera aplicable, era necesario el paso preparatorio 15→16. Intuitivamente, la línea 18 podría leerse como "en caso , la salida es válida (con respecto a la especificación original), mientras que la línea 15 dice "en caso , la salida es válida; el paso 15→16 estableció que ambos casos 16 y 18 son complementarios. ^{[nota 5]} Dado que tanto la línea 16 como la 18 vienen con un término de programa, una expresión condicional da como resultado la columna del programa. Dado que se ha obtenido la fórmula del objetivo , se realiza la prueba y la columna de programa de la línea " " contiene el programa. ${\displaystyle x\leq y}$ ${\displaystyle y}$ ${\displaystyle y\leq x}$ ${\displaystyle x}$ ${\displaystyle {\textit {true}}}$ ${\displaystyle {\textit {true}}}$

Ver también

• programación inductiva
• Metaprogramación
• Derivación del programa
• Programación en lenguaje natural
• Síntesis reactiva

Notas

1. La distinción "Afirmaciones" / "Objetivos" es únicamente por conveniencia; Siguiendo el paradigma de la prueba por contradicción , una Meta equivale a una afirmación . ${\displaystyle F}$ ${\displaystyle \lnot F}$
2. Cuando y está la fórmula del objetivo y el término del programa en una línea, respectivamente, entonces, en todos los casos en los que se cumple, es una salida válida del programa que se va a sintetizar. Esta invariante se mantiene mediante todas las reglas de prueba. Una fórmula de afirmación normalmente no está asociada con un término de programa. ${\displaystyle F}$ ${\displaystyle s}$ ${\displaystyle F}$ ${\displaystyle s}$
3. Solo se admite el operador condicional ( ? :) desde el principio. Sin embargo, se pueden agregar nuevos operadores y relaciones arbitrarias proporcionando sus propiedades como axiomas. En el siguiente ejemplo de juguete, solo se han axiomatizado las propiedades de y que realmente se necesitan en la prueba, en las líneas 1 a 3. ${\displaystyle =}$ ${\displaystyle \leq }$
4. Mientras que la eskolemización ordinaria preserva la satisfacibilidad, la eskolemización inversa, es decir, la sustitución de variables cuantificadas universalmente por funciones, preserva la validez.
5. Para eso se necesitaba el axioma 3; de hecho, si no fuera un pedido total , no se podría calcular ningún máximo para entradas incomparables . ${\displaystyle \leq }$ ${\displaystyle x,y}$

Referencias

1. Cuenca, D.; Deville, Y.; Flener, P.; Hamfelt, A.; Fischer Nilsson, J. (2004). "Síntesis de programas en lógica computacional". En M. Bruynooghe y K.-K. Lau (ed.). Desarrollo de Programas en Lógica Computacional . LNCS. vol. 3049. Saltador. págs. 30–65. CiteSeerX  10.1.1.62.4976 .
2. (Alur, Singh y Fisman)error de harv: sin destino: CITEREFAlurSinghFisman ( ayuda )
3. Iglesia de Alonso (1957). "Aplicaciones de la aritmética recursiva al problema de la síntesis de circuitos". Resúmenes del Instituto de Verano de Lógica Simbólica . 1 : 3–50.
4. Richard Büchi, Lawrence Landweber (abril de 1969). "Resolución de condiciones secuenciales mediante estrategias de estados finitos". Transacciones de la Sociedad Matemática Estadounidense . 138 : 295–311. doi :10.2307/1994916. JSTOR  1994916.
5. Solar-Lezama, Armando (2008). Síntesis del programa mediante bocetos (PDF) (Ph.D.). Universidad de California, Berkeley.
6. Alur, Rajeev; al., et (2013). "Síntesis guiada por sintaxis". Actas de métodos formales en diseño asistido por computadora . IEEE. pag. 8.
7. David, Cristina; Kroening, Daniel (13 de octubre de 2017). "Síntesis del programa: desafíos y oportunidades". Transacciones filosóficas de la Royal Society A: Ciencias matemáticas, físicas y de ingeniería . 375 (2104): 20150403. doi :10.1098/rsta.2015.0403. ISSN  1364-503X. PMC 5597726 . PMID  28871052. 
8. SyGuS-Comp (Concurso de síntesis guiada por sintaxis)
9. Zohar Manna, Richard Waldinger (enero de 1980). "Un enfoque deductivo de la síntesis de programas". Transacciones ACM sobre lenguajes y sistemas de programación . 2 : 90–121. doi :10.1145/357084.357090. S2CID  14770735.
10. Zohar Manna y Richard Waldinger (diciembre de 1978). Un enfoque deductivo para la síntesis de programas (PDF) (Nota técnica). SRI Internacional. Archivado (PDF) desde el original el 27 de enero de 2021.
11. Véase Manna, Waldinger (1980), p.100 para conocer la exactitud de las reglas de resolución.
12. Boyer, Robert S.; Moore, J. Strother (mayo de 1983). Una prueba mecánica de la integridad de Turing de Pure Lisp (PDF) (Reporte técnico). Instituto de Ciencias de la Computación, Universidad de Texas en Austin. 37. Archivado (PDF) desde el original el 22 de septiembre de 2017.
13. Maná, Waldinger (1980), páginas 108-111
14. Zohar Manna y Richard Waldinger (agosto de 1987). "El origen de un paradigma de búsqueda binaria". Ciencia de la programación informática . 9 (1): 37–83. doi :10.1016/0167-6423(87)90025-6.
15. Daniele Nardi (1989). "Síntesis formal de un algoritmo de unificación mediante el método de cuadro deductivo". Revista de programación lógica . 7 : 1–43. doi :10.1016/0743-1066(89)90008-3.
16. Daniele Nardi y Riccardo Rosati (1992). "Síntesis deductiva de programas para respuesta de consultas". En Kung-Kiu Lau y Tim Clement (ed.). Taller Internacional sobre Síntesis y Transformación de Programas Lógicos (LOPSTR) . Talleres de Computación. Saltador. págs. 15-29. doi :10.1007/978-1-4471-3560-9_2.
17. Jonathan Traugott (1986). "Síntesis deductiva de programas de clasificación". Actas de la Conferencia Internacional sobre Deducción Automatizada . LNCS . vol. 230. Saltador. págs. 641–660.
18. Jonathan Traugott (junio de 1989). "Síntesis deductiva de programas de clasificación". Revista de Computación Simbólica . 7 (6): 533–572. doi :10.1016/S0747-7171(89)80040-9.
19. Maná, Waldinger (1980), p.99
20. Maná, Waldinger (1980), p.104
21. Manna, Waldinger (1980), p.103, en referencia a: Neil V. Murray (febrero de 1979). Un procedimiento de prueba para una lógica de primer orden no clausal sin cuantificadores (informe técnico). Universidad de Siracusa. 2-79.
22. Zohar Manna, Richard Waldinger (enero de 1986). "Relaciones Especiales en Deducción Automatizada". Revista de la ACM . 33 : 1–59. doi : 10.1145/4904.4905 . S2CID  15140138.
23. Zohar Maná, Richard Waldinger (1992). "Las reglas de relaciones especiales están incompletas". Proc. CADE 11 . LNCS. vol. 607. Saltador. págs. 492–506.

• Alur, Rajeev; Singh, Rishabh; Fisman, Dana; Solar-Lezama, Armando (2018-11-20). "Síntesis de programas basada en búsquedas". Comunicaciones de la ACM . 61 (12): 84–93. doi :10.1145/3208071. ISSN  0001-0782.
• Zohar Maná, Richard Waldinger (1975). "Conocimiento y razonamiento en síntesis de programas". Inteligencia artificial . 6 (2): 175–208. doi :10.1016/0004-3702(75)90008-9.