This blog is now deprecated

Please redirect your feed reader to http://bmaland.com/.

Working with strings in Prolog

Strings in Prolog can be quite confusing if you come from another language. In this short article I will illustrate how they work, mainly by showing different examples and by creating a term that checks if a string is contained within another string.

First off, strings in Prolog are written in single quotes. Terms written in double quotes are immediately converted to a list of character codes. Therefore, strings can be handed directly to write. Strings are also atoms.

?- 'bergen' = String.
String = bergen.

?- "bergen" = List.
List = [98, 101, 114, 103, 101, 110].

?- atom('bergen').
true.

?- is_list("bergen").
true.

?- write('sdf').
sdf
true.

?- write("sdf").
[115, 100, 102]
true.

?- writef("%s", ["sdf"]).
sdf
true.

Since strings in Prolog are atoms, they naturally cannot be manipulated. So for
certain tasks they need to be converted to char lists. This can be done with
name. So to print the first character of a string you'll have to
convert it to a char list first.

?- name('bergen', CharList), nth0(0, CharList, FirstChar), put(FirstChar).
b
CharList = [98, 101, 114, 103, 101, 110],
FirstChar = 98.

We now know enough to create our term, contains/2. For illustration,
we will make it work for both strings and char lists, by converting to a char
list when needed. It will succeed if A is contained within B. We'll need a
utility term for this as well. Note that I am using SWI-Prolog, so I am
utilizing built in terms that might not be available in other implementations.
The full program as well as an example that generates all possible substrings contained within A follows below.

sublist(S, L) :-
  append(_, L2, L),
  append(S, _, L2).

contains(A, B) :-
  atom(A),
  atom(B),
  name(A, AA),
  name(B, BB),
  contains(AA, BB).

contains(A, B) :-
  atom(A),
  name(A, AA),
  contains(AA, B).

%% The empty list is removed mainly for nicer output in the following example.
contains(A, B) :-
  sublist(B, A),
  B \= [].

?- forall( contains('bergen', X) , writef("%s\n", [X]) ).
b
be
ber
berg
berge
bergen
e
er
erg
erge
ergen
r
rg
rge
rgen
g
ge
gen
e
en
n
true.

Experimenting with automatons in Ruby, part 1

A finite automaton is an abstract computing device, which more often than not is used to recognize formal languages. One can look at an automaton as a tape reader which consists of a initial state, a set of final states and a set of transitions between states. The automaton accepts its input if it has reached the end of the input tape and is in a final state.

For the purpose of language processing we will implement different kinds of automatons in Ruby, starting with the simplest one we can conceive. We'll start out with a deterministic finite-state automaton (DFSA). Such an automaton is called deterministic, since it in any given state only has one possible transition for a given input symbol.

First we need an example language to work with, so I've created the "Ruby-language". It can be described with the following regular expression: /Ru+by/ (yes, DFSA's correspond to the languages that can be described by (pure) regular expressions). I admit this is a quite boring language, but we have to start somewhere, right? The alphabet for this language is the set {R,u,b,y}.

To create an automaton for this language we need four states (visualize this as a directed graph):

• q0: 'R' -> q1
• q1: 'u' -> q2
• q2: 'u' -> q2, 'b' -> q3
• q3: 'y' -> q4
  

The initial state is q0 and the set of final states is {q4}. As you can see there is a cycle at q2 to allow for an (theoretically) infinite amount of 'u' characters. Also note that there is no ambiguity of which state is the next one at any given point for any given input. Hence, the automaton is deterministic.

On to the implementation considerations. One of the most important design decisions is how we should represent the state transitions. For a DFSA almost anything would work, but we want to choose something flexible. Let's try with a nested hash:

{
 :q0 => {"R" => :q1},
 :q1 => {"u" => :q2},
 :q2 => {"u" => :q2, "b" => :q3},
 :q3 => {"y" => :q4}
}

I think this will work quite well. If we look up a given state in the hash, we will get another hash of all the possible transitions. Matching this up with a input tape should be quite easy. I've sketched up a spec for how this should work in practice:

describe "the Ruby-language" do
  before(:each) do
    @r = DFSA.new({
                    :q0 => {"R" => :q1},
                    :q1 => {"u" => :q2},
                    :q2 => {"u" => :q2, "b" => :q3},
                    :q3 => {"y" => :q4}
                  }, :q0, [:q4])
  end

  it "should recognize valid sentences" do
    @r.should recognize %w(R u b y)
    @r.should recognize %w(R u u u u b y)
  end

  it "should reject invalid sentences" do
    @r.should_not recognize %w(r u b y)
    @r.should_not recognize %w(R u b)
  end
end

