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.

Ingeniera Civil en Computación / La robótica es un área de estudio joven que presenta gran potencial de progreso. Esto incita a expertos de diversas áreas a contribuir en su desarrollo mediante proyectos de investigación y de ingeniería. En este escenario el estudiante Miguel Campusano y el profesor Johan Fabry, ambos integrantes del DCC de la Universidad de Chile, proponen un lenguaje de programación para robots denominado LRP. Este lenguaje es implementado en Pharo Smalltalk, un lenguaje de programación caracterizado por su fuerte orientación a objetos y su poderoso ambiente de desarrollo. Utilizar LRP con un robot determinado requiere una aplicación estilo puente escrita en Pharo, que sirva como interfaz de comunicación entre el lenguaje y el robot. Previo a la realización de este trabajo, sólo dos puentes habían sido implementados. Estos permitieron hacer de pruebas con algunos robots. No obstante, para nes investigativos es muy deseable utilizar el lenguaje LRP con tantos robots como sea posible. El AR.Drone 2.0, de la empresa Parrot, es un cuadricóptero eléctrico no tripulado, controlado remotamente y que cuenta con diversos sensores. Este robot es un excelente caso de prueba para LRP, dada su gran diferencia con los robots utilizados anteriormente. La solución presentada en este trabajo de memoria contempla la implementación de la infraes- tructura necesaria para hacer pruebas utilizando LRP con el AR.Drone y su validación mediante distintos programas de prueba implementados en LRP. Se ha creado una API capaz de comuni- carse con el drone y la aplicación tipo puente requerida. Ambas aplicaciones fueron escritas en Pharo. La API permite establecer una conexión con el drone, recibir los datos que publica y enviar comandos de control y con guración. El puente adapta una serie de métodos de la API y permite utilizarlos desde LRP. Provee además mecanismos intuitivos para que el desarrollador interactúe directamente con el drone durante una sesión de programación. La mayoría de las di cultades enfrentadas durante el desarrollo de la API se debieron a la indocumentación de características o requerimientos impuestos por el rmware del drone. Por otro lado, el desarrollo de esta he- rramienta permitió generar conocimiento técnico especí co sobre el AR.Drone, relevante para trabajos posteriores que utilicen este robot. Los programas de ejemplo creados en LRP evidenciaron que no todas las cualidades de la modalidad de programación en vivo pueden ser aprovechadas trabajando con un robot aéreo. Esto porque es difícil restringir límites para el movimiento del robot, por su limitado tiempo de autonomía y porque la interrupción de una sesión, producto de un choque por ejemplo, implica que el desarrollador deba suspender su trabajo para reposicionar y despegar el robot. Sin embargo, live programming permitió ajustar las variables asociadas a programas ya creados, lo que adquiere gran valor al momento de establecer distancias esperadas para el recorrido del robot. Finalmente, la sintaxis de LRP y sus diagramas de estado animados en vivo facilitaron enormemente el proceso de desarrollo.

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.

Doctor en Ciencias, Mención Computación / Los cambios continuos en el código fuente de un programa pueden inadvertidamente introducir una regresión de rendimiento en tiempo de ejecución. Dichas regresiones se refieren a situaciones donde el rendimiento de un programa se degrada en comparación de versiones anteriores del mismo, aunque la nueva versión funcione correctamente. Ejecutar puntos de referencia en cada versión de un programa es una técnica tradicional utilizada para identificar regresiones en etapas tempranas. A pesar de ser efectiva, esta técnica exhaustiva es difícil de llevar a cabo en la práctica, principalmente por la alta sobrecarga que esta actividad demanda. En esta tesis, realizamos un estudio empírico sobre una variedad de programas, con el fin de evaluar cómo el rendimiento de un programa evoluciona en el tiempo, a medida que es modificado. Guiados por este estudio, proponemos Horizontal Profiling, una técnica de muestreo para inferir si una nueva versión de un programa introduce una variación de rendimiento, usando información de la ejecución de versiones anteriores. El objetivo de Horizontal Profiling es reducir la sobrecarga que requiere monitorear el rendimiento de cada versión, ejecutando los puntos de referencia solo en las versiones que contengan cambios costosos de código fuente. Presentamos una evaluación en la cual aplicamos Horizontal Profiling para identificar regresiones de rendimiento en un número de programas escritos en en el lenguaje de programación Pharo. En base a las aplicaciones que analizamos, encontramos que Horizontal Profiling es capaz de detectar más del 80% de las regresiones de rendimiento, ejecutando los puntos de referencia en menos del 20% de las versiones. Adicionalmente, describimos los patrones identificados durante nuestro estudio empírico, y detallamos cómo abordamos los numerosos desafíos que enfrentamos para completar nuestros experimentos. / Este trabajo ha sido parcialmente financiado por CONICYT a través de la beca CONICYT-PCHA/Doctorado Nacional para extranjeros/2013-63130199, OBJECT PROFILE y LAM RESEARCH

