Quackle

QuackleCheckers and chess are no longer the only games where computer programs are able to beat human world champions. Last November, Quackle, a crossword game artificial intelligence and analysis tool, beat a former Scrabble world champion 3 games to 2, as related in this newspaper article. The exciting thing about Quackle, from my point of view, is that it is released under the GPL, meaning that you have access to the source code. An excellent opportunity to learn a thing or two about AI programming for real.

I find mildly amusing how reports and comments on feats like this one are centered around the computer and the computer program. My impression is that frequently an important point is missed, namely, that these programs are actually a homage to the human brain, more concretely, to the very human brains of their creators. I’ve always wished to learn more about the details of how programs like DeepBlue are implemented. For checkers, i had the amusing Blondie24: Playing at the Edge of AI, where David B. Fogel explains how he created a top notch checkers player. Now, with Quackle, i can finally go to the core. Nice.

Advertisements

A Scheme bookshelf

It all began while i was using MDK‘s development as an excuse to learn everything i could about programming and programming tools: makefiles, autoconf, automake, localization, texinfo docs, lexers, parsers… and, eventually, extensibility. I kept hearing about an exotic thing by the name of GNU’s Ubiquitous Intelligent Language for Extensions, and, finally, rose to the bait. But my first attempts at writing Scheme felt awkward. Not because of the parens (i liked Scheme syntax from day zero), but basically because i was writing C code using Scheme. Clearly, i needed to read a bit about this new thing and, to that end, i got a copy of The Little Schemer… to no avail: i didn’t get what elephants, food and Socrates had to do with programming; i still felt awkward. (It was not the book’s fault, mind you, but mine. More about this in a bit.)

Then i found the book. Abelson and Sussman’s Structure and Interpretation of Computer Programs changed my life as a programmer. I’m sure you’ve read lots of praise for this book. Totally deserved! SICP is not really about Scheme, but about thinking about programming. Reading it will make you a better programmer in any language. It will expand your mind. It will cure your diseases. It’s really that good. Besides, SICP is freely available in HTML, PDF and texinfo formats, so you really have no excuse. For extra fun, get the accompanying video lectures, by Abelson and Sussman themselves. These lectures are charming: these guys have a passion for what they do, and they transmit it from the very beginning, when Abelson jokingly explains why computer science is neither a science nor about computers.

Concrete AbstractionsThe most cited alternative to SICP is How to Design Programs by Felleisen, Findler, Flatt and Krishnamurthi. Its authors have even published a rationale, The Structure and Interpretation of the Computer Science Curriculum, on why they think SICP is not well suited to teaching programming and how their book tries to fix the problems they’ve observed. I won’t try to argue against such eminent schemers, but, frankly, my feeling is that HtDP is a far, far cry from SICP. HtDP almost made me yawn, and there’s no magic to be seen. If for whatever reason SICP is not your cup of tea, i would recommend Max Hailperin‘s Concrete Abstractions as a far better (as in more fun than HtDP) alternative.

With SICP under my belt, i was ready for The Little Schemer and The Seasoned Schemer(by Daniel P. Friedman and Matthias Felleisen), which i read in a row. You’d be hard pressed to find any programming book similar to the Schemers books. As in my case, the initial reaction may well be of rejection: on a superficial reading they look too queer, even childish, and by any means the kind of book a serious programmer should read, except maybe for fun. But that’s precisely the point: you won’t learn unless it is for fun! If you enter the game proposed by Daniel and Matthias, accepting to participate in their Socratic scheme, you’ll learn a lot with their books. I found easier to put me in the right mood after SICP because it also is imbued of a kind of magic, and also because i was much better equipped to capture the subtleties lurking in every page of the Schemers books. Besides having a great time, one ends up with a sound grasp of higher order functions, recursion (including the Y combinator) and continuations. In fact, it was reading The Seasoned Schemer that something clicked and i really understood continuations.

After all these readings i felt i was starting to have a good grasp of the conceptual underpinnings of Scheme and Lisp, and that it was due time to strengthen the technical details. Or in other words, i wanted to come to grips with the nitty gritty details of Scheme syntax and semantics, including macros (which i knew from some tutorials and readings on Common Lisp). To that end, Dybvig‘s The Scheme Programming Language was the perfect book. Comprehensible, exacting and with an elegant prose, and to the point. But, despite its succinctness, Dybvig does an excellent job in conveying the details of the language and its usage. The book also includes extended usage examples for a good measure. Thus, TSPL works nicely as both a tutorial and a handy reference.

