What can C++ offer as far as functional programming?

Question

Are the following things, considered intrinsic to FP, possible in C++?

• higher order functions
• lambdas (closures/anonymous functions)
• function signatures as types
• type polymorphism (generics)
• immutable data structures
• algebraic data types (variants)
• adhock data structures (tuples)
• partial function applications
• type inference
• tail recursion
• pattern matching
• garbage collection

Solution 1

Let me start by noting that most of these are not "intrinsic", or shall we say, "required"; many of these are absent from notable functional languages, and in theory, many of these features can be used to implement the others (such as higher order functions in untyped lambda calculus).

However, let's go through these:

Closures

Closures are not necessary, and are syntactical sugar: by the process of Lambda Lifting, you can convert any closure into a function object (or even just a free function).

Named Functors (C++03)

Just to show that this isn't a problem to begin with, here's a simple way to do this without lambdas in C++03:

Isn't A Problem:

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

Anonymous functions (C++11)

However, anonymous functions in C++11 (also called lambda functions, as they derive from the LISP history), which are implemented as non-aliasingly named function objects, can provide the same usability (and are in fact referred to as closures, so yes, C++11 does have closures):

No problem:

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

Polymorphic anonymous functions (C++14)

Even less of a problem, we don't need to care about the parameter types anymore in C++14:

Even Less Problem:

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);

I should note this fully support closure semantics, such as grabbing variables from scope, both by reference and by value, as well as being able to grab ALL variables, not merely specified ones. Lambda's are implicitly defined as function objects, providing the necessary context for these to work; usually this is done via lambda lifting.

Higher Order Functions No problem:

std::function foo_returns_fun( void );

Is that not sufficient for you? Here's a lambda factory:

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

You can't create functions, but you can function objects, which can be passed around as std::function same as normal functions. So all the functionality is there, it's just up to you to put it together. I might add that much of the STL is designed around giving you reusable components with which to form ad-hoc function objects, approximating creating functions out of whole cloth.

Partial Function Applications No problem

std::bind fully supports this feature, and is quite adept at transformations of functions into arbitrarily different ones as well:

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);

For memoization and other partial function specialization techniques, you have to code it yourself using a wrapper:

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];
    });
}

It can be done, and in fact it can be done relatively automatically, but no one has yet done it for you. }

Combinators No problem:

Let's start with the classics: map, filter, fold.

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);} );

These are quite simple, but the headers <functional>, <algorithm>, and <numerical> provide dozens of functors (objects callable as functions) which can be placed into these generic algorithms, as well as other generic algorithms. Together, these form a powerful ability to compose features and behavior.

Let's try something more functional though: SKI can easily be implemented, and is very functional, deriving from untyped lambda calculus:

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));
}

These are very fragile; in effect, these must be of a type which returns it's own type and takes a single argument of their own type; such constraints would then allow for all the functional reasoning of the SKI system to be applied safely to the composition of these. With a little work, and some template metaprogramming, much of this could even be done at compile time through the magic of expression templates to form highly optimized code.

Expression templates, as an aside, are a technique in which an expression, usually in the form of a series of operations or sequential order of code, is based as an argument to a template. Expression templates therefore are compile time combinators; they are highly efficient, type safe, and effectively allow for domain specific languages to be embedded directly into C++. While these are high level topics, they are put to good use in the standard library and in boost::spirit, as shown below.

Spirit Parser Combinators

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;
}

This identifies a comma deliminated list of numbers. double_ and char_ are individual parsers that identify a single double or a single char, respectively. Using the >> operator, each one passes themselves to the next, forming a single large combined parser. They pass themselves via templates, the "expression" of their combined action building up. This is exactly analogous to traditional combinators, and is fully compile time checked.

Valarray

valarray, a part of the C++11 standard, is allowed to use expression templates (but not required, for some odd reason) in order to facilitate efficiency of transforms. In theory, any number of operations could be strung together, which would form quite a large messy expression which can then be aggressively inlined for speed. This is another form of combinator.

