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

Tuesday, May 08, 2007

New parser for RLisp - with string interpolation and regexps

Felipe by José Luna from flickr (CC-NC-SA)
A few hours ago I wrote about syntax supported by RLisp and complained that it lacked decent String interpolation and Regexp syntax.

After writing that I tried to add support for both to the existing ANTLR-based parser. Unfortunately the code generated for parsing interpolated strings raised exceptions instead of backtracking. I think I understand why it was happening, but I didn't see any obvious way of fixing it without making the grammar exceedingly complicated. So I rewrote it all with a bunch of regular expressions for lexer and recursive descend for a parser. Lisp parsers are easy. Now it's possible to write arbitrary RLisp code inside interpolated strings, and write regexps which aren't any uglier than usual:

rlisp> (let m ["40 + 2 = #{(+ 40 2)}" match /(\d+)$/])
#<MatchData:0xb7cacf94>
rlisp> [m get 1]
"42"

Perl-style $1, $2, $~, $` etc. are not supported, only explicit MatchData. $~ support in Ruby is already a big ugly hack (in Perl too, but in Perl everything is a big ugly hack, so it doesn't stick out that much). I'd rather see some clever macros for that. If macro solution won't be possible, I'll try adding $~ and friends to RLisp somehow.

And while we're talking about parsers, RLisp has half-decent backtraces (it had them with the old parser too, I just never got to write about it), with file names, line numbers and function names mostly right:

$ ./rlisp.rb
rlisp> (defun f (x) (g x))
#<Proc:0xb7c276dc@STDIN:1>
rlisp> (map f (list 1 2 3))
No such global variable: g
./rlisp.rb:376:in `default_globals'
STDIN:1:in `call'
STDIN:1:in `default'
STDIN:1:in `[]'
STDIN:1:in `f'
stdlib.rl:112:in `map'
stdlib.rl:112:in `send'
stdlib.rl:112:in `map'
STDIN:2:in `call'
STDIN:2:in `run'
./rlisp.rb:787:in `run'
./rlisp.rb:798:in `repl'
./rlisp_grammar.rb:30:in `each_expr'
./rlisp.rb:796:in `repl'
./rlisp.rb:884:in `main'
./rlisp.rb:888

The rewrite also reduced size of RLisp package from 1MB to some 30kB - earlier it included ANTLR jars just in case someone wanted to play with the grammar.

RLisp syntax for literals

Evil cat by scooter.john from flickr (CC-NC)Every language nowadays requires rich syntax for literals.

Here's a table for RLisp. The lists may seems a bit redundant, but it's basically nicely formatted test set data.

I don't think there's sufficient support for String and Regexp literal syntax.

ClassRLispRubyAST RepresentationNotes
TrueClasstruetrueGlobal identifier true
#ttrueGlobal identifier true (translated inside parser)Scheme compatibility only.
FalseClassfalsefalseGlobal identifier false
#ffalseGlobal identifier false (translated inside parser)Scheme compatibility only.
NilClassnilnilGlobal identifier nil
Integer (Fixnum and Bignum)00Integer object
-0-0
55
-5-5
1234567890123456789012345678901234567890Bignum
-12345678901234567890-12345678901234567890
0x12340x1234Hex
-0x1234-0x1234
07550755Octal
-0755-0755
0b100110b10011Binary
-0b10011-0b10011
Float0.00.0Float objects
-0.0-0.0
5.05.0
-5.0-5.0
3.143.14
-3.14-3.14
1e61e6
-1e6-1e6
1.234e61.234e6
-1.234e6-1.234e6
1.234e+61.234e+6
-1.234e+6-1.234e+6
1.234e-61.234e-6
-1.234e-6-1.234e-6
Array (like "lists" in other Lisps)()[][]Bare non-empty lists are considered function applications.
(list 1 2 3)[1, 2, 3][:list, 1, 2, 3]
'(1 2 3)[1, 2, 3][:quote, [1, 2, 3]]
`(1 2 3)[1, 2, 3][:quasiquote, [1, 2, 3]]
`(1 ,(+ 2 3) 6)[1, 2+3, 6][:quasiquote, [1, [:unquote, [:+, 2, 3]], 6]]
`(1 2 ,@(list 3 4 5))[1, 2, *[3, 4, 5]][:quasiquote, [1, [:"unquote-splicing", [:list, 3, 4, 5]], 6]]
(list 1 2 . (list 3 4 5))[1, 2, *[3, 4, 5]][:list, 1, 2, :".", [:list, 3, 4, 5]]. and & have special meaning in function applications, a bit like Scheme "."/Ruby "*", and Ruby "&".
Range[Range new 1 25]1..25Plain method call
[Range new 2 25 false]2..25
[Range new 3 25 true]3...25
(.. 4 25)4..25Global function ..
(... 5 25)5...25Global function ...
[6 .. 25]6..25Method Object#.. in rlisp_support.rb
[7 ... 25]7...25Method Object#... in rlisp_support.rb
Symbol'foo:foo[:quote :foo]When symbols are evaluated, ., & and self are magical, lowercase are RLisp variables, and uppercase (possibly with ::s inside) are Ruby global constants (but RLisp Array means Ruby ::Array really). In data mode (when quoted, or passed to macros) all symbols are equal. To create unique symbol use (gensym).
foo-bar:"foo-bar"[:quote :"foo-bar"]Symbols can contain some characters that require special escaping in Ruby, like -.
'@foo:@foo[:quote :@foo]
'foo?!?!:"foo?!?!"[:quote :"foo?!?!"]
Hash(hash){}(hash ...) is a macro which expands to [Hash new] and some Hash#[]= calls.
(hash 1 => 2 3 => 4){1 => 2, 3 => 4}
(hash 'foo => 42 'bar => 96){:foo => 42, :bar => 96}
(hash foo: 42 bar: 96){:foo => 42, :bar => 96}Hashes indexed by constant Symbols are so common that they have special syntax (generic syntax still works).
Time[Time now]Time.nowPlain method call.
[Time at 1178573823]Time.at(1178573823)Seconds since Unix epoch
String"Hello""Hello"String object
"Hello, world!\n""Hello, world!\n"Backslash escapes work, #{...} does not.
(str "2 + 2 = " (+ 2 2))"2 + 2 = #{2 + 2}"(str ...) global function which calls #to_s and joins results.
Regexp(rx "foo")/foo/Calls to global function (rx ...) which calls Regexp.new.
(rx "(?i:foo)")/foo/i or /(?i:foo)/
(rx "\\d+")/\d+/Double-escaping is necessary.

Monday, May 07, 2007

Quake-style console for KDE - yakuake

yakuake screenshot by taw (public domain)I played with harnir's fvwm-crystal (screenshots) for a few days. I'm back to KDE now, but one feature was simply too awesome to miss - the Quake-style konsole.

It turns out KDE supports Quake-style konsole too with yakuake package (sudo apt-get install yakuake). Before that I used to keep multitab konsole on virtual desktop 1 (empty now), but I like yakuake much more. The only thing I changed was key binding from truly horrible F12 to Alt-` (run yakuake, press down arrow in lower right corner, select Change Access Key...).

