Total Pageviews

Saturday, August 13, 2011

Programming languages


Machine language
One implication of the stored-program model was that programs could read and operate on other programs as data; that is, they would be capable of self-modification. Konrad Zuse had looked upon this possibility as “making a contract with the Devil” because of the potential for abuse, and he had chosen not to implement it in his machines. But self-modification was essential for achieving a true general-purpose machine.
One of the very first employments of self-modification was for computer language translation, “language” here referring to the instructions that make the machine work. Although the earliest machines worked by flipping switches, the stored-program machines were driven by stored coded instructions, and the conventions for encoding these instructions were referred to as the machine's language.
Writing programs for early computers meant using the machine's language. The form of a particular machine's language is dictated by its physical and logical structure. For example, if the machine uses registers to store intermediate results of calculations, there must be instructions for moving data between such registers.
The vocabulary and rules of syntax of machine language tend to be highly detailed and very far from the natural or mathematical language in which problems are normally formulated. The desirability of automating the translation of problems into machine language was immediately evident to users, who either had to become computer experts and programmers themselves in order to use the machines or had to rely on experts and programmers who might not fully understand the problems they were translating.
Automatic translation from pure mathematics or some other “high-level language” to machine language was therefore necessary before computers would be useful to a broader class of users. As early as the 1830s, Charles Babbage and Lady Lovelace had recognized that such translation could be done by machine (see the earlier section Lady Lovelace, the first programmer), but they made no attempt to follow up on this idea and simply wrote their programs in machine language.
Howard Aiken, working in the 1930s, also saw the virtue of automated translation from a high-level language to machine language. Aiken proposed a coding machine that would be dedicated to this task, accepting high-level programs and producing the actual machine-language instructions that the computer would process.
But a separate machine was not actually necessary. The IAS model guaranteed that the stored-program computer would have the power to serve as its own coding machine. The translator program, written in machine language and running on the computer, would be fed the target program as data, and it would output machine-language instructions. This plan was altogether feasible, but the cost of the machines was so great that it was not seen as cost-effective to use them for anything that a human could do—including program translation.
Two forces, in fact, argued against the early development of high-level computer languages. One was skepticism that anyone outside the “priesthood” of computer operators could or would use computers directly. Consequently, early computer makers saw no need to make them more accessible to people who would not use them anyway. A second reason was efficiency. Any translation process would necessarily add to the computing time necessary to solve a problem, and mathematicians and operators were far cheaper by the hour than computers.
Programmers did, though, come up with specialized high-level languages, or HLLs, for computer instruction—even without automatic translators to turn their programs into machine language. They simply did the translation by hand. They did this because casting problems in an intermediate programming language, somewhere between mathematics and the highly detailed language of the machine, had the advantage of making it easier to understand the program's logical structure and to correct, or debug, any defects in the program.
The early HLLs thus were all paper-and-pencil methods of recasting problems in an intermediate form that made it easier to write code for a machine. Herman Goldstine, with contributions from his wife, Adele Goldstine, and from John von Neumann, created a graphical representation of this process: flow diagrams. Although the diagrams were only a notational device, they were widely circulated and had great influence, evolving into what are known today as flowcharts.
 
Zuse's Plankalkül
Konrad Zuse developed the first real programming language, Plankalkül (“Plan Calculus”), in 1944–45. Zuse's language allowed for the creation of procedures (also called routines or subroutines; stored chunks of code that could be invoked repeatedly to perform routine operations such as taking a square root) and structured data (such as a record in a database, with a mixture of alphabetic and numeric data representing, for instance, name, address, and birth date). In addition, it provided conditional statements that could modify program execution, as well as repeat, or loop, statements that would cause a marked block of statements or a subroutine to be repeated a specified number of times or for as long as some condition held.
Zuse knew that computers could do more than arithmetic, but he was aware of the propensity of anyone introduced to them to view them as nothing more than calculators. So he took pains to demonstrate nonnumeric solutions with Plankalkül. He wrote programs to check the syntactical correctness of Boolean expressions (an application in logic and text handling) and even to check chess moves.
Unlike flowcharts, Zuse's program was no intermediate language intended for pencil-and-paper translation by mathematicians. It was deliberately intended for machine translation, and Zuse did some work toward implementing a translator for Plankalkül. He did not get very far, however; he had to disassemble his machine near the end of the war and was not able to put it back together and work on it for several years. Unfortunately, his language and his work, which were roughly a dozen years ahead of their time, were not generally known outside Germany.
 
Interpreters
HLL coding was attempted right from the start of the stored-program era in the late 1940s. Shortcode, or short-order code, was the first such language actually implemented. Suggested by John Mauchly in 1949, it was implemented by William Schmitt for the BINAC computer in that year and for UNIVAC in 1950. Shortcode went through multiple steps: first it converted the alphabetic statements of the language to numeric codes, and then it translated these numeric codes into machine language. It was an interpreter, meaning that it translated HLL statements and executed, or performed, them one at a time—a slow process. Because of their slow execution, interpreters are now rarely used outside of program development, where they may help a programmer to locate errors quickly.
 
Compilers
An alternative to this approach is what is now known as compilation. In compilation, the entire HLL program is converted to machine language and stored for later execution. Although translation may take many hours or even days, once the translated program is stored, it can be recalled anytime in the form of a fast-executing machine-language program.
In 1952 Heinz Rutishauser, who had worked with Zuse on his computers after the war, wrote an influential paper, Automatische Rechenplanfertigung bei programmgesteuerten Rechenmaschinen (loosely translatable as “Computer Automated Conversion of Code to Machine Language”), in which he laid down the foundations of compiler construction and described two proposed compilers. Rutishauser was later involved in creating one of the most carefully defined programming languages of this early era, ALGOL. (See next section, FORTRAN, COBOL, and ALGOL.)
Then, in September 1952, Alick Glennie, a student at the University of Manchester, England, created the first of several programs called Autocode for the Manchester Mark I. Autocode was the first compiler actually to be implemented. (The language that it compiled was called by the same name.) Glennie's compiler had little influence, however. When J. Halcombe Laning created a compiler for the Whirlwind computer at the Massachusetts Institute of Technology (MIT) two years later, he met with similar lack of interest. Both compilers had the fatal drawback of producing code that ran slower (10 times slower, in the case of Laning's) than code handwritten in machine language.
FORTRAN, COBOL, and ALGOL
Grace Murray Hopper
  • Grace Murray Hopper at the UNIVAC keyboard, c. 1960.
