Feeds:
Posts
Comments

Archive for June, 2009

Computation

Computation

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Computation is a general term for any type of information processing. This includes phenomena ranging from human thinking to calculations with a more narrow meaning. Computation is a process following a well-defined model that is understood and can be expressed in an algorithm, protocol, network topology, etc. Computation is also a major subject matter of computer science: it investigates what can or cannot be done in a computational manner.

Sister project Look up computation in Wiktionary, the free dictionary.

Contents

[hide]

[edit] Classes of computation

Computation can be classified by at least three orthogonal criteria: digital vs analog, sequential vs parallel vs concurrent, batch vs interactive.

In practice, digital computation is often used to simulate natural processes (for example, Evolutionary computation), including those that are more naturally described by analog models of computation (for example, Artificial neural network). In this situation, it is important to distinguish between the mechanism of computation and the simulated model.

[edit] Computations as a physical phenomenon

A computation can be seen as a purely physical phenomenon occurring inside a closed physical system called a computer. Examples of such physical systems include digital computers, quantum computers, DNA computers, molecular computers, analog computers or wetware computers. This point of view is the one adopted by the branch of theoretical physics called the physics of computation.

An even more radical point of view is the postulate of digital physics that the evolution of the universe itself is a computation – Pancomputationalism.

[edit] Mathematical models of computation

In the theory of computation, a diversity of mathematical models of computers have been developed. Typical mathematical models of computers are the following:

  • State models including Turing Machine, Push-down automaton, Finite state automaton, and PRAM
  • Functional models including lambda calculus
  • Logical models including logic programming
  • Concurrent models including Actor model and process calculi

[edit] History

The word computation has an archaic meaning (from its Latin etymological roots), but the word has come back in use with the arising of a new scientific discipline: computer science.

[edit] See also

Computer Science portal
  This computer science article is a stub. You can help Wikipedia by expanding it.

Read Full Post »

Computational problem

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring

“Given a positive integer n, find a nontrivial prime factor of n.”

is a computational problem. Computational problems are one of the main objects of study in theoretical computer science. The field of algorithms studies methods of solving computational problems efficiently. The complementary field of computational complexity attempts to explain why certain computational problems are intractable for computers.

A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. For example in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n.

It is conventional to represent both instances and solutions by binary strings, namely elements of {0, 1}*. For example, numbers can be represented as binary strings using the binary encoding. (For readability, we identify numbers with their binary encodings in the examples below.)

[edit] Types of computational problems

A decision problem is a computational problem where the answer for every instance is either yes or no. An example of a decision problem is primality testing:

“Given a positive integer n, determine if n is prime.”

A decision problem is typically represented as the set of all instances for which the answer is yes. For example, primality testing can be represented as the infinite set

L = {2, 3, 5, 7, 11, …}

In a search problem, the answers can be arbitrary strings. For example, factoring is a search problem where the instances are (string representations of) positive integers and the solutions are (string representations of) collections of primes.

A search problem is represented as a relation over consisting of all the instance-solution pairs, called a search relation. For example, primality can be represented as the relation

R = {(4, 2), (6, 2), (6, 3), (8, 2), (8, 4), (9, 3), …}

which consist of all pairs of numbers (n, p), where p is a nontrivial prime factor of n.

A counting problem asks for the number of solutions to a given search problem. For example, the counting problem associated with primality is

“Given a positive integer n, count the number of nontrivial prime factors of n.”

A counting problem can be represented by a function f from {0, 1}* to the nonnegative integers. For a search relation R, the counting problem associated to R is the function

fR(x) = |{y: (x, y) ∈ R}|.

An optimization problem asks for finding the “best possible” solution among the set of all possible solutions to a search problem. One example is the maximum independent set problem:

“Given a graph G, find an independent set of G of maximum size.”

Optimization problems can be represented by their search relations.

[edit] Promise problems

In computational complexity theory, it is usually implicitly assumed that any string in {0, 1}* represents an instance of the computational problem in question. However, sometimes not all strings {0, 1}* represent valid instances, and one specifies a proper subset of {0, 1}* as the set of “valid instances”. Computational problems of this type are called promise problems.

The following is an example of a (decision) promise problem:

“Given a graph G, determine if G has an independent set of size at most 5, or every independent set in G has size at least 10.”

Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at least 10.

Decision promise problems are usually represented as pairs of disjoint subsets (Lyes, Lno) of {0, 1}*. The valid instances are those in LyesLno. Lyes and Lno represent the instances whose answer is yes and no, respectively.

Promise problems play an important role in several areas of computational complexity, including hardness of approximation, property testing, and interactive proof systems.

[edit] References

Read Full Post »

Computer

Computer

From Wikipedia, the free encyclopedia

Jump to: navigation, search

This article is about the machine. For other uses, see Computer (disambiguation).
“Computer technology” redirects here. For the company, see Computer Technology Limited.

This article may be too long to comfortably read and navigate. Please consider splitting content into sub-articles and using this article for a summary of the key points of the subject. (June 2009)

A computer is a machine that manipulates data according to a set of instructions.

Although mechanical examples of computers have existed through much of recorded human history, the first resembling a modern computer were developed in the mid-20th century (1940–1945). The first electronic computers were the size of a large room, consuming as much power as several hundred modern personal computers (PC).[1] Modern computers based on tiny integrated circuits are millions to billions of times more capable than the early machines, and occupy a fraction of the space.[2] Simple computers are small enough to fit into a wristwatch, and can be powered by a watch battery. Personal computers in their various forms are icons of the Information Age, what most people think of as a “computer”, but the embedded computers found in devices ranging from fighter aircraft to industrial robots, digital cameras, and toys are the most numerous.

The ability to store and execute lists of instructions called programs makes computers extremely versatile, distinguishing them from calculators. The Church–Turing thesis is a mathematical statement of this versatility: any computer with a certain minimum capability is, in principle, capable of performing the same tasks that any other computer can perform. Therefore computers ranging from a personal digital assistant to a supercomputer are all able to perform the same computational tasks, given enough time and storage capacity.

Contents

[hide]

[edit] History of computing

Main article: History of computer hardware

The Jacquard loom was one of the first programmable devices.

The first use of the word “computer” was recorded in 1613, referring to a person who carried out calculations, or computations, and the word continued to be used in that sense until the middle of the 20th century. From the end of the 19th century onwards though, the word began to take on its more familiar meaning, describing a machine that carries out computations.[3]

The history of the modern computer begins with two separate technologies—automated calculation and programmability—but no single device can be identified as the earliest computer, partly because of the inconsistent application of that term. Examples of early mechanical calculating devices include the abacus, the slide rule and arguably the astrolabe and the Antikythera mechanism (which dates from about 150–100 BC). Hero of Alexandria (c. 10–70 AD) built a mechanical theater which performed a play lasting 10 minutes and was operated by a complex system of ropes and drums that might be considered to be a means of deciding which parts of the mechanism performed which actions and when.[4] This is the essence of programmability.

The “castle clock”, an astronomical clock invented by Al-Jazari in 1206, is considered to be the earliest programmable analog computer.[5] It displayed the zodiac, the solar and lunar orbits, a crescent moon-shaped pointer travelling across a gateway causing automatic doors to open every hour,[6][7] and five robotic musicians who played music when struck by levers operated by a camshaft attached to a water wheel. The length of day and night could be re-programmed to compensate for the changing lengths of day and night throughout the year.[5]

The end of the Middle Ages saw a re-invigoration of European mathematics and engineering. Wilhelm Schickard‘s 1623 device was the first of a number of mechanical calculators constructed by European engineers, but none fit the modern definition of a computer, because they could not be programmed.

In 1801, Joseph Marie Jacquard made an improvement to the textile loom by introducing a series of punched paper cards as a template which allowed his loom to weave intricate patterns automatically. The resulting Jacquard loom was an important step in the development of computers because the use of punched cards to define woven patterns can be viewed as an early, albeit limited, form of programmability.

It was the fusion of automatic calculation with programmability that produced the first recognizable computers. In 1837, Charles Babbage was the first to conceptualize and design a fully programmable mechanical computer, his analytical engine.[8] Limited finances and Babbage’s inability to resist tinkering with the design meant that the device was never completed.

In the late 1880s Herman Hollerith invented the recording of data on a machine readable medium. Prior uses of machine readable media, above, had been for control, not data. “After some initial trials with paper tape, he settled on punched cards …”[9] To process these punched cards he invented the tabulator, and the key punch machines. These three inventions were the foundation of the modern information processing industry. Large-scale automated data processing of punched cards was performed for the 1890 United States Census by Hollerith’s company, which later became the core of IBM. By the end of the 19th century a number of technologies that would later prove useful in the realization of practical computers had begun to appear: the punched card, Boolean algebra, the vacuum tube (thermionic valve) and the teleprinter.

During the first half of the 20th century, many scientific computing needs were met by increasingly sophisticated analog computers, which used a direct mechanical or electrical model of the problem as a basis for computation. However, these were not programmable and generally lacked the versatility and accuracy of modern digital computers.

Alan Turing is widely regarded to be the father of modern computer science. In 1936 Turing provided an influential formalisation of the concept of the algorithm and computation with the Turing machine. Of his role in the modern computer, Time Magazine in naming Turing one of the 100 most influential people of the 20th century, states: “The fact remains that everyone who taps at a keyboard, opening a spreadsheet or a word-processing program, is working on an incarnation of a Turing machine.” [10]

George Stibitz is internationally recognized as a father of the modern digital computer. While working at Bell Labs in November of 1937, Stibitz invented and built a relay-based calculator he dubbed the “Model K” (for “kitchen table”, on which he had assembled it), which was the first to use binary circuits to perform an arithmetic operation. Later models added greater sophistication including complex arithmetic and programmability.[11]

Defining characteristics of some early digital computers of the 1940s (In the history of computing hardware)
Name First operational Numeral system Computing mechanism Programming Turing complete
Zuse Z3 (Germany) May 1941 Binary Electro-mechanical Program-controlled by punched film stock (but no conditional branch) Yes (1998)
Atanasoff–Berry Computer (US) 1942 Binary Electronic Not programmable—single purpose No
Colossus Mark 1 (UK) February 1944 Binary Electronic Program-controlled by patch cables and switches No
Harvard Mark I – IBM ASCC (US) May 1944 Decimal Electro-mechanical Program-controlled by 24-channel punched paper tape (but no conditional branch) No
Colossus Mark 2 (UK) June 1944 Binary Electronic Program-controlled by patch cables and switches No
ENIAC (US) July 1946 Decimal Electronic Program-controlled by patch cables and switches Yes
Manchester Small-Scale Experimental Machine (UK) June 1948 Binary Electronic Stored-program in Williams cathode ray tube memory Yes
Modified ENIAC (US) September 1948 Decimal Electronic Program-controlled by patch cables and switches plus a primitive read-only stored programming mechanism using the Function Tables as program ROM Yes
EDSAC (UK) May 1949 Binary Electronic Stored-program in mercury delay line memory Yes
Manchester Mark 1 (UK) October 1949 Binary Electronic Stored-program in Williams cathode ray tube memory and magnetic drum memory Yes
CSIRAC (Australia) November 1949 Binary Electronic Stored-program in mercury delay line memory Yes

A succession of steadily more powerful and flexible computing devices were constructed in the 1930s and 1940s, gradually adding the key features that are seen in modern computers. The use of digital electronics (largely invented by Claude Shannon in 1937) and more flexible programmability were vitally important steps, but defining one point along this road as “the first digital electronic computer” is difficult (Shannon 1940). Notable achievements include:

EDSAC was one of the first computers to implement the stored program (von Neumann) architecture.

  • Konrad Zuse‘s electromechanical “Z machines”. The Z3 (1941) was the first working machine featuring binary arithmetic, including floating point arithmetic and a measure of programmability. In 1998 the Z3 was proved to be Turing complete, therefore being the world’s first operational computer.
  • The non-programmable Atanasoff–Berry Computer (1941) which used vacuum tube based computation, binary numbers, and regenerative capacitor memory. The use of regenerative memory allowed it to be much more compact then its peers (being approximately the size of a large desk or workbench), since intermediate results could be stored and then fed back into the same set of computation elements.
  • The secret British Colossus computers (1943),[12] which had limited programmability but demonstrated that a device using thousands of tubes could be reasonably reliable and electronically reprogrammable. It was used for breaking German wartime codes.
  • The Harvard Mark I (1944), a large-scale electromechanical computer with limited programmability.
  • The U.S. Army’s Ballistics Research Laboratory ENIAC (1946), which used decimal arithmetic and is sometimes called the first general purpose electronic computer (since Konrad Zuse‘s Z3 of 1941 used electromagnets instead of electronics). Initially, however, ENIAC had an inflexible architecture which essentially required rewiring to change its programming.

Several developers of ENIAC, recognizing its flaws, came up with a far more flexible and elegant design, which came to be known as the “stored program architecture” or von Neumann architecture. This design was first formally described by John von Neumann in the paper First Draft of a Report on the EDVAC, distributed in 1945. A number of projects to develop computers based on the stored-program architecture commenced around this time, the first of these being completed in Great Britain. The first to be demonstrated working was the Manchester Small-Scale Experimental Machine (SSEM or “Baby”), while the EDSAC, completed a year after SSEM, was the first practical implementation of the stored program design. Shortly thereafter, the machine originally described by von Neumann’s paper—EDVAC—was completed but did not see full-time use for an additional two years.

Nearly all modern computers implement some form of the stored-program architecture, making it the single trait by which the word “computer” is now defined. While the technologies used in computers have changed dramatically since the first electronic, general-purpose computers of the 1940s, most still use the von Neumann architecture.

Microprocessors are miniaturized devices that often implement stored program CPUs.

Computers using vacuum tubes as their electronic elements were in use throughout the 1950s, but by the 1960s had been largely replaced by transistor-based machines, which were smaller, faster, cheaper to produce, required less power, and were more reliable. The first transistorised computer was demonstrated at the University of Manchester in 1953.[13] In the 1970s, integrated circuit technology and the subsequent creation of microprocessors, such as the Intel 4004, further decreased size and cost and further increased speed and reliability of computers. By the late 1970s, many products such as video recorders contained dedicated computers called microcontrollers, and they started to appear as a replacement to mechanical controls in domestic appliances such as washing machines. The 1980s witnessed home computers and the now ubiquitous personal computer. With the evolution of the Internet, personal computers are becoming as common as the television and the telephone in the household.

Modern smartphones are fully-programmable computers in their own right, and as of 2009 may well be the most common form of such computers in existence.

[edit] Stored program architecture

The defining feature of modern computers which distinguishes them from all other machines is that they can be programmed. That is to say that a list of instructions (the program) can be given to the computer and it will store them and carry them out at some time in the future.

In most cases, computer instructions are simple: add one number to another, move some data from one location to another, send a message to some external device, etc. These instructions are read from the computer’s memory and are generally carried out (executed) in the order they were given. However, there are usually specialized instructions to tell the computer to jump ahead or backwards to some other place in the program and to carry on executing from there. These are called “jump” instructions (or branches). Furthermore, jump instructions may be made to happen conditionally so that different sequences of instructions may be used depending on the result of some previous calculation or some external event. Many computers directly support subroutines by providing a type of jump that “remembers” the location it jumped from and another instruction to return to the instruction following that jump instruction.

Program execution might be likened to reading a book. While a person will normally read each word and line in sequence, they may at times jump back to an earlier place in the text or skip sections that are not of interest. Similarly, a computer may sometimes go back and repeat the instructions in some section of the program over and over again until some internal condition is met. This is called the flow of control within the program and it is what allows the computer to perform tasks repeatedly without human intervention.

Comparatively, a person using a pocket calculator can perform a basic arithmetic operation such as adding two numbers with just a few button presses. But to add together all of the numbers from 1 to 1,000 would take thousands of button presses and a lot of time—with a near certainty of making a mistake. On the other hand, a computer may be programmed to do this with just a few simple instructions. For example:

mov #0,sum ; set sum to 0
mov #1,num ; set num to 1
loop: add num,sum ; add num to sum
add #1,num ; add 1 to num
cmp num,#1000 ; compare num to 1000
ble loop ; if num <= 1000, go back to 'loop'
halt ; end of program. stop running

Once told to run this program, the computer will perform the repetitive addition task without further human intervention. It will almost never make a mistake and a modern PC can complete the task in about a millionth of a second.[14]