You can see yakuake on the screenshot. It supports multiple tabs, automatically hides when it loses focus, and is based on KDE konsole, which in my experience tends to be a much better terminal emulator than all xterm-based stuff.

Sunday, May 06, 2007

How to test glue code ?

Let Me Out!!! by Plastic Jesus from flickr (CC-NC-SA)There's something I don't know about software development, and I'd like to know. Everybody believes Test-Driven Development is the right way to build software, and it's very easy to develop libraries this way, and still reasonably easy to develop applications, but how does one even test glue code ?

The software which got me thinking about this is my iPod-last.fm bridge. It extracts song statistics from an iPod and submits them to last.fm.

It's a bit over 200 lines of code, and it had a few bugs:

  • The magic constant to convert time was off by an hour. My iPod had DST settings wrong, and I miscalculated the constant so the result was right for my iPod.
  • It assumed record size was 16-bytes instead of looking at the headers. Older iPods had 12-byte records.
  • It expected upper-case MD5 in response from last.fm. last.fm switched to sending lower-case MD5s later.
  • Documentation didn't state that Ruby version 1.8.3 or newer is required, and it won't work with Ruby 1.8.2.
Four non-trivial bugs in 200 lines of code is a horrible ratio. What should be done to reduce number of bugs ?

The script is very simple glue code, and it glued things on which it was tested perfectly - Ruby 1.8.4, an iPod with 16-byte records and broken DST settings, whichever version of software last.fm used when I coded the script.

I don't see how it would be possible to test such script. Building simple mock iPod or mock last.fm server wouldn't find any of the bugs, and complex mocks would be far more complex than the script itself, and most likely would contain even more bugs.

I didn't think about testing it with Ruby 1.8.2, as from Linux (crontabbed apt-get upgrade) perspective this version was ancient, it requires effort to install multiple minor versions of Ruby on Ubuntu, and I didn't expect any problems there. After discovering a few more minor incompatibilities, I automatically run unit tests for all my Ruby code on 1.8.4, 1.8.5, 1.8.6, and 1.9. I don't think I need to support 1.8.2 or 1.8.3, but I'd like to be able to know what is supported and what isn't.

I somehow don't see code review finding any of these problems. If I was doing code review, I think I'd be unlikely to question 2082848400 time conversion magic, 16-byte record size, upper case assumption in MD5 rensponse format regexp, or to ask if it would work with very old versions of Ruby would.

Not a single one of this bug could be found by static typing, no matter how strict, or by avoiding side effects.

Releasing the code found 3 of 4 bugs, and they were fixed in a few minutes at most each. Nobody cared enough about time being off by 1 hour to report it, and I found it on my own while playing with iPod settings.

I think it's a typical case for glue code. Very simple code works with some complex systems, and makes assumptions about them, some of which may later prove unwarranted. Testing, code review, static typing and other standard recipes for reducing bug counts don't seem to be working. Most likely they would simply greatly increase amount of code and work. Releasing the code in the wild seems to be very effective (but it failed to find the time bug).

Is it really the best solution we know ?

Saturday, May 05, 2007

Disease eradication

Neska posant el perfil bo by Ainhoa P from flickr (CC-BY)It's safe to say that the vast majority of human suffering is caused by actions and inaction of other people.

Probably the most abominable of these actions is forcing people to live in places where they were born, also known in "developing countries". Contrary to the name, most of these countries aren't "developing" much. A quick glance at life expectancy statistics for 1998 and 2006, an arbitrary cutoff of 73.5 years chosen to be the definition of a "developed country", and naive extrapolation, shows that 83 of 190 countries aren't going to get "developed" in the next 25 years.

Developed countries (life expectancy, and increase since 1998):

  • Andorra - 83.51yr (+0.01)
  • Singapore - 81.71yr (+1.61)
  • San Marino - 81.71yr (+0.61)
  • Japan - 81.25yr (+0.55)
  • Sweden - 80.51yr (+0.91)
  • Switzerland - 80.51yr (+0.91)
  • Australia - 80.50yr (+0.70)
  • Iceland - 80.31yr (+0.91)
  • Canada - 80.22yr (+0.82)
  • Italy - 79.81yr (+0.81)
  • France - 79.73yr (+0.93)
  • Monaco - 79.69yr (+0.89)
  • Liechtenstein - 79.68yr (+0.88)
  • Spain - 79.65yr (+0.85)
  • Norway - 79.54yr (+0.84)
  • Israel - 79.46yr (+0.86)
  • Greece - 79.24yr (+0.84)
  • Austria - 79.07yr (+1.37)
  • Malta - 79.01yr (+1.11)
  • Netherlands - 78.96yr (+0.66)
  • Luxembourg - 78.89yr (+1.79)
  • New Zealand - 78.81yr (+1.01)
  • Germany - 78.80yr (+1.40)
  • Belgium - 78.77yr (+0.97)
  • United Kingdom - 78.54yr (+0.84)
  • Finland - 78.50yr (+1.10)
  • Jordan - 78.40yr (+1.00)
  • Bosnia and Herzegovina - 78.00yr (+6.50)
  • United States - 77.85yr (+0.75)
  • Cyprus - 77.82yr (+1.12)
  • Denmark - 77.79yr (+1.29)
  • Ireland - 77.56yr (+0.76)
  • Portugal - 77.53yr (+1.73)
  • Republic of China (Taiwan) - 77.26yr (+0.86)
  • Albania - 77.24yr (+5.64)
  • Cuba - 77.23yr (+1.03)
  • Kuwait - 77.03yr (+2.53)
  • South Korea - 76.85yr (+2.45)
  • Costa Rica - 76.84yr (+1.04)
  • Chile - 76.58yr (+0.88)
  • Libya - 76.50yr (+1.00)
  • Ecuador - 76.21yr (+5.11)
  • Slovenia - 76.14yr (+1.24)
  • Uruguay - 76.13yr (+0.93)
  • Czech Republic - 76.02yr (+1.52)
  • Argentina - 75.91yr (+0.81)
  • Georgia - 75.88yr (+11.38)
  • Saudi Arabia - 75.46yr (+7.66)
  • Panama - 75.25yr (-0.25)
  • United Arab Emirates - 75.24yr (+1.14)
  • Mexico - 75.19yr (+3.69)
  • Paraguay - 74.89yr (+1.19)
  • Tunisia - 74.89yr (+1.19)
  • Brunei - 74.80yr (+1.20)
  • Poland - 74.74yr (+1.54)
  • Serbia and Montenegro - 74.73yr (+2.33)
  • Dominica - 74.65yr (+1.25)
  • Slovakia - 74.50yr (+0.80)
  • Croatia - 74.45yr (+0.75)
  • Venezuela - 74.31yr (+1.21)
  • Bahrain - 74.23yr (+1.23)
  • Lithuania - 73.97yr (+4.87)
  • Macedonia - 73.73yr (-0.07)
  • Qatar - 73.67yr (+1.27)
  • Saint Lucia - 73.61yr (+1.31)
