Date: Mon, 18 Oct 1999 12:02:11 +0300
From: Diomidis Spinellis <dds@sena.gr>
Subject: Complexity in operating systems and programming languages

A number of contributors to previous digests have stressed the risks
associated with increasingly bloated software applications.  Unfortunately
the same issues permeate a number of facets of the software industry.
Consider operating systems and programming languages which are becoming
increasingly complicated and their implementations less trustworthy.  The
following table [1] contains the number of documented system calls for some
popular Un*x system versions:

Operating System	Year	Number of 
		            	system calls 
First Edition Unix	1971	 33 
Seventh Edition Unix	1979	 47 
SunOS 4.1		1989	171 
4.3 BSD Net 2		1991	136 
HP-UX 9.05		1992	219 
SunOS 5.4		1994	163 
Linux 1.2		1996	211 
SunOS 5.6		1997	190 
Linux 2.0		1998	229

The Windows platform with 3433 API calls (up to NT4 SP3) belongs to a
different league; the associated problems are documented elsewhere [2].
A system call defines an interface to the operating system; more system
calls increase the complexity of the operating system needed to support
them, provide additional opportunities for unwanted interactions between
them, and increase the chances of overlooked security loopholes. 

This increasing complexity has important implications for the reliability of
software developed for a specific platform. Complicated interfaces are
difficult to learn and use effectively. As a result of their size and
complexity, modern operating systems exhibit an increasing number of bugs;
demonstrated by the numerous "fixes" distributed by their vendors.
Developers of robust applications have to take this into account coding
around them, or insist on the installation of all relevant fixes.  Some
fixes may introduce new errors or render other system components
inoperative. The bottom-line of this situation is, that the application
developer is practically rarely singly responsible for the reliability of an
application.

Similarly to operating systems, programming languages also have a tendency
to grow in size and complexity as they mature. Taking as a rough measure the
page number of the language's canonical description the following table
provides an illustration of the evolution of the C and C++ programming
languages:

Book Title						Year	Pages
The C Programming Language (Kernighan and Ritchie)	1978	228 
The C Programming Language; second edition		1988	272 
The C++ Programming Language (Stroustrup)		1986	328 
The C++ Programming Language; second edition 		1991	669 
The C++ Programming Language; third edition 		1997	910

This trend has important implications for the developers of high-reliability
systems. Large languages are difficult to learn and use [3]. It is nowadays
not uncommon for programming teams to lack people who understand the whole
language at a level sufficient to advise other members on issues regarding
the interrelationship between language elements. Subtle bugs arising from
the misunderstanding of language features can thus survive code
walkthroughs. In addition, language complexity and advanced optimisation
techniques combined with processor complexity results in an increased number
of bugs in modern compilers.  This is clearly an additional risk factor for
high-reliability designs.

[1] Diomidis Spinellis. Software reliability: Modern challenges. In G.
I. Schueller and P. Kafka, editors, Proceedings ESREL '99 - The Tenth
European Conference on Safety and Reliability, pages 589-592,
Munich-Garching, Germany, September 1999. ESRA, VDI, TUM, A. A. Balkema.
http://kerkis.math.aegean.gr/~dspin/pubs/conf/1999-ESREL-SoftRel/html/chal.html
[2] Diomidis Spinellis. A critique of the Windows application
programming interface. Computer Standards & Interfaces, 20:1-8, November
1998.
http://kerkis.math.aegean.gr/~dspin/pubs/jrnl/1997-CSI-WinApi/html/win.html
[3] C. A. R. Hoare. Hints on programming language design. In Ellis
Horowitz, editor, Programming Languages: A Grand Tour, pages 31-40.
Computer Science Press, 1983. Reprinted from Sigact/Sigplan Symposium on
Principles of Programming Languages, October 1973.

Diomidis Spinellis, University of the Aegean