:: wikimiki.org ::

Memoization

Memoization

Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. Memoization is a characteristic of dynamic programming. Functions can only be memoized if they are referentially transparent -- that is, if they will always return the same result given the same arguments. Operations which are not referentially transparent, but whose results are not likely to change rapidly, can still be cached with methods more complicated than memoization. In general, memoized results are not expired or invalidated later, while caches generally are. In a functional programming language it is possible to construct a higher-order function memoize which will create a memoized function for any referentially transparent function. In languages without higher-order functions, memoization must be implemented separately in each function that is to benefit from it.

Etymology

Memoization literally means "to put in memory" and is derived from the Latin word memorandum, meaning what must be remembered. The word memoization is often confused with memorization, which, although a good description of the process, is not limited to this specific meaning.

Example

A naive program to compute Fibonacci numbers is fib(n) Because fib() is recomputed over and over for the same argument, run time for the above is Ω(1.6ⁿ). If instead we memoize (save) the value of fib(n) the first time we compute it, the run time is Θ(n). allocate array for memo, setting all entries to zero; initialize memo[1] and memo[2] to 1; fib(n) In a language with closures and higher-order functions, the memoization of any function can be automatically defined. Here "memoize" constructs and returns another function which serves as the memoization of the argument f. memoize(f) The notation


 - args

is meant to represent a rest argument as in Python or Common Lisp. This solution relies on returning a closure over the variable memo, which serves as a cache for the returned function. This function "memoize" can be used to construct a memoized version of "fib": memofib = memoize(fib) Computing Fibonacci numbers can be done in logarithmic time (see Fibonacci numbers); this example illustrates the concept of memoization.

History

The term "memoization" was coined by Donald Michie in his 1968 paper "Memo functions and machine learning" in Nature.

Some uses

- Searching
- Source code generation, including HTML
- Repetitive computations, such as image conversion, encryption, and data compression.
- Pattern recognition such as speech recognition
- Game tree evaluation

External links