Developing countries (life expectancy, increase since 1998, time to become "developed"):
  • Algeria - 73.00yr (+3.30, 1.21yr)
  • Brazil - 71.69yr (+8.79, 1.65yr)
  • Sri Lanka - 73.17yr (+1.37, 1.93yr)
  • Oman - 73.13yr (+1.33, 2.23yr)
  • Egypt - 71.00yr (+7.70, 2.60yr)
  • Armenia - 71.55yr (+5.15, 3.03yr)
  • Thailand - 71.95yr (+3.35, 3.70yr)
  • Solomon Islands - 72.66yr (+1.36, 4.94yr)
  • Lebanon - 72.63yr (+1.33, 5.23yr)
  • Estonia - 71.77yr (+2.27, 6.10yr)
  • Marshall Islands - 70.01yr (+4.51, 6.19yr)
  • Mauritius - 72.38yr (+1.38, 6.49yr)
  • Turkey - 72.36yr (+1.36, 6.71yr)
  • Malaysia - 72.24yr (+1.44, 7.00yr)
  • Latvia - 71.05yr (+2.65, 7.40yr)
  • Saint Kitts and Nevis - 72.15yr (+1.45, 7.45yr)
  • Ukraine - 69.68yr (+3.68, 8.30yr)
  • Hungary - 72.40yr (+1.00, 8.80yr)
  • Kyrgyzstan - 68.16yr (+4.76, 8.97yr)
  • Antigua and Barbuda - 71.90yr (+1.40, 9.14yr)
  • Seychelles - 71.82yr (+1.42, 9.46yr)
  • Colombia - 71.72yr (+1.42, 10.03yr)
  • Bulgaria - 72.03yr (+1.13, 10.41yr)
  • People's Republic of China - 72.27yr (+0.87, 11.31yr)
  • Romania - 71.35yr (+1.45, 11.86yr)
  • Philippines - 69.91yr (+2.41, 11.92yr)
  • El Salvador - 71.22yr (+1.52, 12.00yr)
  • Guatemala - 69.06yr (+2.86, 12.42yr)
  • Morocco - 70.66yr (+1.56, 14.56yr)
  • Samoa - 70.72yr (+1.52, 14.63yr)
  • Nicaragua - 70.33yr (+1.63, 15.56yr)
  • Cape Verde - 70.45yr (+1.55, 15.74yr)
  • Kazakhstan - 66.55yr (+3.35, 16.60yr)
  • Iraq - 68.70yr (+2.20, 17.45yr)
  • Palau - 70.14yr (+1.54, 17.45yr)
  • Vietnam - 70.61yr (+1.31, 17.65yr)
  • Burma - 60.70yr (+5.80, 17.66yr)
  • Syria - 70.03yr (+1.53, 18.14yr)
  • Fiji - 69.53yr (+1.63, 19.48yr)
  • Tonga - 69.53yr (+1.63, 19.48yr)
  • Indonesia - 69.57yr (+1.57, 20.03yr)
  • Uganda - 51.59yr (+8.69, 20.17yr)
Stagnant countries (life expectancy, increase since 1998, time to become "developed"):
  • North Korea - 71.37yr (+0.67, 25.43yr)
  • Tuvalu - 68.01yr (+1.71, 25.68yr)
  • Federated States of Micronesia - 69.75yr (+1.15, 26.09yr)
  • Rwanda - 46.96yr (+7.66, 27.72yr)
  • Gabon - 55.02yr (+4.92, 30.05yr)
  • Sao Tome and Principe - 66.99yr (+1.69, 30.82yr)
  • Republic of the Congo - 52.26yr (+4.86, 34.96yr)
  • Bolivia - 65.50yr (+1.80, 35.56yr)
  • Papua New Guinea - 64.93yr (+1.83, 37.46yr)
  • India - 64.35yr (+1.85, 39.57yr)
  • Maldives - 64.06yr (+1.86, 40.60yr)
  • Guyana - 65.50yr (+1.50, 42.67yr)
  • Pakistan - 63.00yr (+1.90, 44.21yr)
  • Haiti - 52.92yr (+3.72, 44.26yr)
  • Nauru - 62.73yr (+1.93, 44.64yr)
  • Eritrea - 58.47yr (+2.67, 45.03yr)
  • Burundi - 50.29yr (+4.09, 45.40yr)
  • Vanuatu - 62.49yr (+1.89, 46.60yr)
  • Comoros - 61.96yr (+1.96, 47.10yr)
  • Cambodia - 58.92yr (+2.42, 48.20yr)
  • Yemen - 61.75yr (+1.95, 48.21yr)
  • Bangladesh - 62.08yr (+1.88, 48.60yr)
  • Kiribati - 61.71yr (+1.91, 49.38yr)
  • Guinea - 49.36yr (+3.76, 51.36yr)
  • Belarus - 68.72yr (+0.72, 53.11yr)
  • Ethiopia - 48.83yr (+3.63, 54.37yr)
  • Nepal - 59.80yr (+2.00, 54.80yr)
  • Togo - 57.01yr (+2.31, 57.11yr)
  • Cote d'Ivoire - 48.62yr (+3.42, 58.20yr)
  • Sudan - 58.54yr (+1.94, 61.69yr)
  • Malawi - 41.43yr (+3.83, 66.99yr)
  • Benin - 52.66yr (+2.46, 67.77yr)
  • Madagascar - 56.95yr (+1.95, 67.90yr)
  • Laos - 55.08yr (+1.98, 74.42yr)
  • Bhutan - 54.39yr (+1.99, 76.82yr)
  • Democratic Republic of the Congo - 51.10yr (+2.30, 77.91yr)
  • Mauritania - 52.73yr (+1.93, 86.09yr)
  • Mozambique - 40.32yr (+2.82, 94.13yr)
  • Moldova - 65.18yr (+0.68, 97.88yr)
  • Mali - 48.64yr (+1.94, 102.52yr)
  • Somalia - 48.09yr (+1.89, 107.56yr)
  • Zambia - 39.70yr (+2.50, 108.16yr)
  • Iran - 69.96yr (+0.26, 108.92yr)
  • Niger - 43.50yr (+2.20, 109.09yr)
  • Ghana - 58.47yr (+1.07, 112.37yr)
  • Burkina Faso - 48.45yr (+1.75, 114.51yr)
  • Uzbekistan - 64.19yr (+0.49, 152.00yr)
  • Tajikistan - 64.56yr (+0.46, 155.48yr)
  • Namibia - 43.93yr (+1.43, 165.43yr)
  • Azerbaijan - 63.35yr (+0.45, 180.44yr)
  • Turkmenistan - 61.39yr (+0.49, 197.71yr)
  • The Gambia - 53.75yr (+0.55, 287.27yr)
  • Angola - 38.43yr (+0.13, 2158.15yr)
  • Grenada - 64.53yr (+0.03, 2392.00yr)
  • Zimbabwe - 37.82yr (+0.02, 14272.00yr)
  • Kenya - 47.99yr (-0.01, never)
  • Russia - 67.10yr (-0.10, never)
  • Barbados - 72.59yr (-0.41, never)
  • Peru - 69.53yr (-0.47, never)
  • Honduras - 69.30yr (-0.60, never)
  • Central African Republic - 43.39yr (-0.61, never)
  • Trinidad and Tobago - 66.73yr (-1.27, never)
  • Dominican Republic - 71.44yr (-1.76, never)
  • Jamaica - 73.33yr (-1.87, never)
  • Guinea-Bissau - 46.61yr (-2.39, never)
  • Suriname - 68.96yr (-2.44, never)
  • Belize - 68.44yr (-2.46, never)
  • Mongolia - 64.52yr (-2.78, never)
  • Afghanistan - 42.90yr (-3.00, never)
  • Senegal - 58.90yr (-3.30, never)
  • Chad - 47.18yr (-3.32, never)
  • Equatorial Guinea - 49.70yr (-3.90, never)
  • Cameroon - 50.89yr (-3.91, never)
  • Nigeria - 46.74yr (-4.86, never)
  • Botswana - 33.87yr (-5.43, never)
  • Sierra Leone - 39.87yr (-5.43, never)
  • The Bahamas - 65.54yr (-5.56, never)
  • Tanzania - 45.24yr (-7.06, never)
  • Swaziland - 33.22yr (-7.18, never)
  • Djibouti - 43.10yr (-7.70, never)
  • South Africa - 43.27yr (-7.83, never)
  • Liberia - 38.89yr (-12.11, never)
  • Lesotho - 34.47yr (-16.33, never)
