Flow-Based Programming

The following was adapted from the book, "Flow-Based Programming: A New Approach to Application Development", Van Nostrand Reinhold, NY, 1994, ISBN 0-442-01771-5, with permission. Copyright International Thomson Computer Press, 1994.

The 2nd edition of book is now (May, 2010) available from CreateSpace's eStore - https://www.createspace.com/3439170, and at Amazon.com - http://www.amazon.com/Flow-Based-Programming-2nd-Application-Development/dp/1451542321/. Take a look and see how FBP has changed in 15 years!

Herakleitos, in about 500 BC, said
 
usually translated as "Everything changes".  What he actually said was: "Everything flows".

Over the last 20 years, I worked for IBM Canada and had the pleasure of helping to develop several derivatives of the original system. During this time, we gained much practical experience with these concepts, and used them productively for a number of applications within IBM Canada. Eventually, when, rather to my surprise, I found myself retired from IBM (after a mere 33 years), I decided to write a book describing these concepts and our experiences with them, and Van Nostrand Reinhold in New York graciously agreed to publish it. In what follows, I will try to touch on some of the high points.

The kind of programming most of us in the data processing industry do has its roots in the procedural programming that arose during the 40's and 50's: the new invention called computers filled a growing need for repetitive, mainly mathematical calculations, such as tide tables, ballistics and census calculations. In these areas, computers were wildly successful. However, even then, some of the experts in this new world of computing were starting to question whether procedural application programming was really appropriate for building business applications. The combination of more and more complex systems, competition between companies, the sheer difficulty of the medium programmers work in and the need for businesses to reduce overhead is resulting in more and more pressure on today's programming professionals. At one time, it was predicted that more telephone switchboard operators would be needed than the total number of available young ladies. Of course, this problem was solved by the development of automatic telephone switching systems. Similarly, many people believe the present situation in computing can only be solved by a quantum jump in technology, and of course each new software technology claims to be the long-awaited solution. I and a number of other people believe that the concepts described in my book really do have the potential to solve this problem. However, they represent a true paradigm change which fundamentally changes the way we look at the programming process, and therefore a certain amount of unlearning is required for most application development professionals to use it. Paradoxically, these concepts are ones which should be very familiar to the attendees of this conference, but to my knowledge very few writers have realized the advantages in programming productivity and system maintainability that can result from them.

After relatively few years in the computer business, I found myself puzzling over why application programming should be so hard. Its complexity is certainly not the complexity of complex algorithms or logic. The vast majority of business applications do fairly simple things like transforming data from one format to another, accumulating totals or looking up information in one file and incorporating it into another file or a report. I and a number of other workers in the field have come to believe that the main cause of the problem is in fact the same thing that powered the computer revolution itself, namely the von Neumann computer model. As described in an article by Valiant (1990), the power of this model derives from the fact that it has acted as a bridge between the twin "diverse and chaotic" worlds (as Valiant calls them) of hardware and software, while allowing them to evolve separately. But, by the same token, its very success convinced its practitioners that the problems we are facing cannot possibly be due to any fundamental problems with this set of concepts. Programmers are not bright enough, they don't have good enough tools, management doesn't control them tightly enough, or they don't have enough mathematical education. Of course, none of these are valid explanations for the problems we are seeing. There is a far more fundamental problem - namely that, at a basic level, the tool is simply inappropriate for the task at hand. A von Neumann-style program can only do one thing at a time, so business logic, which is primarily a logic of data streams and transformations, has to be forced into a strait jacket of sequentiality.

Valiant says the time is now ripe for a new paradigm to replace the von Neumann model as the bridging model between hardware and software. The paradigm I and my colleagues have been using, which we refer to as Flow-Based Programming (or FBP), is similar to the one Valiant proposes and is in fact one of a family of related approaches, all of which suggest that we have to relax the tight sequential programming style characteristic of the von Neumann machine. Machines and programs have to become more like the real world, with many processes all communicating by means of data. If you look at applications larger than a single program or go down inside the machine, you will find many processes going on in parallel. It is only within a single program (job step or transaction) that you still find strict traditional, sequential logic, and much of the logic in a traditional program has to do with data synchronization, not with business logic. We as an industry have tended to believe that the tight control of execution sequence imposed by this approach is the only way to get reliable systems. It turns out that machines (and people) work more efficiently if you only retain the constraints that matter to your logic and relax the ones that don't, and that you can do this without any loss of reliability, and often with improved performance.

