scm 老師的寓言

我上星期五講了一篇 Jeremy Gibbons 的〈The Third Homomorphism Theorem〉。我沒把 paper 讀得很深，所以講得很淺，不過果然如預期把 scm 老師的 comments 引出來了 XD。今天 scm 老師來信補充一些內幕，講了一個寓言故事：

Hi,

Secondly, some comments on the 3rd homo. theorem.

When I just started my postdoc in Japan, people there were talking about the 3rd homo. theorem. The theorem says that if f can be expressed both as a foldr and a foldl, there exists some ⊙ such that

f (x ++ y) = f x ⊙ f y.

The aim then was to automatically, or semi-automatically, derive the ⊙ operator, given the left-fold and the right-fold.

They were discussing three examples,

1. f = sum, where ⊙ can simply be +.
2. f = sort, ⊙ can be merge.
3. f = scan. It is actually possible to compute f in parallel!

Being just graduated from Oxford, I was not very keen about automation (being too proud of saying "I don't use a computer!"). Instead I felt that all the instances they talked about can be expressed better in a relational setting. So I gave a small presentation with 17 slides, attached below.

The conclusion was "it's difficult, and we have not improved too much since Gibbons." Deep inside I considered these ugly, ad-hoc approaches to automation inferior to our beautiful relational theory.

Last year, however, my colleagues and I met somewhere else. I was told that they eventually published a paper on this subject:

Kazutaka Morita, Akimasa Morihata, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi,
Automatic Inversion Generates Divide-and-Conquer Parallel Programs, PLDI 2007.
http://www.ipl.t.u-tokyo.ac.jp/~hu/pub/pldi07.pdf

Well, I think that shows we cannot just stop when we think it's difficult, and it sometimes pays to get our hands dirty.

Anyway, I'd be happy if someone could read the paper and talk about it someday.

sincerely,
Shin

某種程度而言，我也不喜歡帶有 dirty work 的作品，我的 "ultimate goal"（希望我在某一集回顧會記得談到這個…）也不一定必須做 automation，特別是複雜的 automation。那句 "Deep inside I considered these ugly, ad-hoc approaches to automation inferior to our beautiful relational theory" 的精神其實差不多就是我現在的想法。（像 scm 老師先前提的一篇 array bounds elimination 我根本提不起勁去看…）scm 老師這則故事的寓意對我算是醍醐灌頂。

--
貼在這裡提醒自己，也順便和大家分享 :P。