While the high cost of computer resources placed a premium on fast hand-coded machine-language programs, one individual worked tirelessly to promote high-level programming languages and their associated compilers. Grace Murray Hopper taught mathematics at Vassar College, Poughkeepsie, New York, from 1931 to 1943 before joining the U.S. Naval Reserve. In 1944 she was assigned to the Bureau of Ordnance Computation Project at Harvard University, where she programmed the Mark I under the direction of Howard Aiken. After World War II she joined J. Presper Eckert, Jr., and John Mauchly at their new company and, among other things, wrote compiler software for the BINAC and UNIVAC systems. Throughout the 1950s Hopper campaigned earnestly for high-level languages across the United States, and through her public appearances she helped to remove resistance to the idea. Such urging found a receptive audience at IBM, where the management wanted to add computers to the company's successful line of business machines.
 
IBM develops FORTRAN
In the early 1950s John Backus convinced his managers at IBM to let him put together a team to design a language and write a compiler for it. He had a machine in mind: the IBM 704, which had built-in floating-point math operations. That the 704 used floating-point representation made it especially useful for scientific work, and Backus believed that a scientifically oriented programming language would make the machine even more attractive. Still, he understood the resistance to anything that slowed a machine down, and he set out to produce a language and a compiler that would produce code that ran virtually as fast as hand-coded machine language—and at the same time made the program-writing process a lot easier.
By 1954 Backus and a team of programmers had designed the language, which they called FORTRAN (Formula Translation). Programs written in FORTRAN looked a lot more like mathematics than machine instructions:
DO 10 J = 1,11
I = 11 − J
Y = F(A(I + 1))
IF (400 − Y) 4,8,8
4 PRINT 5,1
5 FORMAT (I10, 10H TOO LARGE)

The compiler was written, and the language was released with a professional-looking typeset manual (a first for programming languages) in 1957.
FORTRAN took another step toward making programming more accessible, allowing comments in the programs. The ability to insert annotations, marked to be ignored by the translator program but readable by a human, meant that a well-annotated program could be read in a certain sense by people with no programming knowledge at all. For the first time a nonprogrammer could get an idea what a program did—or at least what it was intended to do—by reading (part of) the code. It was an obvious but powerful step in opening up computers to a wider audience.
FORTRAN has continued to evolve, and it retains a large user base in academia and among scientists.
 
COBOL
About the time that Backus and his team invented FORTRAN, Hopper's group at UNIVAC released Math-matic, a FORTRAN-like language for UNIVAC computers. It was slower than FORTRAN and not particularly successful. Another language developed at Hopper's laboratory at the same time had more influence. Flow-matic used a more English-like syntax and vocabulary:
1 COMPARE PART-NUMBER (A) TO PART-NUMBER (B);
IF GREATER GO TO OPERATION 13;
IF EQUAL GO TO OPERATION 4;
OTHERWISE GO TO OPERATION 2.

Flow-matic led to the development by Hopper's group of COBOL (Common Business-Oriented Language) in 1959. COBOL was explicitly a business programming language with a very verbose English-like style. It became central to the wide acceptance of computers by business after 1959.
 
ALGOL
Although both FORTRAN and COBOL were universal languages (meaning that they could, in principle, be used to solve any problem that a computer could unravel), FORTRAN was better suited for mathematicians and engineers, whereas COBOL was explicitly a business programming language.
During the late 1950s a multitude of programming languages appeared. This proliferation of incompatible specialized languages spurred an interest in the United States and Europe to create a single “second-generation” language. A transatlantic committee soon formed to determine specifications for ALGOL (Algorithmic Language), as the new language would be called. Backus, on the American side, and Heinz Rutishauser, on the European side, were among the most influential committee members.
Although ALGOL introduced some important language ideas, it was not a commercial success. Customers preferred a known specialized language, such as FORTRAN or COBOL, to an unknown general-programming language. Only Pascal, a scientific programming-language offshoot of ALGOL, survives.

History of computing


A computer might be described with deceptive simplicity as “an apparatus that performs routine calculations automatically.” Such a definition would owe its deceptiveness to a naive and narrow view of calculation as a strictly mathematical process. In fact, calculation underlies many activities that are not normally thought of as mathematical. Walking across a room, for instance, requires many complex, albeit subconscious, calculations. Computers, too, have proved capable of solving a vast array of problems, from balancing a checkbook to even—in the form of guidance systems for robots—walking across a room.
Before the true power of computing could be realized, therefore, the naive view of calculation had to be overcome. The inventors who laboured to bring the computer into the world had to learn that the thing they were inventing was not just a number cruncher, not merely a calculator. For example, they had to learn that it was not necessary to invent a new computer for every new calculation and that a computer could be designed to solve numerous problems, even problems not yet imagined when the computer was built. They also had to learn how to tell such a general problem-solving computer what problem to solve. In other words, they had to invent programming.
They had to solve all the heady problems of developing such a device, of implementing the design, of actually building the thing. The history of the solving of these problems is the history of the computer. That history is covered in this section, and links are provided to entries on many of the individuals and companies mentioned. In addition, see the articles computer science and supercomputer.
 

Early history

Computer precursors

The abacu0s
  • A Chinese wooden abacus.
The earliest known calculating device is probably the aba0cus. It dates back at least to 1100 BCE and is still in use today, particularly in Asia. Now, as then, it typically consists of a rectangular frame with thin parallel rods strung with beads. Long before any systematic positional notation was adopted for the writing of numbers, the abacus assigned different units, or weights, to each rod. This scheme allowed a wide range of numbers to be represented by just a few beads and, together with the invention of zero in India, may have inspired the invention of the Hindu-Arabic number system. In any case, abacus beads can be readily manipulated to perform the common arithmetical operations—addition, subtraction, multiplication, and division—that are useful for commercial transactions and in bookkeeping.
The abacus is a digital device; that is, it represents values discretely. A bead is either in one predefined position or another, representing unambiguously, say, one or zero.
 