If you already have a good basis on functional programming you can use TSPL as your first Scheme book and skip the previous ones (but you will be skipping lots of fun and, maybe, insight too). And if you happen to read French, an interesting alternative for a speedier learning path is Jacques Chazarain’a Programmer avec Scheme. In the first part of the book, Practical programming with Scheme, Scheme is thoroughly presented, using it in many examples taken from the standard data structures and algorithms curriculum. Taking this practical basis as a starting point, Chazarain proceeds to a comprehensive (almost 400 pages long) discussion of the formal basis of the theory of programming languages: automata, lexers and parsers, propositional calculus, rewriting systems, logic programming, lambda calculus and more. As you can see, the scope of this book is amazing, and it’s well worth learning a little French!

The nice thing about learning a programming language in such a good company is that one learns much more than a single programming language. These books helped me obtain a conceptual basis for thinking about programming and programming languages in abstract terms, applicable to any programming problem. As Sussman colorfully demonstrates in one of the SICP lectures, one feels like beholding the heart of the spirit that lives in the machine. An that spirit, of course, is an interpreter. So i delved into the theory and practice of implementing interpreters guided by another classic: Essentials of Programming Languages by Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes. This marvelous book delves deep into the art of writing interpreters using Scheme as the implementation language. By way of running example, an interpreter for an ML-like language is developed all along, showing the magic of, among other things, register machines or continuation-passing style. To get a flavor of what this book has to offer, i wholeheartedly recommend reading Friedman’s The Role of the Study of Programming Languages in the Education of a Programmer, an insightful talk on how a theoretical background is useful (and even needed) to any programmer in any language, which Friedman illustrates with practical cases taken from his book.

Sussman the magicianOne of the rites of passage of any self-deserving schemer is writing a metacircular scheme interpreter, that is, a scheme implemented in itself. Having a look at the innards of your language implementation sheds a whole new light on your daily usage of the language. Sussman goes as far as wearing his magician’s hat when he explains the metacircular interpreter in the SICP lectures, and rightly so. But i’ve always felt a bit frustrated by the fact that the implementations one finds in books like SICP, EOPL or, to cite another classical example, PAIP are actually for toy interpreters not covering all the details of real Schemes. And often the left out precisely the most interesting bits! Fortunately, there’s a book that will tell you everything you ever wanted to know about implementing Lisp interpreters and compilers: Lisp in Small Pieces by Christian Queinnec. This is easily the best book about Lisp i have ever read. LiSP shows, without omitting any details, how the family of Lisp languages is implemented (in interpreted and compiled forms). You’ll learn from the inside the difference between Lisp-1 and Lisp-2, how dynamical and lexical scope work, how blocks and continuations are related, how on earth one implements… everything you ever wanted to know about Lisp implementations, and then more. On top of that, Queinnec writing style is engaging and the book is pervaded by a fine sense of humour that made me laugh out loud several times. If you’re serious about Lisp, you must read this book.

Let me close my list of recommendations with the last addition to my Scheme bookshelf, namely, the third schemer installment: The Reasoned Schemer (by Daniel P. Friedman, William E. Byrd, Oleg Kiselyov). Paraphrasing Alan Perlis, the key reason for learning new languages and paradigms is the fact that they, hopefully, change the way you think about programming. Functional languages do a pretty good job at that, but they’re not the only game in town. Declarative programming is definitely another mind blowing experience, which you can enjoy reading The Reasoned Schemer. The book presents, in that peculiar style of its predecessors that i like so much, the basis of logic programming using a Scheme implementation that, in many ways, surpasses standard declarative languages like Prolog. The best of two awesome worlds, and an excellent way to ensure that you keep learning and expanding your programming horizons.

Happy reading!

The Lord of the Lambdas

Data and procedures and the values they amass,
Higher-order functions to combine and mix and match,
Objects with their local state, the messages they pass,
A property, a package, the control point for a catch–
In the Lambda Order they are all first-class.
One Thing to name them all, One Thing to define them,
One Thing to place them in environments and bind them,
In the Lambda Order they are all first-class.

