¿Qué puede ofrecer C++ en cuanto a programación funcional?

functional-programming

Question

¿Son las siguientes cosas consideradas intrínsecas a la PF posibles en C ++?

• funciones de orden superior
• lambdas (cierres / funciones anonimas)
• funciones de firmas como tipos
• tipo polimorfismo (genéricos)
• estructuras de datos inmutables
• tipos de datos algebraicos (variantes)
• estructuras de datos adhock (tuplas)
• aplicaciones de función parcial

ACTUALIZADO:

• inferencia de tipo
• recursión de la cola
• la coincidencia de patrones
• recolección de basura

Answer 1

(Solo para agregar un poco a la respuesta de Alice, que es excelente.)

Estoy lejos de ser un experto en programación funcional, pero el lenguaje de metaprogramación de plantillas en tiempo de compilación en C ++ a menudo se considera "funcional", aunque con una sintaxis muy arcana. En este lenguaje, las "funciones" se convierten en instanciaciones de plantilla de clase (a menudo recursivas). La especialización parcial sirve para el propósito de la coincidencia de patrones, para terminar la recursión y así sucesivamente. Así que un factorial en tiempo de compilación podría verse algo así:

template <int I>
struct fact
{
    static const int value = I * fact<I-1>::value;
};

template <>
struct fact<1>
{
    static const int value = 1;
};

Por supuesto, esto es bastante horrible, pero muchas personas (especialmente los desarrolladores de Boost) han hecho cosas increíblemente inteligentes y complejas con solo estas herramientas.

Posiblemente también vale la pena mencionar la palabra clave C ++ 11 constexpr , que denota funciones que pueden evaluarse en tiempo de compilación. En C ++ 11, constexpr funciones constexpr están restringidas a (básicamente) solo una simple declaración de return ; pero el operador ternario y la recursión están permitidos, por lo que el factorial de tiempo de compilación anterior se puede reformular de forma mucho más sucinta (y comprensible) como:

constexpr int fact(int i)
{
    return i == 1 ? 1 : i * fact(i-1);
}

con el beneficio adicional de que fact() ahora también se puede llamar en tiempo de ejecución. Si esto constituye una programación en un estilo funcional se deja para que el lector decida :-)

(C ++ 14 parece probable que elimine muchas de las restricciones de constexpr funciones constexpr , lo que permite constexpr un subconjunto muy grande de C ++ en tiempo de compilación)

Answer 2

De tu lista, C ++ puede hacer:

• funciones de firmas como tipos
• Tipo de polimorfismo (pero no de primera clase como en muchos lenguajes funcionales)
• Estructuras de datos inmutables (pero requieren más trabajo)

Solo puede hacer formas muy limitadas de:

• Funciones / cierres de orden superior (básicamente, sin GC, la mayoría de los modismos funcionales de orden superior más interesantes son inutilizables)
• estructuras de datos ad hoc (si se refiere a tipos estructurales ligeros)

Básicamente puedes olvidarte de:

• tipos de datos algebraicos y coincidencia de patrones
• Aplicaciones de función parcial (requiere cierres implícitos en general).
• inferencia de tipo (a pesar de lo que la gente llama "inferencia de tipo" en C ++ land está muy lejos de lo que se obtiene con Hindley / Milner a la ML o Haskell)
• llamadas de cola (algunos compiladores pueden optimizar algunos casos limitados de auto-recursión de cola, pero no hay garantía, y el lenguaje es activamente hostil al caso general (punteros a la pila, destructores, y todo eso))
• recolección de basura (puede usar el recolector conservador de Boehm, pero no es un sustituto real y es poco probable que coexista pacíficamente con el código de terceros)

En general, tratar de hacer algo funcional que vaya más allá de las trivialidades será un gran dolor en C ++ o simplemente inutilizable. E incluso las cosas que son bastante fáciles a menudo requieren tanta repetición y una notación pesada que no son muy atractivas. (A algunos aficionados a C ++ les gusta afirmar lo contrario, pero, francamente, la mayoría de ellos parece tener una experiencia bastante limitada con la programación funcional real).

Answer 3