Analog calculators: from Napier's logarithms to the slide rule
Calculating devices took a different turn when John Napier, a Scottish mathematician, published his discovery of logarithms in 1614. As any person can attest, adding two 10-digit numbers is much simpler than multiplying them together, and the transformation of a multiplication problem into an addition problem is exactly what logarithms enable. This simplification is possible because of the following logarithmic property: the logarithm of the product of two numbers is equal to the sum of the logarithms of the numbers. By 1624, tables with 14 significant digits were available for the logarithms of numbers from 1 to 20,000, and scientists quickly adopted the new labour-saving tool for tedious astronomical calculations.
Most significant for the development of computing, the transformation of multiplication into addition greatly simplified the possibility of mechanization. Analog calculating devices based on Napier's logarithms—representing digital values with analogous physical lengths—soon appeared. In 1620 Edmund Gunter, the English mathematician who coined the terms cosine and cotangent, built a device for performing navigational calculations: the Gunter scale, or, as navigators simply called it, the gunter. About 1632 an English clergyman and mathematician named William Oughtred built the first slide rule, drawing on Napier's ideas. That first slide rule was circular, but Oughtred also built the first rectangular one in 1633. The analog devices of Gunter and Oughtred had various advantages and disadvantages compared with digital devices such as the abacus. What is important is that the consequences of these design decisions were being tested in the real world.
 
Digital calculators: from the Calculating Clock to the Arithmometer
  • The Calculating Clock
In 1623 the German astronomer and mathematician Wilhelm Schickard built the first calculator. He described it in a letter to his friend the astronomer Johannes Kepler, and in 1624 he wrote again to explain that a machine he had commissioned to be built for Kepler was, apparently along with the prototype, destroyed in a fire. He called it a Calculating Clock, which modern engineers have been able to reproduce from details in his letters. Even general knowledge of the clock had been temporarily lost when Schickard and his entire family perished during the Thirty Years' War.
But Schickard may not have been the true inventor of the calculator. A century earlier, Leonardo da Vinci sketched plans for a calculator that were sufficiently complete and correct for modern engineers to build a calculator on their basis.
  • The Arithmetic Machine
The first calculator or adding machine to be produced in any quantity and actually used was the Pascaline, or Arithmetic Machine, designed and built by the French mathematician-philosopher Blaise Pascal between 1642 and 1644. It could only do addition and subtraction, with numbers being entered by manipulating its dials. Pascal invented the machine for his father, a tax collector, so it was the first business machine too (if one does not count the abacus). He built 50 of them over the next 10 years.
  • The Step Reckoner
In 1671 the German mathematician-philosopher Gottfried Wilhelm von Leibniz designed a calculating machine called the Step Reckoner. (It was first built in 1673.) The Step Reckoner expanded on Pascal's ideas and did multiplication by repeated addition and shifting.
Leibniz was a strong advocate of the binary number system. Binary numbers are ideal for machines because they require only two digits, which can easily be represented by the on and off states of a switch. When computers became electronic, the binary system was particularly appropriate because an electrical circuit is either on or off. This meant that on could represent true, off could represent false, and the flow of current would directly represent the flow of logic.
Leibniz was prescient in seeing the appropriateness of the binary system in calculating machines, but his machine did not use it. Instead, the Step Reckoner represented numbers in decimal form, as positions on 10-position dials. Even decimal representation was not a given: in 1668 Samuel Morland invented an adding machine specialized for British money—a decidedly nondecimal system.
  • The Arithmometer
Pascal's, Leibniz's, and Morland's devices were curiosities, but with the Industrial Revolution of the 18th century came a widespread need to perform repetitive operations efficiently. With other activities being mechanized, why not calculation? In 1820 Charles Xavier Thomas de Colmar of France effectively met this challenge when he built his Arithmometer, the first commercial mass-produced calculating device. It could perform addition, subtraction, multiplication, and, with some more elaborate user involvement, division. Based on Leibniz's technology, it was extremely popular and sold for 90 years. In contrast to the modern calculator's credit-card size, the Arithmometer was large enough to cover a desktop.
 
The Jacquard loom
Calculators such as the Arithmometer remained a fascination after 1820, and their potential for commercial use was well understood. Many other mechanical devices built during the 19th century also performed repetitive functions more or less automatically, but few had any application to computing. There was one major exception: the Jacquard loom, invented in 1804–05 by a French weaver, Joseph-Marie Jacquard.
  • Jacquard loom, engraving, 1874
The Jacquard loom was a marvel of the Industrial Revolution. A textile-weaving loom, it could also be called the first practical information-processing device. The loom worked by tugging various-coloured threads into patterns by means of an array of rods. By inserting a card punched with holes, an operator could control the motion of the rods and thereby alter the pattern of the weave. Moreover, the loom was equipped with a card-reading device that slipped a new card from a prepunched deck into place every time the shuttle was thrown, so that complex weaving patterns could be automated.
What was extraordinary about the device was that it transferred the design process from a labour-intensive weaving stage to a card-punching stage. Once the cards had been punched and assembled, the design was complete, and the loom implemented the design automatically. The Jacquard loom, therefore, could be said to be programmed for different patterns by these decks of punched cards.
For those intent on mechanizing calculations, the Jacquard loom provided important lessons: the sequence of operations that a machine performs could be controlled to make the machine do something quite different; a punched card could be used as a medium for directing the machine; and, most important, a device could be directed to perform different tasks by feeding it instructions in a sort of language—i.e., making the machine programmable.
It is not too great a stretch to say that, in the Jacquard loom, programming was invented before the computer. The close relationship between the device and the program became apparent some 20 years later, with Charles Babbage's invention of the first computer.
 

The first computer

By the second decade of the 19th century, a number of ideas necessary for the invention of the computer were in the air. First, the potential benefits to science and industry of being able to automate routine calculations were appreciated, as they had not been a century earlier. Specific methods to make automated calculation more practical, such as doing multiplication by adding logarithms or by repeating addition, had been invented, and experience with both analog and digital devices had shown some of the benefits of each approach. The Jacquard loom (as described in the previous section, Computer precursors) had shown the benefits of directing a multipurpose device through coded instructions, and it had demonstrated how punched cards could be used to modify those instructions quickly and flexibly. It was a mathematical genius in England who began to put all these pieces together.

Computer software