- [http://search.cpan.org/dist/Memoize/Memoize.pm Memoize.pm] - a Perl module that implements memoized subroutines
- [http://www.onjava.com/pub/a/onjava/2003/08/20/memoization.html Java memoization] - an example in Java using dynamic proxy classes to create a generic memoization pattern.
- [http://raa.ruby-lang.org/project/memoize/ memoize] - a Ruby module that implements memoized methods.
- [http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201 Python memoization] - a Python example of memoization. Note: This article contains material taken from a public domain entry within the NIST Dictionary of Algorithms and Data Structures at http://www.nist.gov/dads/HTML/memoize.html Category:Dynamic programming Category:Software design patterns

Computer

A computer is a device capable of processing data according to a program — a list of instructions. The data to be processed may represent many types of information including numbers, text, pictures, or sound. Computers can be extremely versatile. In fact, they are universal information processing machines. According to the Church-Turing thesis, a computer with a certain minimum threshold capability is in principle capable of performing the tasks of any other computer, from those of a personal digital assistant to a supercomputer. Therefore, the same computer designs have been adapted for tasks from processing company payrolls to controlling industrial robots. Modern electronic computers also have enormous speed and capacity for information processing compared to earlier designs, and they have become exponentially more powerful over the years (a phenomenon known as Moore's Law). Computers are available in many physical forms. The original computers were the size of a large room, and such enormous computing facilities still exist for specialized scientific computation - supercomputers - and for the transaction processing requirements of large companies, generally called mainframes. Smaller computers for individual use, called personal computers, and their portable equivalent, the notebook computer, are ubiquitous information-processing and communication tools and are perhaps what most non-experts think of as "a computer". However, the most common form of computer in use today is the embedded computer, small computers used to control another device. Embedded computers control machines from fighter planes to digital cameras.

History of computing

Originally, a "computer" was a person who performed numerical calculations under the direction of a mathematician, often with the aid of a variety of mechanical calculating devices from the abacus onward. An example of an early computing device was the Antikythera mechanism, an ancient Greek device for calculating the movements of planets, dating from about 87 BCE. The technology responsible for this mysterious device seems to have been lost at some point. The end of the Middle Ages saw a reinvigoration of European mathematics and engineering, and by the early 17th century a succession of mechanical calculating devices had been constructed using clockwork technology. A considerable number of technologies that would later prove vital for the digital computer were developed in the late 19th and early 20th centuries, such as the punched card and the vacuum tube ((or valve). Charles Babbage was the first to conceptualize and design a fully programmable computer as early as 1837, but due to a combination of the limits of the technology of the time, limited finance, and an inability to resist tinkering with his design (a trait that would in time doom thousands of computer-related engineering projects), the device was never actually constructed in his lifetime. During the first half of the 20th century, many scientific computing needs were met by increasingly sophisticated, special-purpose analog computers, which used a direct physical or electrical model of the problem as a basis for computation. These became increasingly rare after the development of the digital computer. A succession of steadily more powerful and flexible computing devices were constructed in the 1930s and 1940s, gradually adding the key features of modern computers, such as the use of digital electronics (invented by Claude Shannon in 1937) and more flexible programmability. Defining one point along this road as "the first computer" is exceedingly difficult. Notable achievements include the Atanasoff Berry Computer, a special-purpose machine that used valve-driven computation and binary numbers; Konrad Zuse's Z machines; the secret British Colossus computer, which had limited programmability but demonstrated that a device using thousands of valves could be made reliable and reprogrammed electronically; and the American ENIAC — the first general purpose machine, but with an inflexible architecture that meant reprogramming it essentially required it to be rewired. The team who developed ENIAC, recognizing its flaws, came up with a far more flexible and elegant design, which has become known as the stored program architecture, which is the basis from which virtually all modern computers were derived. A number of projects to develop computers based on the stored program architecture commenced in the late 1940s; the first of these to be up and running was the Small-Scale Experimental Machine, but the EDSAC was perhaps the first practical version. Valve-driven computer designs were in use throughout the 1950s, but were eventually replaced with transistor-based computers, which were smaller, faster, cheaper, and much more reliable, thus allowing them to be commercially produced, in the 1960s. By the 1970s, the adoption of integrated circuit technology had enabled computers to be produced at a low enough cost to allow individuals to own a personal computer of the type familiar today.

How computers work: the stored program architecture

While the technologies used in computers have changed dramatically since the first electronic, general-purpose, computers of the 1940s, most still use the stored program architecture (sometimes called the von Neumann architecture; as the article describes the primary inventors were probably ENIAC designers J. Presper Eckert and John William Mauchly). The design made the universal computer a practical reality. The architecture describes a computer with four main sections: the arithmetic and logic unit (ALU), the control circuitry, the memory, and the input and output devices (collectively termed I/O). These parts are interconnected by a bundle of wires (a "bus") and are usually driven by a timer or clock (although other events could drive the control circuitry). Conceptually, a computer's memory can be viewed as a list of cells. Each cell has a numbered "address" and can store a small, fixed amount of information. This information can either be an instruction, telling the computer what to do, or data, the information which the computer is to process using the instructions that have been placed in the memory. In principle, any cell can be used to store either instructions or data. The ALU is in many senses the heart of the computer. It is capable of performing two classes of basic operations: arithmetic operations, the core of which is the ability to add or subtract two numbers but also encompasses operations like "multiply this number by 2" or "divide by 2" (for reasons which will become clear later), as well as some others. The second class of ALU operations involves comparison operations, which, given two numbers, can determine if they are equal, and if not, which is bigger. The I/O systems are the means by which the computer receives information from the outside world, and reports its results back to that world. On a typical personal computer, input devices include objects like the keyboard and mouse, and output devices include computer monitors, printers and the like, but as will be discussed later a huge variety of devices can be connected to a computer and serve as I/O devices. The control system ties this all together. Its job is to read instructions and data from memory or the I/O devices, decode the instructions, providing the ALU with the correct inputs according to the instructions, "tell" the ALU what operation to perform on those inputs, and send the results back to the memory or to the I/O devices. One key component of the control system is a counter that keeps track of what the address of the current instruction is; typically, this is incremented each time an instruction is executed, unless the instruction itself indicates that the next instruction should be at some other location (allowing the computer to repeatedly execute the same instructions). Physically, since the 1980s the ALU and control unit have been located on a single integrated circuit called a Central Processing Unit or CPU. The functioning of such a computer is in principle quite straightforward. Typically, on each clock cycle, the computer fetches instructions and data from its memory. The instructions are executed, the results are stored, and the next instruction is fetched. This procedure repeats until a halt instruction is encountered. Larger computers, such as some minicomputers, mainframe computers, servers, differ from the model above in one significant aspect; rather than one CPU they often have a number of them. Supercomputers often have highly unusual architectures significantly different from the basic stored-program architecture, sometimes featuring thousands of CPUs, but such designs tend to be useful only for specialized tasks.

Digital circuits

The conceptual design above could be implemented using a variety of different technologies. As previously mentioned, a stored program computer could be designed entirely of mechanical components like Babbage's. However, digital circuits allow Boolean logic and arithmetic using binary numerals to be implemented using relays - essentially, electrically controlled switches. Shannon's famous thesis showed how relays could be arranged to form units called logic gates, implementing simple Boolean operations. Others soon figured out that vacuum tubes - electronic devices, could be used instead. Vacuum tubes were originally used as a signal amplifier for radio and other applications, but were used in digital electronics as a very fast switch; when electricity is provided to one of the pins, current can flow through between the other two. Through arrangements of logic gates, one can build digital circuits to do more complex tasks, for instance, an adder, which implements in electronics the same method - in computer terminology, an algorithm - to add two numbers together that children are taught - add one column at a time, and carry what's left over. Eventually, through combining circuits together, a complete ALU and control system can be built up. This does require a considerable number of components. CSIRAC, one of the earliest stored-program computers, is probably close to the smallest practically useful design. It had about 2,000 valves, some of which were "dual components", so this represented somewhere between 2 and 4,000 logic components. Vacuum tubes had severe limitations for the construction of large numbers of gates. They were expensive, unreliable (particularly when used in such large quantities), took up a lot of space, and used a lot of electrical power, and, while incredibly fast compared to a mechanical switch, had limits to the speed at which they could operate. Therefore, by the 1960s they were replaced by the transistor, a new device which performed the same task as the tube but was much smaller, faster operating, reliable, used much less power, and was far cheaper. transistor In the 1960s and 1970s, the transistor itself was gradually replaced by the integrated circuit, which placed multiple transistors (and other components) and the wires connecting them on a single, solid piece of silicon. By the 1970s, the entire ALU and control unit, the combination becoming known as a CPU, were being placed on a single "chip" called a microprocessor. Over the history of the integrated circuit, the number of components that can be placed on one has grown enormously. The first IC's contained a few tens of components; as of 2005, modern microprocessors such from AMD and Intel contain over 100 million transistors. Tubes, transistors, and transistors on integrated circuits can be and are used as the "storage" component of the stored-program architecture, using a circuit design known as a flip-flop, and indeed flip-flops are used for small amounts of very high-speed storage. However, few computer designs have used flip-flops for the bulk of their storage needs. Instead, earliest computers stored data in Williams tubes - essentially, projecting some dots on a TV screen and reading them again, or mercury delay lines where the data was stored as sound pulses traveling slowly (compared to the machine itself) along long tubes filled with mercury. These somewhat ungainly but effective methods were eventually replaced by magnetic memory devices, such as magnetic core memory, where electrical currents were used to introduce a permanent (but weak) magnetic field in some ferrous material, which could then be read to retrieve the data. Eventually, DRAM was introduced. A DRAM unit is a type of integrated circuit containing huge banks of an electronic component called a capacitor which can store an electrical charge for a period of time. The level of charge in a capacitor could be set to store information, and then measured to read the information when required.

I/O devices

I/O is a general term for devices that send computers information from the outside world and that return the results of computations. These results can either be viewed directly by a user, or they can be sent to another machine, whose control has been assigned the computer: In a robot, for instance, the controlling computer's major output device is the robot itself. The first generation of computers were equipped with a fairly limited range of input devices. A punch card reader, or something similar, was used to enter instructions and data into the computer's memory, and some kind of printer, usually a modified teletype, was used to record the results. Over the years, a huge variety of other devices have been added. For the personal computer, for instance, keyboards and mice are the primary ways people directly enter information into the computer; and monitors are the primary way in which information from the computer is presented back to the user, though printers, speakers, and headphones are common, too. There is a huge variety of other devices for obtaining other types of input. One example is the digital camera, which can be used to input visual information. There are two prominent classes of I/O devices. The first class is that of secondary storage devices, such as hard disks, CD-ROMs, key drives and the like, which represent comparatively slow, but high-capacity devices, where information can be stored for later retrieval; the second class is that of devices used to access computer networks. The ability to transfer data between computers has opened up a huge range of capabilities for the computer. The global Internet allows millions of computers to transfer information of all types between each other.

Instructions

The instructions interpreted by the control unit, and executed by the ALU, are not nearly as rich as a human language. A computer responds only to a limited number of instructions, but they are well defined, simple, and unambiguous. Typical sorts of instructions supported by most computers are "copy the contents of memory cell 5 and place the copy in cell 10", "add the contents of cell 7 to the contents of cell 13 and place the result in cell 20", "if the contents of cell 999 are 0, the next instruction is at cell 30". All computer instructions fall into one of four categories: 1) moving data from one location to another; 2) executing arithmetic and logical processes on data; 3) testing the condition of data; and 4) altering the sequence of operations. Instructions are represented within the computer as binary code - a base two system of counting. For example, the code for one kind of "copy" operation in the Intel line of microprocessors is 10110000. The particular instruction set that a specific computer supports is known as that computer's machine language. To slightly oversimplify, if two computers have CPUs that respond to the same set of instructions identically, software from one can run on the other without modification. This easy portability of existing software creates a great incentive to stick with existing designs, only switching for the most compelling of reasons, and has gradually narrowed the number of distinct instruction set architectures in the marketplace.

Programs

Computer programs are simply lists of instructions for the computer to execute. These can range from just a few instructions which perform a simple task, to a much more complex instruction list which may also include tables of data. Many computer programs contain millions of instructions, and many of those instructions are executed repeatedly. A typical modern PC (in the year 2005) can execute around 3 billion instructions per second. Computers do not gain their extraordinary capabilities through the ability to execute complex instructions. Rather, they do millions of simple instructions arranged by people known as programmers. In practice, people do not normally write the instructions for computers directly in machine language. Such programming is incredibly tedious and highly error-prone, making programmers very unproductive. Instead, programmers describe the desired actions in a "high level" programming language which is then translated into the machine language automatically by special computer programs (interpreters and compilers). Some programming languages map very closely to the machine language, such as Assembly Language (low level languages); at the other end, languages like Prolog are based on abstract principles far removed from the details of the machine's actual operation (high level languages). The language chosen for a particular task depends on the nature of the task, the skill set of the programmers, tool availability and, often, the requirements of the customers (for instance, projects for the US military were often required to be in the Ada programming language). Computer software is an alternative term for computer programs; it is a more inclusive phrase and includes all the ancillary material accompanying the program needed to do useful tasks. For instance, a video game includes not only the program itself, but also data representing the pictures, sounds, and other material needed to create the virtual environment of the game. A computer application is a piece of computer software provided to many computer users, often in a retail environment. The stereotypical modern example of an application is perhaps the office suite, a set of interrelated programs for performing common office tasks. Going from the extremely simple capabilities of a single machine language instruction to the myriad capabilities of application programs means that many computer programs are extremely large and complex. A typical example is the Firefox web browser, created from roughly 2 million lines of computer code in the C++ programming language; there are many projects of even bigger scope, built by large teams of programmers. The management of this enormous complexity is key to making such projects possible; programming languages, and programming practices, enable the task to be divided into smaller and smaller subtasks until they come within the capabilities of a single programmer in a reasonable period. Nevertheless, the process of developing software remains slow, unpredictable, and error-prone; the discipline of software engineering has attempted, with some partial success, to make the process quicker and more productive and improve the quality of the end product.

Libraries and operating systems

Soon after the development of the computer, it was discovered that certain tasks were required in many different programs; an early example was computing some of the standard mathematical functions. For the purposes of efficiency, standard versions of these were collected in libraries and made available to all who required them. A particularly common task set related to handling the gritty details of "talking" to the various I/O devices, so libraries for these were quickly developed. By the 1960s, with computers in wide industrial use for many purposes, it became common for them to be used for many different jobs within an organization. Soon, special software to automate the scheduling and execution of these many jobs became available. The combination of managing "hardware" and scheduling jobs became known as the "operating system"; the classic example of this type of early operating system was OS/360 by IBM. The next major development in operating systems was timesharing - the idea that multiple users could use the machine "simultaneously" by keeping all of their programs in memory, executing each user's program for a short time so as to provide the illusion that each user had their own computer. Such a development required the operating system to provide each user's programs with a "virtual machine" such that one user's program could not interfere with another's (by accident or design). The range of devices that operating systems had to manage also expanded; a notable one was hard disks; the idea of individual "files" and a hierarchical structure of "directories" (now often called folders) greatly simplified the use of these devices for permanent storage. Security access controls, allowing computer users access only to files, directories and programs they had permissions to use, were also common. Perhaps the last major addition to the operating system were tools to provide programs with a standardized graphical user interface. While there are few technical reasons why a GUI has to be tied to the rest of an operating system, it allows the operating system vendor to encourage all the software for their operating system to have a similar looking and acting interface. Outside these "core" functions, operating systems are usually shipped with an array of other tools, some of which may have little connection with these original core functions but have been found useful by enough customers for a provider to include them. For instance, Apple's Mac OS X ships with a digital video editor application. Not all operating systems provide all of the above functions; operating systems for smaller computers typically provide fewer, such as the highly minimal operating systems for early microcomputers. Embedded computers may have a specialized operating system, or sometimes none at all. Instead, the custom programs written for their task perform all necessary functions that would be performed by an operating system in less specialized roles.

Computer applications

Embedded computer The first electronic digital computers, with their large size and cost, mainly performed scientific calculations, often to support military objectives. The ENIAC was originally designed to calculate ballistics-firing tables for artillery, but it was also used to calculate neutron cross-sectional densities to help in the design of the hydrogen bomb. This calculation, performed in December, 1945 through January, 1946 and involving over a million punch cards of data, showed the design then under consideration would fail. (Many of the most powerful supercomputers available today are also used for nuclear weapons simulations.) The CSIR Mk I, the first Australian stored-program computer, evaluated rainfall patterns for the catchment area of the Snowy Mountains Scheme, a large hydroelectric generation project. Others were used in cryptanalysis, for example the first programmable (though not general-purpose) digital electronic computer, Colossus, built in 1943 during World War II. Despite this early focus of scientific and military engineering applications, computers were quickly used in other areas. From the beginning, stored program computers were applied to business problems. The LEO, a stored program-computer built by J. Lyons and Co. in the United Kingdom, was operational and being used for inventory management and other purposes 3 years before IBM built their first commercial stored-program computer. Continual reductions in the cost and size of computers saw them adopted by ever-smaller organizations. Moreover, with the invention of the microprocessor in the 1970s, it became possible to produce inexpensive computers. In the 1980s, personal computers became popular for many tasks, including book-keeping, writing and printing documents, calculating forecasts and other repetitive mathematical tasks involving spreadsheets. spreadsheet (1989) marked the acceptance of CGI in the visual effects industry.]] As computers have become cheaper, they have been used extensively in the creative arts as well. Sound, still pictures, and video are now routinely created (through synthesizers, computer graphics and computer animation), and near-universally edited by computer. They have also been used for entertainment, with the video game becoming a huge industry. Computers have been used to control mechanical devices since they became small and cheap enough to do so; indeed, a major spur for integrated circuit technology was building a computer small enough to guide the Apollo missions and the Minuteman missile, two of the first major applications for embedded computers. Today, it is almost rarer to find a powered mechanical device not controlled by a computer than to find one that is at least partly so. Perhaps the most famous computer-controlled mechanical devices are robots, machines with more-or-less human appearance and some subset of their capabilities. Industrial robots have become commonplace in mass production, but general-purpose human-like robots have not lived up to the promise of their fictional counterparts and remain either toys or research projects. Robotics, indeed, is the physical expressions of the field of artificial intelligence, a discipline whose exact boundaries are fuzzy but to some degree involves attempting to give computers capabilities that they do not currently possess but humans do. Over the years, methods have been developed to allow computers to do things previously regarded as the exclusive domain of humans - for instance, "read" handwriting, play chess, or perform symbolic integration. However, progress on creating a computer that exhibits "general" intelligence comparable to a human has been extremely slow.

