May 27, 2013

(Obligatory 'Random thoughts on the IPL' post of the year)

1. If there is a single piece of imagery that succinctly captures the essence of this whole sordid IPL season -- no, make that the entire IPL -- it's the super slow motion footage (accompanied by faux operatic music, natch) of the scantily clad oxy blonde East European hooker cheerleader dancing with gay abandon, her face frozen in the rictus of feigned joy while holding an open Pepsi bottle that spews out its carbonated sugary poison all over the place, also in super slow motion. Lust, gluttony, greed, pride -- all there. Throw in  some footage of Sreesanth glaring balefully at a batsman while having a towel stuck in his waistband, and you've got wrath and sloth covered as well (brownie points if you figure out how sloth is involved).

2. In related news, the Oxford English Dictionary has decided to replace the present definitions of the words/phrases 'chutzpah', 'cojones', and 'conflict of interest' with just a single picture of Srinivasan. They claim that this change will save them about 0.13% in space, while adding 78% in clarity and simplicity to the definitions.

3. On a more serious note, the reaction of the BCCI president reminds me of Bill Clinton's impeachment troubles. The spin then was that it was a witch hunt that had to be resisted at any cost. What transpired subsequently, in terms of prosperity and economic growth ("It's the economy, stupid"), is purported to have vindicated this stand (ignoring the dotcom bust, and other downsides to bubble economics). Whether this is true in this case as well remains to be seen.

4. If the BCCI president has been able to stand up so far to the powerful forces arrayed against him, this either means that a) he has powerful backers in his corner supporting him behind the scenes or b) he has a few aces up his sleeve that serve as leverage. If you believe that the match/spot fixing scandal emerged as the result of genuine sleuthing and has nothing to do with the moves on the grand chessboard to control the riches offered by Indian cricket, I have lifetime season tickets for two for the hospitality box in all IPL matches to sell to you at a 90% discount.

5. The electronic media's coverage of the spot fixing scandal has been over the top as usual. While this is expected, Deccan Chronicle have also joined the party with their front-page attacks on Srinivasan. No doubt they're getting their revenge for some slight they suffered at his hands when they had a horse in the IPL race.

Building a Lisp Interpreter from Scratch -- Part 9: Serialization

(This is Part 9 of a series of posts on pLisp)

(Note: This post is quite out of sync with the code base; please see Part 13)

Serialization in pLisp is an all-or-nothing thing, i.e. not at the level of individual objects, but at the image level. You can invoke the CREATE-IMAGE special form at any point (at the top level, in the middle of execution, or while in debug mode) to dump the image to the hard disk to a file of your choosing. Loading the image is done by invoking pLisp with the file name as the argument.

$ ./plisp

Welcome to pLISP. Type 'quit' to exit.

USER> (defun fact (n)

        (apply * (range 1 n 1)))

FACT

USER> (fact 10)

3628800

USER> (create-image "test.image")

NIL

USER> q

Bye.

$ ./plisp test.image

Welcome to pLISP. Type 'quit' to exit.

USER> (fact 10)

3628800

USER> quit

Bye.

