@make(ptreport) @device(dover) @font(timesroman10) @Define(Ins,Break,Continue,Above 1,Below 1,Fill,LeftMargin +1.3 inches, Spaces Compact,Indent 0,Spacing 1) @string(ptgdno="SYS.18.01") @begin(titlepage) @document(A Machine-Independent MDL Design Document) @author(Marc S. Blank and Chris Reeve) @date(@value(date)) @end(titlepage) @pageheading",Right="SYS.18.01"> @chapter @section There are a number of possible approaches to re-implementing MDL on various processors; the one chosen for this design is to create a virtual machine running a language called MIM (Machine-Independent MDL). The approach is analogous to that taken with Pascal in that MIM is either an interpreted or compiled language, and interpreters or compilers must be written for each target machine. MIM code will be generated from MDL code by a process called MIMC (the MIM compiler, pronounced mimsy), which will be written in MDL. At the point that an Apollo-MIM (for example) and MIMC are operational, a MDL interpreter written in MDL (called MUM) can be compiled into MIM. MIMC, which will also be written in MDL, can also be compiled into MIM, thereby providing both an MDL interpreter and compiler running on the Apollo. It is also proposed that an order-code compiler for the various target machines be written, to 'open-code' MIM into target machine languages, with an increase in speed traded off for an increase in code length. While MIMOC (MIM Order Compiler) may well become a necessity for runtime systems, it need not become operational for writing, running, and debugging MDL code. A major difference between Pascal P-CODEs and MIM M-CODES is that the latter are in themselves a high-level language, with machine instructions which handle such things as RESTing structures, creating structures, etc. Therefore, very little information of a machine-dependent nature is stored in MIM machine code. By keeping MIM relatively independent of target machine design, better target machine code can eventually be produced by the MIMOC process. @section MIM (Machine-Independent MDL) is designed to enable the MDL language to be rapidly implemented on a variety of machines. Although the language specification is 'machine-independent', it is nonetheless designed with 8/16/32/36 bit processors in mind. In the design of MIM, the goal has been to extract those features of MDL which are 'primitive' and to make those 'primitives' machine instructions. Thus, the MIM machine must understand the concept of an MDL object, MDL structured primtypes, etc. However, it is clear that most of the MDL SUBR/FSUBR's are composites of 'primitives' and that in fact few of the MDL SUBR/FSUBR's need be implemented as machine instructions. For example, MEMQ need not exist given NTH, REST, and ==?. More difficult questions have involved such issues as whether READ can be written efficiently in MDL given only READSTRING, and how much of the ATOM/OBLIST system can be written in MDL. @chapter @tabclear<> @tabset<1.3 inches,2.5 inches> @section Each MIM instructions takes a number of arguments and a destination designator for the result if any. The arguments to a MIM instruction can be either local variable names or quoted MDL objects. The result of a MIM instruction can either be a local variable or the atom STACK which directs the instruction to leave the result on the stack. In describing the instruction set the following convention will be used in denoting operands: @begin @i @end where @i is one of local or any (meaning either a local or constant) and @i indicates the legal value(s) for that operand. @section Some MIM instructions are predicates. These all have mnemonics which end in a question mark (e.g. EQUAL?). These instructions are all followed by a + or - to indicate whether the branch should be taken if the predicate is true or false. After the + or -, the branch label occurs. @section MIM has a few internal variables, which may be read and set. These variables should not be confused with global or local variables in MDL. They are more like MIM state variables. @begin MINF - a UVECTOR of information about the machine on which MIM is running PAGETB - a UVECTOR of information about the address space available to MIM BIND - the most recent binding on the STACK FRAME - the current FRAME ARGS - the number of arguments to the current FRAME OBLIST- the global atom-table ICALL - the @b(MSUBR) to CALL when an interrupt occurs ECALL - the @b(MSUBR) to CALL when an error in order-code occurs NCALL - the @b(MSUBR) to CALL when a non-globally-assigned @b(ATOM) or an @b(ATOM) whose global value is not an @b(MSUBR) is CALLed @end The last three internal variables are intended to be set once during initialization of the MDL interpreter. Extreme caution should be used when setting the BIND, ARGS, FRAME, and OBLIST variables, as these are used internally for @b(MSUBR) CALLing, etc. @section A MIM object is a 64-bit or 72-bit structure which is roughly equivalent to the PDP-10 MDL type/value pair. A MIM object contains the following items: @begin Type Word - 16 or 18 bits specifying the type and primtype of the object. See @i. Length Word - 16 or 18 bits. See @i Value - 32 or 36 bits, a pointer for structures or a value for non-structures. @end @section The unit of executable MIM code is the @b(MSUBR) (@b(M)dl @b(SUBR)outine). This has a format as diagrammed in @i. Briefly, an @b(MSUBR) is a primtype @b(VECTOR) which contains a pointer to an @b(IMSUBR) which is a primtype @b(VECTOR) and contains a pointer to runnable MIM instructions (a primtype @b(UVECTOR) of type @t(MCODE)), as well as other MDL objects used by the @b(MSUBR). By convention, the second element of the MSUBR is its name (an @b(ATOM)), the third is the type declaration for the MSUBR (a @b(LIST)) and the fourth is the offset into the MCODE where the code for this MSUBR starts. When an MSUBR wants to reference an MIM object, it refers to an offset in the IMSUBR. The CALL instruction makes the MIM program counter point to the appropriate element of the @b(MCODE) for the called @b(MSUBR). @section MIM has a stack (referred to as the STACK) which is used for MSUBR calling, bindings, local variables, temporaries, etc. All items on the STACK are either legal MIM objects (i.e. 64-bit structures) or structures placed there by MIM instructions (e.g. FRAME, BIND). @chapter @section MIM has instructions for placing objects on the STACK (PUSH) and for removing objects from the top of the STACK (POP). In addition, the instruction ADJ adjusts the STACK pointer either forward or backward by a given number of MIM objects. MIM local variables (located on the STACK) can be set with the various SET instructions to either the value of another local variable, a slot in the @b(IMSUBR) or a constant. @section In order to transfer control from one @b(MSUBR) to another, a STACK @b(FRAME) must be created. This is done using the FRAME instruction. Such a @b(FRAME) will contain enough inforiadio, to$anlow DrMCUBThBet5xls,mulpip|d`6etur.1, !nd`MDL)style AGAIN." NLe the@v FAOE is btHnT, the argumenlc un dhe @b(MFBR)(HiF@aFy avE USId$ Knto thE QTACJ. `TIenL tam A L ivsTruwtyn is!ayEcetem.  Hgsekc an`a{`)mT(mf`tie0usg (iF`II awSmlbmq Da~gqege novatinlion 5(D cAM instbugtinn: @bggin  ('` `( 0 $` ; cre`tm` ctack Dramm ` ` " 0 ! (push!th hocil v`riablM DO  @` H)&(6 5438({ z)0D(C B     x:(t sr %A (?f AG$ D [@ - 56 5du \C`X' .LG \CO4= \Dwu (X| \|Pd U 4zc  m:  Oi< l M[ u M` R 8 ^ \ KyPM M` ~s?& e,< +M Q7P_ D^ D^+ D^9 `; Y]c" \D%:$ >/g0. KyP4 T0C (IQ |Tm "QO8$rnal representation of the various structure classes. @section MIM supports the concepts of @b(ATOM)s and bindings. This is necessary in that a completely external simulation of atomic bindings would be unreasonably expensive without some knowledge in the interpreter of their structure. A STACK binding (type LBIND) is created with the BIND instruction. BIND does the following: @begin(itemize) Creates an LBIND and places it on the STACK Points this new LBIND to the previous LBIND on the STACK Updates the internal pointer to the most recent LBIND to be the one just created. @end(itemize) Code inside MUM does the remainder of the binding process, including pointing the LBIND at the ATOM which is being bound and placing values and declarations in the LBIND. Additionally, an LBIND for a given ATOM is pointed to the previous LBIND for that ATOM. A number of MIM instructions perform 'unbinding' of @b(ATOM)s (e.g. RETURN, RTUPLE, and AGAIN) back to a given FRAME. The steps in 'unbinding' are: @begin(itemize) Remove the LBIND from the STACK Update the internal pointer to the most recent LBIND to be the previous LBIND (as saved by the BIND instruction) Update the LBIND slot of the ATOM pointed to by the LBIND to be the previous LBIND (if any) for that ATOM. @end(itemize) @section It is intended that MDL have two garbage collectors, a mark-sweep garbage collector, and a full-copy garbage collector. MIM instructions for both are included in this document. @section In order for any @b(MSUBR) to run, it is necessary for MIM to have 'read' that @b(MSUBR). Therefore, MIM must include a primitive MDL reader, which must be capable of parsing the following MDL data types: @b(IMSUBR), @b(MSUBR), @b(MCODE), @b(ATOM), @b(FIX), @b(FLOAT), @b(STRING), @b(VECTOR), @b(LIST), and @b(CHARACTER). By convention, the file BOOT.MSUBR contains the bootstrap routines for loading a MDL. The BOOT file is a sequence of @b(MSUBR)s. MIM must read these @b(MSUBR)s and SETG the names of the @b(MSUBR)s accordingly (by convention, the name of an @b(MSUBR) is the second element of the @b(MSUBR)). Execution commences with MIM CALLing the @b(MSUBR) named BOOT. @chapter @section @b(MUM) (@b(M)DL @b(U)nder @b(M)DL) is the name given to the MDL interpreter which is written in MDL. In most respects, MUM/MDL will be identical to the current PDP-10 and TOPS-20 MDLs. @b(MUM) will, however, include some capabilities not found in the older MDLs. @section The new MDL interpreter (@b(MUM)) is composed of individual speCialty modules (e.g. PRINT, READ, ASOC, ARITH). Each od these modules consists of`@b(MSUBB)s, as wnulD any other piece of user-code'. The result is that the`distinction`between interpreter And 'user-code' `as become blurrmd. To tie casual MDL user, thE interpreter will probably appear lareer than $ib-YB 10 version, because some parts of the MDL environment will be included. However, to the production-systems prWS^itSK` wsY^ eaS`t I_BexGldeQCy_lFalhZf QJ MY imiHrpEKlerA]bomAEHinNAXoaYKJ, YK@vimNBa G[@llKdFanHABlec]Nr Wsbte:\ efec S^n>)M S[dlekK^taSZn>J @QTOjS` aeJFstekFtuEKd w\AbriKitpeRZRDRAlit`AJouDALlmsKZdsTAF IFalQAVnd]H (DPLBS ))AD gIBalQEVnd]H (DPGBS ))PAB pCXe $Qb)"INNRP,!S]H aAb(/ISXVX ECierQ_H taJ@fiegh!t^Belc[NntABanZDlsN@e Ab(]EBXFinYSGctS]H tQCh!tQK`e!CfFnoQY\caA^r Y\baXbi]IPNg\D@b!LIW Ts aCje IQR scSJ siejctkeH aCb(c)M)V\B L_iH tCh DRATOQs G]N @QBLC',)sQCde ]_bmAHAIMAgjruginreFAhhiWPDcaABE e[PniAkXatKHDasQC`e OiPerAgjrugihreV\F TQSfaIYXwsCXl  !"oo@ support for @b(AT_M)s and @b(OBLIST)c to Be wsitteN in MDL itself whth calls to NTH, REST, etc. The BIND instruction creates and returns an @b(LBIND) ol the STACK. There is no need for a GBIND instruction, as a @b(GBIND) can be created with the RECORD instruction. As with @b(ATOM)s, @b(LBIND)s and @b(BIND)s are primtype @b(RECORD)s which can be manipulated; thus, the SUBR's SET and SETG turn into PUTs, asdoH@ DECL, and GDECL. @section @b(FIX) is the only non-structured MIM primtype,!replacing the primtype WORD in the current MDL. All bitwise operations take any primtype @b(FIX) and return a type @b(FIX). The aritHmetic iNstructions take either pairs of @b(FIX)es or @b(FLOAT)s and return objects of the same type. @section MIM provides a very primitive I/O interface, which consists of OPEN, CLOSE, and ctring read/print. The MDL conversion I/O SUBRs (READ, READCHR, PRILT, PRIN1, PRINC, PARSE, and UNPARE) have all been written uskng only these operapions. Block-iode I/O SUBRs (PRINTB( READB, PRINTSTRING, READSTRING) can also be!easily incorporated hnto this scheme.  While these SUBRs cover mcNy MDL I/O applIcations, snme others will nEed tn belevised. Akong these is some form of core-image I/O, which would provide fast, non-parsed I/O, and some machine-independent MDL I/O scheme, which is being devised by an undergraduate at the present time. The SAVE and RESTORE instructions provide the means for saving and restoring a core-image, and is used mostly in the creation of large subsystems. @section There is no support in MIM for associative storage as implemented in the existing MDL. However, such a scheme has been implemented in MDL. @section There is no coroutine/multiprocess facility in MIM. The major issue that coroutines encounter is that of the STACK, whether there should be one for each coroutine, etc. The possible inclusion of this concept into the design of MIM will be considered at a later date. @section MIM has a very primitive interrupt system which interacts with a rather sophisticated software interrupt system written in MDL, and based on the old MDL's interrupt system. When a non-emergent interrupt is received by MIM, MIM CALLs the @b(MSUBR) specified by the SETS ICALL instruction with one argument, a @b(FIX) between 0 and 35, which is the unique identifier of that class of interrupt. To allow for terminal interrupts, the MIM instruction ATIC (Activate Terminal Interrupt Character) takes a @b(CHARACTER) and returns a @b(FIX) which is the unique identifier for a terminal interrupt on that @b(CHARACTER). Emergency interrupts (stack overflow, illegal memory read/write) may require MIM to take some emergency action prior to CALLing the software interrupt system. Naturally, these interrupts are somewhat machine-dependent, and will have to be dealt with for each target machine. l @chapter @section @begin @b@\@i @begin The PUSH instruction @i its operand onto STACK. The special destination STACK for other instructions is another of placing objects on the stack. @end @b@\@i @begin The POP instruction @is the top element from the STACK and moves it into a local variable. Calling an MSUBR also removes the arguments from the stack. @end @b@\@i,@i @begin The various SET instructions set a local variable to the value of another local variable or a constant. The use of local variable as destination also causes a SET of that variable to occur. @end @b@\@i,@i,@i @begin Sets local variable @i(any1) in the current frame to the value of local variable @i(any2) in @i(frame). @end @b@\@i,@i,@i @begin Sets local variable @i(any1) in @i(frame) to the value of local variable @i(any2) in the current frame. @end @b@\@i @begin Adjusts the STACK by @i objects, positive indicating @iing and negative indicating @iping. @end @b@\@i @begin Creates a CALL @i on the STACK. @end @b@\@i @begin Returns the running @i. @end @b@\@i @begin Returns a TUPLE with the arguments to the @i. @end @b@\@i @begin Returns a TUPLE containing @i elements from the top of the STACK. @end @b@\@i @begin The return instruction which follows will cause values to be returned to @i. Unbinding will occur back to @i. @end @b@\@i,@i @begin Starts execution of an MSUBR. This instruction must follow the creation of a FRAME and the PUSHing of arguments. If the global value of @i(atom) is an MSUBR, execution starts immediately. Otherwise, the NCALL routine is executed. @end @b@\@i @begin Builds a FRAME and performs a 'CALL' within the current MSUBR. This is useful for PROGs and REPEATs that have external ACTIVATIONS that maybe RETURNed from or AGAINed. @end @b@\@i,@i...@i @begin Builds and returns a TUPLE out of the arguments passed to an MSUBR. The arguments are the temporaries used in the MSUBR. @end @b@\@i @begin Saves the current offset into the MSUBR as the 'activation' for the current FRAME. @end @b@\@i @begin AGAIN restarts execution of the MSUBR running in @i from the offset specified within that MSUBR by a call to ACTIVATION. Unbinding will occur back to @i. @end @b@\@i,@ @begin Performs a CALL return with value as specified by the operand . The second argument is optional and defaults to the current frame. Unbinding for will occur. @end @b@\@i @begin Performs a CALL return with any number of values, which have been PUSHed onto the STACK, and whose number is specified by @i, returning as the top of STACK a @i pointing to the return values. @end @b@\@i