Observatorio de I+D+i UPM

Memorias de investigación
Thesis:
Advanced Evaluation Strategies for Tabling and Parallelism in Logic Programs
Year:2012
Research Areas
  • Engineering
Information
Abstract
Dentro de los paradigmas de programaci ?on en el mundo de la inform ?atica te- nemos la ?Programaci ?on Lo ?gica?, cuyo principal exponente es el lenguaje Prolog. Los programas Prolog se componen de un conjunto de predicados, cada uno de ellos definido por medio de reglas que aportan un elevado nivel de abstraccio ?n y declaratividad al programador. Sin embargo, las formulacio ?n con reglas impli- ca, frecuentemente, que un predicado se recompute varias veces para la misma consulta y adema ?s, Prolog utiliza un orden fijo para evaluar reglas y objetivos (evaluaci ?on SLD) que puede entrar en ?bucles infinitos? cuando ejecuta reglas re- cursivas declarativamente correctas. Estas limitaciones son atacadas de ra ?z por la tabulaci ?on, que se basa en ?recordar? en una tabla las llamadas realizadas y sus soluciones. As ?, en caso de repetir una llamada tendr ?amos ya disponibles sus so- luciones y la tabulacio ?n evitar ?a la recomputacio ?n de esta llamada. Tambi ?en evita ?bucles infinitos? ya que las llamadas que los generan son suspendidas, quedando a la espera de que se computen soluciones para las mismas usando derivaciones alternativas. La implementacio ?n de la tabulacio ?n no es sencilla. En particular, necesita de tres operaciones que no pueden ser ejecutadas en tiempo constante simulta ?nea- mente. Dichas operaciones son: suspensi ?on de llamadas, relanzamiento de llama- das y acceso a variables. La primera parte de la tesis compara tres implemen- taciones de tabulacio ?n sobre Ciao, cada una de las cuales penaliza una de estas operaciones. Por tanto, cada solucio ?n tiene sus ventajas y sus inconvenientes y se comporta mejor o peor dependiendo del programa ejecutado. La segunda parte de la tesis mejora la funcionalidad de la tabulaci ?on para combinarla con restricciones y tambi ?en para evitar computaciones innecesarias. La programacio ?n con restricciones permite la resoluci ?on de ecuaciones como me- dio de programar, mecanismo altamente declarativo. Hemos desarrollado un fra- mework para combinar la tabulacio ?n con las restricciones, priorizando objetivos como la flexibilidad, la eficiencia y la generalidad de nuestra soluci ?on, obteniendo una sinergia entre ambas t ?ecnicas muy u ?til en numerosas aplicaciones. Por otra parte, un aspecto fundamental de la tabulaci ?on hace referencia al momento en que se retornan las soluciones de una llamada tabulada. Local evaluation devuel- ve soluciones so ?lo cuando todas las soluciones de la llamada tabulada han sido computadas. Por contra, batched evaluation devuelve las soluciones una a una conforme van siendo computadas, por lo que se adapta mejor a problemas don- de no nos interesa encontrar todas las soluciones. Sin embargo, su consumo de memoria es exponencialmente peor que el de local evaluation. La tesis presenta swapping evaluation, un m ?etodo alternativo que devuelve soluciones tan pronto como son computadas pero con un consumo de memoria similar a la de local eva- luation. Adema ?s, se implementan operadores de poda para descartar la bu ?squeda de soluciones alternativas cuando encontramos la solucio ?n deseada.
International
Si
Type
Doctoral
Mark Rating
Sobresaliente cum laude
Date
28/11/2012
Participants
  • Autor: Pablo Chico de Guzmán Huerta (UPM)
  • Director: Manuel Carro Liñares (UPM)
  • Director: Manuel de Hermenegildo Salinas (UPM)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Computación lógica, Lenguajes, Implementación y Paralelismo (CLIP)
  • Departamento: Inteligencia Artificial
S2i 2019 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)