Monday, January 26, 2015

Java 8: Processing character streams

A common operation in a functional language like Haskell involves doing some processing on every character in a string.  For example:

Prelude Data.Char> let flip c = if (isUpper c) then (toLower c) else (toUpper c) 
Prelude Data.Char> map flip "This is a TEST"
"tHIS IS A test"

Using the Java 8 stream libraries to do a similar task is a little tricky:

public class StringDemo1 {
  public static String invertCapitals(String other) {
    return other.chars()
      .mapToObj(StringDemo1::flipCap)
      .map(c -> Character.toString(c))
      .reduce("", (s, c) -> s + c);
  }
 
  public static Character flipCap(int c) {
    if (c >= 'A' && c <= 'Z') {
       return (char)(c - 'A' + 'a');
    } else if (c >= 'a' && c <= 'z') {
       return (char)(c - 'a' + 'A');
    } else {
       return (char)c;
    }
  }
}

First, we need to convert the string to a stream. That is what the chars() method does. Unfortunately, it creates an IntStream. We use the mapToObj() method to turn the IntStream into a Stream<Character>. Having done this, we use map() to turn it into a Stream<String>, and finally we can use reduce() to combine it all into a single string.

While this does get the job done, it is very inefficient, as a new String object must be allocated for each reduction.  The following variation uses collect() to use a StringBuilder to accumulate the new String efficiently:

public class StringDemo2 {
  public static String invertCapitals(String other) {
    return other.chars()
      .mapToObj(StringDemo1::flipCap)
      .map(c -> Character.toString(c))
      .collect(StringBuilder::new,StringBuilder::append,StringBuilder::append)
      .toString();
  }
}


Using collect() is arguably not as aesthetically pleasing as reduce().  Here is an explanation of the arguments:
  • The first argument generates the collection that will be the accumulation target.
  • The second argument appends an element to the collection.
  • The third argument joins two collections.
This particular example is odd because StringBuilder::append is an overloaded static method.  The first one appends a String; the second one appends a CharSequence, an interface that StringBuilder implements.

Having compared the aesthetics, what about performance?

I found that the version with collect() could process a 100,000 character string in 19 milliseconds, while the version with reduce() requires 6520 milliseconds.

My test program is below.  It provides a nice demonstration of passing functions as parameter values.

import java.util.function.Function;
import java.util.stream.IntStream;

public class StringDemoComparison {
  public static void main(String[] args) {
    String input = 
      IntStream.iterate(1, x -> 1 + x)
               .mapToObj(x -> Character.toString((char)(x % 58 + 65)))
               .limit(100000)
               .collect(StringBuilder::new, StringBuilder::append, StringBuilder::append)
               .toString();
  
    runDemo(StringDemo1::invertCapitals, input);
    runDemo(StringDemo2::invertCapitals, input);
  }
 
  public static void runDemo(Function func, String input) {
    long start = System.currentTimeMillis();
    String result = func.apply(input);
    long duration = System.currentTimeMillis() - start;
    System.out.println(result.length());
    System.out.println("Duration for: " + func.toString() + " is: " + duration);
  }
}


Friday, January 23, 2015

JavaFX ObservableList

Continuing my exploration of JavaFX, another very useful feature is its collections library.  In particular, it includes automatically observable versions of the List and Map interfaces from the Java Collections framework.  These can enable very convenient GUI updates.

For example, consider a program that allows a user to enter names into a list.  JavaFX allows us to store our data internally in an ObservableList; the GUI automatically updates whenever ObservableList changes.  Here's a screenshot of the program in action:

To create the interface in SceneBuilder:

  • Create a BorderPane as the root container.
  • Add an HBox to the top of the BorderPane.
    • Place a Button and a TextField in the HBox.
  • Add a ListView to the center of the BorderPane.
The following is the Controller class I wrote to implement the functionality:
package application;

import javafx.collections.FXCollections;
import javafx.collections.ObservableList;
import javafx.fxml.FXML;
import javafx.scene.control.Button;
import javafx.scene.control.ListView;
import javafx.scene.control.TextField;

public class Controller {
 @FXML
 private Button add;
 @FXML
 private TextField name;
 @FXML
 private ListView visibleList;
 
 private ObservableList names = 
                FXCollections.observableArrayList();
 
 @FXML
 private void initialize() {
  visibleList.setItems(names);
 }
 
