Free at last!

The punched-card was restrictive in many ways: there were only codes for letters, digits and a small collection of special characters. No provision was made for both upper and lower case letters and a very few codes were designated for control characters. Each of the computer manufacturers intro­duced their own version of the cards to accommodate their code needs. The American Standards Association’s (ASA) X3.2 subcommittee published the first version of the ASCII 8-bit code-set in 1963. The ASCII code-set was an 8-bit character encoding that eliminated most of the shortcomings of earlier code-sets. The ASA had created an earlier 7-bit code-set which included four separator codes. When IBM launched its System 360 it also introduced the EBCDIC encoding for punched-cards, which included the separator control codes introduced in the ASCII 7-bit code-set. In 1968 President Johnson mandated that all government computers would use ASCII, so IBM dropped their many-flavored EBCDIC and embraced the ASCII 8-bit code-set for System 370.

ASCII has since evolved to UTF-8, UTF-16 and UTF-32. Bigger and bigger code-sets that embrace all of mankind’s various alphabets and symbols. Code-sets went from 5-bits to 32-bits in 50 years. A 32-bit code-set allows for 4,294,967,296 different characters! (I don’t know anyone who uses UTF-32. Most programming is done using UTF-8.) The only reason that I even discuss this issue is because ASCII introduced the four very important control characters; the hierarchical separators. Quoting Wikipedia:

Data structuring. The separators (File, Group, Record, and Unit: FS, GS, RS and US: 1C, 1D, 1E and 1F, hexadecimal) were made to structure data, usually on a tape, in order to simulate punched cards. End of medium (EM) warns that the tape (or other recording medium) is end­ing. While many systems use CR/LF and TAB for structuring data, it is possible to encounter the separator control characters in data that needs to be structured. The separator control characters are not overloaded; there is no general use of them except to separate data into structured groupings. Their numeric values are contiguous with the space character (20 hexadecimal) which can be considered a member of the group, as a word separator.

I decided to use these separators to free IT records from their straight jackets. I devised a scheme for using these control characters to allow variable length fields and unrestrained nesting of dependent data. The paper that I wrote about my scheme may be found here (it was presented at the ACM SIC­FIDET Workshop in Houston Texas in 1970). Unfortunately, I have found it impossible to persuade anyone to employ this technique. I am aware of only two implementations of the use of these concepts. Both were in systems that I developed. (Yes – I’ve been worrying this problem for a long time.)

The tyranny of the punched-card

In the early eighteenth century, perforated paper rolls were used to control looms in France. Basile Bouchon and Jean-Baptiste Falcon introduced punched-cards as a more robust and reliable method of controlling the looms. At the start of the nineteenth century, Joseph Marie Jacquard adopted and adapted their ideas for his looms. In 1832, a Russian homeopath, Semen Korsakov, use punched-cards to store information. His primary interest was to store information and then to search for simi­larities. Korsakov also invented a number of devices for comparing the data in his punched-cards. Herman Hollerith developed a punched-card technology for the 1890 US Census. His company, the Tabulating Machine Company, started in 1896, later became IBM. James Powers, a former Census Bu­reau maintenance man for the Hollerith machines, introduced new devices that included a number of significant improvements. These new devices were marketed by Powers-Samas in Britain and France.

These first punched-cards were used primarily for storing data. Tabulators and sorters were used for accounting and conducting surveys. For IBM, punched-cards were to their equipment, what razor blades were to Gillette or Schick. In Endicott, NY, IBM printed, cut and stacked more than 5 million cards every day (generating a not-insignificant revenue—and their 'razors' were not inexpensive).

There are a fixed number of columns in a punched-card. Adjacent columns are assigned to fields; each field is assigned to different data in the database. A code, representing a letter, a number or a control, is punched into each column. The primary concept is that each card contain one record and that all the cards in a database have an identical layout. This was the first IT straight jacket. Every­thing needed to represent a single entity had to be contained in a single card (and later, in multiple cards)! Numerous clever schemes were invented to squeeze more data onto the cards. The first cards had quite a limited capacity, but over time the cards got bigger and bigger and the phrase 'Do not fold, spindle or mutilate,' became part of the modern psyche. When magnetic tape was introduced the size of the record went ballistic!

Instead of rethinking the way in which data was stored, magnetic tape simply became a collection of very big punched-cards; a larger straight jacket. More stuff could be squeezed into each record but it was simply a mindless extension of the punched-card. The programming language COBOL, that perpetuated this mistake, was developed. It was compatibility with the punched-card milieu that drove the effort. COBOL records were simply punched-card layouts that could become very complex. There were two major problems: the length of each field was fixed, and subordinate fields or groups of fields had to have a fixed number of occurrences. This resulted in some people’s long surnames being truncated, and employees who could have no more than, say eight, dependents. This also meant that a large number of columns in an individual record would go unused.

One of the major shortcomings of COBOL was that the external representation of the records was determined by the individual computer manufacturer. For example, IBM introduced slack bytes, a mechanism that ensured that the data would align itself correctly into their System 360 machine ar­chitecture. This meant that unused data would be inserted into records to avoid having to align the data with their word (32-bit) and double-word (64-bit) boundaries after reading it into memory. It also meant that another manufacturer could not read data written on an IBM computer without being cognizant of these slack bytes. Had the CODASYL committee explicitly controlled these external representations, it would have made it much easier to transfer data from one computer site to another.

Designing databases

Databases should be designed to model the real world. Most Relational Database Management Systems (RDBMS) database designs don't even follow the rudimentary dictates of proper normalization and many software packages allow databases with no referential integrity constraints to be built. If a datum exists only once in the real-world then that datum should only be represented once in a database. Regardless of how complex access to, or maintenance of that datum may become, only a single instance of the datum should exist in the database! (Access to, and maintenance of the datum will actually become simpler.)

The shortcomings of RDBMSs and how they are being implemented are presently being explored by Date and Darwen in The Third Manifesto, and by Terry Halpin who takes a different approach to database modeling with his Object Role Modeling. Once again I will quote from George Santayana who has said, “Those who do not learn from history are doomed to repeat it.” Indeed, it really is history that has hobbled database design. Some of this history will be discussed and the considerations that result in the modeling of the real world, without altering it, will be dealt with.

Two more tales

The COBOL compiler mystery

A major computer manufacturer invited me to present my decision table methodology to their software developers. After the presentation a group asked if I would demonstrate how it worked by looking at a very specific problem. They explained that there was a persistent problem in their COBOL compiler. I agreed to try to solve the problem.

We spent a few days constructing decision tables from the language specification. While constructing one of the tables, two groups of programmers disagreed about how a particular part of the specification should be interpreted. Each group had a different understanding of the intent of the specification.

I mediated the lengthy discussion that ensued. It was obvious that this ambiguity was the source of their problem. We looked at the pros and cons of each interpretation and then voted on which one to adopt. Once this decision had been made, the group, who had had the counter-interpretation, went back to their offices and rewrote their code. The rebuilt compiler no longer had the problem. (This all happened a few years after the compiler had been released to customers.)

The Jims and their epiphanies

Two colleagues, both named Jim, and I were working on a new file storage mechanism for a mainframe computer. (Our goal was to pack and unpack data into strings of contiguous bits. The target was to gain at least a tenfold increase in data density without incurring a large penalty in access speed.) Neither Jim was interested in using decision tables. They estimated that the task could be accomplished in about two weeks.

While they coded their solution I drew the decision tables and prepared a test with which to test their code. About 10 days later they claimed that the code was ready to be tested. I tested their pro­gram using the test I'd prepared and it failed in many different ways. I showed them exactly where it was failing. They felt that they could take care of the problems in a couple of days. A week later the code was still failing a number of tests. At this point I shared the decision tables with them, explained how they worked, and we coded the solution from the decision tables. The resulting code was much smaller than their original code and worked correctly for all the test cases.

All three of us left the company within the next three months. One of the Jims repaired to California to work on flat-bed plotters; the other went to the NIH to work with lab-computers; and I went to Minnesota to work on machine-independent operating systems.

The California Jim called me late one evening about six months later. He had been wrestling with a particularly difficult problem. Out of frustration he decided to try a decision table. His experience convinced him that decision tables really worked. He became a decision tables devotee and has used them ever since.

The other Jim called me a few months after his namesake. He told me about the problem he had been having interfacing a lab instrument to a computer, and how he had solved his problem by us­ing a decision table. He too became a decision table devotee.

Neither of my friends, both very capable programmers, had liked the idea of using decision tables to solve programming problems. After the two incidents described above both started using decision tables in most of their work.

Video Presentation

I have prepared a YouTube presentation entitled 'A Disciplined Approach to Solving Problems' that walks through a theoretical problem space and then through a real problem space. This is available here. It is easy to follow and, should you care to view it, I urge you to persist and watch all four parts.

Serendipitous trip to Ann Arbor

I wrote a paper about my database management concepts which I presented in Ann Arbor, Michi­gan, at the ACM SIGMOD Workshop on Data Description, Access and Control. It was May of 1974 and I had just left CDC and was looking for a new home. In my briefcase I had a handwritten paper describing my decision table methodology.

On the morning after I made my presentation I had breakfast with Jane Jodeit (from Software AG) and Jonas Rabin (from Western Electric). Jane told us something about ADABAS, the product she was supporting in the USA, and Jonas told us about his work with the Decision Table Task Group (DTTG) of CODASYL. I had the handwritten working paper about my decision table methodology copied and gave each of them a copy.

Jane asked if I would be available to meet her CEO, John Maguire, to whom she had spoken earlier that morning. At her behest he had agreed to fly to Ann Arbor to meet me. I met him that afternoon and by the end of the day was an employee of Software AG.

Several months later I received a phone call from Jonas Rabin. He invited me to present the paper, I’d given him a copy of in Ann Arbor, to the DTTG in Chicago the fol­lowing day. I flew to Chicago, met the DTTG members, and presented my paper. They asked if I would be interested in becoming a member of the task group. I accepted their invitation and stayed in Chicago for the rest of that week.

There were about 20 people in the DTTG. They were divided into smaller groups each charged with the responsibility of dealing with a particular task. I was assigned to the group that was writing about development methodology.

I hosted a meeting for the DTTG in Saint Paul a few years later. Each sub-group made presentations to the entire DTTG. This was the first time that I heard how decision tables were going to be de­scribed mathematically. The description lacked substance and was full of holes. I was probably the most vocal critic and felt a little uncomfortable.

When our meeting ended, one of the members, Lewis Reinwald, had to wait for his daughter to ar­rive. She was going to drive him back to Washington, DC. He and I sat on a terrace discussing some of the issues that had been raised. He mentioned the way I had torn the mathematics apart and asked how I would characterize decision tables mathematically. I scribbled some of my ideas on pa­per napkins as we explored the possibilities. A set-theoretic approach seemed the best to me. I fleshed out some of my ideas about being able to prove completeness, and the consequent affect it would have on testing. Many beers and hours later Lewis’s daughter arrived. He asked me to gather up the paper napkins and put them into some sort of order, and took the bundle with him to Wash­ington.

About 6 weeks later I received a parcel from Lewis. He requested that I review the document he had enclosed and asked if this is what I had had in mind. I was amazed, he had threshed out a very meaningful description of decision tables along the lines of our discussion. I made a few changes and suggested that we send it to all the DTTG members as a proposed formal characterization of de­cision tables. At our next meeting the DTTG adopted our proposal. The CODASYL Report, entitled A Modern Appraisal of Decision Tables, was published by the ACM in 1982.

Lewis had developed some very interesting ways of extending decision tables which didn’t fit my model. He called me a purist when I couldn’t fit his extensions into the model. We never did re­solve this difference.

The methodology works!

Years earlier, while working in a group dedicated to unraveling the complexities of operating sys­tems, I had worked with Henry Stambler, a former IBM-er who had been recruited by CDC. Henry was intrigued by my database management concepts.

In 1967, CDC had provided the hardware for a very innovative project at Case Western Reserve University; Dr. Larry Weed’s Problem Oriented Medical Information Systems (PROMIS) project. They were using touch screen terminals (Digis­cribe) to enter and retrieve medical records at patients’ bedsides. The PROMIS project moved, lock, stock and barrel, to the University of Vermont in Burlington, Vermont in 1969. Henry Stambler left CDC a few years later and joined the PROMIS project, where he designed their file system. The history of PROMIS is available here.

Henry Stambler persuaded the PROMIS project management to invite me in to tell them about my database management concepts. I went to visit the project for a couple of weeks. They liked my con­cepts and invited me to join them.

While I was in Vermont I also made some presentations on my problem-solving methodology. Every­one on the project attended. The software people rejected the ideas out of hand, they felt they didn’t need that sort of mothering. Ironically, it was the hardware engineers that wanted to try it. So I spent a few days with them using decision tables to solve some hardware design problems. They took to the methodology like the proverbial ducks to water.

The software group had been working together for some years and had a huge investment in their solution. I realized that changing horses in this rapidly moving stream wouldn’t work, so I thanked them for the offer to join them but did not accept the offer. (I went home to Minnesota with a huge jug of maple syrup.)

Somewhere along the line the hardware engineers must have per­suaded the software people to try decision tables. From page 32 of the history referenced above:

…Henry Beitz, a CDC consultant, convinced us that an unlimited entry decision table could be used as the basis for demonstrating an understanding of a problem and also as the funda­mental design document. Decision tables were used to design and test the interface among hardware and software modules.

The run-time environment developed to support PPL (described in the next section) was de­fined in 17 decision tables and 78 rules. The definition of the polled multi-drop protocol to connect the high-speed terminals to the CPU was a set of 12 decision tables with a total of 77 rules. The protocol was used by Varian Data Machines, by MEGADATA, and by PROMIS Labo­ratory. When the hardware was delivered and the terminals were connected, the system operated correctly the first time it was tried (my emphasis).

The report referenced above was written nearly 10 years after my visit to the PROMIS project. I had no idea that the software group had embraced decision tables so enthusiastically.

Putting the methodology’s feet to the fire

In 1972 I moved from the Advanced Research Laboratory, where CDC was developing the STAR-100 system, to the Scope Operating System group at CDC’s Arden Hills plant in Saint Paul. CDC wanted me to manage a group implementing part of their new operating system. Ray Nienberg, the General Manager, was willing to let me try my methods on one of the modules. They chose something that wasn’t really essential but that would be nice to have: a deadlock-preventing resource scheduler which would ensure that all jobs submitted for execution would run to completion without any re­source deadlocks. The new operating system was to be released to users in 10 months.

I explained to the people in my group how we were going to implement our module. An analysis of precedent revealed that the problem had already been solved. Edsger Dijkstra called it the banker’s algorithm, and Wikipedia deals with it here. Not being one to reinvent the wheel, I simply imple­mented the banker’s algorithm for our operating environment resources. Decision tables were used to ensure that our implementation was robust.

Our group did not use one second of computer time during the first 6 months. We constructed and reviewed decision tables, refining them as we went. When we felt that all the rules (the meaningful combinations of alternatives of all the variables) had been dealt with we created an exhaustive test­ing mechanism to test our implementation. This suite of tests served as a regression test ensuring that when we fixed programming errors we didn’t break anything that had previously worked. The tests were designed to run until an expected outcome didn’t match a program outcome. If this hap­pened we stopped the computer immediately and dumped out a complete map of the memory of the program. Each test situation was constructed mechanically from the decision tables. The tests were exhaustive and tested every possible situation. Remember, we were running on what was then the world’s fastest computer, the CDC 7600 (since we didn’t use any floating point arithmetic we must have been running even faster than its 36 MFLOP capability). When completed, the entire test, which included thousands of rules, took less than 1 second to execute.

We turned our module over to Integration and Evaluation on the day we got right through to the end of the testing sequence. We had completed our task within 8 months, and were one of the few groups ready to release their module by the release date. Integration and Evaluation declared our module ready for release after a couple of weeks of testing. I asked to see the test that Integration and Evaluation had used to test our module. They had used a dedicated super-computer for 300 minutes to test our module. On examination we found that they had tested some situations hun­dreds of millions of times while many situations had not been tested at all. We walked them through our tables and our testing procedure, and they got very excited. They realized the value of what we were doing and immediately wanted to use a similar methodology for all testing. They weren’t able to sell it to project management.

After reviewing the progress of the entire project the company management decided to slip the re­lease date by 3 months. By now everyone in our group had a very good feel for our solution. We re­visited our tables and decided how we could change things. After we had discussed the improve­ments for a few weeks we went ahead, altered the tables, revised the tests, and implemented the im­provements.

The most costly aspect of maintaining a complex system is support. Fixing the bugs and releasing them to the users is very expensive. Monthly meetings were held to see how the new operating sys­tem was doing following its release. Every module would have an outstanding number of known bugs. On average there would be about 20 bugs per module. The support programmers would fix them at about the same rate, but the number of outstanding bugs didn’t appear to go down. New bugs were being created at about the same rate as old ones were fixed. Our module was the exception; a couple of bugs were reported in the first two months and then the module remained stable for the life of that version of the operating system (a number of years). My group was disbanded and all its members were reassigned to other projects. The maintenance of our module was assigned to another support group. There was virtually no cost attributable to maintaining our deadlock-preventing resource scheduler for the life of the operating system.

Problem Solving

The solutions to complex problems are seldom robust. What exactly do I mean by that? Simply that the solutions are incomplete; there are no planned actions for many of the situations that may arise. Some errors are simply that – errors. Most errors are errors of omission. One source of unanticipated errors is a difference in the interpretation of the requirements and another is an inconsistency in the implementation of the solution. To solve complex problems, methodical methods for exhaustively enumerating all the possible situations that may arise, are needed.

The problem space, i. e. the combination of every possible alternative for every variable that describes a possible or impossible situation with respect to the problem, needs to be defined. All erro­neous and impossible situations must be identified and each must be handled as explicitly as any other situation. A seemingly ridiculous goal since a very large number of situations may be identi­fied. Fortunately, decision table can be shown to represent such problem spaces succinctly. Decision tables are useful for solving all kinds of problems, not just those related to computer programming.

The origins of the decision table

Some form of decision table was first tried in the 1950s. But like flow-charts, they were simply a crutch that enabled early programmers to get some idea of how they were going to program the solu­tion to a problem. Early decision tables were neither complete nor robust.

In the early 1970s IBM started using DECTAT, a decision table translator for PL/1 and COBOL. I couldn’t find anything in the tool that enforced completeness. None of the tables, that I looked at in IBM's docu­mentation, was complete. (The reference manual is available from Google Books – AF37765).

In 1964 the late Tom Rozwadowski and I set out to solve a very complex problem. We had worked together as a team for 5 years; first at LEO Computers and then at Control Data Corporation (CDC). The task was to write drivers for some very special devices that our customer wanted to connect to a computer system that we had never seen. Although we were employed by the company that made the computer it was impossible to get any documentation about how to interface hardware to the system. In frustration we decided to analyze how all the interfaces, for external devices connected to the computer system, were programmed.

A few years earlier Tom and I had made a proposal to a government for the implementation of a na­tional population register. We had used tables to analyze the requirements. We realized that similar tables, with a few extensions, would make it possible to analyze the device drivers in the new com­puter's operating system. By the time the hardware was delivered our drivers were ready. We in­stalled our drivers, connected all the devices to the computer system, and tested the devices. All the devices operated correctly and we were able to control the devices using our installed drivers. The methodology proved to be very robust and we both continued using it from that time forward.

Neither of us was able to convince any of our colleagues to use our methods. We read everything we could find about decision tables but found that none of the methods were robust. We had planned to formalize the whole concept together but this wasn’t to be (Tom and his family died in a tragic acci­dent in October 1970). How I completed this task will be revealed later.