Tesis para optar al grado de Doctor en Ciencias, Mención Computación / Han habido muchos enfoques para integrar tipado estático y dinámico. Uno de los enfoques más notables es el del tipado gradual. El enfoque clásico para diseñar lenguajes graduales es usualmente ad-hoc, pero existen metodologías que sistematizan este proceso. Una de ellas es la Abstracting Gradual Typing (AGT), que ayuda a construir sistemáticamente lenguajes graduales a partir de lenguajes estáticamente tipados usando interpretación abstracta al nivel de tipos. A pesar que se a mostrado que AGT a sido efectiva en diferentes contextos, hay aún muchas preguntas abiertas: ¿AGT escala a mecanismos de lenguaje y disciplinas de tipos complejos? ¿Que lenguajes obtienen al usar abstracciones más ricas, o al introducir imprecisión de una manera poco convencional? ¿Cómo se compara el lenguaje gradual resultante con lo existente en la literatura? ¿Que propiedades AGT garantiza de preservar por construcción? ¿Podemos aplicar AGT a un lenguaje gradual derivado con AGT? En esta tesis se trata de responder a estas preguntas, aplicando AGT a disciplinas de tipos y mecanismos de lenguaje complejos. Primero, se aplica AGT a un cálculo lambda con tipado simple y referencias mutables, donde se muestra que una directa aplicación de AGT no garantiza una semántica eficiente respecto al espacio. Se prueba equivalencia contextual con uno de los lenguajes graduales con referencias encontrados en la literatura. Segundo, se aplica AGT a un lenguaje con tipado de seguridad y referencias, introduciendo imprecisión solo en las etiquetas de seguridad de los tipos. Se aprende que una aplicación directa de AGT sólo garantiza preservar por construcción la seguridad de tipos y los criterios refinados de lenguajes graduales. En orden de satisfacer no-interferencia, la propiedad semántica crucial del lenguaje estático, se deben refinar las abstracciones usadas en la semántica dinámica. Pero debido a las referencias mutables, se agrega un chequeo extra en la regla de reducción de asignaciones para prevenir flujos implícitos de información a través de la memoria. Este chequeo extra rompe la garantía gradual dinámica, la cual es parte de los criterios refinados de los lenguajes graduales. Tercero, se aplica AGT para introducir una nueva forma de imprecisión en los tipos, llamada unión gradual, un diseño original de tipos de unión que combina ambos beneficios de uniones etiquetadas y no etiquetadas. Se descubre que las uniones graduales interactúan con el tipo desconocido en una forma que exige un enfoque estratificado para AGT, dependiendo de la composición de dos interpretaciones de abstracción distintas en orden de recuperar optimalidad. Cuarto, se aplica AGT a System F, un lenguaje que soporta polimorfismo paramétrico. Se descubre que una aplicación directa de AGT rompe parametricidad, una propiedad semántica crucial de System F. En orden de recuperar parametricidad, se refinan las abstracciones (y se personalizan ciertas operaciones) usadas en la semántica dinámica. Esta personalización ayuda a preservar parametricidad pero a costa de la violar la garantía gradual dinámica. Esta garantía fue dejada como una conjetura en todos los trabajos previos; aquí se prueba que es simplemente incompatible con la noción clásica de parametricidad. Sin embargo, se establece una propiedad más débil que permite refutar varias afirmaciones acerca de teoremas graduales gratis, clarificando el tipo de razonamiento soportado por la parametricidad gradual. / CONICYT-PCHA/Doctorado Nacional/2015-21150510

El trabajo de tesis presenta al lenguaje de programación Haskell y realiza un estudio comparativo con respecto a lenguajes de programación que son promovidos con gran impacto en la actualidad en los ambientes: académico, industrial y científico. Los lenguajes de programación que servirán como puntos de referencia de comparación para el presente estudio son: C/C++, Java y GOlang. Los criterios de comparación tomados en cuenta en el estudio son: fácil escritura, fácil lectura, confiabilidad, soporte de genéricos y reflexión. Se elige comparar los lenguajes mencionados con el lenguaje de programación Haskell, porque es un lenguaje que ha significado un reto para los estudiosos en Ciencias de la Computación de las universidades más prestigiosas del mundo, quienes diseñaron un lenguaje de programación que mejora y supera errores de diseño de lenguajes de programación convencionales. En el primer capítulo se referencia estudios realizados acerca de los lenguajes de programación en las últimas décadas, la popularidad e impacto que tienen en el ámbito académico, industrial y científico, los lenguajes de programación C/C++, Java y GOlang. En el segundo capítulo se referencia estudios realizados acerca de la categorización de los lenguajes de programación a lo largo de la historia de los lenguajes de programación. En el tercer capítulo se detalla cada uno de los lenguajes de programación en mención, su origen, evolución, aplicaciones y tecnologías desarrolladas en las últimas décadas. En el cuarto capítulo se describen los criterios de evaluación de un lenguaje de programación, según autores de prestigio en el campo de las ciencias de la computación. En el quinto capítulo se realiza un estudio y desarrollo de programas en los lenguajes de programación elegidos para poder evaluar las ventajas y desventajas, con respecto a los criterios de evaluación elegidos: fácil escritura, fácil lectura, confiabilidad, soporte de genéricos y reflexión. / Tesis

