A Turkey by any other name…

Recently we were discussing how the bird Turkey seems to be named after other countries, in Hebrew it’s an Indian chicken, in Portuguese it’s named after Peru and in Arabic it’s Ethiopian.  The fact that turkeys actually originate in North America didn’t seem to be taken into consideration (except by the Russians).

When I stumbled across the List of names for the Wild Turkey Wikipedia page I decided this called for a map.

The longest path I found involved 6 countries (5 links):

Bulgaria → Egypt → Greece → France → India → Peru

Who has access to your private parts?

A famous quip says that C++ is the language in which friends have access to your private parts.

But is it only friends?

When writing an RAII object I was feeling a bit lazy (which as we know is a virtue) and was surprised to discover that a local class (a class defined in a function body) has access to its enclosing class’s private members.

class outer {
    int private_;
public:
    outer() : private_(0) {}

    void print() {   cout << private_ << endl; }

    void foo()
    {
        class local { // RAII object
            outer* outer_;
        public:
            local(outer* p)
                : outer_(p)
            {
                outer_->private_++;
            }

            ~local() { outer_->private_--; }
        };

        print(); // -> 0

        {// Scope for RAII object 

            local in(this);
            print(); // -> 1
        }

        print(); // -> 0
    }
};

A quick look through the standard didn’t show where such behaviour is specified but it compiled with all the compilers I threw it at^[1].

