text:
Compiler

In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language). The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a low-level programming language (e.g. assembly language, object code, or machine code) to create an executable program.

There are many different types of compilers which produce output in different useful forms. A cross-compiler produces code for a different CPU or operating system than the one on which the cross-compiler itself runs. A bootstrap compiler is often a temporary compiler, used for compiling a more permanent or better optimised compiler for a language.

Related software include decompilers, programs that translate from low-level languages to higher level ones; programs that translate between high-level languages, usually called source-to-source compilers or transpilers; language rewriters, usually programs that translate the form of expressions without a change of language; and compiler-compilers, compilers that produce compilers (or parts of them), often in a generic and reusable way so as to be able to produce many differing compilers.

A compiler is likely to perform some or all of the following operations, often called phases: preprocessing, lexical analysis, parsing, semantic analysis (syntax-directed translation), conversion of input programs to an intermediate representation, code optimization and machine specific code generation. Compilers generally implement these phases as modular components, promoting efficient design and correctness of transformations of source input to target output. Program faults caused by incorrect compiler behavior can be very difficult to track down and work around; therefore, compiler implementers invest significant effort to ensure compiler correctness.

Compilers are not the only language processor used to transform source programs. An interpreter is computer software that transforms and then executes the indicated operations. The translation process influences the design of computer languages, which leads to a preference of compilation or interpretation. In theory, a programming language can have both a compiler and an interpreter. In practice, programming languages tend to be associated with just one (a compiler or an interpreter).

History
Theoretical computing concepts developed by scientists, mathematicians, and engineers formed the basis of digital modern computing development during World War II. Primitive binary languages evolved because digital devices only understand ones and zeros and the circuit patterns in the underlying machine architecture. In the late 1940s, assembly languages were created to offer a more workable abstraction of the computer architectures. Limited memory capacity of early computers led to substantial technical challenges when the first compilers were designed. Therefore, the compilation process needed to be divided into several small programs. The front end programs produce the analysis products used by the back end programs to generate target code. As computer technology provided more resources, compiler designs could align better with the compilation process.

It is usually more productive for a programmer to use a high-level language, so the development of high-level languages followed naturally from the capabilities offered by digital computers. High-level languages are formal languages that are strictly defined by their syntax and semantics which form the high-level language architecture. Elements of these formal languages include:
 * Alphabet, any finite set of symbols;
 * String, a finite sequence of symbols;
 * Language, any set of strings on an alphabet.

The sentences in a language may be defined by a set of rules called a grammar.

Backus–Naur form (BNF) describes the syntax of "sentences" of a language. It was developed by John Backus and used for the syntax of Algol 60. The ideas derive from the context-free grammar concepts by linguist Noam Chomsky. "BNF and its extensions have become standard tools for describing the syntax of programming notations. In many cases, parts of compilers are generated automatically from a BNF description."

Between 1942 and 1945, Konrad Zuse designed the first (algorithmic) programming language for computers called Plankalkül ("Plan Calculus"). Zuse also envisioned a Planfertigungsgerät ("Plan assembly device") to automatically translate the mathematical formulation of a program into machine-readable punched film stock. While no actual implementation occurred until the 1970s, it presented concepts later seen in APL designed by Ken Iverson in the late 1950s. APL is a language for mathematical computations.

Between 1949 and 1951, Heinz Rutishauser proposed Superplan, a high-level language and automatic translator. His ideas were later refined by Friedrich L. Bauer and Klaus Samelson.

High-level language design during the formative years of digital computing provided useful programming tools for a variety of applications:
 * FORTRAN (Formula Translation) for engineering and science applications is considered to be one of the first actually implemented high-level languages and first optimizing compiler.
 * COBOL (Common Business-Oriented Language) evolved from A-0 and FLOW-MATIC to become the dominant high-level language for business applications.
 * LISP (List Processor) for symbolic computation.

Compiler technology evolved from the need for a strictly defined transformation of the high-level source program into a low-level target program for the digital computer. The compiler could be viewed as a front end to deal with the analysis of the source code and a back end to synthesize the analysis into the target code. Optimization between the front end and back end could produce more efficient target code.

Some early milestones in the development of compiler technology:
 * May 1952: Grace Hopper's team at Remington Rand wrote the compiler for the A-0 programming language (and coined the term compiler to describe it),  although the A-0 compiler functioned more as a loader or linker than the modern notion of a full compiler.
 * 1952, before September: An Autocode compiler developed by Alick Glennie for the Manchester Mark I computer at the University of Manchester is considered by some to be the first compiled programming language.
 * 1954–1957: A team led by John Backus at IBM developed FORTRAN which is usually considered the first high-level language. In 1957, they completed a FORTRAN compiler that is generally credited as having introduced the first unambiguously complete compiler.
 * 1959: The Conference on Data Systems Language (CODASYL) initiated development of COBOL. The COBOL design drew on A-0 and FLOW-MATIC. By the early 1960s COBOL was compiled on multiple architectures.
 * 1958–1960: Algol 58 was the precursor to ALGOL 60. It introduced code blocks, a key advance in the rise of structured programming. ALGOL 60 was the first language to implement nested function definitions with lexical scope. It included recursion. Its syntax was defined using BNF. ALGOL 60 inspired many languages that followed it. Tony Hoare remarked: "... it was not only an improvement on its predecessors but also on nearly all its successors."
 * 1958–1962: John McCarthy at MIT designed LISP. The symbol processing capabilities provided useful features for artificial intelligence research. In 1962, LISP 1.5 release noted some tools: an interpreter written by Stephen Russell and Daniel J. Edwards, a compiler and assembler written by Tim Hart and Mike Levin.

Early operating systems and software were written in assembly language. In the 1960s and early 1970s, the use of high-level languages for system programming was still controversial due to resource limitations. However, several research and industry efforts began the shift toward high-level systems programming languages, for example, BCPL, BLISS, B, and C.

BCPL (Basic Combined Programming Language) designed in 1966 by Martin Richards at the University of Cambridge was originally developed as a compiler writing tool. Several compilers have been implemented, Richards' book provides insights to the language and its compiler. BCPL was not only an influential systems programming language that is still used in research but also provided a basis for the design of B and C languages.

BLISS (Basic Language for Implementation of System Software) was developed for a Digital Equipment Corporation (DEC) PDP-10 computer by W. A. Wulf's Carnegie Mellon University (CMU) research team. The CMU team went on to develop BLISS-11 compiler one year later in 1970.

Multics (Multiplexed Information and Computing Service), a time-sharing operating system project, involved MIT, Bell Labs, General Electric (later Honeywell) and was led by Fernando Corbató from MIT. Multics was written in the PL/I language developed by IBM and IBM User Group. IBM's goal was to satisfy business, scientific, and systems programming requirements. There were other languages that could have been considered but PL/I offered the most complete solution even though it had not been implemented. For the first few years of the Multics project, a subset of the language could be compiled to assembly language with the Early PL/I (EPL) compiler by Doug McIlory and Bob Morris from Bell Labs. EPL supported the project until a boot-strapping compiler for the full PL/I could be developed.

Bell Labs left the Multics project in 1969, and developed a system programming language B based on BCPL concepts, written by Dennis Ritchie and Ken Thompson. Ritchie created a boot-strapping compiler for B and wrote Unics (Uniplexed Information and Computing Service) operating system for a PDP-7 in B. Unics eventually became spelled Unix.

Bell Labs started the development and expansion of C based on B and BCPL. The BCPL compiler had been transported to Multics by Bell Labs and BCPL was a preferred language at Bell Labs. Initially, a front-end program to Bell Labs' B compiler was used while a C compiler was developed. In 1971, a new PDP-11 provided the resource to define extensions to B and rewrite the compiler. By 1973 the design of C language was essentially complete and the Unix kernel for a PDP-11 was rewritten in C. Steve Johnson started development of Portable C Compiler (PCC) to support retargeting of C compilers to new machines.

Object-oriented programming (OOP) offered some interesting possibilities for application development and maintenance. OOP concepts go further back but were part of LISP and Simula language science. Bell Labs became interested in OOP with the development of C++. C++ was first used in 1980 for systems programming. The initial design leveraged C language systems programming capabilities with Simula concepts. Object-oriented facilities were added in 1983. The Cfront program implemented a C++ front-end for C84 language compiler. In subsequent years several C++ compilers were developed as C++ popularity grew.

In many application domains, the idea of using a higher-level language quickly caught on. Because of the expanding functionality supported by newer programming languages and the increasing complexity of computer architectures, compilers became more complex.

DARPA (Defense Advanced Research Projects Agency) sponsored a compiler project with Wulf's CMU research team in 1970. The Production Quality Compiler-Compiler PQCC design would produce a Production Quality Compiler (PQC) from formal definitions of source language and the target. PQCC tried to extend the term compiler-compiler beyond the traditional meaning as a parser generator (e.g., Yacc) without much success. PQCC might more properly be referred to as a compiler generator.

