Monday, September 29, 2008

Somebody knows Shoes

I'm a fairly late adopter compared to some of you. When Shoes came out, I had followed it, but never tried it. It's been at least 8 months now, and I finally got around to it. I guess I don't really try something out unless I have a use for it in my mind. Still waiting for that Haskell project...

Anyway, trying out Shoes was...easy. Outside of compiling it, actually. I take that back. Once I read the README and figured out what packages I needed, it was easy. Even easier when I found the executables. Running the sample code was...easy. And trying out your own guessed it...even easier. It helps that there's a ton of examples and documentation. Makes me think that when programming, you should keep the API of your code in mind, so that it's easy to use after you've implemented it.

Two things strike me immediately. _why took his ability to make DSL in Ruby to heart. I don't have to think about the buffering, cursor positions, etc. Even better, the functions are orthogonal and consistent.

You can not only move shapes around to follow your mouse, but also widgets, like buttons. => 300, :height => 300 do
background snow
@o = stack do
button("Message") { alert("Sent!") }

motion do |x,y|
@o.move width - x, height - y

Motion gets executed whenever your mouse moves around on the Shoes screen. So you can have a button dancing opposite to your mouse. Another surprising thing is that an app is structured like a webpage, and different pages have urls. And routing is declared in the app block itself! And not only that, it takes regexs
class Dictionary < Shoes
url '/', :index
url '/(\w+)', :word

def index
stack do
title "Enter a Word"
@word = edit_line
button "OK" do
visit "/#{@word.text}"

def word(string)
stack do
para "No definition found for #{string}. ",
"Sorry this doesn't actually work."

I'm not sure how far this sort of thing can go when building more complex GUIs, but so far, it seems pretty promising. There were a couple things that were broken on Ubuntu, however. I couldn't get margins to work, as well as rounded corners: => 20) do
background red, :radius => 12

Boo. Rounded corners would have been exciting.

Well, try it out and see if you like it. There's lots of neat things people have built with Shoes already.

I, on the other hand, just built a prototype. Nothin to see here folks.

Wednesday, September 24, 2008

EmacsWiki: Moving The Ctrl Key

EmacsWiki: Moving The Ctrl Key

I put off doing this for too long now. I have to admit, if there are settings that I can do in a GUI without mucking around in a config file, I'd do it. Ubuntu has made it easy.

Monday, September 22, 2008

Installing Ruby's linalg in Ubuntu

Ruby has a project for download called linalg that exposes the LAPACK functions in Ruby. LAPACK is a set of routines written in Fortran to do Linear Algebra operations. Now, before you cry foul about Fortran, LAPACK is used in a lot of places, and it's pretty damn old and has held up over the years.

The linalg package just updated about two weeks ago, first since 2004, so it has some updates. Unfortunately, there's no easy gem to install. You'll have to download the tar, and then run

sudo ruby install.rb

Of course, you'll run into some problems, unless you have other packages installed:

sudo apt-get install lapack3 lapack3-dev libg2c0-dev

Don't worry, if you don't like it, you can run uninstall. Read INSTALL file for more directions.
I use to wonder how people knew which packages to look for. Apparently, you look at the output and see what files the configure is crapping out on. Then use apt-file to search for which package the file is in. It's one of those basic things that seems not mentioning in hindsight. Like calling "source ~/.bashrc" after you've edited your bash files. No one ever mentions that.

sudo apt-get install apt-file
sudo apt-file update
apt-file list g2c.h

Knowing that, you'll know how to fish, and I'll not post how to install stuff in the future.


Friday, September 12, 2008

Algorithm always matters, even when parallel

I've finally had some time to start looking at things that looked interesting to me. One of the things that I started looking at was parallel algorithms.

