Lambda the Ultimate

I got to thinking that it would be cool if using a language's builtin tools you could create its array type -- without using its array type. Most language's I've seen have some builtin concept of an array or list. And although some languages give a 'definition' of what a list is -- that defining code won't actually run through the interpreter.

I came up with the following C++ implementation that manages to implement an array type without actually using arrays. Before you cry that it depends on the class layout which isn't guarunteed -- it is when a class is a POD, and in this case the element is public so it is, and even if it wasn't, it's a defacto standard that things are layed out this way and projects like boost.python depend on it, and the point of the example is to show that a language can do it (even if the language is "C++ with small tweak").

template<class T, int n>
class Array : public Array<T, n-1>
{
public:
    T& operator[](int i);
    T tail;
};

template<class T, int n>
T& Array<T, n>::operator[](int i)
{
    // Should be able to just use line below
    // but some compilers (GCC 3.4) are stupid
    // return *(&(Array<T, 1>::mem) + i);

    int& x = Array<T, 1>::tail;
    return *(&x + i);
} 

int main(int argc, char *argv[])
{
    Array<int, 5> x;

    cout << sizeof(Array<int, 5>) << endl; // 20 as expected

    x[0] = 9;
    x[1] = 8;
    x[2] = 4;
    x[3] = 2;
    x[4] = 5;

    // Prints correctly
    cout << x[0] << x[1] << x[2] << x[3] << x[4] << endl;

    return 0;
} 

How often do you see recursive inheritance? *grin*

From http://rubyforge.org/forum/forum.php?forum_id=8551:

"APP Design, Inc. released a pre-alpha code set for the Prelude project. The goal is to enable Ruby programmers to use higher-order functions, monads, infinite lists, and other Haskell features. The project is released under GPL, community participation is more than welcome."