Extrapolation has very high error, so each entry on the list can be disputed, but in any case by forcing people who happen to be born in these countries to live there instead of letting them move somewhere else, people are responsible for making new generations of people suffer.

There's nothing inherent about the yet unborn people in Lesotho and other fucked-up places that makes places where they live so fucked up. They just happen to be born where there is no basic healthcare, no viabale economy, no political institutions guaranteeing rule of law, respect for human rights, democracy and so no, and are forced to suffer from all that.

But xenophobia is as strong as ever. The same people who are obsessed about the Holocaust, WTC attacks, and Virginia Tech shootings, are complacent about other genocides, suicide attacks on universities and other places and other catastrophes, at least as long as they don't affect people of European descent, or whatever definition of "us" and "them" they have.

It seems that humans are evolutionarily highly predisposed to xenophobia, and typically care very little about hurting "out-group" people through actions, and not at all about doing so through inaction.

Disease eradication

Over one billion people suffer from diseases caused to being born in the wrong place. In otherwise healthy individuals, and with access to modern medicine, few infectious diseases are live-threatening or seriously debilitating. So most people living in the developed world tend not to care too much about them.

But infectious diseases have a nice side to them. They can in principle be completely eradicated. If the only way to get sick is by contacting an infectious organism, and the only way these organisms can proliferate is by infecting people, then it's enough to break this cycle once and a disease is completely eliminated.

So far only one major diseas was completely eradicated - smallpox. The cost was about US$300 million, that is about one day of ocupation of Iraq (probably a few days, adjusting for inflation). Before it was eradicated, it killed about 2 million people a year.

Currently the largest eradication effort concerns poliomyelitis, with number of cases dropping from estimated 350,000 a year to less than 2,000 a year, but eradication is taking much longer than planned. The cost so far was US$ 3 billion, or ten Iraq-days.

Efforts to eradicate dracunculiasis reduced number of affected people from 3.5 million in the 1980s to about 10,000 in 2005, at cost of US$ 90 millions, or 7 Iraq-hours.

There are realistic plans to eradicate measles, mumps, and rubella. A limited effort to fight measles reduced number of yearly deaths 871,000 (1999) to 454,000 (2004), at cost of $308 million. that is about 1 Iraq-day.

Not every disease can be easily eradicated. Efforts to eradicate malaria failed when mosquitos which transmitted it became immune to insecticides. It doesn't mean we cannot try a different way in the future. We known a lot more about malaria and about mosquitos than we used to, and we have better methods.

It wouldn't be eradication, but occurrence of many diseases like cholera can be greatly reduced by ensuring access to safe drinking water, better nutrition, and letting people in refuge camps (some of the most dangerous places to live) back home, or wherever, as long as it doesn't involve not thousands of people cramped in small space in unsanitary conditions. The cost would be a few Iraq-days at most.

Conclusion

The conclusion is simple - if occupation of Iraq ceased, and the money was spent on global health care instead (for just a month or two), it would save tens of millions of people a year from death, hundreds of millions a year from other infections, and made the world a much better place. And somehow I just don't see it happening.

Wednesday, May 02, 2007

Kingmaker

”The king of Cats”  Kissie!!! by rubyran from flickr (CC-BY)Long time ago, before Web 2.0, before Web 1.0 even, there was a computer game "Kingmaker", closely based on a board game with the same name. Out of nostalgia I wanted to try it out again, a decade later.

The first impression - abandonware websites are not what they used to be. The download links often don't work, and one of the website was bold enough to require you to comment spam some blog with link to them before it would let you download. One spam per downloaded file (a few MBs). And even then the only way to download is using their download manager program, possibly infested with some spyware.

Using a trivial "workaround" of creating an html file with link to them and deleting it immedately afterwards I got Kingmaker zip, badly scanned manual, and something that claimed to be "a crack", but didn't really do anything.

The game worked fine in a dosbox. To start it typed dosbox -c 'mount c ~/kingmaker', then c:, and finally king. The correct sound settings from the startup menu were "Adlib/Sound Blaster" and "No Speech". I don't really remember if speech worked in the original version, but it doesn't in the dosbox, and it's not really important for the gameplay anyway.