 @FXML
 private void addName() {
  if (name.getText().length() > 0) {
   names.add(name.getText());
   name.setText("");
  }
 }
}

In SceneBuilder:

  • Set up the above class as the controller.
  • Bind the three controls to the corresponding variables.
  • Bind the actions for the Button and TextView to addName().
Some notes on the code:
  • The key step here is calling the setItems() method of the visibleList object.  This is what binds the ObservableList names to the GUI.  Once this method is called, any changes to names will automatically appear in the list.
  • Note that this call must be in the initialize() method.  The visibleList object is created after the constructor call, so we can't put this in the constructor.  JavaFX ensures that initialize() is called before any other GUI code runs.
  • By attaching addName() to both the Button and the TextView, the user can add a name either way.

Friday, January 16, 2015

Creating a minimal JavaFX user interface in Java 8

The functional programming features of Java 8 represent a very important improvement to the language. Another important improvement is the replacement of Swing by JavaFX as the primary graphical user interface framework.  I've been using Swing for about a decade, and I've now started looking at JavaFX.

There are some great tutorials on the web about the JavaFX user interface library.  But they often run too long for my attention span.  I prefer enough detail to get a minimal program working, from which I can then tinker on my own.  So in this post I will demonstrate a minimal user interface that shows the basics of how to use Scene Builder, and how to connect the interface built in Scene Builder to some Java code.

To set up Eclipse:
  • Get the all-in-one Eclipse download that has JavaFX already set up.  
  • Make sure JDK 1.8 is installed and set up as the default.  
    • Check Preferences > Java > Installed JREs to be sure.  
  • Also make sure that Preferences > Java > Compiler > JDK Compliance is also set to 1.8.
To set up Scene Builder in Eclipse:
  • Download Scene Builder
  • In Eclipse, go to Preferences > JavaFX and specify the path to the Scene Builder executable.
Once Eclipse is set up, create a new JavaFX project:
  • Go to File > New > Other > JavaFX > JavaFX Project and click "Next"
  • Call the project "minimalfx" and click "Finish"
If you check out the project on the left, it should look something like this:

The Main.java program will contain the following code.  It will run as is, producing an empty window.  The line in red is the code we will need to change in order to incorporate our own interface:

package application;
 
import javafx.application.Application;
import javafx.stage.Stage;
import javafx.scene.Scene;
import javafx.scene.layout.BorderPane;


public class Main extends Application {
 @Override
 public void start(Stage primaryStage) {
  try {
   BorderPane root = new BorderPane();
   Scene scene = new Scene(root,400,400);
   primaryStage.setScene(scene);
   primaryStage.show();
  } catch(Exception e) {
   e.printStackTrace();
  }
 }
 
 public static void main(String[] args) {
  launch(args);
 }
}

Creating an interface with interesting behavior requires two things:
  • Creating an XML file describing the interface components.
  • Modifying the above code to interact with the components in the XML file.
To this end, then, we proceed by creating the XML file as follows:
  • Go to File > New > Other > Create FXML Document.
  • Give it the name "Gui".
  • Right-click on it and select "Open with SceneBuilder"
The Scene Builder window will look something like this:


The current interface is specified in the lower left corner, under the "Document" header.  Available components are given in the upper left corner, under the "Library" header, but separated into categories.  Click on "Controls" and drag a Button into the "CENTER" of the BorderPane.  It should then look like this:


Note that the middle area now contains a representation of our interface.  Select Preview > Show Preview in Window to see what it would look like as a running program:


Now let's modify our Main.java code so that it will run this interface: 
  • Save the interface in SceneBuilder.  It is a separate program from Eclipse, so although you can run it from Eclipse its updates are not automatically reflected therein.
  • Refresh the entire project in Eclipse.  
  • Go to Main.java.  As we can see in the code above, it creates an empty BorderPane that does nothing.  We want our newly created BorderPane to be in there instead.  So replace the original BorderPane creation code (in red) with the following:
  •             
    FXMLLoader loader = new FXMLLoader();
    loader.setLocation(Main.class.getResource("Gui.fxml"));
    BorderPane root = (BorderPane) loader.load();
    
  • Run Main. It should now look like this:

Note the 400x400 size.  That's the size set in Main.java, which we can change as we see fit.

Having created the interface using SceneBuilder, and having linked it up with our code, the last thing we will do is add behavior to the Button.  Create a new Java class called Controller.  Then enter the following code:

package application;

import javafx.fxml.FXML;
import javafx.scene.control.Button;

