I've always enjoyed the mathematical tradition of “proofs without words”, so I wanted to see if something similar could be done with an algorithm. Of course, an algorithm is typically more complicated than a mathematical identity, so it's not surprising that an algorithm typically can't be captured in a single picture. Instead, I've found the idea of a commutative diagram to be a useful pictorial shorthand, where the short way around the diagram gives a high-level view of the operation, and the long way around gives more detail. Here is an attempt to describe my breadth-first numbering algorithm from ICFP 2000 using this idea.
Wanted
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnmJpk5VoJEIcI9OYwRjAfrThyphenhyphen2lr314EZ8zNOknVyV8jQ4-GezptyT6I9bXcrDmyXpBMihoUQmouWJ6LmpeQXcCm-GBu0t9qh14cccurgByQDNgDQJOJ1vVVg5K6GZu2xitW7gjX3sXY/s400/bfn-wanted.jpg)
Rules
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhtjo8lgIbz_35acTiYTPn5HCBW4ZYh-2mGwbCJ06ZCPDSMoUgWfmsFkHuFFYm5rvFYEU05TX67Drz4kFcAEwEBCEs9MR7zYBwOcEo7Tgy3NM7kBFOqPgyCTywo_0w66Tcg9JeQmxwj8kE/s400/bfn-rules.jpg)
Example
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXXEzbzjhNAiVNyvNVxhr-8MIZCKMEHg6uSYU2O7BuQ8HOfFJ8nQTt6pS9X7bqiyPx8m7srtRIOtAoSfpwWSXbu71-hVNI1lRn-jUFNR4yt_QvQMbU0qyqUoq7KAIZPFuHTkvj6-H1CkA/s400/bfn-example.jpg)
3 comments:
Cool. I have tried to do similar things here: Visualizing algorithms and data structures
Way cool. For those interested, the paper is online (Postscript, other formats here).
This reminds me of Aardappel, a programming language in which you write programs in the form of such before-and-after diagrams — sort of. It's free software, you should play with it.
Post a Comment