‘Typesetting’ Presentations with Beamer

Do you use LaTeX for your document processing requirements? Then why switch to any other application when you need to create presentations? Try Beamer instead.

My article on Beamer is out in the November, 2009 issue of Linux For You. By next month, the article will be available at http://www.linuxforu.com. If you want to take a look at it, email me and I might be able to share a personal copy.

Quick Tip: Piping to gnuplot from C

Update, 21/10/09 :Thanks to A.K’s comment, Its “gnuplot” and not “GNU plot”

Couple of things first up:

• gnuplot supports piping, So, echo "plot sin(x)" | gnuplot will plot the sin(x) function.
• However, the plot disappears even before you could see it. For that echo "plot sin(x)" | gnuplot -persist , is useful. It persists the GNU plot main window

The usefulness of the second point is that, if you have a “pipe descriptor” describing a pipe to the open gnuplot instance , you can plot more plots on the first plot, without opening a new gnuplot instance. We shall be using this idea in our code.

C (Cee Language)

#include <stdio.h>
#define GNUPLOT "gnuplot -persist"

int main(int argc, char **argv)
{
        FILE *gp;
        gp = popen(GNUPLOT,"w"); /* 'gp' is the pipe descriptor */
        if (gp==NULL)
           {
             printf("Error opening pipe to GNU plot. Check if you have it! \n");
             exit(0);
           }

        fprintf(gp, "set samples 2000\n");
        fprintf(gp, "plot abs(sin(x))\n");
        fprintf(gp, "rep abs(cos(x))\n");
        fclose(gp);

return 0;
}

The above code will produce a comparative plot of absolute value of sin(x) and cos(x) on the same plot.  The popen function call is documented here. This code/idea should work on GCC and Linux and any other language and OS that supports piping.

Utility: If you have a application which is continuously generating some data, which you will finally plot, then you can plot the data for every new set of data- that gives a nice visualization about how the data is changing with the iterations of your application. This is a perfect way to demonstrate convergence to the best solutions in Evolutionary Algorithms, such as Genetic Algorithms.

Links:

1. Piping
2. gnuplot Homepage

Patterns or Randomness?

Look for patterns. If its a good pattern, (such as the Fibonacci series), all is good. If it is a bad pattern, (such as, you breaking your leg every six months), see randomness.

Bogosort: a O(n.n!) sorting algorithm, Scheme implementation

Bogosort is a perversely awful algorithm [source]. Its awful because it is a direct fallout of the Infinite Monkey Theorem. Keep shuffling a set of numbers till it is sorted. That’s it. For a set of N numbers, you can have N! permutations and exactly one of them is the sorted. Now find that one. Wonderful.

Here is a Scheme implementation of Bogosort developed/tested it only with plt-scheme.I have used the “modern” Fisher-Yates shuffling algorithm for the shuffling exercise. The modern version has a O(n) time complexity versus the O(n^2) of the classic version.

And some more fun with a detailed analysis of  perversely awful randomized sorting algorithms [link] and then there is Wikipedia

Review: Coders at Work

So, I had a sneak peak at Peter Seibel’s upcoming book- Coders at Work. Thanks for the wonderful opportunity, Peter.

Read it, because then you will know the greatest coding brains.

For those of you have not heard of the book, its a collection of the author’s interviews with 15 of the best brains in Computer Science and Programming, the world have seen. I particularly enjoyed reading the interviews of Donald Knuth, Ken Thompson and Guy Steele- these were the more known names to me because of my trade with Computer Science, Unix and Scheme day-to-day.

After scheming through it, I found one thing re-established, Computing was more fun in the early days. This was a common thread running through all of the interviews- a lot of the interviewees shared a opinion that, computing today is a lot abstracted from the real thing beneath. I wish I was born during those days near one of those university campuses

BTW, if you want a sneak peak, please consider emailing the author and you might just get lucky, like me

Of Well commented code and Literate code

Well commented code

I have written more than a couple of dozen technical articles- most of them guided towards newbies, ’cause:

1. I love scratching the surface of a million things, and
2. I want to write them down- the reason which I attribute to a combination of {willing to share, increasing the tally of my articles, a quick buck, boast}, with one or two overpowering the other most times