Programación orientada a objetos. 1. Lenguaje de programación java

Las gramáticas de atributos, desde que fueron propuestas por Knuth en 1966, se han utilizado ampliamente para el desarrollo de herramientas de procesamiento de lenguajes formales como compiladores e intérpretes de lenguajes de programa-ción; como también para especificar la semántica de lenguajes. Las gramáticas de atributos son un formalismo simple para la especificación de la semántica de lenguajes formales, como ser lenguajes de programación o de especifi-cación. Integran la modularidad que brindan las gramáticas libres de contexto y la expresividad de un lenguaje funcional. Si bien las gramáticas de atributos han sido ampliamente estu-diadas no es fácil encontrar definiciones precisas y rigurosas. Los principales motivos del desarrollo de esta tesis son en primer lugar, obtener un material autocontenido sobre sus defi-niciones, extensiones, implementación y aplicaciones, ya que prácticamente no existen libros actualizados en el tema. En segundo lugar, se realiza un estudio profundo sobre nuevas clasificaciones propuestas y métodos de evaluación. En este último aspecto es donde se presentan los aportes más signifi-cativos de esta tesis. En este trabajo se presentan las gramá-ticas de atributos en su forma clásica, mostrando definiciones más precisas que las que se pueden encontrar en la bibliografía tradicional. Se describen diferentes clasificaciones y métodos de evaluación secuenciales y concurrentes. Entre los principa-les aportes de este trabajo, se propone un algorimo eficiente de evaluación dinámica bajo demanda, que puede aplicarse para la evaluación de cualquier gramática de atributos bien definida (no circular). Este algorimo se ha implementado en la herramienta agcc, la cual ha sido desarrollada en el marco de este trabajo. Se analiza una nueva clasificación, la jerarquía NC, propuesta por Wuu Yang en 1999 y se relaciona con la clasificación tradicional. Se describe NCeval, una herramienta desarrollada en el marco de esta tesis, la cual genera evalua-dores estáticos para la familia NC(1). Un evaluador generado por NCEval realiza la evaluación disparando procesos o tareas concurrentes que no requieren sincronización, ya que operan sobre conjuntos independientes de instancias de atributos. El método de particionado usado en NCEval está basado en las dependencias y se demuestra que la partición inducida sobre el conjunto de atributos es la mas fina posible. Hasta el momento, no se conocen herramientas que utilicen este enfo-que. Finalmente se describe agcc (Attribute Grammars Compiler Compiler), herramienta desarrollada en el marco de esta tesis, la cual tiene un diseño totalmente modular per-mitiendo su extensibilidad tanto en los generadores de código como en los métodos de evaluación utilizados. Acepta la familia más amplia de gramáticas de atributos para las cuales pueden generarse evaluadores estáticos