Software denotes programs that run on computers. John Tukey, a statistician at Princeton University and Bell Laboratories, is generally credited with introducing the term in 1958 (as well as coining the word bit for binary digit). Initially software referred primarily to what is now called system software—an operating system and the utility programs that come with it, such as those to compile (translate) programs into machine code and load them for execution. This software came with a computer when it was bought or leased. In 1969 IBM decided to “unbundle” its software and sell it separately, and software soon became a major income source for manufacturers as well as for dedicated software firms.
 

Business and personal software

Business software generally must handle large amounts of data but relatively little computation, although that has changed somewhat in recent years. Office software typically includes word processors, spreadsheets, database programs, and tools for designing public presentations.
A spreadsheet is a type of accounting program. Unlike specialized accounting programs (e.g., payroll and office records), an important function of spreadsheets is their ability to explore “What if?” scenarios. A spreadsheet not only holds tables of data but also defines relationships among their rows and columns. For example, if the profit on a product is defined in terms of various costs—materials, manufacturing, and shipping—it is easy to ask “What if we use cheaper materials that require more manufacturing expense?”
A database is an organized collection of data, or records. Databases organize information to answer questions such as “What companies in the Southwest bought more than 100 of our products last year?” or “Which products made by Acme Manufacturing are in low supply?” Such software is often integrated so that a database report or spreadsheet table can be added to a document composed with a word processor, frequently with illustrative graphs. Today even the most trivial data can effortlessly be glorified by presenting it in a polychromatic bar chart with three-dimensional shading.
 

Scientific and engineering software

Scientific software is typically used to solve differential equations. (Differential equations are used to describe continuous actions or processes that depend on some other factors.) Although some differential equations have relatively simple mathematical solutions, exact solutions of many differential equations are very difficult to obtain. Computers, however, can be used to obtain useful approximate solutions, particularly when a problem is split into simpler spatial or temporal parts. Nevertheless, large-scale problems often require parallel computation on supercomputers or clusters of small computers that share the work.
There are numerous standard libraries of equation-solving software—some commercial, some distributed by national organizations in several countries. Another kind of software package does symbolic mathematics, obtaining exact solutions by algebraic manipulations. Two of the most widely used symbolic packages are Mathematica and Maple.
Scientific visualization software couples high-performance graphics with the output of equation solvers to yield vivid displays of models of physical systems. As with spreadsheets, visualization software lets an experimenter vary initial conditions or parameters. Observing the effect of such changes can help in improving models, as well as in understanding the original system.
Visualization is an essential feature of computer-aided engineering (CAE) and computer-aided design (CAD). An engineer can design a bridge, use modeling software to display it, and study it under different loads. CAE software can translate drawings into the precise specification of the parts of a mechanical system. Computer chips themselves are designed with CAD programs that let an engineer write a specification for part of a chip, simulate its behaviour in detail, test it thoroughly, and then generate the layouts for the photolithographic process that puts the circuit on the silicon.
Astronomical sky surveys, weather forecasting, and medical imaging—such as magnetic resonance imaging, CAT scans, and DNA analyses—create very large collections of data. Scientific computation today uses the same kinds of powerful statistical and pattern-analysis techniques as many business applications.
 

Internet and collaborative software

Among the most commonly used personal Internet software are “browsers” for displaying information located on the World Wide Web, newsreaders for reading “newsgroups” located on USENET, file-sharing programs for downloading files, and communication software for e-mail, as well as “instant messaging” and “chat room” programs that allow people to carry on conversations in real time. All of these applications are used for both personal and business activities.
Other common Internet software includes Web search engines and “Web-crawling” programs that traverse the Web to gather and classify information. Web-crawling programs are a kind of agent software, a term for programs that carry out routine tasks for a user. They stem from artificial intelligence research and carry out some of the tasks of librarians, but they are at a severe disadvantage. Although Web pages may have “content-tag” index terms, not all do, nor are there yet accepted standards for their use. Web search engines must use heuristic methods to determine the quality of Web page information as well as its content. Many details are proprietary, but they may use techniques such as finding “hubs” and “authorities” (pages with many links to and from other Web sites). Such strategies can be very effective, though the need for a Web version of card catalogs has not vanished.
  • Screen shot of the SETI@home page.
A different kind of Internet use depends on the vast number of computers connected to the Internet that are idle much of the time. Rather than run a “screen-saver” program, these computers can run software that lets them collaborate in the analysis of some difficult problem. Two examples are the SETI@home project, which distributes portions of radio telescope data for analysis that might help in the search for extraterrestrial intelligence (SETI), and the “Great Internet Mersenne Prime Search” (GIMPS), which parcels out tasks to test for large prime numbers.
The Internet has also become a business tool, and the ability to collect and store immense amounts of information has given rise to data warehousing and data mining. The former is a term for unstructured collections of data and the latter a term for its analysis. Data mining uses statistics and other mathematical tools to find patterns of information. For more information concerning business on the Internet, see e-commerce.
 

Games and entertainment

Computer games are nearly as old as digital computers and have steadily developed in sophistication. Chinook, a recent checkers (draughts) program, is widely believed to be better than any human player, and the IBM Deep Blue chess program beat world champion Garry Kasparov in 1996. These programs have demonstrated the power of modern computers, as well as the strength of good heuristics for strategy. On the other hand, such brute-force search heuristics have failed to produce a go-playing program that can defeat even moderately skilled players because there are too many possible moves in this Japanese game for simple quantification.
After board games, the earliest computer games were text-based adventures—in which players explored virtual worlds, sought treasure, and fought enemies by reading and typing simple commands. Such games resembled military simulation programs first used in the early 1950s. Contemporary games, however, depend on high-performance computer graphics. Played on arcade machines, special game computers for home use, or PCs, they use the same capabilities as simulation and visualization programs. A related area is computer-generated (CG) animation for films and video.

Networking

Computer communication may occur through wires, optical fibres, or radio transmissions. Wired networks may use shielded coaxial cable, similar to the wire connecting a television to a videocassette recorder or an antenna. They can also use simpler unshielded wiring with modular connectors similar to telephone wires. Optical fibres can carry more signals than wires; they are often used for linking buildings on a college campus or corporate site and increasingly for longer distances as telephone companies update their networks. Microwave radio also carries computer network signals, generally as part of long-distance telephone systems. Low-power microwave radio is becoming common for wireless networks within a building.

Local area networks


  • Local area networks (LANs)