Networking and the Internet

In the 1970s, computer engineers at research institutions throughout the US began to link their computers together using telecommunications technology. This effort was funded by ARPA, and the computer network that it produced was called the ARPANET. 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. In the phrase of John Gage and Bill Joy (of Sun Microsystems), "the network is 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 email and the World Wide Web, combined with the development of cheap, fast networking technologies like Ethernet and ADSL saw computer networking become ubiquitous almost everywhere. 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.

Computing professions and disciplines

In the developed world, virtually every profession makes use of computers. However, certain professional and academic disciplines have evolved that specialize in techniques to construct, program, and use computers. Terminology for different professional disciplines is still somewhat fluid and new fields emerge from time to time: however, some of the major groupings are as follows:
- Computer engineering is that branch of electronic engineering devoted to the physical construction of computers and their attendant components.
- Computer science is an academic study of the processes related to computation, such as developing efficient algorithms to perform specific tasks. It has tackled questions as to whether problems can be solved at all using a computer, how efficiently they can be solved, and how to construct efficient programs to compute solutions. A huge array of specialties has developed within computer science to investigate different classes of problem.
- Software engineering concentrates on methodologies and practices to allow the development of reliable software systems while minimizing, and reliably estimating, costs and timelines.
- Information systems concentrates on the use and deployment of computer systems in a wider organizational (usually business) context.
- Many disciplines have developed at the intersection of computers with other professions; one of many examples is experts in geographical information systems who apply computer technology to problems of managing geographical information.

References

