First class syntax, semantics and their composition

Abstract

Idealmente la complejidad es manejada componiendo un sistema en algunas pocas, mas o menos independientes, descripciones mas pequeñas de varios aspectos del artefacto general. Al describir lenguajes de programacion (extensibles), las gramaticas de atributos han resultado ser una excelente herramienta para la definicion modular y la integracin de sus diferentes aspectos. En la tesis se muestra como construir la implementacin de un lenguaje de programacion mediante la composici´on de una coleccion de fragmentos de gramaticas de atributos que describen aspectos separados del lenguaje. Mas especificamente, se describe un conjunto coherente de bibliotecas y herramientas que en conjunto hacen que esto sea posible en Haskell, donde la correccion de la composicion es forzada a traves de la capacidad del sistema de tipos de Haskell para representar gramaticas de atributos como valores de Haskell y sus interfaces como tipos de datos. Los objetos semanticos construidos de este modo se pueden combinar con parsers que son construidos on the fly a partir de fragmentos de parsers y se representan como valores Haskell tipados. Una vez mas el chequeo de tipos impide composiciones incorrectas. A manera de caso de estudio de las tecnicas propuestas en esta tesis, se implemento un compilador para el lenguaje imperativo (Pascal-like) Oberon0. A traves de un diseño incremental, mostramos las capacidades de modularidad de nuestras tecnicas.

Ideally complexity is managed by composing a system out of quite a few, more or less independent, and much smaller descriptions of various aspects of the overall artifact. When describing (extensible) programming languages, attribute grammars have turned out to be an excellent tool for modular definition and integration of their different aspects. In this thesis we show how to construct a programming language implementation by composing a collection of attribute grammar fragments describing separate aspects of the language. More specifically we describe a coherent set of libraries and tools which together make this possible in Haskell, where the correctness of the composition is enforced through the Haskell type system’s ability to represent attribute grammars as plain Haskell values and their interfaces as Haskell types. Semantic objects thus constructed can be combined with parsers which are constructed on the fly out of parser fragments and are also represented as typed Haskell values. Again the type checker prevents insane compositions. As a small case study of the techniques proposed in this thesis, we implemented a compiler for the (Pascal-like) imperative language Oberon0. Through an incremental design, we show the modularity capacities of our techniques.