Técnica en el procesamiento del lenguaje natural
La tabulación es una técnica desarrollada inicialmente para el procesamiento del lenguaje natural, donde se la denominaba análisis de Earley . Consiste en almacenar en una tabla (también llamada gráfico en el contexto del análisis sintáctico) análisis parciales exitosos que podrían resultar útiles para su reutilización en el futuro.
La tabulación consiste en mantener una tabla de objetivos que se llaman durante la ejecución, junto con sus respuestas, y luego usar las respuestas directamente cuando se llama posteriormente al mismo objetivo. La tabulación ofrece una garantía de total corrección para cualquier programa Prolog (puro) sin símbolos de función. [1]
La tabulación se puede ampliar en varias direcciones. Puede admitir predicados recursivos a través de la resolución SLG o la tabulación lineal. En un sistema Prolog multiproceso, los resultados de la tabulación se pueden mantener privados para un subproceso o compartir entre todos los subprocesos. Y en la tabulación incremental, la tabulación puede reaccionar a los cambios. [2] [3]
Historia
La adaptación de la tabulación a un procedimiento de prueba de programación lógica, bajo el nombre de deducción de Earley, data de una nota inédita de 1975 de David HD Warren . [4] Posteriormente, Tamaki y Sato desarrollaron un método de interpretación basado en la tabulación, modelado como un refinamiento de la resolución SLD. [5]
David S. Warren y sus estudiantes adoptaron esta técnica con la motivación de cambiar la semántica de Prolog de la semántica de completitud a la semántica de modelo mínimo. Prolog en tablas se introdujo por primera vez en XSB . [6] Esto dio como resultado una implementación completa de la semántica bien fundada , una semántica de tres valores que representa valores para verdadero, falso y desconocido. [7]
Referencias
- ^ Körner, Philipp; Leuschel, Michael; Barbosa, Joao; Costa, Vítor Santos; Dahl, Verónica; Hermengildo, Manuel V.; Morales, José F.; Wielemaker, enero; Díaz, Daniel; Abreu, Salvador; Ciatto, Giovanni (17 de mayo de 2022). "Cincuenta años de prólogo y más allá". Teoría y práctica de la programación lógica . 22 (6): 776–858. doi : 10.1017/s1471068422000102 . hdl : 10174/33387 . ISSN 1471-0684.
- ^ Swift, T. (1999). "Tabling para programación no monótona". Anales de Matemáticas e Inteligencia Artificial . 25 (3/4): 201–240. doi :10.1023/A:1018990308362. S2CID 16695800.
- ^ Zhou, Neng-Fa; Sato, Taisuke (2003). "Cálculo eficiente de puntos fijos en tablas lineales" (PDF) . Actas de la 5.ª Conferencia internacional ACM SIGPLAN sobre principios y prácticas de programación declarativa : 275–283.
- ^ Pereira, Fernando CN; Shieber, Stuart M. (1987). Prolog y análisis del lenguaje natural . Stanford: Centro para el estudio del lenguaje y la información . págs. 185–210.
- ^ Tamaki, Hisao; Sato, Taisuke (1986), "Resolución OLD con tabulación", Lecture Notes in Computer Science , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 84–98, ISBN 978-3-540-16492-0, consultado el 27 de octubre de 2023
- ^ Sagonas, Konstantinos; Swift, Terrance; Warren, David S. (24 de mayo de 1994). "XSB como un motor de base de datos deductivo eficiente". ACM SIGMOD Record . 23 (2): 442–453. doi : 10.1145/191843.191927 . ISSN 0163-5808.
- ^ Rao, Prasad; Sagonas, Konstantinos; Swift, Terrance; Warren, David S.; Freire, Juliana (1997), "XSB: Un sistema para calcular eficientemente una semántica bien fundada", Programación lógica y razonamiento no monotónico , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 430–440, ISBN 978-3-540-63255-9, consultado el 27 de octubre de 2023
- Este artículo incorpora texto de esta fuente, que es de PHILIPP KÖRNER, MICHAEL LEUSCHEL, JOÃO BARBOSA, VÍTOR SANTOS COSTA, VERÓNICA DAHL, MANUEL V. HERMENEGILDO, JOSE F. MORALES, JAN WIELEMAKER, DANIEL DIAZ, SALVADOR ABREU y GIOVANNI CIATTO disponible en la licencia CC BY 4.0.