However, computers cannot “think” for themselves in the sense that they only solve problems in exactly the way they are programmed to. An intelligent human faced with the above addition task might soon realize that instead of actually adding up all the numbers one can simply use the equation

1+2+3+...+n = {{n(n+1)} \over 2}

and arrive at the correct answer (500,500) with little work.[15] In other words, a computer programmed to add up the numbers one by one as in the example above would do exactly that without regard to efficiency or alternative solutions.

[edit] Programs

A 1970s punched card containing one line from a FORTRAN program. The card reads: “Z(1) = Y + W(1)” and is labelled “PROJ039” for identification purposes.

In practical terms, a computer program may run from just a few instructions to many millions of instructions, as in a program for a word processor or a web browser. A typical modern computer can execute billions of instructions per second (gigahertz or GHz) and rarely make a mistake over many years of operation. Large computer programs consisting of several million instructions may take teams of programmers years to write, and due to the complexity of the task almost certainly contain errors.

Errors in computer programs are called “bugs“. Bugs may be benign and not affect the usefulness of the program, or have only subtle effects. But in some cases they may cause the program to “hang“—become unresponsive to input such as mouse clicks or keystrokes, or to completely fail or “crash“. Otherwise benign bugs may sometimes may be harnessed for malicious intent by an unscrupulous user writing an “exploit“—code designed to take advantage of a bug and disrupt a program’s proper execution. Bugs are usually not the fault of the computer. Since computers merely execute the instructions they are given, bugs are nearly always the result of programmer error or an oversight made in the program’s design.[16]

In most computers, individual instructions are stored as machine code with each instruction being given a unique number (its operation code or opcode for short). The command to add two numbers together would have one opcode, the command to multiply them would have a different opcode and so on. The simplest computers are able to perform any of a handful of different instructions; the more complex computers have several hundred to choose from—each with a unique numerical code. Since the computer’s memory is able to store numbers, it can also store the instruction codes. This leads to the important fact that entire programs (which are just lists of instructions) can be represented as lists of numbers and can themselves be manipulated inside the computer just as if they were numeric data. The fundamental concept of storing programs in the computer’s memory alongside the data they operate on is the crux of the von Neumann, or stored program, architecture. In some cases, a computer might store some or all of its program in memory that is kept separate from the data it operates on. This is called the Harvard architecture after the Harvard Mark I computer. Modern von Neumann computers display some traits of the Harvard architecture in their designs, such as in CPU caches.

While it is possible to write computer programs as long lists of numbers (machine language) and this technique was used with many early computers,[17] it is extremely tedious to do so in practice, especially for complicated programs. Instead, each basic instruction can be given a short name that is indicative of its function and easy to remember—a mnemonic such as ADD, SUB, MULT or JUMP. These mnemonics are collectively known as a computer’s assembly language. Converting programs written in assembly language into something the computer can actually understand (machine language) is usually done by a computer program called an assembler. Machine languages and the assembly languages that represent them (collectively termed low-level programming languages) tend to be unique to a particular type of computer. For instance, an ARM architecture computer (such as may be found in a PDA or a hand-held videogame) cannot understand the machine language of an Intel Pentium or the AMD Athlon 64 computer that might be in a PC.[18]

Though considerably easier than in machine language, writing long programs in assembly language is often difficult and error prone. Therefore, most complicated programs are written in more abstract high-level programming languages that are able to express the needs of the computer programmer more conveniently (and thereby help reduce programmer error). High level languages are usually “compiled” into machine language (or sometimes into assembly language and then into machine language) using another computer program called a compiler.[19] Since high level languages are more abstract than assembly language, it is possible to use different compilers to translate the same high level language program into the machine language of many different types of computer. This is part of the means by which software like video games may be made available for different computer architectures such as personal computers and various video game consoles.

The task of developing large software systems presents a significant intellectual challenge. Producing software with an acceptably high reliability within a predictable schedule and budget has historically been difficult; the academic and professional discipline of software engineering concentrates specifically on this problem.

[edit] Example

A traffic light showing red

Suppose a computer is being employed to drive a traffic signal at an intersection between two streets. The computer has the following three basic instructions.

  1. ON(Streetname, Color) Turns the light on Streetname with a specified Color on.
  2. OFF(Streetname, Color) Turns the light on Streetname with a specified Color off.
  3. WAIT(Seconds) Waits a specifed number of seconds.
  4. START Starts the program
  5. REPEAT Tells the computer to repeat a specified part of the program in a loop.

Comments are marked with a // on the left margin. Assume the streetnames are Broadway and Main.

START

//Let Broadway traffic go
OFF(Broadway, Red)
ON(Broadway, Green)
WAIT(60 seconds)

//Stop Broadway traffic
OFF(Broadway, Green)
ON(Broadway, Yellow)
WAIT(3 seconds)
OFF(Broadway, Yellow)
ON(Broadway, Red)

//Let Main traffic go
OFF(Main, Red)
ON(Main, Green)
WAIT(60 seconds)

//Stop Main traffic
OFF(Main, Green)
ON(Main, Yellow)
WAIT(3 seconds)
OFF(Main, Yellow)
ON(Main, Red)

//Tell computer to continuously repeat the program.
REPEAT ALL

With this set of instructions, the computer would cycle the light continually through red, green, yellow and back to red again on both streets.

However, suppose there is a simple on/off switch connected to the computer that is intended to be used to make the light flash red while some maintenance operation is being performed. The program might then instruct the computer to:

START

IF Switch == OFF then: //Normal traffic signal operation
{
//Let Broadway traffic go
OFF(Broadway, Red)
ON(Broadway, Green)
WAIT(60 seconds)

//Stop Broadway traffic
OFF(Broadway, Green)
ON(Broadway, Yellow)
WAIT(3 seconds)
OFF(Broadway, Yellow)
ON(Broadway, Red)

//Let Main traffic go
OFF(Main, Red)
ON(Main, Green)
WAIT(60 seconds)

//Stop Main traffic
OFF(Main, Green)
ON(Main, Yellow)
WAIT(3 seconds)
OFF(Main, Yellow)
ON(Main, Red)

//Tell the computer to repeat this section continuously.
REPEAT THIS SECTION
}

IF Switch == ON THEN: //Maintenance Mode
{
//Turn the red lights on and wait 1 second.
ON(Broadway, Red)
ON(Main, Red)
WAIT(1 second)

//Turn the red lights off and wait 1 second.
OFF(Broadway, Red)
OFF(Main, Red)
WAIT(1 second)

//Tell the comptuer to repeat the statements in this section.
REPEAT THIS SECTION
}

In this manner, the traffic signal will run a flash-red program when the switch is on, and will run the normal program when the switch is off. Both of these program examples show the basic layout of a computer program in a simple, familiar context of a traffic signal. Any experienced programmer can spot many software bugs in the program, for instance, not making sure that the green light is off when the switch is set to flash red. However, to remove all possible bugs would make this program much longer and more complicated, and would be confusing to nontechnical readers: the aim of this example is a simple demonstration of how computer instructions are laid out.

[edit] How computers work

A general purpose computer has four main components: the arithmetic and logic unit (ALU), the control unit, the memory, and the input and output devices (collectively termed I/O). These parts are interconnected by busses, often made of groups of wires.

The control unit, ALU, registers, and basic I/O (and often other hardware closely linked with these) are collectively known as a central processing unit (CPU). Early CPUs were composed of many separate components but since the mid-1970s CPUs have typically been constructed on a single integrated circuit called a microprocessor.

[edit] Control unit

Main articles: CPU design and Control unit

The control unit (often called a control system or central controller) manages the computer’s various components; it reads and interprets (decodes) the program instructions, transforming them into a series of control signals which activate other parts of the computer.[20] Control systems in advanced computers may change the order of some instructions so as to improve performance.

A key component common to all CPUs is the program counter, a special memory cell (a register) that keeps track of which location in memory the next instruction is to be read from.[21]

Diagram showing how a particular MIPS architecture instruction would be decoded by the control system.

The control system’s function is as follows—note that this is a simplified description, and some of these steps may be performed concurrently or in a different order depending on the type of CPU:

  1. Read the code for the next instruction from the cell indicated by the program counter.
  2. Decode the numerical code for the instruction into a set of commands or signals for each of the other systems.
  3. Increment the program counter so it points to the next instruction.
  4. Read whatever data the instruction requires from cells in memory (or perhaps from an input device). The location of this required data is typically stored within the instruction code.
  5. Provide the necessary data to an ALU or register.
  6. If the instruction requires an ALU or specialized hardware to complete, instruct the hardware to perform the requested operation.
  7. Write the result from the ALU back to a memory location or to a register or perhaps an output device.
  8. Jump back to step (1).

Since the program counter is (conceptually) just another set of memory cells, it can be changed by calculations done in the ALU. Adding 100 to the program counter would cause the next instruction to be read from a place 100 locations further down the program. Instructions that modify the program counter are often known as “jumps” and allow for loops (instructions that are repeated by the computer) and often conditional instruction execution (both examples of control flow).

It is noticeable that the sequence of operations that the control unit goes through to process an instruction is in itself like a short computer program—and indeed, in some more complex CPU designs, there is another yet smaller computer called a microsequencer that runs a microcode program that causes all of these events to happen.

[edit] Arithmetic/logic unit (ALU)

Main article: Arithmetic logic unit

The ALU is capable of performing two classes of operations: arithmetic and logic.[22]

The set of arithmetic operations that a particular ALU supports may be limited to adding and subtracting or might include multiplying or dividing, trigonometry functions (sine, cosine, etc) and square roots. Some can only operate on whole numbers (integers) whilst others use floating point to represent real numbers—albeit with limited precision. However, any computer that is capable of performing just the simplest operations can be programmed to break down the more complex operations into simple steps that it can perform. Therefore, any computer can be programmed to perform any arithmetic operation—although it will take more time to do so if its ALU does not directly support the operation. An ALU may also compare numbers and return boolean truth values (true or false) depending on whether one is equal to, greater than or less than the other (“is 64 greater than 65?”).

Logic operations involve Boolean logic: AND, OR, XOR and NOT. These can be useful both for creating complicated conditional statements and processing boolean logic.

Superscalar computers may contain multiple ALUs so that they can process several instructions at the same time.[23] Graphics processors and computers with SIMD and MIMD features often provide ALUs that can perform arithmetic on vectors and matrices.

[edit] Memory

Main article: Computer storage

Magnetic core memory was the computer memory of choice throughout the 1960s, until it was replaced by semiconductor memory.

A computer’s memory can be viewed as a list of cells into which numbers can be placed or read. Each cell has a numbered “address” and can store a single number. The computer can be instructed to “put the number 123 into the cell numbered 1357” or to “add the number that is in cell 1357 to the number that is in cell 2468 and put the answer into cell 1595”. The information stored in memory may represent practically anything. Letters, numbers, even computer instructions can be placed into memory with equal ease. Since the CPU does not differentiate between different types of information, it is the software’s responsibility to give significance to what the memory sees as nothing but a series of numbers.

In almost all modern computers, each memory cell is set up to store binary numbers in groups of eight bits (called a byte). Each byte is able to represent 256 different numbers (2^8 = 256); either from 0 to 255 or -128 to +127. To store larger numbers, several consecutive bytes may be used (typically, two, four or eight). When negative numbers are required, they are usually stored in two’s complement notation. Other arrangements are possible, but are usually not seen outside of specialized applications or historical contexts. A computer can store any kind of information in memory if it can be represented numerically. Modern computers have billions or even trillions of bytes of memory.

The CPU contains a special set of memory cells called registers that can be read and written to much more rapidly than the main memory area. There are typically between two and one hundred registers depending on the type of CPU. Registers are used for the most frequently needed data items to avoid having to access main memory every time data is needed. As data is constantly being worked on, reducing the need to access main memory (which is often slow compared to the ALU and control units) greatly increases the computer’s speed.

Computer main memory comes in two principal varieties: random access memory or RAM and read-only memory or ROM. RAM can be read and written to anytime the CPU commands it, but ROM is pre-loaded with data and software that never changes, so the CPU can only read from it. ROM is typically used to store the computer’s initial start-up instructions. In general, the contents of RAM are erased when the power to the computer is turned off, but ROM retains its data indefinitely. In a PC, the ROM contains a specialized program called the BIOS that orchestrates loading the computer’s operating system from the hard disk drive into RAM whenever the computer is turned on or reset. In embedded computers, which frequently do not have disk drives, all of the required software may be stored in ROM. Software stored in ROM is often called firmware, because it is notionally more like hardware than software. Flash memory blurs the distinction between ROM and RAM, as it retains its data when turned off but is also rewritable. It is typically much slower than conventional ROM and RAM however, so its use is restricted to applications where high speed is unnecessary.[24]

In more sophisticated computers there may be one or more RAM cache memories which are slower than registers but faster than main memory. Generally computers with this sort of cache are designed to move frequently needed data into the cache automatically, often without the need for any intervention on the programmer’s part.

[edit] Input/output (I/O)

Main article: Input/output

Hard disks are common I/O devices used with computers.

I/O is the means by which a computer exchanges information with the outside world.[25] Devices that provide input or output to the computer are called peripherals.[26] On a typical personal computer, peripherals include input devices like the keyboard and mouse, and output devices such as the display and printer. Hard disk drives, floppy disk drives and optical disc drives serve as both input and output devices. Computer networking is another form of I/O.

Often, I/O devices are complex computers in their own right with their own CPU and memory. A graphics processing unit might contain fifty or more tiny computers that perform the calculations necessary to display 3D graphics[citation needed]. Modern desktop computers contain many smaller computers that assist the main CPU in performing I/O.

[edit] Multitasking

Main article: Computer multitasking

While a computer may be viewed as running one gigantic program stored in its main memory, in some systems it is necessary to give the appearance of running several programs simultaneously. This is achieved by multitasking i.e. having the computer switch rapidly between running each program in turn.[27]

One means by which this is done is with a special signal called an interrupt which can periodically cause the computer to stop executing instructions where it was and do something else instead. By remembering where it was executing prior to the interrupt, the computer can return to that task later. If several programs are running “at the same time”, then the interrupt generator might be causing several hundred interrupts per second, causing a program switch each time. Since modern computers typically execute instructions several orders of magnitude faster than human perception, it may appear that many programs are running at the same time even though only one is ever executing in any given instant. This method of multitasking is sometimes termed “time-sharing” since each program is allocated a “slice” of time in turn.[28]

Before the era of cheap computers, the principle use for multitasking was to allow many people to share the same computer.

Seemingly, multitasking would cause a computer that is switching between several programs to run more slowly — in direct proportion to the number of programs it is running. However, most programs spend much of their time waiting for slow input/output devices to complete their tasks. If a program is waiting for the user to click on the mouse or press a key on the keyboard, then it will not take a “time slice” until the event it is waiting for has occurred. This frees up time for other programs to execute so that many programs may be run at the same time without unacceptable speed loss.

[edit] Multiprocessing

Main article: Multiprocessing

Cray designed many supercomputers that used multiprocessing heavily.

Some computers are designed to distribute their work across several CPUs in a multiprocessing configuration, a technique once employed only in large and powerful machines such as supercomputers, mainframe computers and servers. Multiprocessor and multi-core (multiple CPUs on a single integrated circuit) personal and laptop computers are now widely available, and are being increasingly used in lower-end markets as a result.

Supercomputers in particular often have highly unique architectures that differ significantly from the basic stored-program architecture and from general purpose computers.[29] They often feature thousands of CPUs, customized high-speed interconnects, and specialized computing hardware. Such designs tend to be useful only for specialized tasks due to the large scale of program organization required to successfully utilize most of the available resources at once. Supercomputers usually see usage in large-scale simulation, graphics rendering, and cryptography applications, as well as with other so-called “embarrassingly parallel” tasks.

[edit] Networking and the Internet

Main articles: Computer networking and Internet

Visualization of a portion of the routes on the Internet.

Computers have been used to coordinate information between multiple locations since the 1950s. The U.S. military’s SAGE system was the first large-scale example of such a system, which led to a number of special-purpose commercial systems like Sabre.[30]

In the 1970s, computer engineers at research institutions throughout the United States began to link their computers together using telecommunications technology. This effort was funded by ARPA (now DARPA), and the computer network that it produced was called the ARPANET.[31] The technologies that made the Arpanet possible spread and evolved.