Note that we give the input to the automaton as a list (I've picked the %w() syntax since it feels kinda Lispy). This is called tokenization, and for now we'll do it by hand. The second argument to the DFSA constructor is the symbol for the initial state, and the third one is the set of final states. We won't worry about the actual implementation yet, as we want to let this sink in for a bit.

The next article in this series will be to create a DSL for setting up the automaton, then I'll write up on non-deterministic automatons and pushdown automatons. I'll also show more actual code (I'll create a GitHub repos for the automaton library). Possibly I'll get to transducers as well. If you have any suggestions, please leave a comment or ship me an e-mail.

Use your .gitignore as the ignore pattern for echoe

Echoe is a library for quickly creating gems in Ruby. I I've hacked up a quick patch for it so you can use your .gitignore file as the manifest ignore pattern. I found it boring to re-list the ignore stuff since it in 99% of the cases (at least for me) already is present in .gitignore.

I'm sure that the patch doesn't work perfectly though. I know there is differences between the globbing syntax in gitignore and in Ruby's File#fnmatch - the latter is stricter. But it still works perfectly for the (small) projects I've tried it on.

Usage goes down like this:

Echoe.new(PROJECT) do |p|
...
p.ignore_pattern = FileList[".gitignore"]
...
end

Grab it from my fork on GitHub.

UPDATE: This feature is now included in echoe 3.0.2!

The lack of Database Abstraction in PHP

Unfortunately, almost none of the most popular PHP software supports other databases than MySQL (with MediaWiki being a notable exception - it supports Postgres). When you're used to programming in Ruby, multi-db compatibility is something you just take for granted after a while, because of the excellent ActiveRecord and DataMapper projects. In PHP however, this is a real deal breaker. I don't know if its a cultural problem or a library problem. I did look at Propel some time ago, but honestly the Java-esque XML configuration and over-complex API turned me off real quick. If someone could come up with something better, maybe even WordPress will support SQLite and PostgreSQL one day...

Zshfully Yours, Gem Shortcuts

Stephen Celis provided a slick bash-method for quickly opening and browsing RDocs, over at his blog. I have merely ported the function to zsh. As a slight modification, $BROWSER and $BROWSER_OPTIONS are used instead of just open, so it works cross platform. The code:

gemdoc() {
  local gemdir=`gem env gemdir`
  $BROWSER $BROWSER_OPTIONS $gemdir/doc/`ls $gemdir/doc/ | grep $1 | sort | tail -1`/rdoc/index.html
}

_gemdoc() {
  compadd $(ls `gem env gemdir`/doc)
}

compdef _gemdoc gemdoc

Arch Linux: Changing Gnome's default browser

I'm a big fan of OpenBox, but out of habit I use a couple of Gnome apps. Most notably Gnome Terminal. For some reason, when I clicked URLs in the terminal they opened in Epiphany. Firefox is still my main browser, so I wanted to change that. I solved it like this:

1. sudo pacman -Sy gconf-editor
2. Run gconf-editor , edit the /desktop/gnome/url-handlers/http(s) keys to your liking. In my case "firefox %s".

That should be it!

Script for removing orphans in Arch Linux

Shell scripting is fun, so I created a small function that removes all orphaned packages as reported by Pacman. It calls itself recursively if removing the current orphans revealed any new ones. Tested with zsh since that is my personal preference the best shell around :) - but it probably runs under bash as well. Here is the code:

remove_orphans() {
 for pkg in `pacman -Qdt|awk -F ' ' '{ printf("%s\n", $1) }'`; do
   sudo pacman -R $pkg
 done
 if [ `pacman -Qdt|wc -l` -gt 0 ]; then remove_orphans; fi
}

Arch Linux: Alt+gr not working in Java apps

I got quite confused when my good old trusty Alt+gr key did not work in NetBeans (since I use Norwegian keyboard layout, this key is essential for progamming). The key worked everywhere except in Java apps, actually. Luckily, I figured out how to fix it:

1. Install scim.
2. Add your locale to the scim global config (/etc/scim/global).
3. Start scim from your xinitrc.
4. Restart your X server - it now should work!

For good measure, here's my .xinitrc file:

# SCIM
export XMODIFIERS='@im=SCIM'
export GTK_IM_MODULE="scim"
export XIM_PROGRAM="scim -d"
export QT_IM_MODULE="scim"
scim -d
# OPENBOX
exec openbox-session

Arch Linux: First impressions

So, I finally got fed up with Ubuntu. I really wanted to use FreeBSD again - but unfortunately the hardware in this box is not compatible. Arch Linux looked like a decent alternative so I downloaded the 2007.08-2 image and started installing. Misfortune struck again as I had to spend a couple of hours trying to get wireless working, but everything worked well as soon as I switched to the 2008.04-RC image. I wonder why they don't link to the RC image on the "Get Arch" page.

After some configuration I ended up with a really slick system - It's amazing how much faster stuff runs on OpenBox! Also, the BSD inspired rc.conf and init system made my day. The only real problem I encountered was when I tried to install an older version of a library. Pacman (Arch's package manager) doesn't support this. I consider this to be a flaw in the package manager (which all over feels immature compared to apt or BSD ports), and I predict the devs will realize this sooner or later - even though they currently consider it to be a "feature".