FBP is best understood as a coordination language (to use the term Gelernter and Carriero introduce in their 1992 paper describing their system called "Linda"), rather than as a programming language. Coordination and modularity are two sides of the same coin, and several years ago Nate Edwards of IBM (Edwards 1974) coined the term "configurable modularity" to denote an ability to reuse independent components just by changing their interconnections, which in his view characterizes all successful reuse systems, and indeed all systems which can be described as "engineered". One of the important characteristics of systems exhibiting configurable modularity is that you can build them out of "black box" reusable modules, much like the chips which are used to build logic in hardware. While you have to have something to connect them together with, they do not have to be modified internally to make this happen. In FBP, these black boxes, called "components", are the basic building blocks that a developer uses to build an application. The emphasis shifts from building everything new to connecting preexisting pieces and only building new when building a new component is cost-justified. If you look at the literature of programming from this standpoint, you will find that almost all writers write from the basis of creating new code, rather than reuse - in fact the very term "reuse" seems to suggest an element of surprise, as if reuse were a fortuitous occurrence that happens seldom and usually by accident! Reuse ought to be the norm, as it is in most walks of life other than programming. Here is a quote from an IBM task-force evaluating one of the dialects of FBP developed by IBM Canada in 1988 for the Japanese market: "Reuse in DFDM is natural. DFDM's technology is unsurpassed in its promotion of reuse as compared to other reuse technologies currently being promoted".

The FBP systems which have been built over the last 25 years have basically all had the following components:

• a number of precoded, pretested functions, provided in object code form ("black boxes"), not source code form, with predefined plugs and sockets (called "ports")
• a "driver" - a piece of software which coordinates the modules comprising an application, and implements the Application Programming Interface which they use to request services
• a notation for specifying how the components are connected together to construct an application and a way of turning this notation into a data structure which the driver can then "interpret" (FBP applications are designed visually, and are also most easily understood that way)
• procedures to enable the developer to convert, compile and package individual modules, networks and partial networks
• documentation (reference and tutorial) for all of the above
• (last but not least) education (preferably hands-on).

Here is an example of a fairly simple FBP network. The example shown here is of a conventional batch update. Of course, FBP can handle interactive applications very well, but this is quite a good example as batch updates are in general extremely complex to code and maintain using conventional technology. This difficulty arises from the fact that batch updates are simply not a good match with the von Neumann paradigm, but can be expressed very easily in terms of asynchronous processes communicating by means of streams of data.

Processes:
• R - reads a sequential file
• COL - "collates" two streams into one
• APPL - (subnet of) application logic
• W - writes a sequential file
• PR - prints a report

Streams:
• M - master records
• D - details
• C - collated stream
• M' - new masters
• R - report output

Any component in FBP can also be defined as a subnet of processes - a network with one or more "sticky" connections. FBP applications are usually built up using functional decomposition, so that a single diagram need not comprise more than an easily graspable number of processes. FBP is thus an excellent match with Structured Analysis, as the late Wayne Stevens pointed out in a number of publications (1982, 1985). In the above diagram, I have labelled the components and the streams - the other needed information is to identify the "ports" alluded to earlier. In earlier dialects of FBP, ports were identified using numbers. More recently we have moved to named ports, e.g. R's output port might be labelled OUT, and COL's input ports might be MAJOR and MINOR, say. We also need to identify the processes and which components (code) they are executing. In the notation of THREADS (a recent PC-based implementation of FBP), the front-end of the network could then be coded as follows:

Read-Masters(R) OUT -> MAJOR Collate(COL),
Read_Details(R) OUT -> MINOR Collate,
Collate OUT -> .....