In time, the network spread beyond academic and military institutions and became known as the Internet. The emergence of networking involved a redefinition of the nature and boundaries of the computer. Computer operating systems and applications were modified to include the ability to define and access the resources of other computers on the network, such as peripheral devices, stored information, and the like, as extensions of the resources of an individual computer. Initially these facilities were available primarily to people working in high-tech environments, but in the 1990s the spread of applications like e-mail and the World Wide Web, combined with the development of cheap, fast networking technologies like Ethernet and ADSL saw computer networking become almost ubiquitous. In fact, the number of computers that are networked is growing phenomenally. A very large proportion of personal computers regularly connect to the Internet to communicate and receive information. “Wireless” networking, often utilizing mobile phone networks, has meant networking is becoming increasingly ubiquitous even in mobile computing environments.

[edit] Further topics

[edit] Hardware

Main article: Computer hardware

The term hardware covers all of those parts of a computer that are tangible objects. Circuits, displays, power supplies, cables, keyboards, printers and mice are all hardware.

History of computing hardware
First Generation (Mechanical/Electromechanical) Calculators Antikythera mechanism, Difference Engine, Norden bombsight
Programmable Devices Jacquard loom, Analytical Engine, Harvard Mark I, Z3
Second Generation (Vacuum Tubes) Calculators Atanasoff–Berry Computer, IBM 604, UNIVAC 60, UNIVAC 120
Programmable Devices Colossus, ENIAC, Manchester Small-Scale Experimental Machine, EDSAC, Manchester Mark 1, Ferranti Pegasus, Ferranti Mercury, CSIRAC, EDVAC, UNIVAC I, IBM 701, IBM 702, IBM 650, Z22
Third Generation (Discrete transistors and SSI, MSI, LSI Integrated circuits) Mainframes IBM 7090, IBM 7080, System/360, BUNCH
Minicomputer PDP-8, PDP-11, System/32, System/36
Fourth Generation (VLSI integrated circuits) Minicomputer VAX, IBM System i
4-bit microcomputer Intel 4004, Intel 4040
8-bit microcomputer Intel 8008, Intel 8080, Motorola 6800, Motorola 6809, MOS Technology 6502, Zilog Z80
16-bit microcomputer Intel 8088, Zilog Z8000, WDC 65816/65802
32-bit microcomputer Intel 80386, Pentium, Motorola 68000, ARM architecture
64-bit microcomputer[32] Alpha, MIPS, PA-RISC, PowerPC, SPARC, x86-64
Embedded computer Intel 8048, Intel 8051
Personal computer Desktop computer, Home computer, Laptop computer, Personal digital assistant (PDA), Portable computer, Tablet computer, Wearable computer
Theoretical/experimental Quantum computer, Chemical computer, DNA computing, Optical computer, Spintronics based computer
Other Hardware Topics
Peripheral device (Input/output) Input Mouse, Keyboard, Joystick, Image scanner
Output Monitor, Printer
Both Floppy disk drive, Hard disk, Optical disc drive, Teleprinter
Computer busses Short range RS-232, SCSI, PCI, USB
Long range (Computer networking) Ethernet, ATM, FDDI

[edit] Software

Main article: Computer software

Software refers to parts of the computer which do not have a material form, such as programs, data, protocols, etc. When software is stored in hardware that cannot easily be modified (such as BIOS ROM in an IBM PC compatible), it is sometimes called “firmware” to indicate that it falls into an uncertain area somewhere between hardware and software.

Computer software
Operating system Unix and BSD UNIX System V, AIX, HP-UX, Solaris (SunOS), IRIX, List of BSD operating systems
GNU/Linux List of Linux distributions, Comparison of Linux distributions
Microsoft Windows Windows 95, Windows 98, Windows NT, Windows 2000, Windows XP, Windows Vista, Windows CE
DOS 86-DOS (QDOS), PC-DOS, MS-DOS, FreeDOS
Mac OS Mac OS classic, Mac OS X
Embedded and real-time List of embedded operating systems
Experimental Amoeba, Oberon/Bluebottle, Plan 9 from Bell Labs
Library Multimedia DirectX, OpenGL, OpenAL
Programming library C standard library, Standard template library
Data Protocol TCP/IP, Kermit, FTP, HTTP, SMTP
File format HTML, XML, JPEG, MPEG, PNG
User interface Graphical user interface (WIMP) Microsoft Windows, GNOME, KDE, QNX Photon, CDE, GEM
Text-based user interface Command-line interface, Text user interface
Application Office suite Word processing, Desktop publishing, Presentation program, Database management system, Scheduling & Time management, Spreadsheet, Accounting software
Internet Access Browser, E-mail client, Web server, Mail transfer agent, Instant messaging
Design and manufacturing Computer-aided design, Computer-aided manufacturing, Plant management, Robotic manufacturing, Supply chain management
Graphics Raster graphics editor, Vector graphics editor, 3D modeler, Animation editor, 3D computer graphics, Video editing, Image processing
Audio Digital audio editor, Audio playback, Mixing, Audio synthesis, Computer music
Software Engineering Compiler, Assembler, Interpreter, Debugger, Text Editor, Integrated development environment, Performance analysis, Revision control, Software configuration management
Educational Edutainment, Educational game, Serious game, Flight simulator
Games Strategy, Arcade, Puzzle, Simulation, First-person shooter, Platform, Massively multiplayer, Interactive fiction
Misc Artificial intelligence, Antivirus software, Malware scanner, Installer/Package management systems, File manager

[edit] Programming languages

Programming languages provide various ways of specifying programs for computers to run. Unlike natural languages, programming languages are designed to permit no ambiguity and to be concise. They are purely written languages and are often difficult to read aloud. They are generally either translated into machine language by a compiler or an assembler before being run, or translated directly at run time by an interpreter. Sometimes programs are executed by a hybrid method of the two techniques. There are thousands of different programming languages—some intended to be general purpose, others useful only for highly specialized applications.

Programming Languages
Lists of programming languages Timeline of programming languages, Categorical list of programming languages, Generational list of programming languages, Alphabetical list of programming languages, Non-English-based programming languages
Commonly used Assembly languages ARM, MIPS, x86
Commonly used High level languages Ada, BASIC, C, C++, C#, COBOL, Fortran, Java, Lisp, Pascal, Object Pascal
Commonly used Scripting languages Bourne script, JavaScript, Python, Ruby, PHP, Perl

[edit] Professions and organizations

As the use of computers has spread throughout society, there are an increasing number of careers involving computers.

Computer-related professions
Hardware-related Electrical engineering, Electronics engineering, Computer engineering, Telecommunications engineering, Optical engineering, Nanoscale engineering
Software-related Computer science, Desktop publishing, Human-computer interaction, Information technology, Scientific computing, Software engineering, Video game industry, Web design

The need for computers to work well together and to be able to exchange information has spawned the need for many standards organizations, clubs and societies of both a formal and informal nature.

Organizations
Standards groups ANSI, IEC, IEEE, IETF, ISO, W3C
Professional Societies ACM, ACM Special Interest Groups, IET, IFIP
Free/Open source software groups Free Software Foundation, Mozilla Foundation, Apache Software Foundation

[edit] See also

Sister project Look up computer in Wiktionary, the free dictionary.
Sister projectWikiquote has a collection of quotations related to: Computers
Sister projectWikimedia Commons has media related to: Computer
Sister project Wikiversity has learning materials about Introduction to Computers

 

[edit] Notes

  1. ^ In 1946, ENIAC consumed an estimated 174 kW. By comparison, a typical personal computer may use around 400 W; over four hundred times less. (Kempf 1961)
  2. ^ Early computers such as Colossus and ENIAC were able to process between 5 and 100 operations per second. A modern “commodity” microprocessor (as of 2007) can process billions of operations per second, and many of these operations are more complicated and useful than early computer operations.
  3. ^ computer, n., Oxford English Dictionary (2 ed.), Oxford University Press, 1989, http://dictionary.oed.com/, retrieved on 2009-04-10 
  4. ^ “Heron of Alexandria”. http://www.mlahanas.de/Greeks/HeronAlexandria2.htm. Retrieved on 2008-01-15. 
  5. ^ a b Ancient Discoveries, Episode 11: Ancient Robots, History Channel, http://www.youtube.com/watch?v=rxjbaQl0ad8, retrieved on 2008-09-06 
  6. ^ Howard R. Turner (1997), Science in Medieval Islam: An Illustrated Introduction, p. 184, University of Texas Press, ISBN 0-292-78149-0
  7. ^ Donald Routledge Hill, “Mechanical Engineering in the Medieval Near East”, Scientific American, May 1991, pp. 64-9 (cf. Donald Routledge Hill, Mechanical Engineering)
  8. ^ The analytical engine should not be confused with Babbage’s difference engine which was a non-programmable mechanical calculator.
  9. ^ Columbia University Computing History: Herman Hollerith
  10. ^ http://www.time.com/time/time100/scientist/profile/turing.html
  11. ^ “Inventor Profile: George R. Stibitz”. National Inventors Hall of Fame Foundation, Inc.. http://www.invent.org/hall_of_fame/140.html. 
  12. ^ B. Jack Copeland, ed., Colossus: The Secrets of Bletchley Park’s Codebreaking Computers, Oxford University Press, 2006
  13. ^ Lavington 1998, p. 37
  14. ^ This program was written similarly to those for the PDP-11 minicomputer and shows some typical things a computer can do. All the text after the semicolons are comments for the benefit of human readers. These have no significance to the computer and are ignored. (Digital Equipment Corporation 1972)
  15. ^ Attempts are often made to create programs that can overcome this fundamental limitation of computers. Software that mimics learning and adaptation is part of artificial intelligence.
  16. ^ It is not universally true that bugs are solely due to programmer oversight. Computer hardware may fail or may itself have a fundamental problem that produces unexpected results in certain situations. For instance, the Pentium FDIV bug caused some Intel microprocessors in the early 1990s to produce inaccurate results for certain floating point division operations. This was caused by a flaw in the microprocessor design and resulted in a partial recall of the affected devices.
  17. ^ Even some later computers were commonly programmed directly in machine code. Some minicomputers like the DEC PDP-8 could be programmed directly from a panel of switches. However, this method was usually used only as part of the booting process. Most modern computers boot entirely automatically by reading a boot program from some non-volatile memory.
  18. ^ However, there is sometimes some form of machine language compatibility between different computers. An x86-64 compatible microprocessor like the AMD Athlon 64 is able to run most of the same programs that an Intel Core 2 microprocessor can, as well as programs designed for earlier microprocessors like the Intel Pentiums and Intel 80486. This contrasts with very early commercial computers, which were often one-of-a-kind and totally incompatible with other computers.
  19. ^ High level languages are also often interpreted rather than compiled. Interpreted languages are translated into machine code on the fly by another program called an interpreter.
  20. ^ The control unit’s role in interpreting instructions has varied somewhat in the past. Although the control unit is solely responsible for instruction interpretation in most modern computers, this is not always the case. Many computers include some instructions that may only be partially interpreted by the control system and partially interpreted by another device. This is especially the case with specialized computing hardware that may be partially self-contained. For example, EDVAC, one of the earliest stored-program computers, used a central control unit that only interpreted four instructions. All of the arithmetic-related instructions were passed on to its arithmetic unit and further decoded there.
  21. ^ Instructions often occupy more than one memory address, so the program counters usually increases by the number of memory locations required to store one instruction.
  22. ^ David J. Eck (2000). The Most Complex Machine: A Survey of Computers and Computing. A K Peters, Ltd.. p. 54. ISBN 9781568811284. 
  23. ^ Erricos John Kontoghiorghes (2006). Handbook of Parallel Computing and Statistics. CRC Press. p. 45. ISBN 9780824740672. 
  24. ^ Flash memory also may only be rewritten a limited number of times before wearing out, making it less useful for heavy random access usage. (Verma 1988)
  25. ^ Donald Eadie (1968). Introduction to the Basic Computer. Prentice-Hall. p. 12. 
  26. ^ Arpad Barna; Dan I. Porat (1976). Introduction to Microcomputers and the Microprocessors. Wiley. p. 85. ISBN 9780471050513. 
  27. ^ Jerry Peek; Grace Todino, John Strang (2002). Learning the UNIX Operating System: A Concise Guide for the New User. O’Reilly. p. 130. ISBN 9780596002619. 
  28. ^ Gillian M. Davis (2002). Noise Reduction in Speech Applications. CRC Press. p. 111. ISBN 9780849309496. 
  29. ^ However, it is also very common to construct supercomputers out of many pieces of cheap commodity hardware; usually individual computers connected by networks. These so-called computer clusters can often provide supercomputer performance at a much lower cost than customized designs. While custom architectures are still used for most of the most powerful supercomputers, there has been a proliferation of cluster computers in recent years. (TOP500 2006)
  30. ^ Agatha C. Hughes (2000). Systems, Experts, and Computers. MIT Press. p. 161. ISBN 9780262082853. “The experience of SAGE helped make possible the first truly large-scale commercial real-time network: the SABRE computerized airline reservations system…” 
  31. ^ “A Brief History of the Internet”. Internet Society. http://www.isoc.org/internet/history/brief.shtml. Retrieved on 2008-09-20. 
  32. ^ Most major 64-bit instruction set architectures are extensions of earlier designs. All of the architectures listed in this table, except for Alpha, existed in 32-bit forms before their 64-bit incarnations were introduced.

[edit] References

[edit] External links

  

Read Full Post »

Mathematical object

Mathematical object

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In mathematics and its philosophy, a mathematical object is an abstract object arising in mathematics. Commonly encountered mathematical objects include numbers, permutations, partitions, matrices, sets, functions, and relations. Geometry as a branch of mathematics has such objects as points, lines, triangles, circles, spheres, polyhedra, topological spaces and manifolds. Algebra, another branch, has groups, rings, fields, group-theoretic lattices and order-theoretic lattices. Categories are simultaneously homes to mathematical objects and mathematical objects in their own right.

The ontological status of mathematical objects has been apart of a long dispute as the subject of much investigation and debate by philosophers of mathematics. On this debate, see the monograph by Burgess and Rosen (1997).

One view that emerged around the turn of the 20th century with the work of Cantor is that all mathematical objects can be defined as sets. The set {0,1} is a relatively clear-cut example. On the face of it the group Z2 of integers mod 2 is also a set with two elements. However it cannot simply be the set {0,1} because this does not mention the additional structure imputed to Z2 by its operations of addition and negation mod 2: how are we to tell which of 0 or 1 is the additive identity, for example? To organize this group as a set it can first be coded as the quadruple ({0,1},+,−,0), which in turn can be coded using one of several conventions as a set representing that quadruple, which in turn entails encoding the operations + and − and the constant 0 as sets.

This approach to the ontology of mathematics raises a fundamental philosophical question of whether the ontology of mathematics needs to be beholden to either its practice or its pedagogy. Mathematicians do not work with such codings, which are neither canonical nor practical. They do not appear in any algebra texts, and neither students nor instructors in algebra courses have any familiarity with such codings. Hence if ontology is to reflect practice, mathematical objects cannot be reduced to sets in this way.

If however the goal of mathematical ontology is taken to be the internal consistency of mathematics, it is more important that mathematical objects be definable in some uniform way, for example as sets, regardless of actual practice in order to lay bare the essence of its paradoxes. This has been the viewpoint taken by foundations of mathematics, which has traditionally accorded the management of paradox higher priority than the faithful reflection of the details of mathematical practice as a justification for defining mathematical objects to be sets.

Much of the tension created by this foundational identification of mathematical objects with sets can be relieved without unduly compromising the goals of foundations by allowing two kinds of objects into the mathematical universe, sets and relations, without requiring that either be considered merely an instance of the other. These form the basis of model theory as the domain of discourse of predicate logic. In this viewpoint mathematical objects are entities satisfying the axioms of a formal theory expressed in the language of predicate logic.

A variant of this approach replaces relations with operations, the basis of universal algebra. In this variant the axioms often take the form of equations, or implications between equations.

A more abstract variant is category theory, which abstracts sets as objects and the operations thereon as morphisms between those objects. At this level of abstraction mathematical objects reduce to mere vertices of a graph whose edges as the morphisms abstract the ways in which those objects can transform and whose structure is encoded in the composition law for morphisms. Categories may arise as the models of some axiomatic theory and the homomorphisms between them (in which case they are usually concrete, meaning equipped with a faithful forgetful functor to the category Set or more generally to a suitable topos), or they may be constructed from other more primitive categories, or they may be studied as abstract objects in their own right without regard for their provenance.