PQCC research into code generation process sought to build a truly automatic compiler-writing system. The effort discovered and designed the phase structure of the PQC. The BLISS-11 compiler provided the initial structure. The phases included analyses (front end), intermediate translation to virtual machine (middle end), and translation to the target (back end). TCOL was developed for the PQCC research to handle language specific constructs in the intermediate representation. Variations of TCOL supported various languages. The PQCC project investigated techniques of automated compiler construction. The design concepts proved useful in optimizing compilers and compilers for the (since 1995, object-oriented) programming language Ada.

The Ada STONEMAN document formalized the program support environment (APSE) along with the kernel (KAPSE) and minimal (MAPSE). An Ada interpreter NYU/ED supported development and standardization efforts with the American National Standards Institute (ANSI) and the International Standards Organization (ISO). Initial Ada compiler development by the U.S. Military Services included the compilers in a complete integrated design environment along the lines of the STONEMAN document. Army and Navy worked on the Ada Language System (ALS) project targeted to DEC/VAX architecture while the Air Force started on the Ada Integrated Environment (AIE) targeted to IBM 370 series. While the projects did not provide the desired results, they did contribute to the overall effort on Ada development.

Other Ada compiler efforts got underway in Britain at the University of York and in Germany at the University of Karlsruhe. In the U. S., Verdix (later acquired by Rational) delivered the Verdix Ada Development System (VADS) to the Army. VADS provided a set of development tools including a compiler. Unix/VADS could be hosted on a variety of Unix platforms such as DEC Ultrix and the Sun 3/60 Solaris targeted to Motorola 68020 in an Army CECOM evaluation. There were soon many Ada compilers available that passed the Ada Validation tests. The Free Software Foundation GNU project developed the GNU Compiler Collection (GCC) which provides a core capability to support multiple languages and targets. The Ada version GNAT is one of the most widely used Ada compilers. GNAT is free but there is also commercial support, for example, AdaCore, was founded in 1994 to provide commercial software solutions for Ada. GNAT Pro includes the GNU GCC based GNAT with a tool suite to provide an integrated development environment.

High-level languages continued to drive compiler research and development. Focus areas included optimization and automatic code generation. Trends in programming languages and development environments influenced compiler technology. More compilers became included in language distributions (PERL, Java Development Kit) and as a component of an IDE (VADS, Eclipse, Ada Pro). The interrelationship and interdependence of technologies grew. The advent of web services promoted growth of web languages and scripting languages. Scripts trace back to the early days of Command Line Interfaces (CLI) where the user could enter commands to be executed by the system. User Shell concepts developed with languages to write shell programs. Early Windows designs offered a simple batch programming capability. The conventional transformation of these language used an interpreter. While not widely used, Bash and Batch compilers have been written. More recently sophisticated interpreted languages became part of the developers tool kit. Modern scripting languages include PHP, Python, Ruby and Lua. (Lua is widely used in game development.) All of these have interpreter and compiler support.

"When the field of compiling began in the late 50s, its focus was limited to the translation of high-level language programs into machine code ... The compiler field is increasingly intertwined with other disciplines including computer architecture, programming languages, formal methods, software engineering, and computer security." The "Compiler Research: The Next 50 Years" article noted the importance of object-oriented languages and Java. Security and parallel computing were cited among the future research targets.

Compiler construction
A compiler implements a formal transformation from a high-level source program to a low-level target program. Compiler design can define an end-to-end solution or tackle a defined subset that interfaces with other compilation tools e.g. preprocessors, assemblers, linkers. Design requirements include rigorously defined interfaces both internally between compiler components and externally between supporting toolsets.

In the early days, the approach taken to compiler design was directly affected by the complexity of the computer language to be processed, the experience of the person(s) designing it, and the resources available. Resource limitations led to the need to pass through the source code more than once.

A compiler for a relatively simple language written by one person might be a single, monolithic piece of software. However, as the source language grows in complexity the design may be split into a number of interdependent phases. Separate phases provide design improvements that focus development on the functions in the compilation process.

One-pass versus multi-pass compilers
Classifying compilers by number of passes has its background in the hardware resource limitations of computers. Compiling involves performing much work and early computers did not have enough memory to contain one program that did all of this work. As a result, compilers were split up into smaller programs which each made a pass over the source (or some representation of it) performing some of the required analysis and translations.

The ability to compile in a single pass has classically been seen as a benefit because it simplifies the job of writing a compiler and one-pass compilers generally perform compilations faster than multi-pass compilers. Thus, partly driven by the resource limitations of early systems, many early languages were specifically designed so that they could be compiled in a single pass (e.g., Pascal).

In some cases, the design of a language feature may require a compiler to perform more than one pass over the source. For instance, consider a declaration appearing on line 20 of the source which affects the translation of a statement appearing on line 10. In this case, the first pass needs to gather information about declarations appearing after statements that they affect, with the actual translation happening during a subsequent pass.

The disadvantage of compiling in a single pass is that it is not possible to perform many of the sophisticated optimizations needed to generate high quality code. It can be difficult to count exactly how many passes an optimizing compiler makes. For instance, different phases of optimization may analyse one expression many times but only analyse another expression once.

Splitting a compiler up into small programs is a technique used by researchers interested in producing provably correct compilers. Proving the correctness of a set of small programs often requires less effort than proving the correctness of a larger, single, equivalent program.

Three-stage compiler structure
Regardless of the exact number of phases in the compiler design, the phases can be assigned to one of three stages. The stages include a front end, a middle end, and a back end.
 * The front end scans the input and verifies syntax and semantics according to a specific source language. For statically typed languages it performs type checking by collecting type information. If the input program is syntactically incorrect or has a type error, it generates error and/or warning messages, usually identifying the location in the source code where the problem was detected; in some cases the actual error may be (much) earlier in the program. Aspects of the front end include lexical analysis, syntax analysis, and semantic analysis. The front end transforms the input program into an intermediate representation (IR) for further processing by the middle end. This IR is usually a lower-level representation of the program with respect to the source code.
 * The middle end performs optimizations on the IR that are independent of the CPU architecture being targeted. This source code/machine code independence is intended to enable generic optimizations to be shared between versions of the compiler supporting different languages and target processors. Examples of middle end optimizations are removal of useless (dead-code elimination) or unreachable code (reachability analysis), discovery and propagation of constant values (constant propagation), relocation of computation to a less frequently executed place (e.g., out of a loop), or specialization of computation based on the context, eventually producing the "optimized" IR that is used by the back end.
 * The back end takes the optimized IR from the middle end. It may perform more analysis, transformations and optimizations that are specific for the target CPU architecture. The back end generates the target-dependent assembly code, performing register allocation in the process. The back end performs instruction scheduling, which re-orders instructions to keep parallel execution units busy by filling delay slots. Although most optimization problems are NP-hard, heuristic techniques for solving them are well-developed and implemented in production-quality compilers. Typically the output of a back end is machine code specialized for a particular processor and operating system.

This front/middle/back-end approach makes it possible to combine front ends for different languages with back ends for different CPUs while sharing the optimizations of the middle end. Practical examples of this approach are the GNU Compiler Collection, Clang (LLVM-based C/C++ compiler), and the Amsterdam Compiler Kit, which have multiple front-ends, shared optimizations and multiple back-ends.

Front end

The front end analyzes the source code to build an internal representation of the program, called the intermediate representation (IR). It also manages the symbol table, a data structure mapping each symbol in the source code to associated information such as location, type and scope.

While the frontend can be a single monolithic function or program, as in a scannerless parser, it was traditionally implemented and analyzed as several phases, which may execute sequentially or concurrently. This method is favored due to its modularity and separation of concerns. Most commonly, the frontend is broken into three phases: lexical analysis (also known as lexing or scanning), syntax analysis (also known as scanning or parsing), and semantic analysis. Lexing and parsing comprise the syntactic analysis (word syntax and phrase syntax, respectively), and in simple cases, these modules (the lexer and parser) can be automatically generated from a grammar for the language, though in more complex cases these require manual modification. The lexical grammar and phrase grammar are usually context-free grammars, which simplifies analysis significantly, with context-sensitivity handled at the semantic analysis phase. The semantic analysis phase is generally more complex and written by hand, but can be partially or fully automated using attribute grammars. These phases themselves can be further broken down: lexing as scanning and evaluating, and parsing as building a concrete syntax tree (CST, parse tree) and then transforming it into an abstract syntax tree (AST, syntax tree). In some cases additional phases are used, notably line reconstruction and preprocessing, but these are rare.