Permítanme comenzar señalando que la mayoría de estos no son "intrínsecos" o, mejor dicho, "requeridos"; muchas de estas están ausentes de los lenguajes funcionales notables, y en teoría, muchas de estas características pueden usarse para implementar las otras (como las funciones de orden superior en el cálculo lambda sin tipo).

Sin embargo, vamos a ir a través de estos:

Cierres

Los cierres no son necesarios, y son azúcar sintáctica: mediante el proceso de Lambda Lifting , puede convertir cualquier cierre en un objeto de función (o incluso solo una función gratuita).

Functors nombrados (C ++ 03)

Solo para mostrar que esto no es un problema para comenzar, aquí hay una manera simple de hacer esto sin lambdas en C ++ 03:

No es un problema:

struct named_functor 
{
    void operator()( int val ) { std::cout << val; }
};
vector<int> v;
for_each( v.begin(), v.end(), named_functor());

Funciones anónimas (C ++ 11)

Sin embargo, las funciones anónimas en C ++ 11 (también llamadas funciones lambda, como se derivan del historial de LISP), que se implementan como objetos de función con nombre no alias, pueden proporcionar la misma facilidad de uso (y de hecho se denominan cierres). así que sí, C ++ 11 tiene cierres):

No hay problema:

vector<int> v;
for_each( v.begin(), v.end(), [] (int val)
{
    std::cout << val;
} );

Funciones anónimas polimórficas (C ++ 14)

Aún menos de un problema, ya no necesitamos preocuparnos por los tipos de parámetros en C ++ 14:

Aún menos problema:

auto lammy = [] (auto val) { std::cout << val; };

vector<int> v;
for_each( v.begin(), v.end(), lammy);

forward_list<double> w;
for_each( w.begin(), w.end(), lammy);

Debo tener en cuenta que esto es totalmente compatible con la semántica de cierre, como tomar variables del alcance, tanto por referencia como por valor, así como poder capturar TODAS las variables, no solo las especificadas. Los dispositivos Lambda se definen implícitamente como objetos de función, proporcionando el contexto necesario para que estos funcionen; Por lo general, esto se hace a través de la elevación de lambda.

Funciones de orden superior No hay problema:

std::function foo_returns_fun( void );

¿No es eso suficiente para ti? Aquí hay una fábrica de lambda:

std::function foo_lambda( int foo ) { [=] () { std::cout << foo; } };

No puede crear funciones, pero puede hacer funcionar objetos, que se pueden pasar como std :: function igual que las funciones normales. Así que toda la funcionalidad está ahí, solo depende de usted juntarla. Podría agregar que gran parte de la STL está diseñada para proporcionarle componentes reutilizables con los que formar objetos de función ad-hoc, aproximando la creación de funciones de todo el paño.

Aplicaciones de función parcial No hay problema

std :: bind es totalmente compatible con esta característica, y también es bastante adepto a las transformaciones de funciones en otras arbitrariamente diferentes:

void f(int n1, int n2, int n3, const int& n4, int n5)
{
    std::cout << n1 << '' '' << n2 << '' '' << n3 << '' '' << n4 << '' '' << n5 << ''/n'';
}

int n = 7;
// (_1 and _2 are from std::placeholders, and represent future
// arguments that will be passed to f1)
auto f1 = std::bind(f, _2, _1, 42, std::cref(n), n);

Para las técnicas de memoización y otras técnicas de especialización de funciones parciales, debe codificarlo usted mismo mediante un contenedor:

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)>
memoize(ReturnType (*func) (Args...))
{
    auto cache = std::make_shared<std::map<std::tuple<Args...>, ReturnType>>();
    return ([=](Args... args) mutable  
    {
        std::tuple<Args...> t(args...);
        if (cache->find(t) == cache->end())
            (*cache)[t] = func(args...);

        return (*cache)[t];
    });
}

Se puede hacer, y de hecho se puede hacer de forma relativamente automática, pero nadie lo ha hecho por ti. }

Combinadores No hay problema:

Empecemos con los clásicos: mapa, filtro, pliegue.

vector<int> startvec(100,5);
vector<int> endvec(100,1);

