Flask Introduction

The Flask is computational system for solving problems and experimenting with an artificial chemistry and evolutionary computation. It is a simulation of a reaction vessel, a virtual flask, where abstract atoms react to form molecules based on a set of user-defined binding rules. By casting problems from a variety of domains in terms of Flask objects, computational problems can be solved without the need for programming in a traditional programming language. In a sense, the Flask is a declarative programming system; however, it may be used as a library to a program that defines more complicated problems. It can also be extended by extending the Flask object model in Java.

Leonard Adelman (in "Molecular Computation of Solutions to Combinatorial Problems", Science 11/1994) showed that processes using DNA molecules could be used to solve the Hamiltonian path problem, an NP-Complete problem in graph theory.  A large number of DNA sequences representing edges in a graph were mixed together resulting in the formation of DNA sequences that represented random paths through the graph.  Various steps involving chemical processing were then performed to remove all sequences that did not met the criterion for a Hamiltonian path.  At the end of the process, if any sequences remained, there was a Hamiltonian path for the set of vertices; otherwise, there was none.  Due to the large number of molecules used, it was very likely that a path would be found if it existed.

The interesting point of this demonstration is that a computation was performed in parallel by a large number of molecules.  Simulations of DNA computing have been created, but simpler simulators like the Flask can be used to study the style of programming needed for molecular computing without the complexity of dealing with real  molecules.  Although the Flask does not benefit from parallel processing, it demonstrates the flavor of parallel molecular computation.

The Flask uses a loose analog to chemistry for its set of basic objects and control mechanism. The primary objects in the Flask are the virtual flask, atoms, and binding sites¹ . The control mechanism simulates atoms reacting in a reaction vessel. This simulation is stochastic: atoms are selected randomly, two at a time, as potential reactants. (The selection of two atoms is called a collision.) This approach means that two runs of the same set of atoms might produce different results. Such non-determinism might seem like a determent for a programming language; however, it is sometimes useful. In simulated annealing and genetic algorithms, randomness allows such systems to find optimal solutions by avoiding suboptimal ones. In the Flask, the randomness allows the search space of atomic configurations to be explored over a number of simulation runs. Although the Flask control mechanism is stochastic in nature, deterministic results can be obtained in cases were dictated by the problem being solved by careful problem construction.

Simple Examples

Before describing the Flask in detail, a few simple examples will be presented to give the flavor of how the Flask works.  In these examples, only simple attributes of Flask objects are presented.  Atoms have a name and a numerical id, for example, a27, a42, and b.  In cases were atoms have the same name but a different id, they belong to the same group of similar atoms.  These atoms have all the same attributes except for their bonds with other atoms.  In cases where specifying an atom by name only is unambiguous, the id does not have to be given.

The primary binding site attributes relative to these examples is name and number.  Binding sites of different atoms with the same name are potential candidates for forming bonds.  The number of a binding site indicates how many other atoms it can bond to.  A number of "*" means that the binding site can link to an indefinite number of atoms.  The number of bonds between two atoms using binding sites of the same name is limited to one.

When discussing The Flask, there are several ways to describe atoms.  Figure 1 shows the diagram method, which is used throughout this site. Each atom is represented by a circle with its name and, optionally, its id written in the center.  Binding sites are represented by lines with the binding site name written beside the line.  In Figure 1a, there are three atoms:  a, b, and c, and they are not bound.  Atom a has a P binding site with number 2.  The other atoms each has a P binding site with number 1.

If the configuration given in Figure 1a were ran in The Flask simulator and if the simulator were run for enough iterations, there are two possible outcomes shown in Figure 1b and c.  Either atoms b and c bond to atom a using the P binding sites or they bind to each other.  The outcome is determined by which two atoms are selected for the first collision.  If a mix of a, b, and c atoms were collided in the Flask, molecules of both form would be found.

Figure 1

Figure 1 - Atoms before they react (a) and possible outcomes (b) and (c)

To solve a problem using the Flask, one must first cast the problem in terms of atoms, their properties, and binding sites.  Figure 2 shows an example.  In this example, the sum atom has two A binding sites.  These binding sites differ from those in Figure 1 in that they have the electrostatic + property.  These binding sites can only bond to A binding sites that have the electrostatic - property as those in atoms value1 and value2,  The electrostatic - binding sites in the value atoms cannot bond, so value1 cannot bind to value2.

Also note in the figure that each atom has its mass in parentheses after its name.  By default, atoms have mass 1, but in this case, the mass of atoms value1 and value2 represent values to be added.  The mass of the sum atom is zero so that the sum will include only the mass values of the atoms attached to its binding sites.  Figure 2b shows the result of running the simulation.  The atoms form a molecule whose mass is the sum of the two value atoms.  Note that the solution to this problem is deterministic; however, we cannot predict which value atom will bind to the sum atom first.  As long as the simulation runs long enough, the solution will be the same.

This simple example illustrates that simple computations, such as summing two numbers, can be solved with the Flask.  But, a variety of more complex problems can be represented and solved using the Flask.  In later sections, we show how the Flask can solve the problem of finding the shortest path between two cities and how it can be used to allocate land to cities based on planning criteria.

Figure 2 - Simple math using the Flask, (a) before reacting and (b) the resulting molecule