The main phases of the front end include the following:
 *  converts the input character sequence to a canonical form ready for the parser. Languages which strop their keywords or allow arbitrary spaces within identifiers require this phase. The top-down, recursive-descent, table-driven parsers used in the 1960s typically read the source one character at a time and did not require a separate tokenizing phase. Atlas Autocode and Imp (and some implementations of ALGOL and Coral 66) are examples of stropped languages whose compilers would have a Line Reconstruction phase.
 * Preprocessing supports macro substitution and conditional compilation. Typically the preprocessing phase occurs before syntactic or semantic analysis; e.g. in the case of C, the preprocessor manipulates lexical tokens rather than syntactic forms. However, some languages such as Scheme support macro substitutions based on syntactic forms.
 * Lexical analysis (also known as lexing or tokenization) breaks the source code text into a sequence of small pieces called lexical tokens. This phase can be divided into two stages: the scanning, which segments the input text into syntactic units called lexemes and assigns them a category; and the evaluating, which converts lexemes into a processed value. A token is a pair consisting of a token name and an optional token value. Common token categories may include identifiers, keywords, separators, operators, literals and comments, although the set of token categories varies in different programming languages. The lexeme syntax is typically a regular language, so a finite state automaton constructed from a regular expression can be used to recognize it. The software doing lexical analysis is called a lexical analyzer. This may not be a separate step—it can be combined with the parsing step in scannerless parsing, in which case parsing is done at the character level, not the token level.
 * Syntax analysis (also known as parsing) involves parsing the token sequence to identify the syntactic structure of the program. This phase typically builds a parse tree, which replaces the linear sequence of tokens with a tree structure built according to the rules of a formal grammar which define the language's syntax. The parse tree is often analyzed, augmented, and transformed by later phases in the compiler.
 * Semantic analysis adds semantic information to the parse tree and builds the symbol table. This phase performs semantic checks such as type checking (checking for type errors), or object binding (associating variable and function references with their definitions), or definite assignment (requiring all local variables to be initialized before use), rejecting incorrect programs or issuing warnings. Semantic analysis usually requires a complete parse tree, meaning that this phase logically follows the parsing phase, and logically precedes the code generation phase, though it is often possible to fold multiple phases into one pass over the code in a compiler implementation.

Middle end
The middle end, also known as optimizer, performs optimizations on the intermediate representation in order to improve the performance and the quality of the produced machine code. The middle end contains those optimizations that are independent of the CPU architecture being targeted.

The main phases of the middle end include the following: Compiler analysis is the prerequisite for any compiler optimization, and they tightly work together. For example, dependence analysis is crucial for loop transformation.
 * Analysis: This is the gathering of program information from the intermediate representation derived from the input; data-flow analysis is used to build use-define chains, together with dependence analysis, alias analysis, pointer analysis, escape analysis, etc. Accurate analysis is the basis for any compiler optimization. The control-flow graph of every compiled function and the call graph of the program are usually also built during the analysis phase.
 * Optimization: the intermediate language representation is transformed into functionally equivalent but faster (or smaller) forms. Popular optimizations are inline expansion, dead-code elimination, constant propagation, loop transformation and even automatic parallelization.

The scope of compiler analysis and optimizations vary greatly; their scope may range from operating within a basic block, to whole procedures, or even the whole program. There is a trade-off between the granularity of the optimizations and the cost of compilation. For example, peephole optimizations are fast to perform during compilation but only affect a small local fragment of the code, and can be performed independently of the context in which the code fragment appears. In contrast, interprocedural optimization requires more compilation time and memory space, but enable optimizations that are only possible by considering the behavior of multiple functions simultaneously.

Interprocedural analysis and optimizations are common in modern commercial compilers from HP, IBM, SGI, Intel, Microsoft, and Sun Microsystems. The free software GCC was criticized for a long time for lacking powerful interprocedural optimizations, but it is changing in this respect. Another open source compiler with full analysis and optimization infrastructure is Open64, which is used by many organizations for research and commercial purposes.

Due to the extra time and space needed for compiler analysis and optimizations, some compilers skip them by default. Users have to use compilation options to explicitly tell the compiler which optimizations should be enabled.

Back end
The back end is responsible for the CPU architecture specific optimizations and for code generation .

The main phases of the back end include the following:
 * Machine dependent optimizations: optimizations that depend on the details of the CPU architecture that the compiler targets. A prominent example is peephole optimizations, which rewrites short sequences of assembler instructions into more efficient instructions.
 * Code generation: the transformed intermediate language is translated into the output language, usually the native machine language of the system. This involves resource and storage decisions, such as deciding which variables to fit into registers and memory and the selection and scheduling of appropriate machine instructions along with their associated addressing modes (see also Sethi–Ullman algorithm). Debug data may also need to be generated to facilitate debugging.

Compiler correctness
Compiler correctness is the branch of software engineering that deals with trying to show that a compiler behaves according to its language specification. Techniques include developing the compiler using formal methods and using rigorous testing (often called compiler validation) on an existing compiler.

Compiled versus interpreted languages
Higher-level programming languages usually appear with a type of translation in mind: either designed as compiled language or interpreted language. However, in practice there is rarely anything about a language that requires it to be exclusively compiled or exclusively interpreted, although it is possible to design languages that rely on re-interpretation at run time. The categorization usually reflects the most popular or widespread implementations of a language – for instance, BASIC is sometimes called an interpreted language, and C a compiled one, despite the existence of BASIC compilers and C interpreters.

Interpretation does not replace compilation completely. It only hides it from the user and makes it gradual. Even though an interpreter can itself be interpreted, a set of directly executed machine instructions is needed somewhere at the bottom of the execution stack (see machine language).

Furthermore, for optimization compilers can contain interpreter functionality, and interpreters may include ahead of time compilation techniques. For example, where an expression can be executed during compilation and the results inserted into the output program, then it prevents it having to be recalculated each time the program runs, which can greatly speed up the final program. Modern trends toward just-in-time compilation and bytecode interpretation at times blur the traditional categorizations of compilers and interpreters even further.

Some language specifications spell out that implementations must include a compilation facility; for example, Common Lisp. However, there is nothing inherent in the definition of Common Lisp that stops it from being interpreted. Other languages have features that are very easy to implement in an interpreter, but make writing a compiler much harder; for example, APL, SNOBOL4, and many scripting languages allow programs to construct arbitrary source code at runtime with regular string operations, and then execute that code by passing it to a special evaluation function. To implement these features in a compiled language, programs must usually be shipped with a runtime library that includes a version of the compiler itself.

Types
One classification of compilers is by the platform on which their generated code executes. This is known as the target platform.

A native or hosted compiler is one whose output is intended to directly run on the same type of computer and operating system that the compiler itself runs on. The output of a cross compiler is designed to run on a different platform. Cross compilers are often used when developing software for embedded systems that are not intended to support a software development environment.

The output of a compiler that produces code for a virtual machine (VM) may or may not be executed on the same platform as the compiler that produced it. For this reason, such compilers are not usually classified as native or cross compilers.

The lower level language that is the target of a compiler may itself be a high-level programming language. C, viewed by some as a sort of portable assembly language, is frequently the target language of such compilers. For example, Cfront, the original compiler for C++, used C as its target language. The C code generated by such a compiler is usually not intended to be readable and maintained by humans, so indent style and creating pretty C intermediate code are ignored. Some of the features of C that make it a good target language include the  directive, which can be generated by the compiler to support debugging of the original source, and the wide platform support available with C compilers.