// map startvec through negate
std::transform(startvec.begin(), startvec.end(), endvec.begin(), std::negate<int>())

// fold startvec through add
int sum =  std::accumulate(startvec.begin(), startvec.end(), 0, std::plus<int>());

// fold startvec through a filter to remove 0''s
std::copy_if (startvec.begin(), startvec.end(), endvec.begin(), [](int i){return !(i==0);} );

Estos son bastante simples, pero los encabezados <functional> , <algorithm> y <numerical> proporcionan docenas de funtores (objetos que se pueden llamar como funciones) que se pueden colocar en estos algoritmos genéricos, así como otros algoritmos genéricos. Juntos, forman una poderosa habilidad para componer características y comportamiento.

Sin embargo, intentemos algo más funcional: SKI se puede implementar fácilmente y es muy funcional, derivado del cálculo lambda sin tipo:

template < typename T >
T I(T arg)
{
    return arg;
}

template < typename T >
std::function<T(void*)> K(T arg)
{
return [=](void*) -> T { return arg; };
}

template < typename T >
T S(T arg1, T arg2, T arg3)
{
return arg1(arg3)(arg2(arg1));
}

Estos son muy frágiles; en efecto, estos deben ser de un tipo que devuelva su propio tipo y tome un solo argumento de su propio tipo; tales restricciones permitirían entonces que todo el razonamiento funcional del sistema SKI se aplique de manera segura a la composición de estos. Con un poco de trabajo y un poco de metaprogramación de plantillas, mucho de esto podría hacerse incluso en tiempo de compilación a través de la magia de las plantillas de expresión para formar un código altamente optimizado.

Las plantillas de expresión , como punto de partida, son una técnica en la que una expresión, generalmente en forma de una serie de operaciones o orden secuencial de código, se basa como argumento de una plantilla. Las plantillas de expresiones por lo tanto son compiladores de tiempo de compilación; son altamente eficientes, seguros para el tipo y permiten que los lenguajes específicos del dominio se incrusten directamente en C ++. Si bien estos son temas de alto nivel, se les da un buen uso en la biblioteca estándar y en boost :: spirit, como se muestra a continuación.

Combinadores de analizador de espíritu

template <typename Iterator>
bool parse_numbers(Iterator first, Iterator last)
{
    using qi::double_;
    using qi::phrase_parse;
    using ascii::space;

    bool r = phrase_parse(
    first,                          
    last,                           
    double_ >> (char_('','') >> double_),   
    space                           
    );

    if (first != last) // fail if we did not get a full match
        return false;
    return r;
}

Esto identifica una lista de números delimitados por comas. double_ y char_ son analizadores individuales que identifican un solo doble o un solo char, respectivamente. Usando el operador >>, cada uno pasa al siguiente, formando un solo analizador combinado grande. Se pasan a través de las plantillas, la "expresión" de su acción combinada se acumula. Esto es exactamente análogo a los combinadores tradicionales, y se comprueba completamente el tiempo de compilación.

Valarray

valarray , una parte del estándar C ++ 11, puede usar plantillas de expresión (pero no es necesario, por alguna extraña razón) para facilitar la eficiencia de las transformaciones. En teoría, cualquier cantidad de operaciones se podrían unir, lo que formaría una gran expresión desordenada que luego se puede alinear agresivamente para la velocidad. Esta es otra forma de combinador.

Sugiero este recurso si desea saber más acerca de las plantillas de expresión; son absolutamente fantásticos para hacer todas las comprobaciones de tiempo de compilación que desea, así como para mejorar la reutilización del código. Sin embargo, son difíciles de programar, por lo que te aconsejo que encuentres una biblioteca que contenga los idiomas que quieras en lugar de rodar los tuyos.

Funciones de firmas como tipos No hay problema

void my_int_func(int x)
{
    printf( "%d/n", x );
}

void (*foo)(int) = &my_int_func;

o, en C ++, usaríamos std :: function:

std::function<void(int)> func_ptr = &my_int_func;

Inferencia de tipos No hay problema

Variables simples escritas por inferencia:

