PDF de programación - Metaprogramación - Computando en tiempo de compilación

Metaprogramación

Computando en tiempo de compilación

Marcelo Arroyo

U.N.R.C.

FCEIA, JCC - 2010

Contenidos

1

Introducción

Metaprogramación
Herramientas de metaprogramación

2 Lenguajes de dos niveles

C++ templates
Converge
Template Haskell

3 Lenguajes de dominio específicos

DSLs en C++

4 Programación orientada a lenguajes

Lenguajes extensibles
Ventajas y desventajas de la metaprogramación
Conclusión

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Metaprogramación

Metaprogramación
Conjunto de técnicas y herramientas para manipular
programas en tiempo de compilación

Metaprograma

escrito en algún metalenguaje
el programa manipulado se denomina lenguaje objeto
un lenguaje reflexivo permite ser su propio metalenguaje

Implementación

Macros
Sistemas de transformación de programas

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Metaprogramación

Metaprogramación
Conjunto de técnicas y herramientas para manipular
programas en tiempo de compilación

Metaprograma

escrito en algún metalenguaje
el programa manipulado se denomina lenguaje objeto
un lenguaje reflexivo permite ser su propio metalenguaje

Implementación

Macros
Sistemas de transformación de programas

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Metaprogramación

Metaprogramación
Conjunto de técnicas y herramientas para manipular
programas en tiempo de compilación

Metaprograma

escrito en algún metalenguaje
el programa manipulado se denomina lenguaje objeto
un lenguaje reflexivo permite ser su propio metalenguaje

Implementación

Macros
Sistemas de transformación de programas

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Metaprogramación

Aplicaciones

Programación genérica

C++ STL
Bibliotecas C++ Boost

Optimización a nivel de aplicación

Biltz++: Object Oriented Scientific Computation

Independencia de herramientas externas
Evaluación parcial
Programación orientada a aspectos
Lenguajes de dominio específico (DSLs)

fp++
lp++
ag++

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Metaprogramación

Aplicaciones

Programación genérica

C++ STL
Bibliotecas C++ Boost

Optimización a nivel de aplicación

Biltz++: Object Oriented Scientific Computation

Independencia de herramientas externas
Evaluación parcial
Programación orientada a aspectos
Lenguajes de dominio específico (DSLs)

fp++
lp++
ag++

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Metaprogramación

Aplicaciones

Programación genérica

C++ STL
Bibliotecas C++ Boost

Optimización a nivel de aplicación

Biltz++: Object Oriented Scientific Computation

Independencia de herramientas externas
Evaluación parcial
Programación orientada a aspectos
Lenguajes de dominio específico (DSLs)

fp++
lp++
ag++

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Metaprogramación

Aplicaciones

Programación genérica

C++ STL
Bibliotecas C++ Boost

Optimización a nivel de aplicación

Biltz++: Object Oriented Scientific Computation

Independencia de herramientas externas
Evaluación parcial
Programación orientada a aspectos
Lenguajes de dominio específico (DSLs)

fp++
lp++
ag++

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Metaprogramación

Aplicaciones

Programación genérica

C++ STL
Bibliotecas C++ Boost

Optimización a nivel de aplicación

Biltz++: Object Oriented Scientific Computation

Independencia de herramientas externas
Evaluación parcial
Programación orientada a aspectos
Lenguajes de dominio específico (DSLs)

fp++
lp++
ag++

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Metaprogramación

Aplicaciones

Programación genérica

C++ STL
Bibliotecas C++ Boost

Optimización a nivel de aplicación

Biltz++: Object Oriented Scientific Computation

Independencia de herramientas externas
Evaluación parcial
Programación orientada a aspectos
Lenguajes de dominio específico (DSLs)

fp++
lp++
ag++

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Herramientas de metaprogramación

Lenguajes de programación

LISP: quasiquote expressions
C++ templates
Template Haskell
Converge
Scala

Herramientas de generación de procesadores lenguajes

ADF-SDF Meta Environment
Stratego/XT
JetBrains MTS
AntLR, . . .

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Herramientas de metaprogramación

Lenguajes de programación

LISP: quasiquote expressions
C++ templates
Template Haskell
Converge
Scala

Herramientas de generación de procesadores lenguajes

ADF-SDF Meta Environment
Stratego/XT
JetBrains MTS
AntLR, . . .

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

C++ templates

C++ templates: Características

Soporte para programación genérica (tipos y funciones
parametrizadas)
Especialización de templates y pattern matching

Templates recursivos
Permiten implementar evaluación parcial
Computación estática
Implementación de instropección (estática)
Static checking

C++ templates
Fragmento Turing-computable

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

