|
Descripción
|
|
|---|---|
| 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. | |
|
Internacional
|
Si |
|
ISBN
|
|
|
Tipo de Tesis
|
Doctoral |
|
Calificación
|
Sobresaliente cum laude |
|
Fecha
|
28/11/2012 |