Now that graphics hardware and software have become available at reasonable cost and performance, we would like to have graphical front-ends for our FBP systems. Since FBP is a highly visual notation, we believe that a graphical front-end will make it even more usable. Some prototype work has been done along these lines and seems to bear this idea out.

And now I would like to quote an unsolicited testimonial from a user of DFDM, one of the software systems which we have built based on these concepts (the PLI he refers to is IBM's PL/1 programming language, and "coroutines" is the DFDM term for "processes"):

"I have a requirement to merge 23 ... reports into one .... As all reports are of different length and block size this is more difficult in a conventional PLI environment. It would have required 1 day of work to write the program and 1 day to test it. Such a program would use repetitive code. While drinking coffee 1 morning I wrote a DFDM network to do this. It was complete before the coffee went cold [my italics]. Due to the length of time from training to programming it took 1 day to compile the code. Had it not been for the learning curve it could have been done in 5 minutes. During testing a small error was found which took 10 minutes to correct. As 3 off-the-shelf coroutines were used, PLI was not required. 2 co-routines were used once, and 1 was used 23 times. Had it not been for DFDM, I would have told the user that his requirement was not cost justified. It took more time to write this note than the DFDM network."

Rej's note was especially satisfying to us because he uses special equipment which converts whatever is on his screen into spoken words. Since FBP has always seemed to me a highly visual technique, I had worried about whether visually impaired programmers would have any trouble using it, and it was very reassuring to find that Rej was able to make such productive use of this technology.

I alluded earlier to FBP's power as a natural reuse vehicle - in my book I give some statistics on component reuse with DFDM in IBM Canada. I would like to give them here as I feel they are quite suggestive. The figures for three projects are shown in the following diagram (the numbers relate to components):
 

In this chart, "project" components are components coded specifically for the project in question, while "general purpose" means components that are off-the-shelf (already available and officially supported). "Unique" means separate components (separate pieces of code), while "occurrences" means total number of processes (component occurrences or network nodes). Thus project A used 154 distinct components, of which 21 came off the shelf, but accounted for 305 of the 489 processes (just over 3/5). GP/T means General Purpose as a fraction of Total, and it is interesting to compare the GP/T for unique components against the GP/T for component occurrences.

The "figure of merit" (FM) is calculated as follows: number of project-coded components divided by the total number of processes. Since the first figure represents the amount of work a programmer has to do (apart from hooking together the network), while the second figure represents the amount of work the program is doing, we felt that the figure of merit was quite a good measure of the amount of real reuse going on. DFDM had been in use about 2 to 3 years in our shop, and we had about 40 off-the-shelf components available, so quite a lot of the common tasks could be done without having to code up any new components. However, when the programmer did have to code up components, you will notice that quite often this code could also be reused, giving reuse factors greater than one (Project C had a factor of 27.0). In Project C, the programmer only had to write 2 new components, although there were 270 separate processes in his program. (You can probably figure out that this project involved running 27 different files through essentially the same 10 processes - so it did a lot of work, with very little investment of programmer effort!). Our experience is that, once the concepts are understood, FBP applications are extremely easy to maintain and extend.

Apart from FBP's ability to improve programmer productivity and system maintainability, it has particular relevance to parallel and distributed systems. Although they are somewhat outside my area of expertise, I think it is obvious that FBP applications would be extremely easy to distribute. In fact, when designing an FBP application we encourage the designer to draw it as "broadly" as is practical, and then subdivide it afterwards. An FBP network diagram can easily be split across multiple job steps by just replacing some connections with sequential files, so there is no point in subdividing it into job steps too early. As illustrated in the above example, files are usually written and read using general purpose, off-the-shelf components. Similar pairs of components could manage a communications line, or indeed any piece of I/O hardware. FBP seems to be highly complementary to IBM's MQSeries, which allows applications running on heterogeneous systems to communicate with each other, using basically the same shared queue concept. In MQSeries queues have to be named explicitly, but these queues could be managed using FBP, thus providing the necessary configurability, so we could use MQSeries at the coarser code level, and FBP at the finer level. FBP also seems a natural vehicle for building Client/Server systems, since every FBP process is a server to all of its upstream processes - the paradigm remains the same at the different levels.

On the subject of multiprocessor and multicomputer systems, I would like to quote a short passage from my book:

"A number of writers seem to favour multiprocessors (with shared memory) because they do not require us to radically change our approach to programming. The programming technique I have described in the foregoing pages seems to be a good match with this approach, as it can be mapped onto a multiprocessor in a straightforward manner: IPs are allocated from the shared memory, and FBP processes are spread across the available processors to obtain parallelism. All commercial multiprocessors provide concurrency control mechanisms such as semaphores; these can be used to manage the concurrent accesses to the IPs. Examples of this type of machine are the KSR 1, CEDAR, DASH, T*, Alewife - this list is from Bell (1992).

"FBP networks also have a natural mapping to multicomputers. Here parallelism is obtained by having a network of connected processors, each with its own memory. The data must be transmitted from one processor to another, as required, so communication speed and bandwidth become important considerations. Examples of this type of machine are the Intel Paragon, CM5, Mercury, nCube 2 and Teradata/NCR/AT&T systems. A number of different network topologies have been investigated - examples are meshes, tree structures, hypercubes, and ring structures.

"FBP could be mapped onto multicomputer systems by again evenly distributing the processes among the processors. An IP would be created in the local memory of the processor on which the creating process resides. If an IP had to be transferred to another processor, the entire IP could be copied over the communication network. Although this sounds inefficient, communication costs can be minimized by having 'neighbour' processes reside in directly connected processors, or even in some cases time-share the same processor, where the economics justify it. There is a considerable body of work on different strategies for handling communication between processors, and for doing the routing when paths are tied up or damaged, and I was struck by how similar some of the problems they have to solve are to those we had to solve for FBP....

"Most of the academic work with multiprocessor configurations seems to be oriented towards determining what parallelism can be obtained from a COBOL or FORTRAN program. However, MIT has a dataflow computer called Monsoon, which 'demonstrates scalability and implicit parallelism using a dataflow language' (Bell 1992), to be followed by one called T* which will be 'multithreaded to absorb network latency'. Researchers at Berkeley are using a 64-node CM5 to explore various programming models and languages including dataflow. ..... Here is a quote from an article (Cann 1992) comparing FORTRAN with functional languages [which I relate to FBP in my book] for programming tomorrow's massively parallel machines ...: 'Tomorrow's parallel machines will not only provide massive parallelism, but will present programmers with a combinatorial explosion of concerns and details. The imperative programming model will continue to hinder the exploitation of parallelism.'" He then goes on to list the advantages of functional languages compared with conventional procedural languages.

I can't leave this topic without mentioning another new paradigm, Object-Oriented Programming (usually abbreviated to OO). FBP may or may not be an OO system, depending on your definition of OO. However, it certainly bears a number of similarities to it, and especially to the more advanced OO concepts, specifically the concept of "active objects" (Ellis and Gibbs, writing in Kim and Lochovsky 1989). Since I wrote my book, there has been a distinct shift in the common use of the term "objects" to mean reusable components. Combined with configurable modularity, active objects and data streams basically add up to FBP, or something very similar to it. My reading of the literature has come up with quite a number of systems which have some subset of these features, and a few which seem to have almost all of them. Rob Strom's NIL (Strom 1983) and Yoshida and Chikayama's A'UM (Yoshida and Chikayama 1988) are particularly interesting examples.

Gelernter and Carriero's Linda is another close relative, and bears the same relationship to FBP as a bus does to a tram - FBP IPs go on "tracks", while Linda "tuples" float freely and can be retrieved associatively by any process which knows some identifying data. Just as in real life, there are well-defined roles for both modes, but it may be that FBP solves some of the performance problems with Linda that some writers have alluded to.

Up to now, I have concentrated on technology, and I confess to being technologically- oriented, so let's assume we have these details out of the way. However, we also have to look at the sociological and psychological factors. What will be needed to get this kind of technology into use in the workplace? Well, for one thing we are going to have to drastically change the way programming productivity is measured. Measurement in terms of KLOC is completely the wrong direction - as E. W. Dijkstra has pointed out, lines of code are a cost factor, not a measure of productivity! Programmers must be motivated to write reusable components which other programmers can use, perhaps by something like a royalty scheme. It is not good enough to simply reward programmers for writing reusable code, as some companies have started doing - rewards must be based on actual usage, which of course is harder to measure.

We are also going to need extensive cooperation between business and academia. As long as business and academia are two solitudes, staring at each other across a deep chasm of non-communication, we are not going to be able to make the transition to a new way of thinking. Business has obtained the impression that it has to become a bunch of mathematical geniuses to do the new programming, because the academics are broadcasting that image. At this point in time, business people are more willing to hire hundreds of COBOL programmers than to invest in new technologies, with the possible exception of OO, mostly because they prefer to stay with a sure thing, even though it's horrendously slow and clumsy.

But I am afraid academia is partly to blame as well. Many computer scientists are having fun creating new systems and languages, but they are somewhat out of touch with what millions of programmers struggle with day in, day out. Surely academics don't expect that business will all change from writing payroll programs in COBOL to using, say, Nassi- Shneiderman diagrams or Flat Guarded Horn Clauses. But each of the approaches being explored in isolation has some essential grains of truth in it, and, as I have tried to show in my book, I believe it really is possible to combine whatever is central to these concepts into something which will address the very serious problems facing the data processing industry today.

My hope is that FBP can act as a bridge between the two worlds of business and academia. My reading in the field suggests that FBP has sound theoretical foundations, and yet it can perform well enough that you can run a company on it, and it is accessible to trainee programmers (sometimes more easily than for experienced ones!). One of the most exciting things about FBP for me is that it provides a bridge between ideas that are currently restricted to very technical papers, and businesses which think they are stuck with COBOL assembly lines for ever. I and my colleagues over the years have had a glimpse of the future of the DP industry. I hope that it will not take another 25 years before we see this vision become a reality!

D. Cann, 1992, "Retire FORTRAN: A Debate Rekindled", Communications of the ACM, Vol. 35, No. 8, Aug. 1992

N.P. Edwards, 1974, "The Effect of Certain Modular Design Principles on Testability", IBM Research Report, RC 5060 (#22344), T.J. Watson Research Center, Yorktown Heights, NY, 9/30/74

D. Gelernter and N. Carriero, 1992, "Coordination Languages and their Significance", Communications of the ACM, Vol. 35, No. 2, February 1992

W. Kim and F.H. Lochovsky, 1989, "Object-Oriented Concepts, Databases, and Applications", ACM Press, Addison-Wesley

J.P. Morrison, 1978, "Data Stream Linkage Mechanism", IBM Systems Journal Vol. 17, No. 4, 1978

J.P. Morrison, 1994, "Flow-Based Programming: A New Approach to Application Development", Von Nostrand Reinhold, NY, 1994, ISBN 0-442-01771-5

W.P. Stevens, 1982, "How Data Flow can Improve Application Development Productivity", IBM System Journal, Vol. 21, No. 2, 1982

W.P. Stevens, 1985, "Using Data Flow for Application Development", Byte, June 1985

R.E. Strom and S. Yemini, 1983, "NIL: An Integrated Language and System for Distributed Computing", Proceedings of SIGPLAN '83 Symposium on Programming Language Issues in Software Systems, June 1983

L.G. Valiant, 1990, "A Bridging Model for Parallel Computation", Communications of the ACM, Aug. 1990, Vol. 33, No. 8

K. Yoshida and T. Chikayama, 1988, "A'UM, A Stream-Based Concurrent Object- Oriented Language", Proceedings of the International Conference on Fifth Generation Computer Systems, 1988, ed. ICOT