C++ templates

C++ templates

Computación estática

template < i n t n>
struct
f a c t o r i a l

s t a t i c const

{
i n t

n∗ f a c t o r i a l <n−1 >:: r e s u l t ;

r e s u l t =

template <>
struct

f a c t o r i a l <0> {

} ;

} ;

/ / s p e c i a l i z a t i o n

s t a t i c const

i n t

r e s u l t = 1;

i n t

fac12 = f a c t o r i a l <12 >:: r e s u l t ;

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

C++ templates

C++ templates

Generación de código

i >

template < i n t
i n l i n e f l o a t meta_dot ( f l o a t a [ ] ,
{

f l o a t b [ ] )
return meta_dot < i −1>(a , b ) + a [ i ] ∗ b [ i ] ;

template <>
i n l i n e f l o a t meta_dot <0>( f l o a t a [ ] ,
{

return a [ 0 ] ∗ b [ 0 ] ;

f l o a t b [ ] )

}

}

f l o a t x [ 3 ] , y [ 3 ] , z = meta_dot <2>(x , y ) ;
/ / z=x [ 0 ]∗ y [ 0 ] + x [ 1 ]∗ y [ 1 ] + x [ 2 ]∗ y [ 2 ]

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

C++ templates

C++ templates

Calculando tipos: traits

template typename<T> −− default . T −> T
struct a v g _ t r a i t s {

typedef T type ;

} ;
template typename<>
struct a v g _ t r a i t s <int > {

−− i n t −> f l o a t

typedef

f l o a t

type ;

} ;
typename a v g _ t r a i t s <int > : : type r ;
r = sum_array ( a ,N ) / N;

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Converge

Converge

Un ejemplo

func expand_power(n, x):

if n == 0:

return [| 1 |]

else:

return [| $c{x}*$c{expand_power(n-1,x)} |]

func mk_power(n):

return [|

func (&x):

return $c{expand_power(n, [| &x |])}

|]

power3 := $<mk_power(3)>
-- power3 = func(x): return x*x*x*1

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Converge

Splice
$<expr> se evalúa (expande) en compilación

Quasi-quotes e inserciones

Quasi-quote: [| expr |] denota un AST
Inserciones:

${e} evalúa una expresión y retorna el AST resultante
dentro del quasi-quote en el que aparecen.
Renombra las variables apareciendo en e por nombres
frescos
$c{e} idem al anterior pero sin renombre de variables,
permitiendo la captura de variables libres
$p{e} pragma: evalúa la expresión y descarta su resultado

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Converge

Splice
$<expr> se evalúa (expande) en compilación

Quasi-quotes e inserciones

Quasi-quote: [| expr |] denota un AST
Inserciones:

${e} evalúa una expresión y retorna el AST resultante
dentro del quasi-quote en el que aparecen.
Renombra las variables apareciendo en e por nombres
frescos
$c{e} idem al anterior pero sin renombre de variables,
permitiendo la captura de variables libres
$p{e} pragma: evalúa la expresión y descarta su resultado

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Template Haskell

Metaprogramación en Template-Haskell

Template-Haskell
Macro-procesador escrito en Haskell e integrado en
compiladores e intérpretes por boostrapping.

Ejemplo

import Language . Haskell .TH

tupleRep : :
tupleRep n = do id <− newName " x "

I n t −> Q Exp

return

$ LamE ( VarP id )
( TupE $ r e p l i c a t e n $ VarE id )

tupleReplicate 3 ⇒ (\x.(x, x, x))

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

Template Haskell

Template-Haskell

Splices: denotados como $id o $(expr)

main = do p r i n t

( $ ( tupleRep 2) 1) −− ( 1 , 1 )

Quotation: generadores de ASTs (mónada Q t)

[| expr |], retorna un valor de tipo Q Exp
[p| pattern |], retorna un valor de tipo Q Pat
[d| decl-list |], retorna un valor de tipo Q [Dec]
[t| type |], retorna un valor de tipo Q Type

Ejemplo: [| \x -> x |] se traducirá a
( do id <− newName " x " ;

return $ LamE [ VarP id ]

( VarE id ) )

Introducción

Lenguajes de dos niveles

Lenguajes de dominio específicos

Programación orientada a lenguajes

DSLs en C++

Definición de parsers. C++/Boost::Spirit

EBNF
group ::= ’(’ expression ’)’
factor ::= integer | group
term ::= factor ((’*’ factor) | (’/’ factor))*
expression ::= term ((’+’ term) | (’-’ term))*

EBNF en Boost::Spirit

group
f a c t o r
term

expression

| group ;

= ’ ( ’ >> expre