In the default settings dosbox uses very little CPU, and the game is slow. Pressing Ctrl-F12 a few times tells it to use more CPU, Ctrl-F11 to use less, Alt-Enter to toggle fullscreen mode, and Ctrl-F10 to release the mouse - normally once the mouse is captured it stays in the dosbox. That's all I needed to learn about dosbox.

The game

In the game the human player and between 1 to 5 computer players control factions in War of the Roses (1455 - 1487), each trying to get their royal heir crowned, and all other eliminated. The rolay heirs are merely puppets here, the faction can change their mind about who has the most rightful claim as often as they wish.

First, a few gameplay tips.
  • When fighting a battle, it's usually better to control manually than to let computer decide the outcome. That's true for pretty much every game where there is such a choice. In manually controlled battles there are no stalemates, and your nobles won't risk their lives when fighting against much smaller enemy armies. You also have a change of winning with a somewhat smaller force - in computer-controlled battles the only possible outcomes are "bigger force wins", and "stalemate" (plus a small chance of each noble dying). You should only let computer decide when you have no chance anyway, and want a chance of killing some enemies or saving your army by a stalemate.
  • When you control the only king (or Chancellor if there are 2 or no kings), you can summon the Parliament. This can easily win the game - you can give your nobles a lot of titles and offices, and force enemies to come to the Parliament, even if they're hiding in Ireland or Calais. If there are too many titles and offices, give some of them to the least important enemy nobles.
  • The easy win strategy is grabbing any royal heir, keeping them safely somewhere, and hunting small enemy nobles. You will gradually grow in power, while others will keep fighting each other. Just keep harassing others and keep your nobles safe.
  • You can move mercenaries between nobles at any time. Just move them each turn to wherever they're most needed. You can move bishops too - if you have a crownable heir somewhere and need to crown them, just reattach bishops to the right noble. And you can move ships, but that's just to
  • If your nobles are captured in battle, computer will sometimes demand ransom. Usually the ransom isn't high, so just accept it. You can demand ransom too, but it's safer to execute them all.
  • In basic plague mode stay in castles not cities, to avoid plagues. In advanced plague mode move away from infected area.
  • In advanced weather mode if you get "severe storms, movement restricted", you cannot fight, so don't even bother. Computer doesn't seem to know about it.
  • Don't bother conquering random castles and cities. The chance of your nobles dying is much greater than the benefit. Conquer only if there is something inside (heir or enemies), or you have some use for the castle/city.
  • If there are many factions, the resource stack is going to become empty. Lost titles and offices do not get back to the stack (they can only be given by the Parliament), only nobles, bishops, and soldiers do. If the stack is empty, and one noble dies in your turn (killed by you, or by enemy), you will get them. So you can safely take 10-troop noble and attack (computer control) a big enemy army. Either they die and you get them back anyway, or they die and kill someone in process, and you might get that someone. Or you can attack small enemy nobles with your big armies (manual control) - you will get whoever you killed.
The biggest problem with the game are long periods during which nothing happens. After initial chaotic phase all factions consolidate their armies, keep their heirs safe somewhere, and everybody is waiting for some random event to tip the balance. It can take half an hour, and then suddenly something happens and the game is over. AI is not too smart, for one it never summons the Parliament. The interface is a bit annoying, especially for splitting armies and for Parliament, but not much more so than in other old games.

The DRM

The game contains an unusual DRM. You are shown a picture of some location, and have to look it up it the manual and type. The locations are (by page, some pages contain no picture):
  • 5 ALNWICK
  • 6 ARUNDEL
  • 7 ASHBY
  • 8 BAMBURGH
  • 9 BATH
  • 11 BELVOIR
  • 12 BRISTOL
  • 14 CAERNARVON
  • 15 CAISTER
  • 16 CANTERBURY
  • 17 CARDIFF
  • 18 CARISBROOKE
  • 19 CARLISLE
  • 20 CHESTER
  • 21 CHICHESTER
  • 22 CHIRK
  • 24 CONISBOROUGH
  • 25 CONWAY
  • 26 CORFE
  • 28 DOVER
  • 29 FRAMLINGHAM
  • 30 HARLECH
  • 32 HELMSLEY
  • 33 HEREFORD
  • 36 LEEDS
  • 37 LICHFIELD
  • 38 LINCOLN
  • 39 LONDON
  • 40 LUDLOW
  • 41 NORWICH
  • 42 NOTTINGHAM
  • 44 OXFORD
  • 46 RABY
  • 47 RICHMOND
  • 48 ROCKINGHAM
  • 49 SALISBURY
  • 50 ST.ALBANS
  • 52 ST.DAVID'S
  • 54 TATTERSHALL
  • 57 WARWICK
  • 59 WELLS
  • 60 WINDSOR
  • 61 WINGFIELD
  • 62 YORK
The pictures in the scanned manual which is available online are big black blobs, so you can't use them. The only easy way I found was starting up a second instance of Kingmaker and checking all possible answers there (the game gives an 11-page range, so it's not that bad). You have to go through this only once - then simply don't quit the program.

One could also make a lot of screenshots and automatically extract the pictures, but I was too lazy for that.

Wednesday, April 25, 2007

Unit testing for RLisp

hoshi loves rawhide by paul+photos=moody from flickr (CC-NC)

I've been coding RLisp pretty much continuously since about one week before RuPy 2007. Even a temporary switch to different hardware and revision control system did not make me stop.

Turning RLisp into something more widely usable seems like a huge task. Every new language is expected to come with full CPAN out of the box. I don't know if RLisp will ever get there, but I should at least cover the few most important targets, like unit testing and web development frameworks. Of course I' not going to code them on my own. Like every good programmer I'm way too lazy and impatient for that, and and adding nice interfaces to existing Ruby stuff achieves far more in a lot less time and effort.

At first I implemented all tests in plain Ruby with a few helper methods.

class Test_RLisp_stdlib < Test::Unit::TestCase
def setup
@rlisp = RLispCompiler.new
@rlisp.run_file("stdlib.rl")
end
def assert_runs(code, expected)
assert_eql(expected, @rlisp.run(RLispGrammar.new(code).get_expr))
end
def test_double
run_rlisp("(let double (fn (x) (* x 2)))")
assert_runs("(double 5)", 10)
assert_runs("(double 11.0)", 22.0)
end
...
end


Testing plain functions worked well enough, testing macros that way turned to be much more difficult, and I wanted to code something in RLisp.

A functional prototype took no time and it looked fairly well:

(ruby-require "test/unit")