[edit] References

  • Azzouni, J., 1994. Metaphysical Myths, Mathematical Practice. Cambridge University Press.
  • Burgess, John, and Rosen, Gideon, 1997. A Subject with No Object. Oxford Univ. Press.
  • Davis, Philip and Hersh, Reuben, 1999 [1981]. The Mathematical Experience. Mariner Books: 156-62.
  • Gold, Bonnie, and Simons, Roger A., 2008. Proof and Other Dilemmas: Mathematics and Philosophy. Mathematical Association of America.
  • Hersh, Reuben, 1997. What is Mathematics, Really? Oxford University Press.
  • Sfard, A., 2000, “Symbolizing mathematical reality into being, Or how mathematical discourse and mathematical objects create each other,” in Cobb, P., et al., Symbolizing and communicating in mathematics classrooms: Perspectives on discourse, tools and instructional design. Lawrence Erlbaum.
  • Stewart Shapiro, 2000. Thinking about mathematics: The philosophy of mathematics. Oxford University Press.

[edit] External links

Read Full Post »

Algorithm

Algorithm

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Flowcharts are often used to graphically represent algorithms.

In mathematics, computing, linguistics, and related subjects, an algorithm is a finite sequence of instructions, an explicit, step-by-step procedure for solving a problem, often used for calculation and data processing. It is formally a type of effective method in which a list of well-defined instructions for completing a task, will when given an initial state, proceed through a well-defined series of successive states, eventually terminating in an end-state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as probabilistic algorithms, incorporate randomness.

A partial formalization of the concept began with attempts to solve the Entscheidungsproblem (the “decision problem”) posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define “effective calculability” (Kleene 1943:274) or “effective method” (Rosser 1939:225); those formalizations included the Gödel-Herbrand-Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church‘s lambda calculus of 1936, Emil Post’s “Formulation 1” of 1936, and Alan Turing‘s Turing machines of 1936–7 and 1939.

Contents

[hide]

[edit] Etymology

Al-Khwārizmī, Persian astronomer and mathematician, wrote a treatise in 825 AD, On Calculation with Hindu Numerals. (See algorism). It was translated into Latin in the 12th century as Algoritmi de numero Indorum (al-Daffa 1977), whose title was likely intended to mean “Algoritmi on the numbers of the Indians”, where “Algoritmi” was the translator’s rendition of the author’s name; but people misunderstanding the title treated Algoritmi as a Latin plural and this led to the word “algorithm” (Latin algorismus) coming to mean “calculation method”. The intrusive “th” is most likely due to a false cognate with the Greek ἀριθμός (arithmos) meaning “number”.

[edit] Why algorithms are necessary: an informal definition

For a detailed presentation of the various points of view around the definition of “algorithm” see Algorithm characterizations. For examples of simple addition algorithms specified in the detailed manner described in Algorithm characterizations, see Algorithm examples.

While there is no generally accepted formal definition of “algorithm”, an informal definition could be “a process that performs some sequence of operations.” For some people, a program is only an algorithm if it stops eventually. For others, a program is only an algorithm if it stops before a given number of calculation steps.

A prototypical example of an “algorithm” is Euclid’s algorithm to determine the maximum common divisor of two integers (X and Y) which are greater than one: We follow a series of steps: In step i, we divide X by Y and find the remainder, which we call R1. Then we move to step i + 1, where we divide Y by R1, and find the remainder, which we call R2. If R2=0, we stop and say that R1 is the greatest common divisor of X and Y. If not, we continue, until Rn=0. Then Rn-1 is the max common division of X and Y. This procedure is known to stop always and the number of subtractions needed is always smaller than the larger of the two numbers.

We can derive clues to the issues involved and an informal meaning of the word from the following quotation from Boolos & Jeffrey (1974, 1999) (boldface added):

No human being can write fast enough or long enough or small enough to list all members of an enumerably infinite set by writing out their names, one after another, in some notation. But humans can do something equally useful, in the case of certain enumerably infinite sets: They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols (Boolos & Jeffrey 1974, 1999, p. 19)

The words “enumerably infinite” mean “countable using integers perhaps extending to infinity.” Thus Boolos and Jeffrey are saying that an algorithm implies instructions for a process that “creates” output integers from an arbitrary “input” integer or integers that, in theory, can be chosen from 0 to infinity. Thus we might expect an algorithm to be an algebraic equation such as y = m + n — two arbitrary “input variables” m and n that produce an output y. As we see in Algorithm characterizations — the word algorithm implies much more than this, something on the order of (for our addition example):

Precise instructions (in language understood by “the computer”) for a “fast, efficient, good” process that specifies the “moves” of “the computer” (machine or human, equipped with the necessary internally-contained information and capabilities) to find, decode, and then munch arbitrary input integers/symbols m and n, symbols + and = … and (reliably, correctly, “effectively”) produce, in a “reasonable” time, output-integer y at a specified place and in a specified format.

The concept of algorithm is also used to define the notion of decidability. That notion is central for explaining how formal systems come into being starting from a small set of axioms and rules. In logic, the time that an algorithm requires to complete cannot be measured, as it is not apparently related with our customary physical dimension. From such uncertainties, that characterize ongoing work, stems the unavailability of a definition of algorithm that suits both concrete (in some sense) and abstract usage of the term.

[edit] Formalization

Algorithms are essential to the way computers process information. Many computer programs contain algorithms that specify the specific instructions a computer should perform (in a specific order) to carry out a specified task, such as calculating employees’ paychecks or printing students’ report cards. Thus, an algorithm can be considered to be any sequence of operations that can be simulated by a Turing-complete system. Authors who assert this thesis include Savage (1987) and Gurevich (2000):

…Turing’s informal argument in favor of his thesis justifies a stronger thesis: every algorithm can be simulated by a Turing machine (Gurevich 2000:1)…according to Savage [1987], an algorithm is a computational process defined by a Turing machine. (Gurevich 2000:3)

Typically, when an algorithm is associated with processing information, data is read from an input source, written to an output device, and/or stored for further processing. Stored data is regarded as part of the internal state of the entity performing the algorithm. In practice, the state is stored in one or more data structures.

For any such computational process, the algorithm must be rigorously defined: specified in the way it applies in all possible circumstances that could arise. That is, any conditional steps must be systematically dealt with, case-by-case; the criteria for each case must be clear (and computable).

Because an algorithm is a precise list of precise steps, the order of computation will always be critical to the functioning of the algorithm. Instructions are usually assumed to be listed explicitly, and are described as starting “from the top” and going “down to the bottom”, an idea that is described more formally by flow of control.

So far, this discussion of the formalization of an algorithm has assumed the premises of imperative programming. This is the most common conception, and it attempts to describe a task in discrete, “mechanical” means. Unique to this conception of formalized algorithms is the assignment operation, setting the value of a variable. It derives from the intuition of “memory” as a scratchpad. There is an example below of such an assignment.

For some alternate conceptions of what constitutes an algorithm see functional programming and logic programming .

[edit] Termination

Some writers restrict the definition of algorithm to procedures that eventually finish. In such a category Kleene places the “decision procedure or decision method or algorithm for the question” (Kleene 1952:136). Others, including Kleene, include procedures that could run forever without stopping; such a procedure has been called a “computational method” (Knuth 1997:5) or “calculation procedure or algorithm” (Kleene 1952:137); however, Kleene notes that such a method must eventually exhibit “some object” (Kleene 1952:137).

Minsky makes the pertinent observation, in regards to determining whether an algorithm will eventually terminate (from a particular starting state):

But if the length of the process is not known in advance, then “trying” it may not be decisive, because if the process does go on forever — then at no time will we ever be sure of the answer (Minsky 1967:105).

As it happens, no other method can do any better, as was shown by Alan Turing with his celebrated result on the undecidability of the so-called halting problem. There is no algorithmic procedure for determining of arbitrary algorithms whether or not they terminate from given starting states. The analysis of algorithms for their likelihood of termination is called termination analysis.

See the examples of (im-)”proper” subtraction at partial function for more about what can happen when an algorithm fails for certain of its input numbers — e.g., (i) non-termination, (ii) production of “junk” (output in the wrong format to be considered a number) or no number(s) at all (halt ends the computation with no output), (iii) wrong number(s), or (iv) a combination of these. Kleene proposed that the production of “junk” or failure to produce a number is solved by having the algorithm detect these instances and produce e.g., an error message (he suggested “0”), or preferably, force the algorithm into an endless loop (Kleene 1952:322). Davis does this to his subtraction algorithm — he fixes his algorithm in a second example so that it is proper subtraction (Davis 1958:12-15). Along with the logical outcomes “true” and “false” Kleene also proposes the use of a third logical symbol “u” — undecided (Kleene 1952:326) — thus an algorithm will always produce something when confronted with a “proposition”. The problem of wrong answers must be solved with an independent “proof” of the algorithm e.g., using induction:

We normally require auxiliary evidence for this (that the algorithm correctly defines a mu recursive function), e.g., in the form of an inductive proof that, for each argument value, the computation terminates with a unique value (Minsky 1967:186).

[edit] Expressing algorithms

Algorithms can be expressed in many kinds of notation, including natural languages, pseudocode, flowcharts, and programming languages. Natural language expressions of algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical algorithms. Pseudocode and flowcharts are structured ways to express algorithms that avoid many of the ambiguities common in natural language statements, while remaining independent of a particular implementation language. Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer, but are often used as a way to define or document algorithms.

There is a wide variety of representations possible and one can express a given Turing machine program as a sequence of machine tables (see more at finite state machine and state transition table), as flowcharts (see more at state diagram), or as a form of rudimentary machine code or assembly code called “sets of quadruples” (see more at Turing machine).

Sometimes it is helpful in the description of an algorithm to supplement small “flow charts” (state diagrams) with natural-language and/or arithmetic expressions written inside “block diagrams” to summarize what the “flow charts” are accomplishing.

Representations of algorithms are generally classed into three accepted levels of Turing machine description (Sipser 2006:157):

  • 1 High-level description:
“…prose to describe an algorithm, ignoring the implementation details. At this level we do not need to mention how the machine manages its tape or head”
  • 2 Implementation description:
“…prose used to define the way the Turing machine uses its head and the way that it stores data on its tape. At this level we do not give details of states or transition function”
  • 3 Formal description:
Most detailed, “lowest level”, gives the Turing machine’s “state table”.
For an example of the simple algorithm “Add m+n” described in all three levels see Algorithm examples.

[edit] Implementation

Most algorithms are intended to be implemented as computer programs. However, algorithms are also implemented by other means, such as in a biological neural network (for example, the human brain implementing arithmetic or an insect looking for food), in an electrical circuit, or in a mechanical device.

[edit] Example

An animation of the quicksort algorithm sorting an array of randomized values. The red bars mark the pivot element; at the start of the animation, the element farthest to the right hand side is chosen as the pivot.

One of the simplest algorithms is to find the largest number in an (unsorted) list of numbers. The solution necessarily requires looking at every number in the list, but only once at each. From this follows a simple algorithm, which can be stated in a high-level description English prose, as:

High-level description:

  1. Assume the first item is largest.
  2. Look at each of the remaining items in the list and if it is larger than the largest item so far, make a note of it.
  3. The last noted item is the largest in the list when the process is complete.

(Quasi-)formal description: Written in prose but much closer to the high-level language of a computer program, the following is the more formal coding of the algorithm in pseudocode or pidgin code:

Algorithm LargestNumber
  Input: A non-empty list of numbers L.
  Output: The largest number in the list L.

  largestL0
  for each item in the list L≥1, do
    if the item > largest, then
      largest ← the item
  return largest
  • “←” is a loose shorthand for “changes to”. For instance, “largestitem” means that the value of largest changes to the value of item.
  • return” terminates the algorithm and outputs the value that follows.

For a more complex example of an algorithm, see Euclid’s algorithm for the greatest common divisor, one of the earliest algorithms known.

[edit] Algorithmic analysis

It is frequently important to know how much of a particular resource (such as time or storage) is required for a given algorithm. Methods have been developed for the analysis of algorithms to obtain such quantitative answers; for example, the algorithm above has a time requirement of O(n), using the big O notation with n as the length of the list. At all times the algorithm only needs to remember two values: the largest number found so far, and its current position in the input list. Therefore it is said to have a space requirement of O(1), if the space required to store the input numbers is not counted, or O(n) if it is counted.

Different algorithms may complete the same task with a different set of instructions in less or more time, space, or ‘effort’ than others. For example, a binary search algorithm will usually outperform a brute force sequential search when used for table lookups on sorted lists.

[edit] Abstract versus empirical

The analysis and study of algorithms is a discipline of computer science, and is often practiced abstractly without the use of a specific programming language or implementation. In this sense, algorithm analysis resembles other mathematical disciplines in that it focuses on the underlying properties of the algorithm and not on the specifics of any particular implementation. Usually pseudocode is used for analysis as it is the simplest and most general representation. However, ultimately, most algorithms are usually implemented on particular hardware / software platforms and their algorithmic efficiency is eventually put to the test using real code.

Empirical testing is useful because it may uncover unexpected interactions that affect performance. For instance an algorithm that has no locality of reference may have much poorer performance than predicted because it thrashes the cache.

[edit] Classification

There are various ways to classify algorithms, each with its own merits.

[edit] By implementation

One way to classify algorithms is by implementation means.

  • Recursion or iteration: A recursive algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition matches, which is a method common to functional programming. Iterative algorithms use repetitive constructs like loops and sometimes additional data structures like stacks to solve the given problems. Some problems are naturally suited for one implementation or the other. For example, towers of Hanoi is well understood in recursive implementation. Every recursive version has an equivalent (but possibly more or less complex) iterative version, and vice versa.
  • Logical: An algorithm may be viewed as controlled logical deduction. This notion may be expressed as: Algorithm = logic + control (Kowalski 1979). The logic component expresses the axioms that may be used in the computation and the control component determines the way in which deduction is applied to the axioms. This is the basis for the logic programming paradigm. In pure logic programming languages the control component is fixed and algorithms are specified by supplying only the logic component. The appeal of this approach is the elegant semantics: a change in the axioms has a well defined change in the algorithm.
  • Serial or parallel or distributed: Algorithms are usually discussed with the assumption that computers execute one instruction of an algorithm at a time. Those computers are sometimes called serial computers. An algorithm designed for such an environment is called a serial algorithm, as opposed to parallel algorithms or distributed algorithms. Parallel algorithms take advantage of computer architectures where several processors can work on a problem at the same time, whereas distributed algorithms utilize multiple machines connected with a network. Parallel or distributed algorithms divide the problem into more symmetrical or asymmetrical subproblems and collect the results back together. The resource consumption in such algorithms is not only processor cycles on each processor but also the communication overhead between the processors. Sorting algorithms can be parallelized efficiently, but their communication overhead is expensive. Iterative algorithms are generally parallelizable. Some problems have no parallel algorithms, and are called inherently serial problems.
  • Deterministic or non-deterministic: Deterministic algorithms solve the problem with exact decision at every step of the algorithm whereas non-deterministic algorithms solve problems via guessing although typical guesses are made more accurate through the use of heuristics.
  • Exact or approximate: While many algorithms reach an exact solution, approximation algorithms seek an approximation that is close to the true solution. Approximation may use either a deterministic or a random strategy. Such algorithms have practical value for many hard problems.

[edit] By design paradigm