I find it amusing how things tend to move in cycles. When I started out with Linux ~8 years ago Slackware was the coolest thing around. Then we somehow ended up with Ubuntu. And now the "KISS"-distros are turning into the hippest kids on the block again. If you're fed up with the bloat, give Arch a try. :)

(str)tr for JavaScript

I couldn't find a function resembling Ruby's tr or PHP's strtr in JavaScript, so I created one. Here's the code:

function tr(str, from, to) {
    var subst;
    for (i = 0; i < from.length; i++) {
        subst = (to[i]) ? to[i] : to[to.length-1];
        str = str.replace(new RegExp(str[str.indexOf(from[i])], 'g'), subst);
    }
    return str;
}

Java oddity

I really don't like the fact that you can run static class-methods from an object in Java. In effect, object.staticMethod(); gets translated into something like object.getClass().staticMethod();. AFAIK, no other language has this "feature". Is there any reason behind this madness?

Nginx 0.5.35 released

I don't know of any feeds that track nginx releases, so this is just a heads up for people that missed the release of nginx 0.5.35. Release notes:

    *) Change: now the ngx_http_userid_module adds start time microseconds 
       to the cookie field contains a pid value.

    *) Change: now the uname(2) is used on Linux instead of procfs.
       Thanks to Ilya Novikov.

    *) Feature: the "If-Range" request header line support.
       Thanks to Alexander V. Inyukhin.

    *) Bugfix: in HTTPS mode requests might fail with the "bad write retry" 
       error; bug appeared in 0.5.13.

    *) Bugfix: the STARTTLS in SMTP mode did not work.
       Thanks to Oleg Motienko.

    *) Bugfix: large_client_header_buffers did not freed before going to 
       keep-alive state.
       Thanks to Olexander Shtepa.

    *) Bugfix: the "limit_rate" directive did not allow to use full 
       throughput, even if limit value was very high.

    *) Bugfix: the $status variable was equal to 0 if a proxied server 
       returned response in HTTP/0.9 version.

    *) Bugfix: if the "?" character was in a "error_page" directive, then 
       it was escaped in a proxied request; bug appeared in 0.5.32.

Now go and upgrade your servers!

Public domain?

I'm currently reading "Fundamentals of database systems" by Elmasri & Navathe as part of the curriculum in a database course at my University. The book overall isn't all that bad, but their take on open source databases is really horrid. Quote:

"Personal computers and database system-like software products such as Excel, Visual FoxPro, Access (Microsoft), or SQL Anywhere (Sybase), and public domain products such as MySQL and PostgreSQL are being heavily utilized by users who previously belonged to the category of casual and occasional database users."

Wow. Public domain? I think they should at least invest two minutes to read up about open source software and open source licences, before they wrote about it. Excel and PostgreSQL in the same sentence? That's pretty fucked up if you ask me. And they have this highly patronizing tone which goes something like "commercial dbms > *, lol!". Someone should ship the authors a copy of PostgreSQL, I'm sure they would've been amazed if they tried it.

Easiest way to check IE version with JavaScript

Alright, so I needed a easy way to execute custom JavaScript for clients using versions of IE lower than 7. All the scripts Google showed me were really huge and quite outdated. So I took what I found, and turned it into something really lightweight. Note that this is just a quick hack, but so far it seems to be enough for my needs.

Code:

var Browser = {
  Version: function() {
    var version = 999; // we assume a sane browser
    if (navigator.appVersion.indexOf("MSIE") != -1)
      // bah, IE again, lets downgrade version number
      version = parseFloat(navigator.appVersion.split("MSIE")[1]);
    return version;
  }
}

Which enables me to do stuff like this:

if (Browser.Version() < 7) {
  ... // if client is using IE6 or lower, run this code
}

..or this:

if (Browser.Version() >= 7) {
  ... // if client is using IE7 or a sane browser, run this code
}

It will simply return 999 if the browser is non-IE. Is it safe to assume that navigator.appVersion always will contain "MSIE" in uppercase?

Quote of the year

