c++ - usando - operaciones con factoriales

¿Cuál es el tipo de esta función factorial autoaplicable?

Question

Escribí una función factorial anónima en C ++ y compilé mi código con g ++ 4.9.2. Funciona bien. Sin embargo, no sé 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 simplemente traduzco el código C ++ a Haskell, no se compilará porque incluye tipos infinitos:

fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)

y tengo que definir algún tipo de trabajo recursivo a su alrededor:

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é g ++ puede obtener exactamente el tipo correcto de la función fac , y qué tipo piensa g ++ que es la función fac ?

Answer 1

Como otros lo señalaron, la lambda actúa como una estructura que involucra una plantilla. La pregunta entonces es: ¿por qué Haskell no puede escribir la autoaplicación, mientras que C ++ sí puede?

La respuesta está en la diferencia entre las plantillas C ++ y las funciones polimórficas de Haskell. Compara 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 el tipo Haskell comprueba la declaración anterior, verifica que la definición sea segura para cualquier tipo a,b . Es decir, si sustituimos a,b con dos tipos, la función debe estar bien definida.

C ++ sigue otro enfoque. En la definición de la plantilla, no se verifica que cualquier sustitución para a,b sea ​​correcta. Esta verificación se difiere 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á verificación: no hay garantía de que pueda realizar x+1 cuando x sea ​​de un tipo arbitrario. El código C ++ está bien, en su lugar. El hecho de que algunas sustituciones de a derivación a un código incorrecto sea irrelevante en este momento.

Aplazar esta comprobación hace que se permitan unos "valores de tipo infinito", aproximadamente. Los lenguajes dinámicos, como Python o Scheme, difieren aún más estos errores de tipo hasta el tiempo de ejecución y, por supuesto, manejarán la autoaplicación sin problemas.

Answer 2

El fac C ++ 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 llamadas sobrecargado oculta algunos de los trucos que realiza C ++ para implementar "funciones lambda"

Cuando "llamas" fac , lo que pasa es

fac.operator() (fac, 3);

por lo tanto, 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 función del operator() sí.
(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 "función" fac :

struct F
{
int operator()(const F& self, int n) const
{
// ...
}
};
F fac;
fac(fac, 3);

Si mantenemos la plantilla y cambiamos el nombre del operator() para 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 de trabajo Haskell y su programa de C ++ son muy similares, las diferencias son principalmente la puntuación.

Por el contrario, en Haskell

fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)

self es una función, y el tipo fac2 debería ser

X -> Int -> Int

para algunos X .
Como self es una función, y self self $ n-1 es un Int, el tipo self es también X -> Int -> Int .

Pero, ¿qué podría ser X ?
Debe ser el mismo que el tipo de self mismo, es decir, X -> Int -> Int .
Pero eso significa que el tipo de self es (sustituyendo a X ):

(X -> Int -> Int) -> Int -> Int

por lo que el tipo X también debe ser

(X -> Int -> Int) -> Int -> Int

así que el tipo del self debe ser

((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.

Answer 3

La expresión que sigue a auto fac = es una expresión lambda, y el compilador generará automáticamente un objeto de cierre 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 de cierre) es un tipo de clase sin unión y sin nombre, denominado tipo de cierre , cuyas propiedades se describen a continuación. 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, el ámbito de clase o el á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 el compilador la traducirá a una clase que se parece a lo siguiente:

struct __unique_name
{
template<typename Arg1, typename Arg2>
auto operator()(Arg1 self, Arg2 n) const
{
// body of your lambda
}
};

No puedo comentar sobre la parte de Haskell, pero la razón por la que la expresión recursiva funciona en C ++ es porque simplemente está pasando una copia de la instancia de objeto de cierre ( fac ) en cada llamada. El operator() es una plantilla es capaz de deducir el tipo de la lambda aunque no sea uno que pueda nombrar de otra manera.