Magíster en Ciencias, Mención Computación. Ingeniero Civil en Computación / Los lenguajes modernos de programación orientada a objetos han aliviado de manera impor- tante a los programadores la tarea de administrar memoria. A pesar de la eficiencia de los recolectores de basura y herramientas de análisis de programas en tiempo real, aún existe una porción importante de memoria siendo desaprovechada. El desaprovechamiento de memoria en software posee graves consecuencias, incluyendo frecuentes interrupciones en la ejecución debido a la presión ejercida sobre el recolector de basura y el uso ineficiente de dependencias entre objetos. Hemos descubierto que supervisar los lugares de producción de objetos y la equivalencia de los objetos producidos es clave para identificar ineficiencias causadas por objetos redundantes. Hemos implementado optimizaciones para reducir el consumo de memoria de seis aplicaciones industriales, obteniendo una reducción superior al 40% en el uso de memoria en la mitad de las aplicaciones sin poseer conocimiento previo de las mismas. Nuestros resultados replican parcialmente los resultados obtenidos por Marinov y O Callahan y exploran nuevas formas de identificar objetos redundantes. / Este trabajo ha sido parcialmente financiado por CONICYT-PCHA/Magíster-Nacional/2015-22150809

Doctor en Ciencias, Mención Computación / Gradual Typing permite a un programador aplicar tipos estáticos a ciertas partes de un programa, dejando el resto dinámicamente tipeado. Sin embargo, esto viene con un costo en el rendimiento. Una razón es que el runtime tiene que realizar siempre un casteo en el borde entre tipos estáticos y dinámicos. Otra razón es que el borde puede ser creado accidentalmente. Esto también trae un efecto lateral de reducir la fiabilidad del código estático, porque ahora el programador no puede garantizar que su código no arrojará errores de tipo en tiempo de ejecución. En este trabajo de tesis, mejoramos el rendimiento y la fiabilidad de los programas gradualmente tipeados. Para esto, desarrollamos un lenguaje gradualmente tipeado, Gradualtalk, y luego presentamos dos novedosas ideas: hybrid strategy y Confined Gradual Typing. La hybrid strategy es una nueva forma de insertar los casts al invocar métodos que combina dos estrategias existentes, permitiendo obtener el mejor rendimiento de ambas. Validamos esta afirmación con benchmarks. Confined Gradual Typing refina gradual typing con anotaciones para prohibir explícitamente ciertos cruces de frontera entre el código estáticamente y dinámicamente tipeado. Nosotros desarrollamos formalmente dos variantes de CGT que capturan diferentes compromisos entre flexibilidad/garantías. Probamos que CGT es type sound y que las anotaciones ofrecen las garantías esperadas.

Doctor en Ciencias, Mención Computación / Los lenguajes de tipado dinámico permiten un desarrollo ágil, el cual es util para construir prototipos rápidamente. Sin embargo, cuando estos pequeños programas se convierten en aplicaciones grandes, depurar se vuelve una tarea tediosa. Esto se debe principalmente a que los errores son solo detectables en tiempo de ejecución. Smalltalk, al ser un lenguaje de tipado dinámico, sufre de estos problemas. Los sistemas de tipos pueden disminuir ciertos errores de los lenguajes de tipado dinámico. Además, la inserción de tipos mejora la documentación de APIs, provee mejor soporte a los editores y ayuda a optimizar la compilación. Los sistema de tipos, especialmente diseñados para lenguajes existentes, son llamados sistema de tipos retro-alimentados (retrofitted type systems en inglés). Diseñar un sistema de tipos retro-alimentado es una tarea complicada. Esto se debe a que tales sistemas de tipos deben soportar patrones de programación muy particulares (llamados idioms), minimizar la refactorización de código por la inserción de tipos, y proveer una integración entre las partes (ej. módulos) con y sin tipos. Estos problemas son exacerbados cuando el lenguaje destino es altamente dinámico, como Smalltalk. Si bien se ha intentado insertar tipos en Smalltalk, el ejemplo mas notable es Strongtalk, ellos no han sido diseñados de un modo de ser sistemas de tipos retro-alimentados. Ademas Strongtalk es un sistema de tipos opcional, es decir que las garantías estáticas no necesariamente se cumple en tiempo de ejecución. En este trabajo de tesis, nosotros presentamos Gradualtalk, un sistema de tipos retro-alimentado para Smalltalk, que soporta la mayoría de las características particulares e idioms de Smalltalk. En la parte del diseño, nosotros analizamos detalladamente cual es el mejor sistema de tipos gradual y aquellas extensiones que mejor encajan en Gradualtalk. Cada una de estas extensiones son claramente justificadas usando evidencia (empírica) disponible en la literatura o propuesta por nosotros. En detalle, nosotros presentamos como evidencia empirical dos estudios a larga escala sobre las características dinámicas de Smalltalk y sobre los predicados de tipos. Ademas presentamos tres estudios preliminares sobre el uso de self, el uso de variables que pueden representar varios valores de diferente tipos, y el uso de colecciones. Con toda esta información implementamos una primera version de Gradualtalk. Finalmente, validamos Gradualtalk mediante la inserción de tipos de varios proyectos Smalltalk reales.

