Friday, December 31, 2004

Is BASIC good for anything?

Has BASIC become the red haired stepchild that nobody wants?

Some folks look down upon BASIC programmers; in fact they even avoid thier company. I'm not trying to say that all programmers are equal in the eyes of the CPU or anything, but remember that Bill Gates is basically a BASIC programmer and that BASIC was once the language of choice for many music related application in the 80's. BASIC's PLAY keyword makes it simple to program musical notes and I'm sure the language has a couple of other redeeming features as well (I just can't remember what they are at the moment).

BASIC's lack of the need for formal structure such as class declarations or include statements plus its interpreted nature makes it a popular language to learn programming even in places like India where everyone is allegedly born partially a programmer.

Speaking of India, here is a song written entirely in BASIC.

10 '+------------------------------------------------------------------------+
20 '|                      The Indian National Anthem                        |
90 '+------------------------------------------------------------------------+
110  PLAY "L8C#D#FFFFFFL4FL8FFD#FL4F#"  '| Jana gana mana adhinayaka jaya hai|
120  PLAY "L4FL8FFL4D#L8D#D#CD#L2C#"    '| Bharatha bhagya vidhatha          |
130  PLAY "L4D#G#L8G#L4G#L5G#"          '| Punjaba Sinda                     |
140  PLAY "L8G#L4G#L8G#G#G#L8A#L4G#"    '| Gujaratha maratha                 |
150  PLAY "L4F#L8F#F#L4FL8FFD#F#L1F"    '| Dravida uthkala vanga             |
160  PLAY "L4FL8FFl4Fl8fd#g#g#l4g#f#f#" '| Vindhya Himachala Yamuna Ganga    |
170  PLAY "L4fl8ffd#d#d#l8cl4d#l1c#"    '| Uthkala jaladi taranga            |
180  PLAY "L8ffffl4fl4fl8d#fl1f#"       '| Tava shubha name jage             |
190  PLAY "L8ff#g#g#l4g#l8f#fd#l8f#l1f" '| Tava shubha ashisa mage           |
200  PLAY "l4ffl8d#d#d#d#cd#l1c#"       '| Gahe Tava jaya gatha              |
210  PLAY "l8g#g#g#g#l4g#l8g#g#"        '| Jana gana mangala                 |
220  PLAY "l4g#l8g#g#g#l8a#l4g#"        '| Dayaka jaya hai                   |
230  PLAY "l4f#l8f#f#l4fl8ffl8d#f#l1f"  '| Bharatha bhagya vidhata           |
240  PLAY "o5l8ccl1c#l8co4a#l1o5c"      '| Jaya hai jaya hai                 |
250  PLAY "l8o4g#g#o5l1o4a#"            '| Jaya hai                          |
260  PLAY "l8c#d#fff#f#d#fl1f#"         '| Jaya jaya jaya jaya hai           |
270  END                                '+-----------------------------------+

Choosing the best suited language

But its got to be done in Jaavaa! (or .NET or VB or whatever)

No, Dr. Dre, you need to choose what's the most suitable language to solve the problem. Believe it or not, the complexity of the application changes dramatically with a language that thinks differently from the problem class at hand.

For example, consider a simple app that converts strips non-ASCII characters by converting them to their ASCII counterparts.

Lets say your manager loves BASIC and writes it as below


OPEN "unstripped" FOR INPUT AS #1
OPEN "stripped" FOR OUTPUT AS #2
WHILE NOT EOF(1)
     a$ = INPUT$(1, 1)
     n = ASC(a$)
     IF n > 127 THEN
           PRINT #2, CHR$(ASC(a$) - 128);
     ELSE
           PRINT #2, a$;
     END IF
WEND
CLOSE
END
That is quite reasonable, isn't it? You could probably write something equivalent in C, Java or related languages.
Yes, but look how much simpler it would be if Perl was chosen as the language of choice.

perl -pe 'y/\x80-\xff/\x00-\x7f/'
Its a one liner you type on the command line. For text processing, Perl tends to beat any other language.

Tuesday, December 07, 2004

Writing good hashcodes and equals

How would one write a good hashcode? Here is one I've seen in real life:

class Thing
{
    List itemlist;

    public int hashCode()
    {
        return toString().hashCode();
    }

    public boolean equals(Object o)
    {
        return o.toString().equals(toString());
    }

    public String toString()
    {
        return "Items = " + itemlist.toString() ;
    }
}
For reasons of brevity, I've drastically reduced the size of the original toString() function, but suffice to say, it printed the all elements of the entire complex Object with appropriate keywords. And the member itemlist was one that could grow indefinitely long. It was obvious that the dude who wrote it does not know what a hashcode is at all. A hashcode serves as a value for quick comparison between Objects. It is essentially used to quickly locate which bucket the item is stored in HashMaps and other data structures that provide near constant access time. If the hashCode computation takes longer than the equals comparison, then you need to brush up on your fundamentals. What could be done differently? A simple way to define a good hashCode is given below:
class A
{
    Integer a, b;
    String c;
    Set d;

    public int hashCode()
    {
        // Sum of (prime number * hashcode) for selected members
        return 7 * a.hashCode() + 11 * b.hashCode();
    }

    public boolean equals(Object o)
    {
        if(o == null || !getClass().equals(o.getClass()) || o.hashCode() != hashCode())
            return false;
        A other = (A)o;
        return other.a == a && other.b == b
            && c.equals(other.c) && d.equals(other.d);
    }
}
As you can see, while equal Objects imply equal hashCodes, the converse is not necessarily true. Most of the time, the check for class and hashCode will eliminate most matches. Among the few that do match, you just need to compare the itemlists without converting them to String first. This has the added benefit that the comparison can terminate early for example if the lengths are different. If you do not have any other members or you believe that they do not sufficiently provide a proper distribution of the hashcodes, you can define the functions as below:
class Thing
{
  private List itemlist;

    public int hashCode()
    {
        if( itemlist != null && itemlist.size() > 0 )
            return itemlist.size() * 7 + itemlist.get(0).hashCode();
        else
            return 0;
    }

    public boolean equals(Object o)
    {
        if (o == null || !getClass().equals(o.getClass()) || o.hashCode() != hashCode())
            return false;
        Thing thing = (Thing)o;
        return thing.itemlist == null && itemlist == null ||
            thing.itemlist.equals(itemlist);
    }

    public String toString()
    {
        return "Items = " + itemlist.toString() ;
    }
}
Of course, you have to ask yourself what business you have in returning toString() of classes that can be very large. If unavoidable, you should at least cache the results of toString() and hashCode() and update them on changes. This may need synchronization, so generally keeping hashcodes and toString functions simple is the better choice.