Jan'uary

今年的比赛

Fri, 03 Jul 2009 20:07:22 -0700

今年在上海举行的花式比赛已经变成了世界锦标赛，多么开心的一件事情。可惜世锦赛的选拔比赛放在酒泉进行，又是多么的悲剧。于是大部分浪人选手也只能参加一下降级为国内比赛的上海公开赛了。

也许这是最后一个夏天了吧...

不怕狼一样的对手，就怕猪一般的盟友

Wed, 17 Jun 2009 04:06:23 -0700

兄弟我这两天真的很郁闷，连续两个晚上，每一把星际群殴都遇人不淑。其实我要求不高，只要你能自保就行了，至少不要被矿后光炮这种多少年前的招式搞死。。

老天保佑今天不会继续衰下去。。你已经下雨弄的我没平花玩了，星际就帮帮我吧，请你吃牛肉。...

告别孩子气

Wed, 13 May 2009 00:05:33 -0700

“你们要做将来的领袖，不仅求得一点专门的知识就足够，必须具有清醒而富有理智的头脑，明辨是非而不徇利害的气概，沉思远虑，不肯盲从的习惯，而同时还要有健全的体格，肯吃苦耐劳，牺牲自己努力为公的精神。这几点是做领袖所不可缺乏的条件。” “诸位，现在我们若要拯救我们的中华民族，亦惟有靠我们自己的力量，培养我们的力量来拯救我们的祖国。这才是诸位到浙江大学来的共同使命。”

国立浙江大学校长竺可桢 1939年2月4日...

想去天堂吗？欢迎来杭州

Sun, 10 May 2009 20:05:02 -0700

70yard.com...

吗隔壁

Sat, 09 May 2009 09:05:21 -0700

http://club.china.com/data/thread/3212956/281/48/90/7_1.html
http://www.19lou.com/forum-5-thread-17461954-1-1.html...

五一劳动节快乐

Thu, 30 Apr 2009 19:05:59 -0700

直到今天我才明白，为什么那些伟大的先人要把五月一日设定为国际劳动节，因为在这一天劳动的感觉实在是太好了。。。

万恶的资本主义。...

China vs US Economy

Thu, 23 Apr 2009 21:04:25 -0700

...

两份武学秘籍

Thu, 23 Apr 2009 20:04:04 -0700

...

贾樟柯

Mon, 13 Apr 2009 22:04:38 -0700

"后来我通过采访发现，那一代父母因为在内心里他们有被牺牲的感觉，所以他们索性更加牺牲，一辈子攒的钱，孩子结婚买房，给出去。或者孩子在工厂上班，同事们都不错，都有车，那就把自己所有的积蓄都拿出来。亏了自己没关系，绝对要保护孩子，绝对要让孩子没有任何阴影，因为他们了解到社会的差距，他们心里有一个落差，所以他们用全部的积蓄让孩子没有落差。"

"从日常来说，我觉得没有人没有理想，但大多数人在理想方面挫败是一个常态，实现理想生活的是一个非常态。成千上万的人没有选择。这个主题不是我故意要拍的，是生活的本质和真相是这样的。如果你是一个悲观主义者，你知道人们缺少爱，你才会有爱给别人。这就是世界需要悲观的原因，否则不是傻开心嘛。"

"我觉得我是。它不妨碍我在生活中也是快乐的，但当我用一个媒介表达我对世界的看法时，城市的话，我觉得本质就是不快乐的。很简单，生老病死不愉快，年华老去也不愉快。生命的过程就有很多悲哀在里面，所有人类才有充沛的情感啊。"

很喜欢贾樟柯的这些话，我觉得很深刻。我常常觉得悲哀是世界的本质，悲剧是人类的鸦片，但是我想不出为什么自己会这样想，今天忽然有点儿感觉了。原来乐观的生活并不代表你是一个乐观主义者。...

穿越城区的老男人

Mon, 13 Apr 2009 05:04:47 -0700

最近的生活发生了挺大的变化。

在我对Apple已经非常不感冒的时候，老板非要给我发一台macbook用来工作。我很有良心的报告说，其实我还是更喜欢PC加双显示器，价格只要macbook的一半，老板很潇洒的回了一句，钱不是问题。唉，啥时候我也能这么潇洒的说这么一句呢。

论实用，macbook确实比不上我的x61。轻便强劲，键盘有手感，linux全面的驱动支持，指点杆完全是神来之笔，配合xmonad之类的wm绝对是天下无敌的开发机器。macbook则完全是一个噩梦。。。08年下半年开始的macbook unibody配的全是broadcom的无线网卡，给他老人家装驱动真是要命，网上文档又特别少，可能花一堆钱买mac偏要装个linux用的人的确太少。。。千辛万苦终于配合着arch/debian/gentoo/ubuntu的文档才搞定。macbook的键盘和触摸板被识别为一个设备，驱动也是超级难搞。最后好不容易能用了，触摸板单击(指tap)和双击(double tap)功能时灵时不灵，palm detection也做的不好，写代码的时候经常一不小心手掌靠上了触摸板，鼠标就飞到你找不到的地方去了，multi touch倒是支持的不错。声卡貌似号称是六声道的，但是用alsa驱动只有前面右边喇叭能出身，其它几个只能发挥配重稳定机身的功能，据大伙儿反映这是驱动的问题，目前没办法解决。显示屏亮度无法控制，每次modprobe mbp_nvidia_bl都出错，google了半天发现ubuntu论坛上有群众也碰倒了这个问题，据那一小撮反映这也是驱动问题，目前无法解决，怒。macbook用的引导系统太先进，装OSX+linux费了老大的劲。OSX花里胡哨的界面越用越烦，据本人客观评价，目前linux上的桌面环境加上compiz一点儿也不比OSX难用。所以我只能恶毒的揣测苹果，把个系统弄的这么不开放就是要把用户绑定的自己的专有平台上面然后杀猪－外接显示器接口弄得独一无二，一个转接线标价499，最后370块买下，成本我估摸着2块钱差不多。

黑了半天，说说macbook的优点。屏幕很亮，看着赏心悦目；运行时声音很小很小很小，苹果毕竟还是有水平，忽悠也得有资本；除此之外。。好像没有了。

=======================

公司的办公地点在城西的最东边，我住在城东的最西边，于是公司体恤老男人发了台电动车让我上班轻松点儿，能留下更多精力被剥削。电动车还真的蛮好玩的，最高能加到三十公里每小时，就是瞬间加速太弱了，不知道是故意弄成这样还是电驱动的原因，每当红灯转绿，我要牛b轰轰的一加油门蹭的一下窜出去的时候，可爱的小车车总是慢慢悠悠的开始挪动，刹那间所有的雄心壮志灰飞烟灭。。以后一定要买辆摩托车玩。

