perm filename MULTI.PUB[L70,TES] blob sn#009954
filedate 1972-08-29 generic text, type T, neo UTF8
00100 .BEGIN CENTER
00200 MULTI-COMPUTER IMPLEMENTATION OF PROGRAMMING LANGUAGES
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
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.
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
03300 Language standards alone have been unable to assure program
03400 transferability. What is needed are ↓_implementation standards_↓.
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.
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.
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.
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.
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.
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.
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.
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.
09200 The most important tables in the LISP70 compiler are:
09400 EXPRESSION. Translates Algol-like M-notation to fully parenthesized
09700 COMPILER. Translates S-notation to the machine language of an ideal
09800 LISP machine (similar to a Burroughs 5500).
10000 ML. Translates the pseudo-machine language to the object machine
10100 assembly language.
10300 For example, the rewrite rule within the EXPRESSION table that translates
10400 ALGOL "if" to LISP "COND" is:
10600 if <expression>:X then <expression>:Y else <expression>:z
10700 → (COND (:X :Y) (T :Z))
10900 which would translate:
11100 if a < 0 then 4 else NIL
11500 (COND ((LESSP A 0) 4) (T NIL))
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.
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.
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.
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.
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
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.
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