// var is int, inferred via constant
auto var = 10;

// y is int, inferred via var
decltype(var) y = var;

Inferencia de tipos genéricos en plantillas:

template < typename T, typename S >
auto multiply (const T, const S) -> decltype( T * S )
{
    return T * S;
}

Además, esto se puede usar en lambdas, objetos de función, básicamente, cualquier expresión de tiempo de compilación puede hacer uso de decltype para la inferencia de tipo de tiempo de compilación.

Pero eso no es lo que realmente buscas aquí, ¿verdad? Desea la deducción de tipos, así como la restricción de tipos, la reconstrucción de tipos y las derivaciones de tipos. Todo esto se puede hacer con conceptos, pero aún no son parte del lenguaje.

Entonces, ¿por qué no los implementamos? boost::concepts , boost::typeerasure y type traits (descendiente de boost :: tti and boost :: typetraits) pueden hacer todo esto.

¿Quieres restringir una función basada en algún tipo? std::enable_if al rescate!

Ah, pero eso es ad hoc ¿verdad? Eso significaría que para cualquier nuevo tipo que quieras construir, necesitarías hacer repetitivo, etc. Bueno, no, ¡pero aquí hay una mejor manera!

template<typename RanIter>
BOOST_CONCEPT_REQUIRES(
    ((Mutable_RandomAccessIterator<RanIter>))
    ((LessThanComparable<typename Mutable_RandomAccessIterator<RanIter>::value_type>)),
    (void)) // return type
stable_sort(RanIter,RanIter);

Ahora, stable_sort solo puede trabajar en tipos que coincidan con sus estrictos requisitos. boost :: concept tiene toneladas de versiones preconfiguradas, solo necesitas colocarlas en el lugar correcto.

Si desea llamar a funciones diferentes o hacer cosas diferentes con tipos diferentes, o rechazar tipos, use rasgos de tipo, ahora es estándar. ¿Necesita seleccionar según las partes del tipo, en lugar del tipo completo? ¿O permitir que muchos tipos diferentes, que tienen una interfaz común, sean solo un tipo con esa misma interfaz? Pues entonces necesitas borrado de tipo, ilustrado abajo:

Tipo polimorfismo no hay problema

Plantillas, para el tiempo de compilación del polimorfismo:

std::vector<int> intvector;
std::vector<float> floatvector;
...

Borrado de tipo, por tiempo de ejecución y polimorfismo de tipo basado en adaptador:

boost::any can_contain_any_type;
std::function can_call_any_function;
any_iterator can_iterator_any_container;
...

El borrado de tipo es posible en cualquier lenguaje OO, e implica configurar objetos de pequeña función que se derivan de una interfaz común y traducir objetos internos a ella. Con un poco de impulso MPL, esto es rápido, fácil y efectivo. Espera ver que esto se vuelva muy popular pronto.

Estructuras de datos inmutables No de sintaxis para construcciones explícitas, pero es posible:

Se puede hacer a través de no utilizar mutadores o metaprogramación de plantillas. Como se trata de una gran cantidad de código (un ADT completo puede ser bastante grande), los vincularé here , para mostrar cómo hacer una lista inmutable de enlaces individuales.

Hacer esto en tiempo de compilación requeriría una buena cantidad de magia de plantilla, pero se puede hacer más fácilmente con constexpr. Este es un ejercicio para el lector; No sé de ninguna biblioteca de tiempo de compilación para esto fuera de mi cabeza.

Sin embargo, hacer una estructura de datos inmutable desde el STL es bastante fácil:

const vector<int> myvector;

Ahí tienes; Una estructura de datos que no se puede cambiar! Con toda seriedad, las implementaciones de árbol de dedos existen y son probablemente su mejor apuesta para la funcionalidad de matriz asociativa. Simplemente no está hecho para ti por defecto.

Tipos de datos algebraicos No hay problema:

El sorprendente boost::mpl permite restringir los usos de los tipos, que junto con boost::fusion y boost::functional hacen cualquier cosa en el momento de la compilación que desee en relación con ADT. De hecho, la mayor parte está hecha para ti:

#include <boost/mpl/void.hpp>
//A := 1
typedef boost::mpl::void_ A;

Como se indicó anteriormente, gran parte del trabajo no se realiza por usted en un solo lugar; por ejemplo, necesitaría usar boost::optional para obtener tipos opcionales, y mpl para obtener el tipo de unidad, como se vio anteriormente. Pero al usar mecánicos de plantillas de tiempo de compilación relativamente simples, puede hacer tipos de ADT recursivos, lo que significa que puede implementar ADT generalizados. Como el sistema de plantillas se ha completado, tiene a su disposición un verificador de tipos y un generador ADT completos.

Sólo está esperando que juntes las piezas.

Variantes basadas en ADT

boost::variant proporciona uniones con tipo de verificación, además de las uniones originales en el idioma. Estos se pueden utilizar sin problemas, entre:

boost::variant< int, std::string > v;

Esta variante, que puede ser int o string, puede asignarse de cualquier manera con la verificación, e incluso puede hacer una visita basada en la variante de tiempo de ejecución:

class times_two_visitor
    : public boost::static_visitor<>
{
public:
    void operator()(int & i) const
    {
        i *= 2;
    }
    void operator()(std::string & str) const
    {
        str += str;
    }
};

Estructuras de datos anónimos / Ad-hoc No hay problema:

¡Por supuesto que tenemos tuplas! Puedes usar structs si quieres, o:

std::tuple<int,char> foo (10,''x'');

También puede realizar una gran cantidad de operaciones en tuplas:

// Make them
auto mytuple = std::make_tuple(3.14,"pi");
std::pair<int,char> mypair (10,''a'');

// Concatenate them
auto mycat = std::tuple_cat ( mytuple, std::tuple<int,char>(mypair) );

// Unpack them
int a, b;
std::tie (a, std::ignore, b, std::ignore) = mycat; 

Recursión de cola No hay soporte explícito, la iteración es suficiente

Esto no se admite ni es obligatorio en el LISP común, aunque está en el Esquema y, por lo tanto, no sé si puede decir que es necesario. Sin embargo, puedes hacer fácilmente la recursión de la cola en C ++:

std::size_t get_a_zero(vector<int>& myints, std::size_t a ) {
   if ( myints.at(a) == 0 ) {
      return a;
   }
   if(a == 0) return myints.size() + 1;

   return f(myints, a - 1 );   // tail recursion
}

Ah, y GCC compilará esto en un bucle iterativo, sin daño ni falta. Si bien este comportamiento no es obligatorio, es permisible y se realiza en al menos un caso que conozco (posiblemente también Clang). Pero no necesitamos recursión de cola: C ++ está totalmente de acuerdo con las mutaciones:

std::size_t get_a_zero(vector<int>& myints, std::size_t a ) {
   for(std::size_t i = 0; i <= myints.size(); ++i){
       if(myints.at(i) == 0) return i;
    }
    return myints.size() + 1;
}

La recursión de la cola se optimiza en iteración, por lo que tiene exactamente la misma potencia. Además, mediante el uso de boost::coroutine , uno puede proporcionar fácilmente el uso de las pilas definidas por el usuario y permitir una recursión ilimitada, haciendo que la recursión de la cola sea innecesaria. El lenguaje no es activamente hostil a la recursión ni a la recursión de la cola; simplemente exige que usted proporcione la seguridad usted mismo.

Coincidencia de patrones No hay problema:

Esto se puede hacer fácilmente a través de boost :: variant, como se detalla en este documento, a través del patrón de visitantes:

class Match : public boost::static_visitor<> {
public:
    Match();//I''m leaving this part out for brevity!
    void operator()(const int& _value) const {
       std::map<int,boost::function<void(void)>::const_iterator operand 
           = m_IntMatch.find(_value);
       if(operand != m_IntMatch.end()){
           (*operand)();
        }
        else{
            defaultCase();
        }
    }
private:
    void defaultCause() const { std::cout << "Hey, what the..." << std::endl; }
    boost::unordered_map<int,boost::function<void(void)> > m_IntMatch;
};