显摆到此结束，插播条新闻：牛人勇闯美利坚，一只红杏出墙来...

Stuck in Code

Fri, 10 Apr 2009 08:04:10 -0700

"I think it is a very *Indian* (or perhaps Asian) thing to expect good developers to "move up" to be managers or directors or Vice Presidents. We are a very hierarchical society and people are very often judged on where we are seen to be on some arbitrary hierarchy. People who work with their hands (or their keyboards) are often considered "inferior"."

http://pindancing.blogspot.com/2009/04/stuck-in-code.html
...

美帝貌似有点儿乱套

Sun, 05 Apr 2009 23:04:23 -0700

A look at victims of the Binghamton, NY, shootings

UC Berkeley Senior Fatally Shot in Oakland

Two dead in Shelbyville shooting

印象中还有一起，找不到链接了，就是几天之内的事情。失业率真是一个可怕的东西，以前学政治经济的时候感觉就是一个数字而已，现在终于明白为什么当权者对失业率升高那么恐慌。

杭州的夜晚突然多了很多路边摊。...

[ANN] Rubytest.vim 0.9.6 Released

Jan — Sun, 14 Jun 2009 19:32:00 -0700

Rubytest.vim 0.9.6 is just released. This version contains some small fix:

* support rspec examples looks like
example "this is an example" do
* correctly handle single/double quote escape for rspec examples and vanilla testcases

Check it out here: http://www.vim.org/scripts/script.php?script_id=2612

* Rubytest.vim is a vim plugin which helps you run ruby tests (including vanilla testcases, rspec examples, shoulda examples ..) quickly.

Infinity in Ruby

Jan — Tue, 02 Jun 2009 12:02:00 -0700

I learned this from a post today:

irb(main):001:0> Infinity = 1/0.0
=> Infinity
irb(main):002:0> (0..Infinity).include?(100000000000000)
=> true
irb(main):003:0> (0..Infinity).include?(-1)
=> false
irb(main):004:0> (-Infinity..0).include?(-1)
=> true
irb(main):005:0> (-Infinity..0).include?(-100000000000000000000)
=> true
irb(main):006:0> (-Infinity..0).include?(1)
=> false
irb(main):007:0> everything = -Infinity..Infinity
=> -Infinity..Infinity
irb(main):008:0> everything.include? 0
=> true

But ruby is not like haskell, which eval lazily - so don't try everything.to_a[0..100] :)

[ANN] Rubytest.vim 0.9.5 Released

Jan — Tue, 12 May 2009 13:49:00 -0700

