Algorithm Visualization - A Domain-Specific Language
Paul Oppenheim
paul@pauloppenheim.com
Why Algorithm Visualization?
- Software is hard to understand.
- In-code: comments, unit tests
- Out-of-code: whiteboards, diagrams, meetings, documentation
- Are there universal guidelines about diagrams relating to software and algorithms?
- How would you implement such guidelines, today?
Software is often difficult to explain. Code authors frequently comment source code, write unit tests, and write external documentation. Additionally, developers use whiteboards and diagrams to communicate how their software works. Are there universal guidelines about diagrams relating to software and algorithms? What are the practical applications that can be taken today given the body of research on the subject?
Why an Algo Vis Language?
- Need *some* type of tool to make initial vis!
- Embed vis description near the code itself in the comments
- Comment-extracting tools (e.g. Doxygen, Sphinx) enhanced to process vis syntax
- Tools make HTML; vis should be web-friendly
One of the most immediate needs of anyone interested in answering this question is a practical tool for generating graphs given pseudocode / visual-code annotations. Ideally, such code would be embedded inside the code itself in the comments along with other documentation. Tools currently used for extracting comments (e.g. Doxygen, Sphinx, etc.) could be enhanced to process additional syntax to generate images. Documentation generated from such tools is typically HTML with other web-friendly data types; as such, it would be expected that diagrams in the software would be similarly web-standards friendly.
Class Project Goals
- research the existing body of work regarding algorithm visualizations
- create a simple, usable language to draw the primitives outlined in the existing work
Bonus / Later Work
- generate an extension to an existing documentation tool which processes this graphing language
- give a simple example by explaining some algorithms in a piece of existing software with these annotations
NOT going to
- be suitable for general-purpose image generation
- automatically generate graphs based on non-annotation source code in any language
- reimplement DOT - http://www.graphviz.org/
- reimplement processing - http://processing.org/
- draw UML
- the graphs will be informal, to the user's specification (possibly to UML, but ideally *mostly* arbitrary)
- UML *will* play a role in minimal flexibility (as in, minimally a user should be able to specify something close to existing UML diagram types)
Example - Quicksort
Data Structures and Algorithms with Object-Orientated Design Patterns in Java (Preiss)
Example - Quicksort
Wikipedia
Example - Quicksort
Intel
Example - Quicksort
Possible annotation to generate wikipedia version (completely uneducated guess at this point)
array, box whitespace
3 7 8 5 2 1 9 5 4
+-----------+ +-+
V | V |
3 7 8 5 2 1 9 5 4
| ^
+---------------+
etc
Example - Quicksort
Or another annotation, closer to software
array a = 3, 7, 8, 5, 2, 1, 9, 5, 4;
idx p = 0; idx i = 1; idx j = len(a) - 1;
i++ until *i > p
j-- until *j < p
line directed j.init, j
lint directed j, i.init
line directed i, j.init
{tmp = a[i.init]; a[i.init] = *j; a[j]=
Will be based on research as I go, many iterations
HOPEFULLY LESS AWFUL THAN MY HACK OF AN EXAMPLE.
Thanks! Questions? Comments?
Presentation - S5 javascript / CSS slideshow