The Science of Simplicity

Ever feel you have too much on  your mind and just can't sort it our?  Imagine, then, that you were told to build a computer system that could simulate a football game and predict its development. You’d have to work on each one of the game’s many elements separately. Specifically, you’d have to take into account the physical and behavioral characteristics of each of the players and of the referees, carefully laying out the way they react to each possible set of circumstances. You’d also have to consider the features of the ball and the field, the condition of the grass, the weather and so on. Then there are the rules of the game, as well as the possibility of human error in referee decisions.

The numerous elements involved make building such a computerized system through regular programming virtually impossible. This is true for many other kinds of systems as well – such as aerospace systems, complex communication networks, embryonic development and even work management in the office. All include many events that trigger multiple and diverse reactions, which is why they are called “reactive systems.”

In the past, Prof. David Harel, Dean of the Faculty of Mathematics and Computer Science at the Weizmann Institute, created a visual programming language called Statecharts, aimed at programming reactive systems. Now, together with Dr. Rami Marelly (who worked with Harel as a graduate student), he proposes a different method that may significantly advance this field.

Instead of describing every component of the game separately, in what is called “intra-object” style, Harel and Marelly propose to describe the game as a collection of scenarios depicting the possible interactions between the components (what they term “inter-object” style). The approach is similar to that of a radio or TV commentator, who rather than describing characteristics of the players and the ball, describes the dynamics among them.

The collection of scenarios includes desirable scenarios (for example, a series of passes leading to a goal), necessary scenarios (a ball kicked upward must eventually come down), forbidden scenarios (the presence of more than 22 players on the field), and the various possible ways in which the game can progress.

An important aspect of the method is that it’s easy to use. A person trying to input the possible scenarios does not need a background in programming. “There is no need to write a single line of code,” says Harel. Instead of writing a cryptic input command, the programmer “plays in” the scenarios in a natural, relatively simple way. If the programmer wants to play in the “behavior” of a telephone, for example, an image of a phone appears on-screen. The programmer – which could be anyone – would “teach” the computer how he or she wants the phone to work, feeding in the desirable, necessary and forbidden scenarios. The computer, in turn, would “understand” how the different scenarios are related, and their combination would constitute the system’s full behavioral repertoire.

This approach is supported by a tool built by the scientists for this purpose, called the Play-Engine. It can analyze the collection of behaviors as one unit and decide, using combinations of scenarios, how to respond to changing circumstances – even those that were not directly fed into the system.

The new method has produced very encouraging results and is already being used to construct computer models of complex biological processes, such as the differentiation of a group of embryonic cells in the C. elegans roundworm. Although the method was only recently published in the scientific literature, numerous scientists have already found it efficient and convenient for programming reactive systems. The Play-Engine promises to produce a significant change in the programming of large systems. It may also allow people with no background in computers to easily design new programs on their PCs, specify the dynamics of their Web pages or reprogram their home appliances.

Harel and Marelly have authored a book called Come, Let’s Play that describes their work in detail. It will be published in May with the Play-Engine software attached so that readers can “play” on their own.

Out With Dead Ends

In a follow-up project to Harel and Marelly's work, a tool called "smart play -out”was developed by graduate student Hillel Kugler, working under the guidance of Harel and Prof. Amir Pnueli of the Computer Science and Applied Mathematics Department. Its aim is to prevent the Play-Engine from running into a dead end or other undesirable situations and to minimize surprises in the behavior of the system.

Prof. David Harel is the incumbent of the William Sussman Professorial Chair. His research is supported by the Arthur and Rochelle Belfer Institute of Mathematics and Computer Science; the Gulton Foundation; and the Ida Kohen Center for Mathematics Research.