Rubytest.vim is a vim (http://www.vim.org) plugin, which helps you to run ruby test (including vanilla test, rspec, shoulda etc.) in vim.

Changelog
---------

* Support quickfix: you can view test errors in quickfix window now
* Small fixes.

Get it here: http://www.vim.org/scripts/script.php?script_id=2612

The problem with young entrepreneurs

Jan — Sun, 03 May 2009 20:23:00 -0700

"Most of the time, this leads to the well-known case of “solutions looking for problems” - beautiful technology that can’t become a profitable business.

Best ideas are a side-effect from solving significant problems that the entrepreneurs themselves experience, observe and intimately understand. As young Web entrepreneurs, we aren’t sufficiently aware of important real-world problems, since our life mostly consists of hacking, coffee and occasional entertainment."

via

Something about latest vimperator

Jan — Thu, 30 Apr 2009 11:53:00 -0700

Latest vimperator release doesn't work well with Firefox 3.0.x and TabMixPlus: slow autocompletion, broken tab functions.

M.Terada provides two patch to make tabs work decently again, I don't know whehter it's included in vimperator's repository now, but you can download them here and here

For faster auto completion, set complete and preload options like this in your .vimperatorrc may help:


set complete=sbh
set nopreload

Some guys suggest setting wildmode to empty, but I don't like that idea.

Below is mine full .vimperatorrc:


set pageinfo=gfm
set showtabline=2
set defsearch=google
set complete=sbh
set nopreload
set showstatuslinks=2
set smartcase
set newtab=all
"set wildmode=

map l gt
map h gT
map b :bmarks!<Space>
map ;; d
map s :js open("mailto:?SUBJECT='" + escape(document.title) + "'" + "&BODY=" + escape(document.getElementById("urlbar").value))<CR>

map <C-p> :pa<CR>
map <C-k> tg<Space>
map <C-u> <C-v><C-u>
map <C-y> <C-v><C-y>
map <C-R> a<Space>-tags=toread<CR>
map <C-r> :bmarks -tags=toread<CR>
map <C-d> :delbm<CR>
"map <C-l> :sidebar LiveHTTPHeaders<CR>

map <silent> <F9> :js inspectDOMDocument(document)<CR>
map <silent> <F1> :js toggle_element('toolbar-menubar');toggle_element('nav-bar')<CR>
map <silent> <F2> :emenu Edit.Preferences<CR>
map <silent> <F3> :emenu Tools.Live HTTP headers<CR>
map <silent> <F10> :exe ":o dict2 "+content.getSelection()<CR>

autocmd PageLoad .* :js modes.passAllKeys = /(mail\.google\.com)|(google\.com\/reader)/.test(buffer.URL)

set nextpattern+=^\s*下一页\s*$
set previouspattern+=^\s*上一页\s*$

javascript <<EOF
(function(){
 var feedPanel = document.createElement("statusbarpanel");
 feedPanel.setAttribute("id", "feed-panel-clone");
 feedPanel.appendChild(document.getElementById("feed-button"));
 feedPanel.firstChild.setAttribute("style", "padding: 0; max-height: 16px;");
 document.getElementById("status-bar")
 .insertBefore(feedPanel, document.getElementById("security-button"));
})();
EOF

javascript << EOF
 toggle_element = function (name) {
 document.getElementById(name).collapsed ^= 1;
 }
EOF

echo ".vimperatorrc sourced"

" vim: ft=vimperator sw=2 sts=2

Announcement of rubytest.vim: a vim plugin aims to help you run ruby test conveniently

Jan — Sun, 19 Apr 2009 10:47:00 -0700

Rubytest.vim is a vim (http://www.vim.org) plugin, which helps you to run ruby test (including vanilla test, rspec, shoulda etc.) in vim.

http://www.vim.org/scripts/script.php?script_id=2612

Installation
------------

Copy all files to your ~/.vim directory.

Usage
-----

After installation, press t will run the test under your cursor if you are editing a ruby test file.

example:

$ cd
$ vim test/unit/user_test.rb
(move cursor into a test case, press t)

( is mapping to '\' by default in vim)

You can customize the command which will be used to run the test case by settting these options in your vimrc file:

let g:rubytest_cmd_test = "ruby %p"
let g:rubytest_cmd_testcase = "ruby %p -n '/%c/'"
let g:rubytest_cmd_spec = "spec -f specdoc %p"
let g:rubytest_cmd_example = "spec -f specdoc %p -e '%c'"

(%p will be replaced by the path of test file, %c will be replaced by the name of test case under cursor)

Default Key Bindings
--------------------

t: run test case under cursor
T: run all tests in file

You can change default key bindings:

map \ RubyTestRun " change from t to \
map ] RubyFileRun " change from T to ]

http://www.vim.org/scripts/script.php?script_id=2612

Bidirectional many-to-many relationship in ActiveRecord

Jan — Thu, 26 Mar 2009 17:31:00 -0700

Bidirectional many-to-many relationship is a common pattern in design, like friendships between users, memberships between users and groups, etc. In this article I'll illustrate how to implement such a relationship in ActiveRecord/Rails.

Let's start with a little context. Suppose we want to add the populer 'friends' feature for our users, we already have User model, what we need is a join table 'friendships' to connect users.


class User < ActiveRecord::Base
end

class CreateFriendships < ActiveRecord::Migration
 def self.up
 create_table :friendships, :id => false do |t|
 t.integer :left_user_id
 t.integer :right_user_id
 end
 end

 def self.down
 drop_table :friendships
 end
end

The behavior we want, can be written like this:


test "should has many friends" do
 users(:quentin).friends << users(:aaron)
 assert_equal 1, users(:quentin).friends.reload.count
end

Of course the test is failed when we run it now. After reading our requirements we decide to use has_and_belongs_to_many (habtm) in ActiveRecord because it is enough for now, so we modify our User model like this:


class User < ActiveRecord::Base
 has_and_belongs_to_many :friends, :join_table => 'friendships',
 :foreign_key => 'left_user_id', :association_foreign_key => 'right_user_id',
 :class_name => 'User'
end

Now run our test, passed, perfect! We can leave office and enjoy *fill whatever you like* now.

"Wait", your brilliant colleague says, and add one line to your unit test:


test "should has many friends" do
 users(:quentin).friends << users(:aaron)
 assert_equal 1, users(:quentin).friends.reload.count
 assert_equal 1, users(:aaron).friends.reload.count
end

He runs the test again and it failed. It's unfair if quentin treat aaron as his friend but aaron doesn't do the same to quentin, isn't it? To fix this problem we need to custom insert and delete sql for the habtm relationship:


class User < ActiveRecord::Base
 has_and_belongs_to_many :friends, :join_table => 'friendships',
 :foreign_key => 'left_user_id', :association_foreign_key => 'right_user_id',
 :class_name => 'User',
 :insert_sql => 'insert into friendships (`left_user_id`, `right_user_id`) values 
(#{id}, #{record.id}), (#{record.id}, #{id})',
 :delete_sql => 'delete from friendships where (left_user_id = #{id} and right_user_id 
= #{record.id}) or (left_user_id = #{record.id} and right_user_id = #{id})'
end

What we do here, is to add two friendship records (both direction) when we add a user to another's friends set. We do the same when delete a user from one's friends set. We rerun the test and it passes as we expected.

Note the ":id => false" argument when we create the join table 'friendships', without it you'll have troubles when loading friends objects. I think this is a long history bug of ActiveRecord, I don't know why it is not fixed. If you really want to keep the 'id' field and use habtm at the same time, a workaround is customize the finder_sql:


class User < ActiveRecord::Base
 has_and_belongs_to_many :friends, ...
 :finder_sql => 'select users.* from friendships left outer join users on 
friendships.right_user_id = users.id where friendships.left_user_id = #{id}'
end

The bidirectional habtm we build here, is in fact a self-referential bidirectional relationship, it relates models to the same type of models (users to users). What will happen if the relationship is NOT self referential?

In that case we should not use habtm, otherwise our (at least my) brain will be burned by the complicated sqls it brings. Don't waste time on those sqls, ActiveRecord provides another way to build many-to-many relationship: has_many :through

So one day the boss comes to you and asks, "Can we group our friends? I want to put Gates in group Evil and Male, and Linus in group Minix and Antarctic"

"Sure", you answered, how can you say No to your boss?

Now the many-to-many relationship is between groups and users, we need to modify User model, create a Group model and write a migration to modify friendships table. Since we'll use has_many :through for this requirement, we also need a model for the join table 'friendships':


class User < ActiveRecord::Base
 has_many :groups
end

class CreateGroups < ActiveRecord::Migration
 def self.up
 create_table :groups do |t|
 t.string :name
 t.integer :user_id
 end
 end

 def self.down
 drop_table :groups
 end
end

class Group < ActiveRecord::Base
 belongs_to :user
 has_many :friendships
 has_many :friends, :through => :friendships
end

class RemodelFriendships < ActiveRecord::Migration
 def self.up
 remove_column :friendships, :left_user_id
 rename_column :friendships, :right_user_id, :friend_id
 change_column :friendships, :group_id, :integer, :null => false
 end

 def self.down
 change_column :friendships, :group_id, :integer, :null => true
 rename_column :friendships, :friend_id, :right_user_id
 add_column :friendships, :left_user_id
 # execute "..."
 end
end

class Friendship < ActiveRecord::Base
 belongs_to :group
 belongs_to :friend, :class_name => 'User'
 validates_uniqueness_of :friend_id, :scope => :group_id
end

Pretty good, it works. But we have the same problem when we use habtm, the relationship is not bidirectional. How can we fix it?

ActiveRecord allow you to extend the association proxy when use has_many :through, the solution here is to override the proxy's default CRUD methods. Let's create a new file lib/bidirection.rb:


module Bidirection
 def <<(friend)
 Friendship.create :group_id => friend.groups.default.id, :friend_id => self.proxy_owner.user.id
 super(friend)
 end

 [:delete, :destroy].each {|m|
 define_method(m) {|friends|
 friends = [friends] unless friends.instance_of?(Array)
 friends.each {|friend|
 Friendship.first(:conditions => {:group_id => friend.groups.default.id, :friend_id => self.proxy_owner.user.id}).try m
 }
 super(friends)
 }
 }

end

Then enhance our has_many :through with it:


class Group < ActiveRecord::Base
 ...
 has_many :friends, :through => :friendships, :extend => Bidirection
end

That's it, you have bidirectional many-to-many relationship between groups and users now. For convinient you can create a default group when create user (use before_create hook), and delegate friends and friends= methods in User model to user's default group, in that way you get the self-referential bidirectional many-to-many relationship betweent users back, as we have when using habtm.

ActiveRecord and DataMapper

Jan — Thu, 19 Mar 2009 00:59:00 -0700

I jumped into a merb project about 1 month ago, it's really an interesting trip. Working in both frameworks make pros and cons crystal clear to see. Here I'll try to remember some of those I found on the different ORM they use, thus ActiveRecord vs DataMapper.

* Schema Definition

ActiveRecord keep all schema definitions in migration files, while DataMapper store most of them in model source code. I prefer DataMapper's way, so you won't need plugins like annotate_models any more. Do you use annotate_models in your rails project?

However, keep model schema in model source code brings more complexity, because sometimes you have tasks which are better written in a migration file instead of model source file. So DataMapper has seperate migrations too, and merb provides more migration rake tasks than rails.

* Many-to-Many Relationships Through Scoped Join Model

Sorry for my poor description, this ticket illustrates the problem well. I don't know why this bug won't be fixed in ActiveRecord - below code works well in DataMapper.


 has n, :bookmarks, :through => :subscriptions, :conditions => "subscriptions.notification = 'f'"

* scope

ActiveRecord introduced named_scope in since 2.x (can't remember), and add dynamic scope (scope_by_xxx like dynamic finder find_by_xxx) in the latest 2.3 release, so now you can chain up many dynamic scopes, named scope and find now. That's really cool, but why we need two seperate finders, find and scope?

In DataMapper, "find" and "scope" is unified. You can do this


 class Zoo
 # all the keys and property setup here
 def self.open
 all(:open => true)
 end
 def self.big
 all(:animal_count.gte => 1000)
 end
 end
 
 big_open_zoos = Zoo.big.open

As you can see, the finder #all is able to be chained up or used independently, smart. And I like tye syntax all(:open => true) than find_all_by_open(true): hash can be auto complete by editors while '_' can not, hash param doesn't require dynamic tricks while find_xxx need. Sometimes I feel rails takes too many cares to his baby programmers, sometimes I feel merb takes too little (not in this case, of course).

* Inheritance vs Include

ActiveRecord model is required to inherit from ActiveRecord::Base, while DataMapper model need to include DataMapper::Resource. Composition is better than inheritance, though module inclusion is in fact inheritance in Ruby.

* Finally

I didn't realize all the things I written down are votes for DataMapper until I write this sentence .. I want to say ActiveRecord is an excellent ORM framework too, at least it's more mature than DataMapper, I enjoy it at most of the time, it just doesn't work in some few case (I really hope the many-to-many relationship through scope join model problem can be fixed, it's a common pattern I've seen it serveral times). The good news is by Rails and Merb merge, rails will become super flexible and you'll be able to switch between ORMs in Rails 3 easily.

The problem is

Jan — Wed, 11 Mar 2009 00:13:00 -0700

"As is often the case when proving things about programming languages, the tricky part here is formulating a precise statement to be proved—the proof itself should be straightforward." - TAPL, pierce

In schools students are always given clearly defined, already formalized questions, I think that's why the students feel uncomfortable when they come to the real world. I should spend more time on the mathematical modeling class when I was in university :(

Use rails.vim and merb.vim together

Jan — Tue, 24 Feb 2009 15:56:00 -0800

I recently works on a merb project. As a vim user I found merb.vim for syntax highlighting, but it will conflict with rails.vim. For example, *before_filter* is a declaration in Rails controller, but in Merb it should *before*. After you installed merb.vim, it will set the file type of your controller file to ruby.merb_controller, so if you open a controller file in a rails project, the 'before_filter' will be highlighten as an error.

The solution is to find a way to have directory/project specific setting for vim. Luckily it already exists.

In you ~/.vimrc:

set exrc

Then move ~/.vim/ftdetect/merb.vim (this file is installed by merb.vim plugin) to $your_merb_project/.vimrc. Now the filetype setting for merb will only affects the merb project dir only.

Rules a Monad should follow

Jan — Sun, 15 Feb 2009 21:32:00 -0800

I. return x >>= f === f x

II. x >>= return === x

III. m >>= (\x -> f x >>= g) === (m >>= f) >>= g

Kernel#eval

Jan — Fri, 06 Feb 2009 17:13:00 -0800

There's an interesting post in ruby mailing list today. The discussion started by a question asked by Jonathan Wills:

a = 1
eval('a=2')
puts a

This will print out '2', as I want. However if I remove the first line,

eval('a=2')
puts a

r.rb:2:in ` ': undefined local variable or method `a' for
main:Object (NameError)

Then Mike Gold gives an excellent explaination:

The thing to remember is that local variables are always determined at parse time.

eval("a = 3", binding)
p local_variables #=> ["a"]
p a #=> undefined local variable or method `a'

We see that the local exists, but because the parser has not seen the "a = ..." syntax, we can't access it.

Locals are not handled in the same way. The local assignment syntax is subject to special examination by the parser. This does not happen for instance variables and globals. Again, it is the parser that determines locals. If all assignments were the same, this would print '3':

eval("a = 3", binding)
puts a

Pickaxe gives this example:

def a
print "Function 'a' called\n"
99
end

for i in 1..2
if i == 2
print "a=", a, "\n"
else
a = 1
print "a=", a, "\n"
end
end

produces:

a=1
Function 'a' called
a=99

But constants and instance variables are different. Which means

eval("@a=2")
@a # => 2

Another interested thing Mike metioned is, when you see this error:

undefined local variable or method `a' for main:Object (NameError)

It in fact means 'undefined method a':

... that error message comes from rb_method_missing(), i.e., it was determined to be a method call. Presumably it is worded that way for the user's benefit, in case there was a misspelling or some such. Locals are determined by the parser; method lookup is done when no such local exists.

Notes of Guy Steele's Lisp Processor Prototype

Jan — Tue, 03 Feb 2009 16:50:00 -0800

The prototype in paper is different from the well known 'Lisp Machine' which in fact has a hybrid (traditional linear vector memory model + linked list model) architecture (e.g. based on TTL logic, with large ALU) while the prototype is totally build on linked list model (with embedded instruction set and almostly no ALU). The history of this project is a very interesting story :) For youth like me, it's hard to imagine that one obstacle of building such a processor is ALU is too large at that time ..

And this paper make me think it's not fair to say modern GC (garbage collection) is an innovation from Lisp (you know some Lisp guys always like to say 'hey, XXX has already be seen in Lisp 30 years ago). As you can read from the paper, GC is an inevitable workaround to fill the gap between functional programming (which will produce lots of immutable intermedia) and von Neumann machine (finite memory), it's not invented to free programmers from C++'s malloc/free hell like Java (which is an imperative language). Like Watt found water can be heated into steam to drive machine is of course an innovation, but use water to generate electricity is a totally diffierent thing.

Most of the contents below are copied from GLS & GJS's paper "Design of LISP-Based Processors", March 1979.

== Notes of the paper ==

An idea which has increasingly gained attention is that computer architectures should reflect specific language structures to be supported.

Stored-program computer is such one that the program and the data reside in the same memory, the program is itself data which can be manipulated as any other data by the processor. Lisp is unusual among high-level languages in that it explicitly supports the stored-program idea, for this reason Lisp is often referred to as a 'high-level machine language'.

One of the central ideas of the Lisp language is that storage management should be completely invisible to the programmer. Lisp is an object-oriented language, rather than a value-oriented language. The Lisp programmer does not think of variables as the objects of interest, bins in which values can be held. Instead, each data item is itself an object, which can be examined and modified, and which has an identity independent of the variable used to name it.

A complete Lisp system is conveniently divided into two parts: (1) a storage system, which provides an operator for the creation of new data objects and also other operators (such as pointer traversal) on those objects; and (2) a program interpreter (EVAL), which executes programs expressed as data structures within the storage system. (Note that this memory/processor division characterizes the usual von Neumann architecture also. The differences occur in the nature of the processor and the memory system.)

Commercially available memories are available only in finite sizes. Lisp (or functional language)'s free and wasteful throw-away use of data objects would be a disaster with finite memory. In order to make such memories useable to Lisp (or functional language) we must interpose between EVAL and the storage system a storage manager which makes a finite vector memory appear to the evaluation mechanism to be an infinite linked-record memory. The memory is "apparently infinite" in the sense that an indefinitely large number of new records can be "created" using the CONS operator. The storage manager recycles discarded records in order to create new ones in a manner completely invisible to the evaluator.

The storage manager therefore consists of routines which implement the operations CAR, CDR, CONS, etc. in terms of the vector memory, plus a garbage collector which deals with the finiteness of the memory by locating records which have been discarded and making them available to the CONS routine for recycling.

In Guy Steele's Lisp processor prototype, there is no garbage collector for some reason. And there's even no ALU! (In fact it have simplest arithmetic and logical capabilities, which can only add 1 and test for 0) This is interesting because Lisp itself is so simple that the interpreter needs no arithmetic to run interesting programs (such as computing symbolic derivatives and integrals, or pattern matching).

This is not to say that real Lisp programs do not need arithmetic, just that the Lisp interpreter itself does not require binary arithmetic of the usual sort (but it does require CONS, CAR and CDR, which in a formal sense indeed form a kind of "number system", where CONS corresponds to "add 1" and both CAR and CDR to "substract 1". In this view, the purpose of the storage manager is to interface between two kinds of arithmetic, namely "Lisp arithmetic" and Peano arithmetic).

Understanding Git Concepts

Jan — Tue, 27 Jan 2009 23:11:00 -0800

Git in fact is a file system with history.

All data is saved in git objects. All git objects has a 40bits id which generated by SHA-1 hashing the object's content. There're 4 types of objects:

blob object: File contents is saved in blob object. No filenames/permissions etc, only contents is saved here.
tree object: Directory structure is saved here. Tree object's content is just a list of its children, either blob object or tree object. A list item will contain either a SHA-1 hash point to a blob object with filename/permissions/etc. or a hash point to a tree object. Here we have got a data structure(tree) which can represent a file system.
commit object: Now we need history. A commit object simple contains a pointer to tree, one or many pointer to parents(also commits) and some booking data like commiter. Commit objects in fact forms a tree graph on a higher layer of blob/tree.
tag object: Tag object is just for referencing an object conviniently. A tag object can have a pointer point to any other git object and a tag, then you can use the tag to reference any object(like an important commit) in your git repo.

A git object is immutable. Another concept in git system is Reference, for referencing mutable things like branch and remote.

Branch is just a file in .git/refs/heads/ dir contains the SHA-1 hash of the most recent commit to that branch. When you create a branch in git, git just create a file contains a 40 bytes hash in .git/refs/heads/, and update .git/HEAD to point to it. With your development moves on, git will find current branch in HEAD and update the branch file in refs/heads correctly.
Remote is a pointer to branch(so it's also a branch) in other people's copies of the same repo. If you get the code by clone instead of 'git init', git will add a default 'origin/master' remote branch for you automatically. 'origin' point to the remote copy location, and 'master' means which branch on remote you cloned from.

When you ask for checking out, git will lookup the argument you provided in .git/refs or .git/HEAD, find the corresponding object/branch/tag/whatever, read the SHA-1 hash which points to a tree from its content, then traverse the tree.

A fetch will merge all updates on a remote branch to your local. By default it will merge in changes on origin/master, but you can fetch updates on other place like origin/cool. After a series of fetch/merge your history graph will looks like a mess, rebase will help. Rebase will leave orphan objects in your repo(you can use 'git gc' to clean it) and should not be used on a repo which can be fetched by others.

Evolutionary algorithm example in Ruby

Jan — Sat, 24 Jan 2009 16:07:00 -0800


#!/usr/bin/ruby -w

# This program is based on this evolutionar computation introduction:
# http://blog.uncommons.org/2009/01/20/practical-evolutionary-computation-an-introduction/
#
# usage: ruby evolution.rb [generations] [goal]
# example: ruby evolution.rb
# ruby evolution.rb 100
# ruby evolution.rb 100 "I make the universe"

# We can set a goal(string) for evolution, and the Evolution object
# will evolute towards the goal you set.
class Evolution
 attr_accessor :set

 # The goal(string) can contain only upcase characters and space
 # CHARSET in fact is gene pool
 CHARSET = ('A'..'Z').to_a + [' ']
 CHARSET_LENGTH = CHARSET.length

 # goal: evolution goal is a string, like 'hello world'
 # population: the population of the society. default to 100, means
 # there're 100 parents in the initial environment. And
 # the environment can only support 100 livings.
 # mutation_rate: the possibility of gene mutation. default to 0.01,
 # means a gene 'A' in one generation has 1/100 possibility
 # to mutate to random gene in CHARSET
 def initialize(goal,population=100,mutation_rate=0.01)
 @goal = goal
 @population = population
 @mutation_rate = mutation_rate

 # @set is the environment all livings live in
 @set = []
 @strlen = goal.length

 # fill the environment with livings
 population.times {|i|
 str = ""
 @strlen.times {|j| str << CHARSET[rand(CHARSET_LENGTH)] }
 @set << str
 }
 end

 # evolution function
 # reproduce: how many generations should the evolution have
 def run(reproduce=1000)
 reproduce.times {|i| generation }
 sort_and_cut(@set).each {|s| puts "#{s} : #{score s}" }
 end

 private

 # one generation
 def generation
 score_set
 pick
 crossover
 mutation
 end

 # give mutation chance to every living in our environment
 def mutation
 k = 1/@mutation_rate
 for str in @set
 str.length.times {|i|
 str[i] = CHARSET[rand(CHARSET_LENGTH)] if rand(k) == 0
 }
 end
 end

 # choose two parent
 # produce offspring
 def crossover
 set = @set.uniq

 offsprings = []
 if set.length == 1
 offsprings = @set
 else
 (set.length-1).times {|i|
 (i+1).upto(set.length-1) {|j|
 pivot = rand(@strlen) + 1
 par1_a, par1_b = set[i][0,pivot], set[i][pivot,@strlen]
 par2_a, par2_b = set[j][0,pivot], set[j][pivot,@strlen]
 offsprings << "#{par1_a}#{par2_b}"
 offsprings << "#{par2_a}#{par1_b}"
 }
 }
 end

 @set = sort_and_cut(offsprings)
 end

 # pick the good candicates (high score)
 # score 2 candicate will have high possiblity to be choosen than score
 # 1 candicate
 def pick
 pool = []
 @score_map.each {|str,score|
 score.times {|i|
 pool << str
 }
 }
 pool.sort! {|a,b| rand(3) - 1} # shuffle
 pool_len = pool.length
 
 @set = []
 @population.times {|i|
 @set << pool[rand(pool_len)]
 }
 end

 # compute score for every candicates
 def score_set
 @score_map = {}
 for str in @set
 @score_map[str] = score(str)
 end
 @score_map
 end

 # score will tell us the simliarity between the str and goal
 # score = the same character on the correct position with goal
 def score(str)
 score = 0
 @strlen.times {|i|
 score += 1 if str[i] == @goal[i]
 }
 score
 end

 # sort livings by score and only the livings with highest score
 # will left. They're the selection of nature.
 def sort_and_cut(set)
 set.sort_by {|s| -(score s)}[0,@population]
 end

end

if __FILE__ == $0
 times = ARGV[0] ? ARGV[0].to_i : 20
 goal = ARGV[1] ? ARGV[1].upcase : 'HELLO WORLD'
 e = Evolution.new(goal)
 e.run times
end

Haskell Functor Typeclass

Jan — Tue, 13 Jan 2009 19:01:00 -0800

A correct functor instance should follow two rules:

fmap id == id
fmap (f . g) == fmap f . fmap g

In natural words, functor should keep data's structure, only change it's value. This rule can't be guranteed by compiler, so we have to remember it by ourselves when implement a functor instance.

Functional interpreter and program modularity

Jan — Sat, 03 Jan 2009 21:19:00 -0800

The purpose of programming tech evolution is modularity. To get modularity, people need abstractions. What's the differences between abstraction and type-saving sugars? A good package of common patterns (abstraction) encapsulates a higher level concept which has meaning *independent* of its implementation.

A package is most useful if its behavior is independent of the context(environment/global resource/etc.) of its use. Such a package is called referentially transparent. In other words, the output(behavior) of a referentially transparent package(function) will always be the same with the same input, because the explictly provided input data is the only source it depends. (What does 'same' mean here is an interesting problem, we'll see later)

To make a modular system, it is often necessary to think of a computational process as having state. In such cases, if the state can be naturally divided into independent parts, an important decomposition may be the division of the program into pieces which separately deal with the part of the state.

Referential transparency will permit programs to be divided into parts so that each part can be separately specified without a description of its implementation. The desirable result is that pieces can be separately written and debugged. At first people made no free variable recusive interpreter[1] with seperated variable bindings (Environment) and procedure bindings. It's expressive power is very litmited.

Seperate Env and Procedure symbol tables will make procedure 2nd-class concept (thus you can't define a 'map' function in the interpreter), but merge these two table unintentionally bring in two property: free variables (in fact, before merge, procedure symbols are free variables, but they're not real 'variables' at that time) and dynamic scope variables.

To avoid function name conflicts, it would be nice to have a notation for functions as objects, or rather a way to write an sexp in code that would evaluate to a procedure. Lisp adapted such a notation from lambda calculus of Alonzo Church.

But lambda plus dynamic scoping will lead to the famous 'FUNARG' problem, so we need lexical scoping. What we want is when computing a lambda, use the environment in which it's evaluated instead of the environment in which it's executed. The solution is simply save the environment in the procedure object when evaluate a lambda (or function, they're the same thing, function is just a lambda with a name in symbol table). Within this change, we say that the procedure is closed in the current environment, and the procedure object is therefore called a *closure* of the procedure, or a *closed procedure*.

The problem of lexical scope is in the REPL: the new definition can only refer to previously defined names! We lose the ablity to define recursive procedure. This conflict, between REPL and lexical scope, is unavoidable, because such a incremental interactive top level loop for reading definitions inherently constitutes a violation of referential transparency, which we successfully got in our interpreter. A piece of code can be read in which refers to an as yet undefined identifier (the name of a procedure), and then later a definition for that identifier read in (thereby altering the meaning of the reference). If we insist on maintaining absolute referential transparency, we are forced to eliminate the incremental top level interaction, to give up interactive debugging (we can't redefine erroneous procedures easily), to give up incremental compilation of separate modules.

If we throw lexical scoping away and turn back to dynamic scoping we would lose a great deal of referential transparency and abstractive power. The solution can be a mixture: procedures must not be allowed to refer to variables internal to other procedures, but only to top-level variables existing at the time they are called. Therefore only the future top-level environment is to be included in the procedure object when it is eventually constructed. In this way free variable references will be dynamic only with respect to the top-level environment.

At this stage, we made our functions really referencial transparency, with no side effect. No side effect means no state, no state means you have to pass states up and down (as functions input and output) through the whole system. So no side effects conflicts with modular discipline. We are forced to introduce side effects as a technique for constructing modular systems. But side effects violate referential transparency, now we have two techniques for achieving modularity have come into direct conflict.

The concept of side effect is induced by particular choices of boundaries between parts of a larger system. If a system boundary encloses all processes of interest (the system is closed), we need no concept of side effect to describe that system as a whole in vacuo. If we wish to make an abstraction by dividing the system into modules more than one of which has independent state, then we have by this action created the concept of side effect.

The concept of side effect is inseparable from the notion of equality/identity/sameness. The only way one can observationally determine that a side effect has occurred is when the same object behaves in two different ways at different times. Conversely, the only way one can determine that two objects are the same is to perform a side effect on one and look for an appropriate change in the behavior of the other.

if CONS return new object on every call, then it has side effect! Because with the same input, it will generate different output (a totally new object).

If side effect are to be usable at all, the references to things denoted by variables must not make copies of those things. If the user is to be able to write procedures which produce lasting side effects on their arguments, then there must be a variable binding mechanism which does not make copies.

The ideal equality predicate should follow these two rules:

1). Two objects which are observed to behave differently must not be equal.
2). Conversely, we would like two objects which are adjudged unequal to exhibit differing behaviors under suitable circumstances.

Any useful equality predicate must satisfy 1), but it's hard to satisfy 2). (Another interesting view is, equality predicate should never be false-positive, but may be false-negative)

Based on above two rules: in the absence of RPLACA ("pure lisp"), EQUAL is preffered to EQ (like (==) in haskell); in the presence of side effects such as RPLACA, EQ is preferred to EQUAL.

Finally we found set-use-reset pattern is very helpful for modularity, and dynamic scope captures this pattern well. So we want to have both dynamic and lexical scope variables in our interpreter. We need to maintain separate environments for lexical and dynamic variables in interpreter to avoid certain problems. This will require a special syntax for distinguishing references to and bindings of the two kinds of variables.

Dynamic scoping provides an important abstraction for dealing with side effects in a controlled way. A low-level procedure may have state variables which are not of interest to intermedia routines, but which must be controlled at a high level. Dynamic scoping allows any procedure to get access to parts of the state when necessary, but permits most procedures to ignore the existence of the state variables. The existence of many dynamic variables permits the decomposition of the state in such a way that only the part of interest need be deal with.

[1] LISP was not originally derived from Church's lambda calculus. In early LISP ppl use "McCarthy conditional" to define recursion:

factorial[x] = [x=0 -> 1; T -> x*factorial[x-1]]

while in resursive function theory one would define it like this:

factorial(0) = 1
factorial(successor(x)) = successor(x) * factorial(x)

haskell adopt the later notion, while keep the first one too (case expression)

Bloom filter

Jan — Sat, 27 Dec 2008 20:04:00 -0800

An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with an even distribution.

To add an element, feed it to each of the k hash functions to get k array positions. Set the bits at all these positions to 1.

To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions are 0, the element is not in the set – if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have been set to 1 during the insertion of other elements.

False positive is possible, false negative is impossible for bloom filter.

False Positive can be understanded as a "failed positive assertion", e.g. If I report to teacher you cheated in the last exam but in fact you didn't. In bloom filter case, it means the filter may report you the keyword 'd' exists in the set {'a','b','c'}, but the filter will never tell you 'a' or 'b' or 'c' not exists in the same set.

igvita provides a ruby implementation.

Rails: ActionController#render become more smarter

Jan — Thu, 25 Dec 2008 10:14:00 -0800

Pratik Naik pushed a series of commits to make ActionController#render more easy to use.

1. It will recognize actions.

# Instead of render(:action => 'other_action')
render('other_action')

2. It will recognize templates.

# Instead of render(:template => 'controller/action')
render('controller/action')

3. It will recognize a file path.

# Instead of render(:file => '/Users/lifo/home.html.erb')
render('/Users/lifo/home.html.erb')

4. It will recognize a symbol. So in your create action you can just write 'render :new' when model save failed!

TDD and BDD

Jan — Mon, 22 Dec 2008 22:05:00 -0800

Update1: I found I misunderstanded TDD, now I confused with BDD again :(see comments below)

Update2: Someone asked me that why we should write tests first? If we write tests immediately after implement a function, what we lose compare to write test first? My answer is simple: how can you know you test will fail before you write the implementation if you don't write test at first? And how can you make sure it's your code made the test pass, not because the test will pass even without your code?

What's the differences between TDD and BDD? That's always a good candidate question for you recruiting :) It's hard to get the answer from their boring description, at least hard to me.

Today I found a good example to demonstrate the diff between them - Rails validations. For those who don't use rails, validations is used to guard data correctness, for example, if I wrote this in my rails app:

class Book < style="font-style: italic;"> validates_presence_of :title
end

it will always check the Book's title is not blank when save the object. Now the problem is, should you write tests/assertions for this statement?

TDD will say no. Rails is released with lots of tests, the validation's correctness has already been guaranteed by it, in other words your own tests are just duplicate works. But from BDDer's POV, you should write tests for it - to describe the Book's *behavior*, not to cover the validation's implementation code.

So, BDD want to make sure we implemented the right behavior, or function/feature/whatever. If you refactor your code one month later, those seems redundant tests will guarantee your app's behavior is consistent after your refactor.

This gap between TDD/BDD will lead a inference: 100% code coverage suggests you did very well in a TDD team, but it means nothing if you're in a BDD team. As the example shows, even you didn't write test for the validation, your test will cover it(you tests definitely will save a book object somewhere, thus emit the validation), but you won't know whether your books will still require a title after refactor.

Haskell Numeric Types

Jan — Sun, 21 Dec 2008 11:27:00 -0800

From http://book.realworldhaskell.org/read/using-typeclasses.html

Table 6.1. Selected Numeric Types

Type	Description
`Double`	Double-precision floating point. A common choice for floating-point data.
`Float`	Single-precision floating point. Often used when interfacing with C.
`Int`	Fixed-precision signed integer; minimum range [-2^29..2^29-1]. Commonly used.
`Int8`	8-bit signed integer
`Int16`	16-bit signed integer
`Int32`	32-bit signed integer
`Int64`	64-bit signed integer
`Integer`	Arbitrary-precision signed integer; range limited only by machine resources. Commonly used.
`Rational`	Arbitrary-precision rational numbers. Stored as a ratio of two `Integer`s.
`Word`	Fixed-precision unsigned integer; storage size same as `Int`
`Word8`	8-bit unsigned integer
`Word16`	16-bit unsigned integer
`Word32`	32-bit unsigned integer
`Word64`	64-bit unsigned integer

Table 6.2. Selected Numeric Functions and Constants

Item	Type	Module	Description
`(+)`	`Num a => a -> a -> a`	`Prelude`	Addition
`(-)`	`Num a => a -> a -> a`	`Prelude`	Subtraction
`(*)`	`Num a => a -> a -> a`	`Prelude`	Multiplication
`(/)`	`Fractional a => a -> a -> a`	`Prelude`	Fractional division
`(**)`	`Floating a => a -> a -> a`	`Prelude`	Raise to the power of
`(^)`	`(Num a, Integral b) => a -> b -> a`	`Prelude`	Raise a number to a non-negative, integral power
`(^^)`	`(Fractional a, Integral b) => a -> b -> a`	`Prelude`	Raise a fractional number to any integral power
`(%)`	`Integral a => a -> a -> Ratio a`	`Data.Ratio`	Ratio composition
`(.&.)`	`Bits a => a -> a -> a`	`Data.Bits`	Bitwise and
`(.\|.)`	`Bits a => a -> a -> a`	`Data.Bits`	Bitwise or
`abs`	`Num a => a -> a`	`Prelude`	Absolute value
`approxRational`	`RealFrac a => a -> a -> Rational`	`Data.Ratio`	Approximate rational composition based on fractional numerators and denominators
`cos`	`Floating a => a -> a`	`Prelude`	Cosine. Also provided are `acos`, `cosh`, and `acosh`, with the same type.
`div`	`Integral a => a -> a -> a`	`Prelude`	Integer division always truncated down; see also `quot`
`fromInteger`	`Num a => Integer -> a`	`Prelude`	Conversion from an `Integer` to any numeric type
`fromIntegral`	`(Integral a, Num b) => a -> b`	`Prelude`	More general conversion from any `Integral` to any numeric type
`fromRational`	`Fractional a => Rational -> a`	`Prelude`	Conversion from a `Rational`. May be lossy.
`log`	`Floating a => a -> a`	`Prelude`	Natural logarithm
`logBase`	`Floating a => a -> a -> a`	`Prelude`	Log with explicit base
`maxBound`	`Bounded a => a`	`Prelude`	The maximum value of a bounded type
`minBound`	`Bounded a => a`	`Prelude`	The minimum value of a bounded type
`mod`	`Integral a => a -> a -> a`	`Prelude`	Integer modulus
`pi`	`Floating a => a`	`Prelude`	Mathematical constant pi
`quot`	`Integral a => a -> a -> a`	`Prelude`	Integer division; fractional part of quotient truncated towards zero
`recip`	`Fractional a => a -> a`	`Prelude`	Reciprocal
`rem`	`Integral a => a -> a -> a`	`Prelude`	Remainder of integer division
`round`	`(RealFrac a, Integral b) => a -> b`	`Prelude`	Rounds to nearest integer
`shift`	`Bits a => a -> Int -> a`	`Bits`	Shift left by the specified number of bits, which may be negative for a right shift.
`sin`	`Floating a => a -> a`	`Prelude`	Sine. Also provided are `asin`, `sinh`, and `asinh`, with the same type.
`sqrt`	`Floating a => a -> a`	`Prelude`	Square root
`tan`	`Floating a => a -> a`	`Prelude`	Tangent. Also provided are `atan`, `tanh`, and `atanh`, with the same type.
`toInteger`	`Integral a => a -> Integer`	`Prelude`	Convert any `Integral` to an `Integer`
`toRational`	`Real a => a -> Rational`	`Prelude`	Convert losslessly to `Rational`
`truncate`	`(RealFrac a, Integral b) => a -> b`	`Prelude`	Truncates number towards zero
`xor`	`Bits a => a -> a -> a`	`Data.Bits`	Bitwise exclusive or

Table 6.3. Typeclass Instances for Numeric Types

Type	`Bits`	`Bounded`	`Floating`	`Fractional`	`Integral`	`Num`	`Real`	`RealFrac`
`Double`			X	X		X	X	X
`Float`			X	X		X	X	X
`Int`	X	X			X	X	X
`Int16`	X	X			X	X	X
`Int32`	X	X			X	X	X
`Int64`	X	X			X	X	X
`Integer`	X				X	X	X
`Rational` or any `Ratio`				X		X	X	X
`Word`	X	X			X	X	X
`Word16`	X	X			X	X	X
`Word32`	X	X			X	X	X
`Word64`	X	X			X	X	X

Table 6.4. Conversion Between Numeric Types

Source Type	Destination Type
Source Type	`Double`, `Float`	`Int`, `Word`	`Integer`	`Rational`
`Double`, `Float`	`fromRational . toRational`	`truncate` *	`truncate` *	`toRational`
`Int`, `Word`	`fromIntegral`	`fromIntegral`	`fromIntegral`	`fromIntegral`
`Integer`	`fromIntegral`	`fromIntegral`	N/A	`fromIntegral`
`Rational`	`fromRational`	`truncate` *	`truncate` *	N/A

procedure/goto/if/case... What should we use?

Jan — Fri, 19 Dec 2008 01:02:00 -0800

"Recently practitioners of programming discipline have advised us not to be afraid to use procedure calls, as the readability they afford is worth the inefficiency. This is like saying that cars with square wheels qare all right because transportation is worth a bumpy ride: we really ought instead to concentrate on improving our wheels."

An interesting metaphor from Guy Lewis Steele in his paper. "as the A they afford is worth the B", I've seen such statements serveral times. It make me think that it's usually an execuse because ppl just don't want to spend time to really resolve a problem.

Two insightful points from this paper:

* Our difficulties in dealing with programming and programming languages stem in part from a confusion between the abstract notions of prgram organization and the concrete embodiment of these notions as programming language constructs. The important point is that for each important programming concept which we have found useful -- modularity, iteration, assignment, conditionals -- there may exist more than one programming language construct which can embody that concept in a reasonably natural manner. In understanding (a piece of) a program it is necessary to determine not only what construct is being used, but the concept it is intended to express.

* We discovered that GOTO was often being used even in situations where more appropriate and expressive constructs were available, and that it was being used for all sorts of purposes we hadn't anticipated, and so we sought to eliminate unwanted concepts and programming styles by banning a construct.

What's need by tail-recursion optimization in funcational language?

Jan — Wed, 17 Dec 2008 09:57:00 -0800

What's the common ideas needed by all high-level programming languages?

* Transfer of control
- conditional
- unconditional
* Environment operation
- variable binding on function entry
- declaration of local variable
* Side effects
- assignment
- IO
* Process synchronization
- resource allocation
- passing of information between processes

The idea behind tail-recursion optimization in applicative language

* function is goto with arguments. There's no need for return address for a function. We need save a return address on the stack when we begin to evaluate a form (function call) which is to provide an argument for another function, rather than when we invoke the function.
* so, we pushes addtional control stack only when evaluate forms, for function application, we only need set up environments.
* this is why we can't use the same way to optimize tail-recursion in imperative language - the return address for the caller function may not be the continuation address of the callee
* lexical binding is necessary for lambda goto rule. we can't use goto to replace funcation call with dynamic binding.

An interesting symmetry: control constructs determine constraints in time (sequencing) in a program, while environment operators determine constraints in space (textual extent, or scope).

Ref. Guy Lewis Steele, Jr.. "Lambda: The Ultimate Declarative". MIT AI Lab. AI Lab Memo AIM-379. November 1976.

Super fast action with Rails Metal

Jan — Tue, 16 Dec 2008 10:11:00 -0800

Josh commit a new feature into edge rails named Metal. With it ppl can use rack directly to serve request easily. Take a look at his example:

 # app/metal/poller.rb
class Poller <> "application/json"},
 Message.recent.to_json]
 else
 super
 end
end
end

* There is a generator to help you get started
`script/generate metal poller`

* Also, metal bits can be ran standalone with rackup
`rackup app/metal/poller.rb`

Not the request to 'http://your.app.com/poller' will be processed in rack, that's more faster than processing it in controller :)