00100	.BEGIN CENTER
00200	MULTI-COMPUTER IMPLEMENTATION OF PROGRAMMING LANGUAGES
00300	.END
00400	.SKIP 4
00500	One of the most important advantages of high-level programming
00600	languages is inter-machine transferability.  The need to execute a
00700	single program on different kinds of computers arises traditionally
00800	in two circumstances: either someone with one machine wants to use a
00900	program written for another machine, or an old computer model is
01000	replaced by a newer one and reprogramming of old software is to be
01100	avoided.  With the advent of computer networks comes a third reason
01200	for transferability: if programs can be assigned to arbitrary
01300	machines in the network, the workload can be distributed more
01400	effectively.
01500	
01600	Unfortunately, the use of a high-level language does not guarantee
01700	inter-machine transferability.  Some incompatibilities are difficult
01800	to overcome, such as differences in hardware speed, memory capacity,
01900	and arithmetic precision.  However, most incompatibilities are due to
02000	implementation differences.  Even where language standards exist, it
02100	is rare to find compatible implementations.
02200	
02300	Implementation differences fall roughly into three categories:
02400	omissions, extensions, and discrepancies.  Omission of the more
02500	complex features of a standard language is often expedient,
02600	especially on smaller machines.  Extensions are often made to take
02700	advantage of unusual hardware facilities or to meet special local
02800	needs.  Discrepancies usually arise from differing interpretations of
02900	the defining standard as a result of vague and ambiguous
03000	specifications.  Sometimes discrepancies are due to bugs in the
03100	implementations.
03200	
03300	Language standards alone have been unable to assure program
03400	transferability.  What is needed are ↓_implementation standards_↓.
03500	
03600	It is a widely accepted premise that the most precise definition of a
03700	programming language is its compiler.  Standards committees should
03800	publish not only a formal definition of a language but also a
03900	standard compiler and library for it.  Adoption of the standard
04000	implementation would assure consistency and save considerable
04100	compiler development expense as well.
04200	
04300	A standards committee should not dissolve after its language is
04400	published, but should maintain an active involvement in the use of
04500	its product.  Channels of communication must be available for
04600	individual installations to share experiences and for the
04700	distribution of improvements and corrections to the implementation.
04800	
04900	Several problems are introduced by the use of implementation
05000	standards.  Formalizations must be chosen for the definition of the
05100	compiler and of the library.  Provisions must be made for extending
05200	the language without destroying implementation consistency.
05300	Reasonable efficiency must be maintained for the single
05400	implementation on a variety of systems.
05500	
05600	One approach to the solution of these problems is a universal
05700	compiler generator, available on every computer.  The implementation
05800	standard of a new language is fed in and an implementation spews
05900	forth.  Unfortunately, it is difficult to design a single generator
06000	that can handle any language, including languages not yet conceived.
06100	
06200	A different approach is to generate many implementations of one
06300	language from a single machine.  Thus, one implementation
06400	generator needs to be written and maintained for each language.  To
06500	produce a system for a new computer, the machine language and
06600	assembler conventions of that machine are taught to the generator and
06700	it produces an assembly language tape that can be assembled and
06800	loaded on the object machine.
06900	
07000	The latter approach is being taken by the group developing LISP70 at
07100	Stanford University (Enea, Smith, and Tesler).  In addition to a
07200	language definition, they are producing a standard implementation and
07300	an implementation generator.  The generator will run on a PDP-10 and
07400	produce LISP70 systems for other computers.
07500	
07600	A LISP70 system consists of a compiler and a library.  The library
07700	is a set of algorithms coded in LISP70 itself.  The compiler
07800	is embodied in a set of tables that are in human-readable form.
07900	Each table consists of a set of rewrite rules of the form A→B,
08000	which replaces an input matching pattern A by an output based
08100	on pattern B.  The patterns usually contain variables, signified
08200	by a colon and an identifier, e.g., ":X".  They often contain
08300	constants, list-forming parentheses, subroutine calls on other tables,
08400	and various special facilities.
08500	
08600	Each table of rewrite rules is translated to high-speed machine language
08700	code, optimized in various ways.  Thus there is no interpreter as
08800	is usually required in table-driven compilers.  The compiled code
08900	calls intrinsic routines to process the input and output streams
09000	and to backtrack when necessary.
09100	
09200	The most important tables in the LISP70 compiler are:
09300	.B
09400	EXPRESSION.  Translates Algol-like M-notation to fully parenthesized
09500	S-notation.
09600	
09700	COMPILER.  Translates S-notation to the machine language of an ideal
09800	LISP machine (similar to a Burroughs 5500).
09900	
10000	ML.  Translates the pseudo-machine language to the object machine
10100	assembly language.
10200	.E
10300	For example, the rewrite rule within the EXPRESSION table that translates
10400	ALGOL "if" to LISP "COND" is:
10500	.B
10600	if <expression>:X then <expression>:Y else <expression>:z
10700	→ (COND (:X :Y) (T :Z))
10800	.E
10900	which would translate:
11000	.B
11100	if a < 0 then 4 else NIL
11200	.E
11300	to:
11400	.B
11500	(COND ((LESSP A 0) 4) (T NIL))
11600	.E
11700	where "a < 0" is translated to "(LESSP A 0)" by a subroutine call on
11800	<expression> whose result is bound to the variable X.
11900	
12000	To generate an implementation of LISP70 for a new computer,
12100	its ML tables will
12200	be coded.  For a first version, where efficiency is of secondary
12300	importance, this should be a few hours work with the
12400	assistance of an implementation guidebook.  Then all the tables will
12500	be fed into the generator running on the PDP-10, and it will produce
12600	a system for the new computer.
12700	
12800	Naturally, errors will arise during the above procedure, and will be
12900	discovered when the system is tested on the new computer.  Correction
13000	and repetition of the procedure will be required until a satisfactory
13100	system is produced.
13200	
13300	The implementation generator is itself a LISP70 program and the
13400	tables are coded in a subset of the LISP70 language.  Therefore any
13500	computer with a LISP70 system can generate implementations.
13600	This capability provides an important first test of the correctness
13700	of a new system.  When fed the tables which were used to generate it,
13800	it should output an assembly language tape identical to the one which
13900	produced it.
14000	
14100	Ideally, all LISP70 implementations will be generated at a central
14200	location.  Centralization should help to create efficient channels of
14300	communication so that bugs can be corrected quickly in all
14400	implementations.
14500	
14600	The problem of language extensions is dealt with in LISP70 by making
14700	it an extensible language.  Additions can be made in various ways by
14800	high level statements, but ultimately they are achieved by extending
14900	the compiler tables.  If a program utilizes certain language
15000	extensions, they are considered part of the program text and are
15100	automatically made to any implementation during the compilation of
15200	that program.  An exception to this situation is any addition to the
15300	ML tables, which must be rewritten for each computer.
15400	
15500	LISP70 is being implemented initially on the Stanford PDP-10.  It is
15600	planned to put it next on other computers of the ARPA network.  The
15700	developers hope that experience with its multi-computer
15800	implementation will test the value of implementation standards to
15900	achieve these three goals: rapid development of compilers;
16000	transferable programs; more effective utilization of computer
16100	networks.