While a common compiler type outputs machine code, there are many other types:
 * Source-to-source compilers are a type of compiler that takes a high-level language as its input and outputs a high-level language. For example, an automatic parallelizing compiler will frequently take in a high-level language program as an input and then transform the code and annotate it with parallel code annotations (e.g. OpenMP) or language constructs (e.g. Fortran's  statements). Other terms for a source-to-source compiler are transcompiler or transpiler.
 * Bytecode compilers compile to assembly language of a theoretical machine, like some Prolog implementations
 * This Prolog machine is also known as the Warren Abstract Machine (or WAM).
 * Bytecode compilers for Java, Python are also examples of this category.
 * Just-in-time compilers (JIT compiler) defer compilation until runtime. JIT compilers exist for many modern languages including Python, JavaScript, Smalltalk, Java, Microsoft .NET's Common Intermediate Language (CIL) and others. A JIT compiler generally runs inside an interpreter.  When the interpreter detects that a code path is "hot", meaning it is executed frequently, the JIT compiler will be invoked and compile the "hot" code for increased performance.
 * For some languages, such as Java, applications are first compiled using a bytecode compiler and delivered in a machine-independent intermediate representation. A bytecode interpreter executes the bytecode, but the JIT compiler will translate the bytecode to machine code when increased performance is necessary.
 * Hardware compilers (also known as synthesis tools) are compilers whose input is a hardware description language and whose output is a description, in the form of a netlist or otherwise, of a hardware configuration.
 * The output of these compilers target computer hardware at a very low level, for example a field-programmable gate array (FPGA) or structured application-specific integrated circuit (ASIC). Such compilers are said to be hardware compilers, because the source code they compile effectively controls the final configuration of the hardware and how it operates. The output of the compilation is only an interconnection of transistors or lookup tables.
 * An example of hardware compiler is XST, the Xilinx Synthesis Tool used for configuring FPGAs. Similar tools are available from Altera,  Synplicity, Synopsys and other hardware vendors.
 * A program that translates from a low-level language to a higher level one is a decompiler.
 * A program that translates into an object code format that is not supported on the compilation machine is called a cross compiler and is commonly used to prepare code for execution on embedded software applications.
 * A program that rewrites object code back into the same type of object code while applying optimisations and transformations is a binary recompiler.

Assemblers, which translate human readable assembly language to the machine code instructions executed by hardware, are not considered compilers. (The inverse program that translates machine code to assembly language is called a disassembler.)

title: Compiler


text:
Talk:Compiler

duplication
the "types of compilers" section is a duplication of text at the very top of the page.

Compiler Execution process section
Hello, , , let us discuss about Compiler Execution process section that kept being reverted over and over again. Please remember not to engage in edit war, but seek consensus. Let us discuss! SunDawn (talk) 16:56, 15 May 2021 (UTC)
 * Well, 94seulgi started this edit war by adding info that was already in the article.--2603:6080:6C04:C700:900F:572:7EFF:875F (talk) 17:04, 15 May 2021 (UTC)

 * I understand, but you should not violate WP:3RR no matter the case. I have reverted to the latest stable version, I have also placed warnings on hoping that he/she will come to discuss. SunDawn (talk) 17:09, 15 May 2021 (UTC)
 * Ok, and 83.26.157.157 is locked for sock puppetry.--2603:6080:6C04:C700:900F:572:7EFF:875F (talk) 17:09, 15 May 2021 (UTC)
 * Hi folks, I'm the first person who reverted 's edits to Compiler, and I did leave a note on their talk page explaining that the material which they added was already in the article. It looks to me as if they are repeatedly adding more or less the same thing without noticing the messages (admittedly when I was a new editor it took me a while to figure out how talk pages worked). I just hope that  joins the discussion here and explains why they feel the need to put duplicate stuff in the article. Murray Langton (talk) 19:03, 15 May 2021 (UTC)

 * I have left a similar message on User talk:Dbtjdgns132. From their editing pattern (small sample) it looks as if this may a sock-puppet. Murray Langton (talk) 13:34, 16 May 2021 (UTC)

Middle "END"?
Trivial observation by a person who made extensive use of FORTRAN some 50 years ago but not since (nor any other compiler or such tool): Under "Compiler Design" one diagram and associated text talks about "Front End, Middle End and Back End". I don't know the terminology of the field, but "Middle End" seems contradictory. Casey (talk) 15:17, 1 January 2022 (UTC)
 * It does, but that is the terminology. Users of compilers likely don't even need to know that, but people who work on them do. There are two parts of compilers that can, mostly, be done without connection to the rest. Those got named front end (the part that first processes input characters) and back end (that generates instructions in the target langauage). The rest then gets named middle end. Gah4 (talk) 17:36, 1 January 2022 (UTC)
 * Discussion on the comp.compilers newsgroup finds this one as an early reference. It is normally the place where optimization is done, so more important as optimization has increased in importance. Gah4 (talk) 22:12, 1 January 2022 (UTC)
 * Discussion on the comp.compilers newsgroup finds this one as an early reference. It is normally the place where optimization is done, so more important as optimization has increased in importance. Gah4 (talk) 22:12, 1 January 2022 (UTC)
 * Discussion on the comp.compilers newsgroup finds this one as an early reference. It is normally the place where optimization is done, so more important as optimization has increased in importance. Gah4 (talk) 22:12, 1 January 2022 (UTC)

History section need the motivation for using a compiler versus machine/assembly language
One of the major reasons driving for compilers in the 1950s versus assembly languages was that the IBM 704 implemented floating point operations in hardware instead of software routines. It sped up floating point calculations by a factor of 10 and switched the execution time of a program from nearly all being floating point computation routines to the rest of the program. And by extension, programmer productivity became a blocking factor.

From: Book: A HISTORY OF COMPUTING IN THE TWENTIETH CENTURY -JOHN BACKUS Chapter: Programming in America in the 1950s-Some Personal Impressions Section 7. The Origins of FORTRAN Page 130-131

"FORTRAN did not really grow out of some brainstorm about the beauty of programming in mathematical notation; instead it began with the recognition of a basic problem of economics: programming and debugging costs already exceeded the cost of running a program, and as computers became faster and cheaper this imbalance would become more and more intolerable.

This prosaic economic insight, plus experience with the drudgery of coding, plus an unusually lazy nature led to my continuing interest in making programming easier. This interest led directly to work on Speedcoding for the 701 and to efforts to have floating point as well as indexing built into the 704.

The viability of most compilers and interpreters prior to FORTRAN had rested on the fact that most source operations were not machine operations. Thus even large inefficiencies in compiling or interpreting looping and testing operations and in computing addresses were masked by the fact that '''most operating time was spent in floating-point subroutines. '''

But the advent of the 704 with built-in floating-point and indexing radically altered the situation.

The 704 presented a double challenge to those who wanted to simplify programming; first it removed the raison d'etre of earlier systems by providing in hardware the operations they existed to provide, and second, it increased the problem of generating efficient programs by an order of magnitude by speeding up floating-point operations by a factor of ten and thereby leaving inefficiencies nowhere to hide.

So what could be done now to ease the programmer's job? Once asked, the answer to this question had to be: Let him use mathematical notation. But behind that answer (in the new 704 environment) there was the really new and hard question: '''Can a machine translate a sufficiently rich mathematical language into a sufficiently economical machine program to make the whole affair feasible? "''' 107.197.56.204 (talk) 16:44, 9 November 2022 (UTC)

 * Another major (or the main) reason - less time needed for creating a working program and obtaining the desired results from running the program: Manual vs compiler A-0, Univac: Hopper. G. M. "Compiling routines". Computers and Automation 2, No. 4, 1953 May. 1-5 MarMi wiki (talk) 13:56, 28 June 2023 (UTC)

Early compilers (1954)
BIOR, NYU Compiler System

AUTOMATIC CODING FOR DIGITAL COMPUTERS, p. 22

Business Input-Output Rerun (BIOR), , (03). MarMi wiki (talk) 11:07, 12 July 2023 (UTC)

Wiki Education assignment: Linguistics in the Digital Age
— Assignment last updated by Cakelover44 (talk) 03:36, 19 February 2024 (UTC)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Talk:Compiler


text:
Castrato

A castrato (Italian; : castrati) is a male singer who underwent castration before puberty in order to retain singing voice equivalent to that of a soprano, mezzo-soprano, or contralto. The voice can also occur in one who, due to an endocrinological condition, never reaches sexual maturity.

Castration before puberty (or in its early stages) prevents the larynx from being transformed by the normal physiological events of puberty. As a result, the vocal range of prepubescence (shared by both sexes) is largely retained, and the voice develops into adulthood in a unique way. Prepubescent castration for this purpose diminished greatly in the late 18th century.

Methods of castration used to terminate the onset of puberty varied. Methods involved using opium to medically induce a coma, then submerging the boy into an ice or milk bath where the procedure of either twisting the testicles until they atrophied, or complete removal via surgical cutting was performed (however the complete removal of the testicles was not a popularly used technique). The procedure was usually done to boys around the age of 8–10; recovery time from the procedure took around two weeks. The means by which future singers were prepared could lead to premature death. To prevent the child from experiencing the intense pain of castration, many were inadvertently administered lethal doses of opium or some other narcotic, or were killed by overlong compression of the carotid artery in the neck (intended to render them unconscious during the castration procedure). The geographical locations of where these procedures took place is not known specifically. During the 18th century, the music historian Charles Burney was sent from pillar to post in search of places where the operation was carried out: "I enquired throughout Italy at what place boys were chiefly qualified for singing by castration, but could get no certain intelligence. I was told at Milan that it was at Venice; at Venice that it was at Bologna; but at Bologna the fact was denied, and I was referred to Florence; from Florence to Rome, and from Rome I was sent to Naples ... it is said that there are shops in Naples with this inscription: 'QUI SI CASTRANO RAGAZZI' ('Here boys are castrated'); but I was utterly unable to see or hear of any such shops during my residence in that city."

As a castrato's body grew, his lack of testosterone meant that his epiphyses (bone-joints) did not harden in the normal manner. Thus, the limbs of the castrati often grew unusually long, as did their ribs. This, combined with intensive training, gave them unrivaled lung power and breath capacity. Operating through small, child-sized vocal cords, their voices were also extraordinarily flexible, and quite different from the equivalent adult female voice. Their vocal range was higher than that of the uncastrated adult male. Listening to the only surviving recordings of a castrato (see below), one can hear that the lower part of the voice sounds like a "super-high" tenor, with a more falsetto-like upper register above that.

Castrati were rarely referred to as such: in the 18th century, the euphemism musico (: musici) was much more generally used, although it usually carried derogatory implications; another synonym was evirato, literally meaning "emasculated". Eunuch is a more general term since, historically, many eunuchs were castrated after puberty and thus the castration had no effect on their voices.

History

Castration as a means of subjugation, enslavement or other punishment has a very long history, dating back to ancient Sumer. In a Western context, eunuch singers are known to have existed from the early Byzantine Empire. In Constantinople around 400 AD, the empress Aelia Eudoxia had a eunuch choir-master, Brison, who may have established the use of castrati in Byzantine choirs, though whether Brison himself was a singer and whether he had colleagues who were eunuch singers is not certain. By the 9th century, eunuch singers were well-known (most in the choir of Hagia Sophia) and remained so until the sack of Constantinople by the Western forces of the Fourth Crusade in 1204. Their fate from then until their reappearance in Italy more than three hundred years later is not clear. It seems likely that the Spanish tradition of soprano falsettists may have hidden castrati. Much of Spain was under Muslim rulers during the Middle Ages, and castration had a history going back to the ancient Near East. Stereotypically, eunuchs served as harem guards, but they were also valued as high-level political appointees since they could not start a dynasty which would threaten the ruler.

European classical tradition
Castrati first appeared in Italy in the mid-16th century, though at first the terms describing them were not always clear. The phrase soprano maschio (male soprano), which could also mean falsettist, occurs in the Due Dialoghi della Musica (Two dialogues upon music) of Luigi Dentice, an Oratorian priest, published in Rome in 1553. On 9 November 1555 Cardinal Ippolito II d'Este (famed as the builder of the Villa d'Este at Tivoli), wrote to Guglielmo Gonzaga, Duke of Mantua (1538–1587), that he has heard that the Duke was interested in his cantoretti (little singers) and offered to send him two, so that he could choose one for his own service. This is a rare term but probably does equate to castrato. The Cardinal's nephew, Alfonso II d'Este, Duke of Ferrara, was another early enthusiast, inquiring about castrati in 1556. There were certainly castrati in the Sistine Chapel choir in 1558, although not described as such: on 27 April of that year, Hernando Bustamante, a Spaniard from Palencia, was admitted (the first castrati so termed who joined the Sistine choir were Pietro Paolo Folignato and Girolamo Rossini, admitted in 1599). Surprisingly, considering the later French distaste for castrati, they certainly existed in France at this time also, being known of in Paris, Orléans, Picardy and Normandy, though they were not abundant: the King of France himself had difficulty in obtaining them. By 1574, there were castrati in the Ducal court chapel at Munich, where the Kapellmeister (music director) was the famous Orlando di Lasso. In 1589, by the bull Cum pro nostro pastorali munere, Pope Sixtus V re-organised the choir of St Peter's, Rome specifically to include castrati.

