The best kittens, technology, and video games blog in the world.

Monday, July 16, 2007

Who reads my blog - Redditers and Googlers

Photo by racciari from flickr (CC-NC-SA)

More than a year ago when I started this blog and I had no idea that anybody would actually read it, but it seems to be doing quite well. According to Google Analytics over the year there were over 90 thousand page views by over 50 thousand visitors. Recently there are about 420 page views daily, or one every three and half minutes. I don't think I have that many friends are relatives, so who reads my blog ?

There seem to be two distinct populations - Redditers, and Googlers. Excluding "direct traffic", which simply means that for whatever reason referrer was not recorder, 35% of visitors come from Google, and 32% from Reddit. The next three sources DZone, Daring Fireball and del.icio.us provide only 6.6%, 3.4% and 1.7% of visits, respectively.

The full story of article's readership look something like that:

  • Article is published. I submit it to del.icio.us and usually also to reddit
  • If Redditers like the article it gets to the main page. I have absolutely no idea which articles Redditers will like and which they won't. Actually I less than no idea - things I consider very interesting almost invariably get downvoted, while random rants I wrote when angry or bored get tens of points. So I submit pretty much everything programming-related and let them decide. My karma from doing so is highly positive, so it's probably not considered a very abusive practice
  • In the next day or two it gets a lot of views from Redditers
  • People submit it to other reddit-like websites, or write answers to it, and it stays popular for a few more days
  • There's a sudden drop in popularity, as people move on to other things
  • Google indexes the article, and a steady flow of Google visits starts. The flow is not wide, but it seems to last pretty much indefinitely
To get some numbers I scrapped Google Analytics reports - Google Analytics has no real API, and it became even more difficult to use programmatically after the update, but I somehow managed to extract the information I want (Google Analytics cookie extracted using Firebug).
require 'time'

$cookie = File.read("/home/taw/ga_cookie").chomp

def wget(url, fn)
system 'wget', '--header', $cookie, url, '-O', fn unless File.exists?(fn)
File.read(fn)
end

def each_day(first_day)
day = Time.now.gmtime
day_number = 0
while true
day_s = day.strftime('%Y%m%d')
break if day_s < first_day
yield day_s, day_number
day_number += 1
day -= 24*60*60
end
end

def get_data_for(day)
url = "https://www.google.com/analytics/reporting/export?fmt=3&id=1222880&pdr=#{day}-#{day}&cmp=average&rpt=TopContentReport&trows=500"
fn = "results-#{day}"
res = wget(url, fn)
header_finished = false
res.each{|line|
unless header_finished
header_finished = true if line =~ /\AURL\tPage Views\tUnique Page Views\t/
next
end
url, page_views, unique_page_views, = line.split(/\t/)
next unless page_views # Skip the final line
next unless url =~ %r[\A/\d{4}/\d{2}/]
next if url =~ /\?/
yield(url, page_views.to_i)
}
end

$stats = {}

each_day('20060923') {|date, day_number|
get_data_for(date){|url, page_views|
$stats[url] ||= []
$stats[url][day_number] = page_views
}
}

$stats_by_post_age = []

$stats.each{|url, stats|
stats.reverse.each_with_index{|page_views, age|
page_views ||= 0
$stats_by_post_age[age] ||= 0
$stats_by_post_age[age] += page_views
}
}

total_page_views = $stats_by_post_age.inject{|a,b| a+b}
p $stats_by_post_age.map{|x| 0.01 * (10000 * x.to_f/total_page_views).to_i}

And the not very surprising results:
  • 22.26% of page views are in the day article is published. As the article could have been published on any time of the day (just after midnight to just before midnight), on average that's article's first 12 hours.
  • It falls rapidly to 11.47% and 4.28% over the next two days
  • In the following ten days the numbers are 2.03%, 1.82%, 1.46%, 1.49%, 1.25%, 0.99%, 0.86%, 0.72%, 0.95%, 0.81%. By that time more than half visits occurred.
  • In the following weeks the number gradually decreases, but I think it's more due to many posts not being online long enough than due to actual popularity loss. Maybe I'll run some statistics to test this hypothesis some day.
You should be able to adapt this script to your blog if you want to know how the numbers looks for your blog.

Sunday, July 15, 2007

Short rant on video game usability and 3D acceleration

Photo by poolzelio from flickr (CC-NC)
There's one thing that pretty much every PC game does, and what I really hate. It's using "constant rendering quality" paradigm instead of "constant FPS" paradigm.

PC hardware differs a lot, with some people using older hardware and wanting to play games even if the rendering is only so-so, while other who have just bought shiny new graphics cards demanding really awesome effects from them, more to impress their friends and stimulate graphics card manufacturing than to actually improve gameplay. What pretty much everybody wants is the highest rendering quality that still gives them reasonably FPS rate.

That's what game engines should do - monitor FPS and increase or decrease rendering quality if FPS is not in some predefined range. But not a single game I know does so. Instead they all opt for providing "constant rendering quality" - maintaining some level of rendering quality whether the game gets unusably slow, or has a lot of free GPU cycles. Often both situations happen as player moves from one location to another. Changing graphics setup every few minutes would distract too much from playing, so most old hardware owners either set the quality low enough that they always have good FPS, even if for 90% of the game GPU is half idle, or accept occasional low FPS in exchange for better rendering quality. Or they solve this software problem in hardware and buy a better graphics card.

Oh, and the graphics setup. Instead of having one big "I want that many FPS" slider and then the game filling in details, there are usually dozens of confusing options - some of them affecting rendering speed considerably, others barely at all.

Time to get a new card, the one bought year ago isn't good enough any more.