Another way of classifying algorithms is by their design methodology or paradigm. There is a certain number of paradigms, each different from the other. Furthermore, each of these categories will include many different types of algorithms. Some commonly found paradigms include:

  • Divide and conquer. A divide and conquer algorithm repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually recursively) until the instances are small enough to solve easily. One such example of divide and conquer is merge sorting. Sorting can be done on each segment of data after dividing data into segments and sorting of entire data can be obtained in the conquer phase by merging the segments. A simpler variant of divide and conquer is called a decrease and conquer algorithm, that solves an identical subproblem and uses the solution of this subproblem to solve the bigger problem. Divide and conquer divides the problem into multiple subproblems and so the conquer stage will be more complex than decrease and conquer algorithms. An example of decrease and conquer algorithm is the binary search algorithm.
  • Dynamic programming. When a problem shows optimal substructure, meaning the optimal solution to a problem can be constructed from optimal solutions to subproblems, and overlapping subproblems, meaning the same subproblems are used to solve many different problem instances, a quicker approach called dynamic programming avoids recomputing solutions that have already been computed. For example, the shortest path to a goal from a vertex in a weighted graph can be found by using the shortest path to the goal from all adjacent vertices. Dynamic programming and memoization go together. The main difference between dynamic programming and divide and conquer is that subproblems are more or less independent in divide and conquer, whereas subproblems overlap in dynamic programming. The difference between dynamic programming and straightforward recursion is in caching or memoization of recursive calls. When subproblems are independent and there is no repetition, memoization does not help; hence dynamic programming is not a solution for all complex problems. By using memoization or maintaining a table of subproblems already solved, dynamic programming reduces the exponential nature of many problems to polynomial complexity.
  • The greedy method. A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the subproblems do not have to be known at each stage; instead a “greedy” choice can be made of what looks best for the moment. The greedy method extends the solution with the best possible decision (not all feasible decisions) at an algorithmic stage based on the current local optimum and the best decision (not all possible decisions) made in a previous stage. It is not exhaustive, and does not give accurate answer to many problems. But when it works, it will be the fastest method. The most popular greedy algorithm is finding the minimal spanning tree as given by Kruskal.
  • Linear programming. When solving a problem using linear programming, specific inequalities involving the inputs are found and then an attempt is made to maximize (or minimize) some linear function of the inputs. Many problems (such as the maximum flow for directed graphs) can be stated in a linear programming way, and then be solved by a ‘generic’ algorithm such as the simplex algorithm. A more complex variant of linear programming is called integer programming, where the solution space is restricted to the integers.
  • Reduction. This technique involves solving a difficult problem by transforming it into a better known problem for which we have (hopefully) asymptotically optimal algorithms. The goal is to find a reducing algorithm whose complexity is not dominated by the resulting reduced algorithm’s. For example, one selection algorithm for finding the median in an unsorted list involves first sorting the list (the expensive portion) and then pulling out the middle element in the sorted list (the cheap portion). This technique is also known as transform and conquer.
  • Search and enumeration. Many problems (such as playing chess) can be modeled as problems on graphs. A graph exploration algorithm specifies rules for moving around a graph and is useful for such problems. This category also includes search algorithms, branch and bound enumeration and backtracking.
  • The probabilistic and heuristic paradigm. Algorithms belonging to this class fit the definition of an algorithm more loosely.
  1. Probabilistic algorithms are those that make some choices randomly (or pseudo-randomly); for some problems, it can in fact be proven that the fastest solutions must involve some randomness.
  2. Genetic algorithms attempt to find solutions to problems by mimicking biological evolutionary processes, with a cycle of random mutations yielding successive generations of “solutions”. Thus, they emulate reproduction and “survival of the fittest”. In genetic programming, this approach is extended to algorithms, by regarding the algorithm itself as a “solution” to a problem.
  3. Heuristic algorithms, whose general purpose is not to find an optimal solution, but an approximate solution where the time or resources are limited. They are not practical to find perfect solutions. An example of this would be local search, tabu search, or simulated annealing algorithms, a class of heuristic probabilistic algorithms that vary the solution of a problem by a random amount. The name “simulated annealing” alludes to the metallurgic term meaning the heating and cooling of metal to achieve freedom from defects. The purpose of the random variance is to find close to globally optimal solutions rather than simply locally optimal ones, the idea being that the random element will be decreased as the algorithm settles down to a solution.

[edit] By field of study

Every field of science has its own problems and needs efficient algorithms. Related problems in one field are often studied together. Some example classes are search algorithms, sorting algorithms, merge algorithms, numerical algorithms, graph algorithms, string algorithms, computational geometric algorithms, combinatorial algorithms, machine learning, cryptography, data compression algorithms and parsing techniques.

Fields tend to overlap with each other, and algorithm advances in one field may improve those of other, sometimes completely unrelated, fields. For example, dynamic programming was originally invented for optimization of resource consumption in industry, but is now used in solving a broad range of problems in many fields.

[edit] By complexity

Algorithms can be classified by the amount of time they need to complete compared to their input size. There is a wide variety: some algorithms complete in linear time relative to input size, some do so in an exponential amount of time or even worse, and some never halt. Additionally, some problems may have multiple algorithms of differing complexity, while other problems might have no algorithms or no known efficient algorithms. There are also mappings from some problems to other problems. Owing to this, it was found to be more suitable to classify the problems themselves instead of the algorithms into equivalence classes based on the complexity of the best possible algorithms for them.

[edit] By computing power

Another way to classify algorithms is by computing power. This is typically done by considering some collection (class) of algorithms. A recursive class of algorithms is one that includes algorithms for all Turing computable functions. Looking at classes of algorithms allows for the possibility of restricting the available computational resources (time and memory) used in a computation. A subrecursive class of algorithms is one in which not all Turing computable functions can be obtained. For example, the algorithms that run in polynomial time suffice for many important types of computation but do not exhaust all Turing computable functions. The class of algorithms implemented by primitive recursive functions is another subrecursive class.

Burgin (2005, p. 24) uses a generalized definition of algorithms that relaxes the common requirement that the output of the algorithm that computes a function must be determined after a finite number of steps. He defines a super-recursive class of algorithms as “a class of algorithms in which it is possible to compute functions not computable by any Turing machine” (Burgin 2005, p. 107). This is closely related to the study of methods of hypercomputation.

[edit] Legal issues

See also: Software patents for a general overview of the patentability of software, including computer-implemented algorithms.

Algorithms, by themselves, are not usually patentable. In the United States, a claim consisting solely of simple manipulations of abstract concepts, numbers, or signals does not constitute “processes” (USPTO 2006), and hence algorithms are not patentable (as in Gottschalk v. Benson). However, practical applications of algorithms are sometimes patentable. For example, in Diamond v. Diehr, the application of a simple feedback algorithm to aid in the curing of synthetic rubber was deemed patentable. The patenting of software is highly controversial, and there are highly criticized patents involving algorithms, especially data compression algorithms, such as UnisysLZW patent.

Additionally, some cryptographic algorithms have export restrictions (see export of cryptography).

[edit] History: Development of the notion of “algorithm”

[edit] Origin of the word

The word algorithm comes from the name of the 9th century Persian mathematician Abu Abdullah Muhammad ibn Musa al-Khwarizmi whose works introduced Indian numerals and algebraic concepts. He worked in Baghdad at the time when it was the centre of scientific studies and trade. The word algorism originally referred only to the rules of performing arithmetic using Arabic numerals but evolved via European Latin translation of al-Khwarizmi’s name into algorithm by the 18th century. The word evolved to include all definite procedures for solving problems or performing tasks.

[edit] Discrete and distinguishable symbols

Tally-marks: To keep track of their flocks, their sacks of grain and their money the ancients used tallying: accumulating stones or marks scratched on sticks, or making discrete symbols in clay. Through the Babylonian and Egyptian use of marks and symbols, eventually Roman numerals and the abacus evolved (Dilson, p.16–41). Tally marks appear prominently in unary numeral system arithmetic used in Turing machine and Post-Turing machine computations.

[edit] Manipulation of symbols as “place holders” for numbers: algebra

The work of the ancient Greek geometers, Persian mathematician Al-Khwarizmi (often considered the “father of algebra” and from whose name the terms “algorism” and “algorithm” are derived), and Western European mathematicians culminated in Leibniz’s notion of the calculus ratiocinator (ca 1680):

“A good century and a half ahead of his time, Leibniz proposed an algebra of logic, an algebra that would specify the rules for manipulating logical concepts in the manner that ordinary algebra specifies the rules for manipulating numbers” (Davis 2000:1)

[edit] Mechanical contrivances with discrete states

The clock: Bolter credits the invention of the weight-driven clock as “The key invention [of Europe in the Middle Ages]”, in particular the verge escapement (Bolter 1984:24) that provides us with the tick and tock of a mechanical clock. “The accurate automatic machine” (Bolter 1984:26) led immediately to “mechanical automata” beginning in the thirteenth century and finally to “computational machines” – the difference engine and analytical engines of Charles Babbage and Countess Ada Lovelace (Bolter p.33–34, p.204–206).

Jacquard loom, Hollerith punch cards, telegraphy and telephony — the electromechanical relay: Bell and Newell (1971) indicate that the Jacquard loom (1801), precursor to Hollerith cards (punch cards, 1887), and “telephone switching technologies” were the roots of a tree leading to the development of the first computers (Bell and Newell diagram p. 39, cf. Davis 2000). By the mid-1800s the telegraph, the precursor of the telephone, was in use throughout the world, its discrete and distinguishable encoding of letters as “dots and dashes” a common sound. By the late 1800s the ticker tape (ca 1870s) was in use, as was the use of Hollerith cards in the 1890 U.S. census. Then came the Teletype (ca. 1910) with its punched-paper use of Baudot code on tape.

Telephone-switching networks of electromechanical relays (invented 1835) was behind the work of George Stibitz (1937), the inventor of the digital adding device. As he worked in Bell Laboratories, he observed the “burdensome’ use of mechanical calculators with gears. “He went home one evening in 1937 intending to test his idea… When the tinkering was over, Stibitz had constructed a binary adding device”. (Valley News, p. 13).

Davis (2000) observes the particular importance of the electromechanical relay (with its two “binary states” open and closed):

It was only with the development, beginning in the 1930s, of electromechanical calculators using electrical relays, that machines were built having the scope Babbage had envisioned.” (Davis, p. 14).

[edit] Mathematics during the 1800s up to the mid-1900s

Symbols and rules: In rapid succession the mathematics of George Boole (1847, 1854), Gottlob Frege (1879), and Giuseppe Peano (1888–1889) reduced arithmetic to a sequence of symbols manipulated by rules. Peano’s The principles of arithmetic, presented by a new method (1888) was “the first attempt at an axiomatization of mathematics in a symbolic language” (van Heijenoort:81ff).

But Heijenoort gives Frege (1879) this kudos: Frege’s is “perhaps the most important single work ever written in logic. … in which we see a ” ‘formula language’, that is a lingua characterica, a language written with special symbols, “for pure thought”, that is, free from rhetorical embellishments … constructed from specific symbols that are manipulated according to definite rules” (van Heijenoort:1). The work of Frege was further simplified and amplified by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica (1910–1913).

The paradoxes: At the same time a number of disturbing paradoxes appeared in the literature, in particular the Burali-Forti paradox (1897), the Russell paradox (1902–03), and the Richard Paradox (Dixon 1906, cf. Kleene 1952:36–40). The resultant considerations led to Kurt Gödel’s paper (1931) — he specifically cites the paradox of the liar — that completely reduces rules of recursion to numbers.

Effective calculability: In an effort to solve the Entscheidungsproblem defined precisely by Hilbert in 1928, mathematicians first set about to define what was meant by an “effective method” or “effective calculation” or “effective calculability” (i.e., a calculation that would succeed). In rapid succession the following appeared: Alonzo Church, Stephen Kleene and J.B. Rosser’s λ-calculus, (cf. footnote in Alonzo Church 1936a:90, 1936b:110) a finely-honed definition of “general recursion” from the work of Gödel acting on suggestions of Jacques Herbrand (cf. Gödel’s Princeton lectures of 1934) and subsequent simplifications by Kleene (1935-6:237ff, 1943:255ff). Church’s proof (1936:88ff) that the Entscheidungsproblem was unsolvable, Emil Post’s definition of effective calculability as a worker mindlessly following a list of instructions to move left or right through a sequence of rooms and while there either mark or erase a paper or observe the paper and make a yes-no decision about the next instruction (cf. “Formulation I”, Post 1936:289-290). Alan Turing‘s proof of that the Entscheidungsproblem was unsolvable by use of his “a- [automatic-] machine”(Turing 1936-7:116ff) — in effect almost identical to Post’s “formulation”, J. Barkley Rosser‘s definition of “effective method” in terms of “a machine” (Rosser 1939:226). S. C. Kleene’s proposal of a precursor to “Church thesis” that he called “Thesis I” (Kleene 1943:273–274), and a few years later Kleene’s renaming his Thesis “Church’s Thesis” (Kleene 1952:300, 317) and proposing “Turing’s Thesis” (Kleene 1952:376).

[edit] Emil Post (1936) and Alan Turing (1936-7, 1939)

Here is a remarkable coincidence of two men not knowing each other but describing a process of men-as-computers working on computations — and they yield virtually identical definitions.

Emil Post (1936) described the actions of a “computer” (human being) as follows:

“…two concepts are involved: that of a symbol space in which the work leading from problem to answer is to be carried out, and a fixed unalterable set of directions.

His symbol space would be

“a two way infinite sequence of spaces or boxes… The problem solver or worker is to move and work in this symbol space, being capable of being in, and operating in but one box at a time…. a box is to admit of but two possible conditions, i.e., being empty or unmarked, and having a single mark in it, say a vertical stroke.
“One box is to be singled out and called the starting point. …a specific problem is to be given in symbolic form by a finite number of boxes [i.e., INPUT] being marked with a stroke. Likewise the answer [i.e., OUTPUT] is to be given in symbolic form by such a configuration of marked boxes….
“A set of directions applicable to a general problem sets up a deterministic process when applied to each specific problem. This process will terminate only when it comes to the direction of type (C ) [i.e., STOP].” (U p. 289–290) See more at Post-Turing machine

Alan Turing’s work (1936, 1939:160) preceded that of Stibitz (1937); it is unknown whether Stibitz knew of the work of Turing. Turing’s biographer believed that Turing’s use of a typewriter-like model derived from a youthful interest: “Alan had dreamt of inventing typewriters as a boy; Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter ‘mechanical'” (Hodges, p. 96). Given the prevalence of Morse code and telegraphy, ticker tape machines, and Teletypes we might conjecture that all were influences.

Turing — his model of computation is now called a Turing machine — begins, as did Post, with an analysis of a human computer that he whittles down to a simple set of basic motions and “states of mind”. But he continues a step further and creates a machine as a model of computation of numbers (Turing 1936-7:116).

“Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child’s arithmetic book….I assume then that the computation is carried out on one-dimensional paper, i.e., on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite….
“The behavior of the computer at any moment is determined by the symbols which he is observing, and his “state of mind” at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite…
“Let us imagine that the operations performed by the computer to be split up into ‘simple operations’ which are so elementary that it is not easy to imagine them further divided” (Turing 1936-7:136).

Turing’s reduction yields the following:

“The simple operations must therefore include:

“(a) Changes of the symbol on one of the observed squares
“(b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares.

“It may be that some of these change necessarily invoke a change of state of mind. The most general single operation must therefore be taken to be one of the following:

“(A) A possible change (a) of symbol together with a possible change of state of mind.
“(B) A possible change (b) of observed squares, together with a possible change of state of mind”
“We may now construct a machine to do the work of this computer.” (Turing 1936-7:136)

A few years later, Turing expanded his analysis (thesis, definition) with this forceful expression of it:

“A function is said to be “effectively calculable” if its values can be found by some purely mechanical process. Although it is fairly easy to get an intuitive grasp of this idea, it is nevertheless desirable to have some more definite, mathematical expressible definition . . . [he discusses the history of the definition pretty much as presented above with respect to Gödel, Herbrand, Kleene, Church, Turing and Post] . . . We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author’s definition of a computable function, and to an identification of computability † with effective calculability . . . .

“† We shall use the expression “computable function” to mean a function calculable by a machine, and we let “effectively calculable” refer to the intuitive idea without particular identification with any one of these definitions.”(Turing 1939:160)

[edit] J. B. Rosser (1939) and S. C. Kleene (1943)

J. Barkley Rosser boldly defined an ‘effective [mathematical] method’ in the following manner (boldface added):

“‘Effective method’ is used here in the rather special sense of a method each step of which is precisely determined and which is certain to produce the answer in a finite number of steps. With this special meaning, three different precise definitions have been given to date. [his footnote #5; see discussion immediately below]. The simplest of these to state (due to Post and Turing) says essentially that an effective method of solving certain sets of problems exists if one can build a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer. All three definitions are equivalent, so it doesn’t matter which one is used. Moreover, the fact that all three are equivalent is a very strong argument for the correctness of any one.” (Rosser 1939:225–6)

Rosser’s footnote #5 references the work of (1) Church and Kleene and their definition of λ-definability, in particular Church’s use of it in his An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand and Gödel and their use of recursion in particular Gödel’s use in his famous paper On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931); and (3) Post (1936) and Turing (1936-7) in their mechanism-models of computation.

Stephen C. Kleene defined as his now-famous “Thesis I” known as the Church-Turing thesis. But he did this in the following context (boldface in original):

“12. Algorithmic theories… In setting up a complete algorithmic theory, what we do is to describe a procedure, performable for each set of values of the independent variables, which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, “yes” or “no,” to the question, “is the predicate value true?”” (Kleene 1943:273)

[edit] History after 1950

A number of efforts have been directed toward further refinement of the definition of “algorithm”, and activity is on-going because of issues surrounding, in particular, foundations of mathematics (especially the Church-Turing Thesis) and philosophy of mind (especially arguments around artificial intelligence). For more, see Algorithm characterizations.

[edit] See also

Sister projectWikibooks has a book on the topic of

Sister project At Wikiversity you can learn more and teach others about Algorithm at:

[edit] References

  • Axt, P. (1959) On a Subrecursive Hierarchy and Primitive Recursive Degrees, Transactions of the American Mathematical Society 92, pp. 85–105
  • Blass, Andreas; Gurevich, Yuri (2003). “Algorithms: A Quest for Absolute Definitions“. Bulletin of European Association for Theoretical Computer Science 81. http://research.microsoft.com/~gurevich/Opera/164.pdf. . Includes an excellent bibliography of 56 references.
  • Boolos, George; Jeffrey, Richard (1974, 1980, 1989, 1999). Computability and Logic (4th ed.). Cambridge University Press, London. ISBN 0-521-20402-X. : cf. Chapter 3 Turing machines where they discuss “certain enumerable sets not effectively (mechanically) enumerable”.
  • Burgin, M. Super-recursive algorithms, Monographs in computer science, Springer, 2005. ISBN 0387955690
  • Campagnolo, M.L., Moore, C., and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In Proc. of the 4th Conference on Real Numbers and Computers, Odense University, pp. 91–109
  • Church, Alonzo (1936a). “An Unsolvable Problem of Elementary Number Theory”. The American Journal of Mathematics 58: 345–363. doi:10.2307/2371045.  Reprinted in The Undecidable, p. 89ff. The first expression of “Church’s Thesis”. See in particular page 100 (The Undecidable) where he defines the notion of “effective calculability” in terms of “an algorithm”, and he uses the word “terminates”, etc.
  • Church, Alonzo (1936b). “A Note on the Entscheidungsproblem”. Journal of Symbolic Logic 1 no. 1 and volume 1 no. 3.  Reprinted in The Undecidable, p. 110ff. Church shows that the Entscheidungsproblem is unsolvable in about 3 pages of text and 3 pages of footnotes.
  • Daffa’, Ali Abdullah al- (1977). The Muslim contribution to mathematics. London: Croom Helm. ISBN 0-85664-464-1. 
  • Davis, Martin (1965). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press.  Davis gives commentary before each article. Papers of Gödel, Alonzo Church, Turing, Rosser, Kleene, and Emil Post are included; those cited in the article are listed here by author’s name.
  • Davis, Martin (2000). Engines of Logic: Mathematicians and the Origin of the Computer. New York: W. W. Nortion.  Davis offers concise biographies of Leibniz, Boole, Frege, Cantor, Hilbert, Gödel and Turing with von Neumann as the show-stealing villain. Very brief bios of Joseph-Marie Jacquard, Babbage, Ada Lovelace, Claude Shannon, Howard Aiken, etc.
  • Paul E. Black, algorithm at the NIST Dictionary of Algorithms and Data Structures.
  • Dennett, Daniel (1995). Darwin’s Dangerous Idea. New York: Touchstone/Simon & Schuster. 
  • Yuri Gurevich, Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pages 77–111. Includes bibliography of 33 sources.
  • Kleene C., Stephen (1936). “General Recursive Functions of Natural Numbers”. Mathematische Annalen Band 112, Heft 5: 727–742. doi:10.1007/BF01565439+.  Presented to the American Mathematical Society, September 1935. Reprinted in The Undecidable, p. 237ff. Kleene’s definition of “general recursion” (known now as mu-recursion) was used by Church in his 1935 paper An Unsolvable Problem of Elementary Number Theory that proved the “decision problem” to be “undecidable” (i.e., a negative result).
  • Kleene C., Stephen (1943). “Recursive Predicates and Quantifiers”. American Mathematical Society Transactions Volume 54, No. 1: 41–73. doi:10.2307/1990131.  Reprinted in The Undecidable, p. 255ff. Kleene refined his definition of “general recursion” and proceeded in his chapter “12. Algorithmic theories” to posit “Thesis I” (p. 274); he would later repeat this thesis (in Kleene 1952:300) and name it “Church’s Thesis”(Kleene 1952:317) (i.e., the Church thesis).
  • Kleene, Stephen C. (First Edition 1952). Introduction to Metamathematics (Tenth Edition 1991 ed.). North-Holland Publishing Company.  Excellent — accessible, readable — reference source for mathematical “foundations”.
  • Knuth, Donald (1997). Fundamental Algorithms, Third Edition. Reading, Massachusetts: Addison-Wesley. ISBN 0201896834. 
  • Kosovsky, N. K. Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms, LSU Publ., Leningrad, 1981
  • Kowalski, Robert (1979). “Algorithm=Logic+Control”. Communications of the ACM (ACM Press) 22 (7): 424–436. doi:10.1145/359131.359136. ISSN 0001-0782. 
  • A. A. Markov (1954) Theory of algorithms. [Translated by Jacques J. Schorr-Kon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e., Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 60-51085.]
  • Minsky, Marvin (1967). Computation: Finite and Infinite Machines (First ed.). Prentice-Hall, Englewood Cliffs, NJ.  Minsky expands his “…idea of an algorithm — an effective procedure…” in chapter 5.1 Computability, Effective Procedures and Algorithms. Infinite machines.”
  • Post, Emil (1936). “Finite Combinatory Processes, Formulation I”. The Journal of Symbolic Logic 1: pp.103–105. doi:10.2307/2269031.  Reprinted in The Undecidable, p. 289ff. Post defines a simple algorithmic-like process of a man writing marks or erasing marks and going from box to box and eventually halting, as he follows a list of simple instructions. This is cited by Kleene as one source of his “Thesis I”, the so-called Church-Turing thesis.
  • Rosser, J.B. (1939). “An Informal Exposition of Proofs of Godel’s Theorem and Church’s Theorem”. Journal of Symbolic Logic 4.  Reprinted in The Undecidable, p. 223ff. Herein is Rosser’s famous definition of “effective method”: “…a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps… a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer” (p. 225–226, The Undecidable)
  • Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing Company. 
  • Stone, Harold S.. Introduction to Computer Organization and Data Structures (1972 ed.). McGraw-Hill, New York.  Cf. in particular the first chapter titled: Algorithms, Turing Machines, and Programs. His succinct informal definition: “…any sequence of instructions that can be obeyed by a robot, is called an algorithm” (p. 4).
  • Turing, Alan M. (1936-7). “On Computable Numbers, With An Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society series 2, volume 42: 230–265. doi:10.1112/plms/s2-42.1.230. . Corrections, ibid, vol. 43(1937) pp.544–546. Reprinted in The Undecidable, p. 116ff. Turing’s famous paper completed as a Master’s dissertation while at King’s College Cambridge UK.
  • Turing, Alan M. (1939). “Systems of Logic Based on Ordinals”. Proceedings of the London Mathematical Society series 2, volume 45: 161–228. doi:10.1112/plms/s2-45.1.161.  Reprinted in The Undecidable, p. 155ff. Turing’s paper that defined “the oracle” was his PhD thesis while at Princeton USA.
  • United States Patent and Trademark Office (2006), 2106.02 **>Mathematical Algorithms< – 2100 Patentability, Manual of Patent Examining Procedure (MPEP). Latest revision August 2006

[edit] Secondary references

[edit] External links

Read Full Post »

Computer programming

From Wikipedia, the free encyclopedia

Jump to: navigation, search

“Programming” redirects here. For other uses, see Programming (disambiguation).
Software development process
Activities and steps
Requirements · Specification
Architecture · Design
Implementation · Testing
Deployment · Maintenance
Models
Agile · Cleanroom · DSDM
Iterative · RAD  · RUP  · Spiral
Waterfall · XP · Scrum  · Lean
V-Model  · FDD
Supporting disciplines
Configuration management
Documentation
Quality assurance (SQA)
Project management
User experience design
Tools
Compiler  · Debugger  · Profiler
GUI designer
Integrated development environment
This box: view  talk

Computer programming (often shortened to programming or coding) is the process of writing, testing, debugging/troubleshooting, and maintaining the source code of computer programs. This source code is written in a programming language. The code may be a modification of an existing source or something completely new. The purpose of programming is to create a program that exhibits a certain desired behaviour (customization). The process of writing source code often requires expertise in many different subjects, including knowledge of the application domain, specialized algorithms and formal logic.

Contents

[hide]

[edit] Overview

Within software engineering, programming (the implementation) is regarded as one phase in a software development process.

There is an ongoing debate on the extent to which the writing of programs is an art, a craft or an engineering discipline.[1] Good programming is generally considered to be the measured application of all three, with the goal of producing an efficient and evolvable software solution (the criteria for “efficient” and “evolvable” vary considerably). The discipline differs from many other technical professions in that programmers generally do not need to be licensed or pass any standardized (or governmentally regulated) certification tests in order to call themselves “programmers” or even “software engineers.” However, representing oneself as a “Professional Software Engineer” without a license from an accredited institution is illegal in many parts of the world.[citation needed]

Another ongoing debate is the extent to which the programming language used in writing computer programs affects the form that the final program takes. This debate is analogous to that surrounding the Sapir-Whorf hypothesis [2] in linguistics, that postulates that a particular language’s nature influences the habitual thought of its speakers. Different language patterns yield different patterns of thought. This idea challenges the possibility of representing the world perfectly with language, because it acknowledges that the mechanisms of any language condition the thoughts of its speaker community.

Said another way, programming is the craft of transforming requirements into something that a computer can execute.

[edit] History of programming

Wired plug board for an IBM 402 Accounting Machine.

The concept of devices that operate following a pre-defined set of instructions traces back to Greek Mythology, notably Hephaestus and his mechanical servants[3]. The Antikythera mechanism was a calculator utilizing gears of various sizes and configuration to determine its operation. The earliest known programmable machines (machines whose behavior can be controlled and predicted with a set of instructions) were Al-Jazari‘s programmable Automata in 1206.[4] One of Al-Jazari’s robots was originally a boat with four automatic musicians that floated on a lake to entertain guests at royal drinking parties. Programming this mechanism‘s behavior meant placing pegs and cams into a wooden drum at specific locations. These would then bump into little levers that operate a percussion instrument. The output of this device was a small drummer playing various rhythms and drum patterns.[5][6] Another sophisticated programmable machine by Al-Jazari was the castle clock, notable for its concept of variables which the operator could manipulate as necessary (i.e. the length of day and night). The Jacquard Loom, which Joseph Marie Jacquard developed in 1801, uses a series of pasteboard cards with holes punched in them. The hole pattern represented the pattern that the loom had to follow in weaving cloth. The loom could produce entirely different weaves using different sets of cards. Charles Babbage adopted the use of punched cards around 1830 to control his Analytical Engine. The synthesis of numerical calculation, predetermined operation and output, along with a way to organize and input instructions in a manner relatively easy for humans to conceive and produce, led to the modern development of computer programming. Development of computer programming accelerated through the Industrial Revolution.

In the late 1880s Herman Hollerith invented the recording of data on a medium that could then be read by a machine. Prior uses of machine readable media, above, had been for control, not data. “After some initial trials with paper tape, he settled on punched cards…”[7] To process these punched cards, first known as “Hollerith cards” he invented the tabulator, and the key punch machines. These three inventions were the foundation of the modern information processing industry. In 1896 he founded the Tabulating Machine Company (which later became the core of IBM). The addition of a control panel to his 1906 Type I Tabulator allowed it to do different jobs without having to be physically rebuilt. By the late 1940s there were a variety of plug-board programmable machines, called unit record equipment, to perform data processing tasks (card reading). Early computer programmers used plug-boards for the variety of complex calculations requested of the newly invented machines.

Data and instructions could be stored on external punch cards, which were kept in order and arranged in program decks.

The invention of the Von Neumann architecture allowed computer programs to be stored in computer memory. Early programs had to be painstakingly crafted using the instructions of the particular machine, often in binary notation. Every model of computer would be likely to need different instructions to do the same task. Later assembly languages were developed that let the programmer specify each instruction in a text format, entering abbreviations for each operation code instead of a number and specifying addresses in symbolic form (e.g. ADD X, TOTAL). In 1954 Fortran was invented, being the first high level programming language to have a functional implementation.[8][9] It allowed programmers to specify calculations by entering a formula directly (e.g. Y = X*2 + 5*X + 9). The program text, or source, is converted into machine instructions using a special program called a compiler. Many other languages were developed, including some for commercial programming, such as COBOL. Programs were mostly still entered using punch cards or paper tape. (See computer programming in the punch card era). By the late 1960s, data storage devices and computer terminals became inexpensive enough so programs could be created by typing directly into the computers. Text editors were developed that allowed changes and corrections to be made much more easily than with punch cards.

As time has progressed, computers have made giant leaps in the area of processing power. This has brought about newer programming languages that are more abstracted from the underlying hardware. Although these high-level languages usually incur greater overhead, the increase in speed of modern computers has made the use of these languages much more practical than in the past. These increasingly abstracted languages typically are easier to learn and allow the programmer to develop applications much more efficiently and with less code. However, high-level languages are still impractical for many programs, such as those where low-level hardware control is necessary or where processing speed is at a premium.

Throughout the second half of the twentieth century, programming was an attractive career in most developed countries. Some forms of programming have been increasingly subject to offshore outsourcing (importing software and services from other countries, usually at a lower wage), making programming career decisions in developed countries more complicated, while increasing economic opportunities in less developed areas. It is unclear how far this trend will continue and how deeply it will impact programmer wages and opportunities.

[edit] Modern programming

[edit] Quality requirements

Whatever the approach to software development may be, the final program must satisfy some fundamental properties. The following five properties are among the most relevant:

  • Efficiency/performance: the amount of system resources a program consumes (processor time, memory space, slow devices such as disks, network bandwidth and to some extent even user interaction): the less, the better. This also includes correct disposal of some resources, such as cleaning up temporary files and lack of memory leaks.
  • Reliability: how often the results of a program are correct. This depends on conceptual correctness of algorithms, and minimization of programming mistakes, such as mistakes in resource management (e.g. buffer overflows and race conditions) and logic errors (such as division by zero).
  • Robustness: how well a program anticipates problems not due to programmer error. This includes situations such as incorrect, inappropriate or corrupt data, unavailability of needed resources such as memory, operating system services and network connections, and user error.
  • Usability: the ergonomics of a program: the ease with which a person can use the program for its intended purpose, or in some cases even unanticipated purposes. Such issues can make or break its success even regardless of other issues. This involves a wide range of textual, graphical and sometimes hardware elements that improve the clarity, intuitiveness, cohesiveness and completeness of a program’s user interface.
  • Portability: the range of computer hardware and operating system platforms on which the source code of a program can be compiled/interpreted and run. This depends on differences in the programming facilities provided by the different platforms, including hardware and operating system resources, expected behaviour of the hardware and operating system, and availability of platform specific compilers (and sometimes libraries) for the language of the source code.

[edit] Algorithmic complexity

The academic field and the engineering practice of computer programming are both largely concerned with discovering and implementing the most efficient algorithms for a given class of problem. For this purpose, algorithms are classified into orders using so-called Big O notation, O(n), which expresses resource use, such as execution time or memory consumption, in terms of the size of an input. Expert programmers are familiar with a variety of well-established algorithms and their respective complexities and use this knowledge to choose algorithms that are best suited to the circumstances.

[edit] Methodologies

The first step in most formal software development projects is requirements analysis, followed by testing to determine value modeling, implementation, and failure elimination (debugging). There exist a lot of differing approaches for each of those tasks. One approach popular for requirements analysis is Use Case analysis.

Popular modeling techniques include Object-Oriented Analysis and Design (OOAD) and Model-Driven Architecture (MDA). The Unified Modeling Language (UML) is a notation used for both OOAD and MDA.

A similar technique used for database design is Entity-Relationship Modeling (ER Modeling).

Implementation techniques include imperative languages (object-oriented or procedural), functional languages, and logic languages.

[edit] Measuring language usage

It is very difficult to determine what are the most popular of modern programming languages. Some languages are very popular for particular kinds of applications (e.g., COBOL is still strong in the corporate data center, often on large mainframes, FORTRAN in engineering applications, scripting languages in web development, and C in embedded applications), while some languages are regularly used to write many different kinds of applications.

Methods of measuring language popularity include: counting the number of job advertisements that mention the language[10], the number of books teaching the language that are sold (this overestimates the importance of newer languages), and estimates of the number of existing lines of code written in the language (this underestimates the number of users of business languages such as COBOL).

[edit] Debugging

A bug which was debugged in 1947.

Debugging is a very important task in the software development process, because an incorrect program can have significant consequences for its users. Some languages are more prone to some kinds of faults because their specification does not require compilers to perform as much checking as other languages. Use of a static analysis tool can help detect some possible problems.

Debugging is often done with IDEs like Visual Studio, NetBeans, and Eclipse. Standalone debuggers like gdb are also used, and these often provide less of a visual environment, usually using a command line.

[edit] Programming languages

Different programming languages support different styles of programming (called programming paradigms). The choice of language used is subject to many considerations, such as company policy, suitability to task, availability of third-party packages, or individual preference. Ideally, the programming language best suited for the task at hand will be selected. Trade-offs from this ideal involve finding enough programmers who know the language to build a team, the availability of compilers for that language, and the efficiency with which programs written in a given language execute.

Allen Downey, in his book How To Think Like A Computer Scientist, writes:

The details look different in different languages, but a few basic instructions appear in just about every language:

  • input: Get data from the keyboard, a file, or some other device.
  • output: Display data on the screen or send data to a file or other device.
  • arithmetic: Perform basic arithmetical operations like addition and multiplication.
  • conditional execution: Check for certain conditions and execute the appropriate sequence of statements.
  • repetition: Perform some action repeatedly, usually with some variation.

Many computer languages provide a mechanism to call functions provided by libraries. Provided the functions in a library follow the appropriate runtime conventions (eg, method of passing arguments), then these functions may be written in any other language.

[edit] Programmers

Main article: Programmer

Computer programmers are those who write computer software. Their jobs usually involve:

[edit] References

  1. ^ Paul Graham (2003). Hackers and Painters. http://www.paulgraham.com/hp.html. Retrieved on 2006-08-22. 
  2. ^ Kenneth E. Iverson, the originator of the APL programming language, believed that the Sapir–Whorf hypothesis applied to computer languages (without actually mentioning the hypothesis by name). His Turing award lecture, “Notation as a tool of thought”, was devoted to this theme, arguing that more powerful notations aided thinking about computer algorithms. Iverson K.E.,”Notation as a tool of thought“, Communications of the ACM, 23: 444-465 (August 1980).
  3. ^ New World Encyclopedia Online Edition New World Encyclopedia
  4. ^ Al-Jazari – the Mechanical Genius, MuslimHeritage.com
  5. ^ A 13th Century Programmable Robot, University of Sheffield
  6. ^ Fowler, Charles B. (October 1967), “The Museum of Music: A History of Mechanical Instruments”, Music Educators Journal 54 (2): 45–49, doi:10.2307/3391092 
  7. ^ Columbia University Computing History – Herman Hollerith
  8. ^ [1]
  9. ^ [2]
  10. ^ Survey of Job advertisements mentioning a given language>

[edit] Further reading

  • Weinberg, Gerald M., The Psychology of Computer Programming, New York: Van Nostrand Reinhold, 1971

[edit] See also

[edit] External links

Sister projectWikibooks has a book on the topic of

Sister projectWikibooks has a book on the topic of

[show]

v  d  e

Major fields of computer science

Mathematical foundations

Theory of computation

Algorithms and data structures

Programming languages and Compilers

Concurrent, Parallel, and Distributed systems

Software engineering

System architecture

Telecommunication & Networking

Databases

Artificial intelligence

Computer graphics

Human computer interaction

Scientific computing

NOTE: Computer science can also be split up into different topics or fields according to the ACM Computing Classification System.
 
 
 
 
 
 
 
Computer architecture · Computer organization · Operating systems
 
Computer audio · Routing · Network topology · Cryptography
 
Data mining · Relational databases · SQL • OLAP
 
 
Visualization · Image processing
 
 
 
[show]

v  d  e

Software engineering

Fields

Concepts

Orientations

Models

Software
engineers

Related fields

 
 
 
 
Development models: AgileIterative modelRUPScrumSpiral modelWaterfall modelXPV-Model
Other models: CMMIData modelFunction modelIDEFInformation modelMetamodelingObject modelView modelUML
 
 

Read Full Post »

Programming language

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Programming language
lists

A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that specify the behavior of a machine, to express algorithms precisely, or as a mode of human communication.

Many programming languages have some form of written specification of their syntax and semantics, since computers require precisely defined instructions. Some (such as C) are defined by a specification document (for example, an ISO Standard), while others (such as Perl) have a dominant implementation.

The earliest programming languages predate the invention of the computer, and were used to direct the behavior of machines such as Jacquard looms and player pianos. Thousands of different programming languages have been created, mainly in the computer field,[1] with many more being created every year.

Contents

[hide]

[edit] Definitions

Traits often considered important for constituting a programming language:

  • Target: Programming languages differ from natural languages in that natural languages are only used for interaction between people, while programming languages also allow humans to communicate instructions to machines. Some programming languages are used by one device to control another. For example PostScript programs are frequently created by another program to control a computer printer or display.
  • Expressive power: The theory of computation classifies languages by the computations they are capable of expressing. All Turing complete languages can implement the same set of algorithms. ANSI/ISO SQL and Charity are examples of languages that are not Turing complete, yet often called programming languages.[4][5]

Some authors restrict the term “programming language” to those languages that can express all possible algorithms;[6] sometimes the term “computer language” is used for more limited artificial languages.

Non-computational languages, such as markup languages like HTML or formal grammars like BNF, are usually not considered programming languages. A programming language (which may or may not be Turing complete) may be embedded in these non-computational (host) languages.

[edit] Usage

A programming language provides a structured mechanism for defining pieces of data, and the operations or transformations that may be carried out automatically on that data. A programmer uses the abstractions present in the language to represent the concepts involved in a computation. These concepts are represented as a collection of the simplest elements available (called primitives). [7]

Programming languages differ from most other forms of human expression in that they require a greater degree of precision and completeness. When using a natural language to communicate with other people, human authors and speakers can be ambiguous and make small errors, and still expect their intent to be understood. However, figuratively speaking, computers “do exactly what they are told to do”, and cannot “understand” what code the programmer intended to write. The combination of the language definition, a program, and the program’s inputs must fully specify the external behavior that occurs when the program is executed, within the domain of control of that program.

Programs for a computer might be executed in a batch process without human interaction, or a user might type commands in an interactive session of an interpreter. In this case the “commands” are simply programs, whose execution is chained together. When a language is used to give commands to a software application (such as a shell) it is called a scripting language[citation needed].

Many languages have been designed from scratch, altered to meet new needs, combined with other languages, and eventually fallen into disuse. Although there have been attempts to design one “universal” computer language that serves all purposes, all of them have failed to be generally accepted as filling this role.[8] The need for diverse computer languages arises from the diversity of contexts in which languages are used:

  • Programs range from tiny scripts written by individual hobbyists to huge systems written by hundreds of programmers.
  • Programmers range in expertise from novices who need simplicity above all else, to experts who may be comfortable with considerable complexity.
  • Programs must balance speed, size, and simplicity on systems ranging from microcontrollers to supercomputers.
  • Programs may be written once and not change for generations, or they may undergo nearly constant modification.
  • Finally, programmers may simply differ in their tastes: they may be accustomed to discussing problems and expressing them in a particular language.

One common trend in the development of programming languages has been to add more ability to solve problems using a higher level of abstraction. The earliest programming languages were tied very closely to the underlying hardware of the computer. As new programming languages have developed, features have been added that let programmers express ideas that are more remote from simple translation into underlying hardware instructions. Because programmers are less tied to the complexity of the computer, their programs can do more computing with less effort from the programmer. This lets them write more functionality per time unit.[9]

Natural language processors have been proposed as a way to eliminate the need for a specialized language for programming. However, this goal remains distant and its benefits are open to debate. Edsger Dijkstra took the position that the use of a formal language is essential to prevent the introduction of meaningless constructs, and dismissed natural……… language programming as “foolish”.[10] Alan Perlis was similarly dismissive of the idea.[11]

[edit] Elements

All programming languages have some primitive building blocks for the description of data and the processes or transformations applied to them (like the addition of two numbers or the selection of an item from a collection). These primitives are defined by syntactic and semantic rules which describe their structure and meaning respectively.

[edit] Syntax

Parse tree of Python code with inset tokenization

Syntax highlighting is often used to aid programmers in recognizing elements of source code. The language above is Python.

A programming language’s surface form is known as its syntax. Most programming languages are purely textual; they use sequences of text including words, numbers, and punctuation, much like written natural languages. On the other hand, there are some programming languages which are more graphical in nature, using visual relationships between symbols to specify a program.

The syntax of a language describes the possible combinations of symbols that form a syntactically correct program. The meaning given to a combination of symbols is handled by semantics (either formal or hard-coded in a reference implementation). Since most languages are textual, this article discusses textual syntax.

Programming language syntax is usually defined using a combination of regular expressions (for lexical structure) and Backus-Naur Form (for grammatical structure). Below is a simple grammar, based on Lisp:

 expression ::= atom   | list
 atom       ::= number | symbol
 number     ::= [+-]?['0'-'9']+
 symbol     ::= ['A'-'Z''a'-'z'].*
 list       ::= '(' expression* ')'

This grammar specifies the following:

  • an expression is either an atom or a list;
  • an atom is either a number or a symbol;
  • a number is an unbroken sequence of one or more decimal digits, optionally preceded by a plus or minus sign;
  • a symbol is a letter followed by zero or more of any characters (excluding whitespace); and
  • a list is a matched pair of parentheses, with zero or more expressions inside it.

The following are examples of well-formed token sequences in this grammar: ‘12345‘, ‘()‘, ‘(a b c232 (1))

Not all syntactically correct programs are semantically correct. Many syntactically correct programs are nonetheless ill-formed, per the language’s rules; and may (depending on the language specification and the soundness of the implementation) result in an error on translation or execution. In some cases, such programs may exhibit undefined behavior. Even when a program is well-defined within a language, it may still have a meaning that is not intended by the person who wrote it.

Using natural language as an example, it may not be possible to assign a meaning to a grammatically correct sentence or the sentence may be false:

  • Colorless green ideas sleep furiously.” is grammatically well-formed but has no generally accepted meaning.
  • “John is a married bachelor.” is grammatically well-formed but expresses a meaning that cannot be true.

The following C language fragment is syntactically correct, but performs an operation that is not semantically defined (because p is a null pointer, the operations p->real and p->im have no meaning):

complex *p = NULL;
complex abs_p = sqrt (p->real * p->real + p->im * p->im);

The grammar needed to specify a programming language can be classified by its position in the Chomsky hierarchy. The syntax of most programming languages can be specified using a Type-2 grammar, i.e., they are context-free grammars.[12]

[edit] Static semantics

The static semantics defines restrictions on the structure of valid texts that are hard or impossible to express in standard syntactic formalisms.[13] The most important of these restrictions are covered by type systems.

[edit] Type system

Main articles: Type system and Type safety

A type system defines how a programming language classifies values and expressions into types, how it can manipulate those types and how they interact. This generally includes a description of the data structures that can be constructed in the language. The design and study of type systems using formal mathematics is known as type theory.

[edit] Typed versus untyped languages

A language is typed if the specification of every operation defines types of data to which the operation is applicable, with the implication that it is not applicable to other types.[14] For example, “this text between the quotes” is a string. In most programming languages, dividing a number by a string has no meaning. Most modern programming languages will therefore reject any program attempting to perform such an operation. In some languages, the meaningless operation will be detected when the program is compiled (“static” type checking), and rejected by the compiler, while in others, it will be detected when the program is run (“dynamic” type checking), resulting in a runtime exception.

A special case of typed languages are the single-type languages. These are often scripting or markup languages, such as Rexx or SGML, and have only one data type—most commonly character strings which are used for both symbolic and numeric data.

In contrast, an untyped language, such as most assembly languages, allows any operation to be performed on any data, which are generally considered to be sequences of bits of various lengths.[14] High-level languages which are untyped include BCPL and some varieties of Forth.

In practice, while few languages are considered typed from the point of view of type theory (verifying or rejecting all operations), most modern languages offer a degree of typing.[14] Many production languages provide means to bypass or subvert the type system.

[edit] Static versus dynamic typing

In static typing all expressions have their types determined prior to the program being run (typically at compile-time). For example, 1 and (2+2) are integer expressions; they cannot be passed to a function that expects a string, or stored in a variable that is defined to hold dates.[14]

Statically typed languages can be either manifestly typed or type-inferred. In the first case, the programmer must explicitly write types at certain textual positions (for example, at variable declarations). In the second case, the compiler infers the types of expressions and declarations based on context. Most mainstream statically typed languages, such as C++, C# and Java, are manifestly typed. Complete type inference has traditionally been associated with less mainstream languages, such as Haskell and ML. However, many manifestly typed languages support partial type inference; for example, Java and C# both infer types in certain limited cases.[15]

Dynamic typing, also called latent typing, determines the type-safety of operations at runtime; in other words, types are associated with runtime values rather than textual expressions.[14] As with type-inferred languages, dynamically typed languages do not require the programmer to write explicit type annotations on expressions. Among other things, this may permit a single variable to refer to values of different types at different points in the program execution. However, type errors cannot be automatically detected until a piece of code is actually executed, making debugging more difficult. Ruby, Lisp, JavaScript, and Python are dynamically typed.

[edit] Weak and strong typing

Weak typing allows a value of one type to be treated as another, for example treating a string as a number.[14] This can occasionally be useful, but it can also allow some kinds of program faults to go undetected at compile time and even at run time.

Strong typing prevents the above. An attempt to perform an operation on the wrong type of value raises an error.[14] Strongly typed languages are often termed type-safe or safe.

An alternative definition for “weakly typed” refers to languages, such as Perl and JavaScript, which permit a large number of implicit type conversions. In JavaScript, for example, the expression 2 * x implicitly converts x to a number, and this conversion succeeds even if x is null, undefined, an Array, or a string of letters. Such implicit conversions are often useful, but they can mask programming errors.

Strong and static are now generally considered orthogonal concepts, but usage in the literature differs. Some use the term strongly typed to mean strongly, statically typed, or, even more confusingly, to mean simply statically typed. Thus C has been called both strongly typed and weakly, statically typed.[16][17]

[edit] Execution semantics

Once data has been specified, the machine must be instructed to perform operations on the data. The execution semantics of a language defines how and when the various constructs of a language should produce a program behavior.

For example, the semantics may define the strategy by which expressions are evaluated to values, or the manner in which control structures conditionally execute statements.

[edit] Core library

For more details on this topic, see Standard library.

Most programming languages have an associated core library (sometimes known as the ‘Standard library’, especially if it is included as part of the published language standard), which is conventionally made available by all implementations of the language. Core libraries typically include definitions for commonly used algorithms, data structures, and mechanisms for input and output.

A language’s core library is often treated as part of the language by its users, although the designers may have treated it as a separate entity. Many language specifications define a core that must be made available in all implementations, and in the case of standardized languages this core library may be required. The line between a language and its core library therefore differs from language to language. Indeed, some languages are designed so that the meanings of certain syntactic constructs cannot even be described without referring to the core library. For example, in Java, a string literal is defined as an instance of the java.lang.String class; similarly, in Smalltalk, an anonymous function expression (a “block”) constructs an instance of the library’s BlockContext class. Conversely, Scheme contains multiple coherent subsets that suffice to construct the rest of the language as library macros, and so the language designers do not even bother to say which portions of the language must be implemented as language constructs, and which must be implemented as parts of a library.

[edit] Practice

A Jovan language’s designers and users must construct a number of artifacts that govern and enable the practice of programming. The most important of these artifacts are the language specification and implementation.

[edit] Specification

The specification of a programming language is intended to provide a definition that the language users and the implementors can use to determine whether the behavior of a program is correct, given its source code.

A programming language specification can take several forms, including the following:

  • An explicit definition of the syntax, static semantics, and execution semantics of the language. While syntax is commonly specified using a formal grammar, semantic definitions may be written in natural language (e.g., the C language), or a formal semantics (e.g., the Standard ML[18] and Scheme[19] specifications).
  • A description of the behavior of a translator for the language (e.g., the C++ and Fortran specifications). The syntax and semantics of the language have to be inferred from this description, which may be written in natural or a formal language.
  • A reference or model implementation, sometimes written in the language being specified (e.g., Prolog or ANSI REXX[20]). The syntax and semantics of the language are explicit in the behavior of the reference implementation.

[edit] Implementation

An implementation of a programming language provides a way to execute that program on one or more configurations of hardware and software. There are, broadly, two approaches to programming language implementation: compilation and interpretation. It is generally possible to implement a language using either technique.

The output of a compiler may be executed by hardware or a program called an interpreter. In some implementations that make use of the interpreter approach there is no distinct boundary between compiling and interpreting. For instance, some implementations of the BASIC programming language compile and then execute the source a line at a time.

Programs that are executed directly on the hardware usually run several orders of magnitude faster than those that are interpreted in software.[citation needed]

One technique for improving the performance of interpreted programs is just-in-time compilation. Here the virtual machine, just before execution, translates the blocks of bytecode which are going to be used to machine code, for direct execution on the hardware.

[edit] History

A selection of textbooks that teach programming, in languages both popular and obscure. These are only a few of the thousands of programming languages and dialects that have been designed in history.

[edit] Early developments

The first programming languages predate the modern computer. The 19th century had “programmable” looms and player piano scrolls which implemented what are today recognized as examples of domain-specific programming languages. By the beginning of the twentieth century, punch cards encoded data and directed mechanical processing. In the 1930s and 1940s, the formalisms of Alonzo Church‘s lambda calculus and Alan Turing‘s Turing machines provided mathematical abstractions for expressing algorithms; the lambda calculus remains influential in language design.[21]

In the 1940s, the first electrically powered digital computers were created. The first high-level programming language to be designed for a computer was Plankalkül, developed for the German Z3 by Konrad Zuse between 1943 and 1945. However, it was not implemented until much later because of wartime damage.[citation needed]

Programmers of early 1950s computers, notably UNIVAC I and IBM 701, used machine language programs, that is, the first generation language (1GL). 1GL programming was quickly superseded by similarly machine-specific, but mnemonic, second generation languages (2GL) known as assembly languages or “assembler”. Later in the 1950s, assembly language programming, which had evolved to include the use of macro instructions, was followed by the development of “third generation” programming languages (3GL), such as FORTRAN, LISP, and COBOL. 3GLs are more abstract and are “portable”, or at least implemented similar on computers that do not support the same native machine code. Updated versions of all of these 3GLs are still in general use, and each has strongly influenced the development of later languages.[22] At the end of the 1950s, the language formalized as Algol 60 was introduced, and most later programming languages are, in many respects, descendants of Algol.[22] The format and use of the early programming languages was heavily influenced by the constraints of the interface.[23]

[edit] Refinement

The period from the 1960s to the late 1970s brought the development of the major language paradigms now in use, though many aspects were refinements of ideas in the very first Third-generation programming languages:

  • APL introduced array programming and influenced functional programming.[24]
  • PL/I (NPL) was designed in the early 1960s to incorporate the best ideas from FORTRAN and COBOL.
  • In the 1960s, Simula was the first language designed to support object-oriented programming; in the mid-1970s, Smalltalk followed with the first “purely” object-oriented language.
  • C was developed between 1969 and 1973 as a systems programming language, and remains popular.[25]
  • Prolog, designed in 1972, was the first logic programming language.
  • In 1978, ML built a polymorphic type system on top of Lisp, pioneering statically typed functional programming languages.

Each of these languages spawned an entire family of descendants, and most modern languages count at least one of them in their ancestry.

The 1960s and 1970s also saw considerable debate over the merits of structured programming, and whether programming languages should be designed to support it.[26] Edsger Dijkstra, in a famous 1968 letter published in the Communications of the ACM, argued that GOTO statements should be eliminated from all “higher level” programming languages.[27]

The 1960s and 1970s also saw expansion of techniques that reduced the footprint of a program as well as improved productivity of the programmer and user. The card deck for an early 4GL was a lot smaller for the same functionality expressed in a 3GL deck.

[edit] Consolidation and growth

The 1980s were years of relative consolidation. C++ combined object-oriented and systems programming. The United States government standardized Ada, a systems programming language derived from Pascal and intended for use by defense contractors. In Japan and elsewhere, vast sums were spent investigating so-called “fifth generation” languages that incorporated logic programming constructs.[28] The functional languages community moved to standardize ML and Lisp. Rather than inventing new paradigms, all of these movements elaborated upon the ideas invented in the previous decade.

One important trend in language design during the 1980s was an increased focus on programming for large-scale systems through the use of modules, or large-scale organizational units of code. Modula-2, Ada, and ML all developed notable module systems in the 1980s, although other languages, such as PL/I, already had extensive support for modular programming. Module systems were often wedded to generic programming constructs.[29]

The rapid growth of the Internet in the mid-1990s created opportunities for new languages. Perl, originally a Unix scripting tool first released in 1987, became common in dynamic Web sites. Java came to be used for server-side programming. These developments were not fundamentally novel, rather they were refinements to existing languages and paradigms, and largely based on the C family of programming languages.

Programming language evolution continues, in both industry and research. Current directions include security and reliability verification, new kinds of modularity (mixins, delegates, aspects), and database integration such as Microsoft’s LINQ.

The 4GLs are examples of languages which are domain-specific, such as SQL, which manipulates and returns sets of data rather than the scalar values which are canonical to most programming languages. Perl, for example, with its ‘here document‘ can hold multiple 4GL programs, as well as multiple JavaScript programs, in part of its own perl code and use variable interpolation in the ‘here document’ to support multi-language programming.[30]

[edit] Measuring language usage

It is difficult to determine which programming languages are most widely used, and what usage means varies by context. One language may occupy the greater number of programmer hours, a different one have more lines of code, and a third utilize the most CPU time. Some languages are very popular for particular kinds of applications. For example, COBOL is still strong in the corporate data center, often on large mainframes; FORTRAN in engineering applications; C in embedded applications and operating systems; and other languages are regularly used to write many different kinds of applications.

Various methods of measuring language popularity, each subject to a different bias over what is measured, have been proposed:

  • counting the number of job advertisements that mention the language[31]
  • the number of books sold that teach or describe the language[32]
  • estimates of the number of existing lines of code written in the language—which may underestimate languages not often found in public searches[33]
  • counts of language references (i.e., to the name of the language) found using a web search engine.

Combining and averaging information from various internet sites, langpop.com claims that [34] in 2008 the 10 most cited programming languages are (in alphabetical order): C, C++, C#, Java, JavaScript, Perl, PHP, Python, Ruby, and SQL.

[edit] Taxonomies

For more details on this topic, see Categorical list of programming languages.

There is no overarching classification scheme for programming languages. A given programming language does not usually have a single ancestor language. Languages commonly arise by combining the elements of several predecessor languages with new ideas in circulation at the time. Ideas that originate in one language will diffuse throughout a family of related languages, and then leap suddenly across familial gaps to appear in an entirely different family.

The task is further complicated by the fact that languages can be classified along multiple axes. For example, Java is both an object-oriented language (because it encourages object-oriented organization) and a concurrent language (because it contains built-in constructs for running multiple threads in parallel). Python is an object-oriented scripting language.

In broad strokes, programming languages divide into programming paradigms and a classification by intended domain of use. Paradigms include procedural programming, object-oriented programming, functional programming, and logic programming; some languages are hybrids of paradigms or multi-paradigmatic. An assembly language is not so much a paradigm as a direct model of an underlying machine architecture. By purpose, programming languages might be considered general purpose, system programming languages, scripting languages, domain-specific languages, or concurrent/distributed languages (or a combination of these).[35] Some general purpose languages were designed largely with educational goals.[36]

A programming language may also be classified by factors unrelated to programming paradigm. For instance, most programming languages use English language keywords, while a minority do not. Other languages may be classified as being esoteric or not.

[edit] See also

Sister projectWikibooks has a book on the topic of

Look up programming language in Wiktionary, the free dictionary.

[edit] References

  1. ^ “HOPL: an interactive Roster of Programming Languages”. Australia: Murdoch University. http://hopl.murdoch.edu.au/. Retrieved on 2009-06-01. “This site lists 8512 languages.” 
  2. ^ ACM SIGPLAN (2003). “Bylaws of the Special Interest Group on Programming Languages of the Association for Computing Machinery”. http://www.acm.org/sigs/sigplan/sigplan_bylaws.htm. Retrieved on 2006-06-19. , The scope of SIGPLAN is the theory, design, implementation, description, and application of computer programming languages – languages that permit the specification of a variety of different computations, thereby providing the user with significant control (immediate or delayed) over the computer’s operation.
  3. ^ Dean, Tom (2002). “Programming Robots”. Building Intelligent Robots. Brown University Department of Computer Science. http://www.cs.brown.edu/people/tld/courses/cs148/02/programming.html. Retrieved on 2006-09-23. 
  4. ^ Digital Equipment Corporation. “Information Technology – Database Language SQL (Proposed revised text of DIS 9075)”. ISO/IEC 9075:1992, Database Language SQL. http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt. Retrieved on June 29 2006. 
  5. ^ The Charity Development Group (December 1996). “The CHARITY Home Page”. http://pll.cpsc.ucalgary.ca/charity1/www/home.html. Retrieved on 2006-06-29. , Charity is a categorical programming language…, All Charity computations terminate.
  6. ^ In mathematical terms, this means the programming language is Turing-complete MacLennan, Bruce J. (1987). Principles of Programming Languages. Oxford University Press. p. 1. ISBN 0-19-511306-3. 
  7. ^ Abelson, Sussman, and Sussman. “Structure and Interpretation of Computer Programs”. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html. Retrieved on 2009-03-03. 
  8. ^ IBM in first publishing PL/I, for example, rather ambitiously titled its manual The universal programming language PL/I (IBM Library; 1966). The title reflected IBM’s goals for unlimited subsetting capability: PL/I is designed in such a way that one can isolate subsets from it satisfying the requirements of particular applications. (“Encyclopaedia of Mathematics » P  » PL/I”. SpringerLink. http://eom.springer.de/P/p072885.htm. Retrieved on June 29 2006. ). Ada and UNCOL had similar early goals.
  9. ^ Frederick P. Brooks, Jr.: The Mythical Man-Month, Addison-Wesley, 1982, pp. 93-94
  10. ^ Dijkstra, Edsger W. On the foolishness of “natural language programming.” EWD667.
  11. ^ Perlis, Alan, Epigrams on Programming. SIGPLAN Notices Vol. 17, No. 9, September 1982, pp. 7-13
  12. ^ Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 2.2: Pushdown Automata, pp.101–114.
  13. ^ Aaby, Anthony (2004). Introduction to Programming Languages. http://web.archive.org/web/20040407162301/cs.wwc.edu/~aabyan/PLBook/HTML/index.html. 
  14. ^ a b c d e f g Andrew Cooke. “An Introduction to Programming Languages”. http://www.acooke.org/andrew/writing/lang.html#sec-types. Retrieved on June 30 2006. [dead link]
  15. ^ Specifically, instantiations of generic types are inferred for certain expression forms. Type inference in Generic Java—the research language that provided the basis for Java 1.5’s bounded parametric polymorphism extensions—is discussed in two informal manuscripts from the Types mailing list: Generic Java type inference is unsound (Alan Jeffrey, 17 December 2001) and Sound Generic Java type inference (Martin Odersky, 15 January 2002). C#’s type system is similar to Java’s, and uses a similar partial type inference scheme.
  16. ^ “Revised Report on the Algorithmic Language Scheme (February 20, 1998)”. http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-4.html. Retrieved on June 9 2006. 
  17. ^ Luca Cardelli and Peter Wegner. “On Understanding Types, Data Abstraction, and Polymorphism”. Manuscript (1985). http://citeseer.ist.psu.edu/cardelli85understanding.html. Retrieved on June 9 2006. 
  18. ^ Milner, R.; M. Tofte, R. Harper and D. MacQueen. (1997). The Definition of Standard ML (Revised). MIT Press. ISBN 0-262-63181-4. 
  19. ^ Kelsey, Richard; William Clinger and Jonathan Rees (February 1998). “Section 7.2 Formal semantics”. Revised5 Report on the Algorithmic Language Scheme. http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-10.html#%_sec_7.2. Retrieved on 2006-06-09. 
  20. ^ ANSI — Programming Language Rexx, X3-274.1996
  21. ^ Benjamin C. Pierce writes:
    “… the lambda calculus has seen widespread use in the specification of programming language features, in language design and implementation, and in the study of type systems.”

    Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press. p. 52. ISBN 0-262-16209-1. 

  22. ^ a b O’Reilly Media. “History of programming languages” (PDF). http://www.oreilly.com/news/graphics/prog_lang_poster.pdf. Retrieved on October 5 2006. 
  23. ^ Frank da Cruz. IBM Punch Cards Columbia University Computing History.
  24. ^ Richard L. Wexelblat: History of Programming Languages, Academic Press, 1981, chapter XIV.
  25. ^ François Labelle. “Programming Language Usage Graph”. Sourceforge. http://www.cs.berkeley.edu/~flab/languages.html. Retrieved on June 21 2006. . This comparison analyzes trends in number of projects hosted by a popular community programming repository. During most years of the comparison, C leads by a considerable margin; in 2006, Java overtakes C, but the combination of C/C++ still leads considerably.
  26. ^ Hayes, Brian (2006), “The Semicolon Wars”, American Scientist 94 (4): 299–303 
  27. ^ Dijkstra, Edsger W. (March 1968). “Go To Statement Considered Harmful“. Communications of the ACM 11 (3): 147–148. doi:10.1145/362929.362947. http://www.acm.org/classics/oct95/. Retrieved on 2006-06-29. 
  28. ^ Tetsuro Fujise, Takashi Chikayama Kazuaki Rokusawa, Akihiko Nakase (December 1994). “KLIC: A Portable Implementation of KL1” Proc. of FGCS ’94, ICOT Tokyo, December 1994. KLIC is a portable implementation of a concurrent logic programming language KL1.
  29. ^ Jim Bender (March 15, 2004). “Mini-Bibliography on Modules for Functional Programming Languages”. ReadScheme.org. http://readscheme.org/modules/. Retrieved on 2006-09-27. 
  30. ^ Wall, Programming Perl ISBN 0-596-00027-8 p.66
  31. ^ Survey of Job advertisements mentioning a given language
  32. ^ Counting programming languages by book sales
  33. ^ Bieman, J.M.; Murdock, V., Finding code on the World Wide Web: a preliminary investigation, Proceedings First IEEE International Workshop on Source Code Analysis and Manipulation, 2001
  34. ^ Programming Language Popularity
  35. ^ “TUNES: Programming Languages”. http://tunes.org/wiki/programming_20languages.html. 
  36. ^ Wirth, Niklaus (1993). “Recollections about the development of Pascal“. Proc. 2nd ACM SIGPLAN conference on history of programming languages: 333–342. doi:10.1145/154766.155378. http://portal.acm.org/citation.cfm?id=155378. Retrieved on 2006-06-30. 

[edit] Further reading

  • Daniel P. Friedman, Mitchell Wand, Christopher Thomas Haynes: Essentials of Programming Languages, The MIT Press 2001.
  • David Gelernter, Suresh Jagannathan: Programming Linguistics, The MIT Press 1990.
  • Shriram Krishnamurthi: Programming Languages: Application and Interpretation, online publication.
  • Bruce J. MacLennan: Principles of Programming Languages: Design, Evaluation, and Implementation, Oxford University Press 1999.
  • John C. Mitchell: Concepts in Programming Languages, Cambridge University Press 2002.
  • Benjamin C. Pierce: Types and Programming Languages, The MIT Press 2002.
  • Ravi Sethi: Programming Languages: Concepts and Constructs, 2nd ed., Addison-Wesley 1996.
  • Michael L. Scott: Programming Language Pragmatics, Morgan Kaufmann Publishers 2005.
  • Richard L. Wexelblat (ed.): History of Programming Languages, Academic Press 1981.

[edit] External links

[show]

v  d  e

Types of programming languages

 
[show]

v  d  e

Types of Computer languages

 

  

Read Full Post »

« Newer Posts - Older Posts »