AV Development Library

3 replies [Last post]
shaffer
shaffer's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 2009

Here are initial thoughts on an AV development library to support the hypertextbook project. This is quite early in the planning process. Thanks to Ville Karavirta and Tom Naps for ideas.

 

Design Ideas for the Hypertextbook AV Development System

Last update: June 8, 2011
  


To best support AV development for the proposed hypertextbook system, it will become necessary to create a new AV development environment. This is driven in part by the new language being developed for (JavaScipt for native execution in HTML5), but also because existing systems do not support all of the features that we can identify as being important to the hypertextbook project. However, it is important to recognize that existing systems have individual aspects that are highly valuable, and to capture and retain such aspects.


Scripting language vs. API?

The most fundamental design question is whether to approach this in terms of

  1. defining (and then implementing) a scripting language for AVs, or
  2. defining a set of library utility routines with an API.
      

If a good scripting language could be devised, that would seem to be preferred. But over the years many have tried to do this, and the result generally is that scripting languages do not support good interaction. So developers quickly run up against the limits of the language. They then get coerced into creating non-interactive AVs. I am doubtful that we could do better this time around, though we would have the advantage of pooling the experience of many developers of such scripting languages.

Advantages of using a library/API approach include:

  1. It can be developed and standardized in functional increments, with changes to one unit of functionality not affecting the other parts.
  2. Individual developers can use or ignore as much as they like, therefore not becoming constrained by the limits of the API.

      

Pseudocode

Pseudocode display is a common feature of AVs *though a study by Saraiya and Shaffer casts a question on whether providing pseudocode
actually improves learning). Regardless, most developers want to provide this functionality in the system if it is not too much work for them. Therefore we should do it right. By far the best pseudocode system that I know of appears in Algorithms in Action, and we should copy that approach for the new system. For a given AV, the pseudocode is defined in a separate file written with a markup language. At the moment, I am leaning toward a markup language in XML for the new system (the one used by AIA is rather cryptic).

Pseudocode display has the concept of collapsing hierarchies, where a function might be presented either by a single comment or by multiple lines, each of which might in turn be expanded into multiple lines. This relationship is captured by the markup language. Of course, once the developer has created the pseudocode markup and initialized the pseudocode pane (see Sectioning), everythieng is handled automatically except for actually calling the highlighting function in the AV driver. Of course, the pseudocode can drive the AV as well. When a section of the pseudocode is closed, the visualization
will typically want to skip over those details. Thus, the AV driver has to be able to get the necessary information about the state of the
hierarchy from the pseudocode API.

In addition to the pseudocode section of the AV, AIA also supports a separate pane that provides extra comments about the currently highlighted line of pseudocode. These additional comments are defined in the pseudocode markup file.

See comments below about Sectioning. The Pseudocode widget should be able to accept various sizing and resizing.

Assessment/Quizzing


An integral part of our vision for the hypertextbook is an extensive system for assessment activities. Not only does assessment help instructors and students know that the student is on track, it also intrinsically improves engagement. In its weakest form, assessment is questions at the end of a (small) unit. Better is when it is closely intertwined with the presentation. For example, TRAKLA exercises.

The assessment system needs to support a rich array of assessment question types. Of course this should include all basics such as multiple choice and fill in the blank. Questions and answers should be store in a recognized standard, in a question bank that supports randomized draw of questions when appropriate, and the system must support storing and forwarding results to the instructor.

Some of the desired exercise/activity types are only relevant to CS topics (such as exercises where the student writes code, which is assessed by executing the code and comparing its output to the answer key). Thus, it will be quite a challenge to deploy this system, since any collaborators providing the assessment might not be inclined to support all that we need. The assessment system architecture needs to be quite flexible, allowing for some concept of "plugins", such as the ability to farm out a code section to some framework that will compile the code, execute it on input, and verify the correctness of the result.

