CS 252

Spring 2007

Lab #14

The purpose of this lab is to gain more experience with Scala actors through a group discussion. (Why a group discussion? Lectures are fine for facts and basic skills, but they aren't very effective for learning higher-level skills. Group discussions are known to be more effective; see for example this paper for an application to CS. Free access through the ACM Digital Library link of the SJSU library)

1. This Scala actors tutorial shows how to do a pretty standard trick: use concurrency to make a tree iterator. Because we also want to be able to do this in Java, we'll use a tree structure that already exists: the DOM tree.

package cs252;

import java.io._;
import javax.xml.parsers._;
import org.w3c.dom._;

object Lab14 {
  def main(args: Array[String]) {
    val factory = DocumentBuilderFactory.newInstance()
    val builder = factory.newDocumentBuilder()
    val file = new File("/path/to/application.xml")
    val doc = builder.parse(file)
    val root = doc.getDocumentElement()
    traverse(root, println _)
  }
  
  def traverse(n : Node, f: (Node) => Unit) {
    f(n)
    val list = n.getChildNodes
    for (i <- 0 until list.getLength) 
        traverse(list.item(i), f)          
  }
}

Replace the file path with a path to some XML file you have. (Don't have one? Use this application.xml.) Run the program. You'll get an output such as

[application: null]
[#text: 
  ]
[display-name: null]
[#text: ActiveLecture]
[#text: 
  ]
[module: null]
[#text: 
    ]
[ejb: null]
[#text: ActiveLecture-ejb.jar]
...

That's the typical preorder tree traversal that you saw way back when in your CS2 course. But often times, it is more convenient to iterate, using the familiar pattern:

val iter = new TreeIterator(root)
while (iter.hasNext) {
  val n = iter.next
  println(n)
}

Our challenge is to turn the traversal into an iteration, using actors. The basic idea is simple:

• We run the tree traversal in an actor
• When we encounter an element, we send a message containing that element
• When we are done, we send a Done message

The iterator's hasNext must wait for the next message. If it contains data, stash it away so that next can get it. If it is Done, return false. Actually, it's a little messier because someone could call hasNext twice, or call next without first calling hasNext. Let's have a peek helper method to solve that:

class TreeIterator extends Iterator[Node] {
  private var current: Node = null // set to the next value by peek
  private var done: false // set to true by peek if at end
  private def peek { if (current == null) ... }
  def hasNext = { peek; !done }
  def next = { peek; val r = current; current = null; r }
}

Note that this messiness has nothing to do with concurrency.

Now peek must wait for a message from the traversal.

How does the process get started? The constructor TreeIterator(Node) must start the traversal actor.

class TreeIterator(root : Node) extends Iterator[Node] {       
  val source = actor {
    traverse(root, n => { target ! n } )
    target ! Done
  }
}        

Note that we can't simply flood the target actor's mailbox with messages. After all, if we simply wanted to dump the nodes into a queue and iterate over that, we could have done so without any actors. But at an O(n) cost, where n = size of the tree. We want an O(1) space mechanism. In other words, we want to put one tree value, have it consumed, put the next, and so on.

Clearly, this is a bit trickier than it appears. Your goal is to develop a strategy (without actually coding it up).

We'll run group discussions (using the same groups A, B, C, as for your projects). In each group, choose roles for

• the facilitator (who ensures that everyone does their part)
• the scribe (who writes up the group decisions)
• the artist (who produces diagrams as required)
• the presenter (who will present the group findings to the class)

You have 20 minutes to develop a strategy for presentation to the class.

2) After listening to the group presentations, your group may choose to modify your strategy. You should then implement the chosen strategy, using one computer. Your roles are now

• the facilitator (who ensures that everyone does their part)
• the typist (who types in the original solution and gets it to compile)
• the fixer (who takes over when the original solution doesn't work)
• the scribe (who keeps track of which changes to the strategy became necessary)

You have 20 minutes to develop an implementation, and will then present it to the class.