Magíster en Ciencias, Mención Computación / Los sistemas de tipos-y-efectos (type-and-effect systems) permiten a los programadores hacer valer invariantes y restricciones sobre los efectos secundarios que se generan durante la evaluación de un programa. Los sistemas de tipos-y-efectos consideran efectos secundarios tales como estado, excepciones y E/S, entre otros. Desafortunadamente, los sistemas de tipos-y-efectos también obligan al programador a introducir anotaciones de efectos, lo que implica un esfuerzo adicional. En la práctica, los sistemas de tipos-y-efectos no son comúnmente usados. Conjeturamos que una de las razones importantes para la limitada adopción de los sistemas de efectos son las dificultades para realizar la transición desde un sistema donde los efectos secundarios son implícitos hacia una disciplina de efectos totalmente estática. Los tipos graduales (Gradual typing) permiten a los programadores combinar la flexibilidad de los lenguajes dinámicamente tipados con las garantías provistas por los sistemas de tipos estáticos. En lenguajes con tipos graduales, las anotaciones de tipos son parte del lenguaje, pero no son obligatorias. Un sistema de tipos gradual utiliza la información disponible para proveer garantías estáticas, rechazando los programas claramente incoherentes, e introduce verificaciones en tiempo de ejecución cuando la información estática no es suficiente para aceptar o rechazar definitivamente un programa. Esta tesis demuestra que las ideas de diseño detrás de los tipos graduales pueden aplicarse a los sistemas de tipos-y-efectos, tanto para aumentar la expresividad de estos sistemas así como para proveer flexibilidad para migrar programas con efectos secundarios impl ́ıcitos e irrestrictos hacia programas con una disciplina de efectos completamente estática. Se adaptaron ideas de tipos graduales para introducir verificación gradual de efectos para sistemas de tipos-y-efectos. La verificación gradual de efectos habilita al programador para decidir dónde y cuándo introducir anotaciones de efectos, agregando verificaciones en tiempo de ejecución cuando las anotaciones estáticas son insuficientes. Para evitar redefinir la verificación gradual de efectos para cada disciplina de tipos-y-efectos, introducimos verificación gradual de efectos para una plataforma genérica de tipos-y-efectos, en la que se puede instanciar cualquier disciplina de efectos monotónica, produciendo un sistema coherente. Presentamos la verificación gradual de efectos basándonos en conceptos de interpretación abstracta para construir la verificación gradual de efectos genérica. Utilizando verificación gradual de efectos genérica, introducimos tipos graduales para sistemas de tipos-y-efectos: un sistema donde las anotaciones de efectos y de tipos no son obligatorias, y donde se introducen verificaciones en tiempo de ejecución y casts cuando la información estática no es suficiente para asegurar la coherencia de un programa. De la manera definida, los tipos graduales para sistemas de tipos-y-efectos permiten migrar desde sistemas carentes de anotaciones de efectos o de tipos hacia una disciplina estática de tipos-y-efectos de manera segura.

Magíster en Ciencias, Mención Computación / Ingeniero Civil en Computación / En el campo de los sistemas distribuidos, lograr la coordinación entre diversas unidades de cómputo y sub-sistemas es una tarea compleja, pues cada unidad de computo se comporta distinta a las demás, de forma concurrente y de manera descentralizada. Con el fin de expresar como diversas unidades de computo se comunican unas con otras, se utilizan definiciones de protocolos. Session types son una disciplina de tipos que permite lograr la coordinación entre muchos participantes de un sistema distribuido, mediante la definición de un protocolo coreográfico. La disciplina de tipos impone condiciones sobre la coreografía con el fin de asegurar que el sistema distribuido que la implementa se comporta de la forma en la que fue definido y además posee garantías sobre propiedades de la comunicación. Entre las propiedades importantes se encuentran la ausencia de: deadlocks, mensajes huérfanos y recepciones inesperadas de mensajes. La coreografía es expresada como una entidad global, la cual es projectada a distintos tipos, uno para cada participante involucrado en la coreografía. Dichos tipos son usados para un proceso de typecheck que verifica que las implementaciones de las unidades distribuidas, llamadas procesos, se comportaran en la interacción global como se espera. Se muestra que lograr modularidad en session types no es trivial. Para ello, se presenta un caso de estudio en el que el uso de definiciones modulares para session types introduce problemas en el comportamiento global luego de su composición. Comenzando desde el caso de estudio, se explica como se introducen dichos problemas al componer sub-sessiones. Se muestra como los problemas globales pueden ser evitados gracias al uso de un mecanismo de composición que se basa en interacciones de bloqueo entre participantes. En este trabajo se desarrolla una extensión de un sistema de tipos que permite la composición modular de session types (MCST). MCST se basa en condiciones impuestas sobre definiciones modulares de sub-sessiones, además de un sistema de tipos que permite verificar sub-sessiones por separado, y un mecanismo de composición que produce sistemas bien formados. La solución presentada es modular, dado que mantiene sus definiciones separadas con el fin de reusarlas. Las condiciones para verificar correctitud no dependen del contexto en el cual una sub-session es llamada.El mecanismo de composición reusa conceptos de inlining y composición con ciclos de trabajos previos, haciéndolas aplicables en más casos, lo que resulta en un sistema más expresivo. MCST mantiene las garantías de comunicación de session types mencionadas previamente. Ademas, MCST mejora la expresividad de session types, dado que la nueva disciplina de tipos con el mecanismo de composición permite definir coreografías que no son permitidas en el estado del arte de session types.