public class Controller {
 @FXML
 private Button clickMe;
 
 private int numClicks;
 
 public Controller() {}
 
 @FXML
 private void initialize() {
  numClicks = 0;
 }
 
 @FXML
 private void clickHandler() {
  numClicks += 1;
  clickMe.setText(numClicks % 2 == 0 ? "Even" : "Odd");
 }
}

Some notes about the code:
  • The @FXML annotation allows these otherwise private elements to be accessed by SceneBuilder.  These items become options we can select within SceneBuilder for our interface.
  • The initialize() method is called when the interface is created.  Typical constructor tasks go there.
  • The JavaFX components often have the same names as the original Java Abstract Windowing Toolkit.  It's important to get the imports right to make sure we have the right components.
Now we're ready to connect the interface to its handler, the Controller class:
  • Back in SceneBuilder, select "Controller" under the Document menu.
  • In the Controller Class box, enter "application.Controller".
  • Now click on the Button we added earlier.  On the right, select the "Code" item.
  • Look for the fx:id field under the Identity header.  This will be near the top of the Code region.
  • There will be a drop-down menu with a single option: clickMe.  
    • Select it.  
    • This binds the object in SceneBuilder to the named object in the Controller class.
  • Under the Main header, go to the "On Action" field.  In the drop-down menu, select clickHandler.  
  • Save the interface in SceneBuilder and refresh the project in Eclipse.
  • SceneBuilder should look like the following at this point:

From within Eclipse, run Main once again.  Once clicking begins, the button should now respond as programmed.

And that's all there is to it.  Happy tinkering!

Monday, January 12, 2015

Java 8: A functional programming language (?)

I'm preparing to teach some Java courses this semester.  I hadn't had a chance to look at Java 8 until this past week, and so far I am impressed.  This post is not really a tutorial; it's more of a small demonstration of the possibilities.

The key to Java 8's functional features is the new stream library.  A Stream in Java is a lazy sequence of values.  Each of the collection classes in the Collections framework has a .stream() method to get a stream view of its contents.  The Arrays class also contains a static method to get a stream view of an array.  The following example, which converts each command-line argument to an integer and prints the sum of the positive values only, demonstrates the framework nicely:

 import java.util.Arrays;  
 public class SimpleDemo1 {  
      public static void main(String[] args) {  
           System.out.println              
              (Arrays.stream(args).map(s -> Integer.parseInt(s))  
                                  .filter(x -> x > 0)  
                                  .reduce(0, (x, y) -> x + y));  
      }  
 }  

Here is an equivalent program in Haskell:

 module Main where  
 import System.Environment  
 main = do args <- getArgs  
           putStrLn $ show 
                    $ foldr (+) 0 
                    $ filter (\x -> x > 0) 
                    (map read args :: [Integer])

Here are some noteworthy similarities:
  • Both languages use -> to separate anonymous function arguments from the code. 
  • Java now includes (limited) type inference and an implicit return.
  • Both use lazy evaluation of the streams.
  • Both implementations have a similar amount of text:
    • Haskell: 30 words, 223 characters
    • Java: 31 words, 264 characters
And some noteworthy differences:
  • The fundamental paradigms of each language dictate the order in which the computations are written.  Note how the Haskell example has the higher-order functions placed in the reverse order of the Java example.
  • Lazy evaluation remains pervasive in Haskell, while being confined to this new little corner of Java.
  • The syntactic overhead of converting to streams in Java is not too bad, but it is not trivial either.  Still, for Java especially, this is an impressive reduction of boilerplate.
I will definitely be including this material in my Data Structures course this semester.  I plan to post periodically regarding how I approach the topic and how the students respond.

Friday, November 21, 2014

Highlights of the AAAI Fall Symposium 2014: Knowledge, Skill, and Behavior Transfer in Autonomous Robots

Last week, I had the privilege of attending the 2014 AAAI Fall Symposium on Knowledge, Skill, and Behavior Transfer in Autonomous Robots.  My own interest in this topic comes from my goal of being able to program a mobile robot by driving it around.  I presented a paper describing an approach for doing this.  It improves upon my previous work by automatically associating actions with the Growing Neural Gas nodes, rather than relying on human input for specifying an action for every node.

To demonstrate the versatility of what I had implemented, on the morning of the talk I drove my Lego Mindstorms EV3 robot (running leJOS) around part of my hotel room for a couple of minutes, teaching it to avoid obstacles.  I then included in my presentation a nice video of the purely visual obstacle avoidance it had learned in this short time span.

