Principal Type Sepcialization of Dynamic Sum-Types

Tesina de Licenciatura en Cs. de la Computación

Fac. Cs. Exactas, Ingeniería y Agrimensura

Universidad Nacional de Rosario

IX Jornadas de Informática e Investigación Operativa

Facultad de Informática, Universidad de la Republica

Montevideo, Uruguay

Alejandro C. Russo

russo@fceia.unr.edu.ar

http://www.fceia.unr.edu.ar/~russo/

Introducción

Program Specialization

(Partial Evaluation)

Source Code

Residual Codes

Type Specialization

Es una forma general de “type inference” para lograr program
specialization

Refinar el sistema de tipos del lenguaje
residual

Residual Type System

Residual Program

Source Program

Source Type System

Resumiendo...

Información
Estática

Información
Dinámica

Introducción de un juicio (judgement) responsable de la
especialización de programas

Source Program

Source Type

Residual Program

Residual Type

Specialization
Assignment
(Free Variables)

Se especifica el proceso de especialización mediante un
conjunto de reglas formales

Source Program

Residual Program

Source Program

Residual Program

Source Program

Residual Program

Source Program

Residual Program

Source Type

Residual Type

Source Program

Residual Program

Source Type

Residual Type

Source Program

Residual Program

Source Type

Residual Type

Ejemplos...

Ejemplos...

¿?

¿?

¿en qué influye esta decisión?

Si una expresión es polivariante, entonces puede especializarse
en más de una forma

Marcamos en el source program qué expresiones son
polivariantes y dónde se utilizan (poly / spec)

La expresión dentro de poly
se especializó dos veces

Para armar la tupla tengo que conocer todos los spec

Otra especialización válida

¿Conocer todos los specs?

Hay infinitas especializaciones posibles (no relacionadas)

Para especializar la función debo esperar a conocer su
argumento (¿especialización modular?)

Problema: falta de principalidad (lack of principality)

Principal Type Specialization

Queremos especializar programas en forma modular

Ausencia de información. ¿Qué hacemos?

¿Haskell?

Queremos especializar pero, si nos falta información, diferiremos
las decisiones

Las decisiones afectan al código generado por la especialización

Necesidad de principalidad

Especialización

Queremos especializar pero, si nos falta información, diferiremos
las decisiones

Las decisiones afectan al código generado por la especialización

Necesidad de principalidad

Especialización

Queremos especializar pero, si nos falta información, diferiremos
las decisiones

Las decisiones afectan al código generado por la especializacion

Necesidad de principalidad

Especialización

Evidencia de predicados
¿Para qué nos sirve?

Teoría de “Qualified Types” de Mark Jones (Ph.D. Thesis,
Cambridge, 1991)

Pablo E. Martínez López adaptó esta teoría para usarla en el proceso
de especialización

Source Program

Source Type

Specialization
Assignment
(Free Variables)

Conjunto de
Predicados

El sistema P captura todas las posibles especializaciones de
un source program (inclusive la principal)

Si escribiera un algoritmo, ¿qué especialización debería
obtener?

Especialización Principal
+	Mecanismo de Instanciación Automatizable
= Obtengo la especialización que necesito en el momento
necesario

Unificar y calcular evidencia de predicados

Las reglas...

Entailment

Las reglas (continuación)...

Ejemplos...

¿Conocer todos los specs?

Principal Type Specialization of Dynamic Sum-Types

Introducir la capacidad de especializar dynamic sum-types

¿Qué queremos?

Desapareció una rama

¿?

¿Principalidad?

Este trabajo...

Se extendieron los sitemas de reglas formales para poder
manipular dynamic sum-types

Se eliminan aquellas ramas de los cases que no son necesarias(menos código muerto)

No se generan declaraciones de constructores que no se utilizan(menos código muerto)

Libertad para combinar constructores y cases dinamicos con las construcciones poly y spec

Se extendieron las demostraciones de la tesis de doctorado de Pablo E. Martínez López para demostrar que el sistema sigue manteniendo la noción de principalidad

Este trabajo (continuación II)...

Se extendio el prototipo ya existente (Mónadas, Clases, etc.)

Se detectaron y arreglaron algunos bugs

Se implento constraint solving (no se formalizo)

¿Preguntas?

¡Muchas Gracias!

2004-08-18T21:58:17