NELIAC

Navy Electronics Laboratory International ALGOL Compiler (NELIAC)
Paradigm	procedural, imperative, structured
Family	ALGOL
Designed by	Harry Huskey, Maurice Halstead, Niklaus Wirth
Developer	Navy Electronics Laboratory
First appeared	1958;66 years ago
Typing discipline	static, strong
Scope	Lexical
Implementation language	Assembly, NELIAC
Platform	AN/USQ-17, AN/USQ-20; CDC 1604; UNIVAC 1107, 490, 418; IBM 704, 709
Influenced by
	ALGOL 58

Last updated January 13, 2024

The Navy Electronics Laboratory International ALGOL Compiler (NELIAC) is a dialect and compiler implementation of the programming language ALGOL 58, developed by the Navy Electronics Laboratory (NEL) in 1958.^[1]

Origin

NELIAC was the brainchild of Harry Huskey, then chairperson of the Association for Computing Machinery (ACM) and a well known computer scientist, and supported by Maurice Halstead, the head of the computing center at NEL. The earliest version was implemented on the prototype AN/USQ-17 computer (called the Countess, after Countess Ada Lovelace) at the laboratory. It was the world's first self-compiling compiler, a trait called bootstrapping. This means that the compiler was first coded in simplified form in assembly language "the bootstrap", and then rewritten in its own language, compiled by this "bootstrap" compiler, and recompiled by itself, making the "bootstrap" obsolete.

It is considered a variant of ALGOL 58 because of similarities to that language, but within two years, the ALGOL committee produced other versions of ALGOL, and NELIAC and ALGOL diverged.

Use

The compiler was used on the Countess to produce a version for the CDC 1604, and later self-compiled on that machine. Many other versions were produced for commercial computers such as the UNIVAC 1107, 490, and 418, and the IBM 704 and 709. The production version of NELIAC was a second generation system (for the AN/USQ-20, a modernized and militarized version of the AN/USQ-20), compiled by the first version, but including full decoding of algorithmic expressions and, later, an input/output (I/O) system missing on all other versions.

The decompiler was a curiosity. The first version ran on the Countess, but was later ported to the CDC 1604, and to other computers, and received some notice at some universities. However, it turned out that, at that time, there were few programs worth decompiling.

NELIAC was never intended to be a commercial product. Its primary advantage over other compilers of the day was its portability to other computers,^[2] and its one-pass compiler architecture which made possible such fast compile times that it compiled 60 to 120 times faster than other high-level programming languages which used multi-pass compilers. The JOVIAL compiler made 14 passes, for example. The simplicity of the language and its rapid compile times permitted much faster development cycles than other contemporaneous compilers. It was an in-house NEL effort to make possible a more cost-effective solution to the problem of computer system development.

NELIAC was used by the Royal Canadian Navy to develop software for the Command and Control System 280 (used on the DDH-280 destroyers) in the years 1967 to 1971. The Canadian Navy established a Program Generation Centre in Ottawa, Ontario, Canada for this software development. The host computer was the Litton L304F containing 160 kB of memory.^[3] Because of memory constraints the NELIAC application software was later rewritten in assembler code.

NELIAC was used to implement an experimental shipboard anti-submarine warfare system, and was also used for the development of the National Emergency Command Post Afloat (NECPA) project which developed a strategic command and control system installed on aircraft carriers and cruisers. Perhaps the most successful NELIAC application was control of the U.S. Navy automated High Frequency Direction Finding network (Classic Bullseye) which went into production in 1968 and lasted until the early 1990s.

In addition, NEL developed NELOS, a batch operating system which provided input-output for magnetic tapes, printers, and telecom equipment, provided sequenced compiling of jobs, and a symbol library permitting linking of very large computer applications and executing them on-line. These included suites of information management programs, including databases, free form queries with a precursor of IBM's GIS, and reporting applications. NECPA and NELOS went to sea in 1966.

NELIAC's end

However, NELIAC programs were not easily portable because the language permitted manipulation of binary characters which were dependent on word lengths. Further, the NELIAC language had no input-output schemes. Also, its looping statement was unusually strict in that the index variable had to hit the end value exactly, or else an infinite loop would occur. These were the Achilles' heels of NELIAC.

Many other well-known computer experts like Niklaus Wirth made contributions to the project, but ultimately NELIAC fell out of favor after the Navy Department standardized on compilers with commercial support.

Related Research Articles

ALGOL is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the Association for Computing Machinery (ACM) in textbooks and academic sources for more than thirty years.

In computing, a compiler is a computer program that translates computer code written in one programming language into another 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 to create an executable program.

In computer programming, a macro is a rule or pattern that specifies how a certain input should be mapped to a replacement output. Applying a macro to an input is known as macro expansion. The input and output may be a sequence of lexical tokens or characters, or a syntax tree. Character macros are supported in software applications to make it easy to invoke common command sequences. Token and tree macros are supported in some programming languages to enable code reuse or to extend the language, sometimes for domain-specific languages.

Niklaus Emil Wirth was a Swiss computer scientist. He designed several programming languages, including Pascal, and pioneered several classic topics in software engineering. In 1984, he won the Turing Award, generally recognized as the highest distinction in computer science, "for developing a sequence of innovative computer languages".

Pascal is an imperative and procedural programming language, designed by Niklaus Wirth as a small, efficient language intended to encourage good programming practices using structured programming and data structuring. It is named after French mathematician, philosopher and physicist Blaise Pascal.

