Saludos
--
Cholo Lennon
Bs.As.
ARG
"Soledad Alborno" <soledad...@gmail.com>
escribió en el mensaje
news:3b03b8d00801110841m7fe...@mail.gmail.com...
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>:
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>:
Salu2
--
Cholo Lennon
Bs.As.
ARG
"Daniel Gutson" <daniel...@gmail.com>
escribió en el mensaje
news:23ab4d1c0801201907r70a...@mail.gmail.com...
Daniel.
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
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.
> 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
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.
2008/1/23 Maximiliano Combina <maxic...@gmail.com>:
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.
> 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
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>:
> 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.
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
====================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
#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;
}
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.
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
On 1/24/08, Cholo Lennon <cholo...@gmail.com> wrote:
>
> 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
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
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, 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
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.
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 :-)
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:
>
> 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() {}
#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
>
>
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
> 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
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
>> 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
> 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
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.
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.
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.
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?
En un rato o mañana pongo lo de type mappings.
Daniel.
2008/1/27 Cholo Lennon <cholo...@hotmail.com>:
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"
-~----------~----~----~----~------~----~------~--~---
--
--
¿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.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/43B40780-2D42-4FB5-BD75-7FB8AB7F41BB%40gmail.com.
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.
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).