XPL is a
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
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.
XPL was designed and implemented by
William M. McKeeman
William is a male given name of Germanic origin.Hanks, Hardcastle and Hodges, ''Oxford Dictionary of First Names'', Oxford University Press, 2nd edition, , p. 276. It became very popular in the English language after the Norman conquest of Engl ...
,
David B. Wortman,
James J. Horning and others at
Stanford University
Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is consider ...
. XPL was first announced at the 1968
Fall Joint Computer Conference The Joint Computer Conferences were a series of computer conferences in the United States held under various names between 1951 and 1987. The conferences were the venue for presentations and papers representing "cumulative work in the omputerfield ...
. The methods and compiler are described in detail in the 1971 textbook ''A Compiler Generator''.
They called the combined work a 'compiler generator'. But that implies little or no language- or target-specific programming is required to build a compiler for a new language or new target. A better label for XPL is a
translator
Translation is the communication of the Meaning (linguistic), meaning of a #Source and target languages, source-language text by means of an Dynamic and formal equivalence, equivalent #Source and target languages, target-language text. The ...
writing system. It helps to write a compiler with less new or changed programming code.
Language
The XPL language is a simple, small, efficient dialect of PL/I intended mainly for the task of writing compilers. The XPL language was also used for other purposes once it was available. XPL can be compiled easily to most modern machines by a simple compiler. Compiler internals can be written easily in XPL, and the code is easy to read. The PL/I language was designed by an
IBM committee in 1964 as a comprehensive language replacing
Fortran,
COBOL
COBOL (; an acronym for "common business-oriented language") is a compiled English-like computer programming language designed for business use. It is an imperative, procedural and, since 2002, object-oriented language. COBOL is primarily us ...
, and
ALGOL, and meeting all customer and internal needs. These ambitious goals made PL/I complex, hard to implement efficiently, and sometimes surprising when used. XPL is a small dialect of the full language. XPL has one added feature not found in PL/I: a
STRING
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
datatype with dynamic lengths. String values live in a separate text-only
heap
Heap or HEAP may refer to:
Computing and mathematics
* Heap (data structure), a data structure commonly used to implement a priority queue
* Heap (mathematics), a generalization of a group
* Heap (programming) (or free store), an area of memory f ...
memory space with automatic
garbage collection
Waste collection is a part of the process of waste management. It is the transfer of solid waste from the point of use and disposal to the point of treatment or landfill. Waste collection also includes the curbside collection of recyclable m ...
of stale values. Much of what a simple compiler does is manipulating input text and output byte streams, so this feature helps simplify XPL-based compilers.
Components
XCOM
The XPL compiler, called XCOM, is a one-pass compiler using a table-driven
parser and simple
code generation techniques. Versions of XCOM exist for different
machine architectures, using different hand-written code generation modules for those targets. The original target was
IBM System/360
The IBM System/360 (S/360) is a family of mainframe computer systems that was announced by IBM on April 7, 1964, and delivered between 1965 and 1978. It was the first family of computers designed to cover both commercial and scientific applica ...
, which is a proper subset of
IBM System/370
The IBM System/370 (S/370) is a model range of IBM mainframe computers announced on June 30, 1970, as the successors to the System/360 family. The series mostly maintains backward compatibility with the S/360, allowing an easy migration path f ...
,
IBM System/390
The IBM System/390 is a discontinued mainframe product family implementing the ESA/390, the fifth generation of the System/360 instruction set architecture. The first computers to use the ESA/390 were the Enterprise System/9000 (ES/9000) ...
and
IBM System z.
XCOM compiles from XPL source code, but since XCOM itself is written in XPL it can compile itself – it is a ''self-compiling compiler'', not reliant on other compilers. Several famous languages have self-compiling compilers, including
Burroughs B5000 Algol, PL/I,
C,
LISP
A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech.
Types
* A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lisping ...
, and
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
. Creating such compilers is a chicken-and-egg conundrum. The language is first implemented by a temporary compiler written in some other language, or even by an interpreter (often an interpreter for an intermediate code, as
BCPL
BCPL ("Basic Combined Programming Language") is a procedural, imperative, and structured programming language. Originally intended for writing compilers for other languages, BCPL is no longer in common use. However, its influence is still ...
can do with
intcode or
O-code).
XCOM began as an Algol program running on Burroughs machines, translating XPL source code into System/360 machine code. The XPL team manually turned its Algol source code into XPL source code. That XPL version of XCOM was then compiled on Burroughs, creating a self-compiling XCOM for System/360 machines. The Algol version was then thrown away, and all further improvements happened in the XPL version only. This is called
bootstrapping the compiler. The authors of XPL invented the
tombstone diagram
In computing, tombstone diagrams (or T-diagrams) consist of a set of “puzzle pieces” representing compilers and other related language processing programs. They are used to illustrate and reason about transformations from a source language ...
or T-diagram to document the bootstrapping process.
Retargeting
In software engineering, retargeting is an attribute of software development tools that have been specifically designed to generate code for more than one computing platform.
Compilers
A retargetable compiler is a compiler that has been designed ...
the compiler for a new machine architecture is a similar exercise, except only the code generation modules need to be changed.
XCOM is a one-pass compiler (but with an emitted code fix-up process for forward branches, loops and other defined situations). It emits
machine code for each statement as each grammar rule within a statement is recognized, rather than waiting until it has parsed the entire procedure or entire program. There are no parse trees or other required intermediate program forms, and no loop-wide or procedure-wide optimizations. XCOM does, however, perform
peephole optimization
Peephole optimization is an optimization technique performed on a small set of compiler-generated instructions; the small set is known as the peephole or window.
Peephole optimization involves changing the small set of instructions to an equiva ...
. The code generation response to each grammar rule is attached to that rule. This immediate approach can result in inefficient code and inefficient use of machine registers. Such are offset by the efficiency of implementation, namely, the use of dynamic strings mentioned earlier: in processing text during compilation, substring operations are frequently performed. These are as fast as an assignment to an integer; the actual substring is not moved. In short, it is quick, easy to teach in a short course, fits into modest-sized memories, and is easy to change for different languages or different target machines.
ANALYZER
The XCOM compiler has a hand-written
lexical scanner and a mechanically-generated parser. The syntax of the compiler's input language (in this case, XPL) is described by a simplified
BNF grammar. XPL's grammar analyzer tool ANALYZER or XA turns this into a set of large data tables describing all legal combinations of the syntax rules and how to discern them. This table generation step is re-done only when the language is changed. When the compiler runs, those data tables are used by a small, language-independent parsing algorithm to parse and respond to the input language. This style of table-driven parser is generally easier to write than an entirely hand-written
recursive descent
In computer science, a recursive descent parser is a kind of top-down parsing, top-down parser built from a set of mutual recursion, mutually recursive procedures (or a non-recursive equivalent) where each such procedure (computer science), proce ...
parser. XCOM uses a
bottom-up parsing method, in which the compiler can delay its decision about which syntax rule it has encountered until it has seen the rightmost end of that phrase. This handles a wider range of programming languages than
top-down
Top-down may refer to:
Arts and entertainment
* " Top Down", a 2007 song by Swizz Beatz
* "Top Down", a song by Lil Yachty from ''Lil Boat 3''
* "Top Down", a song by Fifth Harmony from ''Reflection'' Science
* Top-down reading, is a part of ...
methods, in which the compiler must guess or commit to a specific syntax rule early, when it has only seen the left end of a phrase.
Runtime
XPL includes a minimal runtime support library for allocating and garbage-collecting XPL string values. The source code for this library must be included into most every program written in XPL.
SKELETON
The last piece of the XPL compiler writing system is an example compiler named SKELETON. This is just XCOM with parse tables for an example toy grammar instead of XPL's full grammar. It is a starting point for building a compiler for some new language, if that language differs much from XPL.
XMON
XPL is run under the control of a monitor, XMON, which is the only operating system-specific part of this system, and which acts as a "loader" for XCOM itself or any programs which were developed using XCOM, and also provides three auxiliary storage devices for XCOM's use, and which are directly accessed by block number. The originally published XMON was optimized for
IBM 2311
IBM manufactured magnetic disk storage devices from 1956 to 2003, when it sold its hard disk drive business to Hitachi. Both the hard disk drive (HDD) and floppy disk drive (FDD) were invented by IBM and as such IBM's employees were responsible fo ...
s. An XMON parameter FILE= enabled the monitor to efficiently use other disks with larger block sizes. The working disk block size was also a compile-time constant in
XCOM.
XMON used a very simple strategy for disk direct access. NOTE provided the address of a disk track. POINT set the location of the next disk track to be the address previously returned by NOTE. This strategy was adopted to allow easy porting of XMON to other OSes, and to avoid the much more complicated disk direct access options available at that time.
Converting XMON from its primitive use of NOTE, POINT and READ/WRITE disk operations—with precisely 1 block per track—to
EXCP (i.e., write/create new records) and
XDAP (i.e., read/update old records)—with n blocks per track, where n was computed at run-time from the target device's physical characteristics and could be significantly greater than 1—achieved significantly improved application performance and decreased operating system overhead.
Although originally developed for
OS/360, XMON (either the original NOTE, POINT and READ/WRITE implementation; or the EXCP and XDAP enhancement) will run on subsequently released IBM OSes, including OS/370, XA,
OS/390
OS/390 is an IBM operating system for the System/390 IBM mainframe computers.
Overview
OS/390 was introduced in late 1995 in an effort to simplify the packaging and ordering for the key, entitled elements needed to complete a fully functional ...
and
z/OS, generally without any changes.
Parsing
XCOM originally used a now-obsolete bottom-up parse table method called ''
Mixed Strategy Precedence'', invented by the XPL team (although the ''officially'' released version retains the MSP parser and ''does not'' include later-released "peephole optimizations" and additional data types which were developed outside of the ''original'' implementation team.) MSP is a generalization of the
simple precedence parser In computer science, a simple precedence parser is a type of bottom-up parser for context-free grammars that can be used only by simple precedence grammars.
The implementation of the parser is quite similar to the generic bottom-up parser. A stack ...
method invented by
Niklaus Wirth for
PL360. Simple precedence is itself a generalization of the trivially simple
operator precedence methods that work nicely for expressions like A+B*(C+D)-E. MSP tables include a list of expected triplets of language symbols. This list grows larger as the cube of the grammar size, and becomes quite large for typical full programming languages. XPL-derived compilers were difficult to fit onto minicomputers of the 1970s with limited memories.
[Indeed, using a hand-written LALR-like analyzer and a particularly efficient "decomposition" procedure for the produced parsing tables, it was possible to generate a parser for the entire XPL language on a 2 MHz ]Z80
The Z80 is an 8-bit microprocessor introduced by Zilog as the startup company's first product. The Z80 was conceived by Federico Faggin in late 1974 and developed by him and his 11 employees starting in early 1975. The first working samples were ...
microcomputer which had only 48 kilobytes of internal memory (DRAM
Dynamic random-access memory (dynamic RAM or DRAM) is a type of random-access semiconductor memory that stores each bit of data in a memory cell, usually consisting of a tiny capacitor and a transistor, both typically based on metal-oxid ...
) and only 100 kilobytes of external memory (floppy disk
A floppy disk or floppy diskette (casually referred to as a floppy, or a diskette) is an obsolescent type of disk storage composed of a thin and flexible disk of a magnetic storage medium in a square or nearly square plastic enclosure lined w ...
) running under CP/M
CP/M, originally standing for Control Program/Monitor and later Control Program for Microcomputers, is a mass-market operating system created in 1974 for Intel 8080/ 85-based microcomputers by Gary Kildall of Digital Research, Inc. Initial ...
. This version was completed in 1980. Porting to MacOS (9, later X) was subsequently completed. MSP is also not powerful enough to handle all likely grammars. It is applicable only when the language designer can tweak the language definition to fit MSP's restrictions, before the language is widely used.
The
University of Toronto
The University of Toronto (UToronto or U of T) is a public research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...
subsequently changed XCOM and XA to instead use a variant of
Donald Knuth's
LR parser bottom-up method.
[This version was NOT released to the general community, hence it remains proprietary to its authors, or to their institutions. Repeated requests for an SLR(1) or an LALR(1) distribution of XPL have been ignored by its authors.] XCOM's variant is called
Simple LR or SLR. It handles more grammars than MSP but not quite as many grammars as
LALR
In computer science, an LALR parser or Look-Ahead LR parser is a simplified version of a canonical LR parser, to parse a text according to a set of production rules specified by a formal grammar for a computer language. ("LR" means left-to-right, ...
or full
LR(1). The differences from LR(1) are mostly in the table generator's algorithms, not in the compile-time parser method. XCOM and XA predate the widespread availability of Unix and its
yacc
Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a Look Ahead Left-to-Right Rightmost Derivation (LALR) parser generator, generating a LALR parser (the part of a com ...
parser generator tool. XA and yacc have similar purposes.
XPL is open source. The System/360 version of XPL was distributed through the IBM
SHARE users organization. Other groups ported XPL onto many of the larger machines of the 1970s. Various groups extended XPL, or used XPL to implement other moderate-sized languages.
Applications
XPL has been used to develop a number of compilers for various languages and systems.
*
Stony Brook Pascal
*
HAL/S
HAL/S (''High-order Assembly Language/Shuttle'') is a real-time aerospace programming language compiler and cross-compiler for avionics applications used by NASA and associated agencies ( JPL, etc.). It has been used in many U.S. space projects si ...
, the language used for the Space Shuttle program
*
MALUS
''Malus'' ( or ) is a genus of about 30–55 species of small deciduous trees or shrubs in the family Rosaceae, including the domesticated orchard apple, crab apples, wild apples, and rainberries.
The genus is native to the temperate zone of th ...
, a
system programming language
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 D ...
used by General Motors to develop their
Multiple Console Time Sharing System
The Multiple Console Time Sharing System (MCTS) was an operating system developed by General Motors Research Laboratories in the 1970s for the Control Data Corporation STAR-100 supercomputer. MCTS was built to support GM's computer-aided design ( ...
*
New England Digital
New England Digital Corporation (1976–1993) was founded in Norwich, Vermont, and relocated to White River Junction, Vermont. It was best known for its signature product, the Synclavier Synthesizer System, which evolved into the Synclavier Digita ...
used a variant of XPL, called "Scientific XPL" for their ABLE series computers, used for laboratory automation, computer networking, and control of music synthesis hardware, starting in the mid-1970s
Current status
XPL continues to be ported to current computers. An x86/
FreeBSD
FreeBSD is a free and open-source Unix-like operating system descended from the Berkeley Software Distribution (BSD), which was based on Research Unix. The first version of FreeBSD was released in 1993. In 2005, FreeBSD was the most popular ...
port was done in 2000, an x86/
Linux
Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which ...
port in 2015, and an XPL to C translator in 2017.
Bibliography
* Alexander, W. G. and Wortman, D. B. "Static and Dynamic Charactersistics of XPL Programs." IEEE Computer November 1975; 41-46.
* Ancona, Massimo, Dodero, Gabriella, and Durante, Ercole Luigi "Cross software development for microprocessors using a translator writing system" Proceedings of the 4th International Conference on Software Engineering 1979: 399-402.
* Kamnitzer, S. H. "Bootstrapping XPL from IBM/360 to UNIVAC 1100." ACM SIGPLAN Notices May 1975: 14-20.
* Karger, Paul A. "An Implementation of XPL for Multics." SB thesis. Massachusetts Institute of Technology, 1972.
* Klumpp, Allan R. "Space Station Flight Software: Hal/S or Ada?" Computer March 1985: 20-28.
* Leach, Geoffrey and Golde, Helmut. "Bootstrapping XPL to an XDS Sigma 5 Computer." Software: Practice and Experience 3 (1973): 235-244.
* McKeeman, William M., Horning, James J. and Wortman, David B. A Compiler Generator. Englewood Cliffs, NJ: Prentice-Hall, 1970.
* McKeeman, W. M., Horning, James J., Nelson, E. C., and Wortman, D. B. "The XPL compiler generator system." AFIPS Conference Proceedings: 1968 Fall Joint Computer Conference. Washington DC: The Thompson Book Company. 1968: 617-635.
* Sitton, Gary A., Kendrick, Thomas A., and Carrick, Jr., A. Gil. "The PL/EXUS Language and Virtual Machine" Proceedings of the ACM-IEEE Symposium on High-level-language Computer Architecture Nov, 1973: 124-130.
* Slimick, John "Current Systems Implementation Languages: One User's View" Proceedings of the SIGPLAN symposium on Languages for system implementation Oct, 1971: 20-28.
* Storm, Mark W., and Polk, Jim A. "Usage of an XPL Based Compiler Generator System" Proceedings of the 14th annual ACM Southeast Regional Conference April 1976: 19-26.
* Wortman, D. B
"A roster of XPL implementations."ACM SIGPLAN Notices January 1978: 70-74.
See also
*
PL/M
Notes
References
* McKeeman, William Marshall; Horning, James J.; and Wortman, David B., ''A Compiler Generator'' (1971), {{ISBN, 978-0-13-155077-3. The definitive reference, including source code of all components of the XPL system.
External links
University of Toronto XPL Home PageThe XPL Programming Language''A Compiler Generator'' page at Amazon.comScientific XPL for New England Digital Corporation's ABLE Series Computers
PL/I programming language family
Systems programming languages
Procedural programming languages
Structured programming languages
Programming languages created in 1967
Programming languages