Abelson et al., The Revised Revised Report on Scheme
(Hat tip jcowan on #scheme)

The Functional C++ Programmer

Learning about functional and dynamic languages is a doubled-edged sword. On the one hand, it opens up your mind and ensures many hours of really happy, even enlightened, hacking. But, on the other hand, it spoils you: if you ever have to come back to, say, C or Java programming you may get frustrated by the limitations you’ll find [0]. On the bright side, once you get over the first symptoms of impatience, knowing about better ways of coding will improve your programs in any language. I’ve been using mainly C at work during the last year and a half, and i feel that the quality of the code i write has been greatly improved by my readings on Lisp, Haskell and the like.

Ultimately, it’s not about the language you use or its syntax, but about how you think about your problems. And more about the tools and structures in your mind than in your language: if you have the former, you can usually work around deficiencies in the latter. But still, there has been many a time during the last months that i’ve wished i had been using, say, Scheme. For, although i knew how to reproduce the feature i needed using C, re-implementing it would have been too time-consuming. In this regard, using the most flexible language at your disposal may be a good idea.

For instance, i was reading an article entitled Generalized Function Pointers, which describes a C++ library for handling higher-order functions. For starters, it makes an interesting description of the kind of problems you find in languages with no built-in support for closures and HOFs. It may convince you (if needed) of why they’re a good thing to have. The good news if you’re using C++ is that there’s a boost library, Boost.Function, that implements polymorphic function object wrappers, and lets you write code like this:

function<int (int x, int y)> arithmetic_operation(char k)
{
  switch (k) {
    case '+': return plus<int>();
    case '-': return minus<int>();
    case '*': return multiplies<int>();
    case '/': return divides<int>();
    case '%': return modulus<int>();
    default: assert(0);
  }
}

Not as pretty as Scheme or Haskell, but my point is that, at least, C++ let’s you get closer to the real thing, which is more than C or Java can do [1]. I’ll left it for you to ponder whether the drawbacks of C++ surpass niceties as this one: i’m considering the (not unlikely) scenario where you need to use one of these languages, for whatever reason. Which leads me to my second, and more important, point: had i not studied functional languages, i wouldn’t be in a position to really appreciate and take profit of libraries such as those in boost’s functional and generic programming collections [2], or the excellent FC++. And would have lost lots of fun.


[0] I’m sure he’s exaggerating a bit, but Eric’s recent report of his first month using Haskell vividly expresses this kind of feeling:

For me, it’s a drug. The more Haskell I get, the more I want. The results I’m getting right now aren’t orders of magnitude better than the results I can get in a von Neumann language, but the velocity I can achieve is astounding. (When I’m not dealing with stupid extraneous problems.)

[1] Yes, i know you can do similar things in C or Java, but Boost.Function is more powerful than that (the keyword here being ‘polymorphic’, meaning, essentially, that it handles covariant and contravariant signatures gracefully).

[2] For more on the kind of tricks one can play using templates and Boost.Function, see Sutter’s Generalizing Observer, where the author, essentially, works around the lack of multi-methods in C++. More to the point, that article will make much more sense once one learns a bit of, for instance, Common Lisp’s object model.

Advice to programmers

If you haven’t already, you must read this. Pure gold.

A companion emacs blog

In order to avoid boring those of you using other editors, IDEs and/or operating systems, i’ve put together a companion emacs blog. Those of you so inclined can find there programming aids, elisp packages i like or have written, some tips and tricks, and other silly stuff.

The (poignant) sounds of Ruby

If i had to pick one of the mainstream so-called scripting languages, it would probably be Ruby, if only for Matz’s sympathy. Other reasons are its smalltalkish code blocks and iterators, schemish continuations, and pretty good integration with Cocoa and Applescript. Clever hacks like this tiny prolog implementation and innovative libraries like RSpec also help.

But i must confess that the main reason i would choose Ruby is that it has the most original and fun programming tutorial i’ve ever seen: the why’s (poignant) guide to Ruby. The guide’s author, why the lucky stiff, is (in her/his/its own words) “a fledgling freelance professor, one who will die young and make no lasting impression.” As for the guide itself, it’s full of color and cartoons, funky side-notes and sidebars with titles like Seven moments of Zen from my life. Other innovations include a Ruby Mini-dungeon Adventure and its latest and greatest: a soundtrack! In stiff’s own words:

What is the reason for a soundtrack?

  • Well, music is essential for utmost poignancy, is it not??
  • Because computer books should NOT. And so.
  • My clarinet needs a life too, let’s not forget.

With a song per chapter, the soundtrack is available for your hearing pleasure here.

Funniest thing i’ve seen since Lisperati. Pity i like other languages better ;-).

 Ruby I The.Foxes-6