Another type of exercise that must be supported is that used by TRAKLA. For example, a user drags supplied input data values to the correct node in a tree to demonstrate profiency at insertion. Or drags values around in an array to simulation a sorting algorithm. This should not be so hard to manage. The AV just needs to be able to accept an input stream (such as the numbers to be processed, and provide an output stream (such as placement positions), which can then be compared against the answer key for grading purposes. However, this requires a reasonably rich ability to define the score resulting from such an output stream.

It must be easy for many people to add questions to the data bank, and to control the selection of questions offered. Just as an instructor might wish to pull out a set of modules from the hypertextbook to define a specific course offereing, the instructor might wish to control the questions offered for a particular module, or add his/her own questions.


Messaging

One of the most important features of effective AVs invariably is the stream of comments that are generated by the AV to the user as the visualization progresses. Often this involves computation of values tied to the particular input being processed. If such input is generated on-the-fly, then obviously the contents of the messages also has to be generated on-the-fly, or at least parameterized. Messages need to be color coded. Ideally, the message stream would be defined in a separate file to be fed into the AV engine (see the idea of markup file for pseudocode), though this might not be possible due to
the need to generate on-the-fly bindings. But having the message stream separate makes it easier to edit.

Orthogonal to defining the messages themselves is the delivery of the messages onto the screen. There are at least a couple of different ways that this can be done effectively. Often the best approach is a good sized window, usually taller than it is wide (say along the left side of the AV) gives room for many messages. A scroll bar allows the user to see past messages.

But sometimes the designer won’t want that approach. Perhaps it just isn’t viable to give this much screen real estate to the messages, or perhaps a history is not needed, and only one message at a time needs to be on the screen. The messaging system should be flexible to adapt to various needs. It should be possible to define a message pane (see Sectioning) with scroll bar, or to define a simple one-or-two line overwriting scheme simply by changing configuration parameters when initializing the visualization.


Sectioning


There typically are several distinct visual components to an AV, including possibly pseudocode, messaging, and the main visualization pane or even two main visualization panes. It should be easy to configure the AV canvas to define various panes as desired. So for example, one can define the messaging pane of whatever size and position within the canvas, with options as described above regarding scrolling vs. overwriting. Messages automatically get sent there. One can define a pseudocode pane of whatever size and position, which automatically gets the supporting pseudocode. One can define a main
visualization pane, and direct graphical objects to there. Or two visualization panes, and send appropriate objects to each.


Data Structure Layout

There needs to be support for automated layout of pre-defined data structure types: Array, linked list, trees, and graphs. AV developers should not have to deal with placing the components of such structures.


Charting support


Some AVs might want to be able to present data in the form of a chart. This probably doesn’t need to be too fancy, and we probably should develop this functionality as the needs actually emerge. But anyone who develops some AVs with data charting should make an effort to generalize the functionality for future reuse.


State system support and video player controls


Most presentation-oriented AVs take the form of a "post mortum" dump of a sequence of states and their visual transistions, with the ability to move forward and backward in the sequence (using "standard" videoplayer controls). Even an AV that seems to be working on-the-fly can often make use of the state sequence paradigm between key stages. For example, consider a search tree AV that lets users enter values to insert/search/delete. For any given operation on the tree, the user can enter the value, and the the AV can generate the sequence of states to execute the operation. Then the user can work through a visualization of the sequence, going backward and forward within that particular sequence. When ready, the user goes on to the next operation (and probably cannot back up beyond the beginning of the current operation).

The AV development system should support this approach. The only tricky part is that it might be difficult to define generic "state" objects. The system needs to be flexible enough to allow the developer to store whatever necessary to describe the states and their transistions.
  

shaffer
shaffer's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 2009
Re: AV Development Library

Ville Karavirta and I have begun writing sample code for the project. You can see what we have done (and join us in the effort if you would like) by checking out the OpenDSA directory from the OpenAlgoViz SourceForge project.

svn co https://openalgoviz.svn.sourceforge.net/svnroot/openalgoviz/OpenDSA OpenDSA

We have begun by implementing the Shellsort demo storyboard.

 

shaffer
shaffer's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 2009
Re: AV Development Library

The current version of the library does (so far as we can tell) meet all of the requirements outlined in the section about "Messaging", with the exception of handling messages stored in a separate text file. It supports the designer’s choice of a textarea (with scrolling) that can be defined to whatever size desired, and allows for formating the text (since it is actually an HTML paragraph to which one can write whatever HTML code one wants). Alternatively, with minor changes to style parameters, the designer can choose to have messages written to an invisible spot on the screen such the each message overwrites the last. This seems like a simple and flexible messaging system.

 

shaffer
shaffer's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 2009
Re: AV Development Library

Since Ville chose to implement using JavaScript interacting with CSS/HTML (as opposed to SVG or Canvas), Sectioning as described above turns out to be dead easy, basically coming automatically. There isn’t anything that needs to be added in terms of library support. One merely defines the desired CSS/HTML element in the HTML, and uses the JavaScript DOM access mechansim to do the right things. This, for example, is why we were able to handle Messaging so easily. You simply define a paragraph of the desired type (named "output scroll" or "output line" as desired, depending on whether you want a scrolling box or each message to overwrite the previous), and all calls to our library’s "Tell" function will write there. The placement is where ever  you define the "output" paragraph to be on your page.

In similar fashion, one defines buttons using the HTML elements, and connects the appropriate JavaScript callback functions. Or one sets up various input fields, calling whatever desired JavaScript functions for validation and processing.

If you look at the Shellsort Performance example, yes a lot of the code deals with interface rather than the actual shellsort engine. But the fact is that one can make any similar sort of application with pretty much the same interface code. So if you use my example as a template at that point you mostly only need to write your own simulation or data structure code. Of course, doing either of the other two dynamic components called for in the Shellsort Sotryboard requires a whole lot more technology. That’s why I did the performance example first since it was pretty easy. Ville is working on support for the "slideshow" part next.