RFelix.com

Code Kata Resources

2010-06-19T00:00:00+00:00

Photo by paulpker121

Striving for success without hard work is like trying to harvest where you haven’t planted.

— David Bly

One aspect in becoming a better programmer is actually programming. A lot. Whether you’re learning a new programming language or honing your programming skills, Code Katas are the way to go. They’re ideal because they’re small exercises which don’t occupy too much time, and are fun to do.

I compiled a list of links for myself and thought that it might be of use to other people. Most of them can be done in any language, only the last four are more Ruby specific.

Code Katas:

Bonus

If you’d like to take this concept further and do Code Katas in groups, then you should read Coding Dojo: an environment for learning and sharing Agile practices which explains how to start a Coding Dojo and discusses the experiences of actually creating one.

If you know of any other resources, drop me a line in the comments section. I’ll be sure to update the list and add your name + link for the reference.

Until then, happy practicing.

Git Repo Hosting via SSH

2010-04-06T00:00:00+00:00

Photo by Medmoiselle T

Do you use Git? Great! Do you have a Shared Hosting environment? Or just want to give other people access to your git repositories under one shell account? Then let me introduce you to HostGitRb: Git repository sharing Ruby style.

Features

Easy to install
Git Repository sharing via SSH under one user (ideal for shared hosting)
User permission is based on their public keys
Users can only pull/push Git repos, they can’t login via SSH.

I do know about Gitosis, but I had a few problems installing it on my host, so I did what a respectable hacker would do and created my own stuff. Plus playing with rubies are way more fun than playing with pythons. :)

Because time is precious, here are some shortcuts to help you jump around to the sections you need:

Use Case 1 – Example of how to share Git repos for a University project
Use Case 2 – Example of how to let a one user access multiple repos (even that of a different user)
Reference – Overview of command line options

Installation

It’s easy as pie, just login to your server and install the gem: gem install hostgitrb

Alternatively, clone the HostGitRb repository from GitHub and add the bin/ directory to your PATH.

Use Case 1 – Group Project

I originally made these scripts to share a Git repository with friends for a University project, so I’ll use that as an example to illustrate HostGitRb’s functionality.

On my host, I have a directory that contains all my Git repositories: ~/gitrepos. Under that directory, I created another one called tjs which is a subject I’m taking this semester (translates to Game and Simulation Technology).

The tjs folder contains all the Git repos I want my group to access. There’s actually only one repository in the directory, but hey, who’s counting? It’s called xinkysworld.git (the name of our game).

To give my friends access, I did the following:

Got their public keys (generated via ssh-keygen -t rsa)
Logged in to my server and for each key I executed the following command: hostgitrb --dir ~/gitrepos/tjs --key "ssh-rsa AAAAB3Nza..."
After that they can access the repository like so: git clone rfe@rfelix.com:xinkysworld.git or even git clone ssh://rfe@rfelix.com/xinkysworld.git

Even though they’re using my username to access the repository, they can’t do anything else other than push or pull from the Git repositories under the tjs/ directory. Great! Now they can’t deface my site (yep, they’re evil like that).

Use Case 2 – One User, Multiple Repositories

If you’re a student, your group members might overlap between projects. To allow one person access to different Git repositories, you can set something up that is kinda like GitHub’s structure: git@github.com:rfelix/hostgitrb.git

Say you want to give the user foo access to not only his own repo, but also to another that’s shared between him and the user bar. You can do something like:

Create a directory for him: mkdir -p ~/gitrepos/foo
Create his own repo under ~/gitrepos/foo/project.git
Create a symlink of bar ’s repository in foo ’s directory: ln -s ~/gitrepos/bar/shared.git ~/gitrepos/foo/shared.git
Give his public key permission (from a file this time): hostgitrb --dir ~/gitrepos/tjs --file ~/tmp/foo.pub

Now foo can access whichever repository under his foo/ folder. For example, he can access the shared.git repo via the url (using GitHub’s url for comparison) git@github.com:shared.git

It’s not exactly the <user>/<repository>.git structure like GitHub, but it works.

Reference

Running hostgitrb --help will give you a list of possible options you can use (thanks to Trollop):

> hostgitrb --help
Options:
          --file, -f <s>:  Set path to public ssh key file (default: )
           --key, -k <s>:  Provide public ssh key as a string (default: )
           --dir, -d <s>:  Set full path to directory with git repositories to 
                           allow access to (default: )
          --readonly, -r:  Set access to repositories in --dir to read only
          --nobackup, -n:  Don't make backup of authorized_keys file
--authorizedkeys, -a <s>:  Set authorized_keys file (default: ~/.ssh/authorized_keys)
              --help, -h:  Show this message

They’re pretty much self-explanatory, but here are a few notes:

Use --key when you have the SSH public key is in the clipboard (don’t forget the "" due to spaces)
Use --file when you have the actual public key file on your server.
--readonly makes sure the user can only execute git pull
HostGitRb makes backups of the authorized_keys file it modifies; stop this with --nobackup
--authorizedkeys allows you to change the file that the new permission is added to.

Final Remarks

I’ve put this out in the open source world in hope that this will also be helpful to someone else other than myself. If you have any problems let me know in the comments. Or if you find a bug, please add it to Issues.

Until next time, happy git repo sharing!

The Road to Awesomeness

2010-03-15T00:00:00+00:00

Photo by Nick Owen

Wouldn’t you like to become an awesome programmer?
Be able to excel at your craft and write great code?
I’m sure you do, as do I. But, where do we start?

Well, I found a series of blog posts the other day about being awesome, which is a good start on getting onto this mythical road. The series, written by Jamis Buck, is titled There is no magic, there is only awesome and is summarized in this post.

Any sufficiently advanced technology is indistinguishable from magic.

— Clarke’s 3rd Law

In order to achieve awesomeness, we need to dispel the magic around that advanced technology. We need to understand the how’s, what’s, and why’s of the things we use each day. With this in mind, Jamis suggests four cardinal rules to becoming awesome, each explained in different posts:

What this series basically comes down to is that we should ask the four following questions with every tool, programming language, and library that we use:

What does this do best?
What does this do worst?
Why should I use this in particular?
When was the last time I learnt something new about this?

If any of those questions can’t be answered, then it’s a sign to investigate further and slay that magic dragon.