Local area networks (LANs) connect computers within a building or small group of buildings. A LAN, as shown in the figure, may be configured as (1) a bus, a main channel to which nodes or secondary channels are connected in a branching structure, (2) a ring, in which each computer is connected to two neighbouring computers to form a closed circuit, or (3) a star, in which each computer is linked directly to a central computer and only indirectly to one another. Each of these has advantages, though the bus configuration has become the most common.
Even if only two computers are connected, they must follow rules, or protocols, to communicate. For example, one might signal “ready to send” and wait for the other to signal “ready to receive.” When many computers share a network, the protocol might include a rule “talk only when it is your turn” or “do not talk when anyone else is talking.” Protocols must also be designed to handle network errors.
The most common LAN design since the mid-1970s has been the bus-connected Ethernet, originally developed at Xerox PARC. Every computer or other device on an Ethernet has a unique 48-bit address. Any computer that wants to transmit listens for a carrier signal that indicates that a transmission is under way. If it detects none, it starts transmitting, sending the address of the recipient at the start of its transmission. Every system on the network receives each message but ignores those not addressed to it. While a system is transmitting, it also listens, and if it detects a simultaneous transmission, it stops, waits for a random time, and retries. The random time delay before retrying reduces the probability that they will collide again. This scheme is known as carrier sense multiple access with collision detection (CSMA/CD). It works very well until a network is moderately heavily loaded, and then it degrades as collisions become more frequent.
The first Ethernet had a capacity of about 2 megabits per second, and today 10- and 100-megabit-per-second Ethernet is common, with gigabit-per-second Ethernet also in use. Ethernet transceivers (transmitter-receivers) for PCs are inexpensive and easily installed.
A recent standard for wireless Ethernet, known as WiFi, is becoming common for small office and home networks. Using frequencies from 2.4 to 5 gigahertz (GHz), such networks can transfer data at rates from 11 to 54 megabits per second. Early in 2002 another Ethernet-like standard was released. Known as HomePlug, the first version could transmit data at about 8 megabits per second through a building's existing electrical power infrastructure.

Wide area networks

Wide area networks (WANs) span cities, countries, and the globe, generally using telephone lines and satellite links. The Internet connects multiple WANs; as its name suggests, it is a network of networks. Its success stems from early support by the U.S. Department of Defense, which developed its precursor, ARPANET, to let researchers communicate readily and share computer resources. Its success is also due to its flexible communication technique. The emergence of the Internet in the 1990s as not only a communication medium but also one of the principal focuses of computer use may be the most significant development in computing in the past several decades. For more on the history and technical details of Internet communication protocols, see Internet.

Operating systems


Role of operating systems

Operating systems manage a computer's resources—memory, peripheral devices, and even CPU access—and provide a battery of services to the user's programs. UNIX, first developed for minicomputers and now widely used on both PCs and mainframes, is one example; Linux (a version of UNIX), Microsoft Corporation's Windows XP, and Apple Computer's OS X are others.
One may think of an operating system as a set of concentric shells. At the centre is the bare processor, surrounded by layers of operating system routines to manage input/output (I/O), memory access, multiple processes, and communication among processes. User programs are located in the outermost layers. Each layer insulates its inner layer from direct access, while providing services to its outer layer. This architecture frees outer layers from having to know all the details of lower-level operations, while protecting inner layers and their essential services from interference.
Early computers had no operating system. A user loaded a program from paper tape by employing switches to specify its memory address, to start loading, and to run the program. When the program finished, the computer halted. The programmer had to have knowledge of every computer detail, such as how much memory it had and the characteristics of I/O devices used by the program.
It was quickly realized that this was an inefficient use of resources, particularly as the CPU was largely idle while waiting for relatively slow I/O devices to finish tasks such as reading and writing data. If instead several programs could be loaded at once and coordinated to interleave their steps of computation and I/O, more work could be done. The earliest operating systems were small supervisor programs that did just that: they coordinated several programs, accepting commands from the operator, and provided them all with basic I/O operations. These were known as multiprogrammed systems.
A multiprogrammed system must schedule its programs according to some priority rule, such as “shortest jobs first.” It must protect them from mutual interference to prevent an addressing error in a program from corrupting the data or code of another. It must ensure noninterference during I/O so that output from several programs does not get commingled or input misdirected. It might also have to record the CPU time of each job for billing purposes.
 

Modern types of operating systems

Multiuser systems
An extension of multiprogramming systems was developed in the 1960s, known variously as multiuser or time-sharing systems. (For a history of this development, see the section Time-sharing from Project MAC to UNIX.) Time-sharing allows many people to interact with a computer at once, each getting a small portion of the CPU's time. If the CPU is fast enough, it will appear to be dedicated to each user, particularly as a computer can perform many functions while waiting for each user to finish typing the latest commands.
Multiuser operating systems employ a technique known as multiprocessing, or multitasking (as do most single-user systems today), in which even a single program may consist of many separate computational activities, called processes. The system must keep track of active and queued processes, when each process must access secondary memory to retrieve and store its code and data, and the allocation of other resources, such as peripheral devices.
Since main memory was very limited, early operating systems had to be as small as possible to leave room for other programs. To overcome some of this limitation, operating systems use virtual memory, one of many computing techniques developed during the late 1950s under the direction of Tom Kilburn at the University of Manchester, England. Virtual memory gives each process a large address space (memory that it may use), often much larger than the actual main memory. This address space resides in secondary memory (such as tape or disks), from which portions are copied into main memory as needed, updated as necessary, and returned when a process is no longer active. Even with virtual memory, however, some “kernel” of the operating system has to remain in main memory. Early UNIX kernels occupied tens of kilobytes; today they occupy more than a megabyte, and PC operating systems are comparable, largely because of the declining cost of main memory.
Operating systems have to maintain virtual memory tables to keep track of where each process's address space resides, and modern CPUs provide special registers to make this more efficient. Indeed, much of an operating system consists of tables: tables of processes, of files and their locations (directories), of resources used by each process, and so on. There are also tables of user accounts and passwords that help control access to the user's files and protect them against accidental or malicious interference.
 
