Visualizing RegEx Backtracking

Every developer learning Regular Expressions is foxed when he first encounters the feature called backtracking. Once we’ve learned the basic patterns and done a few small matches, we image a regular expression to be a one-way train, if you will, which marches on with resolve and weeds out what it was asked to look for.

Only if.

The recursive algorithms inside a RegEx engine also make it “re-consider” its choices when a match fails, and the greedy quantifiers “give up” space. In a way, then, the engine goes back, or backtracks. If you’re not careful, you can blow up your processor.

I’m writing this post because I had severe problems finding a visualization of this backtracking process, and why it might lead to  a recursive hell. Almost an hour of searching threw up a wonderful post, so I decided to include the link and screenshot on my website to preserve it.

For the tutorial, go here.

The screenshot of page content is below. I sincerely hope it helps someone!

regex-backtracking-problem

 

Which is the Best PHP Framework?

How I wish I had a dollar for every time this question is asked on programming forums! Frameworks are a highly personal choice; while some worship raw execution speed and are drawn to the likes of Phalcon, others refuse to get over “good old days” and still insist on CodeIgniter, or some variant of it. And then we have yii and Laravel, which claim to be on the bleeding edge of innovation, while Zend likes to throw its “official” weight around. Not to mention FuelPHP, Symfony, make-your-own-framework, or even putting good old PHP spaghetti to work.

It’s not just that there are too many choices, but also that there exists no objective criterion to decide on a framework. If your employer already uses a framework then the die is cast, but when it comes to personal projects, the dilemma is non-trivial.

I’m writing this because I’ve been through my fair share of mental anguish, and that I’ve managed to come out of it. What decided for me was the insight that as a developer, I’m going to be doing two kinds of projects: very, very small personal projects where I make something quick for myself or for friends; and something that’s large enough to demand much heavy-lifting.

And so, I’ve decided on:

  1. Small projects: Slim Framework. It’s a 600+ KB micro-framework with a very clean design.
  2. Large projects: Laravel. A framework that brings magic to PHP development (seriously!).

Can you copy my decision and make it work for you? Perhaps. But a lot goes into making a choice. You need to be at least an intermediate Web developer to understand the various jargons and .htaccess settings, and you need to be willing to waste a few hours trying a few things.

I wish you all the best!

 

 

Could you double-check the grammar, please?

It’s indeed unfair to ask someone not versed in a particular skill-set to deliver something flawless. A software developer, for instance, shouldn’t be chided for overlooking a gross mistake the copywriter made in the headline. Nor should, a graphic designer, be taken to task for not jumping in to save the day when the account manager forgot to respond to an email from the client.

But does that mean all bars are down?

Take my case, for instance. I graduated as an engineer, worked as a writer/editor for the next 6 years, and now am moving to software development. During my stint as a writer, I used to produce all kinds of content. And occasionally, some client would ask for rework. All this is fine in a day’s work, but my blood used to boil when the marketing folks used to come back to me even when the change was something a school kid could have made. For instance, changing “Every woman should know” to “Every woman knows”. What’s worse, I found that senior marketers, people who had spent the last 8-10 years gaining expertise and commanding respect, couldn’t tell the difference between “Its” and “It’s”, and used to write “I will revert back by 5pm” without fear. And from time to time I was also called in to “decode” what an email from client meant, as well as to provide words for what was on my esteemed colleague’s mind.

What’s worse, these are people who never read books, never look at ads and emotional messages closely, and can’t tell if a message has a sense of urgency. And these people are marketers who hope to touch the sky some day!

As if all this wasn’t enough, these people are fully aware of what they lack and how they can improve it, but nobody has the time! It’s as if nothing else matters as long as the monthly paycheck finds its way home.

Seriously, guys, I know English is a foreign language for us, but utilization of our brains need not be.

Hitting the Metal Anvil

I once remarked to a friend, by whom I was introduced to Metal music, that it was a music of disturbed people. He seemed surprised, perhaps because his musicianship went beyond metal (and also because he didn’t consider himself disturbed). Well, if not disturbed people, it is certainly music of extreme people. The drumming is extreme, the guitar distortion is extreme, the lyrics and vocals are extreme. Why will a calm, regular human being put effort into this genre, and eventually come to like it, is beyond me. At least to me, it looks like metal was the culmination of punk, rap, and all those genres that had “rebellion” written all over them.

I make this claim because I fail to understand how the people who listen to metal and claim to have a “superior taste for music” don’t find any charm in the likes of Mozart, Chopin, etc.

A Look Inside the Recursive Hell of Fibonacci Series

Recursion is cute, no? After all, this is what every programmer learns in his early days while attempting (and failing at) the Towers of Hanoi problem. But this cuteness comes at a cost: overhead of making a lot of function calls.