Thus the castrati came to supplant both boys (whose voices broke after only a few years) and falsettists (whose voices were weaker and less reliable) from the top line in such choirs. Women were banned by the Pauline dictum mulieres in ecclesiis taceant ("let women keep silent in the churches"; see I Corinthians, ch. 14, v. 34).

The Italian castrati were often rumored to have unusually long lives, but a 1993 study found that their lifespans were average.

Opera
Although the castrato (or musico) predates opera, there is some evidence that castrati had parts in the earliest operas. In the first performance of Monteverdi's Orfeo (1607), for example, they played subsidiary roles, including Speranza and (possibly) that of Euridice. Although female roles were performed by castrati in some of the papal states, this was increasingly rare; by 1680, they had supplanted normal male voices in lead roles, and retained their position as primo uomo for about a hundred years; an Italian opera not featuring at least one renowned castrato in a lead part would be doomed to fail. Because of the popularity of Italian opera throughout 18th-century Europe (except France), singers such as Ferri, Farinelli, Senesino and Pacchierotti became the first operatic superstars, earning enormous fees and hysterical public adulation. The strictly hierarchical organisation of opera seria favoured their high voices as symbols of heroic virtue, though they were frequently mocked for their strange appearance and bad acting. In his 1755 Reflections upon theatrical expression in tragedy, Roger Pickering wrote: "Farinelli drew every Body to the Haymarket. What a Pipe! What Modulation! What Extasy to the Ear! But, Heavens! What Clumsiness! What Stupidity! What Offence to the Eye! Reader, if of the City, thou mayest probably have seen in the Fields of Islington or Mile-End or, If thou art in the environs of St James', thou must have observed in the Park with what Ease and Agility a cow, heavy with calf, has rose up at the command of the Milk-woman's foot: thus from the mossy bank sprang the DIVINE FARINELLI."The training of the boys was rigorous. The regimen of one singing school in Rome (c. 1700) consisted of one hour of singing difficult and awkward pieces, one hour practising trills, one hour practising ornamented passaggi, one hour of singing exercises in their teacher's presence and in front of a mirror so as to avoid unnecessary movement of the body or facial grimaces, and one hour of literary study; all this, moreover, before lunch. After, half an hour would be devoted to musical theory, another to writing counterpoint, an hour copying down the same from dictation, and another hour of literary study. During the remainder of the day, the young castrati had to find time to practice their harpsichord playing, and to compose vocal music, either sacred or secular depending on their inclination. This demanding schedule meant that, if sufficiently talented, they were able to make a debut in their mid-teens with a perfect technique and a voice of a flexibility and power no woman or ordinary male singer could match.

In the 1720s and 1730s, at the height of the craze for these voices, it has been estimated that upwards of 4,000 boys were castrated annually in the service of art. Many came from poor homes and were castrated by their parents in the hope that their child might be successful and lift them from poverty (this was the case with Senesino). There are, though, records of some young boys asking to be operated on to preserve their voices (e.g. Caffarelli, who was from a wealthy family: his grandmother gave him the income from two vineyards to pay for his studies ). Caffarelli was also typical of many castrati in being famous for tantrums on and off-stage, and for amorous adventures with noble ladies. Some, as described by Casanova, preferred gentlemen (noble or otherwise). Only a small percentage of boys castrated to preserve their voices had successful careers on the operatic stage; the better "also-rans" sang in cathedral or church choirs, but because of their marked appearance and the ban on their marrying, there was little room for them in society outside a musical context.

The castrati came in for a great amount of scurrilous and unkind abuse, and as their fame increased, so did the hatred of them. They were often castigated as malign creatures who lured men into homosexuality. There were homosexual castrati, as Casanova's accounts of 18th-century Italy bear witness. He mentions meeting an abbé whom he took for a girl in disguise, only later discovering that "she" was a famous castrato. In Rome in 1762 he attended a performance at which the prima donna was a castrato, "the favourite pathic" of Cardinal Borghese, who dined every evening with his protector. From his behaviour on stage "it was obvious that he hoped to inspire the love of those who liked him as a man, and probably would not have done so as a woman".

Decline
By the late 18th century, changes in operatic taste and social attitudes spelled the end for castrati. They lingered on past the end of the ancien régime, which their style of opera parallels, and two of their number, Pacchierotti and Crescentini, performed before Napoleon. The last great operatic castrato was Giovanni Battista Velluti (1781–1861), who performed the last operatic castrato role ever written: Armando in Il crociato in Egitto by Meyerbeer (Venice, 1824). Soon after this they were replaced definitively as the first men of the operatic stage by a new breed of heroic tenor, as first incarnated by the Frenchman Gilbert-Louis Duprez, the earliest so-called "king of the high Cs". His successors have included such singers as Enrico Tamberlik, Jean de Reszke, Francesco Tamagno, Enrico Caruso, Giovanni Martinelli, Beniamino Gigli, Jussi Björling, Franco Corelli and Luciano Pavarotti, among others.

After the unification of Italy in 1861, "eviration" was officially made illegal, as the new Italian state had adopted the previous penal code of the Kingdom of Sardinia, which expressly forbade the practice. In 1878, Pope Leo XIII prohibited the hiring of new castrati by the church: only in the Sistine Chapel and in other papal basilicas in Rome did a few castrati linger. A group photo of the Sistine Choir taken in 1898 shows that by then only six remained, plus the Direttore Perpetuo, the fine soprano castrato Domenico Mustafà. In 1902 a ruling was extracted from Pope Leo that no further castrati should be admitted. The official end to the castrati came on St. Cecilia's Day, 22 November 1903, when the new pope, Pius X, issued his motu proprio, Tra le Sollecitudini ("Amongst the Cares"), which contained this instruction: "Whenever ... it is desirable to employ the high voices of sopranos and contraltos, these parts must be taken by boys, according to the most ancient usage of the Church."

The last Sistine castrato to survive was Alessandro Moreschi, the only castrato to have made solo recordings. While an interesting historical record, these discs of his give us only a glimpse of the castrato voice, although he had been renowned as "The Angel of Rome" at the beginning of his career, some would say he was past his prime when the recordings were made in 1902 and 1904 and he never attempted to sing opera. Domenico Salvatori, a castrato who was contemporary with Moreschi, made some ensemble recordings with him but has no surviving solo recordings. The recording technology of the day was not of modern high quality. Salvatori died in 1909; Moreschi retired officially in March 1913, and died in 1922.