I suggest this resource if you wish to know more about expression templates; they are absolutely fantastic at getting all the compile time checks you wish done, as well as improving the re-usability of code. They are hard to program, however, which is why I would advise you find a library that contains the idioms you want instead of rolling your own.

Function Signatures As Types No problem

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

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

or, in C++, we'd use std::function:

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

Type Inference No problem

Simple variables typed by inference:

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

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

Generic type inference in templates:

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

Furthermore, this can be used in lambdas, function objects, basically any compile time expression can make use of decltype for compile time type inference.

But that's not what you are really after here, are you? You want type deduction as well as type restriction, you want type reconstruction and type derivations. All of this can be done with concepts, but they are not part of the language yet.

So, why don't we just implement them? boost::concepts, boost::typeerasure, and type traits (descendant from boost::tti and boost::typetraits) can do all of this.

Want to restrict a function based on some type? std::enable_if to the rescue!

Ah, but that's ad hoc right? That would mean for any new type you'd want to construct, you'd need to do boilerplate, etc etc. Well, no, but here's a better way!

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

Now your stable_sort can only work on types that match your stringent requirements. boost::concept has tons of prebuilt ones, you just need to put them in the right place.

If you want to call different functions or do different things off types, or disallow types, use type traits, it's now standard. Need to select based on parts of the type, rather than the full type? Or allow many different types, which have a common interface, to be only a single type with that same interface? Well then you need type erasure, illustrated below:

Type Polymorphism No problem

Templates, for compile time type polymorphism:

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

Type erasure, for run time and adaptor based type polymorphism:

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

Type erasure is possible in any OO language, and involves setting up small function objects which derive from a common interface, and translate internal objects to it. With a little boost MPL boilerplate, this is fast, easy, and effective. Expect to see this become real popular soon.

Immutable Datastructures Not syntax for explicit constructions, but possible:

Can be done via not using mutators or template metaprogramming. As this is a lot of code (a full ADT can be quite large), I will link you here, to show how to make an immutable singly linked list.

To do this at compile time would require a good amount of template magic, but can be done more easily with constexpr. This is an exercise for the reader; I don't know of any compile time libraries for this off the top of my head.

However, making an immutable datastructure from the STL is quite easy:

const vector<int> myvector;

There you are; a data structure that cannot be changed! In all seriousness, finger tree implementations do exist and are probably your best bet for associative array functionality. It's just not done for you by default.

Algebraic data types No problem:

The amazing boost::mpl allows you to constrain uses of types, which along with boost::fusion and boost::functional to do anything at compile time that you would want in regards to ADT. In fact, most of it is done for you:

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

As stated earlier, a lot of the work isn't done for you in a single place; for example, you'd need to use boost::optional to get optional types, and mpl to get unit type, as seen above. But using relatively simple compile time template mechanics, you can do recursive ADT types, which means you can implement generalized ADT's. As the template system is turing complete, you have a turing complete type checker and ADT generator at your disposal.

It's just waiting for you to bring the pieces together.

Variant based ADT's

boost::variant provides type checked unions, in addition to the original unions in the language. These can be used with no fuss, drop in:

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

This variant, which can be int or string, can be assigned either way with checking, and you can even do run time variant based visitation:

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

Anonymous/Ad-hoc data structures No problem:

Of course we have tuples! You could use structs if you like, or:

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

You can also perform a good deal of operations on tuples:

// 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; 

Tail Recursion No explicit support, iteration is sufficient

This is not supported or mandated in Common LISP, though it is in Scheme, and therefore I don't know if you can say it's required. However, you can easily do tail recursion in 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
}

Oh, and GCC will compile this into an iterative loop, no harm no foul. While this behavior is not mandated, it is allowable and is done in at least one case I know of (possibly Clang as well). But we don't need tail recursion: C++ totally is fine with mutations:

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;
}

Tail recursion is optimized into iteration, so you have exactly as much power. Furthermore, through the usage of boost::coroutine, one can easily provide usage for user defined stacks and allow for unbounded recursion, making tail recursion unnecessary. The language is not actively hostile to recursion nor to tail recursion; it merely demands you provide the safety yourself.

Pattern Matching No problem:

This can easily be done via boost::variant, as detailed elsewhere in this, via the visitor pattern:

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;
};

