Books

Books are great! Some say the internet holds all the answers. I'd say it holds most of the answers and it will hold them all as soon as publishers, authors and hardware companies get off their own way and create serious mechanisms to manage (publish, buy, sell, read, own, share) digital books. If they're as stubborn as the music industry, this will not happen soon; but I think that, with the lessons learned from music, we're moving in the right direction. Let's see what the future holds (or let's ourselves make the future happen). For now, here's a list of technical books I've read lately and I'd like to recommend:

• 
  Beautiful Code
  
  This book is a must read. It is also a very easy read. It's comprised of series of write-ups by different authors of the likes of Brian Kernighan and Simon Peyton Jones where the authors have chosen a problem they've faced and solved "Beautifully". Each author has their own definition of beautiful code (great design, speed and reliability, testability, versatility and more), but all of them teach you valuable ways to think about problem solving, design and development. With languages from Haskell to C (through Python, Ruby, Perl Lisp and others) and topics from quicksort to software transactional memory (through Python's dictionaries, testing, debugging, mapreduce and the original implementation of Paint among others) I can assure you that this book will be of interest to any good computer scientist or software engineer. My recommendation: go buy this book and put it on your night stand; it is very easy to just read a chapter every day.
  


• 
  Real World Haskell
  
  This book is just amazing. It covers Haskell from zero-knowledge to advanced and has something to offer to programmers of most backgrounds. Those who have never programmed in Haskell (or even functionally) will definitely benefit from the paradigm switch and seeing the problems from another perspective. Those that already know Haskell will probably find it a little bit slow as it explores a lot of the basics, but there are, for certain, hidden pearls to be found on every section; plus, you can skim fast through the "Haskell" parts and get to the "Real World" parts to get great examples of the uses of this powerful, different, language.
  



• 
  Programming pearls
  
  This is a book of the like of Beautiful Code but written by only one author (Jon Bentley, who also writes a great article in Beautiful Code) and slightly older. It showcases a series of problems and different ways to approach and solve them. It is not so much focused on the solutions themselves but the way of thinking for arriving to those solutions. The problems in themselves are not overly complex, but the detail in which the different options are explored and the trade-offs and solutions presented is very appealing. All the problems are accompanied with the C code used for solving it but avoiding any unnecessary boilerplate. It's simply a great book to keep you sharp on your computer-problem solving abilities.
  


• 
  The algorithm design manual
  
  While I think this book is a little hard to read at some points it provides an amazingly complete set of algorithms, their implementations and example problems. One thing I liked a lot about this book is that it's not solely based in simple explanatory examples but also shows how the different techniques showcased in the book can be used to solve real life problems (that actually happened). But the really amazing thing of this book is that it contains a chapter with a comprehensive catalogue of algorithms categorized by the type of problem they solve. It is literally half of the book, they all have an illustration to represent what the algorithm does and it serves as a great reference for any future algorithmic problems you might encounter.
  
  

Honorable mentions go to:

• 
  Coders at work: a series of interviews with great programmers in which they expose their thoughts on programming along with their personal experience. As of today I've only read a few chapters, but I go so far as to recommend the whole book as it has left a very good impression.
  


• 
  Introduction to the theory of computation: a great introduction, from regular expressions, finite and push-down automatons to reductions and computability. Very well explained from an expert in the field. It is also well written and very short. Loved it.
  


• 
  Artificial Intelligence: a modern approach, this book contains at least introductory material to most fields in artificial intelligence. It has in-depth material about a lot of topics and instead of trying to deeply explore all of the areas of AI in one book (which would be impossible) it focuses on the most important areas and gives you a great introduction on the rest for you to go and read the papers or a more specific book.
  

Later this month I'll make a list of non-technical books I have read or am reading and I'd like to recommend.

Any technical books you can recommend me?
I am particularly interested in advanced data structures, modern concurrency (Programming Erlang is in my to-read list), compilers (Compilers by Aho et. al. is in my to-read list), optimization and computational geometry. But that's just a list of stuff that popped in my head this instant, so if you have any recommendations on another subject please be sure to let me know!

Emacs mark-stack

There's no worst feeling than being lost in your code. You know, when you need to look at a bunch of code fragments buried in other files or in the same, very large, file; or having to trace back a bunch of function calls spanning multiple emacs buffers and not knowing where the previous stuff was.
Okey, there are probably a lot of feelings that are worst. But you gotta give me it's annoying.

If only there was a way to push positions to a stack and then come back to them later on! I know about C-@ and C-U C-@, but if you use delete-selection-mode or anything else in which you do a lot of marks that's not an option. Plus, the default key bindings suck and it's only buffer local. So I decided to write my own mark system in emacs lisp.

Before people come rushing down to the comments to tell me there's already a better solution for this problem, take into account that I didn't look much into it. I did this not only to solve the problem but to practice my elisp. Nevertheless, if there are alternatives I would love to hear about them; so comment on, just don't troll =)

If you don't know emacs-lisp there's a guide by Xah Lee I can't recommend enough.

Design

So I want two things: (i) To be able to push and pop marks locally to a buffer and (ii) to be able to pop marks globally. The later means that if I push marks in two different buffers and I do a global pop, the current buffer will change to the one with the latest mark.

To do this, I used two datastructures: A hash table that maps a buffer name to its stack, and a global stack that keeps all the pushed positions.

The first one looks like this:

"marks.el" -> (1622 1042 1283)

((1622 "marks.el") (1042 "marks.el") (194 "*Messages*") (1283 "marks.el"))

In the global stack we keep the name of the buffer so we can move to it and remove the mark from the right stack.

So, onto the code.

Code

First we need a helper function to add the list to the hash if it doesn't exist already or push to the stack on an existing list

(defun add-or-push (key value hash)
(if (gethash key hash)
    (progn
    (puthash key (cons value (gethash key hash)) hash))
  (progn
    (puthash key (list value) hash))))

And some functions to clear the local and global stack should things go wrong.

(defun clear-push-mark-for-buffer ()
"Resets the buffer's stack"
(interactive)
(puthash (buffer-name) () local-mark-stack))

(defun clear-global-push-mark ()
"Resets the buffer's stack"
(interactive)
(setq global-mark-stack '())
(maphash (lambda (kk vv) (puthash kk () local-mark-stack)) local-mark-stack)
)

Now, the real code:

For pushing, we just need one function that adds the current possition to both datastructures:

(defun local-push-mark ()
"Pushes a the current point to a stack"
(interactive)
(if (boundp 'local-mark-stack)
    (progn
      (let (buffer point)
        (setq buffer (buffer-name))
        (setq point (point))
        (add-or-push buffer point  local-mark-stack)
        (message "Pushed %d on %s" point buffer)
        (if (boundp 'global-mark-stack)
            (setq global-mark-stack (cons (list point buffer) global-mark-stack))
          (setq global-mark-stack (list point buffer)))))
  (progn
    (setq local-mark-stack (make-hash-table))
    (local-push-mark))))

For popping, however, we need a function for the local stack and another for the global stack

(defun local-pop-mark ()
"Pops the a mark from the current buffer's stack"
(interactive)
(let (stack)
  (setq stack (gethash (buffer-name) local-mark-stack))
  (if (and (boundp 'local-mark-stack) stack)
      (progn
        (goto-char (pop stack))
        (puthash (buffer-name) stack local-mark-stack)
        (setq global-mark-stack
              (remove (list (point) (buffer-name)) global-mark-stack)))
    (message "No marks to pop"))))

(defun global-pop-mark ()
"Pops a mark from any buffer"
(interactive)
(let (pos buffer)
  (setq pos (car global-mark-stack))
  (setq buffer (nth 1 (car global-mark-stack)))
  (setq stack (gethash buffer local-mark-stack))
  (if (and (boundp 'global-mark-stack) stack)
      (progn
        (switch-to-buffer buffer)
        (goto-char (pop stack))
        (puthash buffer stack local-mark-stack)
        (setq global-mark-stack (remove (list pos buffer) global-mark-stack)))
    (message "No marks to pop"))))

the only important detail to notice is that the global pop removes both from the local and global stacks. The rest should be self-explanatory.

And we add a statement to provide the marks module

(provide 'marks)

So now, we just need to load the module and add some key bindings:

(require 'marks)
(global-set-key (kbd "C-x ") 'local-push-mark)
(global-set-key (kbd "C-x ") 'local-pop-mark)
(global-set-key (kbd "C-x S-") 'global-pop-mark)

Using it.

If your using my .emacs you just need to ckeck out the code and compile it.

If not just copy everything up to " (provide "marks") " into a file called marks.el and load it in your .emacs.

Enjoy.

Edit: Apparently there's no lisp syntax support for the highlighter I'm using. sorry for that.

My Pycon talk (Python Metaprogramming)

If you followed the link on my previous post and looked at #64 you might have noticed I'll be giving a talk on Python Metaprogramming. Here's a sneak peak at what the talk will be like along with some comments.

Outline

• Metaprogramming:
  A short explanation of what metaprogramming is, why it is needed and how it can save you time and effort.


• Metaprogramming Languages:
  
  What languages are considered "metaprogramming languages" and what constructs do they provide to be considered as such. A 30000 ft view exploration of the metaprogramming features of languages like Lisp, Ruby, Perl, Javascript, Haskell and OCaml.


• Cool uses/examples of metaprogramming in other languages:
  
  Some interesting examples of metaprogramming regardless of the language. These examples will be ported to Python at the end of the talk. I will go through this very fast just to show what we want to achieve in each example and what techniques are used by other programming languages to achieve this effects. A more detailed explanation will be done at the end of the talk by porting the examples to Python.
  



• Tools for metaprogramming in Python:
  
  Each of the subsections of "Tools for metaprogramming in Python" should contain the following information:
  
  
  
  • Explaination: short explaination
  
  
  • Short example in Python
  
  
  • An example of using the technique to port some othe language metaprogramming features
  
  
  • Patterns: Common or useful patterns to incorporate that metaprogramming tool into your code
  
  
  • Advantages, disadvantages and perils.

The subsections I'll be covering are the following:

1. Code generation: eval() and exec():
   The basics. Code Generation as strings and getting them to execute.
   


2. Python (A.K.A.: Python's data model):
   Exploring the flexibility of Python's data model: Duck-typing, special methods, attribute access, callable emulation, behaviour on operators.
   


3. Decorators:
   An introduction to decoratos and what can be achieved with them. Emphasis on decorator patterns.
   


4. Metaclasses:
   A basic introduction to metaclasses: What they are and when are they needed. Includes an idea of when can metaclasses be replaced by decorators.
   


5. types. Specially types.FunctionType:
   Exploring type objcts. Specially function objects, code attributes, locals, globals defaults and closures
   


6. Others: import hooks, ByteCode, etc:
   A seccion on other useful metaprogramming tools that might fit into the time frame of the talk. (this seccion might be included depending on the time or if there are in depth talks in pycon about somme of the above techniques that suggest cutting down on them in favour of other options)
   

Putting it all together:
Just a pointer to a resourse that shows example code using most of the techniques shown throughout the talk. The example will probably be creating a DSL: possibly language generation (HTML, CSS, SQL or other), a generic problem solver or a small framework for distributed computation. I might take a lightning talk to go through this example in more detail.

The Good, the Bad and the Ugly:
A short conclusion about metaprogramming in Python. Why use it, when to use it, when to avoid it and what is python missing regarding metaprogramming that other languages have.

Alternative titles

There are some alternative titles I'm considering for the talk. Any favourites?

• Baddass Metaprogramming with Python (Thanks, Ahsanul)
  
• The swiss army knife for metaprogramming in Python
• Metaprogramming tricks for Python programmers
  
• A zoo of Python metaprogramming tools
• Tools and techniques for Python metaprogramming
• Enhancing your code through metaprogramming
• Python metaprogramming tricks for your toolbox

Pycon 2010

The list of scheduled talks for Pycon 2010 is out and they are looking very good. Thanks to all the people involved in making Pycon happen!

I am specially fond of #64. Go check it out!

If you missed Pycon 2009 (I did), you can take a look at what went on here.

As for the Blog Posting Month not all of my posts during the month will be like this. A real one is on the way. Promise!

Blog posting month

November is said to be the (Inter)National Blog Posting Month. The idea is simple: 30 days - 30 posts.

People that read this blog regularly would know that it hasn't been very active lately (More than 6 months without posting). That's just wrong. Let's change it.

Keeping up with the Blog Posting Month should be a good motivator to start writing again. I give you that I am already a bit late as today is November 3rd, so I have some catching up to do. From the technical perspective expect stuff in the lines of: concurrency, new-ish programming languages, emacs, linux, comet, python, algorithms and optimization. However, technical posts take some time to prepare and though I have some half-cooked posts already that should be coming out this month do expect to read some lighter content during this month.

That's it for now. Till tomorrow.

GSoC projects I'm excited about

Today the list of accepted projects for Google Summer of Code was made public. Here's the list of the top 25 projects that I'm personally excited about. Im adding an asterisk to those that either I'm really looking forward to use or that really blew my mind.

Boost

• Graph Partitioning in The Boost Graph Library

• Relations data type *

• Boost.Python py3k support

Django

• Multiple Database Support in Django *

• Model aware validation

• UI improvements for the admin interface

Debian

• Large dataset manager

GCC

• Automatic parallelization in Graphite *

Gentoo

• Portage backend for PackageKit

• Universal Select Tool *

• Tree-wide collision checking and provided files database

GIMP

• Advanced GUI for brush dynamics (GIMP)

Google open source programs

• Build a distributed object-capability system on the Caja platform.

Haskell

• Improving space profiling experience

GNU Project

• Improve "sort" on multi-core systems

• GDB - Python Scripting API Enhancements

• Emacs GDB/MI migration

KDE

• Improving Search and Virtual Folders in KDE4 *

• Plasma Media Center Components

• New Widget Explorer

• PlasMate Editor - An editor for Plasmoids, DataEngines and Themes

Mozilla

• Web pages over rsync **

OpenCog

• Python Interfaces For OpenCog Framework API

• Natural Language Generation using RelEx and the Link Parser

Python Software Foundation

• Apache Axis2 extension for Jython

I know that there are a lot more great projects but I had to settle for 25. Which projects are you excited about and why?

Spiral matrix

Today I found a very interesting set of 'simple' problems. It is a list of Berkeley University's "hardcore tech-interview style riddles and mathematical puzzles". I was specially interested in the Computer Science section (as you might have guessed) and, in particular, one problem caught my attention (probably because of the large matrix).

The problem

The problem reads as follows:

Write a program that will display a "spiral" of NxN numbers, using constant space (no arrays allowed). For example, here's what the spiral looks like for N=10:

 99    98    97    96    95    94    93    92    91    90
 64    63    62    61    60    59    58    57    56    89
 65    36    35    34    33    32    31    30    55    88
 66    37    16    15    14    13    12    29    54    87
 67    38    17     4     3     2    11    28    53    86
 68    39    18     5     0     1    10    27    52    85
 69    40    19     6     7     8     9    26    51    84
 70    41    20    21    22    23    24    25    50    83
 71    42    43    44    45    46    47    48    49    82
 72    73    74    75    76    77    78    79    80    81

Sounds simple enough.

The solution

As I've been reading a lot of "Real World Haskell" lately (and considering the language is great for the task at hand) I decided to code this program in Haskell. If you don't already know Haskell I recommend you to go and learn it on your free time. It is an excellent language with a very unorthodox view of programming (not only functional, but pure!) that will open your mind to a very new and interesting programming style. A good resource for learning Haskell (besides the book, which I highly recommend and will do so with further details in a future post about books) is the classical Gentle introduction to Haskell. But if you prefer a nice colourful website with cool drawings and good info to match the cool design (I know I do!) you can check Learn you a Haskell for great good.

Enough with the language. Into the problem.

To analyse the solution I enumerated some of the matrices, from which matrices of size 4 and 5 were the most useful

15, 14, 13, 12,
4,  3,  2, 11,
5,  0,  1, 10,
6,  7,  8,  9

24, 23, 22, 21, 20,
9,  8,  7,  6, 19,
10,  1,  0,  5, 18,
11,  2,  3,  4, 17,
12, 13, 14, 15, 16

A matrix of size n contains the numbers from n*n-1 to 0. So the next matrix will contain 2n-1 new elements and the rest will be the same elements in a different order. This gives us the idea that the algorithm can be solved recursively.
If we look with more detail into the two matrices outlined above, we can notice that the top row and rightmost column contains all the new elements and that, due to the spiral ordering described in the problem, they will always be located in these positions (there are 2n-1 slots there).

What's left is to figure out how the elements in the previous matrix map to those in the next one and we'll have ourselves a recursive algorithm. We can notice that the first element in the matrix of size 4 is the last element in the sub-matrix formed by removing the new elements from the matrix of size 5. Because of the spiral order the next element to the right in the old matrix becomes the next to the left in the new one and the element that was beneath a number is transposed above it. We can see it as a 90 degree rotation on the old matrix.

The code

Knowing this all that's left is to write the code.
We will need a function that given the position in the n-sized matrix will return the element
that belongs to that position.

spiral :: Int -> Int -> Int -> Int
spiral 0 j n = n*n - 1 - j
spiral i j n
   | j == (n-1) = n*n - n - i
   |otherwise   = spiral (n-1-i) (n-j-2) (n-1)

The first line of this function (after the signature) is one of our base cases: The top row of the matrix is formed by the numbers from (n*n)-1 to n*(n-1). The second definition our second base case: the rightmost column. In this case each element descends from the element in the top right corner (i.e.: n*(n-1) ) one number by row. The rest of the function (the otherwise clause) is our recursive case. On the matrix of size n-1, we are interested in the element that occupies the row n2-i where n2 is the size of the smaller matrix (i.e.: n-1) and the column n2-j-1. Note that the difference between the row and the column is that in the column case we need to substract an extra 1 which refers to the extra columns that appears in the larger matrix. If we don't do this, the transformation would be transposed to the right.

Extra

This code is enough to solve the problem. But to better calculate the results (without having to calculate each index at a time) I provided some extra functions.

-- claculates an index based on the previous matrix
spiral :: Int -> Int -> Int -> Int
spiral 0 j n = n*n - 1 - j
spiral i j n
   | j == (n-1) = n*n - n - i
   |otherwise   = spiral (n-1-i) (n-j-2) (n-1)

-- returns the numbers from 0 to n-1
range :: Int -> [Int]
range n = take n (iterate (1+) 0)

-- returns every possible index of an NxN matrix
matrix :: Int -> [(Int,Int)]
matrix n = [(i,j) | i<-range n, j<-range n]  -- a helper function for the map in printSpiral revSp :: Int -> (Int, Int) -> Int
revSp n (i,j) = spiral i j n

-- returns the result for each index
printSpiral :: Int -> [Int]
printSpiral n = map (revSp n) (matrix n)

-- calculates all spiral matrices from 0 to n
through :: Int -> [[Int]]
through n = map printSpiral (range (n+1))

Does anyone have a better (or different) solution?