Saturday, July 14, 2007

Truth, falsehood and voidness in dynamic languages

claws by theogeo from flickr (CC-BY)
One of the things which different dynamic languages do differently is how truth, falsehood, and voidness are handled. I checked how it's done in 9 most popular dynamic languages - Common Lisp, JavaScript, Lua, Perl, PHP, Python, Ruby, Scheme, and Smalltalk.

The first question - does the language has dedicated booleans ? That is - do questions like 2 > 1 return special booleans or something else ?

  • Ruby, Lua, Smalltalk, JavaScript - Yes (true and false)
  • Python - Yes (True and False)
  • Scheme - Yes (#t and #f)
  • Common Lisp - No, it returns symbol t for true and empty list (nil) for false.
  • Perl - No, it return 1 for true, and undef for false.
  • PHP - Kinda. Since PHP4 there are booleans true and false, but their behavior is full of hacks - print true prints 1, print false prints nothing, false == 0, false == NULL, true == 1, even true == 42.
If booleans are used in boolean context their interpretation is obvious. If most objects are used in boolean context they usually are treated the same way as true. There are a few common exceptions. How are empty list, integer 0, floating point 0.0, and empty string treated in boolean context ?
  • Ruby, Scheme, Lua - all are true
  • Perl, PHP, Python - all are false
  • JavaScript - empty list is true, others are false
  • Common Lisp - empty list is false, others are true
  • Smalltalk - NonBooloanReceiver exception is raised if anything but booleans is used in boolean context.
Is string "0" false ?
  • PHP, Perl - unfortunately "0" is false, and this is a huge source of nasty bugs
  • Ruby, Scheme, Lua, JavaScript, Python, Common Lisp - "0" is true
  • Smalltalk - NonBooloanReceiver exception is raised
Is there a special value denoting absence of value ? What accessing nonexistent array element returns ?
  • Ruby, Lua - nil, accessing nonexistent elements returns it
  • JavaScript - undefined, accessing nonexistent elements returns it
  • Perl - undef, accessing nonexistent elements returns it
  • PHP - NULL, accessing nonexistent elements returns it
  • Python - None, accessing nonexistent elements throws an exception
  • Smalltalk - nil, accessing nonexistent elements throws an exception
  • Scheme - there isn't one, accessing nonexistent values is an error
  • Common Lisp - there isn't one, but empty list acts as one in most contexts, it is also returned when accessing nonexistent elements
Is the nonexistent value false in boolean context ?
  • Ruby, Lua, JavaScript, Perl, PHP, Python, Common Lisp - it is false
  • Scheme - there is no nonexistent value marker
  • Smalltalk - NonBooloanReceiver exception is raised
The most common answers are: there are dedicated booleans, and dedicated absence marker; it is possible to use normal objects in boolean context, most of which (including string "0") are treated as true, while absence marker is treated as false.

There is no clear consensus whether 0, 0.0, "", and empty list should be treated as true or false. Personally I think it's better to make them all true. Otherwise either libraries can define other false objects (like decimal 0.00, various empty containers, and so on) what complicates the language, or they cannot what makes it feel inconsistent.

Is most languages accessing nonexistent elements of an array returns an absence marker instead of throwing an exception, and in my opinion that's the right way and it makes the code look much more natural.

Wednesday, July 11, 2007

Using home directory as GTD inbox - version 2

my name is Grisou by *Blunight72* from flickr (CC-NC)

The GTD software I described a few weeks ago evolved quite significantly since then.

Fortunately my inbox is still empty:

$ inbox_size
Your inbox is empty.

It can be used in two modes - either single-shot report of inbox contents with inbox_size, or continuous screening mode plus UI notification with inbox_size_notify. inbox_size.rb is a library (symlinked from /home/taw/local/bin/inbox_size) which finds all items in all my inboxes. It also handles special items:
  • Unread emails in Gmail inbox
  • Uncommitted changes to one of the repositories
  • Music log not committed to last.fm
  • Passwords file chanced since last encrypted copy
  • Last backup older than 3 days
  • Any things I wanted to be informed about

The code


The main code is in inbox_size.rb:
require 'time'
require 'magic_xml'

$offline = false

def inbox_ls
items_whitelist = %w[
/home/taw/Desktop
/home/taw/ebooks
/home/taw/everything
/home/taw/img
/home/taw/ipoddb
/home/taw/local
/home/taw/movies
/home/taw/music
/home/taw/ref
/home/taw/website
/home/taw/website_snapshot
]

files = (Dir["/home/taw/*"] +
Dir["/home/taw/Desktop/*"] +
Dir["/home/taw/movies/complete/*"] -
items_whitelist)
items = files.map{|x|x.sub(%r[\A/home/taw/],"")}

# Code for handling special inbox items goes here
# ...

return items.sort.map{|item| "* #{item}"}
end

if $0 == __FILE__
if ARGV[0] == '--offline'
ARGV.shift
$offline = true
end
items = inbox_ls
if items.empty?
puts "Your inbox is empty."
else
puts "#{items.size} items in your inbox:", *items
end
end


inbox_size_notify which scans the inbox continuouly and displays UI notifications if it's not empty is:
require 'inbox_size'

max_displayed = 30

big_timer = 5
old_items = []

while true
items = inbox_ls
next if items == []

if items == old_items
big_timer -= 1
sleep 60
next unless big_timer == 0
end
big_timer = 5

if items.size > max_displayed
displayed_items = items.sort_by{rand}[0, max_displayed].sort + ["* ..."]
else
displayed_items = items
end
system "notify", "Inbox is not processed", "#{items.size} items in your inbox:", *displayed_items

sleep 60
old_items = items
end


Script which displays KDE notifications is:
header = "Notification"
msg = ARGV.join("\n") # "All your base\nAre belong to us"

system 'dcop', 'knotify', 'Notify', 'notify', 'notify', header, msg, 'nosound', 'nofile', '16', '0'

Backup reminder


Since my disk died I became more serious about backups. I indent to have at least regular rsync of my SVK repository and some important files. Here's a script which rsyncs these files from shanti (my main box) to ishida (an old laptop).

t0 = Time.now

rv = system 'rsync -rL ~/.mirrorme/ taw@ishida:/home/taw/shanti_mirror/'

unless rv
STDERR.puts "Error trying to rsync"
exit 1
end

t1 = Time.now

File.open('/home/taw/.last_backup', 'w') {|fh|
fh.puts t1
}

puts "Started: #{t0}"
puts "Started: #{t1}"
puts "Time: #{t1-t0}s"


If backup was successful a time stamp is saved to /home/taw/.last_backup. inbox_size.rb reminds me if I didn't backup for more than 3 days:

  # Time since last rsync
time_since_last_rsync = Time.now - Time.parse(File.read("/home/taw/.last_backup").chomp)
if time_since_last_rsync > 3 * 24 * 60 * 60
items << "Over 3 days since the last backup"
end

Tickler file


The "tickler file" (/home/taw/.tickler) contains all things I want to be reminded about. Appointments, deadlines, new episodes of The Colbert Report, whatever. Of course usually I want to be reminded before the deadline, not on the deadline, so the date must be some time before the event of interest. Entries in the tickler file look something like that:
Sat Jul 21 05:49:14 +0200 2007
15 days to Wikimedia Foundation validation deadline


It can be edited as a text file, but it's more convenient to add new entries with add_tickler script:
$ add_tickler 24h "New TCR episode will be available"


unless ARGV.size == 2
STDERR.puts "Usage: #{$0} 'due' 'msg'"
exit 1
end

due = ARGV.shift
msg = ARGV.shift

due_sec = case due
when /\A(\d+)s\Z/
$1.to_i
when /\A(\d+)m\Z/
$1.to_i * 60
when /\A(\d+)h\Z/
$1.to_i * 60 * 60
when /\A(\d+)d\Z/
$1.to_i * 60 * 60 * 24
else
STDERR.puts <<EOF
Usage: #{$0} 'due' 'msg'
Due can be:
* 15s
* 15m
* 15h
* 15d
EOF
exit 1
end

due_time = Time.now + due_sec

File.open("/home/taw/.tickler", "a") {|fh|
fh.puts due_time
fh.puts msg
}


The tickler file is checked by the following code in inbox_size.rb:
  # Tickler items
tickler = File.readlines("/home/taw/.tickler")
while not tickler.empty?
deadline = Time.parse(tickler.shift.chomp)
msg = tickler.shift
if Time.now > deadline
items << msg
end
end

The passwords file


Pretty much every website requires an account nowadays. I don't want to reuse password on multiple website, so I generate them randomly (cat /dev/urandom | perl -ple 's/[^a-zA-Z0-9]//g' | head) and keep them in unencrypted file /home/taw/.passwords which I simply grep if I want to login to some weird website again (normally Firefox remembers these passwords anyway, but sometimes it's necessary).

As it would suck to lose all accounts, I AES-256-CBC encrypt this file and keep encrypted copies in /home/taw/ref/skrt/, which is mirrored to multiple servers. As I need to enter my password to encrypt the file, it cannot be done automatically. The most inbox_size.rb can do is reminding me if there's no up-to-date skrt file:
  # skrt up to date ?
pwtm = File.mtime("/home/taw/.passwords")
last_skrt_tm = Dir["/home/taw/ref/skrt/*"].map{|fn| File.mtime(fn)}.max
if pwtm > last_skrt_tm
items << "No up-to-date skrt available"
end


In which case I run the following skrt_new script:
t = Time.now
fn = sprintf "skrt-%04d-%02d-%02d", t.year, t.month, t.day
system "openssl aes-256-cbc /home/taw/ref/skrt/#{fn}

Music log


The iPod-last.fm bridge consists of two parts - one which extracts the log from an iPod, and one which submits the data to last.fm. They communicate using very simple format, with lines like that (time is local):
Sumptuastic ; Cisza (Radio Edit) ; Cisza (Single) ; 185 ; 2007-07-11 17:51:27


Nothing in the format is iPod-specific, so I wrote a wrapper around mplayer which logs music it plays to /home/taw/.music_log. It can also randomize songs and search for them recursively in directories. It uses a few extra programs - id3v2 to get song title, artist and album (from either ID3v2 or ID3v1 tags), and mp3info to get playing time.
def mp3_get_metadata(file_name)
song_info = `id3v2 -l "#{file_name}"`
artist = nil
title = nil
album = nil

if song_info =~ /^TPE1 \(Lead performer\(s\)\/Soloist\(s\)\): (.*)$/
artist = $1
elsif song_info =~ /^Title : .{31} Artist: (.*?)\s*$/
artist = $1
end

if song_info =~ /^TIT2 \(Title\/songname\/content description\): (.*)$/
title = $1
elsif song_info =~ /^Title : (.{0,31}?)\s+ Artist: .*$/
title = $1
end

if song_info =~ /^TALB \(Album\/Movie\/Show title\): (.*)$/
album = $1
elsif song_info =~ /^Album : (.{0,31}?)\s+ Year:/
album = $1
end

return [artist, title, album]
end

def mp3_get_length(file_name)
`mp3info -F -p "%S" "#{file_name}"`.to_i
end

def with_timer
time_start = Time.now
yield
return [time_start, Time.now - time_start]
end

randomize = true
if ARGV[0] == "-s" # --sequential
randomize = false
ARGV.shift
end

songs = ARGV.map{|fn| if File.directory?(fn) then Dir["#{fn}/**/*.mp3"] else fn end}.flatten
songs = songs.sort_by{rand} if randomize

songs.each{|song|
time_start, time_elapsed = with_timer do
rv = system "mplayer", song
exit unless rv
end
artist, title, album = *mp3_get_metadata(song)
length = mp3_get_length(song)

next unless length >= 90 and (time_elapsed >= 240 or time_elapsed >= 0.5 * length)

date = time_start.strftime("%Y-%m-%d %H:%M:%S")

File.open("/home/taw/.music_log", "a") {|fh|
fh.puts "#{artist} ; #{title} ; #{album} ; #{length} ; #{date}"
}
}


It's a good idea to commit the log to last.fm often, but I'm not doing it automatically yet, as network problems with last.fm are too frequent. Instead inbox_size.rb reminds me if there are old uncommitted entries in the log:
  # .music_log not empty and older than one hour
if File.size("/home/taw/.music_log") > 0 and File.mtime("/home/taw/.music_log") < Time.now - 60*60
items << "Music log not clean"
end

Uncommitted stuff in repositories


I sometimes get distracted by some interruption and forget to commit things to repositories.
I wrote uncommitted_changes script which checks local checkouts of all repositories I use (currently 1 SVK and 2 SVN repositories) if there are any uncommitted changes. I use svn/svk diff instead of svn/svk status as the latter finds all kinds of temporary files, and I always svn/svk add all new files when I start coding anyway.

Dir.chdir("/home/taw/everything/") { system "svk diff" }
Dir.chdir("/home/taw/everything/rf-rlisp/") { system "svn diff" }
Dir.chdir("/home/taw/everything/gna_tawbot/") { system "svn diff" }


inbox_size.rb simply checks that output of this script is empty:
  # Uncommitted changes
uc = `uncommitted_changes`
unless uc == ""
items << "There are uncommitted changes in the repository"
end

Unread Gmail emails


The last kind of inbox items tracked by inbox_size.rb are email inbox items. Google APIs are almost invariably ugly Java-centric blobs of suckiness, so instead of using Gmail API I simply get the list from RSS, parsed using magic/xml.
  # Unread Gmail messages
unless $offline
gmail_passwd = File.read("/home/taw/.gmail_passwd").chomp
url = "https://Tomasz.Wegrzanowski:#{gmail_passwd}@mail.google.com/mail/feed/atom"
XML.load(url).children(:entry, :title).each{|title|
items << "Email: #{title.text}"
}
end

Wednesday, June 27, 2007

Regular expressions and strings with embedded objects

Minta by melisdramatic from flickr (CC-NC-SA)

Regular expressions are among the most powerful programming techniques ever invented. Real world "regular expressions" are only loosely related to Computer Science "regular expressions". Computer Science "regular expressions" can only provide yes/no answers to "does this string match that regular expression" type of questions. We are usually interested in much more than that - we want to extract data from strings, convert strings to other strings and so on. We call expressions used for this purpose "regular" too for historical reasons.

Regular expressions are extremely concise, but sometimes they don't suffice and we need to write a "real parser". Unfortunately even with the best parser generating tools parsers tend to be many times more complex and error prone than equivalent regular expressions. And if the problem is too complex for regular expressions, very often it is also too complex for whichever parser generator you're using, and needs a lot of nontrivial hacking around limitation of it, or even writing a parser by hand.

Fortunately for many problems there's an alternative to parsers and parser generating tools - regular expressions plus a few tricks. This blog post is about one of such trick.

For my bot which verifies links in Wikipedia I needed to extract data from SQL dumps. SQL dumps look something like that:

INSERT INTO `page` VALUES (1,0,'Astronomia','',1800,0,0,0.600461925007833,'20070601091320',8076762,8584,0), (2,0,'AWK','',329,0,0,0.487812640599732,'20070530195555',8058046,4265,0), (4,0,'Alergologia','',108,0,0,0.580574716050713,'20070520093413',7912844,292,0), ...
INSERT INTO `page` VALUES (14880,0,'Dźwignica_linotorowa','',26,0,0,0.597327036408081,'20060814072401',4282357,727,0), (14881,0,'Urządzenia_transportowe','',91,0,0,0.176666489966834,'20070527090143',2976610,1041,0), ...

Basically a bunch of INSERT statements with multiple tuples each. I wanted to iterate over the tuples. Extracting tuple data from the sql dump is a simple next unless line =~ /\AINSERT INTO `page` VALUES (.*)\Z/. Spliting this blob into tuples and tuple fields is almost trivial - /\),\(/ separates tuples and , separates tuple fields. Unfortunately there are many strings inside, and some of them might contain commas.

Sure, it's posisble to write a single monster regular expression to do just that, but it would be quite error-prone. Wouldn't it be easier to simply treat whole SQL strings as single "objects" inside the string ? That's exactly what we're going to do. First we need to get rid of \-escapes. That's not really necessary, as a regular expression for matching strings with \-escapes inside wouldn't really be that complicated, but we can make it even simpler this way. So every /\\(.)/ becomes "\x00" + esc[$1], where values of esc[...] are "safe" characters which won't interfere with further parsing, like A, B, C, and so on.

At this point every ' marks either a beginning or an end of some string. So we can replace all strings by object ids like "\x01<1234>", where 1234 is a suitable number. After we do that we can split on /\),\(/ and , just like we wanted. Afterwards we need to convert embedded objects (like \x01<1234> and \x00A) back to their original form.

The complete code is here:
def hash_or_die(kw)
Hash.new{|ht,k| raise "Unknown key: #{k}"}.merge(kw)
end

def parse(data)
esc = hash_or_die "\\" => "A", "\"" => "B", "n" => "C", "'" => "D"
rev_esc = hash_or_die "A" => "\\", 'B' => "\"", "C" => "n", "D" => "'"
data = data.gsub(/\\(.)/) {"\x00" + esc[$1]}
strs = []
data = data.gsub(/('[^']*')/) { # '
strs << $1
"\x01<#{strs.size-1}>"
}
records = []
data.scan(/\((.*?)\)/) {
records << $1.split(/,/).map{|field|
field.gsub(/\x01<(\d+)>/) {
strs[$1.to_i]}.gsub(/\x00(.)/){ rev_esc[$1]
}
}
}
records
end

def sql_str_unquote(str)
str =~ /\A'(.*)'\Z/ or raise "SQL string format is wrong: #{str}"
$1.gsub(/\\(.)/) {$1}
end

page_fn = Dir["plwiki-*-page.sql"].sort[-1]
externallinks_fn = Dir["plwiki-*-externallinks.sql"].sort[-1]

pages = {}

File.open(page_fn).each{|line|
next unless line =~ /\AINSERT INTO `page` VALUES (.*)\Z/
parse($1).each{|id,ns,title,*stuff|
next unless ns == "0"
title = sql_str_unquote(title)
pages[id] = title
}
}

File.open(externallinks_fn).each{|line|
next unless line =~ /\AINSERT INTO `externallinks` VALUES (.*)\Z/
parse($1).each{|from,to,index|
title = pages[from]
next unless title
to = sql_str_unquote(to)
next unless to =~ /\Ahttp:\/\//
puts "#{title}\t#{to}"
}
}


The same technique can be used to parse many other things like parsing Lisp code:
require 'pp'

lisp_code = '(a (b c) (d (e) f g) (((h))))'
nodes = []

lisp_code.gsub!(/([a-z]+)/) {
nodes << [:atom, $1]
"<#{nodes.size-1}>"
}
lisp_code.gsub!(/\s/,"")
true while lisp_code.gsub!(/\(((?:<\d+>)*)\)/) {
nodes << [:app, *$1.scan(/<(\d+)>/).map{|x,| nodes[x.to_i]}]
"<#{nodes.size-1}>"
}
lisp_code =~ /<(\d+)>/
pp nodes[$1.to_i]
# Output:
# [:app,
# [:atom, "a"],
# [:app, [:atom, "b"], [:atom, "c"]],
# [:app, [:atom, "d"], [:app, [:atom, "e"]], [:atom, "f"], [:atom, "g"]],
# [:app, [:app, [:app, [:atom, "h"]]]]]


and math expressions:
require 'pp'

math_code = '(2 + 2 * 2) / ((2 + 2) * 2)'
nodes = []

math_code.gsub!(/(\d+)/) {
nodes << $1.to_i
"<#{nodes.size-1}>"
}
math_code.gsub!(/\s/,"")

until math_code =~ /\A<(\d+)>\Z/
next if math_code.gsub!(/\((<\d+>)\)/) { $1 }
next if math_code.gsub!(/<(\d+)>([\*\/])<(\d+)>/) {
nodes << [$2, nodes[$1.to_i], nodes[$3.to_i]]
"<#{nodes.size-1}>"
}
next if math_code.gsub!(/<(\d+)>([\+\-])<(\d+)>/) {
nodes << [$2, nodes[$1.to_i], nodes[$3.to_i]]
"<#{nodes.size-1}>"
}
end
pp nodes[$1.to_i]
# Output:
# ["/", ["+", 2, ["*", 2, 2]], ["*", ["+", 2, 2], 2]]


Technique of embedding objects in strings and matching such strings with regular expressions is simple and very powerful. Objects can be represented in many ways. If numbers and some sort of brackets are not relevant for parsing, and "\x00" doesn't occur in the input (it almost never does), "\x00<ID>" is a good idea. Fancy Unicode private characters can be used too if the regular expression engine can handle them. If you want to treat different objects in different way you can represent them in some convenient form like \x00<CLASS;PROPERTY_A;PROPERTY_B;ID>. The technique works best in languages with integrated regular expression engines like Ruby, Perl, and RLisp. In others like Python and Java it's going to be somewhat uglier, but still better than full-blown "parsers".

Tuesday, June 26, 2007

Healthcare in Poland

Sick of waiting, Time for action!!! by Andrew Pescod from flickr (CC-NC-SA)

Currently in Poland there's a lot of discussion about the healthcare system. Poland has a mostly state-run healthcare. Not only the health insurance is public, even the hospitals are operated by the government. The former is probably a good idea, considering how horrible the healthcare system is in the only developed country where it is privately run. The latter is a relic of the Communist era which refuses to die.

In the last few months doctors and other healthcare workers were constantly protesting, demanding increased government spending on health care - primarily demanding better salaries. The media completely failed to do their job and didn't provide any real data on health care or health care financing whatsoever. We bloggers need to fill in the gap.

The data wasn't particularly hard to find. It's available from WHO European health for all database (HFA-DB). The comparison is for all 12 "New EU" countries in group and individually, plus "Old EU" and "EU total". I didn't include old EU countries here, as their situation is significantly different, so it wouldn't be particularly meaningful.

CountryLife expectancy (2005)Infant mortality per 1000 births (2005)Healthcare spending as % of GDP (2004)Healthcare spending in USD PPP (2004)
Bulgaria72.6*11.65*8671
Cyprus79.54*3.01*5.81128
Czech Republic76.193.397.31412
Estonia72.895.445.3752
Hungary73.026.237.91308
Latvia71.067.87.1852
Lithuania71.336.846.5843
Malta79.445.969.21733
Poland75.126.426.2814
Romania71.88*16.84*5.1433
Slovakia74.37.27.21061
Slovenia77.584.158.71815
Whole EU78.445.178.72334.32
Old EU79.63*4.34*9.292729.1
New EU73.968.716.51869.61


* - data for 2004

The spending figures are total spending - that is public + private. As you can see healthcare in Poland is somewhat better and somewhat cheaper than "new EU" average. It's still far behind the old EU, but it's not really a crisis situation, especially since the results are improving and the spending is increasing - between 2000 and 2005 life expectancy increased 73.95 to 75.12, infant mortality fell 8.11 to 6.42. Between 2000 and 2004 spending increased as percent of GDP from 5.7 to 6.2, and in USD PPP from 587 to 814.

So the protests seem to be primarily politically motivated. The situation is fairly good compared to other countries in similar situation and is steadily improving. Another thing strongly implying political motivation is the sudden support for the protesting doctors from the normally vehemently anti-union opposition party Platforma Obywatelska.

Making it easy for users to write quality bug reports

Computerkatze by avatar-1 from flickr (CC-SA)

One of the coolest things about making your programs public is the user feedback you will get. Some is going to be "Awsum thx, your program just saved my life" and "I tried to run it on Amiga 500 and it crashed, you suck", but in my experience most of the feedback consists of very helpful suggestions and bug reports.

This is very valuable, and as a developer you have a great influence on quality of the feedback. For most Unix console programs and Ruby libraries nothing needed to be done, as normal stack traces get printed to the terminal, and Unix users tend to know how to write good bug reports, but for jrpg it wasn't that simple - many bugs were highly nondeterministic, and as most users ran it on Windows there was no console to print stack traces to. At first I kept telling users to retry with some sort of console turned on, but after two or three such cases I wrote the following code. In util.py:

def save_errormsg(trace_back):
(tp,v,tb) = trace_back
tbf = traceback.format_exception(tp,v,tb)
f = open("errormsg.txt", "a")
f.write("== ")
f.write(time.asctime(time.localtime()))
f.write(" ==\n")
for line in tbf:
f.write(line)
f.write("\n")
f.close()

And in jrpg.py:
try:
mistakes = Mistakes()
book = demonsoul.Book_of_demons()
mhc = Main_Hero_Controller()
wm = World_model()
wv = World_view()
ui = UI()

main_hero = Chara("female-blue", position=(0, 0))
main_hero.is_main = True

wm.switch_map("world", (14,25))

ui.change_text([U"Welcome to the 日本語RPG", U"", U"Press F1 for quick help"])

ui.main_loop()
except SystemExit:
pass
except Exception:
util.save_errormsg(sys.exc_info())
raise


All exceptions get saved to errormsg.txt. When user reports a bug, I can ask them to attach this file, and thanks to stack backtraces bugs are much easier to fix. For boring technical reasons we don't really want to capture SystemExit, so we let it through.

Another thing that increases feedback quality (and also user count) is good packaging and really good documentation on how to get started - that's where most of the problems seem to be. Listening to users also helps - as you wrote the program it's too easy for you to convince them that they're wrong, and very few users are going to argue with that. Often you're right and their ideas wouldn't work for some reason, but not always. What I found very helpful was explaining the rationale behind the things being the way they are in detail every time an user suggests a change. A couple of times it let me find out that the user was actually right. For example backspace on jrpg repeated significantly too fast - I did some calculations which showed the speed to be just right, and I got used to the way it worked so I didn't notice, but when I tried to explain that to an user I found out that there was a mistake in my calculations and it should really be slowed down a bit.

Being nice to users and replying quickly also improves feedback.

Toy C backend for RLisp compiler

Finette by franziskas garten from flickr (CC-NC-SA)

I wrote a toy RLisp C "backend". It's not yet connected to the real compiler - the only thing it compiles is Ackermann function - of course you can make it compile something else by issuing right opcodes by hand.

First some support code. Symbol#<=> is already in rlisp_support.rb, String#ord is supposed to be a wrapper around different behaviour of Strings in 1.8 and 1.9. Symbol#mangle_c and Symbol#stringify_c convert Ruby symbols (which may contain funny characters like :"==\nblah!@#") to C variable names and strings. For brevity I'm not pasting the tests here.

class Symbol
include Comparable
def <=>(other)
to_s <=> other.to_s
end
protected :<=>
end

class String
# FIXME: 1.8 specific, add support for 1.9
def ord
self[0]
end
end

class Symbol
def mangle_c
to_s.gsub(/([^a-zA-Z0-9])/) { sprintf "_%02x", $1.ord }
end
def stringify_c
'"' + to_s.gsub(/([\\"])/) { "\\#{$1}" } + '"'
end
end


Here's the code which calls the code generator, and then the ack function. It uses Ruby->C trampoline to support closure variables. The interface used by code generator is similar to one used by normal Ruby-backed RLisp code generator, but not identical. I'm going to refactor them both to match, so RLisp frontend can talk with either backend. I think C-compiling at least RLisp stdlib is a good idea. C-compiling REPL less so. Code generators are so simple that I hope to be able to maintain both without too much work.

class Stuff
cg = RLispCodegenC.new(:ack, [:m, :n])
t2, t3, t4, t5, t6, t7, t8, t9, t10, t11, t12, t13, t14, t15 = cg.tmps(14)

cg.funcall(t2, :m, :"==", 0)

cg.x_if(t2) {
cg.funcall(t4, :n, :+, 1);
cg.asg(t3, t4)
}
cg.x_else {
cg.funcall(t5, :n, :==, 0);

cg.x_if(t5) {
cg.global_get(t7, :ack)
cg.funcall(t8, :m, :-, 1);
cg.funcall(t9, t7, :call, t8, 1);
cg.asg(t6, t9)
}
cg.x_else {
cg.global_get(t10, :ack)
cg.funcall(t11, :m, :-, 1)
cg.global_get(t12, :ack)
cg.funcall(t13, :n, :-, 1)
cg.funcall(t14, t12, :call, :m, t13)
cg.funcall(t15, t10, :call, t11, t14)
cg.asg(t6, t15)
}
cg.asg(t3, t6)
}
cg.ret(t3)

inline do |builder|
result = builder.c cg.build
end
end

ack_m = Stuff.new.method(:ack)
globals = {}
closure = { :globals => globals }
globals[:ack] = lambda{|*args| ack_m.call(closure, args) }

print "retval = ", globals[:ack].call(3, 3), "\n"


RLispCodegenC builds one function at time. To use it you need to create a new RLispCodegenC instance, call some opcode methods, call build on the RLispCodegenC object, and compile it using inline. inline caches .so objects, so C compiler is called only when something changed.

require 'inline'

class RLispCodegenC
def initialize(name, args)
@name = name
@args = args
@syms = {:globals => true}
@ids = {}
@temps = []
@code = ""
end

def build
temps = [:globals] + @args + @temps
src = <<EOF
VALUE #{@name}(VALUE closure, VALUE args) {
VALUE #{temps.join(", ")};
#{static_init}
#{arg_init}
#{@code}
}
EOF
src
end

def arg_init
res = "globals = rb_hash_aref(closure, SYM_globals);\n"
@args.each_with_index{|arg, i|
res << "#{arg.mangle_c} = rb_ary_entry(args, #{i});\n"
}
res
end

# This code should be executed just once in Init_*, not every time the method is called
def static_init
ids = @ids.keys.sort
syms = @syms.keys.sort
res = ""
res << %Q[int #{ids.map{|i| "ID_#{i.mangle_c}"}.join(", ")};\n] unless ids.empty?
res << %Q[VALUE #{syms.map{|s| "SYM_#{s.mangle_c}"}.join(", ")};\n] unless syms.empty?
ids.each{|i| res << "ID_#{i.mangle_c} = rb_intern(#{i.stringify_c});\n" }
syms.each{|s| res << "SYM_#{s.mangle_c} = ID2SYM(rb_intern(#{s.stringify_c}));\n" }
res
end

def tmps(sz)
res = []
sz.times{
t = :"t#{@temps.size}"
res << t
@temps << t
}
res
end

def to_c(x)
if x.is_a? Fixnum
"INT2FIX(#{x})"
# It means a C temporary, ***NOT*** Ruby symbol
# FIXME: Mangling ?
elsif x.is_a? Symbol
x.mangle_c
else
raise "Don't know how to convert #{x.class}: #{x.inspect}"
end
end

def funcall(asg_to, recv, mid, *args)
@ids[mid] = true
mid_s = "ID_#{mid.mangle_c}"
args_m = args.map{|a| ", " + to_c(a)}.join
@code << "#{to_c(asg_to)} = rb_funcall(#{to_c(recv)}, #{mid_s}, #{args.size}#{args_m});\n"
end
def x_if(tmp)
@code << "if(RTEST(#{tmp})) {\n"
yield
end
def x_else
@code << "} else {\n"
yield
@code << "}\n"
end
def asg(to, from)
@code << "#{to_c(to)} = #{to_c(from)};\n"
end
def global_get(to, sym)
@syms[sym] = true
sym_s = "SYM_#{sym.mangle_c}"
@code << "#{to} = rb_hash_aref(globals, #{sym_s});\n"
end
def ret(val)
@code << "return #{to_c(val)};\n"
end
def debug(msg, val=nil)
@code << %Q[rb_funcall(self, rb_intern("print"), 1, rb_str_new2(#{msg.inspect})); /* DEBUG */\n]
@code << %Q[rb_funcall(self, rb_intern("p"), 1, #{val}); /* DEBUG */\n] unless val.nil?
end
end

Wednesday, June 20, 2007

Object-Oriented dialects of Lisp

Lolcat based on 'Let's see here, Cat Power, Cat Stevens, Purrs... Ooo, Meatloaf!' by Lazy_Lightning from flickr (CC-BY)

Lisp is much older than object oriented programming. When OOP got popular people wanted to do OOP in Lisp too, but it wasn't obvious how to retrofit Lisp to make it object oriented. CLOS for Common Lisp became somewhat popular, but its quite far from what Smalltalkers would call "object oriented", and some people feel it wasn't very Lispy either. Many Lispers like Paul Graham simply gave up on OOP. Others like me decided to code their own object-oriented dialects of Lisp. Solutions they came up with are very different. I checked the following Object-Oriented dialects of Lisp:

  • RLisp - Lisp integrated with Ruby
  • e7 - Lisp integrated with Python
  • goo - Object-Oriented Lisp inspired by Scheme
  • CLOS - Object-Oriented system built on top of Common Lisp
  • I also wanted to check Coke, but it segfaulted at me, and the last thing I felt like doing was debugging broken C code.
In all four I tried to write the same snippet:
  • Define class Point representing 2D points of vectors
  • Define initializer for this class, which takes 2 arguments x and y and returns a Point instance
  • Define a method for stringifying Points, like Ruby's to_s and Python's __str__. If possible, I wanted it to be automatically called by REPL and (print a_point) or its equivalent.
  • Define a method for adding two Points. I wanted to call it + if possible.
  • Create two points, add them, and print the result.
RLisp code:
(let Point [Class new])
(class Point
(attr-reader 'x)
(attr-reader 'y)
(method initialize (x y)
(set! @x x)
(set! @y y))
(method to_s ()
"<#{@x},#{@y}>")
(method + (other)
[Point new (+ [self x] [other x]) (+ [self x] [other y])]))

(let a [Point new 1 5])
(let b [Point new -2 9])
(print [a + b])


e7 code:
(class Point ()
(def (init self x y)
(set-self x x y y)))
(defmethod (+ (self Point) (other Point))
(Point
(+ self.x other.x)
(+ self.y other.y)))
(defmethod (print (self Point) f)
(fwrite f (format "<%s,%s>" self.x self.y)))

(def a (Point 1 5))
(def b (Point -2 9))

(print (+ a b))


goo code:
(dc <point> (<any>))
(dp point-x (<point> => <num>))
(dp point-y (<point> => <num>))

(dm point-new (x|<num> y|<num>)
(new point-x x point-y y))

(dm point-add (p1|<point> p2|<point> => <point>)
(point-new
(+ (point-x p1) (point-x p2))
(+ (point-y p1) (point-y p2))))

(dm write-point (port|<out-port> x|<point>)
(msg port "<%s,%s>" (point-x x) (point-y x)))

(dv a (point-new 1 5))
(dv b (point-new -2 9))

(write-point out (point-add a b))
(newline out)


CLOS code:
(defclass point ()
((x :reader point-x :initarg :x)
(y :reader point-y :initarg :y)))
(defmethod make-point (x y)
(make-instance 'point :x x :y y))
(defmethod point-add (a b)
(make-point
(+ (point-x a) (point-x b))
(+ (point-y a) (point-y b))))

(defmethod point-print ((p point))
(format t
"<~s,~s>" (point-x p) (point-y p)))

(setf a (make-point 1 5))
(setf b (make-point -2 9))
(point-print (point-add a b))


The first thing I noticed is how different these snippets look in spite of doing pretty much the same thing. The second is that RLisp and e7 are much more concise than goo and CLOS. RLisp and e7 have more syntactic extensions for OO. RLisp supports [ ] syntax for method calls, self for message receiver, and @ivar for instance variables. e7 doesn't go that far and limits itself to obj.attr syntax for attribute access and method calls. In e7 like in Python all attributes are public. In RLisp like in Ruby all attributes are private, and (attr-reader 'x) must be explicitly called.

In RLisp and e7 attributes are dynamic and aren't predeclared anywhere. In goo and CLOS list of attributes is part of class definition. goo even requires attribute types, but will happily accept <any>. Only RLisp seemed to provide a clear way of stringifying objects. recurring-write in goo converts standard objects to strings, but write for some reason ignored extensions of it. In e7 the standard way is overloading print. It seems more limited than stringification method, but it should be possible to print to string buffer instead of a real file. I have no idea what CLOS uses to stringify objects.

The most important ideological difference is treatment of method calls. RLisp makes message sends and function calls separate operations much like Smalltalk-style OOP languages. All others define methods as some kind of generic functions. This means weaker encapsulation and some deep philosophical differences. Coke also separates function calls and message sends, but like I said it was segfaulting, so I was unable to take a closer look at it.

Only in RLisp creating a class and defining stuff inside it are separate operations. Ruby is ambiguous as class Foo can either define a new class or reopen existing class, and RLisp tried to avoid this ambiguity. Of course it's possible to do both with a simple macro. It increased verbosity of code somewhat.

In e7 class is also a constructor. In RLisp it's just an object. CLOS and goo seem to treat classes differently from other objects.

goo and CL provided only REPL environment by default, and didn't like running scripts. RLisp and e7 supported REPL and script mode without any extra hassle.

From a purely subjective point of view, I liked RLisp way most, what's not particularly surprising coming from RLisp's author ;-). Coding in e7 also felt good. On the other hand goo and especially CLOS felt rather unelegant and unpleasant.

Tuesday, June 19, 2007

COBOL and Fortran evidence for Yannis's Law

il gato carnavale by allfr3d from flickr (CC-NC)

Many people find it hard to believe how much programmer productivity increased. For them I have two good examples - CGI script in Fortran, and Sudoku solver in COBOL.

People actually used to code stuff like:

      Write(6,189)
Write(6,190) QS(7:7),QS(8:8),QS(9:9),QS(10:10),QS(11:11),QS(12:12)

189 Format('<Table border=0><TR><TD bgcolor=' '#FFFFFF' '>')
190 Format('Submitted color= 'AAAAAA' </TD></TR></Table>')

Write(6,193)
193 Format('<BR>*</TD></TR>')
Go to 320
else if(j.ne.0) then

and even:
           DISPLAY 'PT3-W700      = ' PT3-W700.
DISPLAY 'WAGON-CNT-W700= ' WAGON-CNT-W700.

DISPLAY 'ARRAY-C:'.

PERFORM VARYING SUB17 FROM 1 BY 1
UNTIL SUB17 > 81
OR ARRAY-C-NUM (SUB17) = ZERO
DISPLAY ARRAY-C-NUM (SUB17) SPACE
ARRAY-C-POSS (SUB17)
END-PERFORM.

It's not just Ruby vs Python vs Java vs Haskell vs Erlang vs Arc thing. There are things far worse than Java. I'm not sure about COBOL vs C++ though.