memoria

Desarrollo de un compilador para un lenguaje
funcional con gesti´n expl´
o
ıcita de la memoria

Proyecto de Sistemas Inform´ticos
a

´
Autores: Jes´ s Conesa, Ricardo L´pez, Angel Lozano
u
o
Profesor director: Clara Mar´ Segura D´
ıa
ıaz
Facultad de Inform´tica
a
Universidad Complutense de Madrid
Julio 2006

3

Resumen
Este proyecto de la asignatura de SistemasInfom´ticos, titulado “Desarrollo del compilador de
a
un lenguaje functional con gesti´n expl´
o
ıcita de la memoria”, est´ enmarcado en un proyecto m´s
a
a
grande destinado al desarrollo de un lenguaje funcional de alto nivel, llamado SAFE, que permite
que el programador gestione la memoria para que no se necesite un recolector de basura en tiempo
de ejecuci´n. Dispone adem´s de un sistema de tiposque garantiza que no se producir´n punteros
o
a
a
descolgados en tiempo de ejecuci´n. El proyecto se encarga de la implementaci´n de la parte frontal
o
o
del compilador, utilizando Alex y Happy como herramientas para el desarrollo del analizador l´xico
e
y sint´ctico y Haskell para la implementaci´n del analizador sem´ntico y el renombramiento de
a
o
a
identificadores, as´ como elresto de los m´dulos. Uno de estos m´dulos, que implementa una de las
ı
o
o
caracter´
ısticas del lenguaje y del compilador es el de las transformaciones amargativas, debido a
que SAFE est´ concebido con dos sintaxis diferentes: una m´s cercana al programador —llamada
a
a
dulce— que facilita la programaci´n y otra m´s cercana a la implementaci´n — llamada amarga—
o
a
o
m´s apta para lasfases posteriores del compilador. El objetivo de este proyecto es, pues, tener
a
una herramienta para probar y validar la portabilidad de diferentes algoritmos desde Haskell hasta
SAFE, permitiendo evaluar la viabilidad de este ultimo lenguaje.
´

Abstract
This “Sistemas Informticos” project, entitled “Desarrollo del compilador de un lenguaje functional con gestin explcita de la memoria” —“Development of a compiler for a functional language
with explicit memory management” — is part of a broader project devoted to the development of a
high-level functional language, called SAFE, which allows the programmer to do memory management in order that a garbage collector would not be needed at runtime. Additionally, a type system
guarantees that dangling pointers will not arise duringexecution. The project is aimed at the implementation of the compiler’s front-end, using Alex and Happy as tools for the development of
the lexical and syntactic parsers, and Haskell for the implementation of the semantic analyzer and
the identifier renamer, as well as the rest of the modules. One of these modules, called desugarer,
implements one feature of the language and its compiler:transforming from sweet to bitter syntax.
This is because SAFE is conceived with two different syntaxes. The one nearer to the programmer
—called sweet— that facilitates programming and the other nearer to the machine —called bitter—
more amenable for the subsequent phases of the compiler. The aim of this project is, then, to have
a tool to validate the portability of different algorithms from Haskell toSAFE, being also a test of
the viability of this latter language.

4

Palabras clave
Compilador: objetivo del proyecto.
Lenguaje funcional: caracter´
ıstica principal del lenguaje desarrollado.
Gesti´n de Memoria: el lenguaje permite al programador gestionar la memoria de forma
o
expl´
ıcita.
Transformaciones: aplicamos transformaciones a la sintaxis del lenguaje.

´
Indicegeneral
1. Introducci´n
o
1.1. Contexto del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Objetivos del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Plan de trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
7
8
8

2. El lenguaje SAFE
11
2.1. Conceptos generales del...