Este ejemplo, de este encantador sitio web muestra cómo obtener todo el poder de la coincidencia de patrones de Scala, simplemente usando boost :: variant. Hay más repetitivo, pero con una bonita plantilla y una biblioteca de macros, gran parte de eso desaparecerá.

De hecho, aquí hay una biblioteca que ha hecho todo eso por ti:

#include <utility>
#include "match.hpp"                // Support for Match statement

typedef std::pair<double,double> loc;

// An Algebraic Data Type implemented through inheritance
struct Shape
{
    virtual ~Shape() {}
};

struct Circle : Shape
{
    Circle(const loc& c, const double& r) : center(c), radius(r) {}
    loc    center;
    double radius;
};

struct Square : Shape
{
    Square(const loc& c, const double& s) : upper_left(c), side(s) {}
    loc    upper_left;
    double side;
};

struct Triangle : Shape
{
    Triangle(const loc& a, const loc& b, const loc& c) : first(a), second(b), third(c) {}
    loc first;
    loc second;
    loc third;
};

loc point_within(const Shape* shape)
{
    Match(shape)
    {
       Case(Circle)   return matched->center;
       Case(Square)   return matched->upper_left;
       Case(Triangle) return matched->first;
       Otherwise()    return loc(0,0);
    }
    EndMatch
}

int main()
{
    point_within(new Triangle(loc(0,0),loc(1,0),loc(0,1)));
    point_within(new Square(loc(1,0),1));
    point_within(new Circle(loc(0,0),1));
}

Tal como lo proporciona esta encantadora respuesta de Como puede ver, no es meramente posible sino también bonita.

Recolección de basura El estándar futuro, los asignadores, RAII y shared_ptr son suficientes

Si bien C ++ no tiene un GC, hay una propuesta para una que se rechazó en C ++ 11, pero puede incluirse en C ++ 1y . Puede usar una amplia variedad de archivos definidos por el usuario, pero C ++ no necesita recolección de basura.

C ++ tiene un lenguaje conocido como RAII para tratar los recursos y la memoria; por esta razón, C ++ no necesita un GC ya que no produce basura; todo se limpia rápidamente y en el orden correcto por defecto. Esto introduce el problema de quién posee qué, pero esto se resuelve en gran medida en C ++ 11 a través de punteros compartidos, punteros débiles y punteros únicos:

// One shared pointer to some shared resource
std::shared_ptr<int> my_int (new int);

// Now we both own it!
std::shared_ptr<int> shared_int(my_int);

// I can use this int, but I cannot prevent it''s destruction
std::weak_ptr<int> weak_int (shared_int);

// Only I can ever own this int
std::unique_ptr<int> unique_int (new int);

Estos le permiten proporcionar una forma de recolección de basura mucho más determinista y controlada por el usuario, que no invoca ningún comportamiento de detención del mundo.

¿Que no es lo suficientemente fácil para ti? Use un asignador personalizado, como boost::pool o roll your own; es relativamente fácil utilizar un asignador basado en grupo o arena para obtener lo mejor de ambos mundos: puede asignar fácilmente la libertad que desee, y luego simplemente eliminar el grupo o arena cuando haya terminado. Sin alboroto, sin desorden, y sin detener al mundo.

Sin embargo, en el diseño moderno de C ++ 11, casi nunca se usaría nuevo de todos modos, excepto cuando se asigna a * _ptr, por lo que el deseo de un GC no es necesario de todos modos.

En resumen

C ++ tiene muchas funciones funcionales de lenguaje, y todas las que enumeró se pueden hacer, con la misma capacidad de expresión y poder de Haskell o Lisp. Sin embargo, la mayoría de estas características no están integradas de forma predeterminada; esto está cambiando, con la introducción de los lambda (que completan las partes funcionales de la STL) y con la absorción de impulso en el lenguaje estándar.

No todos estos modismos son los más sabrosos, pero ninguno de ellos es particularmente oneroso para mí o no se puede enmendar en algunas macros para que sean más fáciles de tragar. Pero cualquiera que diga que no es posible no ha hecho su investigación y me parece que tiene una experiencia limitada con la programación real de C ++.