Reinventing the Wheel, Part I: String Reverse Algorithm

A string reverse algorithm takes a string of characters, and produces a string with the characters in reverse order.

In doing this, we could

• use a more high-level C++ approach,

std::string reverse(const std::string &str);

// ...

std::string reversed = reverse("uncategorized");
printf(reversed);                                 // dezirogetacnu

where the function returns a reversed copy of the original string. (Btw, to reverse a std::string, use the std::reverse algorithm, see bottom of this post.)

Alternatively, we can

• write a C-styled function, using a "raw" pointer and then modify the string, in-place:

void reverseInPlace(char *str);

// ...

char s[] = "november";
reverseInPlace(s);
printf(s);                                // rebmevon

Since we are going for minimal memory footprint and optimal performance, we will pursue the latter approach.

Lambdas in C++0x, Part II

Let's recall the syntax of a lambda expression, from the first part of this post:

  [C](P) M -> R { body }(Q)

  C = capture specification
  P = parameter specification
  M = mutable specification
  R = return type specification
  Q = actual call parameters

Lambda expressions are locally defined functions, also known as anonymous functions. A minimal example could look something like this:

int main()
{
    auto f = []() { std::cout << "hello"; };
    f();
    return 0;
}

The lambda can also be invoked as it is defined, on-the-fly:

[]() { std::cout << "hello"; }();

Here is a lambda that takes an int as argument:

auto fn = [](int x) { std::cout << "x = " << x << "\n"; };
fn(123);

Side note: I tend to use the terms parameter and argument more or less interchangeably. To make things clear, we should, however, make a distinction between the two:

• A parameter is a variable declared in the prototype or declaration of a function.
• The argument is the value that is actually passed to the function.

A return value can be specified, using the trailing return type specification (→ R):

auto fn = [](int x) -> int { return x + 1; };
int n = fn(1);
std::cout << "->" << n << "\n";

The auto keyword saves us some work when the compiler is able to infer the type of an expression automatically. Alternatively, we could write:

std::tr1::function<int(int)> fn = [](int x) -> int { return x + 1; };

In this post, I will continue to examine the capture specification and mutable keyword.

The Meaning and Usefulness of Closures

In the previous post, I talked about the Fixed Point Combinator in λ-Calculus, and mentioned that combinator is another word for a closed lambda term, i.e., an expression with no free variables:

λx.x, λxy.x, λxy.y, etc.

Take for example the term λxy.y, which is really shorthand for λx.λy.y:

FV(λx.λy.y)   =   FV(λy.y) − {x}   =   FV(y) − {y} − {x}   =   {y} − {y} − {x}   =   Ø.

The opposite of a combinator – any expression that uses free variables, is called a closure. Even though the meaning of the term is slightly different in different contexts, the idea is basically the same:

Examining the term λx.(f x), we have the free variables FV(λx.f x) …

= FV(f x) − {x} = FV(f) ∪ FV(x) − {x} = {f} ∪ {x} − {x} = {f, x} − {x}
= {f}.

In Haskell, the definition for a function, func:

func f = \x -> f x

… uses the variable f, bound outside of the abstraction. It is therefore a closure.

The Pattern of Recursion and Fixed Point Combinators

Recursion is an interesting, and important computation tool that enables us to formulate patterns of self-similarity and express infinity, using a finite set of elements. There is a strong relation between recursion and the principle of induction in mathematics. Imperative programming languages usually allow recursion in a program to take place by letting us define a function that calls itself. Here is a simple recursive function in C++:

#include <iostream.h>

void count(int n)
{
    std::cout << "Counting: " << n << "\n";
    if (n < 5) {
        count(n+1);
    }
}

int main(int argc, char **argv)
{
    count(1);
    return 0;
}

Run this example from codepad:
http://codepad.org/YmxQcTIX

In functional programming, recursion has a much more central position. Purely functional languages do not define any looping constructs, but instead rely entirely on recursion to achieve iterative algorithms. Many data types are defined recursively. In Haskell, recursion even allows us to define (conceptually) infinite data structures:

n = 5 : n
take 3 n                -- [5, 5, 5]

Codepad: http://codepad.org/sRbFkSH5

Here, we take the first three elements from an infinite list of fives. The list n is defined as a single element, 5, followed by a list – itself.

n is a 5, followed by n, which is a 5 followed by n, which is a 5 followed …

Lambdas in C++0x, Part I

The new C++0x standard adds support for anonymous functions; so called lambda expressions. The concept of anonymous, or locally defined functions plays a central role in functional programming and has its origin in the Lambda Calculus (λ-Calculus); a theory formulated by Alonzo Church in 1936 (yes, that was before FORTRAN). The basic idea here is to treat functions as first class objects – functions can be stored in variables, passed as arguments, and be used as return values etc.

Lambda expressions are similar to functors (function objects), but with the added advantage of now being an integral part of the language. We can think of them as syntactic sugar for a functor. Just like function objects, lambdas are type-safe and can maintain state.

Using lambda expressions

The lambda term λx.3 represents the anonymous function x → 3, i.e., a function which takes a single input, x and (always) returns 3.

Using the new C++0x lambda syntax, this can be expressed as:

[](int x) { return 3; }

…where the initial square brackets ( [ ] ) are called the lambda introducer and tells the compiler that a lambda expression follows. Since x is irrelevant here, we may simply omit the parameter specification in this case. This leaves us with a very basic function that returns the value 3:

[] { return 3; }

Type Inference in C++: The Return of Auto

With the new C++ standard (C++0x), the auto keyword has returned to the language, like a phoenix rising from the ashes – with new and completely different meaning.

With this new auto, we can ask the compiler to deduce the type of a declared variable from the expression used to initialize it. This feature is known as type inference, and is found in many functional programming languages. Type inference (or type deduction) introduces some of the advantages of dynamic type systems, without incurring the performance penalty and various other negative side-effects associated with relaxed type safety, such as increased risk of run time failure.

A very basic, and not very useful example could look something like:

int x = 1;
auto y = x + 1;

The important thing to note here is that auto is a keyword and not a type. This is to say that, unlike in a dynamically typed language, we can’t assign a value of a different type once the variable has been declared. The type of y (int) must be known at compile time, we just leave to the compiler to figure out what it is.