Even more fun was the poster session.  I had promised to bring the robot with me to the poster session at the end of my oral presentation.  At the start of the poster session, I drove the robot around the poster area for about two or three minutes.  I was careful to make sure I introduced it to numerous human legs, so that it would learn to avoid them.  I then set it loose, and it demonstrated very nice visual obstacle avoidance for about the next hour or so.  When learning, it hadn't seen any white sneakers, so it did run into a couple of people, but for the most part it did great!

I'm hoping to release the source code for my implementation once the semester ends and I have a chance to clean things up a bit.

There were some interesting trends in the presentations I saw.  Several people, including Peter Stone and Stéphane Doncieux, presented work in which learning happened in simulation. Stone's work "closed the loop" by transferring the learned skills to a physical robot, and even learned from the physical robot to retrain the simulation. This was an aspect of transfer I hadn't really thought about very much.

Several other presenters, including Gabriel Barth-Maron, David Abel, Benjamin Rosman, and Manuela Veloso, were focused on Markov Decision Processes and reinforcement learning. That isn't really the focus of my current work, although I've explored it in the past and I may do so again in the future.  Much of the presented work involved ways of extracting transferrable domain knowledge from an MDP policy that had been learned with a particular reward function.  By transferring that knowledge to learning a policy for a new reward function but in the same domain, learning can be accelerated.

Finally, there were several presenters, including Tesca Fitzgerald, Andrea Thomaz, and Yiannis Demiris, who showcased work in demonstration learning.  The first two are interested in humans demonstrating tasks for humanoid robots, by either showing start/stop states for arrangements of objects, or even by directly manipulating their arms.  Of particular interest was Tesca Fitzgerald's efforts towards developing a spectrum of related tasks for which knowledge transfer is possible to varying degrees.  Task knowledge that is not transferred is handled with a planner; she had a great video of a robot hitting a ping-pong ball to illustrate what she had in mind.  Yiannis Demeris does a lot of work with assistive robotics for the disabled.  He showed some fascinating work in which the robots learned to help their clients, but only to the degree that the clients wanted the help.  He's also done some work with robots teaching humans various tasks.  Particularly amusing were the humanoid robot dance instructors!

I received some great feedback on my research from Yiannis Demiris, Nathan Ratliff, Matteo Leonetti, Eric Eaton, Pooyan Fazli, Matthew Taylor, Gabriel Barth-Maron, David Abel, Benjamin Rosman, Tesca Fitzgerald, Bruce Johnson, Cynthia Matuszek, and Laurel Riek.  I returned home with enough new ideas to keep me very busy for the next couple of years.  Thanks again to everyone who helped make this a great symposium!

Sunday, November 9, 2014

Obtaining a tenure-track position in Computer Science at a liberal arts college

The essay Beyond Research-Teaching Divide has some good insights for applying for a tenure-track job at a liberal arts college.  First, a concise overview as to what this type of career entails, which is certainly consistent with my experience at Hendrix College:
The faculty members of many small colleges enjoy robust support with reasonable expectations for research output. We teach eager, inquisitive students who respect the title of “professor” (even when they do call you by your first name), whose whip-smart input enriches research almost as much as engaging with graduate students can.
The author then describes a valuable lesson learned:
I learned how to see small departments’ needs and gaps, thereby arming me to write directly to issues that did not necessarily announce themselves in job postings. Is a history department relying on its Latin Americanist to cover its Canadian history offerings? Mock up a syllabus that will lighten that load, and remark on it in your job letter. ... [W]hen small colleges hire, my experience shows that they hire people who have expertise their department lacks.
While this specific example is not directly pertinent to applying for a computer science position, the general concept definitely is.  Get to know the current faculty.  Determine their interests and aptitudes.  Look at what they publish and what they habitually teach.  From there, try to show how you would strengthen their program.  Typically, what a small department seeks is to increase its breadth.  In your cover letter, talk about how you could contribute in this way.

