template metaprogramming
Soledad Alborno
Cholo Lennon
templates (para implementar un ciclo metaprogramado) de un compilador es
limitada, por lo cual, a primera vista, no veo factible llegar a calcular el
número 1500 de la secuencia, a menos claro que consigas algún algoritmo que
puedas resolverlo como mucho en 17 (o algo más dependiendo del compilador)
iteraciones...
Saludos
--
Cholo Lennon
Bs.As.
ARG
"Soledad Alborno" <soledad...@gmail.com>
escribió en el mensaje
news:3b03b8d00801110841m7fe...@mail.gmail.com...
Daniel Gutson
El algoritmo me lo matchetié de la wikipedia, de Dijstra.
(http://en.wikipedia.org/wiki/Regular_number).
Tiene un problema, que es que el punto de corte es la cantidad de
iteraciones del algoritmo, y no el N-ésimo número horrible.
Así que me pasé, y llegué a ...
Estoy curioso por saber, Cholo, de dónde sacaaste esos números tan
curiosos como el 17.
Te propongo modificar este programita así en vez de ser la n-ésima
iteración, es el n-ésimo nro horrible. Dale que es fácil :D
Daniel.
2008/1/20 Cholo Lennon <cholo...@hotmail.com>:
Daniel Gutson
Quiero ver tu versión!! O también estás oxidado!!!
Dale, un fulbito pa la tribuna!! :D
Aprovechá q Gus está de vacaciones toda la semana, jajaja
2008/1/21 Daniel Gutson <daniel...@gmail.com>:
Cholo Lennon
recursiva de templates. Algunos compiladores sobrepasan este límite, pero no
por mucho. De hecho, el programa que posteaste en mi compilador (VC2005) no
compila (con <START, 10>). Lo máximo alcanzado es con <START, 7>
Salu2
--
Cholo Lennon
Bs.As.
ARG
"Daniel Gutson" <daniel...@gmail.com>
escribió en el mensaje
news:23ab4d1c0801201907r70a...@mail.gmail.com...
Daniel Gutson
para q no sea al pedo esto que mandé, díganme si hay interesados en
q lo explique, por ahi puede servir para dar un pantallazo de TMP.
Daniel.
Fernando Cacciola
Aunque es cierto que esta implementación no llega al número horrible deseado
(por el límite que menciona Cholo), es un muy buen ejemplo de TMP, así que
you propongo que los discutamos. Quizas podrías postear una version
"anotada" y hacer un paralelismo con la version runtime para que sea fácil
entenderlo.
Algo interesante sería cómo encontrarle la vuelta al límite de recusividad
para hacer que llegue hasta el número deseado.
Saludos
Fernando
Daniel Gutson
lo que puedo hacer, dada la mezcla del grado de interes que genera
(poco) y el tiempo que tengo, es esto:
1) la manera de programarlo sale mucho de Prolog (uno de mis lenguages
[muertos] favorito), en donde la recursividad opera sobre listas, y
las listas de elementos se descomponen en [head] (un elemento) y
[tail] (una cola). Es decir que se puede hacer una operacion de 'pop
front'.
Esto explica el NIL y la estructura List.
2) el algoritmo se basa en esto:
- si L es una lista de nros horribles, entonces las listas 2*L,
3*L, y 5*L tambien lo serán (denoto n*L a la lista q es cada elemento
de L multiplicado por n).
- por lo tanto, la manera de expandir L en una 'iteracion' mas, es
hacer un merge entre ellas. Es decir, dada L(i), L(i+1) se obtiene
como
L(i+1) = MERGE( L, 2*L, 3*L, 5*L);
Esto es la metafuncion 'struct HAMMING'
3) lo que sigue es implementacion de como obtener n*L (struct GROW
en mi codigo), y MERGE.
- tanto GROW como MERGE son metafunciones que reciben listas, y
devuelven una lista (::RET).
- GROW( [HEAD | TAIL], N ) := [ N*HEAD | GROW(TAIL, N) ]
- MERGE de 4 listas, es un doble MERGE de dos listas.
- MERGE de 2, elige a que lista arrancarle la cabeza (a la que
tiene el HEAD mas chico, o a ambas si son iguales), y recursiona.
Si alguien tiene alguna pregunta mas, pregunte; sino, no voy a
escribir al vicio :D
Daniel.
Cholo Lennon
escribió en el mensaje
news:23ab4d1c0801221410x664...@mail.gmail.com...
> Fernando,
> lo que puedo hacer, dada la mezcla del grado de interes que genera
> (poco) y el tiempo que tengo, es esto:
Valga la aclaración: En mi caso, no es que no me interese el tema (TMP) ni
mucho menos, realmente me parece algo muy interesante. De hecho he leido
todo lo que anda dando vueltas, desde el paper fundacional hasta libros como
los de Alexandrescu, Vandevoorde/Josuttis, Gurtovoy/Abrahams (Cacciola en
los agradecimientos! :-) etc, etc.
El problema es el tiempo del cual dispongo, el mismo me limita solamente a
participar en cosas puntuales :-(
Salu2
Maximiliano Combina
btw, usando g++ tuve que compilar con -ftemplate-depth-579 (sí, es el
menor numero tal que anduvo). Y el manpage también aclara que uno no
debería sobrepasar 17 :)
On 23 ene, 05:54, "Cholo Lennon" <chololen...@hotmail.com> wrote:
> "Daniel Gutson" <danielgut...@gmail.com>
> escribió en el mensajenews:23ab4d1c0801221410x664...@mail.gmail.com...
Maximiliano Combina
alguna idea (si no entendi mal, lo que hizo Daniel es muy parecido):
Sacado de la wikipedia (http://en.wikipedia.org/wiki/
Haskell_(programming_language) ), la funcion de Hamming en Haskell se
escribe en muy pocas lineas:
hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map
(5*) hamming
where merge (x:xs) (y:ys)
| x < y = x : xs `merge` (y:ys)
| x > y = y : (x:xs) `merge` ys
| otherwise = x : xs `merge` ys
Una vez que tenemos la funcion, podemos aprovechar la laziness de
Haskell para calcular casi cualquier numero en la lista anterior. En
particular, el numero 1500 :
Main> hamming!!1499
859963392
Otra cosa que encontre: Daniel, el programa que enviaste calcula el
numero 40500 (2^2 * 3^4 * 5^3) y luego el 41472 (2^9 * 3^4).
La funcion implementada en haskell, por otro lado, muestra el 40500,
luego el 40960 y luego el 41472. El 40960 es un numero valido (2^13 *
5)
En particular, hamming.cpp no muestra el 859963392.
Ahora queda averiguar si el bug esta en hamming.cpp o en g++ :D
Estoy pensando que podemos hacer trampa :D y enviarle al juez:
#include <iostream>
int main(){
std::cout << "The 1500'th ugly number is 859963392.">>
return 0;
}
Saludos,
Maxi
Daniel Gutson
OK, ya sé dónde está el bug. Esta noche lo arreglo.
:-((((
pd: estoy proponiendo a la UNRC como tesis de grado, un generador de
haskell a TMP.
2008/1/23 Maximiliano Combina <maxic...@gmail.com>:
Daniel Gutson
El tema es q algo que contiene 2^13, aparece poblando la lista en la
iteración 14 (creo :) , hace un rato q lo está calculando).
Ahora, no sé entonces cómo es q haskell lo hace derechito. Maxi,
explicá ahora! :)
Dato: C++ tiene memoization x standard hasta donde yo sé.
Daniel.
2008/1/23 Maximiliano Combina <maxic...@gmail.com>:
Daniel Gutson
de los números.
Hacer un programita de TMP que dado un número, muestre la
factorización en primos.
Ej: le paso 28, me tiene q mostrar 2^2 * 7^1.
Si les interesa, tomemos ésto como un workshop que dure toda una
semana, vayan tirando ideas o soluciones y los voy guiando. Dentro del
tiempo que tenga, puedo ir respondiendo preguntas y ayudando dando
pistas y demás, así cada uno llega al resultado por sí mismo.
Para empezar, pueden hacer uno más chico (q van a necesitar) para que
diga si un número es primo o no. Vale mirar mi ejemplo de hamming.
Consejo: pensar primero el problema recursivo. Vale hacerlo en
runtime.
Alguien le interesa? No conozco mucha gente q sepa TMP, por lo q esto
puede ser una oportunidad para q haya más gente local.
Daniel.
Fernando Cacciola
> Alguien le interesa? No conozco mucha gente q sepa TMP, por lo q esto
> puede ser una oportunidad para q haya más gente local.
>
Muy buena tu propuesta en mi opinion, con el programita que posteate creo que
están ejemplificadas las herramientas básicas.
Estaría bueno tambien, pero más adelante, ver como se hacen estas cosas usando
Boost.MPL o Boost.Fusion
Saludos
Fernando
Daniel Gutson
Ahora pregunto, Maxi, cómo sabe el Haskell hasta qué número tiene q llegar?
Es decir, cómo sabe que si tiene el nro A, y después el B, en el medio
no aparece ninguno? Cómo sabe que tiene q abandonar su pereza por un
momento y evaluar 13 recursiones en el medio?
xfav explíque sr!
pd: dale, tirá tu tesis a la bosta y ponéte a hacer esta de
transformar haskell en TMP :) Vas a ser un doctor más famoso así :D
2008/1/23 Daniel Gutson <daniel...@gmail.com>:
Maximiliano Combina
On Jan 23, 3:13 pm, "Daniel Gutson" <danielgut...@gmail.com> wrote:
> Confirmado, con 14 aparece el número ese.
>
> Ahora pregunto, Maxi, cómo sabe el Haskell hasta qué número tiene q llegar?
> Es decir, cómo sabe que si tiene el nro A, y después el B, en el medio
> no aparece ninguno? Cómo sabe que tiene q abandonar su pereza por un
> momento y evaluar 13 recursiones en el medio?
> xfav explíque sr!
>
O sea, haskell no evalua algo hasta que le sea del todo necesario. Es
decir, hasta que no pueda continuar sin tener que resolver la
operacion pendiente, digamos.
De este modo, permite laburar con (por ejemplo) listas infinitas!
Ejemplo:
[1..] denota la lista [1, 2, 3, 4, ..]
Si uno le pide evaluar [1..] obviamente no termina. Pero la vagueza de
haskel permite cosas como pedirle el n-esimo elemento de una lista
infinita.
Supongamos que queremos el 3er elemento de la lista [1..]:
[1..]!!2 (retorna 3. El index comienza en 0, y el operador !! es el
analogo al [] de C/C++)
La vagancia esta en que no le hace falta computar tooooda la lista
[1..] para obtener el 3er elemento. Para evaluar el "!!" solamente le
hace falta calcular unos pocos numeros (la lista [1..] es algo asi
como 1:2:3:[4...], donde el operador ":" es "insertar por el head)
Ahora, lo mismo pasa con hamming. La funcion "hamming" retorna una
lista (infinita) de todos los numeros feos. Pero al pedirle el que
esta en la posicion 1500, ahi recien se pone a evaluar. Y, la verdad,
es muy rapido :)
A veces la vagancia puede ser muy buena :)
Maxi
PD: volviendo a TMP... no sé mucho... estuve tratando de encontrar el
bug en el programa, pero ni idea. Alguien lo encontro ya.? (Dani?). La
explicacion estaria buena :D
> pd: dale, tirá tu tesis a la bosta y ponéte a hacer esta de
> transformar haskell en TMP :) Vas a ser un doctor más famoso así :D
>
> > Ya ví el problema, y no es un bug.
> > El tema es q algo que contiene 2^13, aparece poblando la lista en la
> > iteración 14 (creo :) , hace un rato q lo está calculando).
> > Ahora, no sé entonces cómo es q haskell lo hace derechito. Maxi,
> > explicá ahora! :)
> > Dato: C++ tiene memoization x standard hasta donde yo sé.
>
> > Daniel.
>
Cholo Lennon
> Dato: C++ tiene memoization x standard hasta donde yo sé.
C++ no posee memoization. Quizás algún compilador pueda implementar esto por su
cuenta, pero el standard no especifica optimización por memoization (supongo que
hablamos de memoization para llamadas funciones). Otra cosa es que algún
algoritmo de STL use internamente algún tipo de memoization pero tampoco eso
está especificado.
Daniel Gutson
Daniel Gutson
14.4 Type equivalence [temp.type]
1
Two templateidsrefer to the same class or function if their template names are identical, they refer to the
same template, their type
templateargumentsare the same type, their nontype
templateargument
sof integral
or enumeration type have identical values, their nontype
templateargument
sof pointer or reference
type refer to the same external object or function, and their template
templateargumentsrefer to the same
template. [
Example:template<class E, int size> class buffer { /* ... */ };
buffer<char,2*512> x;
buffer<char,1024> y;
declares
x and y to be of the same type, andtemplate<class T, void(*err_fct)()> class list { /* ... */ };
list<int,&error_handler1> x1;
list<int,&error_handler2> x2;
list<int,&error_handler2> x3;
list<char,&error_handler2> x4;
declares
x2 and x3 to be of the same type. Their type differs from the types of x1 and x4. ]14.5
====================
David Elfi
Hola a todos,
Despues de haber visto todos los post y haberme sorprendido con el nivel que tienen todos uds, me decidi a aceptar el reto de Daniel.
Por supuesto que me costo tiempo y esfuerzo diria (bastante) pero es un tema que realmente no tenia mucha idea asi que aprendi como loco.
Tambien (de acuerdo al comentario que hizo Daniel sobre prolog) me hizo acordar mucho cuando estaba en la universidad. Tuve 3 materias donde usabamos prolog y terminamos aprendiendo programacion logica a la fuerza... jaja.
Daniel, aca te envio el codigo que me salio. Realmente no probe con muchas cosas, pero con lo que llegue a probar funca. El unico tip que no le hize (por que realmente ya estaba con la cabeza frita) fue el de factorizar los numeros iguales y ponerlos como representacion exponencial. Lo que hace basicamente este programita es imprimir todos los primos que componen el numero repitiendo tantas veces como lo componga, es decir:
input 1500: 2 2 3 5 5 5
input 573: 3 191
Seguramente que debe tener bugs o se puede solucionar mejor. Estaria bueno si lo pueden revisar y le dan con un caño para aprender mas.
Saludos a todos
David
Daniel Gutson
#include <iostream>
using namespace std;
template <int I, int P>
class is_prime_aux
{
public:
enum { prim = ( P % I > 0 ) && is_prime_aux< (I * I > P ? 0 : I + 2 ), P >::prim };
};
template <int P>
class is_prime_aux<0,P>
{
public:
enum { prim = true };
};
template <int P>
class is_prime_aux<3,P>
{
public:
enum { prim = true };
};
template <int N>
class is_prime
{
public:
enum { prim = ( N % 2? is_prime_aux<3,N>::prim : false ) };
};
template <>
class is_prime<2>
{
public:
enum { prim = true } ;
};
template <int N, int Y>
class is_divisible
{
public:
enum { X = ( N % Y == 0 ) ? N / Y : N,
result = ( N > X ) || is_divisible< X, ( N > X )? Y : 0 >::result,
rest = is_divisible< X, ( N > X )? Y : 0 >::rest };
static inline void f() {
if ( result ) {
cout << Y << " ";
is_divisible< X, (N > X)? Y : 0>::f();
}
}
};
template <int N>
class is_divisible<N,0>
{
public:
enum { rest = N,
result = false };
static inline void f() { }
};
template <int N, int Y>
class find_primes
{
public:
enum { rest = is_divisible< N, is_prime<Y>::prim? Y : 0 >::rest,
next = find_primes< rest, Y + 1 >::next };
static inline void print(){
is_divisible< N, is_prime<Y>::prim? Y : 0 >::f();
find_primes< rest, Y + 1 >::print(); }
};
template <int Y>
class find_primes<1,Y>
{
public:
enum { next = 1 };
static inline void print() {}
};
template <int P>
class primes
{
public:
static inline void print() { find_primes<P,2>::print(); }
};
int main()
{
primes<1500>::print();
cout << endl;
primes<573>::print();
cout << endl;
return 0;
}
David Elfi
Cholo Lennon
Ok, ahora queda más claro a lo que apuntabas :-)
El tema es que por más que cierta documentación (C++ Template
Metaprogramming, Gurtovoy/Abrahams,
http://it-reading.org/ebook/c++.template.metaprogramming/index.html?page=book%2F
0321227255%2Fapp03lev1sec3.html) le llame 'memoization' para mi no es
más que una cuestión de sentido común: la instanciación, en una misma
unidad, de entidades iguales sería como declarar la misma clase o
función 2 veces (o más) con el consiguiente error de duplicación de
símbolos y la obvia penalidad en el rendimiento del compilador. Como
contrapartida a mi opinión se púede argumentar, con razón también, que
en nuestro caso de TMP las instanciaciones intermedias son 'temporales'
por lo cual tienen un trato especial y no aplica lo que dije al
principio.
Por la misma razón de la contrapartida que doy en el párrafo anterior
no veo como una 'memoization' oficial del estandar lo que citas (el
hecho de discernir cuando 2 templates son iguales o no). Quizás acá
entremos en un terreno meramente semántico, pero es sólo mi punto de
vista. De todas maneras lo que apuntas es válido para TMP: Two
template-id s refer to the same class or function if (...) their
corresponding non-type template arguments of integral or enumeration
type have identical values and (...) por lo cual te aseguras que el
compilador sólo va a realizar una única generación de template por cada
valor entero o enumerado.
Salu2
PD: Sería posible postear en modo texto y no html? Es complicado
responderte claramente sobre cada línea/párrafo que escribiste. Gracias.
Fernando Cacciola
Esto se está poniendo tan bueno que ya me estoy entusiasmando de verdad :)
Hasta ahora hemos usado (haramos dijo el mosquito) algoritmos basados
*directamente* en pattern matching, bien funcionales, pero la TMP da para
hacer incluso cosas típicamente imperativas, así que les propongo doblar la
apuesta y implementar este otro algoritmo para contar numeros primos:
http://en.wikipedia.org/wiki/Sieve_of_Atkin
que no es en lo más mínimo adecuado para un lenguaje funcional, ya que un su
version imperativa es puro "side effects".
¿Quien se anima?
P.S: Vale hacer trampa y usar Boost.MPL.
Salu2
Fernando Cacciola
Daniel Gutson
1) No hay error de linker por la ODR. En todo caso el impacto seria de
performance.
2) lo que te dice el std., es que el 'tipo' del template instanciado
difiere por el type-parameter y no por el non-type.
Es decir, que (en el ejemplo de David) typeof(is_prime<1>) ==
typeof(is_prime<1500>).
Daniel.
On 1/24/08, Cholo Lennon <cholo...@gmail.com> wrote:
>
Fernando Cacciola
> 2) lo que te dice el std., es que el 'tipo' del template instanciado
> difiere por el type-parameter y no por el non-type.
> Es decir, que (en el ejemplo de David) typeof(is_prime<1>) ==
> typeof(is_prime<1500>).
Tambien difiere por el non-type:
"their nontype template argumentsf integral or enumeration type have
identical values"
(copiado del mismo texto que posteate)
Fernando
Daniel Gutson
template<class E, int size> class buffer { /* ... */ };
buffer<char,2*512> x;
buffer<char,1024> y;
declares x and y to be of the same type
Fernando Cacciola
> Entiendo que no, porque fijate el ejemplo:
>
> template<class E, int size> class buffer { /* ... */ };
> buffer<char,2*512> x;
> buffer<char,1024> y;
>
> declares x and y to be of the same type
>
por tanto abos non-type tienen exactamente el mimso valor
Fernando
Daniel Gutson
A raiz de aclaracion de Sole (de que 2*512 == 1024), y de JUSTAMENTE
de TMP, es cierto. diferentes numeros => diferentes tipos.
Sigo sin saber si hay o no memoization. Ahora pregunto a las fuentes,
cuando tenga rta contesto.
Daniel.
On 1/24/08, Daniel Gutson <daniel...@gmail.com> wrote:
Cholo Lennon
> Cholo, 2 cosas:
> 1) No hay error de linker por la ODR. En todo caso el impacto seria de
> performance.
Ya se que no hay error del linker. Eso se explica porque el compilador nunca
genera 2 copias del mismo template en la misma unidad de compilación por lo
mismo que apuntaste en base al punto 14.4 y no por la ODR (Y si generara las
copias, de alguna manera eso estaría solucionado porque sino no podríamos
desarrollar nada :-)
> 2) lo que te dice el std., es que el 'tipo' del template instanciado
> difiere por el type-parameter y no por el non-type.
> Es decir, que (en el ejemplo de David) typeof(is_prime<1>) ==
> typeof(is_prime<1500>).
En desacuerdo. Esto te lo respondió correctamente Fernando en el otro post.
Salu2
Daniel Gutson
> > typeof(is_prime<1500>).
>
> En desacuerdo. Esto te lo respondió correctamente Fernando en el otro post.
Si usara 15 segundos mas para pensar antes de escribir, no escribiria
algunas cosas.
Obviamente que typeof(is_prime<1>) != typeof(is_prime<1500>),
sino nunca hubiera podido hacer el programita de hamming ni escribir
los control cuts :)
Pero escribo esto mientras le presto atencion a 68 cosas, en
particular a la recuperacion de mi billetera (que la encontro el
colectivero y me lo va a traer de onda, despues de haber cancelado
todas las tarjetas).
Daniel.
Daniel Gutson
cacho nomás :) ) SI HAY MEMOIZATION. Tiene que, y debe haber.
Como dije en el primer posts del tema. Al compilador no le importa si
son types o non-types. Sí o sí los template instantiations quedan
(sean implicitos o explicitos).
Daniel.
pd: ademas, del libro "C++ Template Metaprogramming, etcetc"
C.1.1. Memoization
Even if we ignore the other factors, thinking about complexity just in
terms of template instantiations can be strange, since a particular
template specialization is only instantiated once in a translation
unit:
typedef foo<char>::type t1; // foo<char> instantiated here
...
typedef foo<char>::type t2; // foo<char> is just looked up
Unlike the way regular function calls work, when a metafunction is
called again with the same arguments, the compiler doesn't have to go
through the whole computation again. If you're familiar with the idea
of "memoization," you can think of all metafunction results as being
memoized. At the first invocation, the instantiated class is stored in
a lookup table indexed by the template's arguments. For subsequent
invocations with the same arguments, the compiler merely looks up the
template instantiation in the table.
Cholo Lennon
> Finalmente, despues de pensar un cacho (sí, cada tanto pienso, pero un
> cacho nomás :) ) SI HAY MEMOIZATION. Tiene que, y debe haber.
> Como dije en el primer posts del tema. Al compilador no le importa si
> son types o non-types. Sí o sí los template instantiations quedan
> (sean implicitos o explicitos).
>
> Daniel.
>
> pd: ademas, del libro "C++ Template Metaprogramming, etcetc"
>
> C.1.1. Memoization
> Even if we ignore the other factors, thinking about complexity just in
> terms of template instantiations can be strange, since a particular
> template specialization is only instantiated once in a translation
> unit:
>
> typedef foo<char>::type t1; // foo<char> instantiated here
> ...
> typedef foo<char>::type t2; // foo<char> is just looked up
>
>
>
> Unlike the way regular function calls work, when a metafunction is
> called again with the same arguments, the compiler doesn't have to go
> through the whole computation again. If you're familiar with the idea
> of "memoization," you can think of all metafunction results as being
> memoized. At the first invocation, the instantiated class is stored in
> a lookup table indexed by the template's arguments. For subsequent
> invocations with the same arguments, the compiler merely looks up the
> template instantiation in the table.
>
Como para cerrar el tema (por lo menos en cuanto a mi): El término memoization
está referido exactamente a la optimización de llamadas a funciones en
situaciones repetitivas. De ahí vino mi primera respuesta (y la subsiguiente).
Ahora, se puede pensar como dice Gurtovoy que lo que hace el compilador es una
especie de memoization (técnicamente estamos extrapolando el concepto) al no
instanciar nuevamente un template ya hecho por la definición 14.4 que citaste
del estándar. A título personal pienso que lo que motivó está regla es
simplificación para el linker y optimización de la compilación. Para salir de la
duda, voy a ver como implementaban esto compiladores anteriores al estándar de
1998 (tengo por ahí un VC++ 1.5 (que no recuerdo bien que soporte tenía en
cuanto a templates y un Borland C++ 2.0 que si los soportaba).
Salu2
PD: Suerte con la billetera :-)
Daniel Gutson
puntos de instanciacion, lo cual (mas alla de ODR) no puede ocurrir,
con lo cual esto debe estar si o si desde el vamos, mas alla tambien
de cualquier optimizacion.
Cualquier compilador que se jacte de resolver templates debe resolver
'memoization' tambien. Es simplemente hacerle caso al std en cuanto a
'template instantiation'.
Daniel.
On 1/24/08, Cholo Lennon <cholo...@gmail.com> wrote:
>
Fernando Cacciola
> Sigo sin saber si hay o no memoization.
Este pequeño programita podria usarse para mostrar (aunque no demostrar) que
existe la memoization en TMP.
El programita recurre desde 4 hasta 0 y en los primeros 4 pasos "ejecuta la
metafunción" tmp<N> donde N es 0 o 1.
Como pueden ver, tmp<N> se "ejecuta" 4 veces, 2 con <0> y 2 con <1>.
Si memoization, tmp<0> y tmp<1> se instaciarían 2 veces cada una.
Ahora bien, si lo compilan con un compilador decente van a ver una serie de
warnings.
Si leen con detalle esos warnings, van a ver que en algun lugar del mensaje
del warning aparece la "informacion" que se pasa a la macro
STATIC_PRINT_....
Esa sequencia de warnings es precisamente un "trace" de la ejecución del
TMP.
Adjunto "static_print.hpp"
(hace unos años una version del mismo llamada "debug_print.hpp" era parte de
Boost.MPL, pero que ahora no sé por qué no está mas)
#include "static_print.hpp"
template<int> struct tmp {} ;
template<> struct tmp<0>
{
STATIC_PRINT_MSG(TMP_0);
typedef int type ;
} ;
template<> struct tmp<1>
{
STATIC_PRINT_MSG(TMP_1);
typedef int type ;
} ;
template<int N> struct X
{
STATIC_PRINT_INT(X_N,N);
typedef typename X<N-1>::type type ;
} ;
template<> struct X<0>
{
STATIC_PRINT_MSG(X_0);
typedef int type ;
} ;
X<4>::type x ;
int main() {}
Daniel Gutson
#include <iostream>
using namespace std;
template <int X>
int f()
{
static int i;
return i++;
}
void prueba_1()
{
cout << f<1>();
}
void prueba_2()
{
cout << f<1>();
}
int main()
{
prueba_1();
prueba_2();
return 0;
}
muestra 01
Si no hubiera memoization, mostraria 00.
Daniel.
On 1/24/08, Fernando Cacciola <fernando...@gmail.com> wrote:
> // (C) 2002, Fernando Luis Cacciola Carballal.
> //
> // This material is provided "as is", with absolutely no warranty expressed
> // or implied. Any use is at your own risk.
> //
> // Permission to use or copy this software for any purpose is hereby granted
> // without fee, provided the above notices are retained on all copies.
> // Permission to modify the code and to distribute modified code is granted,
> // provided the above notices are retained, and a notice that the code was
> // modified is included with the above copyright notice.
> //
> //
> #ifndef BOOST_STATIC_PRINT_27NOV2001_HPP
> #define BOOST_STATIC_PRINT_27NOV2001_HPP
>
> #include "boost/preprocessor/cat.hpp"
> #include "boost/preprocessor/stringize.hpp"
>
> //
> // The following macros can be used in template metaprogramming to "print" typenames,
> // integer and boolean values.
> // Unlike STATIC_ASSERT(), the output is via a warning, so the code compiles without error.
> //
>
> // Example:
> //
> // template<class T>
> // struct Foo
> // {
> // STATIC_PRINT_TYPE( FOO_TEMPLATE_PARAMETER, T)
> // } ;
> //
> // template class Foo<string> ;
> //
> // When the template is instatiated, a warning will be issued inside a function named:
> //
> // STATIC_PRINT_TYPE_NAMED_FOO_TEMPLATE_PARAMETER<string>()
> //
> // if you locate the message, you can see which is the the template function parameter
> // (in this case 'string')
> //
>
> #define STATIC_PRINT_TYPE(id,type) \
> template<class> \
> struct BOOST_PP_CAT(STATIC_PRINT_TYPE_NAMED_,id) \
> { \
> static const bool value = 2.0f ; \
> } ; \
> static const bool BOOST_PP_CAT(static_printing_type_named_,id) = BOOST_PP_CAT(STATIC_PRINT_TYPE_NAMED_,id) <type>::value
>
>
> #define STATIC_PRINT_INT(id,val) \
> template<int> \
> struct BOOST_PP_CAT(STATIC_PRINT_INT_NAMED_,id) \
> { \
> static const bool value = 2.0f ; \
> } ; \
> static const bool BOOST_PP_CAT(static_printing_int_named_,id) = BOOST_PP_CAT(STATIC_PRINT_INT_NAMED_,id) <val>::value
>
> #define STATIC_PRINT_BOOL(id,val) \
> template<bool> \
> struct BOOST_PP_CAT(STATIC_PRINT_BOOL_NAMED_,id) \
> { \
> static const bool value = 2.0f ; \
> } ; \
> static const bool BOOST_PP_CAT(static_printing_bool_named_,id) = BOOST_PP_CAT(STATIC_PRINT_BOOL_NAMED_,id) <val>::value
>
> #define STATIC_PRINT_MSG(msg) \
> template<class> \
> struct BOOST_PP_CAT(STATIC_PRINT_MSG_NAMED_,msg) \
> { \
> static const bool value = 2.0f ; \
> } ; \
> static const bool BOOST_PP_CAT(static_printing_msg_,msg) = BOOST_PP_CAT(STATIC_PRINT_MSG_NAMED_,msg) <char>::value
>
>
> #endif
>
>
Soledad Alborno
mucho estas en el tema :)...
Me encanto la charla... ya estoy leyendo el libro de Abrahams and Gurtovoy.
Quiero saber como puedo aplicarlo a mis proyectos. Pero es totalmente
otro paradigma para alguien que ama OO, imagino que es cuestion de
modificar el colador.
Solo queria aportar una cosita por que no me gusto algo que lei...
alguien dijo "las instanciaciones intermedias temporales" y tiene que
ver con esto de memoization, no existen las instanciaciones
temporales. Cada vez que se instancia un template con un parámetro no
utilizado nunca se crea un tipo nuevo, y no podría crearse el mismo
tipo dos veces x ODR como dice Daniel.
Esto es super potente, porque por ejemplo para calcular el número de
permutaciones se calcularia el factorial de algún limite superior en
tiempo de compilación y luego se podria acceder al factorial de
cualquier número sin tener que calcularlo de nuevo, simplemente porque
las implementaciones no son temporales y se podrian acceder siempre.
Saluditos,
Sole
Cholo Lennon
> Guau! cuanto saben de TMP, Fernando, sos un genio, se ve que hace
> mucho estas en el tema :)...
> Me encanto la charla... ya estoy leyendo el libro de Abrahams and
> Gurtovoy.
Buen libro, pero le falta más ideas sobre como aplicar la TMP, es un poco
'áspero' :-)
>
> Quiero saber como puedo aplicarlo a mis proyectos. Pero es totalmente
> otro paradigma para alguien que ama OO, imagino que es cuestion de
> modificar el colador.
Te recomiendo leer el libro de Andrei Alexandrescu, "Modern C++ Design". Acá
puedes ver mucho mejor la aplicación de TMP con ejemplos más concretos sobre
como unir la programación genérica con OO.
> Solo queria aportar una cosita por que no me gusto algo que lei...
> alguien dijo "las instanciaciones intermedias temporales" y tiene que
> ver con esto de memoization, no existen las instanciaciones
> temporales.
Soledad, tomando como ejemplo el factorial: Si no existen las instanciaciones
temporales, como llamarías por ejemplo al factorial de N-1 que es necesario para
calcular el factorial de N? Nos interesa el factorial de N, todo lo demás es
parte del algoritmo, lo cual para mi punto de vista es temporal (a menos claro
que ese factorial de N-1 se usado en otro lugar para otro cálculo).
> Cada vez que se instancia un template con un parámetro no
> utilizado nunca se crea un tipo nuevo, y no podría crearse el mismo
> tipo dos veces x ODR como dice Daniel.
Si te apegas a la regla 14.4 citada por Daniel, la misma te asegura que no se
viole el principio de ODR. O sea, no es por ODR que no se generan 2 templates
iguales sino por la 14.4.
Salu2
Cholo Lennon
> Una manera (mas cortita), tal vez de demostrarlo:
>
>
> #include <iostream>
> using namespace std;
>
> template <int X>
> int f()
> {
> static int i;
> return i++;
> }
>
>
> void prueba_1()
> {
> cout << f<1>();
> }
>
> void prueba_2()
> {
> cout << f<1>();
> }
>
> int main()
> {
> prueba_1();
> prueba_2();
> return 0;
> }
>
>
> muestra 01
> Si no hubiera memoization, mostraria 00.
>
> Daniel.
Como dato anecdótico: Aprovechando que se tomaron el trabajo de realizar los
metaprogramas he probado el tuyo Daniel con ligeras modificaciones (el de
Fernando requería demasiadas) en un compilador del año 1992! El mismo funciona
correctamente. El compilador es el Borland C++ 3.1 para DOS/Win16. Este
compilador tiene un soporte limitado para templates entre otras cosa porque en
esa época la especificación estaba aceptada (por el comite de Ansi C++) pero no
con las características de hoy (y no había ningún estándar ISO como hoy). De
todas maneras se comporta según lo esperado. El dato loco es que el compilador
este de Borland soporta 3 formas de generar templates, una de ellas llamada
global, va agregando todos los templates generados a través de todas las
unidades de compilación a un repositorio común. Por lo tanto (y esto está
aclarado en la documentación) si 2 unidades producen el mismo template, el
linker generará en el paso siguiente errores por símboles duplicados! La verdad
increíble... todavía no le encuentro mucho sentido a esa opción.
Salu2
Fernando Cacciola
>> Solo queria aportar una cosita por que no me gusto algo que lei...
>> alguien dijo "las instanciaciones intermedias temporales" y tiene que
>> ver con esto de memoization, no existen las instanciaciones
>> temporales.
>
> Soledad, tomando como ejemplo el factorial: Si no existen las
> instanciaciones
> temporales, como llamarías por ejemplo al factorial de N-1 que es
> necesario
> para calcular el factorial de N?
<N-1> es una instancia del tmp, pero no veo que sea temporal en el sentido
usual de este término.
Sería temporal si luego de haber instanciado el template "principal",
digamos <N>, se descarta la instancia previa de <N-1>.
Pero no hace eso.
Volvamos al programita de prueba que posteé la vez anterior, y agregemos una
segunda "llamada al algoritmo":
X<4>::type x ;
X<4>::type y ;
Si las instanciaciones fueran temporales, al evaluar la definición de "y"
deberían instanciarse todos los templates nuevamente, y el trace muestra
claramente que no.
La prueba mas simple posteada por Daniel muestra exactamente lo mismo ya que
los templates se instancian en dos expresiones distintas, aunque para
funciones template en lugar de clases (por ello ambas pruebas se
complementan)
> Nos interesa el factorial de N, todo lo
> demás es parte del algoritmo, lo cual para mi punto de vista es temporal
> (a
> menos claro que ese factorial de N-1 se usado en otro lugar para otro
> cálculo).
>
Justamente, no es temporal por cuanto el compilador no lo descarta por si lo
vas a usar más adelante en otro cálculo.
Las instancias de los templates son globales con internal linkage y en ese
sentido "ocupan memoria" de un modo permanente dentro del mismo translation
unit (algo a tener en cuenta)
Salu2
Fernando
Fernando Cacciola
> Por lo tanto (y esto está aclarado en la documentación) si 2 unidades
> producen el mismo
> template, el linker generará en el paso siguiente errores por símboles
> duplicados! La verdad increíble... todavía no le encuentro mucho sentido a
> esa opción.
>
Por 1996 mas o menos yo usaba esa opción para evitar que tardara horas y
horas compilando el programa ha causa de los templates.
Recuerdo que tenia un .cpp con instanciaciones explicitas de todos los
templates que usaba, a mano.
Y creo recordar tambien que tenía que agregar "extern" o algo así en las
definiciones de los templates para evitar el error de símbolos duplicados.
Si me habra salvado la vida esta opción!
Fernando
Cholo Lennon
Ok, queda claro y les doy toda la razón :-) Sólo les explico el porqué de mi
punto de vista (ahora, 'anterior'): Tomando de nuevo al factorial como ejemplo:
Al final de todo queda sólo el resultado de N!. Los valores intermedios ((n-1)!,
(n-2)!, etc) ya no están a menos, como aclaré, que hayan sido requeridos en otro
cálculo. De ahí el punto de vista de llamar a las instanciaciones intermedias
como temporales. Quizás 'intermedio' sea un mejor término.
> Las instancias de los templates son globales con internal linkage y
Eso siempre estuvo claro.
> en ese sentido "ocupan memoria" de un modo permanente dentro del
> mismo translation unit (algo a tener en cuenta)
Aunque ocupan espacio hasta tanto el linker (inteligentes como los de hoy)
remueva el código generado no referenciado.
Cholo Lennon
Ok, ahora le veo el sentido a esa opción! :-)
Había otra opción 'smart' que generaba en todas las unidades y luego agrupaba el
código común. O sea no había 'code bloat', pero como bien cuentas el tiempo de
compilación podía llegar a ser muuuuy largo. Ahora me queda todo más claro.
Daniel Gutson
> compilación podía llegar a ser muuuuy largo. Ahora me queda todo más claro.
>
> Salu2
>
>
> --
> Cholo Lennon
Hablando de 'code bloat', y ya que David resolvió lo de los numeros
primos (bueno, 'casi' :D David, sabes q soy "exigente" :D ),
a alguien le interesa que muestre como evitar code bloat usando type
mappers, o todos lo saben? Si a alguien le interesa, muestro un par de
cositas y un ejercicio no del todo trivial.
Daniel.
pd: Cholo, ya que mencionás al libro de Alexandrescu, hay un paper que
revisó él que te puede resultar interesante:
http://danielgutson.googlepages.com/precomp_cpp.pdf (aunque no esté en
los agradecimientos) y la presentación acá
http://danielgutson.googlepages.com/Cacic2005-esp.ppt
Tiene que ver con esto de TMP pero de otra manera.
Cholo Lennon
>> código común. O sea no había 'code bloat', pero como bien cuentas el
>> tiempo de compilación podía llegar a ser muuuuy largo. Ahora me
>> queda todo más claro.
>>
>> Salu2
>>
>>
>> --
>> Cholo Lennon
>
> Hablando de 'code bloat', y ya que David resolvió lo de los numeros
> primos (bueno, 'casi' :D David, sabes q soy "exigente" :D ),
> a alguien le interesa que muestre como evitar code bloat usando type
> mappers, o todos lo saben? Si a alguien le interesa, muestro un par de
> cositas y un ejercicio no del todo trivial.
Si se sabe o no, quizás no tenga importancia. El foro creo que es amplio
y variado como para que se aproveche el concepto, incluso si el mismo
se sabe. Este hilo de discusión y también los anteriores así lo demuestran.
Eso sí dale vida propia y genera una nueva entrada en el foro :-)
>
> Daniel.
>
> pd: Cholo, ya que mencionás al libro de Alexandrescu, hay un paper que
> revisó él que te puede resultar interesante:
> http://danielgutson.googlepages.com/precomp_cpp.pdf (aunque no esté en
> los agradecimientos) y la presentación acá
> http://danielgutson.googlepages.com/Cacic2005-esp.ppt
> Tiene que ver con esto de TMP pero de otra manera.
Muchas gracias por el paper y la presentación. La verdad que muy
interesante el concepto y la herramienta, sobre todo como se aclara, para
aplicarse en sistemas embebidos. He trabajado en sistemas de ese tipo
y siempre hay que terminar haciendo ciertos malavarismos para que el
código sea los más eficiente posible, pero sin perder la claridad (muchas
veces con pocos resultados).
La herramienta es experimental o la tienen en producción?
Daniel Gutson
lugar público, pero lo más interesante es empujar para ver si la UNRC
(univ. nac. de río cuarto) lo quiere meter en g++ como tesis o
similar.
Por otro lado ya tengo la parte que hace lo equivalente con tipos de
datos y flujo, además de datos (instancias) como está en el paper.
En un rato o mañana pongo lo de type mappings.
Daniel.
2008/1/27 Cholo Lennon <cholo...@hotmail.com>:
Daniel Gutson
Ya sé que no es C++, pero lo agrego porque quizas se pueda sacar
alguna idea (si no entendi mal, lo que hizo Daniel es muy parecido):
Sacado de la wikipedia (http://en.wikipedia.org/wiki/
Haskell_(programming_language) ), la funcion de Hamming en Haskell se
escribe en muy pocas lineas:
hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map
(5*) hamming
where merge (x:xs) (y:ys)
| x < y = x : xs `merge` (y:ys)
| x > y = y : (x:xs) `merge` ys
| otherwise = x : xs `merge` ys
Una vez que tenemos la funcion, podemos aprovechar la laziness de
Haskell para calcular casi cualquier numero en la lista anterior. En
particular, el numero 1500 :
Main> hamming!!1499
859963392
Otra cosa que encontre: Daniel, el programa que enviaste calcula el
numero 40500 (2^2 * 3^4 * 5^3) y luego el 41472 (2^9 * 3^4).
La funcion implementada en haskell, por otro lado, muestra el 40500,
luego el 40960 y luego el 41472. El 40960 es un numero valido (2^13 *
5)
En particular, hamming.cpp no muestra el 859963392.
Ahora queda averiguar si el bug esta en hamming.cpp o en g++ :D
Estoy pensando que podemos hacer trampa :D y enviarle al juez:
#include <iostream>
int main(){
std::cout << "The 1500'th ugly number is 859963392.">>
return 0;
}
Saludos,
Maxi
On 23 ene, 11:29, Maximiliano Combina <maxicomb...@gmail.com> wrote:
> Vale aclarar que a mi también me interesa el tema!
> btw, usando g++ tuve que compilar con -ftemplate-depth-579 (sí, es el
> menor numero tal que anduvo). Y el manpage también aclara que uno no
> debería sobrepasar 17 :)
>
> On 23 ene, 05:54, "Cholo Lennon" <chololen...@hotmail.com> wrote:
>
> > "Daniel Gutson" <danielgut...@gmail.com>
> > escribió en el mensajenews:23ab4d1c0801221410x664f3f60ja66cb4150...@mail.gmail.com...
>
> > > Fernando,
> > > lo que puedo hacer, dada la mezcla del grado de interes que genera
> > > (poco) y el tiempo que tengo, es esto:
>
> > Valga la aclaración: En mi caso, no es que no me interese el tema (TMP) ni
> > mucho menos, realmente me parece algo muy interesante. De hecho he leido
> > todo lo que anda dando vueltas, desde el paper fundacional hasta libros como
> > los de Alexandrescu, Vandevoorde/Josuttis, Gurtovoy/Abrahams (Cacciola en
> > los agradecimientos! :-) etc, etc.
> > El problema es el tiempo del cual dispongo, el mismo me limita solamente a
> > participar en cosas puntuales :-(
>
> > Salu2
>
> > --
> > Cholo Lennon
> > Bs.As.
> > ARG
--~--~---------~--~----~------------~-------~--~----~
¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
En caso de duda visita "http://groups.google.com/group/cppba"
-~----------~----~----~----~------~----~------~--~---
One guess, that’s who?
Who’d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?
Rafael Ontivero
--
--
¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
En caso de duda visita "http://groups.google.com/group/cppba"
---
Has recibido este mensaje porque estás suscrito al grupo "CyC++ Buenos Aires" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a cppba+un...@googlegroups.com.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-38ZafeSHx5Jv546-M_mB1Lt%3DY7H%3D452d84%3DCSPdvB0Zw%40mail.gmail.com.
Daniel Gutson
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/43B40780-2D42-4FB5-BD75-7FB8AB7F41BB%40gmail.com.
Enrique Nieloud
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-1LWFfEU_h_46fyRao-%2Bh5hX%2BLAKBC_qrscTmCC_OpDQw%40mail.gmail.com.
Enrique Nieloud
Hola, no sé de qué va el tema, madre mía, del 2008, tela.Pero yo no soy manager, he rechazado puestos porque yo quiero picar código. Prefiero ser regular tirando líneas de código que peor de manager.(Eso sí, en este mismo momento gano como un manager o más, eso también tengo que decirlo).