The best way to learn programming is by writing programs. Reading programs written by brilliant programmers is equally important. If someone asks me for source code to read and learn from, without a second thought I will point him to SQLite. The following merits make the SQLite source code an ideal learning ground for programmers:

• Informative, balanced comments.
• Good coding practices: well factored-out functions, idiomatic use of the implementation language, consistent style, comprehensive tests etc.
• A real world project. Probably SQLite is the world’s most widely deployed database! Still it is small and amicable to a single brain.

SQLite is implemented in C. Are there open source projects written in other languages/paradigms that have all the above qualities? Personally, I would like to know about a Lisp project. Many will be interested in Java/C++ projects because millions of words have been written (wasted??) about designing ‘maintainable object-oriented software’. It will be informative to to see this ‘wisdom’ in practice.

I raised the same topic at stackoverflow and got a few answers. Unfortunately, some people found it to be “subjective and argumentative” and voted to close it :(.

Update 29/12: This has been voted as a “Great Question” on stackoverflow. The reason for closing the question has changed to: “Questions on Stack Overflow are expected to generally relate to programming or software development in some way…” lol :–/). A question could be up-voted as “Great” and it could be closed as irrelevant at the same time! Is there something wrong with the stackoverflow voting system?

Connexions is an online, open access educational resource dedicated to providing high quality learning materials free online, free in printable PDF format, and at low cost in bound volumes through print-on-demand publishing.

Here is a problem on lossless data compression:

Write the entire 24 volumes of the Encyclopedia Brittanica on the head of a pin.

The person who raised the problem also explained how this could be accomplished:

The head of a pin is a sixteenth of an inch across. If you magnify it by 25,000 diameters, the area of the head of the pin is then equal to the area of all the pages of the Encyclopaedia Brittanica. Therefore, all it is necessary to do is to reduce in size all the writing in the Encyclopaedia by 25,000 times. Is that possible? The resolving power of the eye is about 1/120 of an inch—-that is roughly the diameter of one of the little dots on the fine half-tone reproductions in the Encyclopedia. This, when you demagnify it by 25,000 times, is still 80 angstroms in diameter—-32 atoms across, in an ordinary metal. In other words, one of those dots still would contain in its area 1,000 atoms. So, each dot can easily be adjusted in size as required by the photoengraving, and there is no question that there is enough room on the head of a pin to put all of the Encyclopedia Brittanica.

Furthermore, it can be read if it is so written. Let’s imagine that it is written in raised letters of metal; that is, where the black is in the Encyclopedia, we have raised letters of metal that are actually 1/25,000 of their ordinary size. How would we read it?

If we had something written in such a way, we could read it using techniques in common use today. (They will undoubtedly find a better way when we do actually have it written, but to make my point conservatively I shall just take techniques we know today.) We would press the metal into a plastic material and make a mold of it, then peel the plastic off very carefully, evaporate silica into the plastic to get a very thin film, then shadow it by evaporating gold at an angle against the silica so that all the little letters will appear clearly, dissolve the plastic away from the silica film, and then look through it with an electron microscope!

There is no question that if the thing were reduced by 25,000 times in the form of raised letters on the pin, it would be easy for us to read it today. Furthermore; there is no question that we would find it easy to make copies of the master; we would just need to press the same metal plate again into plastic and we would have another copy.

Here is the full transcript of the speech. I am sure you won’t be surprised by the name of the speaker!

Learning Processing is a book that teaches graphics programming. The target audience is digital artists with no prior experience in programming. But this could also include professional programmers who wish to refresh their graphics programming skills, teachers of preliminary programming courses or people who are just curious about multimedia programming. It uses the Processing language as the programming medium. To work through the examples and exercises I decided to use Spark-Scheme - for two reasons:  

1. It has excellent 2D/3D capabilities.
2. Being a Lisp, it can be easily molded into a DSL for specifying digital images.

So I started implementing this new graphics language on top of Spark. Right now it has one special form, define-display, which allows the artist to issue simple graphics commands to the Spark-Scheme interpreter and immediately view the result on screen. Let us look at a simple display definition and its output:

(define-display basic-shapes
  (background 'white)
  (stroke 'black)
  (fill 'dark-yellow)
  (rect 50 40 75 100)
  (fill 'dark-red)
  (ellipse 150 140 100 100))

(basic-shapes) ;; Displays the following image on screen.

define-display adds a procedure to the environment which translate the commands to Spark's lower-level graphics calls. This procedure can optionally receive the title, position and size of the window in which the image is rendered. The following example makes use of these arguments: 

(define-display line-across-rect 
  (background 150)
  (stroke 'red)
  (line 0 0 100 100)
  (stroke 'white)
  (no-fill)
  (rect 25 25 50 50))

(line-across-rect "Line-Rect" 100 100 100 100)

Here is the solution to exercise 1.4: 

(define-display squares
  (with (a 100)
    (background 'white)
    (stroke 'black)
    (fill 'dark-red)
    (rect 0 0 a a)
    (fill (rgb 205 183 158))
    (rect a a a a)))

(squares "Squares" 100 100 200 200)

Deriving the Y Combinator in 7 Easy Steps.

Here is an easy to remember definition of Y in Scheme:

(define (Y f)
    (f (lambda (x) ((Y f) x))))

An anonymous recursive function that computes the factorial of 10 with the help of Y:

((Y (lambda (f)
  (lambda (n)
(if (= n 0)
    1
    (* n (f (sub1 n)))))))

  10)

=> 3628800

As you can see the combinator is bound to the identifier Y. But if we can bind a function to an identifier, why we need Y in the first place?. We don’t. We need Y when the language don’t allow binding functions to names and as a consequence do not have a convenient way to make recursive calls. Assuming that our implementation of Scheme is very primitive and do not provide these conveniences, we can define the factorial function as:

(((lambda (f)
  (f (lambda (x) ((Y f) x)))) ;; The Y combinator.

    (lambda (f)
      (lambda (n)
        (if (= n 0)
        1
        (* n (f (sub1 n)))))))

  10)

=> 3628800