1.Introduction -------------- PASCAL-U is the name of the dialect of Pascal implemented on the PDP 11/45 under the UNIX time-sharing system. This dialect is based on PASCAL-P as distributed by the ETH at Zurich. The implementation of PASCAL-U has been developed by the vakgroep informatica of the Vrije Universiteit, Amsterdam, The Netherlands. This manual is divided into the following chapters: 1.Introduction 2.Some history 3.How to use PASCAL-U 4.The dialect PAS-CAL-U 5.The S(tack) C(omputer) assembly language 6.The assembler 7.The B(inary) S(tack) C(omputer) code 8.The interpreter 9.How to generate a PASCAL-U system To fully understand chapters 4 to 8, the more detailed description of the Stack Computer in: The PASCAL-P Compiler: Implementation Notes by K.V.Nori, U.Ammann, K.Jensen, H.H.Naegeli and C.Jacobi is recommended. Comments, criticisms and complaints should be directed to: Andrew S. Tanenbaum Vakgroep Informatica Vrije Universiteit De Boelelaan 1081 Amsterdam, The Netherlands 2.Some history -------------- The first plans to implement Pascal on the PDP 11/45 were developed under the guidance of prof.R.P.van de Riet. In those days (mid 1975) the operating system was DOS, a single user system. The greatest problem has been the limited ad- dress space of the machine. The Pcompiler produces code for a virtual machine, called the SC machine. Macro expansion of SC instructions to PDP-11 code was not feasible due to the addressing limit of the PDP-11. Therefore the SC in- structions were directly encoded and an interpreter was written to execute them. The following description concerns work carried out by Rob Thomas, Johan Steven- son and later on by Rudolf van Bottenburg. The first bootstrap used a CDC Cyber 73 computer on which Pascal was available. At the end of 1975 a preliminary version was running under DOS. Many changes have been made to the PASCAL-P2 compiler, most of them forced by the different size for variables of the various standard types and the address alignment. (The Pcompiler foolishly assumed that integers,reals etc. all occupied the same number of storage units.) At the same time, however, the UNIX time-sharing sys- tem was installed. That required adjusting the Pascal system. The interpreter was rewritten in the UNIX assembly language, and the SC assembler in the high level language C. To minimize the space requirements, some changes were made to the first UNIX version: a.based upon static counting of SC-instructions in the compiler itself, some in- structions of 2 or more bytes with a high frequency got a 1-byte format. This is not done very systematically, however. Further measurements are needed. b.a lot of optimization is done concerning label references: offsets instead of indices, distinction between forward and backward, long and short offsets. c.the handling of input and output is improved. This resulted in a 25% saving in space for code, while at the same time the in- terpretation speed improved. The 16000 SC-instructions for the compiler itself are coded in less than 26000 bytes, inclusive constants. This system is called the PASCAL-U1 system. One of the projects under development in our department, is the BASIS system. It is used in teaching basic programming techniques to students of several disci- plines. BASIS is a big program written in Pascal, in size comparable with the Pcompiler. One of the reasons to make Pascal available on the PDP 11/45, has been this BASIS project. The plans for the near future are: a.to adopt the improvements of the P4-compiler with respect to the P2-compiler. b.to allow external procedures. c.to allow the Pascal user to choose between interpretation and execution of ex- panded SC-instructions. For example, one would like to make the scanner of a compiler fast by execution of its expanded code and leave the other parts in- terpreted, since for most programs 20% of the program is responsible for more than 80% of its execution time. d.to make some local improvements touched upon in the assembler description. e.to tune the instruction set of the abstract machine. 3.How to use PASCAL-U --------------------- Compilation of pascal programs is done by ’pc’ (see pc.man for its description). To interpret the resulting binary code file, ’pi’ must be used (see pi.man). 4.The dialect PASCAL-U. ------------------------- A.Differences between PASCAL-U and standard PASCAL. 1.Goto’s may not lead out of a block. 2.Procedures and functions cannot be passed as parameters. 3.Procedures and functions may not be declared extern. 4.Dispose is not implemented. Instead of this: mark (var p: ANYPTR) makes p point to the top of the heap. release (p: ANYPTR) restores the top of the heap from p. ANYPTR is any pointer type. 5.In recordtype declarations empty fields and empty field lists are not al- lowed. 6.Empty statements are not allowed in repeat and case statements. 7.The keyword packed is ignored. Character and boolean fields are allways aligned to a byte boundary, other to a word boundary. B.Files 1.A PASCAL-U program can use at most 8 files, including the predeclared files input and output. These files are associated with UNIX standard input and output. There is no relationship between PASCAL filenames and UNIX file- names, except the order in which they are given in the program heading. 2.Each non-predeclared file must be given in the heading, and must not be de- clared elsewhere. All files have the type text = file of char. 3.Each read file (except standard input) must be opened by reset. 4.Before reading from any file, get must be called to initialize the file win- dow. 5.Write files must be opened by rewrite. This is equivalent to a creat system call. 6.In calls to read or write the first argument can be omitted, however the call write(input^) will go wrong. 7.Readln and writeln require always parentheses. C.Local extensions and implementation constants 1.maxint is 32767 , the setsize is 8 bytes (0..63) 2.The characterset is 128-ASCII , the parity bit is not cleared. Keywords and standard names are recognized in lowercase. 3.There are some hidden library routines used by the BASIS system. 5.The S(tack) C(omputer) assembly language ------------------------------------------ 1. Each line contains 1 instruction or 1 label definition. 2. A blank line marks the end of the SC-code. 3. Each instruction line starts with a space; a label-line does not. 4. The ASCII character set is used. 5. The following notations are used in describing the sc-code: [index] 0..maxaddr [int] 0..32767 [sint] -32768..32767 [level] 0..15 [labno] 0..maxlabel [type] 0..3 [typelevel] 0..63 (16 * type + level) 6. instruction set: a.no parameters: abi abr adi adr and dif dvi dvr eof flo flt inn int ior mod mpi mpr ngi ngr not odd sbi sbr sgs sqi sqr stp trc uni b.1 parameter: lao [index] mov [int] dec [int] inc [int] ixa [int] mst [level] sto [type] ret 0..2 lca #10-char string# ujp l [labno] fjp l [labno] xjp l [labno] csp standard-procedure-mnemonic ,which can be eln get gln rln rdi rdc rdr put pln wln wri wrc wrr wrs wrb orf cwf log sin atn exp cos sqt rst sav new clk avl abt c.2 parameters: ldo [type] [index] ind [type] [index] sro [type] [index] lod [typelevel] [index] str [typelevel] [index] lda [level] [index] cup no.of bytes for parameters l [labno] d.special: ldc 0 [sint] 2 0..1 3 4 real 5 (set elements separated by spaces ) equ neq geq grt les leq with the following pars: 0..4 5 [int] 7. The instruction ’chk’ is not used by the PASCAL-U compiler. 8. A label definition can be described by l [labno] or l [labno]= [int] 6.The assembler --------------- In addition to the replacement of SC-mnemonics by BSC-opcodes, the most impor- tant tasks of the assembler are: 1.to find the indices of the labels and to resolve the label references. (With an index the distance in bytes to the first instruction is meant) Because most UJP and FJP instructions jump over relative small distances forward or back- ward, they have an offset as parameter (like BR .+n in Macro-11). The offset is the absolute value of the distance in bytes between the label definition and the first byte of the next instruction. (There are different BSC instruc- tions for forward and backward branches.) The same solution is used for CUP instructions. (A better idea is to have a table of procedure indices and to give the CUP instruction the index in that table as parameter. For big pro- grams and under the assumption that on the average a procedure is called more than twice, that is cheaper. These changes will be made in the next version.) When the offset is less than 256, then 1 byte is sufficient. The problem is how to compute the offsets, especially the forward ones. The way the current assembler does it, is very clumsy but simple: a.the assembler scans the sc-code several times, the first time with all label indices very big (32767). b.for each label definition the label index is set on the current index. for each label reference the offset is computed, and the appropriate number of bytes are filled in. c.the total number of bytes per scan is decreasing monotonically. d.when 2 scans result in the same number of bytes,you are ready;because: A.the label indices didn’t change the last scan, so B.the offsets, also the forward ones, are correct after the last scan (A better approach is to optimize per procedure, but then you have to take special care of forward procedure definitions; when the new CUP instruction is implemented, the problems are smaller; so changes will be made in the next version.) Sometimes, for big programs, it is needed to scan the SC-code 10 times, and it is not surprising that the assembler is time consuming in such cases. 2.to generate different BSC-instructions for the same SC-instruction, depending on the parameters of the SC-instruction. 3.to build the constant table and compute indices into this table as a parameter to the BSC-instructions: lca,ldcr & ldcs. The constant table is an unstruc- tured bunch of bytes. If at some point a constant has to be added to it, then the table is searched for the correct number, which has to start on a word boundary for reals and sets. If not found, some fresh bytes are initialized and added to the table. 4.to optimize the XJP instruction. The form of the SC-code suggests a group of UJP instructions following XJP. XJP has to choose the correct UJP instruction depending on the value at the top of the stack. But this scheme needs a fixed length UJP instruction. Moreover the UJP opcode is superfluous. The alterna- tive: for each UJP instruction the offset is computed and only this offset, always occupying 2 bytes, is stored. (An improvement for the next version: the bound checking for the CASE statement is not done by SC-instructions any- more, but by giving XJP a parameter: lmax-lmin i.e.the number of UJP’s - 1. XJP can check the top of the stack T for 0 <= T <= lmax-lmin.) 5.to optimize io-calls. Each io-standard procedure call is preceded by LAO n, with n giving the index of the filebuffer. This LAO instruction is being re- placed by an extra field for the cio-instruction. For first 3 files there is even a special instruction: cio0, cio1 & cio2. 7.The B(inary) S(tack) C(omputer) code -------------------------------------- Each instruction has an opcode followed by 0, 1 or 2 fields of 1 or 2 bytes each. The opcode range is 0..255 decimal, or 0000 .. 0377 octal. The instructions with 128<=opcode<=191 have a first field of 1 byte (qfield). There also exist opcodes for these instructions if their qfield needs more than 1 byte. In that case the opcode is 64 higher than the opcode with the short qfield. So opcodes 192..255 are reserved for instructions with long qfields. The opcode table: 0000 ldc0 ldc1 ldc2 ldc3 ldc4 ldc5 ldc6 ldc7 0010 ldc8 ldc9 ldc10 not and ior odd mod 0020 adi sbi mpi dvi ngi abi sqi inn 0030 sgs uni dif int stp new sav rst 0040 equi equs geqi geqs grti - leqi leqs 0050 lesi - neqi neqs ixa1 ixa2 dec1 inc1 0060 retp reti retr ldcn llda10 llda12 llda14 llda16 0070 lstr10 lstr12 lstr14 lstr16 lstr18 lstr20 lstr22 lstr24 0100 llod10 llod12 llod14 llod16 llod18 llod20 llod22 llod24 0110 stoi stoc stor stos mst0 mst1 mst2 mst3 0120 xjp fpp mst cio0 cio1 cio2 cio csp 0130 - - - - - - - - 0140 - - - - - - - - 0150 - - - - - - - - 0160 - - - - - - - - 0170 - - - - - - - - 0200 ldci ldcr ldcs ent equa geqa grta leqa 0210 lesa neqa dec inc ixa mov lao lca 0220 llda sroi sroc sror sros indi indc indr 0230 inds ldoi ldoc ldor ldos lstri lstrc lstrr 0240 lstrs llodi llodc llodr llods fjpf fjpb ujpf 0250 ujpb cup0f cup0b cup2f cup2b cup4f cup4b cupf 0260 cupb lda stri strc strr strs lodi lodc 0270 lodr lods - - - - - - 0300 ldci+ ldcr+ ldcs+ ent+ equa+ geqa+ grta+ leqa+ 0310 lesa+ neqa+ dec+ inc+ ixa+ mov+ lao+ lca+ 0320 llda+ sroi+ sroc+ sror+ sros+ indi+ indc+ indr+ 0330 inds+ ldoi+ ldoc+ ldor+ ldos+ lstri+ lstrc+ lstrr+ 0340 lstrs+ llodi+ llodc+ llodr+ llods+ fjpf+ fjpb+ ujpf+ 0350 ujpb+ cup0f+ cup0b+ cup2f+ cup2b+ cup4f+ cup4b+ cupf+ 0360 cupb+ lda+ stri+ strc+ strr+ strs+ lodi+ lodc+ 0370 lodr+ lods+ - - - - - - A short description of mnemonics: There exist the following suffixes: i/c/r/s the operands are integer,character,real or set f/b the jump instructions have a qfield containing the absolute offset i.e. the absolute value of the difference between the address of the byte after the qfield and the address of where to jump to. f/b indicates forward/backward jump. integer the value of one of its otherwise needed fields. i/s/r/a suffix for test-instructions meaning integer,set,real and multiple + indicates long qfield. The prefix l denotes level=0, so the operand is a local. Some special mnemonics: ldcn load nil retp,reti,retr return 0,1 or 2 words fpp p floating-point instr. (p even) cio p f io-routine p on file f (p even) cio0..2 p =cio p 0..2 csp p special for BASIS (p even) The pfield codes (only even codes used) of fpp: 0000 flt flo trc adr sbr mpr dvr ngr 0020 abr sqr equr geqr grtr leqr lesr neqr 0040 sin cos exp log sqrt atan cio: 0000 eof eln get gln rln rdi rdc rdr 0020 put pln wln wri wrc wrr wrs wrb 0040 orf cwf csp: 0000 abt avl clk Number of bytes for each instruction: opcode op fld1 fld2 total 0000..0120 1 1 0120..0124 1 1 2 0125 1 1 1 3 0126 1 1 2 0200..0256 1 1 2 0257..0271 1 1 1 3 0300..0356 1 2 3 0357..0371 1 2 1 4 8.The interpreter ----------------- The best way to understand the interpreter is to read the listings very careful- ly. A difficult point is the allocation of memory during interpretation. Two cases are discussed: 1. The memory map for a not shareable program. This is the case for all user programs running by a call like: pi program.b userfile1 ... 1.1. The map: bytes: 0 8 16 24 32 40 48 56 64k +-------+-------+-------+-------+-------+-------+-------+-------+ | | || . .. : : | | | | || . .. : : | | | | || . .. : : | | | | || -> . not-used .. <- : : | | | | || . .. : : | | | | || . .. : : | | | | || . .. : : | | +-------+-------+-------+-------+-------+-------+-------+-------+ b0 1 23 4 56 7 8 9 10 text: >---< data: >< bss: >----< stack: >-------------------< 1.2. You can distinguish 10 parts with boundaries b0..b10: b0-b1 the interpreter (PDP machine code & fixed data) .text b1-b2 unused part of the text segment .text b2-b3 the variables used by the interpreter .data b3-b4 the PASCAL stack .bss b4-b5 unused b5-b6 the interpreter stack stack b6-b7 the PASCAL heap stack b7-b8 CODE (the BSC-code of P) stack b8-b9 CONST (constant reals/strings/sets of P) stack b9-b10 io-buffers stack 1.3. How to find addresses of b0..b8: b0=0 b1=011100 (computed by the loader) b2=020000 (end of first segment) b3=020744 (computed by the loader) b4=...... (dynamically growing) b5=...... (ditto) b6=...... (ditto) b7=b8-ncode (word 1 of codefile) b8=b9-nconst (word 2 of codefile) b9=0170000 (room for 8 file buffers) b10=0200000 Some remarks about b4,b5 and b6: - b4 can only grow - when b6 is changed then b5 is always equal to b6; that means: the interpreter stack is empty. - b4 and b5 have to be in different segments, so not all the room can be used. 1.4. To start the interpreter , you have to initialize some variables: r5:=b3 (=store) (r5 is the stackpointer of P) mp:=b3 (mp is the markstackpointer) r4:=b7 (r4 is the programcounter of P) np:=b7 (np is the heappointer) sp:=b7 (sp is the stackpointer of the interpreter) cbase:=b8 (cbase gives the baseaddress of CONST) ccorr:=b8-b3 (CONSTbaseaddress - STOREbaseaddress) 2. The memory map of a shareable PASCAL program e.g. the PASCAL-U compiler. 2.1. The map: bytes: 0 8 16 24 32 40 48 56 64k +-------+-------+-------+-------+-------+-------+-------+-------+ | | | | || . .. | | | | | | || . .. | | | | | | || . .. | | | | code | | || -> . .. <- | | | | | | || . .. | | | | | | || . .. | | | | | | || . .. | | +-------+-------+-------+-------+-------+-------+-------+-------+ b0 1 2 3 45 6 78 9 10 text: >---------------------------< data: >< bss: >----< stack: >---------< 2.2. You can distinguish 10 parts here: b0-b1 interpreter .text b1-b2 CODE .text b2-b3 CONST .text b3-b4 not-used b4-b5 interpreter variables .data b5-b6 the PASCAL stack .bss b6-b7 not-used b7-b8 sp-stack space stack b8-b9 the PASCAL heap stack b9-b10 io-buffers stack 2.3. The values of b0..b10 for the case of the PASCAL-U compiler: b0 0 b1 04016 b2 063110 b3 067100 b4 0100000 b5 0100110 b6 ....... b7 ....... b8 ....... b9 0175000 b10 0200000 9.How to generate a PASCAL-U system ----------------------------------- To generate the PASCAL system you need distribution tape 0 mounted on unit 0 for instance. (Distribution by DEC tape is assumed). The following commands can be used as a shell file. To make the PASCAL-U system, start in a fresh directory. ******************************************** : get the sources of the assembler from tape tp xv0 assnew.c cstnew.c datnew.c extnew.c getnew.c lttnew.c mainew.c : generate the assembler cc -c assnew.c ; rm assnew.c cc -c cstnew.c ; rm cstnew.c cc -c getnew.c ; rm getnew.c cc -c lttnew.c ; rm lttnew.c cc -c datnew.c ; rm datnew.c ar rv palib.o assnew.o cstnew.o getnew.o lttnew.o datnew.o cc mainew.c palib.o -lc -la rm *new* mv a.out /lib/ppass2 : get some other sources from tape 0 tp xv0 share.c pclist.c pc.c pcompiler.i : generate share (used to make a program shared) cc share.c ; mv a.out share ; rm share.c : generate pclist cc pclist.c ; mv a.out /lib/pclist ; rm pclist.c : generate pc cc pc.c ; mv a.out /usr/bin/pc ; rm pc.c : make BSC code of the compiler SC code pc -2 pcompiler.i ; rm pcompiler.i : get the sources from both interpreters from tape tp xv0 pi0.as pi1.as pi2.as pi3.as pi0sh.as tp xv0 pi0pc.as pi1pc.as pi2pc.as pstore.as : generate the interpreter library as pi0.as ; mv a.out pi0.o ; rm pi0.as as pi0sh.as ; mv a.out pi0sh.o ; rm pi0sh.as as pi1.as ; mv a.out pi1.o ; rm pi1.as as pi2.as ; mv a.out pi2.o ; rm pi2.as as pi3.as ; mv a.out pi3.o ; rm pi3.as ar rv pilib.o pi0.o pi0sh.o pi1.o pi2.o pi3.o rm pi?.o pi0sh.o : generate the compiler library as pi0pc.as ; mv a.out pi0pc.o ; rm pi0pc.as as pi1pc.as ; mv a.out pi1pc.o ; rm pi1pc.as as pi2pc.as ; mv a.out pi2pc.o ; rm pi2pc.as ar rv pipclib.o pi0pc.o pi1pc.o pi2pc.o rm pi?pc.o : generate the compiler share pcompiler.b pccc.as ; rm pcompiler.b share as pccc.as ; mv a.out pccc.o ; rm pccc.as as pstore.as ; mv a.out pstore.o ; rm pstore.as ld -n -u ppc pipclib.o pccc.o -la pstore.o mv a.out /lib/ppass1 rm pccc.o : generate the interpreter ld -n -u pi pilib.o -la pstore.o mv a.out /usr/bin/pi rm pstore.o ********************************************