"I get a little paranoid when stuff Just Works though so it's a good thing 99.9% of our customers run Internet Explorer. I'm pretty hard on IE but I will admit to at least one thing it does really well: destroying any sense of pleasantness a developer may feel when building web applications."

So true. Taken from this post.

Liberate yourself from the evil transparent menubar

In Leopard, of course. Get it here!

Using Git with Lighthouse

I wanted to set up Git integration with Lighthouse. The requirements for this was a bit different from the regular SVN integration, since in SVN every commit goes to a central repository, while Git is distributed. For the projects we wanted to integrate with Lighthouse, we use a shared Git repository which acts like the "main" repos. So when our local commits and changes gets pushed to the main repos, we want it to send a new changeset to Lighthouse, which should include the commit messages of all the new revisions since the previous push. A bit more complex than the Svn use case, but luckily Git provides some nice tools that made it quite easy. Google told me that some other guy made something similar a few days ago. However, his solution uses a post-commit hook, and thus sends every single commit to Lighthouse. Which wasn't acceptable for us, since we do a lot of small atomic commits localy. And it works against one of the nicest Git features: quick and easy branches for experimenting, since all the experimental commits would have been exposed to Lighthouse and filled up the overview screen. Summed up, we wanted to be able to make multiple local commits, and then send them as a "revision bundle" to Lighthouse and the main repos.

I solved this by setting up a both post- and pre-receive hooks on the main repos. I suspect that the pre-receive hook can be avoided, but I did the simplest thing that could possibly work. The pre-receive hook saves the current (pre-push) revision to a temporary text file, so it can be used by the post-receive hook. The post-receive hook runs a Ruby script. Most of it is taken from the script in the earlier link. The coolest line goes like this:

commit_log = `#{GIT} rev-list --pretty=short "#{oldrev}..#{newrev}" | git shortlog`

It sums up each authors commits, and shows the commit messages from each of the commits. (You can see this in action on the screenshot at the top of this post) Perfect. The script isn't as complete or elegant as it should be, but it works for now. I will edit it if I come up with something better. If anyone else makes improvements to this script I would love to hear about it (please leave a comment here, or ship me an email)!

Pre-receive hook: http://pastie.caboo.se/112536
Post-receive hook: http://pastie.caboo.se/112535

Choosing a project management system

Last week we were starting up a couple of small projects for some clients. I saw that as a great opportunity to review our choice of project management system. We were currently using Retrospectiva, a open source rails project. It does the job okay, but it isn't exactly very pretty, and the usability kinda sucks. This is supposed to get improved. Anyway, letting clients into Retrospectiva just didn't feel right. Oh, and currently Retrospectiva only supports subversion. And since we've transitioned completely to Git, thats a problem for us.

So I went looking for a substitute. I looked a bit at a new Rails app named WhoDoes. Its pretty cool, and I really wanted to like it since its extremely cheap compared to Lighthouse. It wasn't quite "it" tho. The biggest problem: it lacks a very basic PM requirement: knowledge capture. You really need to have an external wiki or something, since it doesn't even have simple pages/messages like Lighthouse. But I bet this app will improve in the future, so it's something to look out for. So we ended up with Lighthouse, which has a really really beautiful UI. And it's dead easy to use: everything is a ticket. Client-safe, and a whole lot more fun to use than Retrospectiva! We even got Git integration working, which I will write about next.

Leopard: First impressions

Alright, so Leopard has arrived! On Friday I wiped the harddrive of my MacBook and eagerly installed my new OS. I this post I will present some of my thoughts about it, based a couple of days usage.

The good:

• It's very convenient that so much quality software ships with the OS. Built-in svn is nice even tho I prefer Git, since a lot of projects use it. I really wanted the Ruby support to be good. But it turned out that I pretty quickly had to change it with a custom install via MacPorts. The built in Ruby simply refused to install the ruby-postgres gem. I gave the exact same params to extconf.rb with the custom Ruby in place, and it just worked. I had to install PostgreSQL 8.2 from source by the way, since the port for it is broken at the moment. Its still very nice that the OS ships with a up to date Ruby tho.
  
• Spaces are cool, even tho I don't like everything about their behavior. I really want to disable the animated gliding that occurs when you change between spaces.
• The new finder feels much better to use.
• Safari have gotten a bunch of updates as well, I especially like the new search function.
• Its faster than Tiger.

The bad:

• Transparency which you cant turn off. God, I hate transparent windows.
• The new terminal isn't as good as expected. I switched back to iTerm pretty quickly.
• The new dock is way too heavy on the eye candy for my taste.

The ugly:

• A lot of port breakage, but thats to be expected I guess. And most of them get fixed really quick.