¿Cuál es el tipo de esta función factorial autoaplicable?
Escribí una función factorial anónima en C++ y compilé mi código con g++4.9.2. Funciona bien. Sin embargo, no conozco el tipo de mi función.
#include<iostream>
#include<functional>
using std::function;
int main()
{
//tested at g++ 4.9.2
//g++ -std=c++1y -o anony anony.cpp
auto fac = [](auto self,auto n)->auto{
if(n < 1)
return 1;
else
return n * self(self,n-1);
};
std::cout<<fac(fac,3)<<std::endl;//6
return 0;
}
Entonces, me pregunto: ¿cuáles son los tipos de fac y self?
Si traduzco el código C++ a Haskell, no se compilará porque
involucra tipos infinitos:
fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)
Y tengo que definir algún tipo de trabajo recursivo alrededor de él:
data Y a = Y ((Y a)->a->a)
fac2 self 0 = 1
fac2 self n = n * ((applY self self) (n-1))
where applY (Y f1) f2 = f1 f2
fact2 = fac2 $ Y fac2
Entonces, ¿por qué podría g++ obtener exactamente el tipo correcto de la función fac, y qué type ¿cree g++ que la función fac es?
3 answers
La expresión que sigue a auto fac = es una expresión lambda, y el compilador generará automáticamente un objeto closure a partir de ella. El tipo de ese objeto es único y conocido solo por el compilador.
De N4296, §5.1.2/3 [expr.prim.lambda]
El tipo de la expresión lambda (que también es el tipo del objeto closure) es un tipo de clase único, sin nombre y sin unión, llamado closure type , cuyas propiedades se describen debajo. Este tipo de clase no es un agregado (8.5.1) ni un tipo literal (3.9). El tipo de cierre se declara en el ámbito de bloque más pequeño, ámbito de clase o ámbito de espacio de nombres que contiene la expresión lambda correspondiente.
Tenga en cuenta que debido a esto, incluso dos expresiones lambda idénticas tendrán tipos distintos. Por ejemplo,
auto l1 = []{};
auto l2 = []{}; // l1 and l2 are of different types
Su expresión lambda es una lambda genérica de C++14, y será traducida por el compilador a una clase que se asemeje siguiente:
struct __unique_name
{
template<typename Arg1, typename Arg2>
auto operator()(Arg1 self, Arg2 n) const
{
// body of your lambda
}
};
No puedo comentar la parte de Haskell, pero la razón por la que la expresión recursiva funciona en C++ es porque simplemente estás pasando una copia de la instancia del objeto closure (fac) en cada llamada. El operator() siendo una plantilla es capaz de deducir el tipo de la lambda a pesar de que no es uno que se puede nombrar de otra manera.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-01-07 08:07:10
El C++ fac no es realmente una función, sino una estructura que tiene una función miembro.
struct aaaa // Not its real name.
{
template<typename a, typename b>
auto operator()(a self, b n) const
{
}
};
El operador de llamada sobrecargado oculta algunos de los trucos que realiza C++ para implementar "funciones lambda"
Cuando "llamas" fac, lo que sucede es
fac.operator() (fac, 3);
Así que el argumento de la función no es la función en sí, sino un objeto que la tiene como miembro.
Un efecto de esto es que el tipo de la función (es decir, el tipo de operator()) no ocurre en el tipo de la propia función operator().
(El tipo de self es la estructura que define la función.)
La parte de la plantilla no es necesaria para que esto funcione; esta es una versión no genérica de la fac "función":
struct F
{
int operator()(const F& self, int n) const
{
// ...
}
};
F fac;
fac(fac, 3);
Si mantenemos la plantilla y renombramos operator() a applY:
// The Y type
template<typename a>
struct Y
{
// The wrapped function has type (Y<a>, a) -> a
a applY(const Y<a>& self, a n) const
{
if(n < 1)
return 1;
else
return n * self.applY(self, n-1);
}
};
template<typename a>
a fac(a n)
{
Y<a> y;
return y.applY(y, n);
}
Vemos que su programa Haskell de trabajo y su programa C++ son muy similares - las diferencias son principalmente la puntuación.
En contraste, en Haskell
fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)
self es una función, y el tipo de fac2 tendría que ser
X -> Int -> Int
Para algunos X.
Dado que self es una función, y self self $ n-1 es un Int, el tipo de self es también X -> Int -> Int.
Pero ¿qué podría ser X?
Debe ser el mismo que el tipo de self en sí, es decir, X -> Int -> Int.
Pero eso significa que el tipo de self es (sustituyendo a X):
(X -> Int -> Int) -> Int -> Int
Así que el tipo X también debe ser
(X -> Int -> Int) -> Int -> Int
Así que el tipo de self debe be
((X -> Int -> Int) -> Int -> Int) -> Int -> Int
Y así sucesivamente, ad infinitum.
Es decir, en Haskell el tipo sería infinito.
Su solución para Haskell esencialmente introduce explícitamente la indirección necesaria que C++ genera a través de su estructura con una función miembro.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-02-04 12:13:52
Como otros señalaron, la lambda actúa como una estructura que involucra una plantilla. La pregunta entonces es: ¿por qué Haskell no puede escribir la auto-aplicación, mientras que C++ puede?
La respuesta radica en la diferencia entre las plantillas de C++ y las funciones polimórficas de Haskell. Compare estos:
-- valid Haskell
foo :: forall a b. a -> b -> a
foo x y = x
// valid C++
template <typename a, typename b>
a foo(a x, b y) { return x; }
Si bien pueden parecer casi equivalentes, en realidad no lo son.
Cuando Haskell type comprueba la declaración anterior, comprueba que la definición es segura para cualquier tipo a,b. Es decir, si sustituimos a,b con dos tipos cualesquiera, la función debe estar bien definida.
C++ sigue otro enfoque. En la definición de plantilla, no se comprueba que cualquier sustitución de a,b sea correcta. Esta comprobación es diferida hasta el punto de uso de la plantilla, es decir, en el momento de la instanciación. Para enfatizar el punto, agreguemos un +1 en nuestro código:
-- INVALID Haskell
foo :: forall a b. a -> b -> a
foo x y = x+1
// valid C++
template <typename a, typename b>
a foo(a x, b y) { return x+1; }
La definición de Haskell no escribirá check: no hay garantía de que pueda realizar x+1 cuando x es de un tipo arbitrario. El código C++ está bien, en su lugar. El hecho de que algunas sustituciones de a conducen a un código incorrecto es irrelevante en este momento.
Posponer esta comprobación hace que se permitan algunos "valores infinitamente tipados", aproximadamente. Los lenguajes dinámicos como Python o Scheme posponen aún más estos errores de tipo hasta el tiempo de ejecución, y por supuesto manejarán la autoaplicación muy bien.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-01-07 10:48:22