This last paragraph also rings true:
[S]trong letters are those that help us see a potential future colleague in front of a classroom, sharing a coffee with one of our students, and seated around our department’s meeting table (yup, we fit around one table; it’s probably not the room-filled affair you may have attended in graduate school). The best letters tell us more than what you think; they help us feel why you care about sharing those ideas with undergraduates in a classroom as much as with peer scholars in journals and books. Such letters exude enthusiasm for teaching without getting mired down in tedious assignment examples; they indicate your ability to model the research process, or (better) how you actively involve undergraduates in your research agenda.
Both of these last two excerpts are extremely helpful advice for writing a cover letter for a job at a small liberal arts college.  Study the department's web pages, as well as the college's catalog information for the program.  And be sure to convey your enthusiasm for teaching a variety of courses at all levels, especially outside your research area.  Mentioning one or two areas of genuine interest beyond your specialty can definitely be helpful.


Thursday, October 30, 2014

(In)feasibility of self-driving cars; lessons from past masters

A recent article about the challenges involved with self-driving cars contains many valuable observations.  First, the Google self-driving car depends upon maps with an astonishing level of detail:
[T]he Google car was able to do so much more than its predecessors in large part because the company had the resources to do something no other robotic car research project ever could: develop an ingenious but extremely expensive mapping system. These maps contain the exact three-dimensional location of streetlights, stop signs, crosswalks, lane markings, and every other crucial aspect of a roadway.
Creating these maps is not just a matter of adapting Google Maps to the task:
[B]efore [Google]'s vision for ubiquitous self-driving cars can be realized, all 4 million miles of U.S. public roads will be need to be mapped, plus driveways, off-road trails, and everywhere else you'd ever want to take the car. So far, only a few thousand miles of road have gotten the treatment, [...].  The company frequently says that its car has driven more than 700,000 miles safely, but those are the same few thousand mapped miles, driven over and over again. 
 And there is this very crucial caveat:
Another problem with maps is that once you make them, you have to keep them up to date, a challenge Google says it hasn't yet started working on. Considering all the traffic signals, stop signs, lane markings, and crosswalks that get added or removed every day throughout the country, keeping a gigantic database of maps current is vastly difficult.
Odd as it may seem in the constantly changing world of computing, it is important to remember the past.  Every now and then, in any research community, a researcher develops an important new innovation that proves hugely influential, often eclipsing other valuable work that is being undertaken.   For example, Sebastian Thrun, among others, has done phenomenally important work in probabilistic techniques for robot navigation.  His work provides the conceptual foundation for the Google self-driving car.  Much current robotics research is dedicated to extending and improving ideas he pioneered.

So what should we be remembering from the past?  The previous revolution in robotics was the invention of subsumption by Rodney Brooks.  (This is what everyone was excited about back when I started graduate school.)  Let's look at how Brooks described his goals:
I wish to build completely autonomous mobile agents that co-exist in the world with humans, and are seen by those humans as intelligent beings in their own right. I will call such agents Creatures.
  Consider one of the key requirements Brooks specifies for a competent Creature:
A Creature should be robust with respect to its environment; minor changes in the properties of the world should not lead to total collapse of the Creature's behavior; rather one should expect only a gradual change in capabilities of the Creature as the environment changes more and more.
 In describing the subsumption approach, Brooks goes on to describe the role of representation in his scheme:
[I]ndividual layers extract only those aspects of the world which they find relevant-projections of a representation into a simple subspace, if you like. Changes in the fundamental structure of the world have less chance of being reflected in every one of those projections than they would have of showing up as a difficulty in matching some query to a central single world model.
All of this is summarized in his famous conclusion:
When we examine very simple level intelligence we find that explicit representations and models of the world simply get in the way. It turns out to be better to use the world as its own model.
Now, as I see it, the lesson from the Google self-driving car, read in light of the thought of Rodney Brooks, is that developing a high-fidelity representation is a symptom of our ongoing inability to develop a general artificial intelligence, in spite of the almost unthinkable level of resources that Google is throwing at this project.  It is easy to be a critic from the outside, not experiencing what the engineers on the inside are seeing, but I can't help but wonder whether revisiting the ideas that Brooks introduced back in the 80s and 90s might be conceptually helpful in their endeavor.

Even though this pioneering work in subsumption is almost 30 years old, there are still useful lessons to be learned from it.  I will be presenting a paper describing my recent work on learning subsumption behaviors from imitating human actions at the AAAI Fall Symposium on Knowledge, Skill, and Behavior Transfer in a few weeks.  Something important I have learned over the years is that older research that does not conform to current fads can still be a source of cutting-edge ideas.  In fact, when other researchers are clustering around a particular fad, revisiting older ideas can often help us see an opportunity to make a contribution that others are overlooking.