The Catholic Church's involvement in the castrato phenomenon has long been controversial, and there have recently been calls for it to issue an official apology for its role. As early as 1748, Pope Benedict XIV tried to ban castrati from churches, but such was their popularity at the time that he realised that doing so might result in a drastic decline in church attendance.

The rumours of another castrato sequestered in the Vatican for the personal delectation of the Pontiff until as recently as 1959 have been proven false. The singer in question was a pupil of Moreschi's, Domenico Mancini, such a successful imitator of his teacher's voice that even Lorenzo Perosi, Direttore Perpetuo of the Sistine Choir from 1898 to 1956 and a strenuous opponent of the practice of castrato singers, thought he was a castrato. Mancini was in fact a moderately skillful falsettist and professional double bass player.

Modern castrati and similar voices
A male can retain his child voice if it never changes during puberty. The retained voice can be the treble voice shared by both sexes in childhood and is the same as a boy soprano voice. But as evidence shows, many castratos, such as Senesino and Caffarelli, were actually altos (mezzo-soprano) – not sopranos. So-called "natural" or "endocrinological castrati" are born with hormonal anomalies, such as Klinefelter's syndrome and Kallmann's syndrome, or have undergone unusual physical or medical events during their early lives that reproduce the vocal effects of castration without being castrated.

Jimmy Scott, Radu Marian and Javier Medina are examples of this type of high male voice via endocrinological diseases. Michael Maniaci is somewhat different, in that he has no hormonal or other anomalies, but claims that his voice did not "break" in the usual manner, leaving him still able to sing in the soprano register. Other uncastrated male adults sing soprano, generally using some form of falsetto but in a much higher range than most countertenors. Examples are Aris Christofellis, Jörg Waschinski, and Ghio Nannini.

However, it is believed the castrati possessed more of a tenorial chest register (the aria "Navigante che non spera" in Leonardo Vinci's opera Il Medo, written for Farinelli, requires notes down to C3, 131 Hz). Similar low-voiced singing can be heard from the jazz vocalist Jimmy Scott, whose range matches approximately that used by female blues singers. High-pitched singer Jordan Smith has demonstrated having more of a tenorial chest register.

Actor Chris Colfer has stated in interviews that when his voice began to change at puberty, he sang in a high voice "constantly" in an effort to retain his range. Actor and singer Alex Newell has soprano range. Voice actor Walter Tetley may or may not have been a castrato; Bill Scott, a co-worker of Tetley's during their later work in television, once half-jokingly quipped that Tetley's mother "had him fixed" to protect the child star's voice-acting career. Tetley did never personally divulge the exact reason for his condition, which left him with the voice of a preteen boy for his entire adult life. Botanist George Washington Carver was noted for his high voice, believed to be the result of pertussis and croup infections in his childhood that stunted his growth.

Notable castrati

 * Loreto Vittori (1604–1670)
 * Baldassare Ferri (1610–1680)
 * Atto Melani (1626–1714)
 * Giovanni Grossi ("Siface") (1653–1697)
 * Pier Francesco Tosi (1654–1732)
 * Francesco Ceccarelli (1752–1814)
 * Nicolò Grimaldi ("Nicolini") (1673–1732)
 * Gaetano Berenstadt (1687–1734)
 * Carlo Mannelli (1640–1697)
 * Antonio Bernacchi (1685–1756)
 * Francesco Bernardi ("Senesino") (1686–1758)
 * Valentino Urbani ("Valentini") (1690–1722)
 * Francesco Paolo Masullo (1679–1733)
 * Giacinto Fontana ("Farfallino") (1692–1739)
 * Giuseppe Aprile (1731–1813)
 * Giovanni Carestini ("Cusanino") (c. 1704 – c. 1760)
 * Carlo Broschi ("Farinelli") (1705–1782)
 * Domenico Annibali ("Domenichino") (1705–1779)
 * Gaetano Majorano ("Caffarelli") (1710–1783)
 * Francesco Soto de Langa (1534–1619)
 * Felice Salimbeni (1712–1752)
 * Gioacchino Conti ("Gizziello") (1714–1761)
 * Giovanni Battista Mancini (1714–1800)
 * Giovanni Manzuoli (1720–1782)
 * Gaetano Guadagni (1725–1792)
 * Giusto Fernando Tenducci (c. 1736–1790)
 * Giuseppe Millico ("Il Muscovita") (1737–1802)
 * Angelo Maria Monticelli (1710–1764)
 * Gaspare Pacchierotti (1740–1821)
 * Venanzio Rauzzini (1746–1810)
 * Luigi Marchesi ("Marchesini") (1754–1829)
 * Vincenzo dal Prato (1756–1828)
 * Girolamo Crescentini (1762–1848)
 * Francesco Antonio Pistocchi (1659–1726)
 * Giovanni Battista "Giambattista" Velluti (1781–1861)
 * Domenico Mustafà (1829–1912)
 * Giovanni Cesari (1843–1904)
 * Domenico Salvatori (1855–1909)
 * Alessandro Moreschi (1858–1922)

title: Castrato


text:
Counting-out game

A counting-out game or counting-out rhyme is a simple method of 'randomly' selecting a person from a group, often used by children for the purpose of playing another game. It usually requires no materials, and is achieved with spoken words or hand gestures. The historian Henry Carrington Bolton suggested in his 1888 book Counting Out Rhymes of Children that the custom of counting out originated in the "superstitious practices of divination by lots."

Many such methods involve one person pointing at each participant in a circle of players while reciting a rhyme. A new person is pointed at as each word is said. The player who is selected at the conclusion of the rhyme is "it" or "out". In an alternate version, the circle of players may each put two feet in and at the conclusion of the rhyme, that player removes one foot and the rhyme starts over with the next person. In this case, the first player that has both feet removed is "it" or "out". In theory the result of a counting rhyme is determined entirely by the starting selection (and would result in a modulo operation), but in practice they are often accepted as random selections because the number of words has not been calculated beforehand, so the result is unknown until someone is selected.

A variant of counting-out game, known as the Josephus problem, represents a famous theoretical problem in mathematics and computer science.

Examples
Several simple games can be played to select one person from a group, either as a straightforward winner, or as someone who is eliminated. Rock, Paper, Scissors, Odd or Even and Blue Shoe require no materials and are played using hand gestures, although with the former it is possible for a player to win or lose through skill rather than luck. Coin flipping and drawing straws are fair methods of randomly determining a player. Fizz Buzz is a spoken word game where if a player slips up and speaks a word out of sequence, they are eliminated.

Common rhymes
(These rhymes may have many local or regional variants.)
 * Eeny, meeny, miny, moe
 * 10 Little Indians
 * Five Little Ducks
 * Ip dip
 * One, Two, Three, Four, Five
 * Tinker, Tailor (traditionally played in England)
 * Yan Tan Tethera
 * Inky Pinky Ponky
 * One potato, two potato
 * Ink-a-dink
 * Akka bakka bonka rakka
 * En Den Dino

Marx Brothers
A scene in the Marx Brothers movie Duck Soup plays on the fact that counting-out games are not really random. Faced with selecting someone to go on a dangerous mission, the character Chicolini (Chico Marx) chants:

 * Rrringspot, vonza, twoza, zig-zag-zav, popti, vinaga, [tin-lie, tav,] harem, scarem, merchan, tarem, teir, tore...

only to stop as he realizes he is about to select himself. He then says, "I did it wrong. Wait, wait, I start here", and repeats the chant—with the same result. After that, he says, "That's no good too. I got it!" and reduces the chant to

 * Rrringspot, buck!

And with this version he finally manages to "randomly" select someone else.

Seinfeld
A version of a counting game "ink-a-dink" features in the Seinfeld episode "The Statue." The relevant scene includes a discussion between the characters of Jerry and George if the person who is "it" is the "winner" or the "loser":

 * JERRY: Alright, let's go. Hey, you know, you owe me one.
 * GEORGE: What?
 * JERRY: The Ink-a-dink.. you were It.
 * GEORGE: It's bad?
 * JERRY: It's very bad.

title: Counting-out game


text:
Talk:Cryptography

A method used by intelligence
A method used by cyberespionage is the modular variablocks method: "variable length of encryption blocks/cryptoblocks". In this system, we don't codify a standard length of bit-quanta, instead inside the key there is a code of the pattern block-change. It is safer to use a separate key in order to select (algorithmically) a variablock pattern. All users of this encryptive method should know beforehand the algorithms of the variable bit-quanta. Also if we have 30 different sizes of bit-quanta, we need 30 different encryptional vocabularies for the translation (they can be algorithmically related; if they are not related, the system is safer, but you have to use more keys). This system has some problems though. 1. you might have to use two or more keys, 2. if your message has noise you might lose the correct pattern of bit-length-variation, you can protect your message from noise by adding one more layer of anti-noise transcription, but that makes your message longer

If you design it carefully it works just fine, but you have to apply anti-noise encoding, otherwise you might lose track of the variable sections. Remember, variable sections means variable cryptographic dictionary. You must create great algorithms, otherwise it won't work well! It's a very old method, but great (if programmed well)!

 * simple English: Hell_i|s_empty_a|nd_all_t|he|_dev|i|ls_are_|here. (6-9-8-2-4-1-7-5-etc... modular variablock section, each number of digits per section corresponds to a different cryptodictionary, even the result can be of variable block length, but you then need more keys and more anti-noise layers)

 * We deliver some key components via different e-mails, some via-different telephones and some face to face at many meetings, also we deliver separately the order of usage. Lazy people deliver one finalized huge key, and everybody reads their messages.

 * If you rotate the same bit-widths in exact order, infiltrators might be able to find your partition pattern either your message. The whole point is to complicate the order, but that might cause problems to the sender if (s)he's a bad programmer. If you're Japanese it always works!

 * And the most important thing is that we add meaningless random digits at certain (pseudorandom-dedicated) partitions the algorithm dedicates for randomness. That also might cause some problems. If your noise is thoroughly random, the infringer might understand some bit-width partition sections. We use pseudorandom algorithms, in order the result is "natural". Do it well, or don't do it at all! It saves or betrays you!!! (we know which partitions have pseudorandom digits, and we simply delete these)

 * Each bit-width corresponds to many different bit-width encoded dictionaries. This method creates huge dictionaries with many languages that have different widths for the same input. You don't have to know all the codes beforehand. Algorithms do it for you. It still remains a big-data option, but it works fine if programmed well. This system has huge hidden entropy. We never repeal the whole pattern of our systemic entropy, because we use many "cryptolanguages" and we only know how we apply each one. And that code doesn't always work. A Russian girl fucks an agent. No crypt-anal-ysis needed.

 * Before we do that, we encrypt our message with other methods. Always use many layers of different methods of encryption.

Cryptographic Hash Functions
The article's description and categorization of cryptographic hash functions is currently incorrect. Cryptographic hash functions can be used in either symmetric or asymmetric encryption and are essentially kinds of keys. The 'symmetric' vs. 'asymmetric' distinction refers to how the keys are shared, if they're shared at all. CessnaMan1989 (talk) 17:31, 7 September 2021 (UTC)

Added sections "Applications" and "Social issues" + split request
A few weeks year ago, technically (how time flies!), I added the sections "Applications" and "Social issues" to this article per User:Nageh's feedback on the 2011 featured article review. Though I was able to add a lot of stuff to the Applications section (and I'm we're hardly getting started!), the various applications of cryptography is a vast topic (as evidenced, for example, by the sheer size of Category:Applications of cryptography) and so deserves its own article. Therefore, I propose that this section be expanded and then split into another article titled Applications of cryptography.

I also added the section "Social issues". However, I have no idea what to put in it, so I left it blank. (Presumably, it should have enough stuff that it would have to be a mere summary of another article titled Social issues of cryptography, but that's another story.) I would ask Nageh himself, but, alas, it seems that he left Wikipedia in 2013 due to excessive wikidrama. Duckmather (talk) 18:42, 2 January 2022 (UTC)

Duckmather (talk) 18:42, 2 January 2022 (UTC)

 * What is in the applications section currently is a bit light for an article, I think, and does not seem not undue here. If you or someone else were to write more content in a separate article, then one could replace the content currently here with a summary of that article. Otherwise, I would say we should just keep expanding the section here and split it when it is actually too large to remain at the main article. Felix QW (talk) 19:19, 18 November 2023 (UTC)
 * Fine, I removed the split tag; thanks for your astute observation. Duckmather (talk) 05:36, 21 November 2023 (UTC)

Viet Nam POW code
Did you guys know about this code? If not, you set up a square that has five letters in a row, then you set up five rows on it. Then you place certain letters in it that has dual sounds in it, such as C, G, Y in it to replace certain other letters in it. Here is a example:

A B C D E   F G H I L    M N O P Q    R T U V W    X Z J K Y

From this, you tap(on a excellent sound conducting surface, like a pipe), for the letter Q, tap five times, wait for one sec.,tap three times. You repeat this, only you adjust what you are doing for each letter as you spell out your words. In this one, the letter C will be used for the letter S. This was created by shot down US POWs who ended up in the Hanoi Hilton, a Viet Nam prison camp. This was in a print issue of The Readers Digest. I can't source this at this time. Some of the issues referred to what happened in Viet Nam, during the Viet Nam War, and this cipher system was in these articles. There are variations of this system, all created to confuse the Vietnamese guards.

How is pre ISBN, pre Internet, print media sourced for Wikipedia? Thanks. Wikipedia is the best. 😘🥰 Nuclear Sergeant (talk) 09:35, 15 July 2023 (UTC)

 * There's an article about this at Tap code. JaggedHamster (talk) 18:53, 16 July 2023 (UTC)

Security lines
Do we have to have a working phone to do this is it all done through the network as long as you have a Wi-Fi network or some sort to use it and what is the encryption technology 256 or what 71.219.144.28 (talk) 19:27, 29 September 2023 (UTC)

Wiki Education assignment: INFO 505 - Foundations of Information Science
— Assignment last updated by Chillimune (talk) 01:58, 12 December 2023 (UTC)

title: Talk:Cryptography


text:
Key size

In cryptography, key size or key length refers to the number of bits in a key used by a cryptographic algorithm (such as a cipher).

Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the fastest known attack against an algorithm), because the security of all algorithms can be violated by brute-force attacks. Ideally, the lower-bound on an algorithm's security is by design equal to the key length (that is, the algorithm's design does not detract from the degree of security inherent in the key length).

