[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