Thin systems
While minimizing the memory requirements of operating systems for standard computers has been important, it has been absolutely essential for small, inexpensive, specialized devices such as personal digital assistants (PDAs), “smart” cellular telephones, portable devices for listening to compressed music files, and Internet kiosks. Such devices must be highly reliable, fast, and secure against break-ins or corruption—a cellular telephone that “freezes” in the middle of calls would not be tolerated. One might argue that these traits should characterize any operating system, but PC users seem to have become quite tolerant of frequent operating system failures that require restarts.
 
Reactive systems
Still more limited are embedded, or real-time, systems. These are small systems that run the control processors embedded in machinery from factory production lines to home appliances. They interact with their environment, taking in data from sensors and making appropriate responses. Embedded systems are known as “hard” real-time systems if they must guarantee schedules that handle all events even in a worst case and “soft” if missed deadlines are not fatal. An aircraft control system is a hard real-time system, as a single flight error might be fatal. An airline reservation system, on the other hand, is a soft real-time system, since a missed booking is rarely catastrophic.
Many of the features of modern CPUs and operating systems are inappropriate for hard real-time systems. For example, pipelines and superscalar multiple execution units give high performance at the expense of occasional delays when a branch prediction fails and a pipeline is filled with unneeded instructions. Likewise, virtual memory and caches give good memory-access times on the average, but sometimes they are slow. Such variability is inimical to meeting demanding real-time schedules, and so embedded processors and their operating systems must generally be relatively simple.

Output devices


Printers are a common example of output devices. New multifunction peripherals that integrate printing, scanning, and copying into a single device are also popular. Computer monitors are sometimes treated as peripherals. High-fidelity sound systems are another example of output devices often classified as computer peripherals. Manufacturers have announced devices that provide tactile feedback to the user—“force feedback” joysticks, for example. This highlights the complexity of classifying peripherals—a joystick with force feedback is truly both an input and an output peripheral.
  • Inkjet printer
Early printers often used a process known as impact printing, in which a small number of pins were driven into a desired pattern by an electromagnetic printhead. As each pin was driven forward, it struck an inked ribbon and transferred a single dot the size of the pinhead to the paper. Multiple dots combined into a matrix to form characters and graphics, hence the name dot matrix. Another early print technology, daisy-wheel printers, made impressions of whole characters with a single blow of an electromagnetic printhead, similar to an electric typewriter. Laser printers have replaced such printers in most commercial settings. Laser printers employ a focused beam of light  to etch patterns of positively charged particles on the surface of a cylindrical drum made of negatively charged organic, photosensitive material. As the drum rotates, negatively charged toner particles adhere to the patterns etched by the laser and are transferred to the paper. Another, less expensive printing technology developed for the home and small businesses is inkjet printing.  The majority of inkjet printers operate by ejecting extremely tiny droplets of ink to form characters in a matrix of dots—much like dot matrix printers.
Computer display devices have been in use almost as long as computers themselves. Early computer displays employed the same cathode-ray tubes (CRTs) used in television and radar systems. The fundamental principle behind CRT displays is the emission of a controlled stream of electrons that strike light-emitting phosphors coating the inside of the screen. The screen itself is divided into multiple scan lines, each of which contains a number of pixels—the rough equivalent of dots in a dot matrix printer. The resolution of a monitor is determined by its pixel size. More recent liquid crystal displays (LCDs) rely on liquid crystal cells that realign incoming polarized light. The realigned beams pass through a filter that permits only those beams with a particular alignment to pass. By controlling the liquid crystal cells with electrical charges, various colours or shades are made to appear on the screen.
 
Communication devices
The most familiar example of a communication device is the common telephone modem (from modulator/demodulator). Modems modulate, or transform, a computer's digital message into an analog signal for transmission over standard telephone networks, and they demodulate the analog signal back into a digital message on reception. In practice, telephone network components limit analog data transmission to about 48 kilobits per second. Standard cable modems operate in a similar manner over cable television networks, which have a total transmission capacity of 30 to 40 megabits per second over each local neighbourhood “loop.” (Like Ethernet cards, cable modems are actually local area network devices, rather than true modems, and transmission performance deteriorates as more users share the loop.) Asymmetric digital subscriber line (ADSL) modems can be used for transmitting digital signals over a local dedicated telephone line, provided there is a telephone office nearby—in theory, within 5,500 metres (18,000 feet) but in practice about a third of that distance. ADSL is asymmetric because transmission rates differ to and from the subscriber: 8 megabits per second “downstream” to the subscriber and 1.5 megabits per second “upstream” from the subscriber to the service provider. In addition to devices for transmitting over telephone and cable wires, wireless communication devices exist for transmitting infrared, radiowave, and microwave signals.
 
Peripheral interfaces
A variety of techniques have been employed in the design of interfaces to link computers and peripherals. An interface of this nature is often termed a bus. This nomenclature derives from the presence of many paths of electrical communication (e.g., wires) bundled or joined together in a single device. Multiple peripherals can be attached to a single bus—the peripherals need not be homogeneous. An example is the small computer systems interface (SCSI; pronounced “scuzzy”). This popular standard allows heterogeneous devices to communicate with a computer by sharing a single bus. Under the auspices of various national and international organizations, many such standards have been established by manufacturers and users of computers and peripherals.
Buses can be loosely classified as serial or parallel. Parallel buses have a relatively large number of wires bundled together that enable data to be transferred in parallel. This increases the throughput, or rate of data transfer, between the peripheral and computer. SCSI buses are parallel buses. Examples of serial buses include the universal serial bus (USB). USB has an interesting feature in that the bus carries not only data to and from the peripheral but also electrical power. Examples of other peripheral integration schemes include integrated drive electronics (IDE) and enhanced integrated drive electronics (EIDE). Predating USB, these two schemes were designed initially to support greater flexibility in adapting hard disk drives to a variety of different computer makers.

Input devices

Peripherals

Computer peripherals are devices used to input information and instructions into a computer for storage or processing and to output the processed data. In addition, devices that enable the transmission and reception of data between computers are often classified as peripherals.

