$\newcommand{\defeq}{\mathrel{\mathop:}=}$

## 2008/02/04

### 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 xf 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

--

Labels: