View source for XPL

{{Short description|Dialect of the PL/I programming language}}
{{About|a dialect of the PL/I programming language|the meaning of the term and other uses}}
'''XPL''', for '''expert's programming language'''<ref> {{cite journal
 |first=John |last=Slimick
 |title=Current Systems Implementation Languages: One User's View
 |journal=ACM SIGPLAN Notices
 |date=October 1971
 |volume=6 |issue=9
 |pages=20-28
 |doi=10.1145/942596.807056
 |url=http://www.bitsavers.org/pdf/stanford/sail/STAN-CS-76-574_SAIL_Aug76.pdf
}}</ref> 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.

XPL was designed and implemented by [[William M. McKeeman]],<ref name="Shustek_2016">{{cite web |url=http://www.computerhistory.org/atchm/in-his-own-words-gary-kildall/ |title=In His Own Words: Gary Kildall |author-first=Len |author-last=Shustek |date=2016-08-02 |work=Remarkable People |publisher=[[Computer History Museum]]}}</ref><ref name="Kildall_1993">{{cite web |orig-year=1993 |date=2016-08-02 |title=Computer Connections: People, Places, and Events in the Evolution of the Personal Computer Industry |author-first=Gary Arlen |author-last=Kildall |author-link=Gary Arlen Kildall |editor-first1=Scott |editor-last1=Kildall |editor-link=Scott Kildall |editor-first2=Kristin |editor-last2=Kildall |publisher=Kildall Family |type=Manuscript, part 1 |url=https://d1yx3ys82bpsa0.cloudfront.net/kildall-p.1-78-publishable-lowres.pdf |access-date=2016-11-17 |archive-url=https://web.archive.org/web/20200624231947/https://d1yx3ys82bpsa0.cloudfront.net/kildall-p.1-78-publishable-lowres.pdf |archive-date=2020-06-24 |url-status=live}}</ref> [[David Wortman|David B. Wortman]], [[Jim Horning|James J. Horning]] and others at [[Stanford University]]. XPL was first announced at the 1968 [[Fall Joint Computer Conference]].  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 (computing)|translator]] 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]], 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 (computer science)|STRING]] datatype with dynamic lengths.  String values live in a separate text-only [[heap (data structure)|heap]] memory space with automatic [[garbage collection (computer science)|garbage collection]] 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 (compiler)|code generation]] techniques. Versions of XCOM exist for different [[Instruction set|machine architectures]], using different hand-written code generation modules for those targets. The original target was [[IBM System/360]], which is a proper subset of [[IBM System/370]], [[IBM System/390]] 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 (programming language)|C]], [[LISP]], and [[Java (programming language)|Java]]. 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]] 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 (compilers)|bootstrapping]] the compiler.  The authors of XPL invented the [[tombstone diagram]] or T-diagram to document the bootstrapping process.

[[Retargeting]] 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]]. 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 analysis|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]] 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 parsing|top-down]] 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 almost 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 [[History of IBM magnetic disk drives#IBM 2311|IBM 2311]]s.  An XMON parameter FILE= enabled the monitor to efficiently use other disks with larger block sizes.<ref>A Compiler Generator page 251</ref>  The working disk block size was also a compile-time constant in
XCOM.<ref>A Compiler Generator, page 372</ref>

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.<ref>A Compiler Generator Appendix A1,7</ref>

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 [[Execute Direct Access Program|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]] and [[z/OS]], generally without any changes.

==Parsing==
XCOM originally used a now-obsolete bottom-up parse table method called ''[[Shift-reduce parser#MSP|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]] 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.<ref group="nb">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]] microcomputer which had only 48 kilobytes of internal memory ([[DRAM]]) and only 100 kilobytes of external memory ([[floppy disk]]) running under [[CP/M]]. This version was completed in 1980. Porting to MacOS (9, later X) was subsequently completed.</ref>  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]] subsequently changed XCOM and XA to instead use a variant of [[Donald Knuth]]'s [[LR parser]] bottom-up method.<ref group="nb">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.</ref>  XCOM's variant is called [[SLR parser|Simple LR]] or SLR.  It handles more grammars than MSP but not quite as many grammars as [[LALR]] 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]] 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 (computing)|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]], the language used for the Space Shuttle program<ref>{{Cite web|url=https://www.cs.toronto.edu/XPL/hal.html|title=The Development of Hal/S|website=Department of Computer Science, University of Toronto}}</ref>
* [[MALUS]], a [[system programming language]] used by General Motors to develop their [[Multiple Console Time Sharing System]]
* [[New England Digital]] 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]] port was done in 2000,<ref>{{cite web|last1=Bodenstab|first1=Dave|title=Dave Bodenstab's Home Page (archived)|url=http://www.bodenstab.org/|access-date=Sep 13, 2024|archive-date=April 24, 2021|archive-url=https://web.archive.org/web/20210424004152/http://www.bodenstab.org/|url-status=bot: unknown}}</ref> an x86/[[Linux]] port in 2015, and an XPL to C translator in 2017.<ref>{{cite web |url=https://sourceforge.net/projects/xpl-compiler/ |title=XPL compiler: XPL to C translator |last=Weaver |first=Daniel E. |date=November 21, 2017 |website=[[SourceForge]] |publisher=[[Slashdot]] Media |location=[[La Jolla]], CA |access-date=December 6, 2017}}</ref><ref>{{cite newsgroup |title=Announcing the initial release of an XPL Compiler |author=shoefoot (Daniel E. Weaver) |newsgroup=comp.compilers |date=November 21, 2017 |url=https://compilers.iecc.com/comparch/article/17-11-001 |access-date=December 6, 2017 |message-id=17-11-001@comp.compilers}}</ref>

== 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. [https://web.archive.org/web/20120610080129/http://home.roadrunner.com/~pflass/XPL/roster.html "A roster of XPL implementations."] ACM SIGPLAN Notices January 1978: 70-74.

==See also==
* [[PL/M]]

==Notes==
{{Reflist|group="nb"}}

==References==
{{Reflist}}
* 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==
* [http://www.cs.toronto.edu/XPL/ University of Toronto XPL Home Page]
* [http://TeamPLI.net/XPL/ The XPL Programming Language]
* [https://www.amazon.com/Compiler-Generator-Automatic-Computation-McKeeman/dp/0131550772/ref=sr_1_1?s=books&ie=UTF8&qid=1359838077&sr=1-1&keywords=compiler+generator ''A Compiler Generator'' page at Amazon.com]
* [https://books.google.com/books?id=NuQFtwAACAAJ Scientific XPL for New England Digital Corporation's ABLE Series Computers]

[[Category:PL/I programming language family]]
[[Category:Systems programming languages]]
[[Category:Procedural programming languages]]
[[Category:Structured programming languages]]
[[Category:Programming languages created in 1967]]
[[Category:Programming languages]]