When I revealed this discovery to my cow-orkers they responded with an empathic “DUH!”  Oh well there  goes my C++ geek-cred  :o(

Allowing local classes access to private members makes a lot of sense on the language design front, after all if you can create a class in a method you should be able to do anything the method can do.  I just never thought of it before and apparently I’m not the only one.  When looking at C++11′s standard (well the final draft actually) I found the following in section 11 (Member access control):

A member of a class can also access all the names to which the class has access. A local class of a member function may access the same names that the member function itself may access.

Since this sentence does not appear in the original ’98 standard I can only assume that greater minds than mine had also missed this point, at least at first.

Having classes which can access your private parts can be very useful, they can be used for temporarily changing state (as in the RAII class above) or they can be used as parameters to STL algorithms^[2]. The problem is that having a local class breaks the flow of the function and a nested class must be defined in the header so that something which is an implementation detail becomes globally visible.

But wait, the section in the standard had a footnote. “Access permissions are thus transitive and cumulative to nested and local classes.”

Transitive, that implies more than one level, this gave me an idea for a new(?) C++ pattern. I don’t know if I’m the first who thought of it and I doubt it’s very useful but here goes, I’m very proud to introduce the nested² pattern.

For every class we can create a backdoor class that allows creation of quasi-friend classes. Then if the need arises we can add these quasi-friend classes in the .cpp file.

// .h file
class troy {
    class wooden_horse;
    int private_;
public:
    troy();
    void foo();
};

// .cpp file
class troy::wooden_horse {
public:
    struct odysseus {
        troy* t_;
        odysseus(troy* p) : t_(p)
        {
            t_->private_++;
        }

        ~odysseus()
        {
            t_->private_--;
        }
    };

    // Add Greek warriors as needed
};

troy::troy()
    : private_(41)
{
}

void troy::foo()
{
    wooden_horse::odysseus odysseus(this);
    cout << private_ << endl;
}

By making the backdoor class private we can be sure that the quasi-friend classes won’t be abused since nobody but our class will be able to create an object of this type.

---

Edit: Ever since I posted this I couldn’t sleep at night, I knew I would never forgive myself if I don’t to this:

:%s/troy/french_castle/g
:%s/wooden_horse/large_wooden_badger/g
:%s/odysseus/bedemir/g
:%s/Greek warriors/Knights of the round table/g
:wq

---

[1] VC8, VC10, gcc, clang and Comeu (yes I am a bit obsessive, why do you ask?) ↩

[2] Although this is less compelling since the introduction of lambda expressions in C++11. On second thought, since lambda functions are implemented as unnameable classes perhaps this is the reason for the change in the standard, to allow lambda functions the same access rights as the method that defined them. ↩

Did you pack that yourself?

A while ago I answered a stackoverflow question related to C++11′s variadic templates. I gave an example of one of the simplest variadic template functions imaginable:

int maximum(int n)
{
    return n;
}

template<typename... Args>
int maximum(int n, Args... rest)
{
    return max(n, maximum(rest...));
}

A commenter asked if the ellipsis after Args and rest have any meaning or are they just syntactic salt?

To get the jargon straight Args is the variadic template pattern, rest is the variadic parameter pack and the act of turning a template pack into parameters is called pack expansion.

This is a good question, the trailing ellipsis are used to expand the template parameter pack but since the only thing^[1] you can do with a parameter pack (or pattern) is expand it, why do we need the extra syntax?

I didn’t know the answer at first but after a bit of thought I believe this is the rationale:

When you unpack a template pack the compiler conceptually writes out the expanded pack, so if rest is { -2, 3, -4 } the compiler turns maximum(rest...); into maximum(-2, 3, -4);  but you can do more, if you want to find the maximum of the absolute value of the numbers you could write maximum(abs(rest)...) (note the ellipsis come after the close paren) which would expand to maximum(abs(-2), abs(3), abs(-4)). The location of the ellipsis matters that’s why you have to write it explicitly.

This is also true with the template patterns.

template <typename... Pack>
struct united : std::tuple<Pack...> {
};

united<const char*, int, bool> we_stand;
// we_stand is equivalent to being of type:
// struct united_XYZ : std::tuple<const char*, int, bool> {};

std::tuple<const char*, int, bool> *ok = &we_stand;
std::tuple<bool> *error = &we_stand; 

template <typename... Pack>
struct divided : std::tuple<Pack>... {
};

divided<const char*, int, bool> we_fall;
// we_fall is equivalent to being of type:
// struct divided_XYZ : std::tuple<const char*>, std::tuple<int>, std::tuple<bool> {};

std::tuple<bool>*ok =&we_fall;
std::tuple<const char*,int,bool>*error =&we_fall;

This post scheduled to appear on my 10th wedding anniversary

---

[1] And call sizeof… on it but that’s just nitpicking. ↩

Give me some credit!

I’ve been trying to keep to a minimum of one post a month but am a bit short of ideas. In my desperation I’ll take some liberties with the mandate of this blog and talk about something pertaining to payment (even though my previous post regarding financial issues wasn’t such a big hit.)

This must have been around 15 years ago, before I had an international credit card, I wanted to pay for some small purchase with my credit card when the cashier asked to see a photo ID (this is unusual in this neck of the woods.)  I pulled out my ID and she said “The credit card says Motti Lanzkron but the ID says Mordechai Lanzkron.”  I told her, what every native Israeli knows, (she was an immigrant) that Motti is short for Mordechai just as Bill is short for William, this took some convincing but she conceded the point. She then looked at the back of the credit card “this isn’t signed, you need to sign the back.”  I told her it was signed although a bit faded but she insisted so I re-signed the back (thinking inwardly how pointless this was.)

At this point the cashier looked at the back of the credit card and at the signed receipt and said “the signatures aren’t the same.” I was sure she was joking but that was not the case. After pointing out that she had just witnessed me pen both signatures I finally managed to finalize the transaction.

The worst acronym ever: SCARY iterators

A couple of years ago there was a question in stackoverflow about the “Best IT/Programming/Technology related Acronym”. Tongue in cheek  I suggested I18N  (which is I followed by 18 letters followed by N).

Yesterday I discovered the worst acronym when reading about what’s new in VC11, apparently Visual C++ now supports SCARY iterators. The link explaining SCARY iterators had this to say:

N2911 explains that the acronym SCARY “describes assignments and initializations that are Seemingly erroneous (Constrained by conflicting generic parameters), but Actually work with the Right implementation (unconstrained bY the conflict due to minimized dependencies).”

On the reddit  thread feembly said the reason was probably because “SECBCGPBAWWTRIUBTCDTMD just didn’t have the same ring” which I took as proof that he isn’t Welsh. If I remember correctly my grandmother is from a small town near Secbcgpbawwtriubtcdtmd.

On the Complexities of Preparing Dinner

During a coffee break I mentioned that “even though the kids prefer schnitzel I’d rather prepare baked chicken”

When asked why I explained that “Chicken is O(1) and schnitzel is O(N)“.

This is a case in which the joy of using jargon colloquially overrides strict correctness. Obviously making chicken isn’t O(1) even if you do  have an infinitely large oven.

Image stolen from gas-grill-review.com

Then again the complexity of finding an element in an unsorted sequence isn’t really O(N) either, it’s O(N * Max(Cmp(a, b))). Comparing objects can often be considered O(1)  (e.g. 32 bit integers) but if you want to compare books by the number of the times the letter e show up in them, well then, comparing War and Peace to Les Misérables is far from constant speed (you could use A Void as the null book</aside>)

The real^[1] reasons I prefer making chicken to schnitzel are twofold.

1. The constants are much bigger for schnitzel
2. Schnitzel making is synchronous while baking chicken is asynchronous

And don’t get me started about the space dirty dishes complexity.

---

1. Of course how healthy the food is doesn’t count as a consideration, we are geeks here after all. ↩

Formal parameters and the arguments object in JavaScript

Say you’re writing a function which takes a function name as an argument and passes the rest of its arguments to the named function. Your unit test for such a function may look like this:

assertEquals('add', 5, calculate('add', 3, 2));
assertEquals('mul', 6, calculate('mul', 3, 2));

We would like to splice off the first element and pass the rest to another function but since arguments isn’t a real Array it doesn’t support the splice method. Never mind, that’s easily treated by calling splice with arguments as this.

function calculate(operation)
{
    // Remove `operation' from arguments leaving only `a' and `b'
    Array.prototype.splice.call(arguments, 0, 1);
    var funcs = {
        add: function(a, b) { return a + b; },
        mul: function(a, b) { return a * b; }
    }
    return funcs[operation].apply(this, arguments);
}

So why are we getting an Uncaught TypeError: Cannot call method ‘apply’ of undefined? Looking at things in Chrome’s debugger everything looks OK. operation is “add” and funcs[operation] is a function.

It dawned on me that the debugger is lying (Firebug and IE’s debugger don’t have this problem), splice removed the first parameter from arguments and now the value of operation is 3. How come 3? Well operation was the first parameter and the first element in arguments is now 3, it’s obvious really(?).

Now I picked up JavaScript on my own (as I assume many do) so I’m no expert and this took me by surprise (it’s probably not trivial even for real JavaScript developers if Chrome’s debugger has this defect).

After meditating about the facts it makes sense that formal parameters and the elements in the arguments object are aliases so that if you do arguments[2]++ the formal parameter  ‘b’ changes too but this behaviour means that that these references are more like Perl’s much vilified symbolic references than most languages’ references. This means that using a formal parameter in JavaScript is semantically equivalent to indexing into the arguments object, writing  operation in (this example) is just syntactic sugar for arguments[0]. If you want to remove an argument from the arguments object and still used the named parameter you must first cache the value in a separate variable.

Here’s the fixed version of calculate:

function calculate(operation)
{
     var op = operation; // Save value of `operation'
    // Remove `operation' from arguments leaving only `a' and `b'
    Array.prototype.splice.call(arguments, 0, 1);
    var funcs = {
        add: function(a, b) { return a + b; },
        mul: function(a, b) { return a * b; }
    }
    return funcs[op].apply(this, arguments);
}

---

Edit: as strager said in the reddit thread:

Takeaway:
Do not modify the arguments object.
Ever.

Now that I’m older and slightly less ignorant I think this would be a better solution:

function calculate(operation)
{
    var funcs = {
        add: function(a, b) { return a + b; },
        mul: function(a, b) { return a * b; }
    }
    return funcs[operation].apply(this,
                       Array.prototype.slice.call(arguments, 1));
}

---

Edit January 2012: The Chrome defect has been fixed (verified on Chrome 16).

timeoutSort

A recent post in 4chan introduced Sleep Sort. The reddit thread that ensued ported it to many languages (from the original bash) but I didn’t see anyone port it to JavaScript yet. So without further ado here’s my port to JavaScript called timeoutSort

Array.prototype.timeoutSort = function(f) {
    this.forEach(function(n) {
        setTimeout(function() {
            f(n)
        }, 5*n)
    })
}

It can be used thus:

[1,9,8,7,6,5,4,3,2,0].timeoutSort(alert)

Or thus:

[1,6,4,3,5,2,0].timeoutSort(function(n){ document.write(n+'<br>')})

Share and enjoy

Pita Burger

Today is Yom Ha’atzmaut, Israel’s independence day.

In this day it’s traditional to have a cook-out during which many  pitas are spread with hummus and stuffed with meat, salad and chips.

During last year’s celebrations I made a great discovery which will change the course of human history! A half defrosted hamburger split down the middle on the grill presenting a void just waiting to be filled.

So without further ado and in keeping with this blog’s mandate of dealing with things that begin with the letter P, I’m proud to introduce the Pita-Burger!

The world's first(?) Pita-Burger

This invention allows saving that resource which is always most scarce during barbecues, stomach real-estate, by leaving the pita out of the picture.

I was going to patent this stroke of genius and retire on my millions but unfortunately a friend of mine (NKA The Dude) pointed out that there was prior art.

Meaningless Benchmark Redux

A year ago I wrote a post called Yet Another Meaningless JavaScript Benchmark, in which I examined how different browsers behave in regards to an atypical JavaScript program (hence the meaningless part of the title). The last thing I expected was for someone to actually use this as  part of a benchmark suite.

Since I published the post both IE and Firefox have released a new major version (and Chrome has released 7 major versions, but who’s counting?) so I guess now is as good a time as any to see how the new versions fare for the same test. Just re-running the test is rather boring so I’ve added two additional sections to this post in which I experiment with some of HTML5′s features.

1. Using the canvas tag to create a visualization of a Collatz orbit _{[Jump there]}
2. Use Web Worker threads in order to solve the same problem _{[Jump there]}

I should note that I’m not a web developer, I’m just playing around with HTML5 (and blogging) so if you are a web developer some of this may seem obvious. If you’re not a web developer you probably don’t much care about HTML5 so I’m not really sure who the audience of this post is…

All the code is available to play with right here.

Rematch!

When I originally run this test with IE8 Firefox 3.5 and Chrome 3 (yes 3) I got the following results:

Re-running the same test now gives very different results. Again I’m using the latest released versions of the browsers, IE9, Firefox 4 and Chrome 10 (on the same computer).

The first thing we can see is that the playing field has been levelled, IE is no longer pulling the Y axis into the triple digits, in fact it’s planted firmly in the single digits. Chrome is unique in taking more time to perform the optimized version in more time than it did 7 versions ago (I should reiterate that this benchmark is highly specialized which means it’s not worth optimizing for and Chrome may still out perform the other browsers in real-life scenarios).

Well now we’ve got that behind us, lets look at some HTML5 features

Canvas

The canvas element gives us the opportunity to visualize what a Collatz Orbit looks like, here’s the orbit for 87:

The black dot is the starting point, odd numbers go to 3*n+1 (in red) and even numbers go to n/2 (in green), the blue dot marks where the orbit has reached 1.

The code for drawing the orbit is available here, I won’t go into it since it’s pretty trivial. All I want to add on the subject is that I calculate the whole orbit in advance so that I know how big the canvas is going to be, since it can get to be quite big a lot of the drawing may take place off screen. The orbit is drawn step by step in order to give a feeling on what’s going on (you can configure the how fast it runs).

Worker Threads

Another feature of HTML5 is Web Workers, this allows breaking out of JavaScript’s natural single threaded nature and perform calculations in separate threads. In order to prevent data races the worker threads can’t access the browser’s DOM which slightly limits their usage.

Thankfully number crunching doesn’t require access to the DOM and I had a chance to implement Collatz yet again (this is turning into a real code kata, especially counting all the different C++ implementations I wrote).

Here I launch a number of threads, each takes a sparse view of the numbers in the range. I keep track of the threads that have reported the maximal orbit for their slice and when all threads have answered I output the answer.

function parallel(limit, threads) {
    var max = [0, 0];
    var live_threads = threads;

    for (var i = 0; i < threads; ++i) {
        var worker = new Worker("euler14.js"); // Create thread object
        worker.addEventListener('message', function (e) { // This function is how the thread reports back
            var d = e.data;
            if (d.len > max[0]) {
                max = [d.len, d.num];
            }

            if (--live_threads == 0) // Done, output the result
                report("Parallel ("+ threads + ")", begin, max[1], max[0]);
        }, false);

        // Launch the thread
        worker.postMessage({ 'max': limit, 'step': threads, 'offset': i });
    }
}

The thread receives all the information it needs for the computation, when it’s done it reports its findings to the launcher (via self.postMessage) and  commits suicide.

self.addEventListener('message', function (e) {
    var limit = e.data.max;
    var add = e.data.offset;
    var step = e.data.step;
    var max = [0, 0];

    for (var i = 1; i + add < limit; i += step) {
        var length = orbit(i + add);
        if (length > max[0])
            max = [length, i + add];
    }

    self.postMessage({ 'num': max[1], 'len': max[0], 'offset': e.data.offset });
    self.close(); // Goodbye cruel wrold
}, false);

IE9 does not support Web Workers and the numbers I got when running Firefox and Chrome on this varied greatly between runs but here are the best times they achieved on my ageing dual core laptop.