Editing Compiler (section)

== History ==
{{Main|History of compiler construction}}
[[File:Compiler.svg|upright=1.5|thumb |A diagram of the operation of a typical multi-language, multi-target compiler]]
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.<ref>{{Cite web |last=Baghai |first=Christian |date=2023-04-04 |title=The Evolution of Programming Languages: From Primitive Binary to High-Level Abstractions |url=https://christianbaghai.medium.com/the-evolution-of-programming-languages-from-primitive-binary-to-high-level-abstractions-7b8e4b7a2521 |access-date=2024-07-10 |website=Medium |language=en}}</ref> Limited [[main memory|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 language]]s that are strictly defined by their syntax and [[semantics (computer science)|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.<ref>Lecture notes. Compilers: Principles, Techniques, and Tools. Jing-Shin Chang. Department of Computer Science & Information Engineering. National Chi-Nan University</ref>

[[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]].<ref>Naur, P. et al. "Report on ALGOL 60". ''Communications of the ACM'' 3 (May 1960), 299–314.</ref> The ideas derive from the [[context-free grammar]] concepts by linguist [[Noam Chomsky]].<ref>{{cite book |title=Syntactic Structures |isbn=978-3-11-017279-9 |first1=Noam |last1=Chomsky |first2=David W. |last2=Lightfoot |publisher=Walter de Gruyter |date=2002}}</ref> "BNF and its [[Extended Backus–Naur form|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."<ref>{{cite book |title=The Science of Programming |chapter=Appendix 1: Backus-Naur Form |isbn=978-1461259831 |last=Gries |first=David |chapter-url=https://books.google.com/books?id=QFrlBwAAQBAJ&q=1461259835&pg=PA304 |page=304 |publisher=Springer Science & Business Media |date=2012}}</ref>

Between 1942 and 1945, [[Konrad Zuse]] designed the first (algorithmic) programming language for computers called {{lang|de|[[Plankalkül]]}} ("Plan Calculus").  Zuse also envisioned a {{lang|de|Planfertigungsgerät}} ("Plan assembly device") to automatically translate the mathematical formulation of a program into machine-readable [[punched film stock]].<ref name="Hellige_2004"/> While no actual implementation occurred until the 1970s, it presented concepts later seen in [[APL (programming language)|APL]] designed by Ken Iverson in the late 1950s.<ref>{{cite book |title=A Programming Language |url=https://archive.org/details/programminglangu00iver_0 |url-access=registration |first=Kenneth E. |last=Iverson |isbn=978-0-471430-14-8 |publisher=John Wiley & Sons |date=1962}}</ref> APL is a language for mathematical computations.

Between 1949 and 1951, [[Heinz Rutishauser]] proposed [[Superplan]], a high-level language and automatic translator.<ref name="Rutishauser_1951"/> His ideas were later refined by [[Friedrich L. Bauer]] and [[Klaus Samelson]].<ref name="Fothe-Wilke_2014"/>

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.<ref>{{cite book |first=John |last=Backus |chapter=The history of FORTRAN I, II and III |website=Softwarepreservation.org |title=History of Programming Languages |chapter-url=http://www.softwarepreservation.org/projects/FORTRAN/paper/p25-backus.pdf |archive-url=https://ghostarchive.org/archive/20221010/http://www.softwarepreservation.org/projects/FORTRAN/paper/p25-backus.pdf |archive-date=2022-10-10 |url-status=live}}</ref>{{third-party inline|date=October 2024}}
* [[COBOL]] (Common Business-Oriented Language) evolved from [[A-0 System|A-0]] and [[FLOW-MATIC]] to become the dominant high-level language for business applications.<ref>Porter Adams, Vicki (5 October 1981). "Captain Grace M. Hopper: the Mother of COBOL". InfoWorld. 3 (20): 33. ISSN 0199-6649.</ref>
* [[Lisp (programming language)|LISP]] (List Processor) for symbolic computation.<ref>McCarthy, J.; Brayton, R.; Edwards, D.; Fox, P.; Hodes, L.; Luckham, D.; Maling, K.; Park, D.; Russell, S. (March 1960). "LISP I Programmers Manual" (PDF). Boston, Massachusetts: Artificial Intelligence Group, M.I.T. Computation Center and Research Laboratory.</ref>

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.<ref>Compilers Principles, Techniques, & Tools 2nd edition by Aho, Lam, Sethi, Ullman {{ISBN |0-321-48681-1}}</ref>

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 System|A-0]] programming language (and coined the term ''compiler'' to describe it),<ref>{{cite book |last1=Hopper |first1=Grace Murray |title=Proceedings of the 1952 ACM national meeting (Pittsburgh) on - ACM '52 |chapter=The education of a computer |date=1952 |pages=243–249 |doi=10.1145/609784.609818 |s2cid=10081016|doi-access=free }}</ref><ref>{{cite book |last1=Ridgway |first1=Richard K. |title=Proceedings of the 1952 ACM national meeting (Toronto) on - ACM '52 |chapter=Compiling routines |date=1952 |pages=1–5 |doi=10.1145/800259.808980 |s2cid=14878552|doi-access=free }}</ref><ref>{{cite web | title=List of early compilers and assemblers | url=http://shape-of-code.coding-guidelines.com/2017/05/21/evidence-for-28-possible-compilers-in-1957}}</ref> although the A-0 compiler functioned more as a loader or [[Linker (computing)|linker]] than the modern notion of a full compiler.<ref>{{ cite conference |last=Hopper|first=Grace|title=Keynote Address|doi=10.1145/800025.1198341 |book-title=Proceedings of the ACM SIGPLAN History of Programming Languages (HOPL) conference, June 1978 | url=https://dl.acm.org/doi/pdf/10.1145/800025.1198341|url-access=subscription}}</ref><ref>{{ cite web |last=Bruderer|first=Herbert|title=Did Grace Hopper Create the First Compiler? |date=21 December 2022 | url=https://cacm.acm.org/blogs/blog-cacm/268001-did-grace-hopper-create-the-first-compiler/fulltext}}</ref><ref>{{cite journal |last1=Strawn |first1=George |last2=Strawn |first2=Candace |title=Grace Hopper: Compilers and Cobol | url = https://www.computer.org/csdl/magazine/it/2015/01/mit2015010062/13rRUxCitFF |journal=IT Professional |date=2015 |volume=17 |issue=Jan.-Feb. 2015 |pages=62–64 |doi=10.1109/MITP.2015.6 |url-access=subscription }}</ref>
* ''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.<ref>Knuth, Donald E.; Pardo, Luis Trabb, "Early development of programming languages", Encyclopedia of Computer Science and Technology (Marcel Dekker) 7: 419–493</ref>
* ''1954–1957'': A team led by [[John Backus]] at [[IBM]] developed [[Fortran|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.<ref>{{Citation |last=Backus |first=John |title=The history of Fortran I, II, and III |date=1978-06-01 |work=History of programming languages |pages=25–74 |url=https://dl.acm.org/doi/10.1145/800025.1198345 |access-date=2024-10-09 |place=New York, NY, USA |publisher=Association for Computing Machinery |doi=10.1145/800025.1198345 |isbn=978-0-12-745040-7|url-access=subscription }}</ref>
* ''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 [[Block (programming)|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 [[Backus–Naur form|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."<ref>{{cite web |first=C.A.R. |last=Hoare |title=Hints on Programming Language Design |date=December 1973 |url=http://www.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hints.pdf |archive-url=https://ghostarchive.org/archive/20221010/http://www.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hints.pdf |archive-date=2022-10-10 |url-status=live |page=27}} (This statement is sometimes erroneously attributed to [[Edsger W. Dijkstra]], also involved in implementing the first ALGOL 60 compiler.)</ref><ref name="r3rs">{{cite web |editor1-first=Jonathan |editor1-last=Rees |editor2-first=William |editor2-last=Clinger |author-first1=Hal |author-last1=Abelson |author-first2=R. K. |author-last2=Dybvig |title=Revised(3) Report on the Algorithmic Language Scheme, (Dedicated to the Memory of ALGOL 60)
| url=http://groups.csail.mit.edu/mac/ftpdir/scheme-reports/r3rs-html/r3rs_toc.html
|access-date=2009-10-20
|display-authors=etal}}</ref>
* ''1958–1962'': [[John McCarthy (computer scientist)|John McCarthy]] at [[MIT]] designed [[Lisp (programming language)|LISP]].<ref>"[https://dspace.mit.edu/bitstream/handle/1721.1/6096/AIM-008.pdf?sequence=2 Recursive Functions of Symbolic Expressions and Their Computation by Machine]", Communications of the ACM, April 1960</ref> 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.<ref>{{cite book |title=Lisp 1.5 Programmers Manual |publisher=The MIT Press |last1=McCarthy |first1=John |last2=Abrahams |first2=Paul W. |last3=Edwards |first3=Daniel J. |last4=Hart |first4=Timothy P. |last5=Levin |first5=Michael I. |url=https://books.google.com/books?id=68j6lEJjMQwC&pg=PR1 |isbn=978-0-26213011-0 |date=1965}}</ref>

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 (programming language)|B]], and [[C (programming language)|C]].

[[BCPL]] (Basic Combined Programming Language) designed in 1966 by [[Martin Richards (computer scientist)|Martin Richards]] at the University of Cambridge was originally developed as a compiler writing tool.<ref>"[http://prog.vub.ac.be/~tjdhondt/ESL/BCPL_to_Cfront_files/p557-richards.pdf BCPL: A tool for compiler writing and system programming]" M. Richards, University Mathematical Laboratory Cambridge, England 1969</ref> Several compilers have been implemented, Richards' book provides insights to the language and its compiler.<ref>BCPL: The Language and Its Compiler, M Richards, Cambridge University Press (first published 31 December 1981)</ref> BCPL was not only an influential systems programming language that is still used in research<ref>The BCPL Cintsys and Cintpos User Guide, M. Richards, 2017</ref> 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 J. Corbató|Fernando Corbató]] from MIT.<ref>{{cite web |first1=F. J. |last1=Corbató |last2=Vyssotsky |first2=V. A. |title=Introduction and Overview of the MULTICS System |work=1965 Fall Joint Computer Conference |publisher=Multicians.org |url=https://multicians.org/fjcc1.html}}</ref> Multics was written in the [[PL/I]] language developed by IBM and IBM User Group.<ref>Report II of the SHARE Advanced Language Development Committee, 25 June 1964</ref> 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.<ref>Multicians.org "The Choice of PL/I" article, Editor /tom Van Vleck</ref> 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.<ref>"PL/I As a Tool for System Programming", F.J. Corbato, Datamation 6 May 1969 issue</ref> EPL supported the project until a boot-strapping compiler for the full PL/I could be developed.<ref>"[https://www.computer.org/csdl/proceedings/afips/1969/5074/00/50740187.pdf The Multics PL/1 Compiler]", R. A. Freiburghouse, GE, Fall Joint Computer Conference 1969</ref>

Bell Labs left the Multics project in 1969, and developed a system programming language [[B (programming language)|B]] based on BCPL concepts, written by [[Dennis Ritchie]] and [[Ken Thompson]]. Ritchie created a boot-strapping compiler for B and wrote [[Unix|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 (programming language)|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.<ref>Dennis M. Ritchie, "[https://www.bell-labs.com/usr/dmr/www/chist.pdf The Development of the C Language]", ACM Second History of Programming Languages Conference, April 1993</ref> 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.<ref>S.C. Johnson, "a Portable C Compiler: Theory and Practice", 5th ACM POPL Symposium, January 1978</ref><ref>A. Snyder, [https://apps.dtic.mil/sti/pdfs/ADA010218.pdf A Portable Compiler for the Language C], MIT, 1974.</ref>

[[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.<ref>K. Nygaard, University of Oslo, Norway, "[http://www.cs.kent.edu/~durand/CS43101Fall2004/resources/BasicConceptsOOP-Nygaard1986.pdf Basic Concepts in Object Oriented Programming]", SIGPLAN Notices V21, 1986</ref> Bell Labs became interested in OOP with the development of [[C++]].<ref>B. Stroustrup: "What is Object-Oriented Programming?" Proceedings 14th ASU Conference, 1986.</ref> 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.<ref>Bjarne Stroustrup, "An Overview of the C++ Programming Language", Handbook of Object Technology (Editor: Saba Zamir, {{ISBN |0-8493-3135-8}})</ref> 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 language]]s 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.<ref>Leverett, Cattell, Hobbs, Newcomer, Reiner, Schatz, Wulf: "An Overview of the Production Quality Compiler-Compiler Project", CMU-CS-89-105, 1979</ref> 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.<ref>W. Wulf, K. Nori, "[https://apps.dtic.mil/sti/pdfs/ADA125935.pdf Delayed binding in PQCC generated compilers]", CMU Research Showcase Report, CMU-CS-82-138, 1982
</ref> 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.<ref>Joseph M. Newcomer, David Alex Lamb, Bruce W. Leverett, Michael Tighe, William A. Wulf - Carnegie-Mellon University and David Levine, Andrew H. Reinerit - Intermetrics: "TCOL Ada: Revised Report on An Intermediate Representation for the DOD Standard Programming Language", 1979
</ref> 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 (programming language)|Ada]].

The Ada ''STONEMAN'' document{{efn| name=Stoneman|1= [[United States Department of Defense]] (18 February 1980) [https://en.wikisource.org/wiki/Stoneman_requirements Stoneman requirements] }} 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.<ref>William A. Whitaker, "Ada - the project: the DoD High Order Working Group", ACM SIGPLAN Notices (Volume 28, No. 3, March 1991)</ref>

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.<ref>CECOM Center for Software Engineering Advanced Software Technology, "Final Report - Evaluation of the ACEC Benchmark Suite for Real-Time Applications", AD-A231 968, 1990</ref> 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.<ref>P.Biggar, E. de Vries, D. Gregg, "A Practical Solution for Scripting Language Compilers", submission to Science of Computer Programming, 2009</ref>

"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."<ref>M.Hall, D. Padua, K. Pingali, "Compiler Research: The Next 50 Years", ACM Communications 2009 Vol 54 #2</ref> 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.