Este artigo foi traduzido por máquina.
C++
Programação em estilo funcional em C++
C++ é uma linguagem de multiparadigm, sistemas-nível que fornece abstrações de alto nível com muito baixa (muitas vezes de zero) de tempo de execução custo. Os paradigmas comumente associados com C++ incluem programação procedural, orientada a objeto e genérica. Porque C++ oferece excelentes ferramentas para programação de alto nível, a programação do mesmo estilo funcional é bastante razoável.
Pela programação de estilo funcional, não me refiro que a programação é estritamente funcional, só que é fácil de usar muitos dos blocos funcionais em C++. Este artigo irá se concentrar em uma das mais importantes construções programação funcionais: Trabalhando com valores em vez de identidades. Falarei sobre o forte suporte C++ sempre teve para trabalhar com valores e, em seguida, mostrar como o novo padrão de C++ 11 expande este suporte com lambdas. Finalmente, vou apresentar um método de trabalhar com estruturas de dados imutáveis que mantém a velocidade que c++ é conhecido para, fornecendo a proteção que têm desfrutado de linguagens funcionais.
Valores vs. Identidades
Deixe-me primeiro explicar o que quero dizer, trabalhando com valores, em vez de identidades. Valores simples como 1, 2 e 3 são fáceis de identificar. Eu também poderia dizer que o 1, 2 e 3 são valores inteiros constantes. Isso seria redundante, no entanto, porque todos os valores são realmente de constantes e os próprios valores nunca mudam (1 é sempre 1 e 1 nunca será 2). Por outro lado, o valor associado a uma identidade pode mudar (x pode ser igual 1 agora, mas ele podia ser igual 2 mais tarde).
Infelizmente, é fácil confundir valores e tipos de valor. Tipos de valor são repassados pelo valor, em vez de referência. Embora eu quero focar aqui os valores e não o mecanismo envolvido em uso ou copiá-los, é útil ver como tipos de valor ir parte em preservar o conceito de valores e identidades.
O código em Figura 1 demonstra um simple uso de um tipo de valor.
Figura 1, usando um tipo de valor
void Foo()
{
for (int x = 0; x < 10; ++x)
{
// Call Bar, passing the value of x and not the identity
Bar(x);
}
}
void Bar(int y)
{
// Display the value of y
cout << y << " ";
// Change the value that the identity y refers to
// Note: This will not affect the value that the variable x refers to
y = y + 1;
}
// Outputs:
// 0 1 2 3 4 5 6 7 8 9
Com apenas uma pequena alteração, a variável y pode tornar-se um tipo de referência — que altera drasticamente a relação entre x e y, como mostrado na Figura 2.
Figura 2 usando um tipo de referência
void Foo()
{
for (int x = 0; x < 10; ++x)
{
// Call Bar, passing the identity of x
Bar(x);
}
}
void Bar(int& y)
{
// Display the value of y
cout << y << " ";
// Change the value that the identity y refers to
// Note: This will affect the variable x
y = y + 1;
}
// Outputs:
// 0 2 4 6 8
Como Figura 3 mostra, C++ fornece também o modificador const, que impede que o programador fazer alterações em uma variável e, portanto, ainda preserva o conceito de valor. (Como a maioria das coisas em C++, no entanto, há pelo menos uma forma de derrotar essa proteção. Para obter mais informações, procure const_cast, que destina-se para trabalhar com código antigo que não é "const correta.")
Figura 3 O modificador const
void Foo()
{
for (int x = 0; x < 10; ++x)
{
// Call Bar, passing the identity of x,
// yet the value of x will be protected by the const
Bar(x);
}
}
void Bar(const int& y)
{
// Use the value of y
cout << y << " ";
// Attempt to change the value of what the identity y refers to
y = y + 1; // This line will not compile because y is const!
}
Observe na Figura 3 que que y é passado por referência, o valor de y é protegido em tempo de compilação por um modificador const. Isto dá os programadores C++ um método eficiente de passar grandes objetos enquanto estiver trabalhando com seus valores, ao contrário de suas identidades.
Com o modificador const, C++ tem tipos de dados imutáveis que se assemelham àquelas encontradas em linguagens de programação mais funcionais. No entanto, lidar com esses tipos de dados imutáveis é difícil. Além disso, fazer cópias de profundidade (completo) de objetos grandes para cada pequena mudança não é eficiente. No entanto, deve ficar claro que o C++ padrão sempre teve um conceito de trabalhar com valores (mesmo se não é um conceito muito puro).
Note que o suporte para tipos valor estende para tipos definidos pelo usuário através de construtores de cópia e operadores de atribuição. Construtores de cópia de C++ e operadores de atribuição permitem tipos definidos pelo usuário fazer uma cópia em profundidade do objeto. Tenha em mente que, enquanto os construtores de cópia de C++ pode ser implementado para fazer uma cópia superficial, você terá que certificar-se de que a semântica de valor é preservada.
C++ 11 suporte para programação funcional-estilo
C++ 11 traz uma série de novas ferramentas para programação funcional-estilo. Talvez mais importante, C++ agora tem suporte para lambdas (também conhecido como fechamentos ou funções anônimas). Lambdas permitem que você escreva o seu código de maneiras que não teria sido práticas antes. Esta funcionalidade estava disponível anteriormente através de functores, que são poderosos, mas menos prático de usar. (Na verdade, lambdas de C++ escreva functores anônimos nos bastidores) Figura 4 mostra como lambdas melhoraram nosso código com um exemplo simples que usa a biblioteca padrão do C++ (STL).
Figura 4 usando Lambdas
void Foo()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for_each(begin(v), end(v), [](int i) {
cout << i << " ";
});
}
// Outputs:
// 1 2 3
Neste caso, a função for_each aplica um lambda para cada elemento de um vetor. É importante notar que lambdas de C++ foram projetados para ser usados em linha quando possível; Assim, lambdas podem executar tão rápido quanto código artesanal.
Enquanto C++ é apenas uma das muitas línguas imperativas que agora têm lambdas, o que faz com que lambdas de C++ especial é que (semelhante a linguagens de programação funcionais) podem preservar o conceito de trabalhar com valores em vez de identidades. Enquanto linguagens de programação funcionais conseguir isso fazendo variáveis imutáveis, C++ faz isso fornecendo um controle sobre a captura. Considere o código na Figura 5.
Figura 5 captura por referência
void Foo()
{
int a[3] = { 11, 12, 13 };
vector<function<void(void)>> vf;
// Store lambdas to print each element of an array
int ctr;
for (ctr = 0; ctr < 3; ++ctr) {
vf.push_back([&]() {
cout << "a[" << ctr << "] = " << a[ctr] << endl;
});
}
// Run each lambda
for_each(begin(vf), end(vf), [](function<void(void)> f) {
f();
});
}
// Outputs:
// a[3] = -858993460
// a[3] = -858993460
// a[3] = -858993460
Nesse código, tudo é captado por referência, que é o comportamento padrão para lambdas em outros idiomas. Ainda captura por referência complica as coisas, a menos que as variáveis sejam capturadas são imutáveis. Se você é novo para trabalhar com lambdas, você provavelmente esperar a saída do código a seguir:
a[0] = 11
a[1] = 12
a[2] = 13
No entanto, que não é a saída que você obter — e o programa ainda pode falhar. Isso ocorre porque a variável ctr é capturado por referência, então todos os lambdas usam o valor final do ctr (isto é, 3, o valor que fez o loop para chegar a um fim) e, em seguida, acessar a matriz para além dos seus limites.
Também é interessante notar que, para manter a variável ctr viva para ser usado por lambda fora do loop, declaração da variável ctr tem de ser levantada do loop for. Enquanto que algumas línguas eliminam a necessidade de levantar as variáveis de tipo de valor para um escopo apropriado, que não resolve realmente o problema, o que é que o lambda deve usar o valor de ctr em oposição a identidade do CTR variável. (Existem soluções alternativas para outras linguagens que envolvem fazer uma cópia explícita a uma variável temporária. No entanto, isso torna um pouco incerto sobre o que está acontecendo, e é sujeito a erro porque a variável original também é capturada e, portanto, ainda está disponível para uso.)
Como Figura 6 mostra, C++ fornece uma sintaxe simples para permitir o fácil controle da captura do lambda, que preserva o conceito de trabalhar com valores.
Figura 6 a sintaxe do C++ para controlar Lambda capturar
| [] | Não captura nada (exatamente o que eu queria no primeiro exemplo de lambda) |
| [&] | Capture tudo por referência (comportamento de lambda tradicional, porém não é consistente com a programação funcional ênfase em valores) |
| [=] | Capture tudo por valor (enquanto isso preserva o conceito de valores, que limita a utilidade os lambdas; Além disso, pode ser caro copiar objetos grandes) |
| [& ctr] | Capturar apenas ctr e capturar ctr por referência |
| [& ctr] | Capturar apenas ctr e capturar ctr por valor |
| [&, ctr] | Capturar ctr por valor e tudo mais por referência |
| [=, & v] | Capture v por referência e tudo o mais pelo valor |
| [&, ctr1, ctr2] | Capturar ctr1 e ctr2 por valor e tudo mais por referência |
É claro, de Figura 6 que o programador tem controle completo sobre como o lambda captura variáveis e valores. No entanto, enquanto isso preserva o conceito de trabalhar com valores, ele não faz nada para tornar o trabalho com dados complexos estruturas como valores eficientes.
Tipos de dados imutáveis
O que está faltando são as estruturas de dados imutáveis eficiente com algumas linguagens de programação funcionais. Estas línguas facilitam a estruturas de dados imutáveis que são eficientes mesmo quando muito grandes, porque eles compartilham dados comuns. A criação de estruturas de dados em C++ que compartilham dados é trivial — você alocar dinamicamente apenas dados e cada estrutura de dados tem ponteiros para os dados. Infelizmente, é mais difícil de gerenciar a vida útil de variáveis compartilhadas (por esta razão, coletores de lixo têm se tornado populares). Felizmente, C++ 11 fornece uma solução elegante para trabalhar com variáveis compartilhadas por meio da classe de modelo de std::shared_ptr, como mostrado na Figura 7.
Figura 7 compartilhamento de variáveis
void Foo()
{
// Create a shared int
// (dynamically allocates an integer
// and provides automatic reference counting)
auto sharedInt = make_shared<int>(123);
// Share the integer with a secondShare
// (increments the reference count)
shared_ptr<int> secondShare(sharedInt);
// Release the pointer to the first integer
// (decrements the reference count)
sharedInt = nullptr;
// Verify the shared int is still alive
cout << "secondShare = " << *secondShare << endl;
// Shared int is automatically de-allocated
// as secondShare falls out of scope and the reference
// count falls to zero
}
// Outputs:
// secondShare = 123
O código em Figura 7 ilustra um uso simple do std::shared_ptr e seu std::make_shared de função auxiliar. Usar std::shared_ptr facilita o compartilhamento de dados entre as estruturas de dados sem medo de vazamento de memória (como referências circulares são evitadas). Observe que o std::shared_ptr fornece as garantias de segurança básica, e corre rápido porque ele usa um design sem bloqueio. No entanto, tenha em mente que a segurança do thread básica garantir que std::shared_ptr fornece automaticamente não se estende para o objeto ao qual ele está apontando. Ainda, std::shared_ptr garante que não irá reduzir a garantia de segurança do thread do objeto aponta. Objetos imutáveis naturalmente oferecem uma garantia de segurança do segmento forte porque depois que são criados, eles nunca mudam. (Na verdade, nunca mudam de maneira observável, que inclui, entre outras coisas, uma garantia de segurança do thread apropriado.) Portanto, quando você usar um std::shared_ptr com um objeto imutável, a combinação mantém a garantia de segurança do thread forte do objeto imutável.
Agora pode facilmente criar uma simple classe imutável que potencialmente compartilha dados, como mostrado na Figura 8.
Figura 8 uma classe imutável para compartilhamento de dados
class Immutable
{
private:
// Use a normal double, copying is cheap
double d_;
// Use a shared string, because strings can be very large
std::shared_ptr<std::string const> s_;
public:
// Default constructor
Immutable()
: d_(0.0),
s_(std::make_shared<std::string const>(""))
{}
// Constructor taking a string
Immutable(const double d, const string& s)
: d_(d),
s_(std::make_shared<std::string const>(s))
{}
// Move constructor
Immutable(Immutable&& other)
: s_()
{
using std::swap;
swap(d_, other.d_);
swap(s_, other.s_);
}
// Move assignment operator
Immutable& operator=(Immutable&& other)
{
swap(d_, other.d_);
swap(s_, other.s_);
return *this;
}
// Use default copy constructor and assignment operator
// Getter Functions
double GetD() const
{
// Return a copy because double is small (8 bytes)
return d_;
}
const std::string& GetS() const
{
// Return a const reference because string can be very large
return *s_;
}
// "Setter" Functions (always return a new object)
Immutable SetD(double d) const
{
Immutable newObject(*this);
newObject.d_ = d;
return newObject;
}
Immutable SetS(const std::string& s) const
{
Immutable newObject(*this);
newObject.s_ = std::make_shared<std::string const>(s);
return newObject;
}
};
O código em Figura 8 é um pouco longo, mas a maioria é o código clichê para os construtores e operadores de atribuição. As duas últimas funções são a chave para fazer com que o objeto imutável. Note-se que os conjuntos e SetD métodos retornam um objeto novo, que deixa o objeto original inalterado. (Incluindo os conjuntos e SetD Métodos while como membros é conveniente, é um pouco de uma mentira, porque eles realmente não mudam o objeto original. Para uma solução de limpeza, consulte a ImmutableVector no figuras 9 e 10.) Figura 11 mostra a classe imutável em ação.
Figura 9 usando a classe de modelo de ImmutableVector inteligentes
template <class ImmutableVector>
void DisplayImmutableVector(const char* name, const ImmutableVector& v)
{
using namespace std;
cout << name << ".Size() = " << v.Size()
<< ", " << name << "[] = { ";
for (size_t ctr = 0; ctr < v.Size(); ++ctr) {
cout << v[ctr] << " ";
}
cout << "}" << endl;
}
void ImmutableVectorTest1()
{
// Create an ImmutableVector with a branching size of four
ImmutableVector<int, 4> v;
// Another ImmutableVector (we will take a copy of v at element 6)
ImmutableVector<int, 4> aCopyOfV;
// Push 16 values into the vector (this will create a two level tree).
// Note that the vector is being assigned to itself.
The
// move constructor insures this is not very expensive, but
// if a copy was made at any point the copy would remain
// unchanged, but continue to share the applicable data with
// the current version.
for (int ctr = 0; ctr < 10; ++ctr) {
v = AppendValue(v, ctr);
if (ctr == 6) aCopyOfV = v;
}
// Display the contents of the vectors
DisplayImmutableVector("v", v);
DisplayImmutableVector("aCopyOfV", aCopyOfV);
}
// Outputs:
// v.Size() = 10, v[] = { 0 1 2 3 4 5 6 7 8 9 }
// aCopyOfV.Size() = 7, aCopyOfV[] = { 0 1 2 3 4 5 6 }
Figura 10 métodos para operar o ImmutableVector
void ImmutableVectorTest2()
{
ImmutableVector<int, 4> v;
v = AppendValue(v, 1);
v = AppendValue(v, 2);
v = AppendValue(v, 3);
int oldValue = v.Back();
auto v1 = TruncateValue(v);
auto v2 = SubstituteValueAtIndex(v, 0, 3);
auto v3 = GenerateFrom(v, [](ImmutableVector<int, 4>::MutableVector& v) {
v[0] = 4;
v[1] = 5;
v[2] = 6;
v.PushBack(7);
v.PushBack(8);
});
auto v4 = GenerateFrom(v3, [](ImmutableVector<int, 4>::MutableVector& v4) {
using namespace std;
cout << "Change v4 by calling PopBack:" << endl;
cout << "x = v4.PopBack()" << endl;
int x = v4.PopBack();
cout << "x == " << x << endl;
cout << endl;
});
// Display the contents of the vectors
DisplayImmutableVector("v", v);
DisplayImmutableVector("v1", v1);
DisplayImmutableVector("v2", v2);
DisplayImmutableVector("v3", v3);
DisplayImmutableVector("v4", v4);
}
// Outputs:
// Change v4 by calling PopBack:
// x = v4.PopBack()
// x == 8
//
// Resulting ImmutableVectors:
// v.Size() = 3, v[] = { 1 2 3 }
// v1.Size() = 2, v1[] = { 1 2 }
// v2.Size() = 3, v2[] = { 3 2 1 }
// v3.Size() = 5, v3[] = { 4 5 6 7 8 }
// v4.Size() = 4, v4[] = { 4 5 6 7 }
Figura 11 A classe imutável em ação
using namespace std;
void Foo()
{
// Create an immutable object
double d1 = 1.1;
string s1 = "Hello World";
Immutable a(d1, s1);
// Create a copy of the immutable object, share the data
Immutable b(a);
// Create a new immutable object
// by changing an existing immutable object
// (Note the new object is returned)
string s2 = "Hello Other";
Immutable c = a.SetS(s2);
// Display the contents of each object
cout << "a.GetD() = " << a.GetD() << ", "
<< "a.GetS() = " << a.GetS()
<< " [address = " << &(a.GetS()) << "]" << endl;
cout << "b.GetD() = " << b.GetD() << ", "
<< "b.GetS() = " << b.GetS()
<< " [address = " << &(b.GetS()) << "]" << endl;
cout << "c.GetD() = " << c.GetD() << ", "
<< "c.GetS() = " << c.GetS()
<< " [address = " << &(c.GetS()) << "]" << endl;
}
// Outputs:
// a.GetD() = 1.1, a.GetS() = Hello World [address = 008354BC]
// b.GetD() = 1.1, b.GetS() = Hello World [address = 008354BC]
// c.GetD() = 1.1, c.GetS() = Hello Other [address = 008355B4]
Nota que o objeto b compartilha a mesma seqüência como objeto um (ambas as seqüências de caracteres são no mesmo endereço). Adicionar campos adicionais com associado getters e setters é trivial. Embora esse código é bom, é um pouco mais difícil de dimensionar para recipientes quando você está sendo eficiente. Por exemplo, um ingênuo ImmutableVector pode manter uma lista de ponteiros compartilhadas que representa cada elemento da matriz. Quando o ingênuo que imutável-Vector for alterado, todo o array de ponteiros compartilhados precisa ser duplicada, incorrer em custos adicionais como cada elemento da matriz de shared_ptr seria precisa sua contagem de referência para ser incrementado.
Há uma técnica, porém, que permite que a estrutura de dados compartilhar a maioria de seus dados e minimizar a duplicação. Esta técnica usa uma árvore de alguma forma para exigir a duplicação de apenas os nós que são diretamente afetados por uma mudança. Figura 12mostra uma comparação de um ingênuo de ImmutableVector e um ImmutableVector inteligente.
Figura 12 comparação ingênua e Smart ImmutableVectors
Esta técnica de árvore dimensiona bem: à medida que cresce o número de elementos, a porcentagem da árvore que precisa ser duplicado é minimizada. Além disso, ajustando-se o fator de ramificação (assim cada nó tem mais de dois filhos), você pode conseguir um equilíbrio na reutilização de nó e a sobrecarga de memória.
Eu desenvolvi uma classe de modelo de ImmutableVector inteligente que pode ser baixada de archive.msdn.microsoft.com/mag201208CPP. Figura 9 mostra como você pode usar a minha classe de ImmutableVector. (Como observado anteriormente, para fazer a natureza imutável do ImmutableVector mais clara para os usuários, ImmutableVector usa funções de membro estático para todas as ações que geram novas versões).
Para ações de somente leitura, o vetor pode ser usado tanto como um vetor normal. (Note que neste exemplo, ainda não implementei iteradores, mas isso deve ser bastante trivial). Para ações de gravação, AppendValue e TruncateValue métodos estáticos retornam uma nova ImmutableVector, preservando assim o objeto original. Unfortu-nately, isso não é razoável que o operador subscrito da matriz, por isso fiz o operador subscrito de matriz somente leitura (ou seja, ele retorna uma referência constante) e forneceu um método estático de SubstituteValueAtIndex. Seria bom, no entanto, ser capaz de fazer um grande número de modificações usando o operador de subscrito de matriz em um único bloco de código. Para facilitar isso, o ImmutableVector fornece um método estático de Gerardo, que leva um lambda (ou qualquer outro functor). Por sua vez, o lambda tem uma referência a MutableVector como um parâmetro, que permite trabalhar em um MutableVector temporário que pode ser alterada livremente como um normal de std:: vector lambda. O exemplo de Figura 10 mostra os vários métodos para operar o ImmutableVector.
A beleza do método estático Gerardo é que o código dentro dele pode ser escrito de forma imperativa, enquanto resultando em um objeto imutável que pode ser compartilhado com segurança. Note que a gerar-do método estático impede o acesso não autorizado ao ImmutableVector subjacente, desativando o MutableVector ele passado em lambda logo que saiu o lambda. Por favor, note também que, enquanto ImmutableVector, fornece uma garantia de segurança do segmento forte, sua classe de auxiliar MutableVector não (e se destina a ser utilizado localmente dentro do lambda, não repassado para outros segmentos). Minha implementação também otimiza a várias alterações dentro do método de mudança tal que não há mínimo de reestruturação que ocorrem na árvore temporária, o que dá um impulso de bom desempenho.
Encerramento
Este artigo dá-lhe apenas um gosto de como você pode usar o estilo funcional de programação em seu código C++. Além disso, recursos de C++ 11 como lambdas de trazem um toque de estilo funcional programação independentemente do paradigma usado.
David Cravey é MVP de C++ Visual que gosta de programação em talvez C++ um pouco demais. Você vai encontrá-lo apresentando às universidades e grupos de usuário local do C++. Durante o dia ele gosta de trabalhar na NCR, através de TEKsystems em Fort Worth, Texas.
Agradecemos aos seguintes especialistas técnicos pela revisão deste artigo: Giovanni Dicanio, Stephan T. Lavavej, Angel Hernández Matos, Alf P. Steinbach e David Wilkinson