I was reading Hacker News, and I saw some link that lead me to discover Cilk, a C extension to easily make parallel programs.
thread int fib(int n) {
if (n < 2)
return n;
else {
cont int x, y;
x = spawn fib (n-2);
y = spawn fib (n-1);
return x+y;

This was the example given for calculating the Fibonacci sequence in parallel. This is the standard mathematical way to define it, and it looks clean enough. So instead of trying it out in Cilk, I fired up Erlang to try my hand at doing a port. I found it a little bit difficult because while you can easily spawn processes in Erlang, there was no quick way for the parent process to wait/sync/join child processes and get their results. Since that was besides the point of the exercise, I fired up Ruby, even though they had a slow Threading library (which is suppose to be fixed in 1.9, plus Fibers!) I'll do with it Erlang some other time.

First I wrote the threaded version to mimic the Cilk code:
def fib_threaded(n)
if n < 2
return 1
threads = []
x = 0
y = 0
threads << - 2) { |i| x = fib_threaded(i) }
threads << - 1) { |i| y = fib_threaded(i) }
threads.each { |thread| thread.join }
return x + y

I don't have a multi-core processor. I'm on a 3 year old 1GHz laptop. At a mere fib(18), it was taking about 21 seconds to run. To see if there was a difference, I wrote a serial version.

def fib_serial(n)
n < 2 ? 1 : fib_serial(n - 1) + fib_serial(n - 2)

This one ran much much faster. It took about 0.02594 seconds. At this point, it's probably the overhead of thread creation that's making it take so long to run. Maybe with green threads or lightweight threads, the threaded version would run much faster. That makes me want to try it in Erlang just to compare. But wtf, adding shouldn't take that long, even if it is 0.025 seconds

When I thought about it, it was an efficient algorithm: there's a lot of wasted cycles. In order to compute f(n), you have to calculate f(n - 1) and f(n - 2) in separate threads.
  • The f(n - 1) thread requires it to spawn two more threads to compute f(n - 2) and f(n - 3).
  • The f(n - 2) thread requires it to spawn two more threads to compute f(n - 3) and f(n - 4).
Notice that both the threads for f(n - 1) and f(n - 2) have to spawn two different threads to calculate f(n - 3). And since this algorithm has no way for threads to share their results, they have to recompute values all over again. The higher the n, the worse the problem is, exponentially.

To calculate the speedup given to an algorithm by adding more processors, you calculate the amount of total work required and divide it by the span of the parallel graph. If that didn't make sense, read lecture one for Cilk, which is where the diagram comes from. So for fib(n)

Twork = O(n^2)

The total amount of work is the total number of processes spawned. Since every f(n) recursively spawns two other processes, it's about n^2 processes.

Tspan = O(ln n)

The total span is how many nodes a particular calculation traverses. A la the diagram, it's about the height of the tree, so that's about ln n nodes.

Therefore, for fib(n), the processor speed up is at most:

Tw / Ts = O(n^2) / O(ln n)

I don't know of any reductions for that off the top of my head, but you can see that the processor speedup gain grows somewhere in between n and n^2. On one hand, it means this algorithm can benefit from speedups by adding up to somewhere between n and n^2 processors. However, that also means that to make this algorithm go as fast as it can to process fib(1000), you need more than 1000 processors to make it worthwhile. Not so good for a parallel program that's just doing addition.

As a last version, I wrote one that computed the Fibonacci from 0 up to n, and keeping the total as I go along, instead of the recursive version that has to work its way n back down to zero.

def fib_loop(n)
sequence = [1, 1]
if n < 2
sequence = (1..n-1).inject(sequence) do |t, e|
t << (t[-2] + t[-1])

It's not space effective since I wrote it quickly, but this beat the pants off the other two running at 0.00014 seconds. As you can see, you're not recalculating any f(n) more times than you need to.

I wish Cilk had a better first example to parallel programs. Given that the guy making Cilk is the same guy that co-wrote the famous mobile book for algorithms, I guess I was surprised. However, it was a fun exercise, and made me think about algorithms again.

I'll find some other little project that requires me to write in Erlang, rather than falling back on the comfortable Ruby. snippet! Below if you want to run it yourself.

Wednesday, September 10, 2008

Anonymous scope, the unknown cousin of Named scope

Last time, I showed you the well known named scopes. This time, I'll talk about the little documented anonymous scopes.

Anonymous scopes were mentioned briefly on Ryan's Scraps. And in the API, I found it tucked away in ActiveRecord::NamedScope module documentation.
All subclasses of ActiveRecord::Base have two named_scopes:
  • all, which is similar to a find(:all) query, and
  • scoped, which allows for the creation of anonymous scopes, on the fly:
    Shirt.scoped(:conditions => {:color => ‘red’}).scoped(:include => :washing_instructions)