Most symmetric-key algorithms are designed to have security equal to their key length. However, after design, a new attack might be discovered. For instance, Triple DES was designed to have a 168-bit key, but an attack of complexity 2112 is now known (i.e. Triple DES now only has 112 bits of security, and of the 168 bits in the key the attack has rendered 56 'ineffective' towards security). Nevertheless, as long as the security (understood as "the amount of effort it would take to gain access") is sufficient for a particular application, then it does not matter if key length and security coincide. This is important for asymmetric-key algorithms, because no such algorithm is known to satisfy this property; elliptic curve cryptography comes the closest with an effective security of roughly half its key length.

Significance
Keys are used to control the operation of a cipher so that only the correct key can convert encrypted text (ciphertext) to plaintext. All commonly-used ciphers are based on publicly known algorithms or are open source and so it is only the difficulty of obtaining the key that determines security of the system, provided that there is no analytic attack (i.e. a "structural weakness" in the algorithms or protocols used), and assuming that the key is not otherwise available (such as via theft, extortion, or compromise of computer systems). The widely accepted notion that the security of the system should depend on the key alone has been explicitly formulated by Auguste Kerckhoffs (in the 1880s) and Claude Shannon (in the 1940s); the statements are known as Kerckhoffs' principle and Shannon's Maxim respectively.

A key should, therefore, be large enough that a brute-force attack (possible against any encryption algorithm) is infeasible – i.e. would take too long and/or would take too much memory to execute. Shannon's work on information theory showed that to achieve so-called 'perfect secrecy', the key length must be at least as large as the message and only used once (this algorithm is called the one-time pad). In light of this, and the practical difficulty of managing such long keys, modern cryptographic practice has discarded the notion of perfect secrecy as a requirement for encryption, and instead focuses on computational security, under which the computational requirements of breaking an encrypted text must be infeasible for an attacker.

Key size and encryption system
Encryption systems are often grouped into families. Common families include symmetric systems (e.g. AES) and asymmetric systems (e.g. RSA and Elliptic-curve cryptography [ECC]). They may be grouped according to the central algorithm used (e.g. ECC and Feistel ciphers). Because each of these has a different level of cryptographic complexity, it is usual to have different key sizes for the same level of security, depending upon the algorithm used. For example, the security available with a 1024-bit key using asymmetric RSA is considered approximately equal in security to an 80-bit key in a symmetric algorithm.

The actual degree of security achieved over time varies, as more computational power and more powerful mathematical analytic methods become available. For this reason, cryptologists tend to look at indicators that an algorithm or key length shows signs of potential vulnerability, to move to longer key sizes or more difficult algorithms. For example,, a 1039-bit integer was factored with the special number field sieve using 400 computers over 11 months. The factored number was of a special form; the special number field sieve cannot be used on RSA keys. The computation is roughly equivalent to breaking a 700 bit RSA key. However, this might be an advance warning that 1024 bit RSA keys used in secure online commerce should be deprecated, since they may become breakable in the foreseeable future. Cryptography professor Arjen Lenstra observed that "Last time, it took nine years for us to generalize from a special to a nonspecial, hard-to-factor number" and when asked whether 1024-bit RSA keys are dead, said: "The answer to that question is an unqualified yes."