Since, I write them for newbies, I want them to be very detailed, with all the fancy screenshots, et. al. (The first tine we met face-2-face, Sriram Narayanan actually appreciated that). A direct fallout, or shall I say a good fallout, because of that is I really feel inclined to do the same when I write the code comments whenever I write a piece of code I want someone else to understand.  For eg. this code

Literate Programming

This programing paradigm was conceptualized by Donald Knuth to introduce a new programming style where you would write code the way you think, not the way your particular language makes you to. You define separate chunks of code in your program, as you cook it up in your mind and then you weave them together to form a large program which is closer to the way you think, than you are made to think. Top-down, or Bottom-up just doesn’t cut it at times. You have to define this, before that, declare that before this and what you get is code which is a lot different from what you would have liked to.

Consider this piece of Scheme code written using/for plt-scheme. It is written using the scribble/lp (since plt-scheme 4.1.5) plt-scheme module which provides support for Literate Programming in Scheme. Here we  have defined a chunk of code and named it as squarefunction. Next, you could define N more chunks of code, in the way your mind cooks it over and then combine the chunks together. For eg, the source code of  chat-noir.

Well commented code v$ Literate code

Now, as you can see from my naive example, which is the first time I have made any attempt to write literate code, I started thinking that well commented code serves my purpose just fine. Hence, I really didn’t get that intuitive motivation for writing a Literate Program. But there is a difference- I write well commented code for others to  understand my code, I would write Literate Code for myself, ’cause that is the way it is being manufactured by the cells in my brain, and my programming system shouldn’t hinder that flow.

Related post: http://www.wisdomandwonder.com/link/2100/literate-programming-in-scheme and my Stack Overflow question looking for the intuitive motivation

Literate Programming tools and systems

See the Wikipedia entry

fileserveHTTP.ss: Serve your local files over HTTP

The GNU GPL source of the first release, Version 0.8  is available at http://bitbucket.org/amitksaha/foobar-scripts/src/tip/fileserveHTTP.ss

Background:

I accidentally came across the SimpleHTTPServer.py Python module, while back and immediately found it a very useful utility script. As part of my Scheme learning exercise, I implemented the same (AFAIK, complete) functionality in the Scheme language using PLT Scheme.

More: Systems Programming with PLT Scheme helped me get started with a multi-threaded server (till Step 6). From then on, I tried to understand what the code in the Python module does, and tried to implement the functionality in the Scheme code.

High Level Execution flow

The code execution starts from (serve) procedure which creates the server process and hence is ready for accepting new client connections. A new client connection is handled in a new thread. For the first GET request, the list of current sub-directories and files in the directory from which the server was started is returned (in a HTML page) to the client. This is performed by the (doGet-list) procedure. After the first request, the new GET requests are served by the (doGet-file) procedure.

Limitations:

• I have used a lot of plt-scheme APIs, so this code will work only with plt-scheme
• I have developed this code on Ubuntu Linux and that is the only OS, on which I know it works. Specifically, I would like to test the path name handling and MIME type detection on other Unix and may be Windows too
• The code doesn’t do any exception handling as of now
• This is my first proper Scheme program, so I might have written C/Java/Python in Scheme.

Usage instruction can be found in the source code itself. Please suggest comments/suggestions for improvements to amitsaha.in@gmail.com or post a comment here.

Let the angels guide you

This is a rant. Feel free to skip.

Angels and Demons: Watching the movie within a week of finishing the book was a bad idea. The movie per se wasn’t bad, by any means. Brilliant Tom Hanks, amazing background score (Hans Zimmer) and a gala stage. I just couldn’t watch the movie without trying to match it page by page with the book. Bad Idea!

Perhaps, its just a tough job to do justice to a good book of 600+ pages in a < 180 min. movie. Even more tough when you try to sell the movie  as based on the book.… Perhaps the based is a keyword here. Its not THE book that has been brought to life., but its a adaptation or, may be a inspiration.

No wonder that, its got a rating on < 7 on IMDB.

This is one of those movies, that I watched after having read the book. Perhaps, that is why I didn’t rant after watching The Godfather trilogy.

A Primer on Recursion

The study of Recursion abounds in such statements as:

“Hofstadter’s Law: It always takes longer than you expect, even when you take into account Hofstadter’s Law. ” —Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid.

They are amusing and thought provoking at the same time. The idea of recursion is simple when you think of expressing something complex in terms of simpler versions of itself. You will then see recursion in action in the simple things we do everyday, the music we create, the language we speak and the things that happen at sub-atomic levels. In the chapter titled “Recursive Structures and Processes”, of Gödel, Escher, Bach ( http://en.wikipedia.org/wiki/Gödel,_Escher,_Bach ), Douglas Hofstadter ( http://en.wikipedia.org/wiki/Douglas_Hofstadter )takes you into a World of Music, Art, Physics and Programming where recursion abound. The underlying concept is to decompose a big problem into indivisible sub-problems, solve them and then combine each of these partial solutions to get the holistic solution. This combination operator is not a universal operator and is specific to the problem at hand. As a crude example, consider the factorial function, fact(N). It is elementary to observe that  fact(N)   = N * fact(N-1) = N * (N-1) * fact(N-2)…

As is apparent, we are combining smaller fact()’s by the multiplication operator to obtain fact(N). Here our combination operator is multiplication operator- ‘*’. In the rest of this paper, I shall touch upon recursion in Formal Languages, Linguistics, Mathematics and Computer Science. Except for the last one, in which I have had my education, I am just a guy who takes keen interest in these fields.

The rest of the essay is available in PDF here or html here

Suggestions/Comments welcome.

Tail Recursion Optimization, gcc, gdb

Debugging or even throwing optimized code in a debugger is a stupid idea, when you are trying to debug the code, that is. Not so lame, when you are trying to learn whether the optimization has actually taken place . I wanted to check whether Tail Call Optimisation (better yet, Tail Call Elimination) has taken place on a certain piece of code. Here’s how:

Consider the following C implementation of the factorial function:

/* factorial-tail.c */

#include <stdio.h>
unsigned long long factorial(unsigned long long fact_so_far, unsigned long long count, unsigned long long max_count){
if (max_count==0 || max_count==1 || count >= max_count)
return fact_so_far;
else
{
//	printf("%llu  %p \n", count, &factorial); /*
return factorial(fact_so_far * count, ++count, max_count);
}
}

int main(int argc, char **argv)
{
unsigned long long n;
scanf("%llu", &n);
printf("\n Factorial %llu \n",factorial(1,0,n));
return 0;

}

Consider the function, factorial. As required by the definition of tail call recursion, the last executed statement is the recursive call to itself. No operation is pending in the caller, once the callee finishes its task.

Compile the code using ‘gcc’:

gcc -O2 -fno-inline -o factorial-tail factorial-tail.c

Now, fire up ‘gdb’ with the object code obtained above:

$ gdb ./factorial-tail
(gdb) b factorial
Breakpoint 1 at 0x8048426
(gdb) run
Starting program: /home/amit/Documents/Writings/cs-essays/fact-codes/factorial-tail
5
Breakpoint 1, 0x08048426 in factorial ()
Current language: auto; currently asm
(gdb) c
Continuing.
Factorial 120
Program exited normally.

As you can see the breakpoint was hit just once, whereas clearly if the code was executed unoptimized, it should have been called 5 times.

A note on ‘-fno-inline’ flag: Explicitly mentioing the ‘-fno-inline’ flag prevents any inlining of the fuctions due to the ‘-O2′ flag. On my gcc/gdb combination, without the flag, inlining was being done, due to which the breakpoint wasn’t hit even once.

Now, compile the same code, without the -O2 and -fno-inline flags:

gcc -o factorial-tail factorial-tail.c

Fire up ‘gdb’ as above:


$ gdb ./factorial-tail.
(gdb) b factorial
Breakpoint 1 at 0x80483f8
(gdb) run
Starting program: /home/amit/Documents/Writings/cs-essays/fact-codes/factorial-tail
5
Breakpoint 1, 0x080483f8 in factorial ()
Current language: auto; currently asm
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Factorial 120
Program exited normally.
(gdb)

Point taken?

Thanks to folks here and here

Some other further readings:

• http://stackoverflow.com/questions/490324/how-do-i-check-if-gcc-is-performing-tail-recursion-optimization
• http://sunsite.ualberta.ca/Documentation/Gnu/gcc-2.95.2/html_chapter/gcc_14.html
• https://webmail.iro.umontreal.ca/pipermail/mslug/2008-April/000292.html

If you see any errors, I stand corrected. If you want to share any thoughts/findings on something related, please leave a comment.