Tuesday, November 07, 2006

Symmetry

The book Discover Physics by Benjamin Crowell, talks about symmetry in Physics and in Nature. Wikipedia defines symmetry as

"In formal terms, we say that an object is symmetric with respect to a given mathematical operation, if, when applied to the object, this operation does not change the object or its appearance. Two objects are symmetric to each other with respect to a given group of operations if one is obtained from the other by some of the operations (and vice versa)"

Of the various types of symmetry described in the article, I find the reflection symmetry and rotation symmetry, the easiest to understand.


Reflective Symmetry




Rotation Symmetry
The interesting thing about symmetries is that they apply not only to nature, physics and mathematics, but to computing as well.
Consider that you are writing an API or developing a programming language or a library. By design, you the code needs to be able to undo, what it's allowed to do.
Consider a "C" program
Let's say we carry out the following steps


1. Allocate memory
2. Copy from user
3. Open a file
4. Write to file



What happens in case there is an error in step 4?
We carry out the following steps


1. Close the file
2. Free the allocated memory



We need to do the same when our we are done writing to the file.

Now compare what we did with reflection symmetry. Did you find anything similar? I think we should as a guideline make our API/code symmetric with respect to reflection. In lay man's terms, the code should be able to undo its own effect.

Most programming languages and API are symmetric. "C" has malloc()/free(), open(), close(). "C++" has a constructor and a destructor for each class, so we are mostly good as far as this rule is concerned. "Java" on the other hand, provides a garbage collector to maintain the symmetry. Consider what would happen if you could just allocate memory and never free it up? Open files, but never close them? The system would soon become unstable, the weight would grow on one side (memory, descriptor leaks) and the system would crash.

The symmetry created by the garbage collector makes life easy for the lazy programmer, but losing control over symmetry can throw a system in a non-deterministic state. Consider the case where a system has a lot of memory, the garbage collector never kicks in (of-course a lot depends on the actual algorithm). When a critical application needs to run, it needs most of memory, but to get free memory, the garbage collector starts running, starving the critical application of CPU time, making it wait for its memory demand. All of this could have been avoided (the CPU time overhead), but being in control of symmetry and freeing the memory when not needed.

Coming to rotational symmetry, I am yet to find a good use case for it in computer science (for an average programmer). For those involved in graphical illustrations, we could exploit it to make it easier to draw illustrations.

2 comments:

Anonymous said...

Nice.
Nicer to know that you're reading Physics now
Nicest to know that we are on the same page on garbage collection.

Point is also that garbage collection only works for memory - we still need to close files, sockets, GDI resources (heh heh, Windows only :)) and so on, something novice programmers totally ignore.

Balbir said...

Gops, yes, we do agree on something finally :)

The reason why I did not mention sockets, files, etc is because eventually they do map to memory (data structures in memory). Garbage collection should work for all resources irrespective of their type.

Coming to Physics, of late I've been reading A Shortcut through Time by George Johnson. It talks about Quantum Computing and Cellular Automata. I would highly recommned it to everyone interested in exploring computing beyond our daily needs

Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...