This example, from this very charming website shows how to gain all the power of Scala pattern matching, merely using boost::variant. There is more boilerplate, but with a nice template and macro library, much of that would go away.

In fact, here is a library that has done all that for you:

#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));
}

As provided by this lovely stackoverflow answer As you can see, it is not merely possible but also pretty.

Garbage Collection Future standard, allocators, RAII, and shared_ptr are sufficient

While C++ does not have a GC, there is a proposal for one that was voted down in C++11, but may be included in C++1y. There are a wide variety of user defined ones you can use, but the C++ does not need garbage collection.

C++ has an idiom know as RAII to deal with resources and memory; for this reason, C++ has no need for a GC as it does not produce garbage; everything is cleaned up promptly and in the correct order by default. This does introduce the problem of who owns what, but this is largely solved in C++11 via shared pointers, weak pointers, and unique pointers:

// 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);

These allow you to provide a much more deterministic and user controlled form of garbage collection, that does not invoke any stop the world behavior.

That not easy enough for you? Use a custom allocator, such as boost::pool or roll your own; it's relatively easy to use a pool or arena based allocator to get the best of both worlds: you can easily allocate as freely as you like, then simply delete the pool or arena when you are done. No fuss, no muss, and no stopping the world.

However, in modern C++11 design, you would almost never use new anyway except when allocating into a *_ptr, so the wish for a GC is not necessary anyway.

In Summary

C++ has plenty of functional language features, and all of the ones you listed can be done, with the same power and expression ability of Haskell or Lisp. However, most of these features are not built in by default; this is changing, with the introduction of lambda's (which fill in the functional parts of the STL), and with the absorption of boost into the standard language.

Not all of these idioms are the most palatable, but none of them are particularly onerous to me, or unamendable to a few macros to make them easier to swallow. But anyone who says they are not possible has not done their research, and would seem to me to have limited experience with actual C++ programming.

Solution 2

From your list, C++ can do:

• function signatures as types
• type polymorphism (but not first-class like in many functional languages)
• immutable data structures (but they require more work)

It can do only very limited forms of:

• higher order functions / closures (basically, without GC most of the more interesting higher-order functional idioms are unusable)
• adhoc data structures (if you mean in the form of light-weight structural types)

You can essentially forget about:

