Manejo de memoria en programación lógica con tabulación

Los lenguajes de programación son el idioma que los programadores usamos para comunicar a los computadores qué queremos que hagan. Desde el lenguaje ensamblador, que traduce una a una las instrucciones que interpreta un computador hasta lenguajes de alto nivel, se ha buscado desarrollar lenguajes más cercanos a la forma de pensar y expresarse de los humanos. Los lenguajes de programación lógicos como Prolog utilizan a su vez el lenguaje de la lógica de 1er orden de modo que el programador puede expresar las premisas del problema que se quiere resolver sin preocuparse del cómo se va a resolver dicho problema. La resolución del problema se equipara a encontrar una deducción del objetivo a alcanzar a partir de las premisas y equivale a lo que entendemos por la ejecución de un programa. Ciao es una implementación de Prolog (http://www.ciao-lang.org) y utiliza el método de resolución SLD, que realiza el recorrido de los árboles de decisión en profundidad(depth-first) lo que puede derivar en la ejecución de una rama de busqueda infinita (en un bucle infinito) sin llegar a dar respuestas. Ciao, al ser un sistema modular, permite la utilización de extensiones para implementar estrategias de resolución alternativas como la tabulación (OLDT). La tabulación es un método alternativo que se basa en memorizar las llamadas realizadas y sus respuestas para no repetir llamadas y poder usar las respuestas sin recomputar las llamadas. Algunos programas que con SLD entran en un bucle infinito, gracias a la tabulación dán todas las respuestas y termina. El modulo tabling es una implementación de tabulación mediante el algoritmo CHAT. Esta implementación es una versión beta que no tiene implementado un manejador de memoria. Entendemos que la gestión de memoria en el módulo de tabling tiene gran importancia, dado que la resolución con tabulación permite reducir el tiempo de computación (al no repetir llamadas), aumentando los requerimientos de memoria (para guardar las llamadas y las respuestas). Por lo tanto, el objetivo de este trabajo es implementar un mecanismo de gestión de la memoria en Ciao con el módulo tabling cargado. Para ello se ha realizado la implementación de: Un mecanismo de captura de errores que: detecta cuando el computador se queda sin memoria y activa la reinicialización del sitema. Un procedimiento que ajusta los punteros del modulo de tabling que apuntan a la WAM tras un proceso de realojo de algunas de las áreas de memoria de la WAM. Un gestor de memoria del modulo de tabling que detecta c realizar una ampliación de las áreas de memoria del modulo de tabling, realiza la solicitud de más memoria y realiza el ajuste de los punteros. Para ayudar al lector no familiarizado con este tema, describimos los datos que Ciao y el módulo de tabling alojan en las áreas de memoria dinámicas que queremos gestionar. Los casos de pruebas desarrollados para evaluar la implementación del gestor de memoria, ponen de manifiesto que: Disponer de un gestor de memoria dinámica permite la ejecución de programas en un mayor número de casos. La política de gestión de memoria incide en la velocidad de ejecución de los programas. ---ABSTRACT---Programming languages are the language that programmers use in order to communicate to computers what we want them to do. Starting from the assembly language, which translates one by one the instructions to the computer, and arriving to highly complex languages, programmers have tried to develop programming languages that resemble more closely the way of thinking and communicating of human beings. Logical programming languages, such as Prolog, use the language of logic of the first order so that programmers can express the premise of the problem that they want to solve without having to solve the problem itself. The solution to the problem is equal to finding a deduction of the objective to reach starting from the premises and corresponds to what is usually meant as the execution of a program. Ciao is an implementation of Prolog (http://www.ciao-lang.org) and uses the method of resolution SLD that carries out the path of the decision trees in depth (depth-frist). This can cause the execution of an infinite searching branch (an infinite loop) without getting to an answer. Since Ciao is a modular system, it allows the use of extensions to implement alternative resolution strategies, such as tabulation (OLDT). Tabulation is an alternative method that is based on the memorization of executions and their answers, in order to avoid the repetition of executions and to be able to use the answers without reexecutions. Some programs that get into an infinite loop with SLD are able to give all the answers and to finish thanks to tabulation. The tabling package is an implementation of tabulation through the algorithm CHAT. This implementation is a beta version which does not present a memory handler. The management of memory in the tabling package is highly important, since the solution with tabulation allows to reduce the system time (because it does not repeat executions) and increases the memory requirements (in order to save executions and answers). Therefore, the objective of this work is to implement a memory management mechanism in Ciao with the tabling package loaded. To achieve this goal, the following implementation were made: An error detection system that reveals when the computer is left without memory and activate the reinizialitation of the system. A procedure that adjusts the pointers of the tabling package which points to the WAM after a process of realloc of some of the WAM memory stacks. A memory manager of the tabling package that detects when it is necessary to expand the memory stacks of the tabling package, requests more memory, and adjusts the pointers. In order to help the readers who are not familiar with this topic, we described the data which Ciao and the tabling package host in the dynamic memory stacks that we want to manage. The test cases developed to evaluate the implementation of the memory manager show that: A manager for the dynamic memory allows the execution of programs in a larger number of cases. Memory management policy influences the program execution speed.

Estructuras óptimas de detección y corrección de errores dirigidas a computadores construidos con lógica de alto nivel de Integración: aplicación industrial

Este trabajo trata de la aplicación de los códigos detectores y correctores de error al diseño de los Computadores Tolerantes a Fallos, planteando varias estrategias óptimas de detección y corrección para algunos subsistemas. En primer lugar,"se justifica la necesidad de aplicar técnicas de Tolerancia a Fallos. A continuación se hacen previsiones de evolución de la tecnología de Integración, así como una tipificación de los fallos en circuitos Integrados. Partiendo de una recopilación y revisión de la teoría de códigos, se hace un desarrollo teórico cuya aplicación permite obligar a que algunos de estos códigos sean cerrados respecto de las operaciones elementales que se ejecutan en un computador. Se plantean estrategias óptimas de detección y corrección de error para sus subsistemas mas Importantes, culminando en el diseño, realización y prueba de una unidad de memoria y una unidad de proceso de datos con amplias posibilidades de detección y corrección de errores.---ABSTRACT---The present work deals with the application of error detecting and correctíng codes to the désign of Fault Tolerant Computers. Several óptimo» detection and correction strategies are presented to be applied in some subsystems. First of all, the necessity of applying Fault Tolerant techniques is explained. Later, a study on íntegration technology evolution and typification of Integrated circuit faults 1s developed. Based on a compilation and revisión of Coding Theory, a theoretical study is carried out. It allows us to force some of these codes to be closed over elementary operations. Optimum detection and correction techniques are presented for the raost important subsystems. Flnally, the design, building and testing of a memory unit and a processing unit provided with wlde error detection and correction posibilities 1s shown.

Bases para un planteamiento jerárquico de la lógica aplicable a la representación e interpretación del conocimiento

Uno de los campos de investigación más activos hoy en dia dentro del terreno de la inteligencia artificial (I.A.) es el de la representación del conocimiento. Actualmente es usual el clasificar los esquemas de representación del conocimiento en tres grandes grupos [Mylos 82]: Lógicos, de redes semánticas y procedimentales. Ponemos en primer lugar las representaciones lógicas porque es precisamente dentro de ellas donde el presente trabajo se puede encuadrar.

Tratamiento N-categorial de la lógica de la programación

En el contexto de las técnicas de validación de programas, de las estructuras de axiomatización de la programación planteadas por Hoare y del desarrollo de la Lógica de la Programación que Dijkstra realiza con el operador wp, hemos dotado a los elementos esenciales que intervienen en dicho desarrollo de una estructura que permite su estudio en el ámbito de las categorias. En este trabajo se demuestra que el conjunto de precondiciones de un fragmento de programa anotado tiene estructura de N-categoría y que sucede lo mismo con el conjunto de postcondiciones. Más aún, se ha puesto de manifiesto (y probado) que el operador wp actúa como un funtor entre estos pares de N-categorías. Además, los conjuntos de guardas surgen de un modo natural en la lógica de la programación, han sido tratados desde el punto de vista de la semántica denotacional (Wlrth para el PASCAL y Scott y otros, después, en un enfoque más general) y presentados por Manes y Arbib en su semántica parcialmente aditiva. Pues bien, en este trabajo se demuestra que los conjuntos de guardas tienen también estructura de N-categoría y gue cualguier N-categoría dotada de una suma definida adecuadamente tiene estructura de conjunto de guardas, de tal modo, además, gue el preorden inducido por la suma en el conjunto de guardas coincide con la flecha de la N-categoría. Esta suma es, en concreto, la disyunción exclusiva, lo que adicionalmente supone una sorprendentemente sencilla definición alternativa a la suma de las categorías parcialmente aditivas definida por Manes y Arbib. Con todo esto, se aportan herramientas conceptuales para entender mejor y resolver más eficientemente los problemas que tiene planteados la lógica de la programación, pues se dispone de un punto de vista distinto y nuevo y de toda una familia de instrumentos adicionales.---ABSTRACT---In the context of program validation techniques, Hoare's systems for programming and Dijkstra's development of the logic of programming, based on the operator wp, we have endowed the essential features of this development with a structure that permits to study them in the frame of category theory. In this thesis we show that the set of preconditions of an annotated program segment is an N-category, and the same happens for the set of postconditions. Even more, it is shown that the operator wp acts as a functor between those pairs of Ncategories. Furthermore, guard sets come out in a natural way in the logic of programming, they have been considered from a denotational semantics point of view (Wirth for Pascal and afterwards Scott and al. in a more general setting) and they have been embodied by Manes and Arbib in their partially additive semantics. Then, it is shown in this thesis that the above mentioned guard sets also have the structure of an N-category and that any N-category with an appropiately defined sum has the structure of a guard set in such a way that, besides, the preorder defined in the guard set by the sum operation coincides with the arrows of the N-category. This sum is just the exclusive or of Boolean Logic and this fact adds a surprisingly simple alternative definition for the sum operation in Manes and Arbib partially additive categories. The present work, in summary, makes a contribution of conceptual tools for a better understanding and a more efficient solution of the problems posed to the logic of programming and it does so by providing a new different point of view and a whole family of additional techniques.