Input devices
A plethora of devices falls into the category of input peripheral. Typical examples include keyboards, mice, trackballs, pointing sticks, joysticks, digital tablets, touch pads, and scanners.
Keyboards contain mechanical or electromechanical switches that change the flow of current through the keyboard when depressed. A microprocessor embedded in the keyboard interprets these changes and sends a signal to the computer. In addition to letter and number keys, most keyboards also include “function” and “control” keys that modify input or send special commands to the computer.

    Mechanical mice and trackballs operate alike, using a rubber or rubber-coated ball that turns two shafts connected to a pair of encoders that measure the horizontal and vertical components of a user's movement, which are then translated into cursor movement on a computer monitor. Optical mice employ a light beam and camera lens to translate motion of the mouse into cursor movement.
    Pointing sticks, which are popular on many laptop systems, employ a technique that uses a pressure-sensitive resistor. As a user applies pressure to the stick, the resistor increases the flow of electricity, thereby signaling that movement has taken place. Most joysticks operate in a similar manner.
    Digital tablets and touch pads are similar in purpose and functionality. In both cases, input is taken from a flat pad that contains electrical sensors that detect the presence of either a special tablet pen or a user's finger, respectively.
    A scanner is somewhat akin to a photocopier. A light source illuminates the object to be scanned, and the varying amounts of reflected light are captured and measured by an analog-to-digital converter attached to light-sensitive diodes. The diodes generate a pattern of binary digits that are stored in the computer as a graphical image.

    Computer hardware


    The physical elements of a computer, its hardware, are generally divided into the central processing unit (CPU), main memory (or random-access memory, RAM), and peripherals. The last class encompasses all sorts of input and output (I/O) devices: keyboard, display monitor, printer, disk drives, network connections, scanners, and more.
     



    The CPU and RAM are integrated circuits (ICs)—small silicon wafers, or chips, that contain thousands or millions of transistors that function as electrical switches. In 1965 Gordon Moore, one of the founders of Intel, stated what has become known as Moore's law: the number of transistors on a chip doubles about every 18 months. Moore suggested that financial constraints would soon cause his law to break down, but it has been remarkably accurate for far longer than he first envisioned. It now appears that technical constraints may finally invalidate Moore's law, since sometime between 2010 and 2020 transistors would have to consist of only a few atoms each, at which point the laws of quantum physics imply that they would cease to function reliably.
     

    Central processing unit

    The CPU provides the circuits that implement the computer's instruction set—its machine language. It is composed of an arithmetic-logic unit (ALU) and control circuits. The ALU carries out basic arithmetic and logic operations, and the control section determines the sequence of operations, including branch instructions that transfer control from one part of a program to another. Although the main memory was once considered part of the CPU, today it is regarded as separate. The boundaries shift, however, and CPU chips now also contain some high-speed cache memory where data and instructions are temporarily stored for fast access.
    The ALU has circuits that add, subtract, multiply, and divide two arithmetic values, as well as circuits for logic operations such as AND and OR (where a 1 is interpreted as true and a 0 as false, so that, for instance, 1 AND 0 = 0; see Boolean algebra). The ALU has several to more than a hundred registers that temporarily hold results of its computations for further arithmetic operations or for transfer to main memory.
    The circuits in the CPU control section provide branch instructions, which make elementary decisions about what instruction to execute next. For example, a branch instruction might be “If the result of the last ALU operation is negative, jump to location A in the program; otherwise, continue with the following instruction.” Such instructions allow “if-then-else” decisions in a program and execution of a sequence of instructions, such as a “while-loop” that repeatedly does some set of instructions while some condition is met. A related instruction is the subroutine call, which transfers execution to a subprogram and then, after the subprogram finishes, returns to the main program where it left off.
    In a stored-program computer, programs and data in memory are indistinguishable. Both are bit patterns—strings of 0s and 1s—that may be interpreted either as data or as program instructions, and both are fetched from memory by the CPU. The CPU has a program counter that holds the memory address (location) of the next instruction to be executed. The basic operation of the CPU is the “fetch-decode-execute” cycle:
    • Fetch the instruction from the address held in the program counter, and store it in a register.
    • Decode the instruction. Parts of it specify the operation to be done, and parts specify the data on which it is to operate. These may be in CPU registers or in memory locations. If it is a branch instruction, part of it will contain the memory address of the next instruction to execute once the branch condition is satisfied.
    • Fetch the operands, if any.
    • Execute the operation if it is an ALU operation.
    • Store the result (in a register or in memory), if there is one.
    • Update the program counter to hold the next instruction location, which is either the next memory location or the address specified by a branch instruction.

    At the end of these steps the cycle is ready to repeat, and it continues until a special halt instruction stops execution.
    Steps of this cycle and all internal CPU operations are regulated by a clock that oscillates at a high frequency (now typically measured in gigahertz, or billions of cycles per second). Another factor that affects performance is the “word” size—the number of bits that are fetched at once from memory and on which CPU instructions operate. Digital words now consist of 32 or 64 bits, though sizes from 8 to 128 bits are seen.
    Processing instructions one at a time, or serially, often creates a bottleneck because many program instructions may be ready and waiting for execution. Since the early 1980s, CPU design has followed a style originally called reduced-instruction-set computing (RISC). This design minimizes the transfer of data between memory and CPU (all ALU operations are done only on data in CPU registers) and calls for simple instructions that can execute very quickly. As the number of transistors on a chip has grown, the RISC design requires a relatively small portion of the CPU chip to be devoted to the basic instruction set. The remainder of the chip can then be used to speed CPU operations by providing circuits that let several instructions execute simultaneously, or in parallel.
    There are two major kinds of instruction-level parallelism (ILP) in the CPU, both first used in early supercomputers. One is the pipeline, which allows the fetch-decode-execute cycle to have several instructions under way at once. While one instruction is being executed, another can obtain its operands, a third can be decoded, and a fourth can be fetched from memory. If each of these operations requires the same time, a new instruction can enter the pipeline at each phase and (for example) five instructions can be completed in the time that it would take to complete one without a pipeline. The other sort of ILP is to have multiple execution units in the CPU—duplicate arithmetic circuits, in particular, as well as specialized circuits for graphics instructions or for floating-point calculations (arithmetic operations involving noninteger numbers, such as 3.27). With this “superscalar” design, several instructions can execute at once.
    Both forms of ILP face complications. A branch instruction might render preloaded instructions in the pipeline useless if they entered it before the branch jumped to a new part of the program. Also, superscalar execution must determine whether an arithmetic operation depends on the result of another operation, since they cannot be executed simultaneously. CPUs now have additional circuits to predict whether a branch will be taken and to analyze instructional dependencies. These have become highly sophisticated and can frequently rearrange instructions to execute more of them in parallel.
     

    Main memory

    The earliest forms of computer main memory were mercury delay lines, which were tubes of mercury that stored data as ultrasonic waves, and cathode-ray tubes, which stored data as charges on the tubes' screens. The magnetic drum, invented about 1948, used an iron oxide coating on a rotating drum to store data and programs as magnetic patterns.
    In a binary computer any bistable device (something that can be placed in either of two states) can represent the two possible bit values of 0 and 1 and can thus serve as computer memory. Magnetic-core memory, the first relatively cheap RAM device, appeared in 1952. It was composed of tiny, doughnut-shaped ferrite magnets threaded on the intersection points of a two-dimensional wire grid. These wires carried currents to change the direction of each core's magnetization, while a third wire threaded through the doughnut detected its magnetic orientation.
    The first integrated circuit (IC) memory chip appeared in 1971. IC memory stores a bit in a transistor-capacitor combination. The capacitor holds a charge to represent a 1 and no charge for a 0; the transistor switches it between these two states. Because a capacitor charge gradually decays, IC memory is dynamic RAM (DRAM), which must have its stored values refreshed periodically (every 20 milliseconds or so). There is also static RAM (SRAM), which does not have to be refreshed. Although faster than DRAM, SRAM uses more transistors and is thus more costly; it is used primarily for CPU internal registers and cache memory.
    In addition to main memory, computers generally have special video memory (VRAM) to hold graphical images, called bit-maps, for the computer display. This memory is often dual-ported—a new image can be stored in it at the same time that its current data is being read and displayed.
    It takes time to specify an address in a memory chip, and, since memory is slower than a CPU, there is an advantage to memory that can transfer a series of words rapidly once the first address is specified. One such design is known as synchronous DRAM (SDRAM), which became widely used by 2001.
    Nonetheless, data transfer through the “bus”—the set of wires that connect the CPU to memory and peripheral devices—is a bottleneck. For that reason, CPU chips now contain cache memory—a small amount of fast SRAM. The cache holds copies of data from blocks of main memory. A well-designed cache allows up to 85–90 percent of memory references to be done from it in typical programs, giving a several-fold speedup in data access.
    The time between two memory reads or writes (cycle time) was about 17 microseconds (millionths of a second) for early core memory and about 1 microsecond for core in the early 1970s. The first DRAM had a cycle time of about half a microsecond, or 500 nanoseconds (billionths of a second), and today it is 20 nanoseconds or less. An equally important measure is the cost per bit of memory. The first DRAM stored 128 bytes (1 byte = 8 bits) and cost about $10, or $80,000 per megabyte (millions of bytes). In 2001 DRAM could be purchased for less than $0.25 per megabyte. This vast decline in cost made possible graphical user interfaces (GUIs), the display fonts that word processors use, and the manipulation and visualization of large masses of data by scientific computers.
     

    Secondary memory

    Secondary memory on a computer is storage for data and programs not in use at the moment. In addition to punched cards and paper tape, early computers also used magnetic tape for secondary storage. Tape is cheap, either on large reels or in small cassettes, but has the disadvantage that it must be read or written sequentially from one end to the other.
    IBM introduced the first magnetic disk, the RAMAC, in 1955; it held 5 megabytes and rented for $3,200 per month. Magnetic disks are platters coated with iron oxide, like tape and drums. An arm with a tiny wire coil, the read/write (R/W) head, moves radially over the disk, which is divided into concentric tracks composed of small arcs, or sectors, of data. Magnetized regions of the disk generate small currents in the coil as it passes, thereby allowing it to “read” a sector; similarly, a small current in the coil will induce a local magnetic change in the disk, thereby “writing” to a sector. The disk rotates rapidly (up to 15,000 rotations per minute), and so the R/W head can rapidly reach any sector on the disk.
     



     Early disks had large removable platters. In the 1970s IBM introduced sealed disks with fixed platters known as Winchester disks—perhaps because the first ones had two 30-megabyte platters, suggesting the Winchester 30-30 rifle. Not only was the sealed disk protected against dirt, the R/W head could also “fly” on a thin air film, very close to the platter. By putting the head closer to the platter, the region of oxide film that represented a single bit could be much smaller, thus increasing storage capacity. This basic technology is still used.

    Refinements have included putting multiple platters—10 or more—in a single disk drive, with a pair of R/W heads for the two surfaces of each platter in order to increase storage and data transfer rates. Even greater gains have resulted from improving control of the radial motion of the disk arm from track to track, resulting in denser distribution of data on the disk. By 2002 such densities had reached over 8,000 tracks per centimetre (20,000 tracks per inch), and a platter the diameter of a coin could hold over a gigabyte of data. In 2002 an 80-gigabyte disk cost about $200—only one ten-millionth of the 1955 cost and representing an annual decline of nearly 30 percent, similar to the decline in the price of main memory.
     



     
    • The DVD player uses a laser that is higher-powered and has a correspondingly finer focus point than …
    Optical storage devices—CD-ROM (compact disc, read-only memory) and DVD-ROM (digital videodisc, or versatile disc)—appeared in the mid-1980s and '90s. They both represent bits as tiny pits in plastic, organized in a long spiral like a phonograph record, written and read with lasers. A CD-ROM can hold 2 gigabytes of data, but the inclusion of error-correcting codes (to correct for dust, small defects, and scratches) reduces the usable data to 650 megabytes. DVDs are denser, have smaller pits, and can hold 17 gigabytes with error correction.
    Optical storage devices are slower than magnetic disks, but they are well suited for making master copies of software or for multimedia (audio and video) files that are read sequentially. There are also writable and rewritable CD-ROMs (CD-R and CD-RW) and DVD-ROMs (DVD-R and DVD-RW) that can be used like magnetic tapes for inexpensive archiving and sharing of data.
    The decreasing cost of memory continues to make new uses possible. A single CD-ROM can store 100 million words, more than twice as many words as are contained in the printed Encyclopædia Britannica. A DVD can hold a feature-length motion picture. Nevertheless, even larger and faster storage systems, such as three-dimensional optical media, are being developed for handling data for computer simulations of nuclear reactions, astronomical data, and medical data, including X-ray images. Such applications typically require many terabytes (1 terabyte = 1,000 gigabytes) of storage, which can lead to further complications in indexing and retrieval.