• algebraic data types & pattern matching
• partial function applications (requires implicit closures in general)
• type inference (despite what people call "type inference" in C++ land it's a far shot from what you get with Hindley/Milner a la ML or Haskell)
• tail calls (some compilers can optimise some limited cases of tail self-recursion, but there is no guarantee, and the language is actively hostile to the general case (pointers to the stack, destructors, and all that))
• garbage collection (you can use Boehm's conservative collector, but it's no real substitute and rather unlikely to coexist peacefully with third-party code)

Overall, trying to do anything functional that goes beyond trivialities will be either a major pain in C++ or outright unusable. And even the things that are easy enough often require so much boilerplate and heavy notation that they are not very attractive. (Some C++ aficionados like to claim the opposite, but frankly, most of them seem to have rather limited experience with actual functional programming.)

Solution 3

(Just to add a little to Alice's answer, which is excellent.)

I'm far from a functional programming expert, but the compile-time template metaprogramming language in C++ is often seen as being "functional", albeit with a very arcane syntax. In this language, "functions" become (often recursive) class template instantiations. Partial specialisation serves the purpose of pattern matching, to terminate recursion and so on. So a compile-time factorial might look something like so:

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

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

Of course, this is pretty hideous, but many people (particularly the Boost developers) have done incredibly clever and complex things with just these tools.

It's possibly also worth mentioning the C++11 keyword constexpr, which denotes functions which may be evaluated at compile time. In C++11, constexpr functions are restricted to (basically) just a bare return statement; but the ternary operator and recursion are allowed, so the above compile-time factorial can be restated much more succinctly (and understandably) as:

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

with the added benefit that fact() can now be called at run-time too. Whether this constitutes programming in a functional style is left for the reader to decide :-)

(C++14 looks likely to remove many of the restrictions from constexpr functions, allowing a very large subset of C++ to be called at compile-time)

Comments

[Yakk - Adam Nevraumont]

Yes. C++ is Turing complete, up to hardware. It even has a Turing complete compile time sublanguage. By the turing tar pit, all of the above can be done. Now, do you have a practical problem you need help solving? Because doing it and doing it well are completely different things.

[Trident D'Gao]

No, I don't have a practixal task to solve. I just wanted to understand how far C++ is from principles on which FP is built.

[Nate C-K]

Closures and garbage collection probably ought to be added to the list. Partial applications can be done with closures. (Lots of FP languages don't have partial applications as a first-class feature.)

[Alice]

As stated, almost none of these are intrinsic to functional programming; many of them can be implemented in terms of the others, etc etc

[Nate C-K]

I would say closures ARE intrinsic to functional programming.

[Alice]

Lambda calculus has no closures, and it's the origin of most functional languages. They are syntactical sugar, not fundamental necessities. Let me put it this way: you can do functional programming without them and lose no power.

[Nate C-K]

You lose a lot of power without closures. If you mean "power" in the sense of "a Turing machine can compute anything" then 1) it is not worth discussing, and 2) you do not mean the same thing that most people mean when they say "power". Power in a language means how easy it is to implement things in that language. Not all languages are the same, otherwise we would not care which one we used. Closures and GC are a very powerful combination, one which is difficult to imitate in C++, although I think you make a fair case that it can be done.

[Nate C-K]

Granted you would have to stop using all the standard libraries.

[Alice]

@NateC-K No, that's expressiveness. But furthermore, as indicated by lambda lifting, closures are syntactical sugar; there is no loss of expressiveness, there is only a loss of elegance. And elegance, while beautiful, can be quite cruel, as seen by all the setf's in my LISP code; often we have to trade it for speed or other considerations.

[aoeu256]

What about combinators and adverbs(Python calls these "decorators"). myfunc = cached(myfunc).

[Tristan Brindle]

For partial function application, std::bind probably suffices

[Alice]

I think partial functional specialization is a bit more complex and involved than that, involving some form of memiorization, but I'll add std::bind.

[Alice]

I was going to add things related to this, but while this is certainly functional and indeed turing complete, the fact they are compile time is a little less useful.

[Tristan Brindle]

Minor point: doesn't the capture-by-value in the lambda in memoize() mean that you're creating a disposable copy of cache, and therefore never actually adding anything to the original?

[Alice]

@TristanBrindle Correct. A more explicit and obvious way would be to unroll the lambda into an explicit functor with the map/unordered_map as a data member, and each call to operator () checking it, but using a lambda seemed more interesting.

[Yakk - Adam Nevraumont]

@Alice note that recursive functions require a bit more work for memoization. The recursive function needs to have its recursive call passed into itself. Doing so with type erasure is a bit tricky: typedef std::function< void(Args..., my_own_type) > my_own_type; is hard to express.

[Yakk - Adam Nevraumont]

typedef boost::make_recursive_variant< boost::optional<int>, std::tuple<std::unique_ptr<boost::recursive_variant_>, std::unique_ptr<boost::recursive_variant_>> >::type Tree; for a quick and dirty algebraic Tree. I joined the leaf and empty tree in an optional (I did not have to), but the boost::apply_vistor works much like pattern matching.

[Alice]

@AndreasRossberg We just showed how you can do algebraic data types and pattern matching, partial function applications, and C++ type inference is still type inference. As for Garbage Collection, it's being integrated into the language in C++1y. The features of C++11 drastically reduce the boilerplate needed, and given the STL was heavily based on functional programming, I would call your statements a bit unjust. Especially the comments about requiring a GC; C++ has no garbage due to RAII, so why would we need a collector?

[Alice]

@Yakk Excellent! As I presupposed, those sorts of things can be done with template magic, though I think Concepts will make this drastically easier.

[Trident D'Gao]

@Alice, I think I missed ADT somewhere in your showings (as well as pattern matching), would you point it out for me? ;). As for the collector, I think you need it for closures, otherwise what would be a mechanism of freeing the memory held by an .. instance of a function?

[Alice]

@AndreasRossberg Added, I was working on it! And you do not need closures; they provide no additional power compared to a context bound to a function call, which can be provided with std::bind, OR via C++ lambda's OR, if you are particularly into backwards compatibility, named object instances. Closures are syntactical sugar, and are directly equivalent to function objects (or functors as we call them).

[Alice]

@AndreasRossberg ADT's fully explained, both in simple form (variant) as well as much more complex (GADT, various FP types). Pattern matching provided via TWO libraries, both variant as before and one by the creator of C++. C++ has closures in TWO forms, without a GC, and C++'s explicit dependency tracking via shared_ptr can get the job done as well. All bases accounted for.

[Nate C-K]

C++ closures do not have unlimited extent (because C++ data/objects in general do not), which makes them somewhat different from what we usually mean in FP when we talk about closures. In FP you can close over function arguments and know that they will not go away. Nor will they change, since they're immutable. You can get around this to some extent in C++, but the language doesn't do you any favors.

[Nate C-K]

I'll admit, though, having them does mean you can give the language a much more functional feel.

[Trident D'Gao]

I like this answer too as an example of being stubbornly constructive and promoting positive thinking. With such DIY attitude it shows out the fair price of having FP conveniences that come for free in functional languages. After all you are right there are ways around to get somewhat similar to FP features that in a way do their job to some extent granted you are willing to do some extra typing like having to create, pass and manage the context object to simulate closures. Question remains if all that hassle is worth the shot.

[Trident D'Gao]

@Alice, using visitors to simulate variants is an old well known trick that I used to do a lot in C# before I tried F# and Haskell and found out that they have full fledged support for ADT. This is more of a question of using the right tool for to get the job done. Can you make a hole with a nail instead of a drill? No doubt you can! Would you do that though if you have a luxury to choose? I doubt so. That's the message I think Andress left in his answer. (By the way ADTs are essentially just tuples and variants so there is no such thing as simpler or more advanced ADTs)

[Alice]

@1224 I think GADT's would care to disagree, as they are quite more advanced than mere ADT's. Furthermore, you made no mention of elegance, luxury, or any other measure but possibility. His statement that these things are things you can "forget about" is at odds with reality; they are not merely possible but easy, with the right coding patterns. Furthermore, this idea that the support must be native to be full fledged is silly; if the feature is provided fully by a pattern, then it is "full fledged". boost::variant satisfies this.

[Alice]

@1224 Your question did not mention even for a moment the hassle needed to implement these features. It asked about the possibility. If you wished to ask about elegance, if you wished to ask about the least characters, I suggest you ask such a question in stack overflow's golf section. However, to say that these things are "free" in FP or that they are costly in C++ shows a fundamentally deconstruction and biased attitude. Almost all of these are provided by a library or a fundamental language feature, and represent commonly used idioms that can easily be wrapped or macro'd.

[Alice]

@1224 Furthermore, for many of these, there is absolutely no amount of extra typing needed, or a one time cost if you wish to wrap it in a macro. Anonymous functions, tail recursion, simple type inference, higher order functions, partial function application, compile time type polymorphism, function sigs as types, and even pattern matching can be done with quite similar code length to such things in many FP languages. Pattern matching in particular was amazingly elegant to me, and quite similar to uses in FP. And let us not forget the guiding principle of the STL is FP. So where is the cost?

[Alice]

@NateC-K Copy by value makes them not change, and will make them not go away. To what extent does this differ from your traditional usage? Such values will be bound to the function object and thus have unlimited extent.

[Andreas Rossberg]

@Alice, I'm sorry but more advanced closure-based techniques like, say, combinators are impractical without GC. So are many uses of functional data structures. Sure, you can try to do it, but you will end up fighting the language to the point that it's counter-productive. Moreover, reference counting is rather inefficient. As for visitors, they are a very poor substitute for pattern matching, to put it mildly.

[Trident D'Gao]

@Alice, that elegant pattern matching library, you gave a link to, has a suspicious Otherwise case which can signify that their approach doesn't guarantee the totality or exhaustiveness if you will (which can be achieved with visitors though), without being able to guarantee that all cases from a variant and only those that are in variant are considered it is rendered useless. Now speaking of closures, how does memory management work for objects being closed over? A implicit function object that you've mentioned has to have an implicit destructor, doesn't it? If so, what's happening in it?

[Alice]

@1224 I've no idea what you mean in "rendered useless"; I've used them to great success, as have others. Otherwise provides that guarantee by forcing a static_assert if the type is not in the variant, which provides the totality guarantee you seek; if they are not in the variant, a compile time error occurs. How is this in any way different from the use case you wanted?

[Alice]

@AndreasRossbergn Reference counting need not be more inefficient than a GC, and in many cases can be much more efficient. Furthermore, this is more akin to arena based memory, which is effectively the most efficient form of memory allocation we currently know of. Furthermore, some reference counts are ineffecient, many are not. here is one that uses a nursery to provide highly efficient reference counting, a tactic which combines both RC and GC's advantages.

[Alice]

@AndreasRossberg Welcome to boost::spirit, a library that provides highly complex combinator-parsers to provide parsers which are implemented exclusively as combinators. Is this perhaps "fighting the language", as you say? How about something from the standard library: valarray's members are combinators which take other members, a technique known as expression templates. Expressions templates take expressions and build on them, pass on them, and call them. No GC. Works fine.

[Alice]

@1224 You are asking me about how a built in part of the language is implemented? Due to C++'s "as-if" rule, lambda's can be implemented in any way that provides the same semantics or the same output. My reply is "Implementation defined, and as a programmer I shouldn't care". However, as with any object, when the object goes out of scope, the destructor is called, which frees the memory as per RAII. So what sir, is your question?

[Alice]

@AndreasRossberg As documented in my list, pattern matching in C++ can be quite elegant, and indeed, is quite similar to ML. In fact, looking at the ML and the C++ representation, I find they have a 1 to 1 correspondence. If I could find more "very poor substitute"s of this quality, I would be a lucky person.

[Trident D'Gao]

@Alice, see, in FP the power of pattern matching against a variant comes from the fact that compiler makes you consider every possible case a variant can take not more not less, this is another type safety measure called exhaustiveness, this is how it's guaranteed that when you add a new case to a variant it will be addressed everywhere in your application otherwise your code won't compile, with this said the example of your elegant library uses Otherwise - a default case that doesn't account for new cases it just let you silently ignores them, this is what makes ADTs made this way usless

[Alice]

@1224 First, in no way does that make it useless; it still allows type checking and safe usage of disparate types. Even if it did not allow compile time checking, it would still be far from useless. That's sort of like saying a safety on a gun is useless because you can still fire the gun; anything that decreases the chance of unsafe or hazardous conditions is useful. Don't fall into the nirvana fallacy. ADT's even without compile time checking are useful, and in this example, a simple fix to your problem is Otherwise() throw std::bad_cast().

[Alice]

@1224 Furthermore, with expression templates, even compile time checking could be done. This would be much simpler with Concepts, but using the boost::concept library, idioms as simple and elegant as this one could be used to check at compile time as well (it may indeed be possible even in this library). I know it can be done with boost::mpl. However, I fully disagree with the idea that it is in any way 'useless', even if not done at compile time. It's still preventing errors and insuring safety, and that's still important.

[Nate C-K]

@Alice: I know I've been giving you a bit of a hard time here, but I think you did a nice job of answering the question. C++ closures really just have the same problem as other data structures, which is that if you point to mutable (or freeable) data then you have to be wary that what you're referencing is still valid. This can be addressed by using appropriate data structures, or just by being careful.

[Nate C-K]

@1224: I'm gonna have to agree with Alice on pattern matching: some is better than none. Anyway, some FP languages (e.g. Erlang) don't check for exhaustive matches. Appropriate development methodology should include unit tests, which should usually catch inexhaustive match bugs.

[Alice]

@NateC-K Those problems are mostly addressed with the shared_ptr construct I detailed in the garbage collection section, which makes such things quite easy in many cases. It's true a GC makes things easier, but it also comes at a high cost, too high for many of the applications. And thank you, I try my best to be informative and to provide the wealth of idioms I know.

[Andreas Rossberg]

@Alice, no need to evangelise, I'm well aware of these. Just to be clear, boost::spirit is not built with closures, and probably took a lot of code and effort to build. And no, reference counting is almost never a match for a generational GC -- especially not when you use functional programming techniques, which tend to allocate plenty of short-lived data. Similar caveats apply to many of your other arguments. I have tried to use some of these techniques in real code, and it usually turned out to be a terrible experience. Have you?

[Alice]

@AndreasRossberg As indicated in the links I made, reference counting with a nursery is quite effective. I'm not evangelising; your statements are simply untrue and indicative of, in your own words, "limited experience". I've used many of these, both in production code and in my spare time. And just to be clear, boost::spirit is a library of highly complex combinators; I said nothing about them being closures. Furthermore, you are moving goal posts; it is simply intellectually dishonest to say one can "forget about" techniques that I've provided ample evidence for being practical.

[Andreas Rossberg]

@Alice, I mentioned combinators as an example of something that's impractical to do with closures when you don't have GC, so boost::spirit is no counter-example. I don't think you truly want to get into an experience contest with me, neither wrt C++ nor wrt functional programming. You're entitled to your own opinion, of course, but you will have a hard time finding many knowledgeable functional programmers who would agree with you.

[Alice]

@AndreasRossberg You have made specific statements. I have provided counters to those statements, with code examples when feasible. You have countered with abstract and vague refutations, and ignored my sources in favor of blanket statements asserting things my links prove are not true. Even so, I have attempted to accommodate this goal post moving, because programmers may see this page, and wish to use these techniques, and I believe they may benefit from being shown they are possible. You may indeed have more experience than I, sir, but I do not see that wisdom in your demeaning words.

[Alice]

@AndreasRossberg Furthermore, boost::spirit is a combinator library, closures are readily usable with minimal effort via shared_ptr's, and finally, as shown in my edited example, closures and combinators (whether template based or inheritance based) can co-exist quite well. And while the combinators provided are quite simplistic and in need of checking, typedefs, and all sorts of other ornamentation, they serve to demonstrate the point. I do not find your assertions that these things are impractical compelling, especially since the subject of this question was about possibilities, not elegance

[Andreas Rossberg]

@Alice, I didn't do any such thing, please re-read my replies. I think the main miscommunication here is that you seem to be equating "supporting a feature" with "providing a workaround for the absence of a feature", which is not very helpful (and neither is your tone).

[Alice]

@AndreasRossberg Please re-read your assertion of authority via experience as well as your demeaning words towards "some" to "most" C++ programmers in your quite underwhelming answer before you say anything about my tone. Furthermore, there is no miscommunication; this question is about possibilities. "Are the following things considered intrinsic to FP possible in C++?" Not are they elegant. Not are they built in primitives. Not are they "workarounds". He explicitly asked about possibilities, and you have asserted things are impossible which I have spent considerable time proving they are not

[Alice]

@AndreasRossberg and as a note, many of the idioms now embedded in the standard library started exactly this way; by people finding "work arounds" as you call them, making libraries that make them easy to use, and then proposing their inclusion. The STL, one of the most well crafted libraries of any language I've seen, was one such library, proposing a fusion of generic programming, functional programming, and object oriented programming with strict bounds on performance. If you can implement the feature in terms of built in features, the feature is not absent.

[Alice]

@AlekseyBykov Given the actually accepted answer is worthless, do you want me to update this to talk about the drastic improvements in the language that make functional programming even easier in C++14, given I use them every day now, or are you going to keep accepting an answer that has no actual, uh, answers?

[aoeu256]

Same expressiveness of Lisp or Haskell... Lisp has homoiconic macros, embedable DSLs, and interactive development, and Haskell's syntax is much much nicer than C++ for all these things.

[Alice]

>embeddable DSL's As does C++; many of the libraries I listed are DSL's, but allow me to point you towards Spirit, an eDSL for parsing in C++: boost.org/doc/libs/1_73_0/libs/spirit/doc/html/index.html