Magíster en Ciencias, Mención Computación / Operaciones realizadas por un programa de computación pueden producir efectos. Efectos computacionales pueden ser definidos como operaciones que interactúan y que se comunican con su ambiente. Ejemplos de efectos son imprimir en pantalla, leer data de usuarios, asignación de memoria, excepciones, etc. Una función que no produce efectos es llamada una función pura. Los sistemas de efectos ayudan a controlar estos efectos colaterales . Por ejemplo, permite correr funciones puras en paralelo sin temer a obtener carreras de datos. Una function pura también preserva la transparencia referencial, asegurando que si una función es aplicada con los mismos argumentos más de una vez, el resultado sigue siendo el mismo. En este trabajo se diseñó y desarrolló un sistema de efectos genérico que se caracteriza por ser práctico, combinando para ello tres conceptos de efectos fundamentales: efectos graduales, efectos polimórficos y efectos personalizados. Debido a que la verificación estática puede ser demasiada restrictiva (algunos programas válidos son rechazados), Bañados et al propusieron una teoría que mezcla chequeo de efectos dinámico y estático, permitiendo a desarrolladores a adaptar gradualmente una disciplina de efectos en proyectos existentes. Este sistema de efectos graduales da la flexibilidad para moverse entre un sistema completamente anotado con efectos (estático) a uno sin anotaciones de efectos (dinámico), introduciendo chequeos en tiempo de ejecución cuando sea necesario. Rytz et al diseño e implementó un sistema de efectos polimórficos, el cual incrementa la expresividad de los sistemas de efectos usando patrones de orden superior para efectos. Una función es polimórfica en los efectos de su argumento si es que los efectos de la función depende de los efectos de su argumento. Esto permite expresar funciones como map, pura en efectos salvo por los efectos que la función que recibe como argumento pueda producir. En general los dominios de efectos carecen de localidad: tienen un alcance muy general. Por ejemplo: no es necesario considerar toda operación de entrada/salida como un efecto. Los sistemas de efectos no permiten hacer un seguimiento de efectos de operaciones específicas definidas por el usuario. Incorporar y personalizar un sistema de efectos requiere conocimientos previos acerca de sistemas de efectos. Inclusive, con la experiencia adecuada, implementar una disciplina de efectos puede ser difícil o lento. Es necesario un sistema que permita la fácil creación de dominios de efectos. El trabajo de ésta tesis consiste en tres partes. La primera parte extiende la formalización del sistema de efectos graduales añadiendo efectos polimórficos. En la segunda parte se diseña la sintaxis y semántica necesaria para crear dominios de efectos a través de un lenguaje específico de dominio (DSL). El DSL permite la creación de dominios de efectos con estructuras y relaciones complejas, y la especificación de donde los efectos deben ser producidos mediante especificaciones de efectos externa. También se entrega una formalización del DSL extendiendo el sistema de efectos combinado de la primera parte. La tercera y final parte consiste en la implementación del sistema final de efectos y del DSL en el lenguaje de programación Scala a través de plugins para el compilador.

No description available.

D.L. A 881-2006

Este proyecto tiene como objetivo principal el diseño, desarrollo e implementación de un intérprete de un lenguaje de programación que pueda ser usado en los primeros cursos de introducción a la computación. El trabajo muestra cómo se pueden crear intérpretes, lo que en nuestro país tiene escasa tradición, a diferencia de lo que ocurre en los países más desarrollados. Además, presenta un entorno de desarrollo integrado para facilitar la introducción a la programación, ofreciendo un ambiente amigable y un lenguaje de programación totalmente basado en el idioma español. En opinión de la autora esta segunda característica favorecerá a que el alumno entienda mejor el lenguaje y los procesos de computación. En el capítulo 1 del presente documento se presenta la descripción del problema de escoger un lenguaje adecuado para la enseñanza de los primeros cursos de programación, las opciones que tenemos en nuestra actualidad y una posible solución a este problema. En el capítulo 2 se formula una propuesta que resuelve el problema planteado en el capítulo 1 que permite definir el lenguaje, su funcionamiento y el entorno en el que se ha de ejecutar. El capítulo 3 presenta la implementación del intérprete y la del entorno, propuestos anteriormente. En el capítulo 4 se exponen las observaciones, conclusiones, recomendaciones y trabajos futuros, tanto del intérprete como del entorno. / Tesis