SNOBOL is a series of programming languages developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky, culminating in SNOBOL4. It was one of a number of text-string-oriented languages developed during the 1950s and 1960s; others included COMIT and TRAC.

Turing is a high-level, general-purpose programming language developed in 1982 by Ric Holt and James Cordy, at University of Toronto in Ontario, Canada. It was designed in order to help students taking their first computer science course learn how to code. Turing is a descendant of Pascal, Euclid, and SP/k that features a clean syntax and precise machine-independent semantics.

In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.

JOVIAL is a high-level programming language based on ALGOL 58, specialized for developing embedded systems. It was a major system programming language through the 1960s and 1970s.

BLISS is a system programming language developed at Carnegie Mellon University (CMU) by W. A. Wulf, D. B. Russell, and A. N. Habermann around 1970. It was perhaps the best known system language until C debuted a few years later. Since then, C became popular and common, and BLISS faded into obscurity. When C was in its infancy, a few projects within Bell Labs debated the merits of BLISS vs. C.

A system programming language is a programming language used for system programming; such languages are designed for writing system software, which usually requires different development approaches when compared with application software. Edsger Dijkstra refers to these languages as machine oriented high order languages, or mohol.

ALGOL 60 is a member of the ALGOL family of computer programming languages. It followed on from ALGOL 58 which had introduced code blocks and the begin and end pairs for delimiting them, representing a key advance in the rise of structured programming. ALGOL 60 was one of the first languages implementing function definitions. ALGOL 60 function definitions could be nested within one another, with lexical scope. It gave rise to many other languages, including CPL, PL/I, Simula, BCPL, B, Pascal, and C. Practically every computer of the era had a systems programming language based on ALGOL 60 concepts.

XPL, for expert's programming language is a programming language based on PL/I, a portable one-pass compiler written in its own language, and a parser generator tool for easily implementing similar compilers for other languages. XPL was designed in 1967 as a way to teach compiler design principles and as starting point for students to build compilers for their own languages.

ALGOL 58, originally named IAL, is one of the family of ALGOL computer programming languages. It was an early compromise design soon superseded by ALGOL 60. According to John Backus

The Zurich ACM-GAMM Conference had two principal motives in proposing the IAL: (a) To provide a means of communicating numerical methods and other procedures between people, and (b) To provide a means of realizing a stated process on a variety of machines...

CMS-2 is an embedded systems programming language used by the United States Navy. It was an early attempt to develop a standardized high-level computer programming language intended to improve code portability and reusability. CMS-2 was developed primarily for the US Navy’s tactical data systems (NTDS).

The U.S. Navy Electronics Laboratory (NEL) was created in 1945, with consolidation of the naval radio station, radar operators training school, and radio security activity of the Navy Radio and Sound Lab (NRSL) and its wartime partner, the University of California Division of War Research. NEL’s charter was “to effectuate the solution of any problem in the field of electronics, in connection with the design, procurement, testing, installation and maintenance of electronic equipment for the U.S. Navy.” Its radio communications and sonar work was augmented with basic research in the propagation of electromagnetic energy in the atmosphere and of sound in the ocean.

In computer science, bootstrapping is the technique for producing a self-compiling compiler – that is, a compiler written in the source programming language that it intends to compile. An initial core version of the compiler is generated in a different language ; successive expanded versions of the compiler are developed using this minimal subset of the language. The problem of compiling a self-compiling compiler has been called the chicken-or-egg problem in compiler design, and bootstrapping is a solution to this problem.

In computing, a compiler is a computer program that transforms source code written in a programming language or computer language, into another computer language. The most common reason for transforming source code is to create an executable program.

In computer programming, self-hosting is the use of a program as part of the toolchain or operating system that produces new versions of that same program—for example, a compiler that can compile its own source code. Self-hosting software is commonplace on personal computers and larger systems. Other programs that are typically self-hosting include kernels, assemblers, command-line interpreters and revision control software.

References

↑ Huskey, H.D.; et al. (August 1960). "NELIAC: A Dialect of Algol". Communications of the ACM. 3 (8): 463–468. doi: 10.1145/367368.367373 . S2CID 5226222.
↑ Halstead, Maurice Howard (January 1, 1962). Machine-Independent Computer Programming. Spartan Books. ISBN 978-0-5984-1477-9.
↑ Macgillivray, D.N.; Switzer, G. "Canadian Naval Contribution to Tactical Data Systems and Data Link Development" (PDF). Canadian Naval Technical History Association. Retrieved 12 January 2024.

External links

A syntactic description of BC NELIAC at the ACM.
Original documents about NELIAC and background information. (archived 2007)
History of NELIAC through 1991.
Documentation on bitsavers.org web-site (in English)
Documentation on softwarepreservation.org web-site (in English)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Huskey, H.D.; et al. (August 1960). "NELIAC: A Dialect of Algol". Communications of the ACM. 3 (8): 463–468. doi: 10.1145/367368.367373 . S2CID 5226222.

[2] Halstead, Maurice Howard (January 1, 1962). Machine-Independent Computer Programming. Spartan Books. ISBN 978-0-5984-1477-9.

[3] Macgillivray, D.N.; Switzer, G. "Canadian Naval Contribution to Tactical Data Systems and Data Link Development" (PDF). Canadian Naval Technical History Association. Retrieved 12 January 2024.

[1]

[2]

[3]