[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

computer-go: Adaptive Functional Programming



Issues of incremental update of data structures come up fairly
regularly in Go programming.

Anyone interested in a highly mathematical, abstract treatment of
making this happen automatically might want to check out the Adaptive
Functional Programming stuff in
  <http://www-2.cs.cmu.edu/~rwh/papers.htm>
(which I stumbled across in a <http://lambda.weblogs.com/> note by
Ehud Lamm on 5/30/02).

The demo application in the POPL '02 paper is feeding quicksort into
their meta-algorithm and automatically producing code which not only
(1) does quicksort on an initial data set, but also (2) efficiently
updates the sorted result incrementally when a new element is added to
the dataset. Of course for sorting it's easy to achieve both ends by
hand-coding two algorithms, but it's still pretty nifty to be able to
achieve both ends automatically by just hand coding the first
algorithm; and hopefully the approach generalizes reasonably well to
less trivial problems where you definitely don't want to hand-maintain
both algorithms.

(The treatment is limited to purely functional calculations, alas.)

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
"Do the minimum necessary to declare victory, then get out!"
  -- Tim Bray (among many others, I think)
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C