Land of Lisp

I came to know of this fun looking Lisp book on Slashdot book reviews. Its called Land of Lisp: Learn to Program in Lisp, One Game at a Time!

Here is fun video introducing the book: http://www.youtube.com/watch?v=HM1Zb3xmvMc

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

Advertisement

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.

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.