These anonymous scopes tend to be useful when procedurally generating complex queries, where passing intermediate values (scopes) around as first-class objects is convenient.
How would this be useful? In the example given, it's really not. And most of the time, what you need to do will suffice with named scope. However, there are times when named scope doesn't give you the flexibility that you need, and it is actually quite powerful when it's used in conjunction with association proxies.

I was using the better nested set plugin. It allows you to have a fast access tree structure in a relational database. And while it's a neat plugin, I couldn't chain my calls like such:
@father.subtree.with_email  # => fails

to find all the father's descendants that had an email. That's because subtree() exists in the plugin and it uses find(), and that returns an array of objects. You can't further extend the call, because by find returns an array, not an association proxy.

In our association proxies, if we expect to chain the calls, we can use scoped() instead of find(). Just to demonstrate:
class Person < ActiveRecord::Base
has_many :people do
def subtree
scoped(:conditions => ["lft between and", self.lft, self.rgt])

named_scope :with_emails, :conditions => ["email is not null"]

That means we would be able to change other scoped after subtree():
@father.subtree.with_emails # => returns all children

There's not much to it, but it's nice when, once again, you're into breaking Law of Demeter.


Monday, September 08, 2008

not vs !, and vs &&

It's always confusing when you have similar methods that have slightly different meaning. What's the difference between not vs !, and and &&?

The difference between is subtle enough that it might not matter most of the time, but it might bite you in the ass one day. It doesn't say which is which, this post gives the example of precedence order. But just by experimenting, you can see that it's and, or, and not that form statements, which can't be used in arguments


Friday, September 05, 2008 alumni list

Last year August, I joined the local Ruby meetup in Chicago, mainly to meet other programmers, and see if they know stuff about Ruby I hadn't come across yet. Since I lived in the suburbs, going to Chirb was a little bit of a hike, so good thing for ChicagoRuby.

At the first meetup, there were seven people, and one of them being Ray Hightower. The previous organizer was stepping down, Ray volunteered to step up, and I said I'd help him out. I mainly helped out with small things and giving talks when there was none to be had. Since then, Ray's grown the meetup to over 150 people, not to mention setting up a whole conference on Rails. WindycityRails, however is sold out, so you'll have to wait until next year. Kudos to Ray.

I hadn't been involved with ChicagoRuby since about March or so, since I've run off to Boston and then New York. So Ray rightfully set me up on the Alumni list. Yay.

Anyway, if any of you are based in Chicago, go to ChicagoRuby, and help Ray out. Volunteer for stuff. He'll appreciate it, and your ruby community will appreciate it too. The benefits of doing work and getting involved far outweigh the costs of doing so.

Set your hostname when installing yaws

I had recently installed yaws to be able to play with Erlyweb, but I haven't had time to. There's been a string of open source projects that I wanted to dive into to read other peoples' code. Shoes, jquery, couchdb, ejabberd, bittorrent, ubiquity commands. Those are just the ones I think I can digest. Google's V8 engine looks interesting to peruse through, but it's more time than I have anyway.

Regardless, I was getting this on all my package updates on Ubuntu.
$ sudo apt-get install yaws
sudo: unable to resolve host toughie
Reading package lists... Done
Building dependency tree
Reading state information... Done
Suggested packages:
yaws-chat yaws-mail yaws-wiki yaws-yapp
The following NEW packages will be installed:
0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 0B/637kB of archives.
After this operation, 2138kB of additional disk space will be used.
Selecting previously deselected package yaws.
(Reading database ... 169590 files and directories currently installed.)
Unpacking yaws (from .../archives/yaws_1.73-2_i386.deb) ...
Setting up yaws (1.73-2) ...
hostname: Unknown host
chown: cannot access `/etc/yaws/*.pem': No such file or directory
dpkg: error processing yaws (--configure):
subprocess post-installation script returned error exit status 1
Errors were encountered while processing:
E: Sub-process /usr/bin/dpkg returned an error code (1)

To be honest, I had no idea what *.pem files are. Apparently, they're for SSL, and the Ubuntu install can't figure out how to start the yaws server without your machine having the hostname set up correctly.