Actually knowing and being able to apply that knowledge is so much more important than just knowing about. And that is essential to form an opinion about the things we use and answer the above questions. An opinion is crucial to becoming awesome because:

People without opinions are, frankly, boring. They’re pretty much the opposite of awesome.

—Jamis Buck in Know thy tools

And that’s a big NO NO.

It’s also important to note that, even if we’re able to answer those questions, we should continue to learn something new about the tools we use. Jamis suggests we try do that each day by reading something we didn’t know before. Then, integrate that knowledge in what we’re doing, be it in a project we’re working on, playing around with simple code examples, or even blogging about it. Doing this will help cement the newly acquired knowledge. After that, we then need to use it repeatedly so we don’t forget it.

Now that we know the direction of The Road to Awesomeness, the only thing standing in our way is ourselves. It’s now up to each one of us to pick up the torch and go down this road.

Start with reading the posts in the series, then get to answering those questions and follow that yellow brick road to awesomeness. Leave any suggestions or experiences in the comments section.

Until the next post, happy road trip!

Book: Ruby Best Practices

2010-03-07T00:00:00+00:00

UPDATE: The Ruby Best Practices book is now fully available as open source. You can now have access to the book’s source and a PDF version, but seriously think about showing support and purchasing a hardcopy of your own. More info over at the Ruby Best Practices blog (Updated on 17/03/2010)

After learning the basics of Ruby and feeling at ease with the language, it’s time to take it to the next level. It’s time to start writing code like the experts: the Ruby way. Ruby Best Practices is just the book to help you do that, with a friendly tone and lots of yummy code examples for you to chew on and learn.

Read on to find out what to expect from the book and for some reading tips (that I wish I had done) on how to make the most out of it.

Overview

Ruby Best Practices was written by Gregory T. Brown and comes at 298 pages. The subtitle “Increase Your Productivity – Write better Code” pretty much sums what the book is about: taking your Ruby skills to the next level by learning how to write code like the experts, thus increasing your productivity.

The book covers a lot of topics such as (but not limited to): designing beautiful APIs, testing and debugging your code, taking advantage of Ruby’s dynamic features, and how to maintain your projects.

The Price

Ruby Best Practices costs $23.09 on Amazon.com and £14.87 on Amazon.co.uk (around €16). You also get access to the online version of the book for 45 days from Safari Books Online.

Gregory Brown is also open sourcing the book, so you can download the chapters yourself for free to see if it’s worth buying. I think it is. You can get the chapters from the RBP Blog along with other high quality Ruby-related articles.

What You Get

At 298 pages, you get 8 chapters:

Driving Code Through Tests – talks about code testing, mocks and stubs, and TDD.
Designing Beautiful APIs – shows what Ruby features help you create elegant and easy to use APIs.
Mastering the Dynamic Toolkit – explains Ruby’s many reflective capabilities and how to use them.
Text Processing and File Management – tricks and tips to help you manage and process files.
Functional Programming Techniques – goes through some functional techniques that can help you.
When Things Go Wrong – mentions ways to hunt for bugs when your program explodes.
Reducing Cultural Barriers – explains various methods to make your apps internationally friendly.
Skillful Project Maintenance – shows you and explains how Ruby projects are typically structured.

And 3 appendices:

Writing Backward-Compatible Code – useful for writing apps that need to work with any Ruby version.
Leveraging Ruby’s Standard Library – some libraries you might not know about that can help.
Ruby Worst Practices – a collection of bad examples to learn from and avoid.

The Good

Real Examples. The code examples use throughout the book were extracted from actual open source projects. This is really great because you get to see how other people are actually solving problems, rather than just theoretical and abstract examples.

Practice Code Reading Skills. Each chapter starts off with some sample code taken from an open source project, which you may not understand at first. This is a good exercise at reading other people’s code, which is essential to becoming a better programmer. Once you get a grasp of the problem, Gregory Brown then goes into more detail and explains various techniques that can be used to solve that problem.