The 2015 Logjam attack revealed additional dangers in using Diffie-Hellman key exchange when only one or a few common 1024-bit or smaller prime moduli are in use. This practice, somewhat common at the time, allows large amounts of communications to be compromised at the expense of attacking a small number of primes.

Brute-force attack
Even if a symmetric cipher is currently unbreakable by exploiting structural weaknesses in its algorithm, it may be possible to run through the entire space of keys in what is known as a brute-force attack. Because longer symmetric keys require exponentially more work to brute force search, a sufficiently long symmetric key makes this line of attack impractical.

With a key of length n bits, there are 2n possible keys. This number grows very rapidly as n increases. The large number of operations (2128) required to try all possible 128-bit keys is widely considered out of reach for conventional digital computing techniques for the foreseeable future. However, a quantum computer capable of running Grover's algorithm would be able to search the possible keys more efficiently. If a suitably sized quantum computer would reduce a 128-bit key down to 64-bit security, roughly a DES equivalent. This is one of the reasons why AES supports key lengths of 256 bits and longer.

Symmetric algorithm key lengths
IBM's Lucifer cipher was selected in 1974 as the base for what would become the Data Encryption Standard. Lucifer's key length was reduced from 128 bits to 56 bits, which the NSA and NIST argued was sufficient for non-governmental protection at the time. The NSA has major computing resources and a large budget; some cryptographers including Whitfield Diffie and Martin Hellman complained that this made the cipher so weak that NSA computers would be able to break a DES key in a day through brute force parallel computing. The NSA disputed this, claiming that brute-forcing DES would take them "something like 91 years".

However, by the late 90s, it became clear that DES could be cracked in a few days' time-frame with custom-built hardware such as could be purchased by a large corporation or government. The book Cracking DES (O'Reilly and Associates) tells of the successful ability in 1998 to break 56-bit DES by a brute-force attack mounted by a cyber civil rights group with limited resources; see EFF DES cracker. Even before that demonstration, 56 bits was considered insufficient length for symmetric algorithm keys for general use. Because of this, DES was replaced in most security applications by Triple DES, which has 112 bits of security when using 168-bit keys (triple key).

The Advanced Encryption Standard published in 2001 uses key sizes of 128, 192 or 256 bits. Many observers consider 128 bits sufficient for the foreseeable future for symmetric algorithms of AES's quality until quantum computers become available. However, as of 2015, the U.S. National Security Agency has issued guidance that it plans to switch to quantum computing resistant algorithms and now requires 256-bit AES keys for data classified up to Top Secret.

In 2003, the U.S. National Institute for Standards and Technology, NIST proposed phasing out 80-bit keys by 2015. At 2005, 80-bit keys were allowed only until 2010.

Since 2015, NIST guidance says that "the use of keys that provide less than 112 bits of security strength for key agreement is now disallowed." NIST approved symmetric encryption algorithms include three-key Triple DES, and AES. Approvals for two-key Triple DES and Skipjack were withdrawn in 2015; the NSA's Skipjack algorithm used in its Fortezza program employs 80-bit keys.

Asymmetric algorithm key lengths
The effectiveness of public key cryptosystems depends on the intractability (computational and theoretical) of certain mathematical problems such as integer factorization. These problems are time-consuming to solve, but usually faster than trying all possible keys by brute force. Thus, asymmetric keys must be longer for equivalent resistance to attack than symmetric algorithm keys. The most common methods are assumed to be weak against sufficiently powerful quantum computers in the future.

Since 2015, NIST recommends a minimum of 2048-bit keys for RSA, an update to the widely-accepted recommendation of a 1024-bit minimum since at least 2002.

1024-bit RSA keys are equivalent in strength to 80-bit symmetric keys, 2048-bit RSA keys to 112-bit symmetric keys, 3072-bit RSA keys to 128-bit symmetric keys, and 15360-bit RSA keys to 256-bit symmetric keys. In 2003, RSA Security claimed that 1024-bit keys were likely to become crackable sometime between 2006 and 2010, while 2048-bit keys are sufficient until 2030. the largest RSA key publicly known to be cracked is RSA-250 with 829 bits.

The Finite Field Diffie-Hellman algorithm has roughly the same key strength as RSA for the same key sizes. The work factor for breaking Diffie-Hellman is based on the discrete logarithm problem, which is related to the integer factorization problem on which RSA's strength is based. Thus, a 2048-bit Diffie-Hellman key has about the same strength as a 2048-bit RSA key.

Elliptic-curve cryptography (ECC) is an alternative set of asymmetric algorithms that is equivalently secure with shorter keys, requiring only approximately twice the bits as the equivalent symmetric algorithm. A 256-bit Elliptic-curve Diffie–Hellman (ECDH) key has approximately the same safety factor as a 128-bit AES key. A message encrypted with an elliptic key algorithm using a 109-bit long key was broken in 2004.

The NSA previously recommended 256-bit ECC for protecting classified information up to the SECRET level, and 384-bit for TOP SECRET; In 2015 it announced plans to transition to quantum-resistant algorithms by 2024, and until then recommends 384-bit for all classified information.

Effect of quantum computing attacks on key strength
The two best known quantum computing attacks are based on Shor's algorithm and Grover's algorithm. Of the two, Shor's offers the greater risk to current security systems.

Derivatives of Shor's algorithm are widely conjectured to be effective against all mainstream public-key algorithms including RSA, Diffie-Hellman and elliptic curve cryptography. According to Professor Gilles Brassard, an expert in quantum computing: "The time needed to factor an RSA integer is the same order as the time needed to use that same integer as modulus for a single RSA encryption. In other words, it takes no more time to break RSA on a quantum computer (up to a multiplicative constant) than to use it legitimately on a classical computer." The general consensus is that these public key algorithms are insecure at any key size if sufficiently large quantum computers capable of running Shor's algorithm become available. The implication of this attack is that all data encrypted using current standards based security systems such as the ubiquitous SSL used to protect e-commerce and Internet banking and SSH used to protect access to sensitive computing systems is at risk. Encrypted data protected using public-key algorithms can be archived and may be broken at a later time, commonly known as retroactive/retrospective decryption or "harvest now, decrypt later".

Mainstream symmetric ciphers (such as AES or Twofish) and collision resistant hash functions (such as SHA) are widely conjectured to offer greater security against known quantum computing attacks. They are widely thought most vulnerable to Grover's algorithm. Bennett, Bernstein, Brassard, and Vazirani proved in 1996 that a brute-force key search on a quantum computer cannot be faster than roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case. Thus in the presence of large quantum computers an n-bit key can provide at least n/2 bits of security. Quantum brute force is easily defeated by doubling the key length, which has little extra computational cost in ordinary use. This implies that at least a 256-bit symmetric key is required to achieve 128-bit security rating against a quantum computer. As mentioned above, the NSA announced in 2015 that it plans to transition to quantum-resistant algorithms.

In a 2016 Quantum Computing FAQ, the NSA affirmed: "'A sufficiently large quantum computer, if built, would be capable of undermining all widely-deployed public key algorithms used for key establishment and digital signatures. [...] It is generally accepted that quantum computing techniques are much less effective against symmetric algorithms than against current widely used public key algorithms. While public key cryptography requires changes in the fundamental design to protect against a potential future quantum computer, symmetric key algorithms are believed to be secure provided a sufficiently large key size is used. [...] The public-key algorithms (RSA, Diffie-Hellman, [Elliptic-curve Diffie–Hellman] ECDH, and [Elliptic Curve Digital Signature Algorithm] ECDSA) are all vulnerable to attack by a sufficiently large quantum computer. [...] While a number of interesting quantum resistant public key algorithms have been proposed external to NSA, nothing has been standardized by NIST, and NSA is not specifying any commercial quantum resistant standards at this time. NSA expects that NIST will play a leading role in the effort to develop a widely accepted, standardized set of quantum resistant algorithms. [...] Given the level of interest in the cryptographic community, we hope that there will be quantum resistant algorithms widely available in the next decade. [...] The AES-256 and SHA-384 algorithms are symmetric, and believed to be safe from attack by a large quantum computer.'"

In a 2022 press release, the NSA notified: "'A cryptanalytically-relevant quantum computer (CRQC) would have the potential to break public-key systems (sometimes referred to as asymmetric cryptography) that are used today. Given foreign pursuits in quantum computing, now is the time to plan, prepare and budget for a transition to [quantum-resistant] QR algorithms to assure sustained protection of [National Security Systems] NSS and related assets in the event a CRQC becomes an achievable reality.'"

Since September 2022, the NSA has been transitioning from the Commercial National Security Algorithm Suite (now referred to as CNSA 1.0), originally launched in January 2016, to the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0), both summarized below:

CNSA 2.0

CNSA 1.0

title: Key size