INTRODUCTION
PORTABILITY AS AN EDUCATION ISSUE
MACHINE DEPENDENCE AND INDEPENDENCE AS AN EDUCATION
ISSUE
THE DINING PHILOSOPHERS
THE PORTABLE DINERS
ENCAPSULATING MACHINE DEPENDENCIES
PORTABILITY TESTS
DISCUSSION
UPDATE
REFERENCES
One of the most important advantages of Ada is its strong standard, which governs the entire language including modularization (package) and concurrency (task) constructs. This project demonstrates that sophisticated Ada programs, using a number of packages and tasks, can be written, without much difficulty, to be entirely portable.
The base version of Portable Diners has been compiled without error and executed successfully using nearly thirty different Ada compilers, from most major compiler vendors, running on computers ranging from the IBM PC and Apple Macintosh through several families of VMS and Unix workstations, to IBM and Cray mainframes.
An interesting aspect of the portability tests is the use of the Internet to carry them out. The Ada source modules for Portable Diners were posted to an Internet newsgroup (comp.lang.ada), then copied from the network by Ada users around the world and tested with the compilers they had available.
Many real-world programs depend to a certain extent on machine-dependent characteristics such as the capabilities of the display device. Only the machine-independent parts are therefore portable. Good system design dictates that machine-dependent information be separated and encapsulated.
To illustrate the importance of separating machine-dependent from machine-independent parts of a program, we have developed several versions of Portable Diners. These differ only in the style of animation, which is governed by the kind of graphics display.
Current animation styles include line-by-line output (completely portable), very simple window-oriented animation (requiring a 24 x 80 ANSI terminal), and IBM PC color (requiring a compiler-specific graphics library). Creating a new version requires modifying only a single package body embodying the display instructions.
The formal education of students in the computing disciplines should include some exposure to the benefits of language and system standards; it is an aspect of professionalism. A language standard, together with a validation process that assesses a compiler's conformance to that standard, makes it possible to develop programs that can be moved from today's hardware to tomorrow's without major coding changes. More immediately, a language standard encourages the existence of multiple compilers for a single computer system, each compiler having its strengths, e.g., in compilation vs. runtime efficiency, or user-friendliness vs. code optimization, but all compilers accepting the same language.
Ada is an especially good case in point, because its government sponsors mandated a standard [DoD 83, Nyberg 89] that governs the entire language, including features for modularization and configuration management (packages) and concurrent programming (tasks). The government also sponsors a validation process in which a compiler is tested, using a publicly available suite of several thousand programs, for conformance to the standard. Subsets and supersets are not allowed. It is not forbidden to market a non-conforming compiler--the government allowed its trademark to lapse in 1988--but only a conforming compiler can be advertised as "validated" and used for government work. To our knowledge, no non-conforming compilers are currently on the market.
The strong Ada standard and the validation process have spawned an industry of more than thirty compiler vendors, with perhaps a dozen major players. More than 300 compiler/computer pairs--a pair is a given vendor's product running on a given machine--are currently validated. A Sun-3 or VAX/VMS installation can choose from around ten distinct compilers each; five companies market MS-DOS-family compilers. An academic computer laboratory can therefore, without too much difficulty or financial hardship, create an environment with several compilers, in which students can be taught the benefits of portability. (A very useful counterexample is the difficulty experienced in moving a non-trivial Pascal program from, say, Borland's compiler to Microsoft's, or from MS-DOS to UNIX.)
Students should be exposed to the issue of localizing machine dependencies, as part of their general study of abstraction mechanisms and good design.
Figure 1 shows the situation in the dining room, with well-known modern philosophers at the table (apologies for the poor resemblance of the caricatures to their namesakes). Dijkstra's right chopstick is #1; the chopsticks are numbered clockwise around the table.
The diners must cooperate to remain alive. Each right stick is someone else's left one, so if each philosopher first acquires his or her right chopstick, holding it greedily until (s)he can acquire the other chopstick, all philosophers will starve. This is a classical circular-wait deadlock.
Many programs demonstrating the diners have allowed the philosopher processes to communicate with the world outside the room (via display statements). This is an incorrect implementation of the situation: The diners should concentrate only on eating and thinking. To allow an outside observer to follow the action, however, we compromise and permit philosophers to communicate their state via messages to a head waiter task. The head waiter serves as the interface between the dining room and the outside world; its job is not only to assign chopsticks but also to serve as a play-by-play announcer, interpreting the goings-on to the audience.
Figure 2 gives the system structure for Portable Diners. Each rectangular box represents a library package; the arrows show the import structure, e.g., Main imports Room, which in turn imports Philosophers, Chopsticks, and Text_IO (Ada's standard input/outpt library). Note that Philosophers and Room are mutually importing. This is allowable but a bit subtle to implement. A philosopher is assigned chopsticks by the head waiter.
The main program's only function is to bring the head waiter to life, then wait until the program is terminated. The head waiter creates the dining room and brings the philosophers to life, one by one, deciding whether each philosopher will grab the left or right stick first.
Figure 4 shows a few lines of the scrolling output produced by the head waiter. Stroustrup is the non-conformist, having been instructed by the head waiter to choose his left chopstick (#1) before his right one (#5).
This implementation of Dining Philosophers is believed to be entirely
portable and will produce similar output regardless of the compiler, computer,
or display used; our portability tests are discussed below.
Room.Head_Waiter. Report_State(Who_Am_I, Breathing); LOOP Room.Sticks(First_Grab).Pick_Up; Room.Head_Waiter.Report_State (Who_Am_I, Got_One_Stick, First_Grab); Room.Sticks(Second_Grab).Pick_Up; Room.Head_Waiter.Report_State (Who_Am_I, Got_Other_Stick, Second_Grab); Meal_Time := Random.Random_Int(10); Room.Head_Waiter.Report_State (Who_Am_I, Eating, Meal_Time); DELAY Duration(Meal_Time); Room.Head_Waiter.Report_State (Who_Am_I, Done_Eating); Room.Sticks(First_Grab).Put_Down; Room.Sticks(Second_Grab).Put_Down; Think_Time := Random.Random_Int(10); Room.Head_Waiter.Report_State (Who_Am_I, Thinking, Think_Time); DELAY Duration(Think_Time); END LOOP;
T= 21 Eddy Dijkstra Thinking 7 seconds. T= 21 Moti Ben-Ari First chopstick 2 T= 21 Bjarne Stroustrup Second chopstick 5 T= 21 Bjarne Stroustrup Eating 6 seconds. T= 23 Barb Liskov Yum-yum (burp) T= 23 Moti Ben-Ari Second chopstick 3 T= 23 Barb Liskov Thinking 6 seconds. T= 23 Jean Ichbiah First chopstick 4 T= 23 Moti Ben-Ari Eating 4 seconds. T= 27 Bjarne Stroustrup Yum-yum (burp) T= 27 Bjarne Stroustrup Thinking 1 seconds. T= 27 Jean Ichbiah Second chopstick 5 T= 27 Jean Ichbiah Eating 5 seconds. T= 27 Moti Ben-Ari Yum-yum (burp) T= 27 Moti Ben-Ari Thinking 10 seconds. T= 28 Eddy Dijkstra First chopstick 1 T= 28 Eddy Dijkstra Second chopstick 2 T= 28 Eddy Dijkstra Eating 9 seconds. T= 29 Barb Liskov First chopstick 3 T= 32 Jean Ichbiah Yum-yum (burp) T= 32 Barb Liskov Second chopstick 4 T= 32 Jean Ichbiah Thinking 1 seconds.
Figure 5 shows the relevant part of the new system structure.These packages are written in pure, portable Ada, but programs using them display output correctly only on an appropriate terminal. Only the body of the Room package requires modification to produce this version; the rest of the system is entirely unchanged and does not even need to be recompiled. Given Ada's standard library management facility, and assuming that Screen and Windows are already compiled into the library system, the new version is produced simply by compiling the new body of Room and relinking the system.
Figure 6 shows a snapshot of the screen output during a run of this version. The action is more heavily animated; each philosopher's state is displayed in a separate window, and the screen resembles the table in Figure 1.
During the testing, only one significant change was necessary to get the program to execute correctly on all systems, namely the use of a compiler directive (pragma, in Ada terminology) to force a compiler-independent elaboration order on the two mutually-importing packages. The only unsuccessful test was carried out on a particular IBM-PC family compiler, which generated executable code that "hung" the computer. The test exposed a bug in the compiler's memory allocation scheme.
To broaden the scope of the portability tests, we posted a file containing the Portable Diners source code to the Ada newsgroup on the Internet, requesting that readers test the program on their favorite compilers and report back by electronic mail. Some thirty responses were received from academic and industrial sites in North America and Europe; adjusting for multiple respondents using the same compiler, fifteen more compiler/computer pairs could be added to the list of successful tests of either the window or line version.
The list of successful tests, by compiler vendor, is given below. The twelve companies in question represent most of the major Ada suppliers, especially suppliers of compilers to the academic world.
Portable Diners is also a fairly small program. The line-oriented version, consisting of Main and the packages Room, Chopsticks, and Philosophers, is about 100 statements long, not including 40 statements of general-purpose packages for input/output instantiation and random-number generation, because these packages can be assumed to have been pre-compiled into the library.
The window-oriented version is only about 20 statements (40 lines) longer; the difference is in the more elaborate head waiter task. We do not count the packages Screen (25 statements) and Windows (150 statements), again because these are general-purpose packages assumed to be in the library already.
The entire system, including the reusable packages, is available from the author by Internet mail or on diskette. The system is included in the government-sponsored Ada Software Repository, and has already received wide Internet distribution. Several compiler vendors are considering it for inclusion in their demonstration libraries.
That such an interesting program can be written so portably and compactly is a commentary on the power of using reusable, pre-compiled components, and also on the benefit of including concurrent-programming constructs in the programming language. Exposure of students to programs like this is a valuable part of their educational experience.
Much information on Ada and Ada 95 is available on the World Wide Web, starting from Ada Resources for Educators and Students