Nice read. I enjoyed the way the book was written. Gregory Brown writes in an easy-to-understand way, with a friendly “voice” which makes you feel like he is in the trenches with you. Another thing I appreciated was that each chapter ended with a few bullet points summarizing the covered topics and offers some advice on when you might want to use some of them. (Check Tip #2 to make the most out of the examples).

The Bad

There’s not much I didn’t like about this book, only a few nitpicks really.

Lost interest when I got to Chapter 7. Although this is not the book’s fault, rather it was me that wasn’t really interested in that chapter (“Reducing Cultural Barriers”) to begin with. I just read it half way and then jumped to the next chapter which renewed my interest. (Check Tip #1 to avoid this).

Long examples with a lot of baggage. The examples presented in the book, namely the ones at the beginning of each chapter, are sometimes long and need a bit of context. I actually think this is good, but some might not like it. What it comes down to is: this is not a cookbook for copy-and-pasting solutions straight into your project. The book tries to show you the many tools Ruby gives you to solve your problems, which you then have to transpose into your project and think about it.

Extra: Reading Tips

Here are a few reading tips that will help you make the most out of the RBP Book:

Read the most interesting chapters first. Each chapter is fairly self-contained so read the chapters in any order. This way you won’t rush through reading Chapter 1 just to get to Chapter 2, for example.
Reread the code examples. Once you’ve finished reading a chapter, before proceeding to the next, go back and reread the initial example that got you started. Make sure you now fully understand it.
Read your book next to the computer. Take your time reading each chapter and pause often to actually try out the new concepts you’ve learnt. And most importantly, play with the code, have fun!

And The Verdict

If you’re really interested in honing your Ruby coding skills, then this book is for you. It will show you how “real” Ruby code is written, what techniques you have at your disposal while tackling those hard-to-solve problems, and at the same time practice your code reading skills.

Even though the book is being open sourced, I still think you should support the hard work of a fellow programmer and buy a hardcopy. Personally, I prefer holding a book in my hand while reading, then again, I might be a bit “old-fashioned” that way. Plus, if you buy it then you’re showing O’Reilly that it’s worth open sourcing their books.

Hope you enjoy it. Happy reading!

Bruce Lee, Water, and Programming

2010-01-26T00:00:00+00:00

Empty your mind, be formless, shapeless – like water. Now you put water into a cup, it becomes the cup; you put water into a bottle, it becomes the bottle; you put it into a teapot, it becomes the teapot. Now water can flow or it can crash. Be water, my friend.

— Bruce Lee in an interview

When Bruce Lee said this, I’m sure he wasn’t thinking about programming. He was a great martial artist who knew his shit, but little did he know that us programmers can also apply his wisdom to our craft.

Now that I’ve finished my Programming Language Pragmatics class and discussed programming languages like Algol, ADA, Lisp, Scheme, Prolog, Smalltalk, C, C++, Java, C#, etc., I’ve come to realize that there are a shit load of languages out there, each with their own set of pros and cons. Some thrive, others perish. Having this in mind, we can’t put all our eggs in one basket and only learn one language. What if it flops?

If there’s any one constant thing about the IT industry, is that there is no such a thing as constant. We can rely on its unreliability. What’s awesome and great today, can suck and disappear tomorrow.

So what is a programmer to do?

Bruce Lee has the answer: be water, my friend.

Empty your mind – we shouldn’t treat any programming language like a religion. Just because it’s Turing Complete, it doesn’t mean it should be used everywhere. You could build a web app in C++, but that would be like taking your teeth out with a hammer.

We need to learn more than one language. More than two even. The more different, the better! It will help us to make informed decisions about the most suitable tool for the job, plus it will also help expand our minds and teach us to think differently. Be formless, shapeless – like water. Confining ourselves to one language will only make us stiff.

Notice that the stiffest tree is most easily cracked, while the bamboo and the willow survive by bending with the wind.

— Bruce Lee

We need to adapt, be dynamic, and have more than one language under our belt. We need to become a cup when we’re in a cup; become a bottle when we’re in a bottle; become Ruby when we’re in Ruby. Be able to flow or crash when need be.

This doesn’t mean we should learn every language under the sun, jumping on the latest technology fad bandwagon like a dog after a frisbee.

We need to learn at our own pace – we’re all different. It doesn’t have to be one language a year; maybe one every two years is more suitable.
When we start to feel comfortable in a language, maybe that is a sign we should try another one.

The most important is not the language you learn, it’s what you learn from the language.

Program a lot in Java? Try C.
Sick of C++? Try Ruby!
Tired of juggling objects all day? Try something more functional like Scheme, Lisp, or hardcore Haskell.
Hell, be strategic about this: go for Clojure for something lispy; Scala or Erlang for something akin to Haskell.

At the moment I’m focusing on improving my Ruby-Fu, but afterwards I would love to look into Haskell or Scala.
What about you? What languages do you plan on learning? Drop me a comment, lets have a chat.

Whatever you do, remember to bend with the wind and

Be water, my friends.

Jekyll Extensions -= Pain

2010-01-19T00:00:00+00:00

UPDATE: jekyll_ext is now a gem and easy to install. See Installation. (Updated on 21/06/2010)

UPDATE: I’ve created a wiki page over at GitHub to list all the extensions that use jekyll_ext. At the moment it’s a bit sparse, but hopefully that will change. Add your creations to the Extensions page. (Updated on 24/03/2010)

If you’ve been using Jekyll for your blog, you no doubt have needed to extend it in some way or another. Like me, you probably have your own forked version of Jekyll where you keep your customizations. This was fine in the beginning, but after a while it became kinda painful:

You can’t use the Jekyll gem anymore because you’re using your own version. Either make that a gem and use it, or just clone the repo and symlink it. You now have to worry about maintaining your fork when a new release comes out.
Forget about sharing your extensions with others. Actually, you can, using Git and its branching capabilities, but having to resolve conflicts takes the pleasure away.

Wouldn’t it be great if you could extend Jekyll without creating your own fork?
Wouldn’t it be even better if we could share and reutilize those extensions?

Well, wait no more…

Ladies and Gentlemen, may I present jekyll_ext!

I’ve come up with a solution that leverages Ruby’s metaprogramming superpowers and its Open Class mechanism to give you:

Extensions that are local to the blog directory, stored under the _extensions dir
Extensions that can be reutilized and shared
All this without modifying the Jekyll gem codebase

As a bonus, this solution comes with 3 Aspect-Oriented Programming style helper methods (before, after, and around) to facilitate extension creation and also hide some of the metaprogramming ~~magic~~ code.

Installing jekyll_ext

gem install jekyll_ext

Now you just need to create the directory _extensions in your blog where all your extensions will live. Any .rb file in that directory or subdirectory will automatically be loaded by jekyll_ext.

IMPORTANT: Instead of using the jekyll command, you should now use ejekyll instead (which is just a jekyll wrapper that loads your extensions).

Extending Jekyll with jekyll_ext

jekyll_ext attempts to load the file jekyll_ext.rb located in the _extensions directory of your blog. That file works as an entry point to load all the extensions that will be used when generating the site for your blog.

The idea here is that you can use Ruby’s Open Class mechanism to define new methods in Jekyll classes, or even replace them if need be. You can then use the AOP style helper functions I wrote to intercept method calls and add functionality to existing Jekyll class methods without actually changing the Jekyll code base:

before can be used when you want to execute some code before a method is invoked.
after can be used when you want to execute some code after a method is invoked.
around can be used to control the execution of a method and to change the result returned by that method. With this you can execute code before and after the original method plus change the method’s result.

For a more general overview on how to use these methods you can have a look at the specs.
The extensions I’m using for my blog are also available on GitHub (my_jekyll_extensions) which you can use in your own blog or just as example code to get you started.

Helper Methods in Detail

Here’s a more detailed explanation of how you can actually use the helper methods:

AOP.before(<Class to intercept>, <Name of Method to intercept>)
Executes the block you pass to it before the method you supply is called. Your block receives the following as parameters:
1. The receiver of the intercepted method (the class’s instance)
2. An array with the arguments that were passed to the method
AOP.after(<Class to intercept>, <Name of Method to intercept>)
Executes the block you pass to it after the method you supply is called. Your block receives the following as parameters:
1. The receiver of the intercepted method (the class’s instance)
2. The method’s result
3. An array with the arguments that were passed to the method
AOP.around(<Class to intercept>, <Name of Method to intercept>)
Executes the block you pass to it around the method you supply, i.e. you control when the original method gets executed and can change its result. The value returned by the intercepted method will be whatever the last line in the block you supply evaluates to. Your block receives the following as parameters:
1. The receiver of the intercepted method (the class’s instance)
2. The method’s result
3. An array with the arguments that were passed to the method
4. Lambda/Proc that corresponds to the method that’s been intercepted. You must explicitly invoke the call method on this proc to execute the intercepted method.
5. Lambda/Proc that can be used to explicitly abort the method. Whatever you pass when invoking the call method as arguments will be returned by the intercepted method.

Once again, you can use my jekyll extensions to see how all this comes together and allows you to extend Jekyll without touching its codebase.

Hope this makes extending Jekyll less painfull for you as it did for me.
If you have any problems, drop me a comment and I’ll try help you out as best I can.

Happy Jekyll extending!

Book: Don't Make Me Think!

2010-01-07T00:00:00+00:00

I can’t remember why I bought this book, but I’m glad I did. The author, Steve Krug, is a web usability expert and basically wrote about almost everything he knows about web usability (so he says on his website).

Even though this second version of the book was written way back in 2005, I found its content to still be applicable today. The only chapter that might be a bit outdated is Chapter 11: “Accessibility, Cascade Style Sheets, and You”. Nowadays I think everyone uses CSS and don’t bother with html table based layouts anymore. Other than that little nitpick, the rest of the chapter, and book, is relevant and a good read.

It’s Not Rocket Surgery!™

The subtitle is “A Common Sense Approach to Web Usability” which I think portrays the book quite well. The author explains many usability concepts in an easy to understand way, always showing things from a user’s perspective.

Don’t think of it as a rule book, it does not tell you how to build sites “the right way”, nor does it bad mouth other websites. What is does do, is provide you with a set of guiding principles that you should take into consideration when designing your website. These principles are explained in a way that makes sense, and is accompanied by many examples and illustrations to show them in action. There are also many real world website designs that the author uses to show what works, what doesn’t, and why. All of this comes at 184 pages, so it’s a quick read, plus it’s colorful and visually appealing which transmits a friendly feeling.

Not web apps, websites

Even though the book is about web usability, it doesn’t discuss web applications and focuses only on websites. Still, many of the guidelines presented in the book are also applicable to web applications. It essentially gives you a behind-the-scenes view of the world from a user’s perspective, with a lot of tips on how to enhance the various elements of your site. This type of information is invaluable, whether your designing web applications or websites.

Lesson #1

The most important thing I take away from this book is exactly its title: Don’t Make Me Think! It might seem silly, but only after reading the book did I realize the importance of designing your websites in the most clear and simple way possible. Forget about counting clicks, worry more about reducing the number of “???” (question marks) that popup in a user’s head. It might only take 3 clicks to do something, but if it confuses the user, it won’t matter. Once you realize there is no such thing as an “average” web user, things start falling into place.

Lesson #2

The second most important lesson for me is: do usability tests early, and do them often. Such things like the “average web user” and “the right way to design websites” are myths. They don’t exist. It all depends on the context. Just because you like something, it doesn’t mean that everyone else will like it too. Want to see if your design works? Test it with actual people!

Complicated tests aren’t necessary, nor is it essential to find your “target user”, and you don’t need to spend a lot of money or time. Steve shows you how to conduct simple, no hassle web usability tests which is accompanied by a sample test session so you actually get to “see” how it’s done.

Verdict: Recommended

The only possible reason to not buy this book right now is because another 5 years have almost passed and a new version might be coming (1st Edition published October 2000; 2nd in August 2005). So it’s up to you if you want to wait. But, if you think it can come in handy right now, then go ahead and order the book! One thing is for sure, your users will appreciate it!

4 Queens Problem with Continuation-Passing Style

2009-12-28T00:00:00+00:00

(This is post #2 of the Continuations Explained with Ruby Series)

In post #1 of this series, I showed you how to save the computations of a factorial and how to manipulate the base condition. As I said, we can’t do much with that, but it is the basis for what we’re going to be looking at in this post.

4 Queens Problem

The problem we’re going to solve in this post is the 4 Queens problem, which is just a simplified version of the 8 Queens problem. The idea is that we have a 4×4 chess table, and 4 Queen chess pieces. We now have to position those 4 Queens in such a way that there is only one queen per line and none of them are able to capture any other using standard chess moves.

Detecting Collisions

To detect a collision between Queens, we need to check the columns and the diagonals. Collisions can be easily checked if we assign index positions to chess board matrix and keep 3 separate collision lists: one for columns and two for the diagonals. We update the collision lists whenever a Queen is placed. For the column list, we simply add the Queen’s column position; for one diagonal, we add the sum of the Queen’s line with the Queen’s column to the list (called Diag+); and for the other diagonal, we add the subtraction of the line and column position to the list (called Diag-).

For example, take a look at the above image. Lines and columns are labeled from 1 to 4. The Diag+ elements are in the lower triangle in dark grey, and the Diag- elements are in the upper triangle in white. In table (b), the Queen on line 1 can capture the Queen on line 2 because summing their line and column position both result in the same number (4). Queen on line 2 collides with Queen on line 3 because of Diag-: subtract their line and column positions and you get the same value (0). Queen in line 1 and line 3 also collide because they have the same column position.

Recursion

One way to solve this problem is to employ backtracking depth first search. Think of backtracking as being just like recursion, except that you’re not sure if the path you took is the right one, so you need to be able to go backwards and take another path if need be.

Here’s a possible recursive solution to this problem:

def queens_collide?(i, j, col, diag_plus, diag_minus)
  col.include?(j) || diag_plus.include?(i + j) || diag_minus.include?(i - j)
end

def place_queens(n, i, j, col, diag_plus, diag_minus)
  if i.zero?
    col
  elsif j.zero?
    false
  elsif queens_collide?(i, j, col, diag_plus, diag_minus)
    place_queens(n, i, j - 1, col, diag_plus, diag_minus)
  else
    queen_placed_ok = place_queens(
      n, i - 1, n, 
      col + [j], 
      diag_plus + [i + j], 
      diag_minus + [i - j]
    )
    if queen_placed_ok
      queen_placed_ok
    else
      place_queens(n, i, j - 1, col, diag_plus, diag_minus)   
    end
  end
end

def queens(n)
  place_queens(n, n, n, [], [], [])
end

puts queens(4).inspect
# >> [3, 1, 4, 2]

I Want More

The code I just presented to you works fine, but what if we didn’t like that answer? What if we wanted to compute another solution? And another one after that?

The key here is line 13, which represents the backtracking checkpoint. It’s the point of the algorithm where, if the path taken by the recursion leads to a wrong answer (collision or if the end of the table is reached), then it has to backtrack up until that deciding point and choose another path. Also notice that the code in the line I mentioned is a non tail-recursive call, meaning that the line is a dependency which uses the stack to store intermediate results.

CPS FTW

The idea here is to make the dependencies explicit and thus avoid the usage of the stack, because once the method finishes it’s computation, all the intermediate results disappear along with the call stack. And we want access to those saved computations, so we can use them to calculate other possible solutions. To do that, we’ll transform the place_queens recursive function into a tail-recursive one using the Continuation-Passing Style technique by making the implicit computations, which are stored in the stack, explicit using anonymous functions (lambdas):

$queens_continuation = nil

def queens_collide?(i, j, col, diag_plus, diag_minus)
  col.include?(j) || diag_plus.include?(i + j) || diag_minus.include?(i - j)
end

def place_queens(n, i, j, col, diag_plus, diag_minus, continuation)
  if i.zero?
    $queens_continuation = continuation
    continuation.call([])
  elsif j.zero?
    continuation.call(false)
  elsif queens_collide?(i, j, col, diag_plus, diag_minus)
    place_queens(n, i, j - 1, col, diag_plus, diag_minus, continuation)
  else
    queen_placed_ok = place_queens(
      n, i - 1, n, 
      col + [j], 
      diag_plus + [i + j], 
      diag_minus + [i - j],
      lambda do |r| 
        if r
          continuation.call(r + [j])
        else
          place_queens(n, i, j - 1, col, diag_plus, diag_minus, continuation)
        end
      end
    )
  end
end

def queens(n)
  place_queens(n, n, n, [], [], [], lambda { |r| r })
end

puts queens(4).inspect
# >> [2, 4, 1, 3]

This code still produces a correct answer, even if it’s not the same as the 1st recursive version.

Now for the fun part. The global variable $queens_continuation contains the final continuation of the method. In other words, after calling the function, not only do we get the results like normal, but we now have access to the computations that were performed to reach it.

Therefore, if we call the continuation passing an empty array, we’ll get the same answer:

puts $queens_continuation.call([]).inspect
# >> [2, 4, 1, 3]

If you take a look at the continuation we create at line 21, more specifically the if statement, we check if the argument r is true, in which case the lambda just calls the previous continuation with a list to be concatenated as the result. But if it’s false, then it’s because it hasn’t gotten to a valid result yet, so it continues to calculate Queen positions.

So, with access to the final continuation when the function call finished, we can do some interesting stuff. Say that you don’t like the first result and want another one. We just need to call the continuation with false and it’ll think that it the Queens have collided and will calculate another solution for us:

puts $queens_continuation.call(false).inspect
# >> [3, 1, 4, 2]

And once again, when it returns, we have our solution plus access to its computations in $queens_continuation. So if we’re still not happy with the result, we can call the continuation again with false. Although, this time we ran out of solutions:

puts $queens_continuation.call(false).inspect
# >> false

But if we had initially called queens(8), we’d have more solutions to go through. But I’ll leave that for you to try: fire up IRB, copy-and-paste the above code, invoke queens(8), and see how many possible solutions exist by passing false to the continuation lambda in $queens_continuation.

Moral of the Story

By making the dependencies of a normal recursive function explicit and removing the usage of the stack, we have the capacity to reutilize the previous computations and calculate more results, just like Prolog. If the compiler/interpreter is sufficiently smart to optimize tail-recursive functions, we also gain a performance boost! The only problem is Tail Call Optimization (TCO) is only done in some Ruby implementations: JRuby (limited) and YARV (not enabled by default).

I hope you found this as interesting as I did when my teacher explained it to the class. I don’t know if I’ll ever need to do something like this again, but I found it really cool and wanted to share this with you all (even if I’m the only reader of my blog =).

If you have any questions, please, don’t hesitate and drop me a comment.

My Jekyll Extensions

2009-12-21T00:00:00+00:00

UPDATE: I have extracted my customizations into portable extensions using that you can use in your own Jekyll-powered blog. Read Jekyll Extensions -= Pain for more information on how to use jekyll_ext to extend Jekyll without modifying the Jekyll gem codebase. (Updated on 19/01/2010)

I’ve been getting some of traffic from my listing in the Jekyll Sites page, so I take it that people are interested in the extensions I made to get Jekyll to fit my needs. In this post I’ll explain some of the modifications that I did and how to use. I will also point out the modifications I made to the Jekyll code base, in case you wan’t to incorporate some specific changes in your own customization.

Category Listing

Jekyll by default only allows you to get a list of posts that belong to a category if you specify that category name: site.categories.CATEGORY. But what I also wanted to do was iterate through the all the categories I have in order to generate a category/topics page.

After stumbling around the Jekyll code base and messing with things, figuring out what code does what, I managed to do exactly what I wanted. You can see the results for yourself in the Topics section of this blog. The alteration was actually quite simple (after a bit of fiddling), you can find the code in lib/jekyll/site.rb under the following methods: site_payload and make_iterable.

To use this feature, all you need to do is iterate over site.iterable.categories. You then have access to the category’s name and the posts that belong to it by accessing the properties name and posts. Here’s part of the code I used to generate my Topics for a complete example: Category/Topics Listing Liquid Markup (Sorry for linking to a Gist, but I wasn’t able to properly display that code here due to my failed attempt at escaping the liquid markup I’m trying to show you).

Shorten Filter

I wanted my home page to display just the most recent post, and then below it display the titles of the other posts in chronological order (this is a blog after all). But, because some titles might be a bit long, I wanted a way to limit the number of words that can appear in a title and only show some words from the beginning and end with “…” for the middle. For example, my post title “Syntax Highlighting Code in Posts with Textmate” when passed to the shorten filter becomes “Syntax Highlighting Code…with Textmate”.

The code for this filter can be found under the method shorten in lib/jekyll/filters.rb. Just call it like any other filter and pass the maximum number of characters as its argument, like so: {{ post.title | shorten: 45 }}

Categories in _posts

I made this alteration because I wanted to use categories in my blog, but I didn’t want them spread around in various directories. Now all my posts live happily under their own category in the _posts directory. This feature was implemented easily in 4 lines of code, which can be found in lib/jekyll/post.rb under method initialize (lines 41-45).

Pretty URL but without the Category

At the time I setup my blog, I was so busy hacking away that I completely missed that you could specify the exact permalink structure in your “_config.yml” file. So my customization has an additional permalink style, which can be found under the method template in lib/jekyll/post.rb, called “pretty_no_category”. At least now what appears under the permalink option in “_config.yml” is permalink:pretty_no_category rather than permalink: /:year/:month/:day/:title.

Future Extensions

In the future, I plan on adding the same support for Category iteration to Tags. This should be implemented quite easily seeing as I already have a helper function (make_iterable mentioned in Category Listing) that I used for the categories. Other than that, Jekyll serves its purpose just fine!

I didn’t put the code for my site on GitHub because I didn’t think that people would be interested in it. But if you would like to check it out, drop a comment. If I see there’s enough interest, I’ll put it up.

You Know You're a Geek When...

2009-12-03T00:00:00+00:00

While driving back and forth from classes at University, every now and again I see a car with a GPL sticker on.

Now, you know you’re a (portuguese) geek when…

The first thing that pops into your head whenever you see that sign is General Public License rather than “Gás de petróleo liquefeito” (Liquefied petroleum gas in english).

(And it happens every time…)

Introduction to Continuation-Passing Style

2009-10-09T00:00:00+00:00

This post #1 of the Continuations Explained with Ruby Series

Photo by gadl

Recursion & Tail-Recursion

For those of you that are reading my blog, you already probably know what recursion is. Still, I would like to share with you one of my favorite definitions of recursion: “Definition of Recursion: If you still don’t get it, see the definition of recursion.”

Now, it is generally agreed upon that using recursion tends to be a lot slower and occupies a lot more memory that the iterative version. This isn’t always the case. It is more accurate to say that a naive implementation of iteration is usually more efficient than a naive implementation of recursion.

The major advantage that iteration has over recursion is that it doesn’t allocate as much space on the run-time stack to store local variable and bookkeeping information.

This advantage can be minimized if an “optimizing” compiler is used, in particular, one for a Functional Programming Language which is able to generate excellent code for recursive functions, especially for tail-recursive functions.

A tail-recursive function is one that doesn’t have any additional computations along with the recursive call. In other words, the function’s return statement is just another call to the function itself, without any pending operations. Let’s take a look at some code to better illustrate the point:

# Normal recursive version of Factorial
def fact_r(n)
  return 1 if n == 0
  # Here's the pending operation with a call to a recursive function:
  n * fact_r(n - 1) 
end

# Tail-Recursive version of Factorial
def fact_tr(n)
  def fact_aux(n, accumulator)
    return accumulator if n == 0
    # No pending operations here, only a call to the recursive function:
    fact_aux(n - 1, accumulator * n)
  end
  fact_aux(n, 1)
end

The tail-recursive function is much faster because the compiler doesn’t need to dynamically allocate space on the stack for the pending operations. It can just reuse the space belonging to the current iteration when the tail-recursive function is called.

Transforming Non-Tail-Recursive functions into Tail-Recursive ones

By using Continuation-Passing style, a compiler for a functional language can automatically optimize a non-tail-recursive function into a tail-recursive one, which, in turn, allows it to apply further optimizations.

But before we continue, we need to know what a Continuation is. According to Wikipedia, a Continuation is an abstract representation of the control state. In other words, they allow you to represent computations with dependencies in an explicit manner.

Now, let’s take a look at the fact_r function from the above example, more specifically, the last line of the function: n * fact_r(n - 1)

What we see here is a clear example of a computation with dependencies: fact(3) has to wait for 3 * fact(2) to be computed, which in turn needs to wait for 2 * fact(1) to be computed, which still needs to wait for 1 * fact(0) to be computed.

Now, how can remove those dependencies? First, we have to add a new argument to the function that will contain the continuation. Then, instead of performing the operation that causes the recursive function to wait, we wrap it in a lambda to be calculated later on. Only when we get to the base condition of the recursive function do we actually execute the continuation, which will then calculate the result and present it to us. This is easier to see in an example:

def fact_cps(n, c)
  if n == 0
    c.call(1)
  else
    fact_cps(n - 1, lambda { |r| c.call(n * r) })
  end
end

> fact_cps(5, lambda { |r| r })
120

What we’re doing is transferring the control to another function, either fact_cps or to the continuation c, without leaving any dependent computations in the stack.

As I said earlier, using CPS results in a tail-recursive function, so the stack doesn’t grow like a normal recursive function. But, because we use lambdas and chain them, they get allocated in the heap instead. Once used, the Garbage Collector will then clean up after us.

First steps towards imitating Prolog’s backtracking capability

Now let’s have some fun messing around with CPS: when n reaches 0, what would happen if we saved the continuation in a global variable?

def fact_cps(n, c)
  if n == 0
    $end_fact_cps = c
    c.call(1)
  else
    fact_cps(n - 1, lambda { |r| c.call(n * r) })
  end
end
> fact_cps(5, lambda { |r| r })
120

After calling the new fact_cps for the first time, the global variable $end_fact_cps contains a reference to the continuation that was used, i.e. we now have access to the computations that were performed while calculating the factorial of 5. We can now play around with them:

> $end_fact_cps.call(1) # 5 * 4 * 3 * 2 * 1
120
> $end_fact_cps.call(2) # 5 * 4 * 3 * 2 * 2
240
> $end_fact_cps.call(3) # 5 * 4 * 3 * 2 * 3
360

Calling the saved continuation with 1 makes it calculate the result as if we were calling fact_cps with 5. When we call it with 2, or 3, what we’re doing is changing the value that’s used when the base condition of the recursive function is reached. So, instead of calculating the factorial of 5, we calculate the double and the triple of the factorial of 5.

Now, I admit this is nothing special, but it’s the basis for what we’re going to explore in the next blog post in the series. We’re going to be doing something similar to create a recursive backtracking function that will allow us to produce different solutions to the 4-Queens problem (simpler version of the 8-Queens problem) depending on user input – something that Prolog does easily.

I hope you were able to understand how to use Continuation-Passing style to explicitly represent computations with dependencies in a recursive function.

If you have any questions, I’ll gladly try and answer them. Just drop me a comment!

That’s it for now, hope to see you here for the next post in the series where we’ll do a lot more interesting things! Until then…

Continuations Explained with Ruby (Series)

2009-10-09T00:00:00+00:00

In my PLP class (Pragmática das Linguagens de Programação/Programming Language Pragmatics) we’ve been talking about continuations in Scheme and how they allow us to do some pretty interesting stuff.

As they say, in order to understand something properly, you’ve gotta be able to explain it to someone else. So I’m going to give it a shot and try to explain what Continuations are and how they can be used using Ruby as my language of choice.

Before we continue, let me just get a few things straightened out:

I do not claim to be an expert on this subject, so if you happen to find an error, please let me know. I’m just explaining what I learnt in class and by reading up on it (Programming Language Pragmatics book by Michael L. Scott and Wikipedia).
I don’t plan to cover everything about continuations. For the moment I’m just going to focus on explaining Continuation-Passing style (CPS) using Ruby. Other things like Ruby Fibers or Call-with-Current-Continuation (call/cc) won’t be discussed for the time being (but may come at a later stage).

Introduction to Continuation-Passing Style
Recursion vs. Iteration; Tail Recursion; Transforming a non-tail recursive function into a tail recursive one using CPS; Saving computations and avoiding the stack (kinda like Prolog).
4 Queens Problem with CPS
4 Queens Problem; Recursive Solution; Solution using CPS that uses backtracking like Prolog and is capable of returning more than one solution (without duplicating calculations).

Game of My Life

2009-09-26T00:00:00+00:00

Last week the teacher of my DDJ class (Desenho e Desenvolvimento de Jogos/Design and Development of Games) asked us a simple question: what is the game of your life and why? We were then sent home to think about it and prepare a quick, 4 minute presentation on it.

At first, I wasn’t sure what game I was going to choose, seeing as I don’t play that much. But of all the games I’ve played, which one did I really like? Which one was my favorite of all? Which one did I have the most fun playing?

After a few minutes, a name just drifted into my head…
Solid Snake.

What follows is the text that I wrote to sort out my ideas and to help prepare the basis for my presentation. I had to present it in portuguese, so it’s not exactly what I said, but very close. The images you see to the right are the slides I made to go along with the presentation.

So, without further ado…

I don’t only have one game of my life, per say. I have four games of my life, and they’re all part of the Metal Gear Solid series. I like MGS so much that I saved money for a year and a half just to buy a Playstation 3 because I knew MGS4 would come out exclusively for it.

Why do I like this game so much? Three reasons:

1. Stealth

MGS popularized the Stealth Action video game genre. You sneak around, trying to evade all the enemies. You can take them out, or you can just try go around them and avoid confrontation. You do all this in a Ninja like fashion; the only thing missing is a sword. In the more recent games, you now have camouflage to help while moving around undetected.

I just think that the game not forcing you to kill everyone is really awesome. I mean sure, killing the enemy is pretty fun, but not making it obligatory is just as fun and is actually harder to do.

2. Story line

The story behind Metal Gear Solid, in my opinion, is just great! It talks about so many different things: it has secret military conspiracy theories, nuclear weapons, war, cloning, artificial intelligence, censorship, and much more. I admit that it gets bit complex at times, but that’s exactly what I like about it.

3. Cinematic

Playing MGS is just like watching a movie, except that you get to control the actions of the main character. It has huge and entertaining cut scenes which tell the story. You just get so involved in the game and in the cut scenes that time just flies by without you noticing it.

For me, the worst part of the cut scenes is that it’s always during that time when people interrupt me – either the phone will ring, or someone will want to talk to me – and I wouldn’t be able to pause it. Thankfully, MGS4 has introduced Pause during the “mini movies” which is really helpful. Before that, I had to not save the game and then replay the last bit just to watch the cut scene without being interrupted.

What about you? What’s the game of your life and why? Drop me a line in the comments or a link to your own blog post.

RFelix.com: Reloaded

2009-09-25T00:00:00+00:00

Hi there! It’s been quite a while since my last post (15th of March). Things got a bit hectic with all the university class projects and my internship work. That’s life I guess.

I admit that I’ve neglected this blog quite a bit. I started it at the beginning of the year, but kept the main page of the site pointing to my about page rather than the blog. I just never really took it seriously.

Well, things have now changed…

Welcome to the new and improved RFelix.com!

The blog has been promoted and is now a first class citizen!

I’ve completely changed the layout. Rather than use a predefined template, I created my own simple theme. This is what is used to look like:

I just never really liked it, it just wasn’t me. That’s why I needed to create my own thing, make this whole space more personal.

Now that I think about it, it was horrible. Yuck.

I’ve also stopped using Wordpress and started blogging like a hacker using Git and my own custom version of Jekyll.

Posting Schedule

I don’t have as many subjects this semester as I had the previous years, but I also have to work on my master’s dissertation, so that will consume a lot of time.

I’m not going to commit myself to a schedule, but my goal is to at least post one decent entry per week. I’ll probably write about:

My classes
My dissertation
Other projects I’m working on
Or any new things I’m learning about

Arrivederci

For now, that’s it. I hope to see you around here more often.

And please, if you have any thoughts about the new theme or blog, any bugs, feel free to write a comment. Especially seeing as I’ve really only tried viewing this site in Safari 4 and Firefox 3.5, any help on that front is greatly appreciated.

Until the next post…

Memoization with Reflection in Ruby

2009-03-15T00:00:00+00:00

Since my classes started, in Programação Avançada (Advanced Programming) we have been talking about Reflection, using Lisp and Java for the examples. Now, Ruby is well know for it’s Metaprogramming magic, so, being the geek I am, I was anxious to apply some of the things we discussed in class with Ruby.

Because this post is so long please feel free to jump around and view only the parts that interest you the most. Here’s a mini table of contents to help you out:

Reflection
Self-Modification
Self-Modification and Memoization with Lisp
Self-Modification and Memoization with Java
Self-Modification and Memoization with Ruby
Simple Ruby Code Benchmark

Reflection

Reflection, as per Wikipedia, is a particular kind of Metaprogramming. It is the process of reasoning about yourself and acting upon oneself. So basically it gives you the power to observe your own computer program during it’s execution and, in some cases, allow you to modify it.

Reflection can be divided into two categories:

Introspection – the ability to examine the structures of the program in execution from within itself;
Intercession – the ability to actually modify the behavior of the program in run-time.

Intercession can still be divided into another two sub-categories:

Self-Modification – the ability to modify one’s own structure;
Intercession – the ability to to modify the semantics of the language within the language itself.

Self-Modification

The teacher in class used the recursive Fibonacci function – fib(n) – as an example. Because of it’s recursive nature, it’s extremely inefficient to calculate fibonacci for big values of n. To speed up it’s execution, the teacher defined a memoization function and applied it to fib(n). So it turns the original fibonacci function from an exponential beast into a linear calculation. It’s pretty awesome to see how much time is saved by keeping the intermediate values and how that influences the execution time.

So now let me show you how it’s done in Lisp first, then in Java, and finally in Ruby.

I won’t spend too much time explaining the Lisp and Java code samples, they’re here more for illustrative purposes than anything else. But if you’re really interested in these samples and would like a detailed explanation, please drop me a comment as I’d be glad to explain them to you.

Please note that the following 2 code examples I’m going to show you weren’t programed by me; they were taken from my classes powerpoint slides which were created by my teacher, António Leitão. Only the Ruby code is 100% mine =)

Lisp

Let’s take a look at the Fibonacci function in Lisp:

(lambda (n) 
	(if (< n 2) 
		n 
		(+	(fib (- n 1))
			(fib (- n 2)))))

The memoize function looks like this:

(defun memoize (lambda-form)
	(setcar (cddr lambda-form)
			`(let ((result ,(caddr lambda-form)))
				(setcar (cddr ',lambda-form)
					`(if (eql	,',(caadr lambda-form)
								',,(caadr lambda-form))
						',result
						,(caddr ',lambda-form)))
				result)))

Pretty scary right? I’m not going to explain it, it’s just here for me to scare you and show you how cool Ruby is.

But what this function does is it changes the fib(n) function so that every time it has to calculate the fibonacci of some n, it modifies itself. It does this by adding a new If condition to the beginning of the function body, checking if n is equal to some n that was previously calculated. If so, it returns the value straight away. If not, the function calculates the value recursively and modifies itself once again.

Java

Java doesn’t allow destructive modification of programs at run-time like Lisp does. But what it does allow you to do is modify the program before the class is loaded by the Java Virtual Machine – aka Load-Time. This is done by using an external library, in this case, Javassist.

The Fibonacci in Java looks something like:

public class Fib { 
	public static Long fib (Long n) { 
		if (n < 2) { 
			return n; 
		} else { 
			return fib(n - 1) + fib(n - 2); 
		} 
	} 
}

A bit verbose, I know. Now for the memoization function:

import javassist.*; 
import java.io.*; 

public class Memoize { 
	public static void main(String[] args) 
		throws NotFoundException, CannotCompileException, IOException { 
		if (args.length != 2) { 
			System.err.println("Usage: java Memoize <class> <method>"); 
			System.exit(1); 
		} else { 
			ClassPool pool = ClassPool.getDefault(); 
			CtClass ctClass = pool.get(args[0]); 
			memoize(ctClass, ctClass.getDeclaredMethod(args[1])); 
			ctClass.writeFile();
		} 
	} 
	static void memoize(CtClass ctClass, CtMethod ctMethod) 
		throws NotFoundException, CannotCompileException { 
		CtField ctField = 
			CtField.make("static java.util.Hashtable cachedResults = " + 
						 " new java.util.Hashtable();", 
						 ctClass);
		ctClass.addField(ctField); 
		String name = ctMethod.getName(); 
		ctMethod.setName(name + "$original"); 
		ctMethod = CtNewMethod.copy(ctMethod, name, ctClass, null); 
		ctMethod.setBody("{" + 
					     " Object result = cachedResults.get($1);" + 
					     " if (result == null) {" + 
					     " result = " + name + "$original($$);" + 
					     " cachedResults.put($1, result);" + 
					     " }" + 
					     " return ($r)result;" + 
					     "}"); 
		ctClass.addMethod(ctMethod);
	} 
}

Instead of adding an If statement to be beginning of the function every time it calculates n recursively, we’ll use a Hash Table to keep the intermediate values by using n as a key and the fibonacci value as the key’s value.

So this code renames the fib(n) function to original$fib which isn’t normally allowed, but because Javassist works at such a low-level, it’s allowed to do that. Plus, this way, it avoids any namespace collisions. After the rename, it redefines the original fib(n) method so that it:

1. Checks if n is in the hash table. If so, return the corresponding value. 2. If not, call the original$fib function, store the value in the hash table, and return it.

Pretty simple right? That’s exactly what I did in Ruby.

Ruby

I saved the best for last. To be consistent, I’ll show you the Fibonacci method I defined in Ruby:

class Fib
  def fib(n)
    return n if n < 2
    return fib(n-1) + fib(n-2)  
  end
end

And here’s my memoization function:

def memoize(className, methodName)
  className.class_eval do 
    alias_method("original_memoize_#{methodName}", methodName)
    
    define_method(methodName) do |*args|
      hash = instance_variable_get("@memoize_#{methodName}_hash")
      
      if hash.nil?
        hash = Hash.new
        instance_variable_set("@memoize_#{methodName}_hash", hash) 
      end
      
      return hash[args] if hash.has_key?(args)
      res = self.send("original_memoize_#{methodName}", *args)
      hash[args] = res
      return res
    end
  end
end

The function takes as arguments: the Class to be modified and the corresponding method name as a symbol. With that it modifies the method, giving it memoization super powers.

So, given fib(Fib, :fib), the function:

Opens up the Fib class and changes the fib method’s name to original_memoize_fib
Adds a new method to the Fib class, called fib, that:
- Tries to get the hash table from an instance variable called @memoize_fib_hash
- If that instance variable doesn’t exist, it defines and initializes it with an empty Hash
- Checks if the key n exists in the hash table, if it does, then return it straight away.
- If not
  - Call the original fib function, original_memoize_fib and calculate the value recursively
  - Add it to the hash table
  - Finally, return the value.

Simple Benchmark

Here’s an sample execution with n = 30.

Running Fib with 30
Without Memoization:
  1.530000   0.000000   1.530000 (  1.565292)
With Memoization:
  0.000000   0.000000   0.000000 (  0.000440)

And that’s pretty much it for the Ruby version. Out of all the examples, I prefer this one, and not because it was me that did it. I find the code is a bit more elegant than the Lisp version, and a lot more elegant and less verbose than the Java one.

If you want to play with the code, you can get the full version here.