Consider this simple Java program that produces the first 100 members of the Fibonacci series:

When I run it on my SSD-enhanced, Intel i5-powered laptop, the computation time starts hitting several seconds even as the 44th member is being printed. Interesting . . . I’m now intrigued about exactly how many function calls are being made. So let’s tweak this program a little and add a static variable to keep the count:

This run reveals something startling:

fibonacci-recursive-growth

As you can see, the function exhibits insane growth as soon as it nears N=40. At N=44, this “cute” recursive function is making more than 2 billion function calls!

That’s scary. Now let’s convert it into an iterative computation:

And the resulting growth graph:

fibonacci-iterative

Look like a quadratic growth curve. As you can see, for N=40, we now have to make only 821 calls as opposed to 2 billion+ form before. Quite an improvement!

Moral of the story: Go easy on recursion, people!

Flipkart is Shutting Down

Its website, apparently.

But the news that the largest e-commerce player in the India market is considering moving to an app-only format, has become, well, bigger than Flipkart itself. Confusion reigns, as some say only the mobile website is shutting down, while others say the desktop one will die as well.

In any case, what prompted me to write this post was some of the comments I came across on TOI about this development:

flipkart-2

flipkart-1

Long live Indians! 😀

Thoughts on Reference-Based Copying

One of the biggest annoyances I remember when learning scripting languages was wrapping my head around copy by reference. I came from a typical “C/C++ rules everything” background, and I was amazed how quickly I was able to pick up Python because it was oh so similar to C++. Except that copy and deepcopy made no sense to me. Yesterday I was learning object-oriented programming in PHP, and the __clone() method came up.

One might argue why the language designers have gone to such elaborate fence-building when it comes to copying objects? Why not simply copy by value and let that be the end of it. One explanation, of course, is memory usage. But I think it’s also part of language design philosophy.

The so-called modern languages were created to make programming faster and more intuitive. And so we have loose typing, which most people agree is a sanity-saver (including me). This is why when you write “$” * 4 in Python you get $$$$ and not an error; after all, if you forget about computer architecture for a while, isn’t that what you were trying to accomplish?

I think the same thing is going on in reference-based copying. When we write a = b, we tend to think in our minds that a and b are now identical. This means that if one part of a is changed, b is changed as well. Of course you might argue that it’s essentially mathematical notation and there it has no connotations of “identical-ness”; but hey, let’s not split hairs here. :-)

Coding without Syntax Highlighting?

How good is the idea of coding without syntax highlighting? Like, when everything is pitch black on white background (or reverse, if you’re intent on losing your eyesight early). Despite what I thought earlier, it’s one horrible idea. Syntax highlighting is not just eye-candy; the color scheme you follow is a powerful filtering system that helps you quickly locate what you’re looking for: “An error occurred while parsing a string? Hmm, then I need to quickly scan the red portions in the login script”.

And this, in turn, reduces the pressure on your eyes and nervous system A LOT. The conclusion, which I accept with humility, is that I can be an ass sometimes.

My First Attempt at Limericks

Today I felt like sitting down and writing a few limericks. These might not be great, but I feel an odd joy in the thought that these are original. Here goes!

~1~

I’m often confused about what to read
with what my brilliant mind to feed
those mystery stories with clever hooks
or the tales of unfortunate crooks
but like always, I can’t decide, and am undone by greed.

~2~

When it rains outside my home
on the faraway marble dome
through the window comes a light
dancing, twirling, with footsteps light
and my thoughts follow the clouds that roam.

~3~

Am I saint or a heathen sinner
a loser or a glorious winner
these thoughts occupy my mind
against my wish, oh what a grind
I lose sense of time, and every day, forget my dinner.

~4~

There was a girl who always said
she will never embrace the marriage bed
one day the pressure became too much
from somewhere she got a gun or such
and when they found her, her eyes were full of lead.

~5~

Don’t ask me to say something profound
I’ll only keep talking round and round
until your patience will run out
and you’ll begin to stomp and shout
while I’ll still be admiring the insects on the ground.

It’s all about Sex

I started reading J.M. Coetzee’s Disgrace, anticipating the rush of pleasure that comes from reading a fine book. It’s a great read, but I’m kind of getting fed up with sex featuring as the bedrock of every great work. Now, don’t get me wrong — sex is interesting; very interesting, in fact. But I’m kind of getting tired of reading about frustrated desires, lost desires, suppressed desires, and whatnot.

Maybe it’s time I turned to the Russians? I remember no sex in Crime and Punishment, and Master and Margarita also looks like a promising read. Anyway, here’s to bad luck, which follows us more faithfully that a tail follows a dog!