- [http://www.andrew.mallett.net/tech Learn to configure your computer at Andy's Tech Page] category: computer science ja:コンピュータ ko:컴퓨터 ms:Komputer nb:Datamaskin simple:Computer th:คอมพิวเตอร์

Computer programs

A computer program or software program (usually abbreviated to "a program") is a step-by-step list of instructions written for a particular computer architecture in a particular computer programming language. A layman equivalent example would be writing a step-by-step list of instructions in English instructing a human how to make a Peanut butter and jelly sandwich (the human being the specific architecture). More often than not, computer programs are compiled or assembled into non-human readable format. Executable uncompiled programs are referred to as scripts.

Terminology

The term "program" specifically refers to the blocks of instruction code that are loaded into memory for execution by an interpreter. (See Program Execution below.) In comparison, the term "software" refers to the computer program and any resources related to it. This would include static data, components (plugins), configuration files, and so on. These resources are usually bundled together into a software package to be distributed. Software programs (collections of programs and related resources) are most frequently referred to as applications by end-users, as most users are focused on the abilities of application software (application programs) rather than system software. (Users see things differently than programmers.) Note: The British English spelling programme is, for the most part, no longer used to refer to computer programs, as most internationally-used computing terms use the words (and spelling conventions) adopted in the U.S..

Program Execution

A modern day computer program is loaded into memory (usually by the operating system), interpreted and then executed ("run") instruction by instruction until "program termination", either with success or through computer error. Some primitive types of computers ran instructions encoded in various ways, an example would be punch cards. Before a computer can execute any sort of program (including the operating system which is also a program) the computer hardware must be initialized. This is done by a piece of software stored on programmable memory chips installed by the manufacturer called the BIOS. The BIOS will attempt to initialize the boot sequence making the computer ready for miscellaneous program execution.

Programs vs Data

A program has been defined. Data can be defined as information that is to be processed by some program. When the entire scope of a computer system is taken into account, there are regions where the distinction between the two is not so evident. CPUs sometimes have a set of smaller instructions that control the computer's hardware, data can contain a program that is executed (see Scripting programming language), programs can be written to create another program; all of which making the comparison largely one of perspective. Some deny that the distinction between program and data is useful altogther. Writing a program to generate a computer program is called metaprogramming. One application of this is have a program generate code according to a certain given data set. A single program might not easily be able to account for all the different aspects of the given data. Analysing the data to create a program that can handle all the aspects might prove easier. Lisp is an example of a language that provides strong support for this aspect of programming. The weights stored in a neural network are a form of data. It is precisely these weights that, combined with the topology of the network, define the network's behavior. It is unclear what the values of these weights actually represent or whether these weights can be programmed. This and other questions pertaining to artificial intelligence further test the comparison between program and data.

Programming

Creating a computer program is the iterative process of implementing new source code (or simply just "code") and testing, analyzing and refining the newly implemented code for syntax and semantic errors. One who practices this skill is referred to as a computer programmer. Since the evolution of computers is so rapid, the tasks of a computer programmer have become more diverse giving rise to different classes of computer programmers, each with a more specialized task. Two examples are a software developer and a systems architect. The lengthy process of computer programming is now referred to as "software development" or software engineering. The latter becoming more popular due to the increasing maturity of the discipline. (see Debate over who is a software engineer) Hence, a contemporary computer programmer can refer to a specialist in one area of computer programming or to the general mass of programmers working for a software company who implement the bulk of the code in large scale software. A group of programmers working for a software company maybe assigned a lead programmer and a project manager to oversee project development and deadlines. Large scale software usually undergoes a lengthy design phase by a system architect before actual development and cowboy coding is frowned upon. Two other forms of modern day approaches are team programming where each member of the group has equal say in the development process except for one person who guides the group through discrepancies. These groups tend to be around 10 people to keep the group manageable. The second form is referred to as "peer programming" or pair programming. See Process and methodology for the different aspects of modern day computer programming.

Algorithms

A formal methodology to solve a particular problem usually combined with a study of different degrees of performance constitute an algorithm. Algorithms can be purely theoretical or implemented by a computer program. Where theoretical algorithms are usually classified in categories according to complexity , implemented algorithms are usually profiled to test routines for efficiency. Note that although an algorithm can be theoretically performant, it can be poorly implemented wasting valuable computer resources. (see Algorithmic information theory for more information)

Example of a program (source code)

The supplied code is a small program in assembly language written for a virtual computer . The example shows a selection of instructions with the corresponding address in memory where each instruction will be placed. These addresses are not static, see memory management. Accompanying each instruction is the generated (by compilation) object code that coincides with the virtual computer's architecture (or ISA). For more examples, see the hello world program.

Bibliography

- Miles J. Murdocca & Vincent P. Heuring (2000). Principles of Computer Architecture. Prentice-Hall, Inc. ISBN 0-201-43664-7
- [http://iiusaedu.com/~murdocca/POCA Principles of Computer Architecture] (POCA) – ARCTools virtual computer available for download to execute referenced code, accessed August 24, 2005
- J.Glenn Brookshear (1989). Theory of Computation, Formal Languages, Automata, and Complexity. The Benjamin/Cummings Publishing Co.Inc. ISBN 0-8053-0143-7

External links

- [http://www.webopedia.com/TERM/P/program.html Definition of Program @ Webopedia]
- [http://www.Agtivity.com/computer_program.htm Definition of Computer program @ Agtivity]
- [http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?query=software Definition of Software @ FOLDOC] Category:Computer science Category:Software
- ja:プログラム (コンピュータ) ko:프로그램 simple:Computer program th:โปรแกรม

Referential transparency

In computer programming, a referentially transparent function is one that, given the same parameter(s), always returns the same result. While in mathematics all functions are referentially transparent, in programming this is not always the case. For example, take a function that takes no parameters and returns input from the keyboard. A call to this function might be GetInput(). The return value of GetInput() depends on what the user feels like typing in, so multiple calls to GetInput() with identical parameters (the empty list) may return different results. A more subtle example is that of a function that uses a global variable (or a dynamically scoped variable, or a lexical closure) to help it compute its results. Since this variable is not passed as a parameter but can be altered, the results of subsequent calls to the function can differ even if the parameters are identical. (In pure functional programming, assignment is not allowed; thus a function that uses global (or dynamically scoped) variables is still referentially transparent, since these variables cannot change.) The importance of referential transparency is that it allows a programmer (or compiler) to reason about program behavior. This can help in proving correctness, finding bugs that could not be found through testing, simplifying an algorithm, assisting in modifying code without breaking it, or optimizing code by means of memoization. Some functional programming languages enforce referential transparency for all functions. Referential transparency will cause as a side effect that no difference is made or recognised between a reference to a thing and the corresponding thing itself. Without referential transparency, such difference can be easily made and utilized in programs.

Cache

For other uses, see Cache (disambiguation) or caché. In computer science, a cache (pronounced kăsh) is a collection of data duplicating original values stored elsewhere or computed earlier, where the original data are expensive (usually in terms of access time) to fetch or compute relative to reading the cache. Once the data are stored in the cache, future use can be made by accessing the cached copy rather than refetching or recomputing the original data, so that the average access time is lower. Caches have proven extremely effective in many areas of computing, because access patterns in typical computer applications have locality of reference. There are several sorts of locality, but we mainly mean that the same data are often used several times, with accesses that are close together in time, or that data near to each other are accessed close together in time.

Operation

locality of reference A cache is a pool of entries. Each entry has a datum, which is a copy of the datum in some backing store. Each entry also has a tag, which specifies the identity of the datum in the backing store of which the entry is a copy. When the cache client (a CPU, web browser, operating system) wishes to access a datum presumably in the backing store, it first checks the cache. If an entry can be found with a tag matching that of the desired datum, the datum in the entry is used instead. This situation is known as a cache hit. So, for example, a web browser program might check its local cache on disk to see if it has a local copy of the contents of a web page at a particular URL. In this example, the URL is the tag, and the contents of the web page is the datum. The percentage of accesses that result in cache hits is known as the hit rate or hit ratio of the cache. The alternative situation, when the cache is consulted and found not to contain a datum with the desired tag, is known as a cache miss. The datum fetched from the backing store during miss handling is usually inserted into the cache, ready for the next access. If the cache has limited storage, it may have to eject some other entry in order to make room. The heuristic used to select the entry to eject is known as the replacement policy. One popular replacement policy, LRU, replaces the least recently used entry. When a datum is written to the cache, it must at some point be written to the backing store as well. The timing of this write is controlled by what is known as the write policy. In a write-through cache, every write to the cache causes a write to the backing store. Alternatively, in a write-back cache, writes are not immediately mirrored to the store. Instead, the cache tracks which of its locations have been written over (these locations are marked dirty). The data in these locations is written back to the backing store when that data is evicted from the cache. For this reason, a miss in a write-back cache will often require two memory accesses to service. Data write-back may be triggered by other policies as well. The client may make many changes to a datum in the cache, and then explicitly notify the cache to write back the datum. The data in the backing store may be changed by entities other than the cache, in which case the copy in the cache may become out-of-date or stale. Alternatively, when the client updates the data in the cache, copies of that data in other caches will become stale. Communication protocols between the cache managers which keep the data consistent are known as coherency protocols.

Applications

CPU caches

Main article: CPU cache Small memories on or close to the CPU chip can be made faster than the much larger main memory. Most CPUs since the 1980s have used one or more caches, and modern general-purpose CPUs inside personal computers may have as many as half a dozen, each specialized to a different part of the problem of executing programs.

Disk buffer

(also known as disk cache or cache buffer) Hard disks have historically often been packaged with embedded computers used for control and interface protocols. Since the late 1980s, nearly all disks sold have these embedded computers and either an ATA, SCSI, or Fibre Channel interface. The embedded computer usually has some small amount of memory which it uses to store the bits going to and coming from the disk platter. The disk buffer is physically distinct from and is used differently than the page cache typically kept by the operating system in the computer's main memory. The disk buffer is controlled by the embedded computer in the disk drive, and the page cache is controlled by the computer to which that disk is attached. The disk buffer is usually quite small, 2 to 8 MB, and the page cache is generally all unused physical memory, which in a 2004 PC may be between 20 and 2000 MB. And while data in the page cache is reused multiple times, the data in the disk buffer is typically never reused. In this sense, the phrases disk cache and cache buffer are misnomers, and the embedded computer's memory is more appropriately called the disk buffer. The disk buffer has multiple uses:
- Readahead / readbehind: When executing a read from the disk, the disk arm moves the read/write head to (or near) the correct track, and after some settling time the read head begins to pick up bits. Usually, the first sectors to be read are not the ones that have been requested by the operating system. The disk's embedded computer typically saves these unrequested sectors in the disk buffer, in case the operating system requests them later.
- Speed matching: The speed of the disk's I/O interface to the computer almost never matches the speed at which the bits are transferred to and from the hard disk platter. The disk buffer is used so that both the I/O interface and the disk read/write head can operate at full speed.
- Write acceleration: The disk's embedded computer may signal the main computer that a disk write is complete immediately after receiving the write data, before the data are actually written to the platter. This early signal allows the main computer to continue working, but is somewhat dangerous because, if power is lost before the data are permanently fixed in the magnetic media, the data will be lost from the disk buffer, and the filesystem on the disk may be left in an inconsistent state. Write acceleration is controversial, and for this reason can usually be turned off. On some disks, this vulnerable period between signaling the write complete and fixing the data can be arbitrarily long, as the write can be deferred indefinitely by newly arriving requests. Write acceleration is very rarely used on database servers or other machines where the integrity of the data on the disks is very important. In some cases, write acceleration caching is done by a RAID controller, which uses a battery-backed memory system for caching data.
- Command queueing: Newer SATA and most SCSI disks can accept multiple commands while any one command is in operation. These commands are stored by the disk's embedded computer until they are completed. Should a read reference the data at the destination of a queued write, the write's data will be returned. Command queueing is different from write acceleration in that the main computer's operating system is notified when data are actually written onto the magnetic media. The OS can use this information to keep the filesystem consistent through rescheduled writes.

Other caches

CPU caches are generally managed entirely by hardware. Other caches are managed by a variety of software. The cache of disk sectors in main memory is usually managed by the operating system kernel or file system. The BIND DNS daemon caches a mapping of domain names to IP addresses, as does a resolver library. Write-through operation is common when operating over unreliable networks (like an ethernet LAN), because of the enormous complexity of the coherency protocol required between multiple write-back caches when communication is unreliable. For instance, web page caches and client-side network file system caches (like those in NFS or SMB) are typically read-only or write-through specifically to keep the network protocol simple and reliable. A cache of recently visited web pages can be managed by your Web browser. Some browsers are configured to use an external proxy web cache, a server program through which all web requests are routed so that it can cache frequently accessed pages for everyone in an organization. Many internet service providers use proxy caches to save bandwidth on frequently-accessed web pages. The Google search engine keeps a cached copy of each page it examines on the web. These copies are used by the Google indexing software, but they are also made available to Google users, in case the original page is unavailable. If you click on the "Cached" link in a Google search result, you will see the web page as it looked when Google indexed it. Another type of caching is storing computed results that will likely be needed again, or memoization. An example of this type of caching is ccache, a program that caches the output of the compilation to speed up the second-time compilation.

External links

Category:Computer architecture Category:Computer hardware Category:Computer memory als:Cache ms:Cache ja:キャッシュ (コンピュータシステム)

Higher-order function

In mathematics and computer science, higher-order functions are functions which do at least one of the following:
- take one or more functions as an input
- output a function In mathematics these are also known as operators or functionals. The derivative in calculus is a common example, since it maps a function to another function. In the untyped lambda calculus, all functions are higher-order; in a typed lambda calculus, from which most functional programming languages are derived, higher-order functions are generally those with types containing more than one arrow. In functional programming, higher-order functions that return other functions are said to be curried. The map function found in many functional programming languages is one example of a higher-order function. It takes a function f as an argument, and returns a new function which takes a list and applies the f to each element. Other examples of higher-order functions include function composition, integration, and the constant-function function λx.λy.x.

Alternatives

Programming languages can achieve some of the same algorithmic results as are obtained through higher-order functions by dynamically executing code (sometimes called "Eval" or "Execute" operations) in the scope of evaluation. Unfortunately, there are significant drawbacks to this approach:
- The argument code to be executed is usually not statically typed; these languages generally rely on dynamic typing to determine the well-formedness and safety of the code to be executed.
- The argument is usually provided as a string, the value of which may not be known until run-time. This string must either be compiled during program execution (using just-in-time compilation) or evaluated by interpretation, causing some additional overhead at run-time. In rare cases, this may actually result in faster overall execution because more information is available for optimization. Macros can also be used to achieve some of the effects of higher order functions. However, macros usually cannot avoid the problem of variable capture; they may also result in large amounts of duplicated code, which can be more difficult for a compiler to optimize. Macros are generally not strongly typed, although they may produce strongly typed code. Objects in an object-oriented programming environment can be used as higher order functions – a method of an object acts in many ways like a function, and a method may take objects (containing methods) as arguments or return objects with methods. Unfortunately, objects often carry additional run-time overhead compared to pure functions. Language syntax can introduce additional difficulties; an object must be created to hold any parameters that are functions, and any resulting function must also have an associated object.

Latin

Latin is an ancient Indo-European language originally spoken in the region around Rome called Latium. It gained great importance as the formal language of the Roman Empire. All Romance languages, those being most notably Spanish, French, Portuguese, Italian, and Romanian, are descended from Latin, and many words based on Latin are found in other modern languages such as English. The Latin alphabet, derived from the Greek, remains the most widely-used alphabet in the world. It is said that 80 percent of scholarly English words are derived from Latin (in a large number of cases by way of French). Moreover, in the Western world, Latin was a lingua franca, the learned language for scientific and political affairs, for more than a thousand years, being eventually replaced by French in the 18th century and English in the late 19th. Ecclesiastical Latin remains the formal language of the Roman Catholic Church to this day, and thus the official national language of the Vatican. The Church used Latin as its primary liturgical language until the Second Vatican Council in the 1960s. Latin is also still used (drawing heavily on Greek roots) to furnish the names used in the scientific classification of living things. The modern study of Latin, along with Greek, is known as Classics.

Main features

Latin is a synthetic inflectional language: affixes (which usually encode more than one grammatical category) are attached to fixed stems to express gender, number, and case in adjectives, nouns, and pronouns, which is called declension; and person, number, tense, voice, mood, and aspect in verbs, which is called conjugation. There are five declensions (declinationes) of nouns and four conjugations of verbs. There are six noun cases: #nominative (used as the subject of the verb or the predicate nominative), #genitive (used to indicate relation or possession, often represented by the English of or the addition of s to a noun), #dative (used of the indirect object of the verb, often represented by the English to or for), #accusative (used of the direct object of the verb, or object of the preposition in some cases), #ablative (separation, source, cause, or instrument, often represented by the English by, with, from), #vocative (used of the person or thing being addressed). In addition, some nouns have a locative case used to express location (otherwise expressed by the ablative with a preposition such as in), but this survival from Proto-Indo-European is found only in the names of lakes, cities, towns, small islands, and a few other words related to locations, such as "house", "ground", and "countryside". Latin itself, being a very old language, is far closer to Proto-Indo-European than are most modern Western European languages; it has, in fact, about the same relationship with PIE as modern Italian or French has to Latin. There are six general tenses in Latin (technically they are tense/aspect/mood complexes). The indicative mood can be used with all of them. The subjunctive mood, however, has only present, imperfect, perfect, and pluperfect tenses. These tenses in the subjunctive mood do not completely correlate in meaning to the tenses in the indicative. The following examples are of the first conjugation verb "laudare" ("to praise") in the indicative mood and the active voice:
Primary sequence tenses
# present (laudo, "I praise") # imperfect (laudabam, "I was praising") # future (laudabo, "I shall praise," "I will praise")
Secondary sequence tenses
# perfect (laudavi, "I praised", "I have praised") # pluperfect (laudaveram, "I had praised") # future perfect (laudavero, "I shall have praised," "I will have praised") The future perfect tense can also imply a normal future idea (like in "When I will have run...") and so may also sometimes be included in the primary sequence.
Latin and Romance
After the collapse of the Roman Empire, Latin evolved into the various Romance languages. These were for many centuries only spoken languages, Latin still being used for writing. For example, Latin was the official language of Portugal until 1296 when it was replaced by Portuguese. The Romance languages evolved from Vulgar Latin, the spoken language of common usage, which in turn evolved from an older speech which also produced the formal classical standard. Latin and Romance differ (for example) in that Romance had distinctive stress, whereas Latin had distinctive length of vowels. In Italian and Sardo logudorese, there is distinctive length of consonants and stress, in Spanish only distinctive stress, and in French even stress is no longer distinctive. Another major distinction between Romance and Latin is that all Romance languages, excluding Romanian, have lost their case endings in most words except for some pronouns. Romanian retains a direct case (nominative/accusative), an indirect case (dative/genitive), and vocative. In Italy, Latin is still compulsory in secondary schools as Liceo Classico and Liceo Scientifico which are usually attended by people who aim to the highest level of education. In Liceo Classico Ancient Greek is a compulsory subject.
Latin and English
See Latin influence in English for a more complete exposition. English grammar is independent of Latin grammar, though prescriptive grammarians in English have been heavily influenced by Latin. Attempts to make English grammar follow Latin rules — such as the prohibition against the split infinitive — have not worked successfully in regular usage. However, as many as half the words in English were derived from Latin, including many words of Greek origin first adopted by the Romans, not to mention the thousands of French, hundreds of Spanish, Portuguese and Italian words of Latin origin that have also enriched English. During the 16th and on through the 18th century English writers created huge numbers of new words from Latin and Greek roots. These words were dubbed "inkhorn" or "inkpot" words (as if they had spilled from a pot of ink). Many of these words were used once by the author and then forgotten, but some remain. Imbibe, extrapolate, dormant and inebriation are all inkhorn terms carved from Latin words. In fact, the word etymology is derived from the Greek word etymologia, meaning "true sense of the word." Latin was once taught in many of the schools in Britain with academic leanings - perhaps 25% of the total [http://www.channel4.com/history/microsites/T/teachem2/thennow/]. However, the requirement for it was gradually abandoned in the professions such as the law and medicine, and then, from around the late 1960s, for admission to university. After the introduction of the Modern Language GCSE in the 1980s, it was gradually replaced by other languages, although it is now being taught by more schools along with other classical languages.
Latin education
The linguistic element of Latin courses offered in high schools or secondary schools, and in universities, is primarily geared toward an ability to translate Latin texts into modern languages, rather than using it in oral communication. As such, the skill of reading is heavily emphasized, whereas speaking and listening skills are barely touched upon. However, there is a growing movement, sometimes known as the Living Latin movement, whose supporters believe that Latin can, or should, be taught in the same way that modern "living" languages are taught, that is, as a means of both spoken and written communication. One of the most interesting aspects of such an approach is that it assists speculative insight into how many of the ancient authors spoke and incorporated sounds of the language stylistically; without understanding how the language is meant to be heard it is very difficult to identify patterns in Latin poetry. Institutions offering Living Latin instruction include the Vatican and the University of Kentucky. In Britain the Classical Association encourages this approach, and there has been something of a vogue for books describing the adventures of a mouse called Minimus. In the United States there is a thriving competitive organization for high school Latin students, the National Junior Classical League (the second-largest youth organization in the world after the Boy Scouts), backed up by the Senior Classical League for college students. Many would-be international auxiliary languages have been heavily influenced by Latin, and the moderately successful Interlingua considers itself to be the modernized and simplified version of the language (le latino moderne international e simplificate). Latin translations of modern literature such as Paddington Bear, Winnie the Pooh, Harry Potter and the Philosopher's Stone, Le Petit Prince, Max und Moritz, and The Cat in the Hat have also helped boost interest in the language.
See also

About the Latin language

- Latin grammar
- Latin spelling and pronunciation
- Latin declension
- Latin conjugation
- Latin alphabet
- List of Latin words with English derivatives
- Latin verbs with English derivatives
- Latin nouns with English derivatives
- ablative absolute
- Word order in Latin
About the Latin literary heritage

- Latin literature
- Romance languages
- Loeb Classical Library
- List of Latin phrases
- List of Latin proverbs
- Brocard
- List of Latin and Greek words commonly used in systematic names
- List of Latin place names in Europe
- Carmen Possum
Other related topics

- Roman Empire
- Internationalism
References

- Bennett, Charles E. Latin Grammar (Allyn and Bacon, Chicago, 1908)
- N. Vincent: "Latin", in The Romance Languages, M. Harris and N. Vincent, eds., (Oxford Univ. Press. 1990), ISBN 0195208293
- Waquet, Françoise, Latin, or the Empire of a Sign: From the Sixteenth to the Twentieth Centuries (Verso, 2003) ISBN 1859844022; translated from the French by John Howe.
- Wheelock, Frederic. Latin: An Introduction (Collins, 6th ed., 2005) ISBN 0060784237
External links

- [http://www.jambell.com/latin.html Latin Phrases for after dinner conversation (Thanks to Elaine Poole)]
- [http://www.ethnologue.com/show_language.asp?code=lat Ethnologue report for Latin]
- [http://forumromanum.org/literature/index.html Corpus Scriptorum Latinorum] is a comprehensive webography of Latin texts and their translations.
- [http://www.perseus.tufts.edu/ The Perseus Project] has many useful pages for the study of classical languages and literatures, including [http://www.perseus.tufts.edu/cgi-bin/resolveform?lang=Latin an interactive Latin dictionary].
- [http://lysy2.archives.nd.edu/cgi-bin/words.exe words by William whitaker] is a dictionary program online capable of looking up various word forms.
- [http://retiarius.org/ Retiarius.Org] includes a Latin text search engine.
- [http://www.nd.edu/~archives/latgramm.htm Latin-English dictionary and Latin grammar from U of Notre Dame]
- [http://latin-language.co.uk/ Latin language] History of Latin language, Latin texts with English translation and a collection of dictionaries.
- [http://augustinus.eresmas.net/scl/ Societas Circulorum Latinorum] gathers together Latin Circles all over the world.
- [http://www.learnlatin.tk LearnLatin.tk] - Free online course in Latin
- [http://www.latintests.net/ LatinTests.net] - Lets Latin learners test their grammar and vocabulary with self-checking quizzes.
- [http://thelatinlibrary.com/ The Latin Library] contains many Latin etexts
- [http://www.textkit.com/ Textkit] has Latin textbooks and etexts.
- [http://www.websters-online-dictionary.org/definition/Latin-english/ Latin–English Dictionary]: from Webster's Rosetta Edition.
- [http://www.language-reference.com/ Language reference] Cross-foreign-language lexicon powered by its own search engine. All cross combinations between Latin and French, German, Italian, Spanish.
- [http://comp.uark.edu/~mreynold/rhetor.html Rhetor by Gabriel Harvey] was originally published in 1577 and never again reprinted.
- [http://freewebs.com/omniamundamundis omniamundamundis] Latin hypertexts from fourteen ancient Roman authors.
- [http://www.saltspring.com/capewest/pron.htm Pronunciation of Biological Latin, Including Taxonomic Names of Plants and Animals]
- [http://www.yleradio1.fi/nuntii Nuntii Latini (News in Latin)], written and spoken (RealAudio) news in latin. Weekly review of world news in Classical Latin, the only international broadcast of its kind in the world, produced by YLE, the Finnish Broadcasting Company.
- [http://www.tranexp.com:2000/InterTran?url=http%3A%2F%2F&type=text&text=Replace%20Me&from=eng&to=ltt InterTran Latin], Translate from Latin to ENGLISH or vice versa.
- [http://www.latinvulgate.com Latin Vulgate] The Latin and English of the Old & New Testaments in parallel, along with the Complete Sayings of Jesus in parallel Latin and English. Category:Classical languages Category:Ancient languages Category:Fusional languages Category:Languages of Italy Category:Languages of Vatican City als:Latein zh-min-nan:Latin-gí ko:라틴어 ja:ラテン語 simple:Latin language th:ภาษาละติน

Memorandum

A memorandum is a written form of communication most often employed in business environments. It is used as a means of communication between executives and their employees. A memorandum is typically written using the following structure: TO: FROM: DATE: the date of when the memorandum is being distributed SUBJECT: - Opening statement, that states the purpose of the memorandum. - Discussion segment, where the subject is developed. - Closing statements, that notifies the reader of what providences must follow. A memorandum can also be a legal document setting out the terms of an agreement or contract as in a "Memorandum of Sale" or "Memorandum of Shipment".

Internal links

See also business memo for a guide on how to create and format a business memo.

External links

- [http://owl.english.purdue.edu/handouts/pw/p_memo.html Memo Writing Brought to you by the Purdue University Online Writing Lab]
- [http://www.internalmemos.com Internal Memos], large internet collection of corporate memos and internal communication
- [http://www.uchicago.edu/research/jnl-crit-inq/features/artsstatements/arts.guillory.htm Article]: The Memo and Modernity

Big O notation

Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. More precisely, it is used to describe an asymptotic upper bound for the magnitude of a function in terms of another, usually simpler, function. It has two main areas of application: in mathematics, it is usually used to characterize the residual term of a truncated infinite series, especially an asymptotic series. In computer science, it is useful in the analysis of the complexity of algorithms. It was first introduced by German number theorist Paul Bachmann in his 1892 book Analytische Zahlentheorie. The notation was popularized in the work of another German number theorist Edmund Landau, hence it is sometimes called a Landau symbol. The big-O, standing for "order of", was originally a capital omicron; today the capital letter O is used, but never the digit zero.

Uses

There are two formally close, but noticeably different usages of this notation: infinite asymptotics and infinitesimal asymptotics. This distinction is only in application and not in principle, however—the formal definition for the "big O" is the same for both cases, only with different limits for the function argument.

Infinite asymptotics

Big O notation is useful when analyzing algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size n might be found to be T(n) = 4n² - 2n + 2. As n grows large, the n² term will come to dominate, so that all other terms can be neglected. Further, the coefficients will depend on the precise details of the implementation and the hardware it runs on, so they should also be neglected. Big O notation captures what remains: we write :

T(n)\in O(n^2)

and say that the algorithm has order of n² time complexity.

Infinitesimal asymptotics

Big O can also be used to describe the error term in an approximation to a mathematical function. For example, :

e^x=1+x+x^2/2+\hbox(x^3)\qquad\hbox\ x\to 0

expresses the fact that the error (the difference

e^x - (1 + x + x^2/2)

) is smaller in absolute value than some constant times x³ if x is close enough to 0.

Formal definition

Suppose f(x) and g(x) are two functions defined on some subset of the real numbers. We say :f(x) is O(g(x)) as x

\to

∞ if and only if :there exist numbers x₀ and M such that |f(x)| ≤ M |g(x)| for x > x₀. The notation can also be used to describe the behavior of f near some real number a: we say :f(x) is O(g(x)) as x

\to

a if and only if :there exists numbers δ>0 and M such that |f(x)| ≤ M |g(x)| for |x - a| < δ. If g(x) is non-zero for values of x sufficiently close to a, both of these definitions can be unified using the limit superior: :f(x) is O(g(x)) as x

\to

a if and only if :

\limsup_ \left|\frac\right| < \infty.

Image:Yorick215.PNG In mathematics, both asymptotic behaviors near ∞ and near a are considered. In computational complexity theory, only asymptotics near ∞ are used; furthermore, only positive functions are considered, so the absolute value bars may be left out.

Example

Take the polynomials: :

f(x) = 6x^4 -2x^3 +5 \,

g(x) = x^4.  \,

We say f(x) has order O(g(x)) or O(x⁴). From the definition of order, |f(x)| ≤ C |g(x)| for all x>1, where C is a constant. Proof: :

|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^3 + 5 \,

where x > 1 :

|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^4 + 5x^4 \,

because x³ < x⁴, and so on. :

|6x^4 - 2x^3 + 5| \le 13x^4 \,

|6x^4 - 2x^3 + 5| \le 13 \,|x^4 |. \,

Matters of notation

The statement "f(x) is O(g(x))" as defined above is often written as f(x) = O(g(x)). This is a slight abuse of notation: we are not really asserting the equality of two functions. The property of being O(g(x)) is not symmetric: :

\mbox(x)\,=\,\mbox(x^2)

but

\mbox(x^2)\,\ne\,\mbox(x)

. For this reason, some authors prefer a set notation and write f

\in

O(g), thinking of O(g) as the set of all functions dominated by g. Furthermore, an "equation" of the form :

f(x) = h(x) + \mbox(g(x))

should be understood as "the difference of f(x) and h(x) is O(g(x))".

Common orders of functions

Here is a list of classes of functions that are commonly encountered when analyzing algorithms. All of these are as n increases to infinity. The slower-growing functions are listed first. c is an arbitrary constant. Not as common, but even larger growth is possible, such as the single-valued version of the Ackermann function, A(n,n). Conversely, extremely slowly-growing functions such as the inverse of this function, often denoted α(n), are possible. Although unbounded, these functions are often regarded as being constant factors for all practical purposes.

Properties

If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n). For example :

f(n) = 10 \log n + 5 (\log n)^3 + 7n + 3n^2 + 6n^3 \in \hbox(n^3)\,\!

. In particular, if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial. O(n^c) and O(cⁿ) are very different. The latter grows much, much faster, no matter how big the constant c is (so long as it is greater than one). A function that grows faster than any power of n is called superpolynomial. One that grows slower than any exponential function of the form cⁿ is called subexponential. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest known algorithms for integer factorization. O(log n) is exactly the same as O(log(n^c)). The logarithms differ only by a constant factor, (since log(n^c)=c log n) and thus the big O notation ignores that. Similarly, logs with different constant bases are equivalent.

Product

O(f(n)) O(g(n)) 
= O(f(n)g(n)) \,

Sum

O(f(n)) + O(g(n)) = O(\max \lbrace f(n),g(n) \rbrace) \,

Multiplication by a constant

O(k g(n)) = O(g(n)) \!\,

, k≠0

Addition of a constant

O(k\ + g(n)) = O(g(n))

unless g(n) ∈ o(1), in which case it is O(1). Other useful relations are given in section Big O and little o below.

Related asymptotic notations: O, o, Ω, ω, Θ, Õ

Big O is the most commonly used asymptotic notation for comparing functions, although it is often actually an informal substitute for Θ (Theta, see below). Here, we define some related notations in terms of "big O": Here "lim sup" and "lim inf" denote limit superior and limit inferior. (A mnemonic for these Greek letters is that "omicron" can be read "o-micron", i.e., "o-small", whereas "omega" can be read "o-mega" or "o-big".) The relation f(n) = o(g(n)) is read as "f(n) is little-oh of g(n)". Intuitively, it means that g(n) grows much faster than f(n). Formally, it states that the limit of f(n)/g(n) is zero. Aside from big-O, the notations Θ and Ω are the two most often used in computer science; the lower-case o is common in mathematics but rarer in computer science. The lower-case ω is rarely used. In casual use, O is commonly used where Θ is meant, i.e., when a tight estimate is implied. For example, one might say "heapsort is O(n log n) in the average case" when the intended meaning was "heapsort is Θ(n log n) in the average case". Both statements are true, but the latter is a stronger claim. Another notation sometimes used in computer science is Õ (read Soft-O). f(n) = Õ(g(n)) is shorthand for f(n) = O(g(n) log^kg(n)) for some k. Essentially, it is Big-O, ignoring logarithmic factors. This notation is often used to describe a class of "nitpicking" estimates (since log^kn is always o(n) for any constant k).

Big O and little o

The following properties can be useful:
- o(f ) + o(f ) ∈ o(f )
- o(f ) o(g ) ∈ o(fg )
- o(o(f )) ∈ o(f )
- o(f ) ∈ O(f ) (and thus the above properties apply with most combinations of o and O).

Multiple variables

Big O (and little o, and Ω...) can also be used with multiple variables. For example, the statement :

f(n,m) = n^2 + m^3 + \hbox(n+m) \mbox n,m\to\infty

asserts that there exist constants C and N such that :

\forall n, m>N:f(n,m) \le n^2 + m^3 + C(n+m).

To avoid ambiguity, the running variable should always be specified: the statement :

f(n,m) = \hbox(n^m) \mbox n,m\to\infty

is quite different from :

\forall m: f(n,m) = \hbox(n^m) \mbox n\to\infty.

External links

- [http://www.cprogramming.com/tutorial/computersciencetheory/algorithmicefficiency1.html Cprogramming.com: Algorithm Efficiency] An article on the Big O in C

References

- Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.11: Asymptotic Representations, pp.107–123.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 3.1: Asymptotic notation, pp.41–50.
- Pages 226–228 of section 7.1: Measuring complexity. Category:Mathematical notation Category:Mathematical analysis Category:Asymptotic analysis ko:대문자 O 표기법 th:สัญกรณ์โอใหญ่

Closure (computer science)

In programming languages, a closure is an abstraction that combines a function and a special lexical environment bound to that function. The variables in the lexical environment are designed to retain state information between function calls. Unlike garden-variety functions which retain no memory of what happened in previous calls, closures are capable of storing information across function calls. Closure lexical variables differ from global variables in that they do not occupy (or pollute) the global variable namespace. They differ from object oriented object variables in that they are bound to functions and not objects. Closures are useful when functions need to "remember" information from a previous call. One common use is for a function to take special actions the first time it is called, but remember that these actions are not necessary every time the function is called.

Implementation and Theory

Closures are typically implemented with a special data structure that contains a pointer to the function code, plus a representation of the function's lexical environment (i.e., the set of available variables and their values) at the time when the function was created. Closures are closely related to Actors in the Actor model of concurrent computation where the values in the function's lexical environment are called acquaintances. An important issue for closures in concurrent programming languages is whether the variables in a closure can be updated and if so how these updates can be synchronized. Actors provide one solution (Will Clinger [1981]).

Closures and functions

Closures typically appear in languages that allow functions to be first-class values—in other words, such languages allow functions to be passed as arguments, returned from function calls, bound to variable names, etc., just like simpler types such as strings and integers. For example, in ML, the following code defines a function f that returns its argument plus 1: fun f(x) = x + 1; Such a function may capture name/value bindings from its enclosing environment, producing a closure. For example, in the code fragment: val x = 1; fun f(y) = x + y; the closure data structure representing f contains a pointer to the enclosing environment, in which x is bound to 1. Therefore, f will always return its argument plus 1, even if the environment in which it is applied has a different value for x. Therefore, consider the code fragment: let val x = 1; fun f(y) = x + y; in let val x = 2; in f(3) end end In this code, the call f(3) occurs in an environment (the inner let) where x is bound to 2. However, the closure for f was constructed in an environment (the outer let) where x is bound to 1. Therefore the result of the call f(3) is 4, not 5.

Uses of Closures

Closures have many uses:
- Designers of software libraries can allow users to customize behavior by passing closures as arguments to important functions. For example, a function that sorts values can accept a closure argument that compares the values to be sorted according to a user-defined criterion.
- Because closures delay evaluation—i.e., they do not "do" anything until they are called—they can be used to define control structures. For example, all Smalltalk's standard control structures, including branches (if/then/else) and loops (while and for), are defined using objects whose methods accept closures. Users can easily define their own control structures as well.
- Multiple functions can be produced which close over the same environment, enabling them to communicate privately by altering that environment. Note: Some speakers call any data structure that binds a lexical environment a closure, but the term usually refers specifically to functions.

Programming languages with closures

Scheme was the first programming language to have fully general, lexically scoped closures. Virtually all functional programming languages, as well as the Smalltalk-descended object-oriented programming languages, support some form of closures. Some prominent languages that support closures include:
- Haskell
- Lisp (including Scheme)
- JavaScript
- ActionScript
- All variants of ML (including OCaml and Standard ML)
- Python
- Perl
- Ruby
- Sleep
- Smalltalk
- Oz
- Lua
- Boo
- Groovy
- C# from version 2.0
- Nemerle
- Eiffel
- AppleScript
- Matlab

Simulating closures

In C you could use the "static" keyword in front of local variable declarations. A static variable retains its value between function calls. This also applies to C++ since it is a superset of C. int Function( int arg ) Some object-oriented languages enable the programmer to use objects to simulate some features of closures. For example:
- Java allows the programmer to define "anonymous classes" inside a method; an anonymous class may refer to names in lexically enclosing classes, or final names in the lexically enclosing method. public interface Function ... public final Function createAdder(final int x) ... (Note that this example uses Java 1.5/5.0's generics, autoboxing and autounboxing syntax.)
- In C++ and D, programmers may define classes that overload the () (function application) operator. Instances of such classes are called function objects, or occasionally functors (although the latter term is confusing, because it has a very different meaning in other programming languages). Such function objects behave somewhat like functions in a functional programming language, but they are different from closures in that variables from their environment are not captured. To approximate an actual closure, one can imagine placing all global variables in a single struct, a copy of which can be passed to a function object.
- C# allows a delegate to store reference to method of class instance; when calling such delegate, the method is invoked for the particular instance. To approximate an actual closure, one can create class instance (i.e. object) with required data members. Another way to support closures was introduced in version 2.0 of C# using "anonymous methods".