La programación orientada a aspectos (POA) es un paradigma de programación. Permite encapsular funcionalidad que se encuentra dispersa en un sistema. Para ello utiliza pointcuts, predicados que definen eventos del programa, y advices, el código que es ejecutado en los eventos definidos por un pointcut. Un aspecto es una entidad que agrupa pointcuts y advices. AspectJ es un lenguaje de programación para POA. Está diseñado como una extensión de Java, de forma que cualquier programa Java es también un programa AspectJ válido. Además del compilador oficial del proyecto AspectJ existen otros, de los cuales AspectBench Compiler (abc) es el más avanzado. La reentrancia de aspectos ocurre cuando la ejecución de un aspecto desencadena nuevamente su propia ejecución; produciéndose bucles infinitos. Actualmente la reentrancia se soluciona utilizando chequeos y patrones adhoc. La introducción de niveles de ejecución evita la reentrancia de aspectos. La ejecución del programa se separa en distintos niveles. Por defecto, la computación base ocurre en el nivel 0, mientras que los aspectos que observan esta ejecución se ubican en el nivel 1. La ejecución en el nivel 1 sólo puede ser observada desde el nivel 2, y así sucesivamente. Esta estructura para la ejecución de los programas soluciona casi todos los casos de reentrancia. Para el caso faltante, se utiliza un mecanismo adicional de control de reentrancia. Para esta memoria se extendió el compilador abc para incorporar una adaptación de niveles de ejecución. El lenguaje soportado por el compilador extendido incorpora nueva sintaxis para ello. Y los programas compilados contienen rutinas adicionales que agregan la estructura de niveles de ejecución y el control de reentrancia. Además, es posible controlar el nivel de ejecución en que se ejecutará una expresión, si fuese necesario. Se hicieron distintas pruebas para validar el trabajo realizado. Se confeccionaron tests para las distintas funcionalidades que, en conjunto, implementan niveles de ejecución. También se verificó la correcta compilación y ejecución de AJHotDraw, un framework para interfaces gráficas de programas de dibujo. Adicionalmente se probó el compilador con RacerAJ, una herramienta para la detección de data races implementada en AspectJ. RacerAJ es de interés porque incorpora pointcuts para evitar la ocurrencia de reentrancia de aspectos; removidos estos pointcuts, el programa funciona correctamente al ser compilado con esta versión extendida de abc. Además se realizó un ligero análisis de performance para medir el impacto en los programas compilados. Para ello se utilizó una suite de benchmarks para AspectJ. Se compararon los tiempos de ejecución logrados al utilizar el compilador desarrollado y la versión original.

La programación orientada a aspectos es un paradigma de programación que intenta solucionar el problema de las funcionalidades transversales, esto es, funcionalidades de la aplicación que están dispersas por muchas áreas del código, y no pueden separarse en forma eficiente usando el paradigma de programación orientada a objetos. Un aspecto representa una funcionalidad transversal de la aplicación. Éste incluye en su definición un pointcut, que representa un conjunto de puntos en la ejecución de la aplicación que van a ser capturados por el aspecto, y un advice, que representa la funcionalidad del aspecto, esto es, el código que va a ser ejecutado en los puntos capturados. En este trabajo se diseñó e implementó un lenguaje de aspectos para el lenguaje de programación Pharo Smalltalk, donde se incluyeron características destacadas de otros lenguajes de aspectos, junto a nuevas funcionalidades que le otorgan un mayor control y flexibilidad al lenguaje desarrollado. El lenguaje desarrollado incluye un sistema de definición de patrones para la definición de los pointcuts, reglas de precedencia globales y a nivel de pointcut. También contiene modificadores de clases similares a las inter-type declarationsde AspectJ, y un sistema de control dinámico en el orden de ejecución de los advice. Para el lenguaje desarrollado se implementó el concepto de membranas computacionales. Éstas son una forma de controlar el alcance que tienen los aspectos en el sistema, permitiendo controlar problemas como la reentrancia en los aspectos, esto es, cuando un aspecto captura un evento desencadenado por sí mismo. Junto a esto, las membranas computacionales son capaces de controlar la visibilidad que los aspectos tienen sobre el sistema donde son instalados. Se creó una suite de test usando el framework para test unitarios de Pharo Smalltalk, para comprobar el correcto funcionamiento del lenguaje desarrollado, además, se comprobó el grado de cobertura de la suite de test usando el software Hapao. Finalmente, se comprobó el funcionamiento del lenguaje de aspectos desarrollado, usándolo para refactorizar algunas partes del software de análisis dinámico de código Spy. Se realizaron algunos benchmark para comprobar el sobrecosto generado por la infraestructura de aspectos desarrollada, donde se pudo apreciar un sobrecosto variable, siendo elevado en algunos casos.