Magic

Projects (especially, B.Tech Projects) are very fascinating, in that they let you do a lot of things just for the sake of it. For example, at one point in my code, I wanted to iterate through all the 4-element subsets of a given N-element set. The most straightforward way would be to actually write 4 nested loops. A bit “scalable” approach would probably employ proper recursion.

Or.. we could do some goto magic!

int i[4];
int m=0;
 nest:
for(i[m]=(m?i[m-1]+1:0);i[m]<10;i[m]++){
    if(m<3) {m++; goto nest;}

    cout<<i[0]<<i[1]<<i[2]<<i[3]<<endl;

  unnest:
    ;
  }
  if(m>0) {m--;  goto unnest;}

The above C++ code will iterate through (and print) all 4-subsets of {0,1,..,9}.

How does it work? To understand that, one needs to appreciate a very simplistic view of compilation, namely that it is just a highly complex regexp find-replace operation. (Of course, this is oversimplifying things; since so many intermediate steps and much optimization happens; but we’ll ignore that, because all that does not define (or change) the external behavior of the program)

In other words, processors have no real sense of understanding about what the program syntax means. Code is just executed as it comes along; and the code can be doing absolutely anything. And this is precisely what the above snippet makes use of. The nest and goto-nest is a small nesting loop that blindly steps our program flow 4 levels deep into for-loops. The processor has simply no idea that it is seeing the same for-statement again and again! It simply executes it, which is to say it nests up another level each time.

And then, the unnest-loop is needed to formally exit all the nested levels, so that the program can continue execution ahead. Again, the processor is given the illusion that it is encountering four quite distinct ‘unnesting’ operations.

Word of caution: goto is considered hazardous, and the above snippet indicates why: simply because then the program flow takes strange routes, difficult to keep track of. But the above also suggests that if somehow you can manage the ‘proofreading’, goto can do some beautiful things for you.

Advertisements

new Category(“BTP”);

Yes, I know.. that statement won’t compile. But honestly, I couldn’t think of any good name for the pointer that should have been.

As an aside, some of my programming sessions in the past have been fruitless because I simply didn’t like the variable names, or their length (because the code won’t line up otherwise). A particularly nasty one is that “server” and “client” are of the same length; but “peer” just disrupts everything. I could call it “peerer”, if I wanted. But then, the English embedded in the C statements is horrible: “kill(peerer);” almost sounds like a fundamentally barbarian act.

But back to the main: This is the new category: my B.Tech project. I feel that any ‘sensibly chosen’ project should teach us many things along the way, and that’ll happen on a wide range, from something concrete (like a new software or language) to abstract (like a general heuristic or thumb-rule). Well, my BTP is a very sensible research problem, and is set amidst a very sensible team. For now, at least. And I think that sharing the notable ideas as one comes across them along the way, would be a great way for research enthusiasts to know what each other is doing.

Of course, I don’t plan to bore the readers by posting about each and every detail of my project, because that will essentially amount to making the readers of this category recreate my results from scratch. Rather, I’ll abstract out the noteworthy things I discover, and present them with some context, for the reader to appreciate them.

For now, let me just give a brief background about the problem: It started with a single frequency estimation problem as my summer project. And now as a BTP, it has been extended in the most natural way: estimate more frequencies. I have been working on it for about two weeks now, and I’ve already started writing my first algorithms, which are just natural extensions from lower-order results that I had arrived at during the summer. Nothing interesting yet, except that this doesn’t beat logic, and that’s a good thing.

Again, as an aside: In a place where logic doesn’t seem to be applied to decide our core syllabus, today I was looking for logic in the order in which the bathroom buttons in my new wing are arranged, with respect to the lights they control. What would be funnier, is if some faculty/authority reads this, and decides to fix the buttons before the syllabus.