(let Test_testing_framework [Class new Test::Unit::TestCase])
(class Test_testing_framework
(method test_assertions ()
[self assert_equal 9 (+ 2 7)]
[self assert_equal 2 (- 6 4)]
[self assert_in_delta 1.99 2.02 0.05 "Deviation is too high"]
[self assert_not_equal () nil]
[self assert_same #f false]
[self assert_same #t true]
)
)


In Ruby messages to self have nice syntax, and they're often used for designing DSLs. Unit testing language is a DSL too. Lisps are well known for their DSLs too, except that they build them with macros.

That's how the first RLisp DSL began. Syntactic sugar for test suites (classes) and tests (methods) was straightforward.

(defmacro test (name . body)
(let test_name [(+ "test_" [name to_s]) to_sym])
`(method ,test_name () ,@body)
)

(defmacro test-suite (name . body)
(let class_name [(+ "Test_" [name to_s]) to_sym])
`(do
(let ,class_name [Class new Test::Unit::TestCase])
(class ,class_name
,@body
)
)
)


It was less obvious what to do with assertions. There are too many assert_* methods, and creating one globally visible macro for each didn't sound like an exactly elegant idea. Making the macros active only within a test suite would be nicer, but I wasn't really convinced it was the best way, and besides I've never done such a thing before, it seemed complicated, and writing nontrivial macros with just defmacro and quasiquotes is very hard.

But I wasn't limited to defmacro and quasiquotes any more - the RLisp pattern matching macro (itself implemented with way too many quasiquotes) was just sitting there waiting for some action.

After some syntactic experiments I came out with this syntax:

(require "rlunit.rl")

(test-suite RLUnit
(test assertions
(assert 9 == (+ 2 7))
(assert 2 == (- 6 4))
(assert 2 == (- 6 4) msg: "Subtraction should work")
(assert 96 == (* 8 4 3))
(assert nil? nil)
(assert true)
(assert (> 3 2))
(assert msg: "assert_block failed" block: (true))
(assert (not (== 3 7)))
(assert 1.99 == 2.02 delta: 0.05 msg: "Deviation is too high")
(assert '() instance_of? Array)
(assert '(foo bar) instance_of? Array)
(assert '(foo bar) kind_of? Enumerable)
(assert () != nil)
(assert #f same: false)
(assert #t same: true)
)
)


I could have converted everything to assert_block, but it seemed more elegant to use specific assertions, mostly to reuse nice failure messages.

(defmacro assert args
(match args

('nil? a) `[self assert_nil ,a]
('nil? a 'msg: ,msg) `[self assert_nil ,a ,msg]

(a '=~ b) `[self assert_match ,b ,a]
(a '=~ b 'msg: msg) `[self assert_match ,b ,a ,msg]

(a '!~ b) `[self assert_no_match ,b ,a]
(a '!~ b 'msg: msg) `[self assert_no_match ,b ,a ,msg]

(a '!= b) `[self assert_not_equal ,a ,b]
(a '!= b 'msg: msg) `[self assert_not_equal ,a ,b ,msg]

(a 'same: b) `[self assert_equal ,a ,b]
(a 'same: b 'msg: msg) `[self assert_equal ,a ,b ,msg]

(a 'not_same: b) `[self assert_not_same ,a ,b]
(a 'not_same: b 'msg: msg) `[self assert_not_same ,a ,b ,msg]

(a 'kind_of? b) `[self assert_kind_of ,b ,a]
(a 'kind_of? b 'msg msg) `[self assert_kind_of ,b ,a ,msg]

(a 'instance_of? b) `[self assert_instance_of ,b ,a]
(a 'instance_of? b ,msg: msg) `[self assert_instance_of ,b ,a ,msg]

(a b) `[self assert_equal ,a ,b]

(a '== b 'delta: c) `[self assert_in_delta ,a ,b ,c]
(a '== b 'delta: c
'msg: msg) `[self assert_in_delta ,a ,b ,c ,msg]


(a '== b) `[self assert_equal ,a ,b]
(a '== b 'msg: msg) `[self assert_equal ,a ,b ,msg]

('block: (blk)) `[self assert_block & (fn () ,blk)]
('block: (blk) 'msg: msg) `[self assert_block ,msg & (fn () ,blk)]
('msg: msg 'block: (blk)) `[self assert_block ,msg & (fn () ,blk)]

(a) `[self assert ,a]
(a 'msg: msg) `[self assert ,a ,msg]

(raise SyntaxError [(cons 'assert args) inspect_lisp])
)
)


At first it was just a few lines, but as pattern matching is so simple I just kept adding more assertions, and then even Smalltalk-style pretty optional arguments. I'm not convinced wheather raising an exception during macro expansion is a good idea or not. Exceptions in RLisp are much less useful than in Ruby - RLisp compiler compiles RLisp to Ruby and then runs it. Unfotunately backtraces telling you that an exception came from (eval) statement aren't very useful. I pached the compiler so that at least the file names are preserved. It would be far better to have line numbers and function names, but Lisp code is usually heavily processed by macros, so most of the information is already lost before the compilation even begins. I still think it should be possible to get something that works reasonably well most of the time.

The internals have been heavily refactored. For example it's possible to freely mix Ruby and RLisp tests, and RLispCompiler will handle .rlc files and so on on its own. Brad Ediger in his RLisp plugin for Ruby on Rails simply made Ruby require statement handle RLisp files transparently. Doing so would probably require a global instance of RLispCompiler, and I was trying to make it possible to have many independent instances of RLisp running concurrently. Maybe it doesn't make that much sense - after all they will all share a single Ruby environment anyway. Right now running RLisp code takes only a bit more typing than a straight require:

require 'test_parser'
require 'test_rlvm'
require 'test_rlisp'
require 'test_run'
rlisp = RLispCompiler.new
rlisp.run_file 'stdlib.rl'
rlisp.run_file 'test_macros.rl'
rlisp.run_file 'tests/unit_test_test.rl'
rlisp.run_file 'tests/test_rlunit.rl'


$ ./test_all.rb
Loaded suite ./test_all
Started
..............................................................................................
Finished in 13.523565 seconds.

94 tests, 308 assertions, 0 failures, 0 errors


Half of the tests implemented in Ruby, half in RLisp. Here's a sample:

(defmacro assert-macroexpands (source expected-expansion)
`(assert
',expected-expansion
==
(macroexpand-rec ',source)
)
)

(test-suite OO_Macros
(test class
(assert-macroexpands
(class Foo code code2 code3)
(send Foo 'instance_eval & (fn ()
code code2 code3
))
)
(assert-macroexpands
(class Foo)
(send Foo 'instance_eval & (fn ()))
)
)
(test method
(assert-macroexpands
(method foo (args) body)
(send self 'define_method 'foo & (fn (args) body))
)
)
; Should they autoquote ?
(test attributes
(assert-macroexpands
(attr_reader 'foo)
(send self 'attr_reader 'foo)
)
(assert-macroexpands
(attr_writer 'foo)
(send self 'attr_writer 'foo)
)
(assert-macroexpands
(attr_accessor 'foo)
(send self 'attr_accessor 'foo)
)
)
)


There's plenty of other changes. Capitalized names, with ::s or not, are simply treated as Ruby constants. RLisp one-liners are possible with the usual -e syntax, dotted pair notation is supported by many operations including pattern matching (of course as RLisp uses arrays and not linked lists, it wouldn't be possible to support all use cases), #to_s_lisp (used by print) and #inspect_lisp (used by REPL) operations are now separate just like in Ruby. It should simply be a lot more fun to hack.

Tuesday, April 24, 2007

Distributed version control with SVK

charleyBook by Hackintosh from flickr (CC-NC)

I had to shut down the server with my Subversion repository for a few days. As I felt like coding and I hate coding without some sort of revision control system in place, it was the time to check out some Subversion alternatives.

I dumped my Subversion repository (svnadmin dump) and scp'ed it to another machine. Pretty much at random I picked SVK first.

It turned out what I did wasn't the right strategy for setting up a local repository - most distributed revision control systems prefer to use network connections to set up mirrors. I had possible to convert the dump back to Subversion database (svk admin load does more or less the same thing as svnadmin load), moving the imported files somewhere else, and mirroring that, using file:// protocol (svk mirror followed by svk sync -a).

That wasn't all, as one is not supposed to work on mirrors directly - the official way is to create a local branch (svk copy), commit there, and sync later. Setup was a bit compicated, and svk sync -a took over 15 minutes, but afterwards it was a pure pleasure.

Pretty much every single command I used in Subversion just worked, I only had to say svk whatever instead of svn whatever. Even svnadmin commands are available with svk admin. That's quite important, as I knew and liked Subversion already, and didn't really felt like switching paradigm more than necessary. svk was also very fast once installed. That's also a nice thing, as I tend to commit every single new unit test separately instead of doing big commits every few hours.

Well, there's not much more to add - SVK just works, and without a lenghty adjustment period.

Monday, April 23, 2007

RuPy 2007

the thicket by Steve took it from flickr (CC-NC-SA)

I've been too busy coding to write anything about it earlier, but a week and a few days ago I attended a Ruby & Python conference in Poznań - RuPy 2007.

I strongly prefer active participation, so I prepared a talk for the conference. My talk was about RLisp. I wasn't really sure if it would be well-received, as the conference was dominated by web developers, and back then RLisp didn't even have a web framework. As it turned out the reception was very enthusiastic, and many people seemed to be fascinated by the idea, even if just for the sake of geek points. What surprised me even more was that the very first person I talked with knew my blog.

Slides I prepared for the talk are available in ODP and PDF formats. The main point of my talk was that RLisp is at the same time Lisp with access to all great Ruby libraries, and Ruby with macros. There were few Lispers in the audience, but Lisp hype spread by Paul Graham and others seemed to have reached everyone. I made a bold claim that RLisp has more libraries than all other Lisps taken together. Ruby definitely does, thanks to Ruby gems, and RLisp is a fully-featured Lisp. The boldness was in my assumption that Ruby and RLisp code can seamlessly live together and naturally blend. I designed RLisp with this goal in mind, but it with so little real life testing maybe it's too early to say such things.

I think that integrating with Ruby runtime was the best possible choice. An obvious alternative from library count point of view would be Perl, but its semantics are so hideously complex that a language living in the same environment as Perl would have to be Perl, or else it would have severely restricted access to its libraries. I'm talking about Perl's semantics, not syntax. Things in Perl don't even know wheather they're equal to other things or not. Strings "00" and "0" are considered equal in some contexts, but not in others (they're ==, they are not eq, and the former is true while the latter is false). If any language were to work with Perl, it would need to support String-Number hybrids, scalar/list/void and some even more obscure contexts for all function calls, badly bolted-on OO system without even usable reflection, and it even would need to copy all ugliness of Perl references. I tried it once, it wasn't nice.

I'm not trying to bash Perl (at least not too much, it's such an easy target it wouldn't be much fun). It has many redeeming features like CPAN and focus on getting things done efficiently even if it meant breaking with holy traditions of programming language design. The last time I wrote about Perl here an anonymous reader left a truly insightful comment:
Saying "Perl is great at ..." is the same as saying "I don't know much about ...."

And that's the very point of Perl. You grab a package from CPAN, run some Unix commands, convert the data with a few one liners full of regular expression magic and you're done. There's not enough time for becoming an expert at everything. It's far more efficient to take advantage of someone else's expertise - in this case the the CPAN module's author's. Of course every now and then you get deep into something. One of the greatest things about Perl is that the community of Perl programmers developed strong traditions of sharing effects of their work, on CPAN and elsewhere.

Continuing the side note, Python seems rather unfriendly towards functional programming, and static-centric environments like JVM and .NET would most likely cause very severe impedance mismatch with a highly dynamic language like Lisp. I'm really impressed by how far JRuby guys were able to get. Code examples available online don't seem particularly drastic for code that crosses language boundaries, and between two established languages at that, with so little room for modifying either language to work better with the other.

Getting back to my RuPy talk, one of the greatest powers of Lisp are its metaprogramming facilities - having a very convenient representation for code, which can be robustly generated, transformed, and analyzed. Robust code generation is a far more important issue than most people realize. Four common bugs in run-time code generation - XSS, SQL injections, PHP includes, and format string attacks - are responsible for 40% of all security vulnerabilities (counting only vulnerabilities of known types). Unfortunately in Web 2.0 even HTML is code, highly security-critical code at that. Would you rather have robust and convenient macros for generating safe HTML, or pray every day that you never forget to escape dangerous input ? I don't want to sound bleak, but we all know for how long people had means of avoiding all buffer overflows, SQL injections, PHP include, format string, and many other classes of vulnerabilities, and didn't use them. Most likely many people will keep escaping HTML by hand even in 2020.

Returning from another side track, RLisp is Lisp with Ruby libraries, object system and so on, but it's also Ruby with macros. For some reasons languages with rich syntax like Ruby rarely get powerful macro systems, and even when they get some, like Dylan, Nemerle, and Lua, macros are very reluctantly used by most programmers. Only in Lisps macro use is widespread. I think the basic reason is that Lisp code can not only be generated easily, but albo transformed and analyzed. All Lisp syntax gets converted to a small core, and the core is all a metaprogrammer needs to deal with. It's certainly possible to imagine all Ruby syntax getting compiled to just literals, message sends, and a few control structures. Unfortunately real Ruby AST has 105 kinds of nodes in its abstract syntax tree, the set which is highly non-orthogonal, and it's difficult to transform the AST in any nontrivial way without accidentally breaking code semantics. If you feel like getting your hands dirty, SexpProcessor converts Ruby to something vaguely Lisp-like and back. I tried it once and it SexpProcessor felt much harder than Lisp macros. Just in case someone thinks I'm exaggerating, here's an example of Ruby magical behaviour. When a blocks is called with one argument, it expects multiple arguments (possibly optional, but |*args| doesn't cause magic), and the argument is an Array, it is magically expanded into a list of arguments.
irb> x="foo"; Proc.new{|a,*b| a}.call(x)
=> "foo"
irb> x=[1,2]; Proc.new{|a,*b| a}.call(x)
=> 1
I'd love to improve Ruby's elegance and hackability. If I had my way, I'd get rid of most of these irregularities in Ruby 2 (saving one or two keypresses for explicit * or really isn't worth the added complexity), together with protected, most of the private (global functions like Kernel#puts need to stay private for technical reasons, but many should be made public, especially commonly used metaprogramming methods like Module#define_method), class checks on UnboundMethod#bind (checking internal C representation is more than enough), and I'd get Object#become, Object#class= and other useful methods from evil.rb. I guess I'm not a particularly representative Ruby hacker, so maybe it's better for most that I'm not in charge of Ruby. ;-)

I really meant to write about the conference, but it turned into a post about RLisp. So on the conference ... people seemed to like RLisp. The obvious question I received after the talk was about web frameworks for RLisp. Back then there weren't any, the compiler was barely written a few days before and not even pubished, but I thought RLisp should be able to use Ruby on Rails without too much porting effort. And indeed just a few days later Brad Ediger created an RLisp plugin for Rails. Ruby has not only great libraries, but also great hackers.

And on RuPy 2007, the talk I liked most was "PyPy, the implementation of Python in Python". They're doing a lot of cool stuff with Python, I'd realy love to see similar things for Ruby. Some other talks I liked were "Python usage in Embedded Environments", "Domain-specific languages in Ruby", and "Hands-on! Wrapping FileMagic as a RubyGem". Between sessions, there were many cool hackers there, a lot of them involved in local Ruby User Groups (or suchlike). I think I'll follow their advice and check if there's something like that around.

Friday, April 20, 2007

Pattern matching for RLisp

claws by dotpolka from flickr (CC-NC-ND)One of the reasons I had for creating RLisp was a desire for a platform on which I could experiment with Lisp-style macros, and where they would do something useful. All other Lisps are either gross like Common Lisp or lack full macro system like Scheme. And in either case they don't have things that we take for granted nowadays in Ruby, Python or even Perl. Now that RLisp exists, and is even decently fast, I finally got to playing with macros. Some observations:

  • It's very difficult. Much more difficult than plain metaprogramming by code generation.
  • Macros are very intolerant - a typo or thinko in macro definition usually results in a completely uninformative error message. And thinkos are quite common.
  • I was never biten by macro hygiene issues. Obviously I (gensym) an identifier if I need one. It seems that to have hygiene problems the macro would need to use global variable, which was shadowed in local scope. This doesn't seem likely to happen.
Probably the most complicated macro I've written so far is pattern matching macro (match ...). It provides pattern matching syntax similar to OCaml's (SML's, Haskell's, and so on):
(defun arithmetics (expr)
 (match expr
   (x 'plus y)  (+ (arithmetics x) (arithmetics y))
   (x 'minus y) (- (arithmetics x) (arithmetics y))
   (x 'times y) (* (arithmetics x) (arithmetics y))
   (x 'div y)   (/ (arithmetics x) (arithmetics y))
   z z
 )
)
(arithmetics '5.0) ; => 5.0
(arithmetics '(1 plus 2)) ; => 3
(arithmetics '((3 times 4) plus 5)) ; => 17
The macro is built in stages. The first stage simply protects against evaluating the expression more than once.
(defmacro match (val . cases)
 (let tmp (gensym))
 `(do
   (let ,tmp ,val)
   (match-2 ,tmp ,@cases)
 )
)
(match-2 ...) does the same thing as (match ...), except that it knows its first argument is a temporary variable, so it doesn't have to worry about evaluating it multiple times. (match-2 ...) builds a tree (if (tmp matches pattern 1) (code 1) (if (tmp matches pattern 2) (code 2) ...)), possibly with a default value if all patterns fail.
(defmacro match-2 (tmp . cases)
 (if [cases empty?]
   `nil
   (if (== [cases size] 1)
      (hd cases)
      `(if (match-3 ,tmp ,(nth cases 0))
         ,(nth cases 1)
         (match-2 ,tmp ,@(ntl cases 2))
      )
   )
 )
)
(match-3 ...) generates code which matches a single value against a single pattern. There's a cool part - in RLisp (let foo bar) sets foo variable in the nearest enclosing scope (typically a function), so we don't have to do any extra work to get our patterns bind values to identifiers.
(defmacro match-3 (tmp pattern)
 (if [pattern is_a? Array]
   (if [pattern == ()] `[,tmp == ,pattern]
     (if [(hd pattern) == 'quote]
       `[,tmp == ',(nth pattern 1)]
       `(bool-and
          [,tmp is_a? Array]
          [[,tmp size] == ,[pattern size]]
          ,@[[Range new 0 [[pattern size] - 1]] map & (fn (i)
            (let tmpi (gensym))
            `(do
               (let ,tmpi [,tmp get ,i])
               (match-3 ,tmpi ,(nth pattern i))
            )
          )]
       )
     )
   )
   (if [pattern is_a? Symbol]
     `(do (let ,pattern ,tmp) true)
     `[,tmp == ,pattern]
   )
 )
)
(match-3 ...) isn't very pretty. It handles the following patterns:
  • Symbol - bind value to identifier
  • Array (quote symbol) - check if value equals symbol
  • Empty array - check if value is an empty array too
  • Other array - check if value is an array or the right size. If it is, check each of its elements against each element of pattern array.
  • Anything else - check if value equals pattern.
It would be nice to handle variable-sized lists with patterns like (foo bar . rest) . It shouldn't be that hard to implement it. (bool-and ...) is simply (and ...) except that it returns true or false, instead of the last value or nil. (and ...) would work here too, but I wanted simpler version for unit testing (match ...).
(defmacro bool-and args
 (if (empty? args)
   true
   (if [[args size] == 1]
     (hd args)
     `(if ,(hd args)
       (bool-and ,@(tl args))
       false
     )
   )
 )
)
I'm still undecided when to send messages like [args empty?] and when to call functions like (empty? args) and on other such details.