Nifty. An even more powerful aspect is the ability to do this in the middle of a debugging session (Hi, Smalltalk. It's been a long time, we should catch up sometime soon.):

$ ./plisp

Welcome to pLISP. Type 'quit' to exit.

USER> (let ((x 10))

        (break)

        (* 2 x))

BREAK

DEBUG> x

10

DEBUG> (create-image "debug.image")

NIL

DEBUG> (resume)

20

USER> q

Bye.

$ ./plisp debug.image

Welcome to pLISP. Type 'quit' to exit.

DEBUG> x

10

DEBUG> (resume)

20

USER> q

Bye.

Astute readers will observe that starting pLisp with the image takes us directly into the debugging session that was active when the image was created. The real utility of this feature is in allowing us to share the image file with somebody and enlist them in our dirty debugging efforts.

All these good things are possible courtesy of the TPL serialization library (thanks Troy, especially for help with the tricky bit involving packing arrays inside structs). The following variables capture the complete state of pLisp, and serializing/deserializing them is all it takes:

strings

top_level_env

free_list

last_segment

heap

current_package

gen_sym_count

packages

debug_mode

debug_continuation

debug_env

execution_stack

debug_execution_stack

reg_accumulator

reg_next_expression

reg_current_env

reg_current_value_rib

reg_current_stack

images.c is the place where all this action is.

Update: One feature not yet implemented is the serialization of references to foreign function libraries: if we load a bunch of .so's and then create an image, the handles to these libraries will be lost when we invoke pLisp with the image file. The way out is to serialize an array of strings containing the shared library names, and then do a dlopen() on these libraries afresh.

May 20, 2013

Quick, what's the first thing that comes to mind when you hear the word "shochaley"? If you answered "Vidya Balan", pat yourself on the back and stand in the line over there for your lollipop. I understand the importance of proper plumbing, the need for celebrities to lend their time to worthwhile causes, and so on, but if somebody told me that roping her in for this ad was a plot concocted by her rivals to damage her brand ("Jahan shochaley, vahan Vidya Balan"), I'll probably nod my head in thoughtful agreement.

Does anybody believe that spot-fixing in the IPL begins and ends with the three Rajasthan Royals players, and nobody else from the other franchises (the word 'franchise' itself reeks of the money-grubbing ethos of the whole thing) is involved? Please return the lollipop if you do. The convenient death of the person responsible for the tapping of the phones? Just a coincidence, please move along.

Must-read article about Ranbaxy.

Building a Lisp Interpreter from Scratch -- Part 8: Garbage Collection

(This is Part 8 of a series of posts on pLisp)

(Note: This post is somewhat out of sync with the code base; please see Part 13)

There are many algorithms available for garbage collection. We go with the simplest (well, the second simplest, since mark-and-sweep is simpler, but needs allocation of one bit in the object, something which we cannot do), i.e. tri-color marking.

Tri-color marking works like this: we have three sets of objects -- white, grey and black. The white set consists of all objects that can be garbage collected, while the black set contains objects that should not be (because somebody is holding on to references to these objects). The grey set contains objects that we're not sure about yet.

Before moving on, something about the when of garbage collection: we do GC after every execution of the REPL.

Whenever an object is created (through object_alloc()), it is added to the white set. If, after execution of the REPL, we find that it's still in the white set, it is GC'd. Objects save themselves by first getting themselves promoted to the grey set and then to the temporary haven that is the black set. Temporary because, as they say, you're only as good as your last hit, so beware the next call of gc() -- nobody may be holding your hand when the music stops.

The grey set starts off with all the root references. A root reference is an object that we're sure is reachable and hence cannot be GC'd. In the case of pLisp, the root references are all the top-level objects, conveniently captured in the top_level_env CONS object. Thus our grey set starts with this single object.

For each root reference, we do the following:

1. Move it to the black set
2. Move all the objects it directly references to the grey set.

The above algorithm is applied recursively till we end up with no more objects in the grey set.

Now GC is just a simple matter of freeing up RAW_PTRs corresponding to the objects remaining in the white set.

We use a binary search tree to store the contents of the three sets:

struct node
{

struct node *left;
struct node *right;
OBJECT_PTR key;
} ;

with the OBJECT_PTR values serving as the key. A slight wrinkle is needed to make sure that the BST remains balanced when we remove a node with both children present: we toss a coin to determine whether we go down the left or the right sub tree.

How to determine the objects referenced by a given object is pretty straightforward:

1. If it's a CONS object, check its CAR and CDR
2. If it's a closure or a macro object, it will reference three CONS objects: a parameter list, the enclosing environment, and the body of the closure/macro.
3. For array objects, check all the array elements
4. If it's a continuation object, the CONS object corresponding to the current call stack will be the referenced object (remember the trickery we resorted to to efficiently store the current call stack in the continuation object?)
5. Objects of other types (character, integer, float, symbols, strings) do not reference other objects.

The memory needed to store symbols and strings does not come from the heap, but from a dynamic (char **) array called 'strings'. pLisp does not do any GC for this yet; maybe in the future.

Integers and floats, while not referencing other objects, are actually allocated on the heap. Lopping off the tag from objects of these two types yields a RAW_PTR that indexes into the heap; the relevant location contains 32 bits that is the integer/float value of the object. This is very inefficient, actually, since the same number will be stored multiple times on the heap, but this is required if we want to leverage the full 32 bits to store the integer (only 28 bits were being used earlier [see Part 3]). Maybe we can use the flyweight pattern or something.

May 3, 2013

Patriotism is the last refuge of the scoundrel.

Watching Musharraf's travails after his return to Pakistan reminds me of a Tom and Jerry cartoon: the one where Tom sneaks furtively into a yard, only to be ambushed by the bulldog, his tail firmly in the grip of said bulldog's jaws, with periodic 'boing, boing' noises emanating whenever Tom's head makes contact with the hard ground. Not that I have any sympathy for the f*cker. Musharraf, that is; Tom I dearly love.

Speaking of bulldogs, Surendra's recent cartoon about the CBI and the Supreme Court is a classic.