UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The implementation of BCPL on a microcomputer Hayter, Ronald Stewart 1983

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1983_A6_7 H39.pdf [ 3.67MB ]
Metadata
JSON: 831-1.0051848.json
JSON-LD: 831-1.0051848-ld.json
RDF/XML (Pretty): 831-1.0051848-rdf.xml
RDF/JSON: 831-1.0051848-rdf.json
Turtle: 831-1.0051848-turtle.txt
N-Triples: 831-1.0051848-rdf-ntriples.txt
Original Record: 831-1.0051848-source.json
Full Text
831-1.0051848-fulltext.txt
Citation
831-1.0051848.ris

Full Text

THE IMPLEMENTATION OF BCPL ON A MICROCOMPUTER By RONALD STEWART HAYTER B . S c , The U n i v e r s i t y o f B r i t i s h C o l u m b i a , 1978 A THESIS SUBMITTED I N PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES ( D e p a r t m e n t o f Computer S c i e n c e ) We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d THE UNIVERSITY OF B R I T I S H COLUMBIA O c t o b e r 1983 R o n a l d S t e w a r t H a y t e r , 1983 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y a v a i l a b l e f o r reference and study. I further agree that permission for extensive copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the head of my department or by h i s or her representatives. I t i s understood that copying or pub l i c a t i o n of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of Co^>u-f-<e*r" "SoV^ g-^ og The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date m ^ , C M - *4 DE-6 (3/81) i i Abstract BCPL/Z80 i s a complete system f o r the development of BCPL programs. I t runs on a microcomputer based on the Z i l o g Z80 processor and c o n s i s t s of a number of independent programs c o o r d i n a t e d by an o p e r a t i n g system. Among these programs are in c l u d e d an e d i t o r , a compiler, and a te x t formatter, a l l of which were designed f o r use on computers both f a s t e r and l a r g e r than an 8 - b i t machine. The l i m i t e d resources of a microcomputer made implementation of a stand-alone program development system f o r a h i g h - l e v e l language c h a l l e n g i n g . T h i s document d e s c r i b e s how t h i s task was accomplished. i i i Table of Contents Chapter Page 1 . Introduction 1 2. Background 3 8-Bit Program Development Systems 3 BCPL on Microcomputers 4 SLIM Intermediate Machine 6 Zilog Z80 Processor 9 3. Overview of BCPL/Z80 11 Operating System 11 Program Development 12 F i l e System .12 Hardware 13 4. Implementation Issues 15 Operating System 15 Run-Time Library 17 Program Development F a c i l i t i e s 18 Interpretation vs Translation 20 5. The F i r s t SLIM Interpreter 23 Instruction Interpretation. 23 Traps 24 Input/Output 25 Performance 26 6. TC1: SLIM Threaded Code, Version 1 28 Threaded Code 28 UCSD p-code 29 Threaded SLIM 30 Inner Loop 32 Improving Size and Speed 33 Stati c vs Dynamic Frequencies.. 34 Input/Output 36 7. TC2: SLIM Threaded Code, Version 2..'. 37 Library Routines 37 Peephole Optimization 38 TC2 Instruction Set 41 Effectiveness of the Improver 44 Input/Output 44 8. Results 47 Benchmarks 47 iv 9. Conclusions 51 Bibliography 53 Appendix A: TC2 Code Improvement Rules.' ..55 Appendix B: TC2 Instruction Encodings 56 Appendix C: BCPL/Z80 User's Manual ..59 V Acknowledgement I would l i k e to thank John Peck, my supervisor, for - his guidance and our many long discussions, and Harvey Abramson for his comments on this document. I am also indebted to the authors of some of the programs incorporated into BCPL/Z80: J E L Peck (the compiler, the CHEF editor, the DORIS formatter), M A Maclean (CHEF), J D Dyment (DORIS), M Richards (the compiler), and a large number of others (the compiler). 1 J_. I n t r o d u c t i o n A program development system i s the set of programs needed f o r d e veloping programs i n a h i g h - l e v e l language. Normally t h i s set of programs runs on a p a r t i c u l a r computer under some op e r a t i n g system. At a minimum, t h i s set i n c l u d e s : a tex t e d i t o r , f o r composing and c o r r e c t i n g programs and f o r w r i t i n g documentation; and e i t h e r (depending on the h i g h - l e v e l language) a compiler, f o r t r a n s l a t i n g programs i n t o executable form, or an i n t e r p r e t e r , f o r executing programs. A l s o sometimes i n c l u d e d are a few u t i l i t i e s : a t e x t formatter, f o r a r r a n g i n g documentation on p r i n t e d pages; a l i n k e r , f o r combining the s e p a r a t e l y - c o m p i l e d p a r t s of a program; a debugger, f o r t e s t i n g programs and determining the cause of e r r o r s ; a p r o f i l e r , f o r l o c a t i n g b o t t l e n e c k s i n the execution of a program; and perhaps a code o p t i m i z e r , f o r improving the s i z e and speed of programs a u t o m a t i c a l l y . BCPL/Z80 i s such a program development system, running on a Z80-based microcomputer. Chapter 2 p r o v i d e s background f o r the work on BCPL/Z80. I t d e s c r i b e s a number of program development systems f o r microcomputers. One such system, the UCSD p-System, i s used as a y a r d s t i c k f o r comparison with BCPL/Z80 throughout t h i s document. A l s o d e s c r i b e d are two implementations of BCPL f o r the Z80, the SLIM intermediate language (a c e n t r a l element i n a number of BCPL 2 i m p l e m e n t a t i o n s a t the U n i v e r s i t y of B r i t i s h Columbia, i n c l u d i n g BCPL/Z80), and the Z80 p r o c e s s o r . Chapter 3 g i v e s a b r i e f d e s c r i p t i o n of the BCPL/Z80 hardware and s o f t w a r e . Chapter 4 d i s c u s s e s a number of i m p o r t a n t i m p l e m e n t a t i o n i s s u e s w h i c h were r e s o l v e d d u r i n g the development of BCPL/Z80. In p a r t i c u l a r , the reasons f o r c h o o s i n g t o i n t e r p r e t c o m p i l e d code r a t h e r than t r a n s l a t e i t t o Z80 code a r e g i v e n . The next t h r e e c h a p t e r s d e s c r i b e the t h r e e s u c c e s s i v e g e n e r a t i o n s of the i n t e r p r e t e r used i n BCPL/Z80. Chapter 8 compares the performance of BCPL/Z80 w i t h o t h e r systems. Chapter 9 c o n t a i n s some c o n c l u d i n g remarks. I n c l u d e d as an appendix i s the u s e r ' s manual f o r the system. 3 2. Background In t h i s chapter, a number of program development systems are b r i e f l y d e s c r i b e d . A f t e r t h i s , s e v e r a l implementations of BCPL are examined. F i n a l l y , the SLIM intermediate machine and the Z i l o g Z80 processor are d e s c r i b e d . 8-Bit Program Development Systems In the world of 8-bit microcomputers, there are a number of program development systems f o r h i g h - l e v e l languages a v a i l a b l e commercially. U n f o r t u n a t e l y , l i t t l e has been p u b l i s h e d about them. A number of these systems are based on the popular CP/M o p e r a t i n g system from D i g i t a l Research [ K i l d 8 l ] . CP/M i s not a p l e a s a n t system f o r naive users but, being one of the f i r s t a v a i l a b l e , much software has been w r i t t e n f o r i t . From v a r i o u s software houses are a v a i l a b l e powerful f u l l - s c r e e n e d i t o r s as w e l l as c o m p i l e r s f o r many h i g h - l e v e l languages, i n c l u d i n g P a s c a l , C, and PL/I. Most compilers produce n a t i v e machine code, u s u a l l y f o r the I n t e l 8080 p r o c e s s o r . Some compilers a l s o emit intermediate code meant for i n t e r p r e t a t i o n ; by doing so, compile time i s shortened d u r i n g the e a r l y debugging stages when the 4 slower speed of program execution is unimportant. Another program development system i s the UCSD p-System [Over80], developed at the University of C a l i f o r n i a at San Diego. It i s available for a wide range of 8- and 16-bit machines. The p-System i s an easy-to-use system for developing Pascal programs, although compilers are also available for FORTRAN, COBOL, BASIC, and Modula-2. The full-screen editor, the compiler, and a number of u t i l i t i e s are a l l integrated into an exceptionally pleasant package. The p-System compiler produces intermediate p-code which i s then interpreted. The lat e s t version of the p-System (version IV.1) also allows p-code to be translated into native machine code. BCPL on Microcomputers The language BCPL has been implemented on many computers of a l l sizes. One reason for i t s being so widespread i s i t s portable compiler [Rich7l], This compiler produces code for an intermediate (hypothetical) machine: either OCODE or INTCODE. Programs in the form of, say, OCODE can be e a s i l y transported by writing an OCODE interpreter on the new machine. In p a r t i c u l a r , the compiler, which i s written in BCPL, can be transported in t h i s way. For most machines, however, this method of transporting 5 programs i s used only for bootstrapping, since interpreted programs generally run much slower than those translated to the native machine code. Once the compiler, in OCODE form, i s running on the new machine, a translator from OCODE to the native code is usually written. By t h i s use of an intermediate machine code, BCPL can be implemented on a new machine by writing only an interpreter and a t r a n s l a t o r — u s u a l l y much less work than writing a whole compiler. Recently, BCPL was implemented on a Z80-based microcomputer under CP/M by Cowderoy and Wall i s [Cowd82]. They wrote an OCODE interpreter and transported the compiler to their machine. They did not, however, write a translator, apparently because of the limited memory (36 Kbytes) in th e i r machine. Their compiler i s 12 Kbytes of OCODE, but i t i s 19.5 Kbytes when translated into PDP-11 code; presumably i t would be even larger i f translated to Z80 code. Rather than red.uce the amount of .memory l e f t for the symbol table and the parse tree, they accepted a slower compilation speed. They mentioned that their interpreted BCPL compiler on the Z80 i s a factor of 8 slower than the directly-executed PDP-11 version. Unfortunately, they neglected to mention which model of PDP-11 they used. BCPL CINTCODE, by Richards Computer Products [RCP81], also runs under CP/M. Their compiler produces a compact form of INTCODE rather than OCODE, but their system is also interpreted, not translated into native machine code. BCPL CINTCODE i s a more 6 ambitious implementation than that of Cowderoy and Wallis, including not only a compiler and an interpreter but also a number of u t i l i t y programs, debugging aids, and support for overlays and multi-tasking. Although the l i t e r a t u r e describing BCPL CINTCODE does not include any quantitative performance figures, a few comparisons are given: A t y p i c a l BCPL program in CINTCODE requires about a t h i r d of the storage of f u l l y compiled Z80 code. and: BCPL CINTCODE i s s i g n i f i c a n t l y more compact than UCSD Pascal, and runs faster. SLIM Intermediate Machine As mentioned above, most BCPL compilers produce either OCODE or INTCODE as their intermediate code. One exception i s a compiler written at the University of B r i t i s h Columbia. This compiler produces an intermediate code c a l l e d SLIM [Peck83]. The SLIM machine i s a hypothetical one, s p e c i f i c a l l y designed for compiling BCPL. It has an accumulator, a stack, and a number of special-purpose r e g i s t e r s . The program counter (C-) register points to the next SLIM 7 instruction to be executed. It i s incremented as each instruction i s executed but i t i s also changed by the 'jump' ( J ) , 'jump i f true' (T), 'jump i f fa l s e ' (F), ' c a l l ' (C), and 'return' (R) instructions. The environment (E-) register points into the stack to the parameters and l o c a l variables of a procedure; the parameters are at negative offsets from the E-register, while the l o c a l variables are at positive o f f s e t s . It is modified by the ' c a l l ' (C) and 'return' (R) instructions. The high-point (H-) register points to the current top of the stack. It i s incremented by the 'push' (P), and 'push then load' (PL) instructions, and changed by the 'modify high-point' (M), ' c a l l ' (C), and 'return' (R) instructions. The global (G-) register points to the base of a vector of c e l l s for BCPL global variables. (The other two registers, the stack l i m i t (S-) and interrupt (N-) r e g i s t e r s , are not important to this discussion.) Most SLIM instructions i m p l i c i t l y involve the accumulator, and most of these also e x p l i c i t l y involve an operand. For example, in the following sequence of instructions: LIE1 +5 SG101 8 the 'load' (L) instruction loads a value into the accumulator from the f i r s t l o c a l variable of the current procedure, then the 'add' (+) instruction adds f i v e to the accumulator, and f i n a l l y the 'store' (S) instruction stores the accumulator in global c e l l 101. SLIM has been used to transport BCPL to several machines, ranging in size from an Amdahl 470 to a Data General Nova and, recently, to a 16-bit microcomputer based on the Intel 8088 processor. In a l l of these implementations, SLIM was translated into the native machine code. Because SLIM was designed for the representation of compiled BCPL programs rather than as the instruction set of a real machine, the encoding of SLIM instructions as b i t patterns i s not defined. Such an encoding for a 16-bit machine has been suggested (chapter 10 of [Peck83]) and i t was used in a microprogrammed implementation of SLIM. This scheme encodes a SLIM instruction as either one or two 16-bit words. It i s designed so that the instructions that are encountered most frequently (those with operands which are small constants or small o f f s e t s from base registers) require only one word to encode. Relatively few instructions require two words. Although t h i s encoding for SLIM has been suggested, an implementor i s free to choose other encodings. 9 Ziloq Z80 Processor The Zilog Z80 [Zilo76] is an 8 - b i t microprocessor. It i s a superset of the e a r l i e r (and once very popular) Int e l 8080 . Because the Z80 i s a superset, i t has surpassed the 8080 in popularity. However, i t has inherited an awkward architecture and, despite i t s new instructions, the instruction set i s incomplete. The Z80. has three 16-bit general-purpose registers (BC, DE, and HL) which a l t e r n a t i v e l y may be used as six 8-bit registers (B, C, D, E, H, and L ) . It also has an 8 - b i t accumulator (A), and a number of other special-purpose re g i s t e r s , including a program counter (PC), a stack pointer (SP), a pair of index registers (IX and IY), and a flags register (F) for condition codes. Ten d i f f e r e n t addressing modes are defined. Unfortunately, there are many r e s t r i c t i o n s placed on t h e i r use. Not a l l registers may be used with some modes, and most instructions allow only certain modes to be used. As a r e s u l t , A and HL are the most useful registers and data must often be transferred between these registers and the others. Most arithmetic and l o g i c a l instructions involve the accumulator i m p l i c i t l y . Some of the operations available are: • 10 add, subtract, increment, decrement, compare, and, inclusive-or, exclusive-or, s h i f t , rotate, set b i t , reset b i t , and test b i t . As well as these 8-bit operations, a few 16-bit ones are also available: add, subtract, increment, and decrement. Data can be transferred between reg i s t e r s , or between registers and memory, either 8 or 16 b i t s at a time, by the 'load' (LD) in s t r u c t i o n . Because of addressing mode r e s t r i c t i o n s , however, i t is often necessary when tranferring data between registers to use memory temporarily. The program counter i s changed by the 'jump' (JP and JR), ' c a l l ' (CALL) and 'return' (RET) instructions. Jumps may be re l a t i v e to the current PC (JR) or to absolute memory locations (JP); c a l l s can only be to absolute locations. The PC i s pushed on the stack by a c a l l and popped by a return. There i s no addressing mode which e a s i l y allows an ar b i t r a r y word in the stack to be referenced; only the topmost word may be accessed, by 'push' and 'pop'. 11 3. Overview of BCPL/Z80 BCPL/Z80 is a self-contained program development system consisting of an operating system, a number of independent u t i l i t y programs, and a f i l e system. This chapter gives an overview of the f a c i l i t i e s a v a i l a b l e . The use of BCPL/Z80 i s described more f u l l y in the user's manual [Hayt83] in Appendix C. Operating System A program c a l l e d the Shell allows the user to run any of the u t i l i t y programs or any of the user's own. The user can select the p a r t i c u l a r u t i l i t y from a menu of choices simply by typing a single l e t t e r . Programs normally have their standard input and output directed to the console. However, l i k e the s h e l l of UNIX [Ritc78], the BCPL/Z80 Shell allows them to be redirected to f i l e s . A subsystem of the Shell i s c a l l e d the F i l e r . The F i l e r i s used for manipulating f i l e s : l i s t i n g , renaming, and destroying f i l e s , and moving f i l e s from one disk to another. I t , too, i s menu-driven. 12 Program Development Programs and documents may be composed and modified with the aid of the Editor. It includes the many features found in most large-system line-oriented editors, but also allows full-screen e d i t i n g . The Compiler translates BCPL programs into SLIM assembly language. These SLIM programs usually can be made smaller and faster by the Improver. The Encoder translates SLIM assembly language programs • into executable code. The separately-compiled sections of a program are merged by the Linker. F i n a l l y , the Formatter prepares documents for prin t i n g . F i l e System The BCPL/Z80 f i l e system i s organized as a two-level hierarchy. In the f i r s t l e v e l are two kinds of volumes: character and block. Typical character volumes are the keyboard, the screen, the printer, and the modem. Reading from or writing to a character volume i s done one character at a time. The character volumes are known by the names "CONSOLE:" (the keyboard and the screen), "PRINTER:" (the p r i n t e r ) , and "REMOTE:" (the modem). Block volumes are disks and, for these, information i s 13 transferred in blocks of 512 bytes at a time. The names of block volumes are chosen by the user at the time that a disk i s i n i t i a l i z e d . Block volumes are structured objects, subdivided into f i l e s (the second l e v e l in the hierarchy) and a directory. Just as with character volumes, characters may be read from or written to f i l e s one character at a time. F i l e names are, of course, chosen by the user. Volume and f i l e names are used for opening streams to character volumes or f i l e s . For example, an input stream from the modem may be established by c a l l i n g 'Findlnput': Findlnput ("remote:") Si m i l a r l y , an output stream may be set up to a f i l e named "OUT.TEXT" on the disk "WORK:" by c a l l i n g 'FindOutput': FindOutput ("work:out.text") Hardware BCPL/Z80 was developed on an Exidy Sorcerer microcomputer having a 2.1 MHz Z80 processor and 55 Kbytes of memory. The computer has a b u i l t - i n keyboard and memory-mapped video screen, as well as both printer and modem interfaces. Attached to the computer i s a North Star mini-floppy disk system consisting of 1 4 two double-density drives, with a combined capacity of 350 Kbytes. 1 5 4. Implementat ion Issues In implementing something as large as a program development system for a high-level language, many issues must be resolved. This chapter discusses how they were resolved for BCPL/Z80. Operating System Much of the early development of BCPL/Z80 was done using the UCSD p-System (version 1.5). Superb as i t i s as a program development system, the p-System was judged to be unsuitable as a host for BCPL/Z80 for several reasons. The p-System occupies about one-third of memory, leaving only 40 Kbytes for user programs. Also, the f i l e system cannot be accessed by a Z80 assembly program; a l l f i l e manipulation must be done by Pascal code. The only other operating system available was a primitive one c a l l e d the North Star Disk Operating System (DOS). DOS i s much smaller than the p-System: only 4 Kbytes. It does have an assembly language interface to i t s f i l e system but the f i l e system i t s e l f i s very crude compared to that of the p-System. In fact, i t consists of only three procedures: one to read a disk directory and locate a f i l e name in i t , another to write a 16 d i r e c t o r y back on the d i s k , and the l a s t to read or w r i t e a number of d i s k s e c t o r s beginning at a given s e c t o r . I t i s l e f t t o the programmer to supply procedures which a l l o c a t e space on the d i s k f o r f i l e s , open and c l o s e f i l e s , and read and w r i t e c h a r a c t e r s . DOS p r o v i d e s l i t t l e i n the way of support f o r a p p l i c a t i o n programs and, f o r t h i s reason, i t too was r e j e c t e d . A f t e r the a v a i l a b l e o p e r a t i n g systems were r e j e c t e d , i t was decided to w r i t e a new one i n BCPL. T h i s simple o p e r a t i n g system i s f o r a s i n g l e user, and i s very s i m i l a r to the p-System. I t was not only modelled a f t e r the .p-System, but i t a l s o has compatible d i s k d i r e c t o r y and f i l e s t r u c t u r e s . T h i s c o m p a t i b i l i t y was p a r t i c u l a r l y important before BCPL/Z80 had a f u l l - s c r e e n e d i t o r . Because of i t , f o r example, programs c o u l d be composed using the p-System e d i t o r and compiled with the BCPL/Z80 Compiler. UNIX was another i n f l u e n c e on the design of the BCPL/Z80 o p e r a t i n g system. The S h e l l s of both systems are simply user programs (although r a t h e r s o p h i s t i c a t e d user programs) and so may be r e p l a c e d with others i f d e s i r e d . The other u s e f u l idea borrowed from UNIX i s that of the r e d i r e c t i o n of the standard input and output of a program. R e d i r e c t i o n i s not p o s s i b l e i n the e a r l y v e r s i o n s of the p-System, but t h i s d e f i c i e n c y has been c o r r e c t e d i n the l a t e s t v e r s i o n . Another p o s s i b l e host f o r BCPL/Z80 might have been CP/M. I t 17 i s almost as small as DOS and yet i t has the extensive f i l e system interface that DOS lacks. When a decision had to be made, however, this operating system was not available for the computer used. Although CP/M i s now available, the BCPL/Z80 operating system works well and i s easier to use. Adapting BCPL/Z80 to run under CP/M would l i k e l y be a serious undertaking, but i t might be attempted in the future. Run-Time Library One of the distinguishing c h a r a c t e r i s t i c s of BCPL i s that i t i s a small language. Many of the f a c i l i t i e s that are b u i l t into other languages, such as input/output and storage a l l o c a t i o n , are ordinary procedures in BCPL. The proposed draft BCPL standard [Eage82] defines a large number of procedures which might be included in the run-time l i b r a r y . Many of these procedures are present in BCPL/Z80, including the following: the opening and closing of streams to f i l e s , devices, and in-memory character strings; the reading and writing of single characters or ar b i t r a r y numbers of characters; the reading and writing of formatted text; the positioning of streams to a r b i t r a r y points; several s t r i n g processing operations; the dynamic a l l o c a t i o n of memory from the stack or a heap; and the c a l l i n g of assembly language procedures. There are, in addition to these standard ones, a number of other procedures: for the 18 renaming and destroying of f i l e s ; for the positioning of the cursor on the screen of the console; and for the loading and unloading of program overlays. An optional l i b r a r y permits the use of coroutines and multi-tasking. A l l except a very few are written in BCPL rather than Z80 assembler, making implementation quick and modification easy. The BCPL/Z80 run-time l i b r a r y was also influenced by the UCSD p-System. As mentioned in the previous section, the.disk d i r e c t o r i e s and f i l e s used by BCPL/Z80 are compatible with those of the p-System. In addition, the l i b r a r y was designed to be no more machine-dependent than the p-System. The p-System runs on many d i f f e r e n t machines. It i s e a s i l y portable because i t r e l i e s on only a few machine-dependent procedures (not, of course, including the p-code interpreter which i s written in the assembly language of the processor). These procedures read or write disk sectors, and read characters from or write characters to the console, the p r i n t e r , and the modem. These I/O procedures together with code which i n i t i a l l y loads the p-System into memory are a l l that must be changed to adapt the p-System to another machine (having the same processor). BCPL/Z80 r e l i e s on these same machine-dependent procedures and so should be as portable as the p-System. However, t h i s claim has not yet been tested. 19 Program Development F a c i l i t i e s An author of a program development system for BCPL begins with a head s t a r t : BCPL was designed with p o r t a b i l i t y in mind, and a number of large and portable programs have been written in BCPL. The BCPL/SLIM compiler i s one such program. It has been transferred to a number of d i f f e r e n t machines at the University of B r i t i s h Columbia. What i s more, i t i s capable of running on machines with r e l a t i v e l y small memories. It compiles programs in a few d i s t i n c t passes and the code for each pass needs to be present in memory only during that pass. To further save memory, the i nternal form of the program (the parse tree plus the symbol table) may reside in a disk f i l e rather than in memory. The CHEF text editor [Macl8l] i s written in BCPL. It has many powerful operators (commands') including 'alter' which allows f u l l - s c r e e n e d i t i n g . CHEF was also designed to be portable [Peck8l]. Its memory requirements are modest because CHEF uses a disk f i l e to hold the text being edited. For computers with very small memories, the code for some of the less commonly-used operators can be put into overlays which are only brought into memory when needed. The DORIS text formatter [Dyme82] i s another BCPL program. It i s quite powerful yet i t i s small and easy to use. DORIS i s 20 also portable, but largely because i t uses standard BCPL and i s not big enough to require overlays or temporary disk f i l e s . With these portable programs available and working, i t was decided to use them as the heart of BCPL/Z80. Since the compiler produces a SLIM assembly language f i l e , the only missing component needed was a program to put such a f i l e into executable form: either a SLIM assembler or a SLIM-to-Z80 translator. Interpretation vs Translation Perhaps the two biggest obstacles to successfully implementing a program development system on an 8-bit microcomputer are the slow speed of the processor and the small size of the memory. BCPL/Z80 was developed on a machine with a 2.1 MHz Z80 processor and 55 Kbytes of memory. Much e f f o r t , therefore, was expended making the system small enough to f i t yet fast enough to be useful. An early (and important) decision was to interpret SLIM rather than translate i t to Z80 machine code. Two considerations decided the issue in favour of interpretation: the expected size of BCPL/Z80 programs, and the expected speed of BCPL/Z80. The more important consideration was s i z e . The BCPL compiler and the CHEF editor, the main components of BCPL/Z80, 21 are large programs. Thus i t was important to ensure that they would be small enough to f i t in memory. Using the SLIM encoding for a 16-bit machine mentioned in Chapter 2, the compiler was estimated to be 25 Kbytes long and CHEF 26 Kbytes. These estimates do not include the memory needed for data structures; each requires several thousand more bytes and both can make use of a l l available memory to improve performance. The translation of SLIM to Z80 machine code i s , in a sense, easy. SLIM i s a higher-level machine than the Z80 and so almost every SLIM instruction must be translated into many Z80 i n s t r u c t i o n s . Consequently, to keep the size of translated programs reasonable, i t i s necessary to place the Z80 instructions corresponding to most SLIM instructions into procedures. The Z80 code generated for a SLIM instruction is then (usually) a load of the operand value into a register, followed by a c a l l to the procedure implementing the in s t r u c t i o n . If t h i s simple scheme were used, a translated program would be roughly three times the size of the encoded program. For small programs, t h i s i n f l a t i o n in size could be j u s t i f i e d by the increased speed of execution. Programs as large as the compiler and CHEF, however, would simply be too large to f i t into memory. A more sophisticated algorithm might be able to translate programs into a number of bytes comparable to the 16-bit encoding, but t h i s p o s s i b i l i t y was not explored. The other consideration was speed. An interpreted program 22 i s several times slower than a translated one. However, on a microcomputer, the absolute speed of a program i s rarely important. What i s important is whether the program i s fast enough to do i t s job without annoying the user. The example provided by the UCSD p-System showed that an interpreted system could be s u f f i c i e n t l y fast. Almost the entire p-System, including both the compiler and the editor, are Pascal programs translated to p-code and interpreted. The speed of these programs i s impressive and c e r t a i n l y adequate. Together, these two considerations lead to writing a SLIM interpreter for BCPL/Z80. A goal has been to equal (or surpass) the small size and high speed of the p-System. The next three chapters d e t a i l the pursuit of t h i s goal. 23 5. The F i r s t SLIM Interpreter The f i r s t SLIM interpreter .on the Z80 evolved considerably during i t s l i f e t i m e . O r i g i n a l l y , i t was written e n t i r e l y in UCSD Pascal. As might be expected of an interpreter which was i t s e l f being interpreted, i t was very slow. Its speed was improved by about 20 times by recoding most of i t in Z80 assembly language. It was, however, s t i l l quite slow when compared with p-code. It was eventually abandoned when i t seemed that i t s performance could not be improved except by using an e n t i r e l y d i f f e r e n t approach. Instruction Interpretation This f i r s t interpreter used the suggested encoding for a 16-bit machine. Interpretation of each instruction consisted of several steps: 1. determine the type of the operand of the instruction 2. calculate the modified operand, leaving the C-register pointing to the next instruction 3. determine the type of the opcode of the instruction 24 4. jump to the appropriate service routine 5. return to step 1. Traps Almost; a l l of the interpreter was written in assembly language. The part written in Pascal was responsible for i n i t i a l i z a t i o n and for handling exceptional circumstances. After loading a SLIM program into memory, the Pascal part c a l l e d the assembly procedure 'Execute' which interpreted SLIM instructions repeatedly. 'Execute' returned to the Pascal part, an operation known as trapping, only when something exceptional occurred. A trap could occur for a number of reasons including dividing by zero, executing an i l l e g a l i n s t r u c t i o n , overflowing the SLIM stack, referencing a bad memory address, c a l l i n g a missing global procedure, reaching a user-specified breakpoint, and executing the 'quit' i n s t r u c t i o n . Recognizing a global procedure which had not been loaded into memory was accomplished by setting a l l of the c e l l s in the SLIM global vector i n i t i a l l y to negative numbers. The c e l l s corresponding to the global procedures which were later loaded 25 would contain the addresses of the procedures, always positive numbers. Other c e l l s would remain negative. The service routine for the ' c a l l ' i nstruction checked whether the address of the c a l l e d procedure was negative and, i f so, i t caused a trap. To make i t easier to determine which p a r t i c u l a r global procedure was missing, the values i n i t i a l l y put into the c e l l s were the complements of the global c e l l numbers. When such a trap occurred, the number of the missing global procedure was then simply the complement of the C-register. Input/Output As mentioned in the previous chapter, one of the problems with using the p-System as a host operating system i s that i t provides only a Pascal interface to i t s f i l e system; f i l e s cannot be accessed from assembly language. This problem was overcome by making use of the trap for missing global procedures. For most kinds of traps, the Pascal part of the interpreter displayed the cause of the trap on the console and waited for a command to be typed. However, i f the trap was the result of a missing global procedure, and i f the missing procedure was one of a small set, the trap was treated d i f f e r e n t l y : not as an error but rather as a request. 26 I n i t i a l l y , the only procedures in t h i s set were 'RdCh' and 'WrCh'. In response to traps for these BCPL procedures, the interpreter performed the corresponding Pascal operations, 'Read' and 'Write', on the console. Later, f i l e input/output was added, with Pascal array indexes serving as BCPL stream numbers. 'Findlnput' and 'FindOutput' were mapped into 'Reset' and 'Rewrite', respectively, and both 'EndRead' and 'EndWrite' were implemented by 'Close' (a UCSD Pascal extension). 'Selectlnput', 'SelectOutput', 'Input', and 'Output' manipulated the indexes. This technique of using the trap for missing global procedures proved to be so useful that later versions of the interpreter adopted i t . When the p-System was abandoned, these traps were used as a way to give BCPL names to (a very few) procedures written in assembly language. Performance Despite the fact that most of the interpreter was written in assembly language for the sake of speed, compared to p-code t h i s interpreter was s t i l l slow: a p-code program was more than twice as fast as an equivalent SLIM program. By manually counting Z80 instructions, i t was determined that during the interpretation of some of the most common SLIM instructions (loads and stores) about half of the execution time of an instruction was spent in decoding (steps 1 and 3 above). Decoding was a time-consuming 27 procedure because the Z80 i s not well suited to extracting a r b i t r a r y groups of bi t s from a 16-bit word. Furthermore, to determine the opcode type of an instruction requires sequentially testing as many as five such groups of b i t s , and the operand type may require another two. Some speed improvement l i k e l y could have been achieved by streamlining the code of the interpreter further. However, i t was decided instead that a d i f f e r e n t encoding of the SLIM instructions might be better suited to the l i m i t a t i o n s of the Z80. The technique known as threaded code [Bell73] was t r i e d in the second SLIM interpreter with great success. Threaded code, also used in the p-code interpreter, i s described in the next chapter. 28 6. TC1 : SLIM Threaded Code, Version j _ The f i r s t SLIM interpreter based on threaded code (explained below) was c a l l e d TC1. The use of threaded code helped reduce the overhead of instruction decoding. As a r e s u l t , the i n i t i a l implementation of the threaded code interpreter was 30 per cent faster than the interpreter using the standard encoding. Fine-tuning further increased the speed of TC1 u n t i l i t was twice as fast, within 15 per cent of the speed of p-code. Threaded Code A program compiled to threaded code consists merely of a sequential l i s t of addresses, each possibly followed by data words. The addresses are those of l i b r a r y routines which perform operations such as addition, m u l t i p l i c a t i o n , function c a l l i n g , and array indexing. The data words are the (constant) arguments of the l i b r a r y routines. Interpretation of threaded code involves the following steps: 1. fetch the address which i s in the word pointed to by the program counter (PC) of the threaded code machine 2. increment the PC 29 3. jump to the l i b r a r y routine at the address just fetched 4. jump back to step 1. The f i r s t three steps form the inner loop of the interpreter and the jump of step 4 i s placed at the end of each l i b r a r y routine. On the PDP-11, the inner loop is p a r t i c u l a r l y simple; i t requires only a single i n s t r u c t i o n : NEXT: JMP @(R) + where R i s the program counter of the threaded code machine. Following an address of a l i b r a r y routine in the threaded code may be data words. Before i t jumps back to 'Next', the routine fetches these values and increments the program counter. UCSD p-code The p-code used in the UCSD p-System i s a variation of threaded code. The p r i n c i p a l difference i s that a p-code program consists of a l i s t of of f s e t s rather than addresses. These offs e t s are used in looking up in a table the addresses of the l i b r a r y routines. The advantage of this scheme i s that the l i b r a r y routines may be modified without the need for recompiling 30 a l l Pascal programs; only the table changes, not the threaded code. Since a p-code opcode i s not a machine address but rather an index into a r e l a t i v e l y small table, opcodes were defined to be single bytes, allowing 256 l i b r a r y routines. A further difference between threaded code and the p-code var i a t i o n i s that a number of opcodes have an i m p l i c i t data value. For example, the f i r s t 128 opcodes push a small integer constant (the opcode value i t s e l f ) onto the p-machine stack,; thereby avoiding the need for an e x p l i c i t data value for t h i s very common operation. Because of t h i s technique, p-code programs are very compact and they are probably faster than they would otherwise be. Threaded SLIM Reducing the overhead of instruction decoding required overcoming two bottlenecks: the extraction of groups of b i t s within a word, and the sequential testing of several values. The f i r s t problem was solved by using only whole bytes or words for both opcodes and operands, the second by performing a multi-way jump based on a single value. SLIM instructions can be divided into two classes, here c a l l e d A and B. Class A instructions take an operand and have the form: 31 <opcode> <operand> Class B instructions do not take an operand and so have the simpler form: <opcode> The 'LIEn' instruction i s an example from class A and 'R' i s one from class B. To make i t easier to encode SLIM using threaded code, class A instructions were s p l i t into two separate instructions, one to load the modified operand into a temporary work regi s t e r , the W-register, and the other to use the value in the W-register. For example, the 'LIEn' instruction i s replaced by 'WIEn' and 'LW'. (By coincidence, t h i s idea was conceived independently by another group [Macl82] at about the same time.) The new W-register instructions ('Wn', 'Win', 'WCn', 'WICn!, 'WEn', 'WIEn', 'WGn*, 'WIGn', 'WH', and 'WIH') are class C, and the instructions which take the W-register as the operand form class D. The instructions in classes B and D have no e x p l i c i t operands. Of the class C instructions, a l l but 'WH' and 'WIH' have a raw operand. To simplify decoding, an entire byte was used for each opcode. The size of SLIM programs was reduced by providing class C instructions both for raw operands which can be represented in one byte and those which need a word. In t h i s 32 way, much of the information that the e a r l i e r interpreter obtained by extracting and testing instruction f i e l d s (namely, whether the raw operand was a byte or a word, the register by which the operand was to be modified, and whether in d i r e c t i o n was to be performed) was instead i m p l i c i t l y encoded in the opcode. Decoding was thus reduced to a simple process of jumping to one of a number of l i b r a r y routines, each of which knew the form of the expected operand. This version of threaded SLIM code was quite similar to p-code. A major difference between them was that not a l l of the 256 possible values of an opcode byte were defined for SLIM. A SLIM opcode s t i l l served as an offset into a table, but instead of that table containing the l i s t of addresses of l i b r a r y routines, the table contained a l i s t of jumps to those addresses. Putting jump instructions in the table allowed the inner loop to be shorter than i t would have been otherwise. Inner Loop The size of the inner loop i s very important to the o v e r a l l speed of an interpreter. It was not possible to implement the inner loop on the Z80 as a single i n s t r u c t i o n , but i t was nonetheless quite short: NEXT: LD A,(BC) INC BC ; Fetch the opcode byte. ; Increment SLIM C-register. 33 LD LD JP H,LRPAGE L, A (HL) Calculate location in table of jump to l i b r a r y routine. Jump to that jump. After much experimentation, the BC register pair was selected as the threaded code program counter (the SLIM C-register). The table of jumps indexed by the opcode byte was located on a page (256-byte) boundary so that the address of the required jump could be formed in HL by concatenating the page number with the opcode, instead of adding the opcode to the s t a r t i n g address of the table. This inner loop uses 28 machine cycles plus 10 for the jump in the table plus a further 10 for the jump at the end of each l i b r a r y routine. Forty-eight machine cycles translate into 23 microseconds for a Z80 with a 2.1 MHz clock. Improving Size and Speed When programs were encoded using the threaded code described so far, they were about 30 per cent faster than when they were encoded conventionally. However, they were also about twice as large. A Z80 jump instruction i s three bytes long and so, using the opcode byte as an offset into the jump table, there could be at most 86 l i b r a r y routines (86 = C e i l i n g (256 div 3)). There are 10 instructions in class B (not counting '0', 'L$', and 'S$'), 18 34 in class C, and 31 in class D. I n i t i a l l y only the 59 l i b r a r y routines for these instructions were defined. Soon a f t e r , SLIM programs were made both smaller and faster by defining the 27 remaining possible l i b r a r y routines. Library routines were defined for the most common pairs of opcodes and operands; in other words, p a r t i c u l a r class A instructions were re-introduced and given opcodes. The SLIM code produced by the Compiler was analyzed so that the opcodes could be allocated to the most frequently used class A instructions. A t o t a l of over 10,000 instructions were c o l l e c t e d from a number of BCPL programs, including the Compiler i t s e l f , the CHEF editor, and the BCPL/Z80 run-time system. It was found, for example, that 10 per cent of a l l instructions were 'LIEb' (with 'b' between -8 and 247), and that 'CIGb' (with 'b' between 0 and 255) made up another 7.5 per cent. The 27 class A instructions which eventually were chosen accounted for 82 per cent of a l l instructions. A l l o c a t i n g an opcode to each, thereby saving a byte for each use, reduced the size of threaded code programs to within 15 per cent of the conventional encoding. These changes, plus some fine-tuning of the interpreter code, also brought the speed to within 20 per cent of p-code. Static vs Dynamic Frequencies The 27 c l a s s A instructions that were allocated opcodes were 35 chosen because they were the most common opcode/operand pairs in the programs analyzed. The number of times an instruction appears in a piece of code does not necessarily r e f l e c t how often i t w i l l be executed, however. As an experiment, the TC1 interpreter was modified to count the number of times each SLIM instruction was executed. Three programs were measured: the Compiler, CHEF, and DORIS. It was discovered that the instructions that were dynamically most frequent were usually those that were also s t a t i c a l l y most frequent, although there were a few exceptions. A large number of 'L@n' instructions were counted but they were not executed very frequently. The 'L@n' instruction i s most often used in two contexts: i n i t i a l i z i n g the global c e l l s associated with global procedures, and passing format strings to 'WriteF'. The programs analyzed had many global procedures but the global c e l l s are i n i t i a l i z e d only once, and the programs did not make much use of 'WriteF'. Also common to the three tests were disproportionately large numbers of executions of the '=H' and '>H' instructions. It was found that these instructions were used in both 'RdCh' and 'WrCh' for f i l e streams. A l l three programs used these procedures heavily. Selecting 27 class A instructions to optimize based on s t a t i c counts results in smaller object programs. In contrast, 36 the use of dynamic counts results in faster object programs. Except for a few anomalies, however, the two counts gave the same res u l t s : 23 of the 27 most often executed class A instructions were also among the 27 most often counted. Input/Output Shortly after the threaded code interpreter was working, the BCPL/Z80 operating system was written and i t became the new host. The only parts of the system not written in BCPL were a few simple assembly language device drivers and the interpreter i t s e l f . These device drivers were made to look l i k e BCPL procedures by using the trap for missing global procedures. When one of these drivers was c a l l e d , the interpreter intercepted the trap and c a l l e d the appropriate assembly language procedure. After the driver was finished, i t returned to 'Next'. 37 7. TC2: SLIM Threaded Code, Version 2 Despite the large improvement in speed gained by using threaded code, TCI did not quite achieve the goal of equalling the performance of the p-code interpreter. The next (and f i n a l ) interpreter, TC2, is not as r a d i c a l l y d i f f e r e n t from TC1 as TC1 was from i t s predecessor. However, TC2 is faster than the p-code interpreter and SLIM programs for i t are smaller than when the standard encoding i s used. Library Routines The performance of TC1 (both in speed of interpretation and in size of object programs) was greatly improved by using the 27 empty sl o t s in the jump table for l i b r a r y routines for class A instructions. There was not room, unfortunately, for other common opcode/operand combinations such as 'L%IEb', '<=b', or '=IEb*. One idea that was considered was to replace the jump table with an array of l i b r a r y routine addresses, as i s used in the p-code interpreter. This method would allow 128 or 256 l i b r a r y routines to be defined. The idea was rejected because the inner loop would also be considerably slower. 38 Eventually, i t was realized that one of the jump table entries could be used as an escape. The 'Escape' l i b r a r y routine is very similar to 'Next' except that the byte that follows the escape byte i s used as an index into a second jump table. The inner loop overhead for an opcode in the second table ('Next' plus 'Escape' plus three jumps) i s 83 machine cycles, or 40 microseconds. By removing the l i m i t of 86 l i b r a r y routines in TC1, i t was possible in TC2 to make a number of improvements in performance. One improvement was to move rarely executed SLIM instructions, such as '~', '==W, and 'X', to the second jump table. The freed s l o t s were then used for common class A instructions. Another improvement was to define l i b r a r y routines for instructions that . frequently have p a r t i c u l a r raw operands. TC2 has opcodes for such instructions as 'LO', 'L1', 'L-1', 'LIE-3', 'LIE1', 'SET, '+1', '-1', 'L!0', 'L%0', 'M-1', and 'M-2'. Defining these l i b r a r y routines increased the size of the interpreter somewhat, but i t also s i g n i f i c a n t l y reduced the size of SLIM programs and increased t h e i r speed. Peephole Optimization It was necessary once again to count SLIM instructions to 39 determine which should be moved into the second jump table, and which opcode/operand combinations should be allocated s l o t s in the f i r s t . A t o t a l of over 28,000 instructions were coll e c t e d t h i s time, a l l from programs running under BCPL/Z80. Instead of counting the instructions produced d i r e c t l y by the Compiler, however, the Improver (mentioned in chapter 3) f i r s t processed the SLIM programs. The Improver uses the technique of peephole optimization, replacing short sequences of instructions with others which are better (shorter or faster or both). The Improver was inspired by the peephole optimizers of Tanenbaum et a l [Tane82] and Sweet and Sandman [Swee82], but i t is simpler than either. Because the Compiler performs some of i t s own peephole optimizations, many of the more sophisticated c a p a b i l i t i e s of those optimizers were not needed. Instructions are replaced according to rules in a data f i l e . (Appendix A contains the complete l i s t of rules used by the Improver.) Each rule consists of two parts: a pattern and a replacement. If the pattern part of a rule can be matched against a sequence of instructions, the replacement part of the rule i s substituted for them. For example, the following rule: [ Q => CIG98 DO ] replaces a 'Q' instruction with a c a l l to global routine 98, 40 which i s the routine 'Stop' on BCPL/Z80. Most characters in a rule stand for themselves. The more interesting rules include pattern variables. The following rule replaces, for example, '+-1' with '-1': [ +-r => -r ] The 'r' matches a raw operand: either a character constant or a (possibly signed) integer. The variables 's' and ' t ' also match raw operands. Another three variables, 'm', 'n', and 'o', match modified operands: 'H' , 'IH', or raw operands possibly preceded by '<§', 'I§', 'E', 'IE', 'G', or 'IG'. The next example: [ ~=m Tn => =m Fn ] converts a test for inequality to one for equality. Once a variable has matched a sequence of characters, i t stands for those characters anywhere i t appears l a t e r in the pattern or the replacement. The f i n a l variable, 'q', matches a quoted s t r i n g . The following two rules delete the debugging code that some versions .of the BCPL compiler produce: 41 [ $q Ddr => $q ] [ @r:DO DO Dq => ] T C 2 Instruction Set Before instructions were allocated l i b r a r y routines, they were processed by the Improver. This additional step made the selection of instructions somewhat easier. One way in which improvement helped was that i t reduced the number of d i f f e r e n t commonly-used instructions. For example, SLIM has six comparison operators (' =W , '~=W, ' <W , '<=W, '>W, and '>=W) and two conditional jumps ('TW and 'FW). Since almost a l l comparisons are followed by a jump, and since the objects being compared are usually simple variables or constants, most instruction sequences involving comparisons could be rewritten using only two of the operators: * =W and '<=W. The following rules accomplish t h i s task: [ Lm >=n => Ln <=m ] [ <m Fn => >=m Tn ] [ <m Tn => >=m Fn ] [ >m Fn => <=m Tn ] [ >m Tn => <=m Fn ] [ ~=m Fn => =m Tn ] [ ~=m Tn => =m Fn ] After a program has been processed by the Improver, there are very few occurrences of the other four comparison operators. Thus, the jumps to their l i b r a r y routines were put into the second jump table. 42 Closely related was the reduction in the number of commonly-used combinations of opcodes and operands. The following rules, for example: [ Lr +Im => Lim +r ] [ Lr L!Im => Lim L!r ] try to ensure that the operands of '+W and 'L!W are constants whenever possible. The Improver also allowed two small changes to be made to the SLIM machine. The SLIM document [Peck83] does not specify the behaviour of 'TW and 'FW when the accumulator contains a value other than 0 ('False') or -1 ('True'). For TC2, 'False' i s defined to be 0 and 'True' i s any non-zero value. This r e d e f i n i t i o n allows the following rules to be used, speeding up SLIM programs and making them smaller: [ =0 Tm => Fm ] [ =0 Fm => Tm ] (Recall that most '""=0' instructions are translated to '=0' by the rules given e a r l i e r . ) Before the Improver was used, the programs analyzed contained over 200 occurrences of '=0'. After improving, only 7 remained. The other change was the addition of a pair of instructions to increment and decrement a var i a b l e . It is quite common in a 43 BCPL program to add or subtract one from a variable, and the step size in most 'for' commands i s also 1 or -1. These new instructions are put into a program by the Improver: [ LIm +1 Sm => +:m LIm ] [ LIm -1 Sm => -:m LIm ] (Note that the variable 'm' appears twice in the pattern part of the rule.) '+:W and '-:W do not a f f e c t the accumulator and i t is necessary to e x p l i c i t l y load the result afterwards so that the same effect as before i s achieved. In many cases, however, the result i s not needed. These rules catch most of these cases: [ Lm Ln => Ln ] [ Lm @r:Ln => @r:Ln 3 [ Lm Cn DO => Cn DO ] The f i r s t two rules are for the cases when the accumulator i s immediately reloaded with a new value; only the second value i s needed. In the t h i r d rule, the value in the accumulator i s unimportant i f a procedure i s c a l l e d and no arguments are passed to i t . The following sequence of instructions i s t y p i c a l of the code that occurs at the end of a 'for' command: LIE1 +1 SE1 §2:LIE1 <=IE2 T@1 The application of two rules r e s u l t s in the following improved sequence: 44 +:E1 @2:LIE1 <=IE2 T<§1 Appendix B shows the TC2 instruction set, together with i t s encoding. Effectiveness of the Improver The Improver was useful in designing the TC2 instruction encoding, but i t was also intended to be used as an optional step in compiling a program. After a program has been debugged, i t s size and speed can often be improved by the Improver. For some programs, as much as a 10 per cent improvement in both size and speed can be realized. However, i t i s an optional step because the degree of improvement i s usually smaller than that. T y p i c a l l y , a program i s reduced in size by about f i v e per cent and i t runs about three per cent faster. Input/Output It was stated e a r l i e r that TC1 did not quite match the speed of the p-code interpreter. During the development of TC2, i t was discovered that this statement was untrue. The benchmark programs used for comparison did run faster on the p-System than they did on BCPL/Z80, but i t turned out that t h i s result was due 45 not to the difference in speed of the interpreters. TC1 was, in fact, about 20 per cent faster than p-code. However, input/output on BCPL/Z80 was much slower than on the p-System, and the benchmarks did much I/O. The redesign of SLIM instruction encodings for TC2 was successful in speeding up the benchmark programs, but BCPL/Z80 was only just able to match the p-System. The l a s t major change to TC2 was to re-implement input/output. The I/O system of BCPL/Z80 i s based on two functions: 'ReadBytes' and 'WriteBytes'. They read and write an ar b i t r a r y number of bytes on the current input and output streams, respectively. The other procedures, 'ReadN', 'Reads', 'WriteN', 'WriteS', 'WriteF', and even 'RdCh' and 'WrCh', are implemented using these functions. 'ReadBytes' and 'WriteBytes', written in BCPL, were in turn implemented using a few lower-level procedures to read and write 512-byte blocks (for disks) or single characters (for the console, the p r i n t e r , and the modem). These two functions were translated into Z80 assembly language and incorporated into the interpreter. Doing so increased the size of the interpreter by about 700 bytes, but decreased the size of the run-time system by about the same amount. It also greatly sped up input/output. More speed was gained by also translating 'RdCh' and 'WrCh' and la t e r 'ReadS' and 'WriteS' into assembly language. With these changes, the speed of I/O was approximately double that TC1. BCPL/Z80 at last surpassed the p-System in the benchma programs. 47 8. Results BCPL/Z80 i s now considerably faster than the p-System. In thi s chapter, the performance of the BCPL/Z80 system (TC2) i s compared with others, including the previous version of the system (TC1) and the p-System. Both execution times and program sizes are used in the comparisons. Benchmarks Several benchmark programs have been used to compare each new version of BCPL/Z80 with i t s predecessors and with the p-System. Three of these programs are discussed here. The f i r s t program, Hanoi, i s a solution to the Towers of Hanoi problem of six discs. It does not require much ca l c u l a t i o n , but i t produces a prodigious amount of output on the screen. The second program, Ack, computes Ackermann's function with the arguments 3 and 5. It does an enormous amount of work (most of i t being function c a l l s ) , but i t s only output i s the f i n a l answer. The l a s t program, Compare, i s a l i n e - b y - l i n e comparison of two text f i l e s . I t mainly exercises the system f i l e I/O. 48 The following table shows the sizes of these programs for several systems: program size in words Std TC1 TC2 UCSD S i r i u s Hanoi 85 85 76 1 02 136 Ack 105 1 12 92 1 33 1 46 Compare 253 258 231 381 378 The column marked Std shows the program sizes when the standard encoding i s used, as in the f i r s t SLIM interpreter on the Z80, and the UCSD column is for the p-System (version 1.5). The f i n a l column i s for an implementation of SLIM for the S i r i u s (Victor 9000), a machine based on the Intel 8088 16-bit processor. In t h i s implementation, SLIM is translated into the assembly language of the processor, not interpreted. Translation was the natural choice for the S i r i u s because that machine has 128 Kbytes or more of memory, at least twice what i s possible on a Z80-based machine. From the above table, i t can be seen that TC2 programs are consistently smaller than others by at least 10 per cent. Not too surprising i s that programs on the S i r i u s are substantially larger than TC2. What i s surprising, however, i s that the p-System programs are only s l i g h t l y smaller than those on the S i r i u s ; p-code was designed to be compact. 49 The table below shows the time taken to run the benchmark programs: program time in seconds Std TC1 TC2 UCSD S i r i u s Hanoi 14 8 6 6 2 Ack - 55 41 69 5 Compare — 67 24 53 -(The only time shown for the standard encoding i s for Hanoi. Unfortunately, a copy of the system for the Z80 no longer exists and the other two benchmarks were not used while i t did; the program sizes given e a r l i e r were obtained from a version of the interpreter running on an Amdahl 470/V8.) The Hanoi program has been used often during the development of BCPL/Z80 as a benchmark, but i t gradually became evident that the screen output procedures were the bottleneck, not the interpreter. The Ack program shows more c l e a r l y the differences in speed of c a l c u l a t i o n . TC2 i s 68 per cent faster than the p-code interpreter and 34 per cent faster than TC1. Note that TC1 was also faster than p-code, by 25 per cent. The S i r i u s implementation i s almost an order of magnitude faster than even TC2; a factor of four i s perhaps due to the d i f f e r e n t hardware ( i t i s a 16-bit machine, not 8-bit, and i t s clock i s 5 MHz, not 2.1 MHz), but the rest must be because SLIM i s translated to assembly language rather than interpreted. 50 The Compare program shows the improvement in the speed of f i l e I/O. TC2 i s more than twice as fast as the p-System and almost three times as fast as TC1. TC1 i s 26 per cent slower than the p-System. A quotation in Chapter 2 stated that another implementation of BCPL for the Z80, CINTCODE, was s i g n i f i c a n t l y more compact than UCSD Pascal and that i t runs faster. The same can be said of BCPL/Z80 and TC2. 51 9. Conclusions BCPL/Z80 i s a p r a c t i c a l program development system running on a microcomputer. It was b u i l t around three ex i s t i n g portable programs: the BCPL compiler, the CHEF text editor, and the DORIS text formatter. Because these programs were adopted largely unmodified and thus there was no need to write comparable u t i l i t i e s , attention was focussed instead on the interpreter. With the TC2 interpeter, SLIM programs are small and they are executed quickly. However, as with any large piece of software, the performance of TC2 could be improved with some fine-tuning. For example, i t was stated e a r l i e r that, in most cases, comparisons can be rewritten using only two of the six comparison ins t r u c t i o n s : '=W' and '<=W'. Since 'True' was defined to be any non-zero value, the '=W' instruction i s also superfluous in most contexts. The following rules would replace tests for equality with subtractions: [ =m Tn => -m Fn ] [ =m Fn => -m Tn ] With these rules, '=W' would be rarely needed and the s l o t s in the f i r s t jump table used by variations of t h i s instruction could be used for more common ins t r u c t i o n s . The saving due to t h i s pair of rules l i k e l y would be very small, but other similar 52 improvements are probably possible. Another improvement would be the elimination of some 'void' (V) instructions. Currently, the addresses encoded in instructions and held in variables are SLIM addresses, i . e . word, rather than byte, addresses. As a r e s u l t , the Encoder i s required to insert 'V instructions into the code to force alignment on word boundaries. Most of these addresses, however, are for the labels used as targets of 'J@n', 'T@n', and 'F@n' instructions. Since only a very few of these labels are accessible to a BCPL programmer, most need not be aligned on word boundaries and instead could have byte addresses. Eliminating many of the 'V instructions could save as much as 5 per cent in both size and speed. A f i n a l improvement also a f f e c t s jump ins t r u c t i o n s . Target labels of most jumps are only a short distance away from the jumps. Although the target address i s encoded in an instruction as an o f f s e t r e l a t i v e to the location of the in s t r u c t i o n , currently t h i s o f f s e t i s encoded in a word, not a byte. If offs e t s were encoded in bytes whenever possible, programs would be about 10 per cent smaller, but about as f a s t . A goal throughout the project has been to equal or surpass the popular UCSD p-System in the size of object programs and the speed of. execution. It required several attempts, but BCPL/Z80 i s now faster and smaller than the p-System. 53 Bibliography [Bell73] J R B e l l , "Threaded Code", Communications of the ACM, vol 16 #6 (1973 Jun). [Cowd82] R I Cowderoy and P J L Wallis, "The Transfer of a BCPL Compiler to the Z80 Microcomputer", Software—Practice and Experience, vol 12 pp 235-239 (1982). [Dyme82] J D Dyment, "A T u t o r i a l Guide to DORIS (A Text Formatting Program)", University of B r i t i s h Columbia, 1982 Dec. [Eage82] R D Eager et a l , "Draft BCPL Standard", University of Kent, 1982 Dec. [Hayt83] R S Hayter, "The BCPL/Z80 Programming System User's Manual", University of B r i t i s h Columbia, 1983 J u l , (included as appendix C). [ K i l d 8 l ] G K i l d a l l , "CP/M: A Family of 8- and 16-Bit Operating Systems", Byte, vol 6 #6 (1981 Jun). [Macl8l] M A Maclean and J E L Peck, "CHEF: A V e r s a t i l e Portable Text Editor", Software—Practice and Experience, vol 11 pp 467-477 (1981). [Macl82] M A Maclean, private communication to J E L Peck, 1982 May. [Over80] M Overgaard, "UCSD Pascal: A Portable Software Environment for Small Computers", National Computer Conference, 1980. [Peck8l] J E L Peck and M A Maclean, "The Construction of a Portable Editor", Software—Practice and Experience, vol 11 pp 479-489 (1981). [Peck83] J E L Peck, "The Essence of Portable Programming" (d r a f t ) , University of B r i t i s h Columbia, 1983. [RCP81] Richards Computer Products, "More from the Micro with BCPL CINTCODE", advertizing l i t e r a t u r e , 1981. 54 [Rich7l] M Richards, "The P o r t a b i l i t y of the BCPL Compiler", Software—Practice and Experience, vol 1 pp 135-146 (1971). [Ritc78] D M Ritchie and K Thompson, "The UNIX Time-Sharing System", B e l l System Technical Journal, vol 57 #6 part 2 pp 1905-1929 (1978 Jul-Aug). [Swee82] R Sweet and J Sandman, "Static Analysis of the Mesa Instruction Set", Proceedings of the Symposium on Architectural Support for Programming Languages and Operating Systems, ACM SIGPLAN Notices, vol 17 #4 (1982 Apr) . [Tane82] A S Tanenbaum, H van Staveren, and J W Stevenson, "Using Peephole Optimization on Intermediate Code", ACM Transactions on Programming Languages and Systems, vol 4 # 1 (1982 Jan). [Zilo76] Zilog, "Z80-CPU Technical Manual", 1976. Appendix A: TC2 Code Improvement Rules LIm +1 Sm = > +:m LIm LIm - 1 Sm => -:m LIm Lm >=n = > Ln <=m Lr +Im = > LIm +r PLr +Im = > PLIm +r Lr L!Im = > LIm L!r Lr Slim => LIm S i r Lr Lm Ln = > Ln Lm @r:Ln = > dr :Ln Lm Cn DO => Cn DO ~=m Fn => =m Tn ~=m Tn = > =m Fn = 0 Tm = > Fm = 0 Fm = > Tm = - 1 Tm => + 1 Fm = - 1 Fm => + 1 Tm = 1 Tm = > - 1 Fm = 1 Fm = > - 1 Tm <m Fn => >=m Tn <m Tn => >=m Fn >m Fn = > <=m Tn >m Tn = > <=m Fn +-r => -r Q => CIG98 DO ~ Fm => Tm ~ Tm = > Fm $q D@r => $q @r:D0 DO Dq => 56 Appendix B: TC2 Instruct ion Encodings Encoding Mnemonic 00 V FF B 06 xx Wb xx in [0. .255] 09 y y X X Wc xxyy in [ -32768 . .32767] 03 02 y y X X WCc xxyy in [ -32768 . .32767] OC X X WEb xx-10 in [-10.. 245] 03 05 y y X X WEc xxyy in [ -32768 . .32767] 03 08 X X WGb xx in [0. .255] -03 0B X X WGb2 xx+256 in [256. .511] 03 0E y y X X WGc xxyy in [ -32768 . .32767] OF WH 12 y y X X WICc xxyy in [ -32768 . .32767] 1 5 X X WIEb xx-10 in [-10. . 245] 03 11 y y X X WIEc xxyy in [ -32768 . .32767] 18 X X WIGb xx in [0. .255] 1B X X WIGb2 xx+256 in [256. .511] 03 14 y y X X WIGc xxyy in [ -32768 ..32767] 03 17 WIH 1E y y X X CICc 21 X X CIGb 03 1A CW 24 R 27 y y X X JCc 03 1D JW 2A y y X X FCc 03 20 FW 2D y y X X TCc 03 23 TW 03 26 ?I 30 ?S 03 29 N 03 2C Q 33 L-1 36 L0 39 L1 3C X X Lb 3F y y X X Lc 42 y y X X LICc 45 LIE-5 48 LIE-4 4B LIE-3 4E LIE1 51 LIE2 54 LIE3 57 LIE4 5A LIE5 5D X X LIEb 60 xx LIGb 63 X X LIGb2 66 LW 69 L!0 6C X X Lib 6F X X L 1 IEb 72 L1W 75 L%0 78 X X L%IEb 7B L%W 03 2F L:W 03 32 LRS 7E PLO 81 PL 1 84 X X PLb 87 yy X X PLc 8A yy X X PLICc 8D PLIE-4 90 PLIE-3 93 PLIE1 96 PLIE2 99 PLIE3 9C X X PLIEb 9F X X PLIGb A2 X X PLIGb2 A5 PLW A8 yy X X SCc AB SE1 AE SE2 B1 X X SEb B4 X X SGb B7 X X SGb2 03 35 SW BA S! 0 BD X X S!b CO X X S! IEb C3 S!W C6 S%0 C9 X X S%IEb CC S%W 03 38 S:W 03 3B SRS CF P 03 3E X D2 M-2 D5 M-1 D8 MW 03 41 | 03 44 DB + 1 DE X X +b E1 X X +IEb E4 +w E7 X X + :Eb 03 47 + :W EA -1 ED -W 03 4A -:W 03 4D *W 03 50 /w 03 53 /*w -FO X X =b F3 =w 03 56 ~=w F6 X X <=b F9 X X <=IEb FC <=W 03 59 <W 03 5C >W 03 5F >=W 03 62 « w 03 65 >>w 03 68 A w 03 6B \/w 03 6E 03 71 ==w 03 74 w Appendix C: BCPL/Z80 User's Manual 60 !• T n e BCPL/Z80 Programming System BCPL/Z80 i s a complete system for the development of BCPL programs. It consists of a number of independent programs: the CHEF Text Editor i s used to create and modify both programs and documents; the Compiler translates BCPL programs into the SLIM intermediate assembly language; the Improver can be used to make SLIM programs smaller and faster; the Encoder translates SLIM programs into executable binary code; the Linker merges independently-compiled BCPL sections. One of the more useful u t i l i t y programs i s the DORIS Text Formatter which prepares documents for p r i n t i n g . In many respects, there i s a strong resemblance between BCPL/Z80 and the UCSD p-System. The use of the programs described above i s coordinated by an operating system program (called the Shell) modelled after that in the p-System. There i s a subsystem c a l l e d the F i l e r for the manipulation (moving, renaming, destroying and so on) of f i l e s . As well, the BCPL/Z80 disk directory structure i s i d e n t i c a l to the p-System's, and text and data f i l e s generated by either system can be read by the other. Section 2 introduces the important concepts of devices, volumes, and f i l e s . Subsequent sections describe the Sh e l l , the F i l e r and the other programs in more d e t a i l . It i s assumed in this document that the reader i s familiar with the language BCPL. Some knowledge of the UCSD p-System might also be h e l p f u l . The descriptions below apply to the current version of the system (1983 Jun) for the Exidy Sorcerer computer with 55 Kbytes of RAM and two double-density North Star mini-floppy diskettes. Parts of the BCPL/Z80 system were borrowed from other authors. The CHEF Text Editor was written by M Maclean and J Peck. The BCPL Compiler i s a descendent of one written by M Richards. The DORIS Text Formatter was o r i g i n a l l y written by D Dyment and later rewritten by J Peck. 61 2. Devices, Volumes, And F i l e s A t y p i c a l BCPL/Z80 computer system includes a keyboard, a screen, and several disk drives. There may also be a printer and a modem. These are known as input/output devices. Devices Devices are divided into two classes: block and character. For a block device (the disk d r i v e s ) , information i s transferred in blocks of 512 bytes. For a character device (the keyboard, the screen, the printer, and the modem), only one byte at a time i s transferred. Associated with each device i s a device number: dev # device 0 void 1 screen and keyboard with echo 2 screen and keyboard without echo 3 unused 4 disk drive 1 5 disk drive 2 6 printer 7 unused 8 modem 9 disk drive 3 10 disk drive 4 (The differences between devices 1 and 2 w i l l be explained shortly.) Referring to devices by device numbers i s awkward at best. Instead, volume names are used. Volume Names A volume name may be up to 7 characters long and i t i s always followed by a ":". These characters may be l e t t e r s , numbers, ".", "-", "_", "/", or "\". A l l lower case l e t t e r s are automatically s h i f t e d to upper case. Character Volumes The character devices are known as the volumes "CONSOLE:", "SYSTERM:", "PRINTER:", and "REMOTE:". These volume names may be 62 passed as arguments to 'Findlnput' or 'FindOutput' to set up streams to the associated devices. "CONSOLE:" (device #1) i s the keyboard for input and the screen for output. As characters are typed at the keyboard, they are echoed to the screen. In addition, the keyboard i s buffered; no characters w i l l be given to a program reading from "CONSOLE:" u n t i l a <cr> (ASCII carriage return) i s typed. Buffering allows the user to correct typing errors. The la s t character typed can be erased by typing <bs> (backspace) or <del> (delete), and the entire l i n e i s erased when <can> (cancel) i s typed. An <etx> (end of text) i s translated to 'EndStreamCh'. There i s room in the buffer for 99 characters. Whenever a <cr> i s written to the screen, a <lf> (li n e feed) i s automatically written also, so that subsequent text appears on the next l i n e . F i n a l l y , i f a <dle> (data link escape) i s written, the next character written i s taken to be a count (plus 32) of the number of spaces to be displayed on the screen. This two-character sequence i s used by BCPL/Z80 to make text f i l e s (described below) smaller. "SYSTERM:" (device #2) i s similar to "CONSOLE:". One difference is that the keyboard does not echo characters typed to the screen. Another i s that the keyboard i s not buffered; a program w i l l receive characters as they are typed, and i t w i l l receive a <nul> ( n u l l character) i f no character i s ava i l a b l e . The l a s t difference i s that a <lf> i s not automatically inserted after a <cr> when one i s written to the screen, and the two-character <dle> sequence i s not expanded into a number of spaces to be displayed. "SYSTERM:" i s not used as often as "CONSOLE:" i s , but i t i s occasionally useful. "PRINTER:" (device #6) i s not yet implemented. It w i l l behave s i m i l a r l y to "SYSTERM:". "REMOTE:" (device #8) i s similar to "SYSTERM:" but i s associated with the modem. A program reading from th i s volume w i l l receive characters as they are received by the modem, or a <nul> i f none are av a i l a b l e . Characters written are sent by the modem, and <cr> and <dle> are not treated s p e c i a l l y . In addition to these character volumes, there i s another c a l l e d "VOID:". "VOID:" (device #0) ignores characters written to i t , and returns 'EndStreamCh' whenever an attempt i s made to read from i t . Block Volumes Volume names are also associated with disks. However, a volume name does not refer to the disk drive i t s e l f ; i t refers to the disk that i s in the drive. A disk drive i s known by the disk that i s mounted in i t , and so, i t may have d i f f e r e n t names at di f f e r e n t times. 63 For convenience, there are two s p e c i a l shorthand volume names: "*" and ":". The f i r s t r e f e r s to the system volume, the di s k which was i n d r i v e 1 at the time BCPL/Z80 was s t a r t e d up. The other name r e f e r s to the d e f a u l t volume. I n i t i a l l y , the d e f a u l t volume i s the same as the system volume, but i t may be changed by the ' P ( r e f i x ' command d e s c r i b e d l a t e r i n s e c t i o n 4. O c c a s i o n a l l y i t i s u s e f u l to r e f e r to volumes by t h e i r c o rresponding device numbers. The s p e c i a l volume names "#1:", "#2:", and so on r e f e r t o those d e v i c e s . Note t h a t "#4:" r e f e r s to whatever volume happens to be i n d r i v e 1 at the time. F i l e s Block volumes, u n l i k e c h a r a c t e r volumes, are s t r u c t u r e d o b j e c t s . On each block volume there can be a number of f i l e s (up to 77). A d i r e c t o r y on the volume i n d i c a t e s the names of the f i l e s , and the l o c a t i o n of the f i l e s on the d i s k , among other t h i n g s . F i l e s are ra t h e r s i m i l a r to c h a r a c t e r d e v i c e s i n the sense that c h a r a c t e r s may be t r a n s f e r r e d one at a time. The d i f f e r e n c e i s , of course, that the c h a r a c t e r s are s t o r e d permanently on the d i s k . The name of a f i l e , preceded by the name of the volume i t i s on, can be given to 'Fin d l n p u t ' or 'FindOutput' to set up a stream to the f i l e . I f 'Findlnput' i s used, the f i l e must e x i s t a l r e a d y on the d i s k . 'FindOutput' c r e a t e s a new f i l e w ith the name g i v e n . To make the new f i l e permanent, the stream must be c l o s e d by c a l l i n g 'EndWrite'. F a i l i n g to do so w i l l cause the f i l e to disappear when the program st o p s . 'FindOutput' may be given the name of f i l e which a l r e a d y e x i s t s . In t h i s case a l s o , a new f i l e i s c r e a t e d . If 'EndWrite' i s used to c l o s e i t , the o l d f i l e i s removed; otherwise, the new f i l e d i s a p p e a r s and the o l d one remains i n t a c t . R e q u i r i n g an e x p l i c i t c a l l to 'EndWrite' p r o t e c t s e x i s t i n g f i l e s from being l o s t should the system c r a s h . F i l e Names A f i l e name may be up to 15 c h a r a c t e r s l o n g . As i n volume names, these c h a r a c t e r s may be l e t t e r s , numbers, "_", "/", or "\". A l l lower case l e t t e r s are a u t o m a t i c a l l y s h i f t e d t o upper case. 64 F i l e Types There are two types of BCPL/Z80 f i l e s : text and data. (The UCSD p-System has several other f i l e types, but BCPL/Z80 regards these a l l as data f i l e s . ) The names of text f i l e s have a s u f f i x of ".text" and data f i l e s do not. Data f i l e s are the simpler of the two types. The bytes in a data f i l e are exactly those which were written to the f i l e . To make text f i l e s smaller, however, spaces at the beginning of each l i n e of text are stored as the two-character <dle> sequence described e a r l i e r . This compression i s done automatically as characters are written, and they are expanded again when they are read. So that BCPL/Z80 text f i l e s are compatible with those of the p-System, the text in such a f i l e is preceded by a two-block header (1024 bytes) of <nul> characters, and enough <nul>s follow the text to make the f i l e an even number of blocks long. BCPL/Z80 skips these <nul>s when the f i l e i s la t e r read by a program. Data bytes should never be put into a text f i l e . The bytes read from a text f i l e w i l l not be exactly the same as those which were written into i t because of the extra <nul>s and the special treatment of spaces and <dle>s. In contrast, text may be put into a data f i l e . However, depending on the text, the data f i l e might be longer than the corresponding text f i l e with i t s compressed spaces. F i l e Sizes F i l e s each occupy some number of contiguous blocks on the disk. Normally, when a f i l e i s created by 'FindOutput', the largest unused portion of the disk (the largest hole) i s allocated. If desired, the length may be e x p l i c i t l y given by appending "[n]" (where 'n' i s the requested number of blocks) to the f i l e name given to 'FindOutput'. For example: FindOutput ("bcpl:work.space[16]") The blocks are taken from the f i r s t hole large enough, searching from the start of the disk. (A f i l e size may be given when c a l l i n g 'Findlnput' also, but i t i s ignored.) If a f i l e size s p e c i f i c a t i o n of " [ * ] " i s used instead, either the second biggest hole or one-half of the biggest hole i s allocated, whichever i s larger. 6 5 F i l e Specifications To summarize, 'Findlnput' and 'FindOutput' take a f i l e s p e c i f i c a t i o n as an argument. The s p e c i f i c a t i o n i s made up of three parts: the volume name, the f i l e name, and the f i l e s i z e . If the volume name i s that of a character volume, the f i l e name and size are ignored. An omitted volume name i s assumed to refer to the default volume. If the size i s omitted, the size of the largest hole i s assumed. Changing Disks Whenever 'Findlnput' or 'FindOutput' i s given a f i l e s p e c i f i c a t i o n in which the volume name i s that of a disk ( i . e . i t is not a character volume name), BCPL/Z80 searches the disk drives to see i f there i s a block volume of that name. If the volume cannot be found, the user i s given an opportunity to put the disk into a drive. In the example given e a r l i e r , i f the volume "BCPL:" could not be found, the following message would be displayed on the screen: Put BCPL: in and type <cr> (<esc> to abort). At t h i s point the user should put "BCPL:" in one of the drives and then type <cr>. An <esc> (escape) should be typed instead i f the user does not want to put in "BCPL:", perhaps because the volume name was misspelt. Usually, the user should not change disks unless told to do so. Removing a disk with open f i l e s on i t from a drive w i l l probably cause data for those f i l e s to be l o s t . Even worse, putting a d i f f e r e n t disk into that drive w i l l probably result in f i l e s on the disk being overwritten. BCPL/Z80 i s sometimes, but not always, able to detect when a disk with open f i l e s has been removed. If so, the following message i s displayed: Put X: back in and type <cr>. The system w i l l not continue u n t i l the user puts the volume "X:" back i n . It i s always safe to remove or replace a disk i f i t has no open f i l e s . While in the Shell or in the F i l e r , there are no open f i l e s and any disks may be removed or replaced. It i s also usually safe to do so whenever a program asks the user for a f i l e s p e c i f i c a t i o n , but since this i s not always true, i t i s safer to allow BCPL/Z80 to prompt for new disks. 66 Limits Here are col l e c t e d a l l the size l i m i t s r e l a t i n g to devices, volumes, and f i l e s : 1. A volume name may be up to 7 characters long, not including the f i n a l ":". 2. A f i l e name may be up to 15 characters long. 3. There may be up to 77 f i l e s on a block volume. 4. Up to 8 f i l e s may be open simultaneously. 5. There are 350 blocks on a disk but, since the directory occupies the f i r s t 10 blocks, a f i l e can be no bigger than 340 blocks long. 6. A text f i l e i s always an even number of blocks long. It sta r t s with a two-block header of <nul>s and the text i s padded at the end with more <nul>s. Thus, text f i l e s are at least 4 blocks long. 7. The "CONSOLE:" keyboard buffer i s 99 characters long. 67 3. The S h e l l The S h e l l i s the program which runs a u t o m a t i c a l l y when BCPL/Z80 i s s t a r t e d . The user may run other programs by t y p i n g commands to the S h e l l . A f t e r each program f i n i s h e s , the S h e l l i s run once ag a i n . S t a r t u p A f t e r the computer i s turned on (or r e s e t ) , put the system d i s k i n the l e f t d r i v e and then type: go dcOO Within a few seconds, the BCPL/Z80 logo w i l l be d i s p l a y e d on the screen. Within a few more seconds, the S h e l l w i l l begin running. Commands While the S h e l l i s running, i t d i s p l a y s a menu of commands at the top of the screen: S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? T h i s menu l i s t s most of the commands which may be used. Another menu which l i s t s the remaining commands i s d i s p l a y e d when a "?" i s typed: S h e l l : A(ssem, L ( i n k , R ( e s t a r t ? Any of these commands may be performed by simply t y p i n g the corresponding l e t t e r , the one shown before the " ( " . Although these l e t t e r s are shown i n upper case, e i t h e r upper or lower case may be typed. The commands are d e s c r i b e d below. I t i s safe to change d i s k s while the S h e l l i s running. In t h i s s e c t i o n , and i n the o t h e r s t o f o l l o w , a number of examples are g i v e n . The input that a user would type i s u n d e r l i n e d . 68 A(ssem The 'A(ssem' command is used to run the Z80 assembler. The Assembler, which is not yet finished and so i s not described, w i l l be in the f i l e "*system.assmbler". C(omp The 'C(omp' command is used to run the BCPL Compiler. The Compiler, described in section 6, i s in the f i l e "*system.compiler"'. The f i l e s "*system.c .parse", "*system.c.trans", and "*system.c.error" are used by the Compiler. D(ate The 'D(ate' command i s used to set the system date. When the BCPL/Z80 system i s started, i t displays i t s current date, usually the date th i s command was la s t used. (The BCPL/Z80 does not include a real-time clock, so the date must, unfortunately, be set manually.) It i s important to keep t h i s date accurate, since i t i s used by the system whenever a f i l e i s created or modified. When the command i s used, the system displays the current date and then asks for today's. If i t i s supplied, the date i s set. The year, the month, and the day must be entered in that order. Any of them, however, may be omitted and those that are w i l l not change. If present, the year must be between 1901 and 1999, the day must be between 1 and 31, and at least the f i r s t three l e t t e r s (upper or lower case) of the month's name must be given. Example: S h e l l : C(omp, D(ate T E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? d Current date i s 1983 Jun 30 New date? j u l 2 Current date i s 1983 J u l 2 S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , Kmprove, eN(code, eX(ec? 69 E(dit The 'E(dit' command i s used to run the CHEF Text Editor. CHEF, described in section 5, i s in the f i l e "*system.editor". The f i l e "*system.e.msg" is used by CHEF. F( i l e The ' F ( i l e ' command i s used to enter the F i l e r subsystem. The F i l e r , described in section 4, i s part of the Sh e l l , not a separate program. I(mprove The 'I(mprove' command i s used to run the Improver. The Improver, described in section 7, i s in the f i l e "*system.improver". L(ink The 'L(ink' command is used to run the Linker. The Linker, described in section 9, i s in the f i l e "*system.linker". eN(code The 'eN(code' command i s used to run the Encoder. The Encoder, described in section 8, i s in the f i l e "*system.linker". R(estart The 'R(estart' command i s used to re-run the program which was most recently run. This command i s p a r t i c u l a r l y handy when used after a complicated 'eX(ec' command. 70 eX(ec The 'eX(ec' command i s used to run programs. The Shell asks which f i l e to run. In addition to the program name, the user may specify the i n i t i a l input and output streams for the program. These streams are named in a manner similar to that used on UNIX. The input f i l e s p e c i f i c a t i o n is prefixed by a "<" and the output s p e c i f i c a t i o n i s prefixed by a ">". If either or both streams are not redirected in th i s way, they are i n i t i a l l y set to "CONSOLE:". .When a system program ( l i k e the Compiler, for example) is run using one of the above s i n g l e - l e t t e r commands ('C(omp'), the input and output streams are set to "CONSOLE:". The 'eX(ec' command can be used to redirect input or output when running one of these programs, i f required. (Output redirection was used to produce the examples in t h i s document.) The f i l e names of the system programs were given with the descriptions of the commands above. Example: S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? x Execute what f i l e ? *hanoi <x:h.in.text >x:h.out.text S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? *system.startup When the BCPL/Z80 system i s started, i t checks to see i f there i s a f i l e c a l l e d "*system.startup". If so, this program i s run before the S h e l l . It i s th i s Startup program that displays the BCPL/Z80 logo mentioned e a r l i e r . If desired, another program can be renamed "*system.startup" and i t w i l l then be run whenever the system i s started. 71 4. The F i l e r The F i l e r i s a subsystem useful for manipulating f i l e s . It is entered by typing the ' F ( i l e ' Shell command. The F i l e r i s based on a similar program which i s part of the UCSD p-System. The current BCPL/Z80 version i s much less powerful, however. It i s intended that t h i s deficiency w i l l be corrected soon. In the meantime, although i t i s inconvenient to do so, the UCSD F i l e r may be used for those commands not yet implemented. Only those commands implemented so far are described here. Commands While the F i l e r i s running, i t displays a menu of commands at the top of the screen: F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? These commands are described below. In the examples, the system volume i s assumed to be "BCPLZ80:" and the default volume i s "WORK:". It i s safe to change disks while in the F i l e r . C(hanqe The 'C(hange' command i s used to change the name of a f i l e . The F i l e r f i r s t asks which f i l e i s to be renamed and then for the new name. When the new name i s typed, i t i s not necessary to give a volume name; i t i s ignored since the f i l e stays on the same volume. - , 72 Example: F i l e r : C(hange, L ( i s t , P (refix, R(emove, T(ransfer, Q(uit? c Change what f i l e ? ' *hanoi To what? system.startup BCPLZ80:HANOI changed to SYSTEM.STARTUP. F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? L ( i s t The ' L ( i s t ' command i s used to l i s t the f i l e s on a volume. The F i l e r asks for the name of a volume. The l i s t which i s then displayed shows, for each f i l e , i t s name, the date i t was created or l a s t modified, the block number at which i t s t a r t s , i t s length in blocks, the number of bytes used in i t s l a s t block, and i t s type. (As explained e a r l i e r , BCPL/Z80 f i l e types are either "text" or "data", but f i l e s created under the p-System may have other types.) Any unused parts of the disk (holes) are also shown in the l i s t together with t h e i r s t a r t i n g block number and length. After t h i s l i s t are some s t a t i s t i c s : the number of f i l e s on the volume, the number of disk blocks used and unused, and the size of the largest hole. 73 Example: F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? 1 L i s t the directory of what volume? bcplz80: BCPLZ80: 1983 Jul 25 SYSTEM.C.ERROR 1982 Jun 4 10 10 512 text HEADER.B.TEXT 1 983 May 19 20 18 512 text SYSTEM.SHELL 1 983 Jun 3 38 10 312 data SYSTEM.E.MSG 1 982 Oct 18 48 10 512 text SYSTEM.STARTUP 1983 Jul 25 58 4 80 data SYSTEM.RUNTIME0 1983 Jul 25 62 32- 512 data SYSTEM.ENCODER 1983 May 26 94 16 20 data SYSTEM.LINKER 1 983 May 26 1 10 3 12 data SYSTEM.IMPROVER 1 983 Jun 1 2 1 13 9 190 data SYSTEM.EDITOR 1 983 Jun 3 122 49 308 data SYSTEM.COMPILER 1983 May 27 171 6 202 data SYSTEM.C.PARSE 1983 May 27 1 77 19 60 data SYSTEM.C.TRANS 1 983 May 27 1 96 25 386 data < unused > 221 129 13 f i l e s , using 211 blocks. 129 blocks unused; 129 in largest hole. F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? P(refix The 'P(refix' command i s used to set the name of the default volume.. If a f i l e s p e c i f i c a t i o n given to 'Findlnput' or 'FindOutput' does not include a volume or has a volume name of ":", i t i s considered to refer to the default volume. I n i t i a l l y , the default volume i s the same as the system volume. Example: F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? p_ Prefix names with what volume? work: New prefi x i s WORK:. F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? 74 R(emove The 'R(emove' command i s used to destroy a f i l e . The F i l e r asks which f i l e i s to be removed. Example: F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? r Remove what f i l e ? hanoi.s WORK:HANOI.S removed. F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? T(ransfer The 'T( ransf er.' command i s used to make a copy of a f i l e . The F i l e r f i r s t asks which f i l e i s to be transferred and then the name of the copy. The copy may go to the same volume or to a di f f e r e n t one, and i t may have the same name or a d i f f e r e n t one. A text f i l e may be displayed on the screen by tranferring i t to "CONSOLE:", and keyboard input ( u n t i l an <etx> i s typed) may be put into a f i l e by trans f e r r i n g to i t from "CONSOLE:". Example: F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? t Transfer what f i l e ? hanoi To where? *system.startup[4 3 WORK:HANOI transferred to BCPLZ80:SYSTEM.STARTUP. F i l e r : C(hange, L ( i s t , P ( r e f i x , R(emove, T(ransfer, Q(uit? Q(uit The 'Q(uit' command i s used to return to the S h e l l . 75 5. The CHEF Text Editor CHEF i s a general-purpose text editor suitable for the creation and modification of both programs and documents. The command language i s described in The CHEF Editor. CHEF i s run by typing the 'E(dit' Shell command. It then prompts for commands. Only one command has not been implemented: 'QS'. As a resul t , i t i s not possible to execute Shell commands from CHEF, nor i s i t possible to temporarily leave CHEF and resume i t l a t e r . The BCPL/Z80 version of CHEF has the screen mode 'A' command. In screen mode a number of special keys are used: key function <g-UA> cursor up <g-DA> cursor down <g-LA> cursor l e f t <g-RA> cursor right <g-i> begin insert mode <g-e> end insert, mode <g-d> delete character <gs-I> insert l i n e <gs-D> delete l i n e <g-1 > exit <g-2> renew <g-3> merge <g-4> ma r k <g-5> save <g-6> ' inject where <g-UA> means that the 'up arrow* key on the keypad i s typed while the 'graphic' key i s held down, <g-i> means that " i " i s typed with 'graphic' held, <gs-I> means that " I " i s typed with both 'graphic' and ' s h i f t ' held. For the la s t 6 functions, the number keys on the top row should be used, not those on the keypad. The prompt at the top of the screen while in a l t e r mode is a reminder of which keys are associated with these 6 functions: >>g1-Exit,g2-Renew,g3-Merge,g4-Mark,g5-Save,g6-Inject<< The system disk should never be removed from the drive while CHEF i s running. Example: S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , l(mprove, eN(code, eX(ec? BCPL/Z80 Editor (CHEF) Enter H for help (Q for quit) >ef work:hanoi.b.text 488 ...editing commands >wf. 503 >2 S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? 77 6. The BCPL Compiler The Compiler translates BCPL programs into SLIM assembly language. The language accepted by the Compiler corresponds quite cl o s e l y to that defined in the Draft BCPL Standard (1982 Dec). The standard header f i l e can be included in a program by means of the following get d i r e c t i v e : get "**header.b.text" The procedures declared in the standard header are described in more d e t a i l in The BCPL/Z80 Run-Time Library. The Compiler i s run by typing the 'C(omp' Shell command. It then prompts for the name of the f i l e containing the BCPL program, and for the name of a f i l e to write the SLIM text. Usually, the BCPL f i l e has a s u f f i x of ".b.text" and the SLIM f i l e has one of ".s". A BCPL program i s compiled in two passes. In the f i r s t , a parse tree i s constructed corresponding to the program. A "." is printed on the screen for each l i n e of the program as i t i s processed. Procedure names are also printed as their d e f i n i t i o n s are reached. Also, as each get i s encountered, a message i s printed. In the second pass, the parse tree i s used to generate an equivalent SLIM program. Again, procedure names are printed, and a "." i s printed for each l i n e of SLIM generated. The f i l e to be compiled may contain any number of BCPL sections. Should the Compiler detect an error during either pass, an error message w i l l be displayed. The user then may type either 'C(ontinue' to allow the Compiler to resume, or 'Q(uit' to abort the compilation and return to the S h e l l . The system disk should never be removed from the drive while the Compiler i s running. Example: S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? c BCPL/Z80 Compiler Compile what f i l e ? work:hanoi.b.text Into what f i l e ? work:hanoi.s • • • get *header.b.text START HANOI Tree size = 2304. START HANOI No errors detected. S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? 79 1_. The Improver A SLIM assembly language program can usually be made both smaller and faster by the Improver. It uses the technique of peephole optimization to replace short sequences of instructions by equivalent, but better, sequences. The degree of improvement possible depends on the SLIM program, but t y p i c a l l y the improved program is 10% smaller and 5% faster . Because these gains are rather modest, i t i s probably only worthwhile to improve debugged and often-used programs. The Improver i s run by typing the 'I(mprove' Shell command. It then prompts for the name of the f i l e containing the SLIM program to be improved, and for the name of a f i l e to write the improved program. Usually, the SLIM f i l e has a s u f f i x of ".s" and the improved SLIM f i l e has one of " . i s " . Procedure names are printed on the screen as they are processed. Also, a "." i s printed for each l i n e of SLIM text written. The f i l e to be improved may contain any number of SLIM sections. It is safe to remove any disk from i t s drive when a f i l e name i s requested. Example: S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I (mprove, eN(code, eX(ec? _i BCPL/Z80 Improver Improve what f i l e ? work:hanoi.s Into what f i l e ? work:hanoi.is • START HANOI 78 instructions read and 78 written. 1 successful pattern matches. S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? 80 8. The Encoder A SLIM assembly language program must be encoded as bi n a r y o b j e c t code bytes by the Encoder before i t can be run. The Encoder i s run by t y p i n g the 'eN(code' S h e l l command. It then prompts f o r the name of the f i l e c o n t a i n i n g the SLIM program to be encoded, and f o r the name of a f i l e to w r i t e the bin a r y code. U s u a l l y , the assembly language f i l e has a s u f f i x of " . s " or " . i s " and the binary f i l e does not have a s u f f i x . Procedure names are p r i n t e d on the screen as they are processed. A l s o , a "." i s p r i n t e d f o r each l i n e of SLIM tex t read. The f i l e to be encoded may c o n t a i n any number of SLIM s e c t i o n s . I t i s safe to remove any d i s k from i t s d r i v e when a f i l e name i s requested. Example: S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? e BCPL/Z80 Encoder Encode what f i l e ? work:hanoi.is Into what f i l e ? work:hanoi • • START HANOI No e r r o r s d e t e c t e d . 91 words of SLIM code and 5 r e l o c a t i o n s . S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? 81 9. The Linker If a BCPL program has been organized as a number of separately-compiled sections in separate f i l e s , the sections must be linked together before the program can be run. It i s not, however, necessary to l i n k the sections i f they are already in the same code f i l e . The Linker i s run by typing the *L(ink' Shell command. It then prompts for the names of the f i l e s containing the SLIM sections to be linked, and for the name of a f i l e to write the binary code. Usually, none of the f i l e s has a s u f f i x . It i s safe to remove any disk from i t s drive when a f i l e name i s requested. Example: S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? 1 BCPL/Z80 Linker Input code f i l e ? doris:d1 Input code f i l e ? Input code f i l e ? Input code f i l e ? Input code f i l e ? 4567 words of SLIM Output code f i l e ? doris:d2  doris:d3  doris:d4 code and 224 doris:doris relocations. S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , l(mprove, eN(code, eX(ec? 82 10. The DORIS Text Formatter DORIS i s a program which formats documents in preparation for p r i n t i n g them. Although i t i s simple to use, i t i s also quite powerful. The use of DORIS i s described in A T u t o r i a l  Guide To DORIS (A Text Formatting Program). DORIS i s run by typing the 'eX(ec' Shell command and i s in the f i l e "doris:doris". It then prompts for the name of the f i l e containing the document to be formatted, and for the name of a f i l e to write the formatted document. It also prompts for the name of a f i l e to be used in constructing an index, but i t i s only necessary to type a name i f the document contains ' . f i l ' commands. Usually, the document f i l e has a s u f f i x of ".di.text", the formatted f i l e has one of ".do.text", and the index f i l e has one of ".dx.text". It i s safe to remove any disk from i t s drive when a f i l e name i s requested. Example; S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? x Execute what f i l e ? d o r i s i d o r i s BCPL/Z80 Text Formatter (DORIS) Process what f i l e ? work:thesis.di.text Into what f i l e ? work:thesis.do.text Use what index f i l e ? S h e l l : C(omp, D(ate, E ( d i t , F ( i l e , I(mprove, eN(code, eX(ec? 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051848/manifest

Comment

Related Items