Thursday, February 9, 2012

Functional Languages and Call-By-Value, Part 1

A whole lot of work goes into avoiding unnecessary copies in C++. Much of this responsibility lies in the programmer with manual optimizations such as passing large objects by pointer or by reference rather than by value. This concern is pervasive in the language, from the choice of increment/decrement operators to the implementation of constructors. Many compiler optimizations are also target copying such as the return value optimization (RVO) and, more recently, the move semantics in C++11. The reasoning behind the emphasis on copying seems intuitive enough: pass-by-value of any data larger than a primitive type (i.e., larger than a pointer) gets too expensive especially if the data in question is in a temporary which must be destroyed anyway. C++'s machinery to work-around this inefficiency isn't representative of imperative and object-oriented languages. For example, Java makes references the default way for manipulating objects even though the primitive calling semantics is pass-by-value. However, in functional programming, copying is seldom the overriding emphasis. Why isn't copy as big of a deal in functional languages? For the sake of argument, I will take ML as the canonical functional language. Lazy evaluation in languages such as Haskell adds another layer of complexity which I won't address here.

The key problem in C++ (which is not unique to C++) is that copying remains pervasive despite its largely imperative nature. The default pass-by-value semantics of function calls means that every time a function is called, all its arguments must be evaluated and the result of this evaluation (the value) must be passed to the callee. For objects, this means making a copy. If the argument is a large object such as a long vector, this may be expensive. Consider the following code:

vector g() { return vector(); }
vector identity(vector v) { return v; }

Furthermore, if the argument were a function call itself (i.e. identity(g()) such that g() yields an object), then the program will construct two potentially identical objects where one will be destroyed without any further use. But this is where things get complicated. The temporary object g() is not necessarily identical to the result of copy construction (v) needed for the function call identity. The copy constructor may rely on some additional state. Thus, the compiler cannot in general reuse the temporary object g() due to the impact of potential state on default and copy construction.

If this isn't dizzying enough, when identity returns, it will have to call the copy constructor again because that copy v is going to be destroyed since we are leaving the scope of identity, which delimits the lifetime of v. That adds up to two copy constructions for an identity function call alone.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.