rA.7uA0%mEJLY@,(+9F7HKoe|Zv( t]7Ho#H]&`$j7PvThe following two sections are partially drawn from a paper in the Proceedings Of The 1979 MACSYMA Users' Conference, "NIL: A Perspective", by Jon L White, and from an internal status report prepared Jan 15, 1981. Currently associated with the project are Richard L Bryan, Robert W Kerns, and Jon L White. ________________________________________________________________________ Brief Overview of the MIT NIL project NIL is a "New Implementation of Lisp"; it is a modernization of LISP suitable for implementation on any of the current generation, large-address space, standardly-available computers. The design is intended to be the best machine-independent lisp possible, and thus no facilities are presumed which would require special purpose hardware for efficient operation (such as "cdr-coding", or "bit-map raster display"). Rather, the language will expose in the higher level more of the capabilities which are common to nearly all of the likely target machines -- such as typical computer arithmetic, string and character manipulation operations, objects with indexed-access structure in addition to linked-list-access, and so on. Major goals are: a) To be maximally upwards compatible with MacLISP, and absorb enough of of the LISPMachine's facilities so as to enable most non-system programmers to run their applications in either environment (in particular, the non-I/O oriented parts of programs should be compatible with trivial effort on the programmer's part). b) To provide a rich set of primitive data types, which will reflect capabilities of typical off-the-shelf computers, and also to provide a general user-extensible mechanism for new data types (going beyond the capacity of ECL, for example). c) To build NIL in NIL, not merely as a curiosity, but to demonstrate the feasibililty of building an operating system in NIL itself; and to make it easier for the end LISP user to tailor the system to personal requirements. The non-LISP kernel, called the "VM" for Virtual Machine, corresponds roughly to the micro-code complement in a special purpose lisp machine. We will build "VM"'s on several different machine environments, in order to gain experience in generalizing what are the basic primitives needed. d) To build an EMACS in NIL; To build MACSYMA in NIL. A very usable EMACS has been built under Multics MacLISP, but suffers from an efficiency problem and a proprietary interest limitation (by Honeywell). MACSYMA has already begun the slow process of abstracting out much of the old code, during the re-building of it under Multics MacLISP and the LISPMachine (and significant pieces of it under Franz Lisp). Thus the overall performance of NIL must be high enough so that these systems can be competitively supported. e) To provide "object-oriented" programming as an adjunct to standard lisp recursion style. Message-passing semantics has been seen to be the "right" way to think about certain problems, but we feel that it is not a panacea, and thus its provision in NIL will not ubiquitously displace standard lisp capabilities. f) To provide a peak-performance compiler, with modes of "partial compilation". For example, in one mode, the output is a truly machine-independent code called LLCODE (for Linearized Lisp CODE), which could be supported by micro-code (but surely won't be, since the VM design would be more aggressive when a real micro-code option is available). Generation of actual machine instructions from LLCODE permits a number of compile-time choices (see below under "Some compile time options ..."), but in general there will be no need to do "block compilation" in order to achieve efficiency, as most such options can be successfully delayed until runtime. g) To cooperate with similar efforts in reducing the low-level differences between dialects, so that a nearly-complete implementation of many existing lisp systems can be done in "piggy-back" fashion on top of the NIL kernel and support code. h) To actualize the implementations on the VAX computer, on the extended- addressing PDP-20/80, and on the Nu machine (a personal computer project to be undertaken by the Laboratory for Computer Science, which was to be based on a MC68000 micro-processor, but which has been postponed due to contract failure with the initial hardware supplier). Where the operating system supports it, the compiler and assembler produce sharable, read-only object segment in the file system which the loader merely "maps" in and links up; in the VAX implementation, we will have a dynamic loader also for FORTRAN object files, with a relatively efficient interface between LISP and FORTRAN compiled code. i) To provide the basis for continued development, as new ideas come forth. The M.I.T research environment is a continuously active one, so a major consideration of NIL is to provide a vehicle for experimentation with all the new ideas cropping up in the worlds of AI and of Programming Languages. In particular, the data type EXTEND, which is essentially a VECTOR (that is, indexed-access block of S-expressions) with a link to a type-descriptor, has been a general enough mechanism for us to experiment recently with several different message-passing protocols, since the VM design allows a slot in the type-descriptor for the user to provide a "message-sending" interpreter. We have decided upon a typed-pointer scheme rather than segmenting the address space into chunks of homogeneous data types; as a consequence, memory management calls for a "Stop-and-Copy" garbage collector rather than the "Mark-and-Sweep" variety. Additionally, storage will be divided into a static area and a living area; normally, the GC will only reclaim addresses from the living area, but under explicit user invocation, a "hyper" GC will reclaim also from the static area (such a split has been found to be of paramount importance in reducing the memory management overhead in PDP-10 MacLISP.) We have a very efficient method of achieving the kind of limited FUNARGs known as CLOSUREs on the LISPMachine; and we have provided for the future installment of a co-routine facility similar to the "stack-group" of the LISPMachine. We have rejected the spaghetti-stack model of control in favor of CLOSUREs and co-routines. Some compile time options during the generation of actual machine instructions from LLCODE are of interest to the user. In particular, the choice of data access (such as CAR/CDR's, i'th character of string, array referencing and so on) is determined by a switch to be one of: e1) closed-compiled, with a "mini" subroutine call so that all operations may be certified for application to proper data. This option will likely offer a speed improvement over interpretation of between 5 and 10. More importantly, it will allow one to experiment with variant storage methods; in particular, one can try out various "real time" or "incremental" garbage collection methods merely by modifying the "mini" subr which implements the data access. e2) open-compiled, with a few instructions for data-type certification installed before the actual data access This option will offer a speed improvement over the closed option of between 2 and 4 (and thus over interpretation by 10 to 40). Significant pieces of semi-debugged user code may want to be compiled in this way. e3) "fast, open-compilation", as currently happens with PDP-10 MacLISP; this "speed first" option makes no guarantees about what happens when an operation is applied to an inappropriate datum. This will offer a speed improvement over (e2) of possibly a factor of 1.5, and will also produce significantly more compact code. This will be the option for secure, debugged code. A message-passing protocol is being built which will be at least upwards-compatible with the "Flavor" system of the LISPmachine. One feature of importance to NIL user is that the "inheritance hierarchy" is flattened at a compilation and flavor-composition time, so that no time-consuming search through a tree of super-classes need be made at invocation time. Quite likely, message-passing will be only slightly slower than functional invocation, even where there is no special hardware support for such operations. Current Operational status, and future plans: Since early 1979, a large body of "compatible" software has been built up, in which the same source files serve as both NIL and MacLISP system code. Portions of this body of code have been compiled and run on the LISPmachine and on Multics MacLISP to demonstrate its machine-independent nature (the LISPMachine's own body of code development supplies many of these utilities, in a "compatible-in-spirit" form, and though there seems to be no advantage to sharing code between projects, there is still a degree of design cooperation). By early 1980, a "piggy-backed" version of NIL was running on top of MacLISP. Using this emulated NIL environment, we developed some VAX-specific tools -- assembler and compiler -- and were able in May of 1980 to demonstrate pieces of the whole system running on the VAX. By late summer of 1980, we had a "toy" interpreter running on the VAX, despite lingering bugs in the VM support. Following this section is a more extensive progress report which was prepared in mid-January 1981. A new LISPMachine manual is on the press right now, and a comprehensive MacLISP manual will be press ready by June 1981. These two manuals will serve the initial need for a NIL manual, with a modest sized pamphlet detailing the differences and limitations of NIL from its "friendly cousins". Also by June 1981, a pilot version of the NIL system for the VAX, running under the VMS operating system, will be ready for some non-antagonistic testing/usage by selected sites. During the summer, we will continue to replace parts of the system which currently are serving as "scaffolding" for our work, but which are not in final form. Later this year, we will begin a true NIL implementation for the extended-addressing PDP-20/80 (as opposed to the "piggy-backed" version running in the 18-bit address PDP-10). Plans for bringing NIL up on a micro-processor are somewhat nebulous right now, due to postponement of the Nu project, and to manpower shortages. NIL will be a fairly large system, approximating an operating system in scope, and will itself require a large segment of memory/address-space; but an important feature of the NIL design is the dynamic linking of position-independent code modules from the file system, much the way Multics object segments are linked up, and this will increase the mutual sharabililty of all code segments. This will be important when there are several different applications, each built on top of a NIL, running on the same VAX (currently, only DEC's VMS operating system permits us the flexibility for the sharing of dynamically-linked code, and we are indeed doing this, but the Berkeley UNIX may soon supply this capability too). Because of the high degree of sharing of the read-only code-segment files, We expect to be able to run several (3 or 4?) simultaneous users of a large applications (such as MACSYMAs, NIL-based text editors, etc) on the VAX 11/780; jobs would be incrementally sharing disk pages even when they were not initiated from the same "dump" file. ________________________________________________________________________ Current Progress on the NIL System, and on the VAX Implementation of It Jan 15, 1981 In May of this past year, we demonstrated certain pieces of each component of the system as being in operation, but as a whole it wasn't debugged enough to run even a toy LISP system; in mid August, we demonstrated a "toy" LISP system, which had some of the rudiments necessary to a typical LISP (mini-reader, partial EVALuator, and mini-printer). Even though this system was at a "toy" level, it did help us find many bugs in each component of the system -- from the compiler/assembler to the "virtual-machine" code -- and a good deal of debugging at each level has proceeded since then. We are currently still cross-compiling and assembling from the NIL emulator systems running on the PDP10, and may be in this mode for another four months. Between mid September and mid November, we re-structured our PDP10 emulation environment, partly to help extract from it a more implementation-independent body of code, and partly to reduce the size of our "piggy-backed" system (the NIL emulator runs "on top of" the PDP10 MacLISP system). Since NIL intends to incorporate into its runtime system a large measure of the MIT LISP Machine environment, this has severely impacted the addres space available on the 18-bit PDP10. [The MIT LISP Machine will henceforward be referred to as merely "LISPM"]. On a component-by-component basis, our current status is: VM ("Virtual Machine") Certain facilities are presumed to exist for the runtime environment of NIL; with a very flexible micro-code structure, one could put most of these facilities into micro-code, but currently we have no plans to put any of them into micro-code on the VAX. Typical of such items are data-accessing primitives which, at runtime, certify the correctness of the data type, primitive dispatch for the interrupt system, primitive i/o routines, primitive error service, and a cold-load startup routine which sets up an initial stack and initial dynamic storage areas. The Vax NIL also contains VAX debugger, and some additional LISP-oriented debugging routines. Many of these functions are called "minisubrs", due to the fact that when not microcoded, they can be called out-of-line using whatever fast, non-recursive subroutine facililty is available (JSB seems to be the only candidate for the VAX). Some of the mini- subrs are "essential", in that the correct compilation of some piece of code will require them; others are "inessential", in that they will be used only when the user requests, by means of a compiler switch, full error checking in the runtime code. Currently, the VM consists of a motly collection of BLISS-32 code, and of a macro-assembler code which must be pre-parsed and converted into MACRO (we do this in order to fill in what we percieve to be the gaps of VAX MACRO). Although there are more than 15.K lines of this kind of code, one of the members of the group has been working on a lisp-coded data base which would permit the mechanical generation of most of the minisubrs and of the initial data tables; this should help the conversion of this code to run under UNIX (if necessary). ASSEMBLER/LOADER The NIL-assembler for the VAX, written entirely in the NIL language, is working fairly well since about July 1980. It is a non-macro, symbolic assembler, with a few pseudo-ops, and this is adequate for a "lisp" assembler. Current faults are mainly that no Jump-optimizations are being done -- all forward-branching jumps are "longword", and conditional jumps are done by conditional branches around a jump -- and that some PDP10 dependencies may remain. The assembler produces a byte-image file, which is then packed into a bit-stream suitable for file-transfer from the PDP10 to the VAX; one part of this file is like a "program section", in that it represents position-independent, read-only instructions; another part is for storing LISP s-expressions, which have to be "relocated" upon loading. Since instructions do make reference to this "s-expression" data, there is no way to use the linking-loaders of other VAX systems. The loader is written in BLISS-32, and ultimately the intention is for it to page-map in the read-only pages of a file, to gain sharability among multiple users, but currently it is merely inputting these pages. Although the i/o usage of the existing loader is VMS dependent, it should be possible to transcribe it fairly straightforwardly into any other VAX operating system (such as UNIX). Hopefully, someday, we would like to do what the group at Xerox's Palo Alto Research Center have done -- write the loader in NIL itself, and bootstrap a "cold-load" system by running in a "shadow" mode of the NIL emulator (which of course would be running on the PDP10). COMPILER(s): By May 1980, a primitive versison of an incremental NIL compiler had been coded; it is incremental in that it first produces a generally machine-independent code called LLCODE (acronymic for Linearized-Lisp-CODE), which is somwhat akin to the basic output of the LISPM compiler. LLCODE is then converted into LAP (the machine-language for the lisp assembler mentioned above) for the VAX by an independent module which is much like a second compilation phase (hence the appelation "incremental compiler"). By mid-August, this compiler had been completed for the full NIL language, with some work left to do on the optimization of registers during the generation-of-LAP phase. One member of the project began, in early April 1980, the conversion of a partial NIL compiler built for the S1; this compiler was experimental and uses a strategy of compilation outlined in Guy Steele's master's thesis; another member of the project joined this effort in mid May, and by mid August, a subset of the NIL language could reliably be compiled for the VAX. The particular optimization strategies of this, compiler, while interesting from a theoretical point of view, quite likely have very little, if any, payoff on the VAX (since it has a fairly large memory cache), and under the NIL function-calling sequence (since it uses the VAX CALLS instruction. Consequently, interest in furthering this compiler has waned; but out of its "ashes", one group member, by mid-December, had distilled a slightly-more-comprehensive but very simple, stack-machine compiler which he is using as an working tool. EVALUATOR The "toy" interpreter mentioned above was unduly restricted due to bug in the "Virtual-Machine", especially the failure of the module which does the dynamic function-call transfer (i.e. given the symbolic name of a function at runtime, create a subroutine call to it, with the arguments put into a stackframe). As many of these bugs have been caught and corrected this fall, a more comprehensive evaluator has been tested out now (Jan 1981). By June 1981, an evaluator of the general capability of MacLISP will be available -- but of course all written in NIL itself. Our future plans call for an evaluator which has a fast, lexical-variable scheme; the structure of this idea has been worked out by one of us, but it is not of paramount practical importance now (it will follow some of the ideas of the SCHEME language designed by Gerry Sussman and Guy Steele). RUN TIME ENVIRONMENT The NIL "environment" is much like a subroutine library, along with a mixture of interpretive/compiler-oriented aids. A large part of this environment is inspired by the LISPM's environment, and is sufficiently rich that most programs written for the LISPM will run under NIL (major exceptions are, of course, I/O specialties the newer, experimental parts of the CLASS system). Fortunately, this library is about 90% written in a compatible subset of NIL so that it forms the basis of the NIL emulator on the PDP10 -- thus it has been possible to develop extensively and debug this code on the PDP10. It currently consists of just about 10.K lines of rather dense NIL code, which is source-compatible for use either by a native NIL (such as on the VAX), by MacLISP on the PDP10, by the LISPM, and (eventually) by MacLISP on Multics. LISP DEBUGGING AIDS Very little has been coded as of Jan 1981. Plans call for a stack- analyzing tool similar to that available in MacLISP and INTERLISP; Each compiled function will eventually also contain a "road-map" so that variables which are stack-allocated by the compiler may be referenced by their original symbolic names. [note: by March 1981, a fairly impressive amount of one of the MacLISP stack debugging tools had been brought up on the VAX; nothing has been coded for the "road-maps" however.] NILE An EMACS editor, written entirely in NIL, has been developed by an MIT undergraduate student, who also did a significant amount of work on the Multics EMACS (written in Multics MacLISP). This system has been running, after a fashion, since December 1980, under the NIL emulator on the PDP10. Possibly new problems will arise when it is brought up on the VAX, since a major feature of it is its interactive use of a CRT screen. CLASS SYSTEM Perhaps the most exciting, innovative idea in programming languages now is that of "object-oriented programming"; a first-version of this technology was implemented for the piggy-backed NIL in the spring of 1980, and major improvements were done during November and December 1980. Support for "message passing", a fundamental operation in such systems, has been provided in the VAX VM, and in the compiler, but more work is needed to get the most recent system to be free of PDP10 dependencies -- hopefully this will be done by the end of March 1981. Our goal is to be at least modestly compatible with the kinds of usages available on the LISPM, and this will no doubt mean continuing development, since this whole area of endeavor is somewhat new. A record-structure facility, called DEFVST, has been completed which depends (partially) on having a CLASS system available -- by connecting each structured object into a "class", or "sub-class" of objects, there is full extensibility at runtime. DEFVST is entirely written in NIL -- only the low-level "class" support must be provided by the compiler and VM.  May 8, 1980 How did the NIL demonstration to DEC go yesterday? Well! We presented less than we had hoped for (I, at least, foolishly expected to be able to compile and run DISPLA), but they demanded less than we had imagined. We reviewed the overall design, and then demonstrated the steps, beginning with the PDP10 emulation base, of compiling a few small programs into LLCODE with the current NIL compiler, assembling them with the NIL assembler into a "VASL" format, and then loading them into our "Virtual Machine" on the VAX. A loop of READ-COMPUTE.FACTORIAL-PRINT even sort of worked. In another two weeks, we'll be able to do exponentialy more. The major amout of design/coding has been done, and now its just a matter of further debugging along the various parts of the pathway in order to see the entire system translplanted to the VAX. Our Sales representative showed up too, and asked more questions than anyone else. Of course, they asked about time estimates for "release" versions, and we predicted 2 months for the "pilot", meaning that there is good reason to believe that we'll be shipping out a semi-workeable version to knowledgeable sites sometime in June ("knowledgeable" means that the site would be able to give us some feedback on observed bugs). Also the sales representative was concerned about follow-through, and we presented two aspects beyond that of continuing software maintenance: (1) development of things now "on the back burner", such as CLOSUREs, CO-ROUTINES, compiler optimizations etc., and (2) implementation on other hardware. At least, I hope we'll have the resources to do these things, although understandably DEC would be less concerned about the latter. We mentioned, of course, that we expect to modify our Virtual Machine to run under some version of UNIX on the VAX -- hopefully before late fall of this year -- but that has taken a back-seat to the task of getting a generally-debugged system going in the first place. Three hacker types from DEC showed up and were suitably bedazzled with the array of software. They's been playing around with a version of the Delphi LISP on the VAX, and after seeing some of the stuff running here were moved to want LISP for their own research/development, especially because of the debugging environment. A point we made was that a proper design of the basic LISP allows much more friendlier debuggers to be written, in LISP of course, and they appreciated that. Bob Kerns showed them some sample "toy" uses of the CLASS system (under Maclisp) - probably we should develop more and better demonstrations of that, since "data abstractions" seem to be the big thing now and since their "flavourfulness" will be a strong point for NIL (see Jim Purtilo's paper in current SIGSAM bulletin). One question concerned speed, and as it was asked about "the interpreter", we had to bring out Occam's razor to show the difference between the protion (and relative unimportance) of the EVAL/APPLY function as compared to the runtime support system, which we've been calling the VM ("Virtual Machine") and which for the LISP Machine is the rather extensive set of special microcode. We mentioned the tests done by Rich Bryan and myself which seem to show the VAX to be inherently about 40% to 60% as fast as the MC KL-10 (long discussion of relative timings is in a file MC:JONL;VAXIMA TIMES - collection of RLB's data, LISPM versus KL-10 Macsyma timings, and comments on "Vaxima" timings). The related question of memory requirememts was also brought up. We volunteered information (and opinion) that 1 Megabyte would probably be enough to run a demonstration system, suitable for teaching LISP, but due to the sheer size of most interesting applications, that more that 2 Megabytes would be needed. NIL will be a fairly large system, approximating an operating system in scope, and will itself require a large segment of memory/address-space; but an important feature of the NIL design is the dynamic linking of position-independent code modules from the file system, much the way MULTICS object segments are linked up, and this will increase the mutual sharabililty of all code segments. This will be important when there are several different applications, each built on top of a NIL, running on the same VAX; although most operating systems on the VAX would permit the sharing of a single application program, only VMS permits us the flexibility for the sharing of dynamically-linked code, and we are indeed doing this (but the Berkeley version may remedy this situation for UNIX). We volunteered the conjecture that a reasonable NIL system on a 4-Megabyte VAX would support 5 simultaneous MACSYMAs, which would make the VAX a bit more powerful than a KA-10; this is a non-trivial observation, since a modern LISP design, such as NIL is, must be inherently slower (in some relative sense) than Maclisp on the PDP10, due to the necessity of properly utilizing a large address space, say of at least 32 bits (PDP10 Maclisp is limited to 18 bits). Unknown to me beforehand was Rees's comment that the NIL project now has accumulated about 25000 lines of Code; of course, I would add a certain expansion factor because our coding style here is highly macro-ified (for example, the compiler accounted for less than 6K lines of code, I believe, but it results in 16K resident instructions and 40K resident database produced by a non-resident program). They also asked about cooperation with other LISP projects around the community: the degree of portability of NIL software, and the amount of code sharing with other projects. I had to mention that we were able to take some LISP Machine code and transform it for NIL (notably, the user- interface to the error handler and the "package" system), and also that I thought FRANZ was able to take almost all of the NILCOM software without much trouble (this is NIL system code which is written in a "common" subset so that it maybe used on any Maclisp-like lisp - such as the LISP Machine and Multics Maclisp). But as yet, there seems to be nothing that the LISP Machine people want from NIL, and nothing yet we are able to get from the FRANZ group (in the line of portable LISP code, that is - I'm not referring to use of the whole system.) Additionally, we expect to share some code with the S1 NIL effort, although as of now, it appears that the lion's share of transfer will be from our side to theirs. We were also able to report that Rich Zippel has two MIT students working on an EMACS to be written in NIL, which likely will be finished by the end of the summer 1980. The usability of this EMACS, as well as that of MACSYMA (also to be converted over the summer), will be a test of NIL as a "system" programming language. From the conversion of MACSYMA code we expect to gain experience in converting other Maclisp programs, such as FRL - sadly, even though both the LISP Machine and NIL are claimed to be "upward-compatible" extensions of Maclisp, there is frequently some implementation-dependent code in user applications which must be confronted. One more question asked was whether we intended to make a presentation of NIL at John Allen's LISP conference - answer is Yes-and-No. "No", we don't have a paper submitted, such as was submitted to the Macsyma User's Conference last summer, but "Yes" there will no doubt be discussion and presentation (probably even a demonstration if we can get a VAX). I may go to the conference, and Jonathan Rees will likely be there, so there will be some representation. I'm not sure if the LISP conference was soliciting papers which merely announced another LISP implementation, but indeed there are a couple of innovative ideas in NIL (even if not 100% new) which ought to be the basis of a reseach report someday. _________________________________________________________________________ Current Progress on the NIL System, and on the VAX Implementation of It Jan 15, 1981 In May of this past year, we demonstrated certain pieces of each component of the system as being in operation, but as a whole it wasn't debugged enough to run even a toy LISP system; in mid August, we demonstrated a "toy" LISP system, which had some of the rudiments necessary to a typical LISP (mini-reader, partial EVALuator, and mini-printer). Even though this system was at a "toy" level, it did help us find many bugs in each component of the system -- from the compiler/assembler to the "virtual-machine" code -- and a good deal of debugging at each level has proceeded since then. We are currently still cross-compiling and assembling from the NIL emulator systems running on the PDP10, and may be in this mode for another four months. Between mid September and mid November, we re-structured our PDP10 emulation environment, partly to help extract from it a more implementation-independent body of code, and partly to reduce the size of our "piggy-backed" system (the NIL emulator runs "on top of" the PDP10 MacLISP system). Since NIL intends to incorporate into its runtime system a large measure of the MIT LISP Machine environment, this has severely impacted the addres space available on the 18-bit PDP10. [The MIT LISP Machine will henceforward be referred to as merely "LISPM"]. On a component-by-component basis, our current status is: VM ("Virtual Machine") Certain facilities are presumed to exist for the runtime environment of NIL; with a very flexible micro-code structure, one could put most of these facilities into micro-code, but currently we have no plans to put any of them into micro-code on the VAX. Typical of such items are data-accessing primitives which, at runtime, certify the correctness of the data type, primitive dispatch for the interrupt system, primitive i/o routines, primitive error service, and a cold-load startup routine which sets up an initial stack and initial dynamic storeage areas. The Vax NIL also contains VAX debugger, and some additional LISP-oriented debugging routines. Many of these functions are called "minisubrs", due to the fact that when not microcoded, they can be called out-of-line using whatever fast, non-recursive subroutine facililty is available (JSB seems to be the only candidate for the VAX). Some of the mini- subrs are "essential", in that the correct compilation of some piece of code will require them; others are "inessential", in that they will be used only when the user requests, by means of a compiler switch, full error checking in the runtime code. Currently, the VM consists of a motly collection of BLISS-32 code, and of a macro-assembler code which must be pre-parsed and converted into MACRO (we do this in order to fill in what we percieve to be the gaps of VAX MACRO). Although there are more than 15.K lines of this kind of code, one of the members of the group has been working on a lisp-coded data base which would permit the mechanical generation of most of the minisubrs and of the initial data tables; this should help the conversion of this code to run under UNIX (if necessary). ASSEMBLER/LOADER The NIL-assembler for the VAX, written entirely in the NIL language, is working fairly well since about July 1980. It is a non-macro, symbolic assembler, with a few pseudo-ops, and this is adequate for a "lisp" assembler. Current faults are mainly that no Jump-optimizations are being done -- all forward-branching jumps are "longword", and conditional jumps are done by conditional branches around a jump -- and that some PDP10 dependencies may remain. The assembler produces a byte-image file, which is then packed into a bit-stream suitable for file-transfer from the PDP10 to the VAX; one part of this file is like a "program section", in that it represents position-independent, read-only instructions; another part is for storing LISP s-expressions, which have to be "relocated" upon loading. Since instructions do make reference to this "s-expression" data, there is no way to use the linking-loaders of other VAX systems. The loader is written in BLISS-32, and ultimately the intention is for it to page-map in the read-only pages of a file, to gain sharability among multiple users, but currently it is merely inputting these pages. Although the i/o usage of the existing loader is VMS dependent, it should be possible to transcribe it fairly straightforwardly into any other VAX operating system (such as UNIX). Hopefully, someday, we would like to do what the group at Xerox's Palo Alto Research Center have done -- write the loader in NIL itself, and bootstrap a "cold-load" system by running in a "shadow" mode of the NIL emulator (which of course would be running on the PDP10). COMPILER(s): By May 1980, a primitive versison of an incremental NIL compiler had been coded; it is incremental in that it first produces a generally machine-independent code called LLCODE (acronymic for Linearized-Lisp-CODE), which is somwhat akin to the basic output of the LISPM compiler. LLCODE is then converted into LAP (the machine-language for the lisp assembler mentioned above) for the VAX by an independent module which is much like a second compilation phase (hence the appelation "incremental compiler"). By mid-August, this compiler had been completed for the full NIL language, with some work left to do on the optimization of registers during the generation-of-LAP phase. One member of the project began, in early April, the conversion of a partial NIL compiler built for the S1; this compiler was experimental and uses a strategy of compilation outlined in Guy Steele's master's thesis; another member of the project joined this effort in mid May, and by mid August, a subset of the NIL language could reliably be compiled for the VAX. The particular optimization strategies of this, compiler, while interesting from a theoretical point of view, quite likely have very little, if any, payoff on the VAX (since it has a fairly large memory cache), and under the NIL function-calling sequence (since it uses the VAX CALLS instruction. Consequently, interest in furthering this compiler has waned; but out of its "ashes", one group member, by mid-December, had distilled a slightly-more-comprehensive but very simple, stack-machine compiler which he is using as an working tool. EVALUATOR The "toy" interpreter mentioned above was unduly restricted due to bug in the "Virtual-Machine", especially the failure of the module which does the dynamic function-call transfer (i.e. given the symbolic name of a function at runtime, create a subroutine call to it, with the arguments put into a stackframe). As many of these bugs have been caught and corrected this fall, a more comprehensive evaluator has been tested out now (Jan 1981). By June 1981, an evaluator of the general capability of MacLISP will be available -- but of course all written in NIL itself. Our future plans call for an evaluator which has a fast, lexical-variable scheme; the structure of this idea has been worked out by one of us, but it is not of paramount practical importance now (it will follow some of the ideas of the SCHEME language designed by Gerry Sussman and Guy Steele). RUN TIME ENVIRONMENT The NIL "environment" is much like a subroutine library, along with a mixture of interpretive/compiler-oriented aids. A large part of this environment is inspired by the LISPM's environment, and is sufficiently rich that most programs written for the LISPM will run under NIL (major exceptions are, of course, I/O specialties the the newer, experimental parts of the CLASS system). Fortunately, this library is about 90% written in a compatible subset of NIL so that it forms the basis of the NIL emulator on the PDP10 -- thus it has been possible to develop extensively and debug this code on the PDP10. It currently consists of just about 10.K lines of rather dense NIL code, which is source-compatible for use either by a native NIL (such as on the VAX), by MacLISP on the PDP10, by the LISPM, and (eventually) by MacLISP on Multics. LISP DEBUGGING AIDS Very little has been coded as of Jan 1981. Plans call for a stack- analyzing tool similar to that available in MacLISP and INTERLISP; Each compiled function will eventually also contain a "road-map" so that variables which are stack-allocated by the compiler may be referenced by their original symbolic names. NILE An EMACS editor, written entirely in NIL, has been developed by an MIT undergraduate student, who also did a significant amount of work on the Multics EMACS (written in Multics MacLISP). This system has been running fairly reliably, since December 1980, under the NIL emulator on the PDP10. Possibly new problems will arise when it is brought up on the VAX, since a major feature of it is its interactive use of a CRT screen. CLASS SYSTEM Perhaps the most exciting, innovative idea in programming languages now is that of "object-oriented programming"; a first-version of this technology was implemented for the piggy-backed NIL in the spring of 1980, and major improvements were done during November and December 1980. Support for "message passing", a fundamental operation in such systems, has been provided in the VAX VM, and in the compiler, but more work is needed to get the most recent system to be free of PDP10 dependencies -- hopefully this will be done by the end of March 1981. Our goal is to be at least modestly compatible with the kinds of usages available on the LISPM, and this will no doubt mean continuing development, since this whole area of endeavor is somewhat new. A record-structure facility, called DEFVST, has been completed which depends (partially) on having a CLASS system available -- by connecting each structured object into a "class", or "sub-class" of objects, there is full extensibility at runtime. DEFVST is entirely written in NIL -- only the low-level "class" support must be provided by the compiler and VM.  3 Why NIL, rather than MACLISP/FRANZ? In attempt broadly to classify some of the differences between NIL and MACLISP, the first priority item must be the flexibility of making extensions to the language/system. Such extensibility is not at all limited to the system designers, such as for the purpose of "patching bugs" or making minor extensions, but is available to the end-user as a normal programming tool. In fact, the notion of "data-abstractions" may be one of the more profound ideas to hit programming-languages in recent years, and It may well be said that LISP is the vehicle of choice, not only for A.I. researchers, but for many who are trying out new ideas in programming languages. Since many languages attempting some sort of data-abstraction, like CLU at MIT, or even SIMULA which is popular in Europe, are compile- time only, often with "hard-typing" at compile time, that leaves LISP as the logical choice in which to experiment furhter with these ideas; the provision of a runtime "operating system" with LISP, which includes at least a parser (READ), a program interpreter (EVAL) and some minimal amount of data displaying routines (PRINT, and many others), permits a most flexible interactive "debugging" and program development environment. A few examples of usage for these features will be appended to this note. The MIT LISP-machine has spurred the development, in NIL, of several new pieces of programming syntax (some of which have been retro-fitted into PDP-10 MACLISP, such as several styles of "optional" arguments in function definitions), and in particular has demonstrated a high value to "object-oriented" programming. Furthermore, the LISP-machine code, operating system and all, has been entirely written in LISP, so that any lisp system flexible enough to support the (new) lower-level primitives can similarly develop these new ideas, even sharing code with the LISP-machine. As new ideas continue to filter into the LISP world, the shape of a lisp implementation must keep pace, or it will be as left-behind as batch operating systems have been. Major differences: NIL has 1) A "rich-pointer" data encoding scheme; each 32-bit datum has a type-code part and a remainder (which may or may not be an address). "BIBOP" storeage management, like MACLISP and FRANZ have, treat virtually all "pointers" as address, with the address space broken up into fixed size segments; they maintain a large table to indicate the data-type contained within each (uniform) "segment". Such memory-management is out-of-date in a large-address space LISP system. The use of the data-pointer to include some type (or "tag") bits filitates three very important goals; without it, the system will have three serious flaws: 1a) Segmentation of address space for spurious reasons - with "rich-pointer" schemes, segmentations of the address space occurs due to criteria which are truly *memory* related (such as, "static area" that the GC need not bother with, or "pure" areas that are read-only, or stacks and other relocatable tables.) with BIBOP schemes, there is a proliferating due to merely the presence of multiple data types. 1b) Limit on size of data objects. Except for ARRAYs, MACLISP's objects must all be of a certain pre-set size; (FRANZ kludges in just a pre-set number of STRINGS, and and does not have real ARRAYs). In turn, lack of a general arbitrary-length data-type compilcates adding data-abstractions in any but the most primitive, emulative fashion. 1c) No "immediate" data, except by ad-hoc and time-costly "split" in the address space. The type-bits of a "rich-pointer" specify certain codes to be "immediate" - that is, all the data are fully contained within the pointer itself (as opposed to the memory cell addressed by the pointer); in the BIBOP style, very few data objects can be so represented, and often it is at the cost of a "split" in the address space (e.g., some FIXNUMs may be represented by addresses, and others by a "split-off" pointer - this destroys any hope of efficient compilation for fixnums). Where "non-immediate" data are used, the intermediate results of a computation may require large amounts of consing for temporary storage. NIL has a number of "immediate" data types, including all FIXNUMs and a SMALL-FLONUM type which may be useful for interfacing to some "convolution-box" hardware being built at MIT and Stanford. 2) New data and language primitives: 2a) As in STANDARD LISP, NIL will have the VECTOR as a primitive data concept (which will mirror the concept of indexed-access to a block of memory), the STRING (mirroring the concept of a character string, especially so on a byte-addressed computer), the BITS (a general sequence of "bits", indexible either as a single bit or as sub-sequence of bits), the SUBR (executable code module), and many more new data types. 2b) As in MIT's LISP-machine, there are keywords in lambda lists, "CLASSES" (as in SMALLTALK and SIMULA), co-routining mechanisms ("stack-groups" on the LISP-machine, yet-to-be implemented in VAX/NIL), "PACKAGE" concept for reader (instead of maclisp limited OBARRAY concept), full-data primitives for STRING processing (with a view to open-coding those operations supported by the VAX hardware), extensive operations for generalized sequence handling. 3) Specially-tailored, unified COMPILER/ASSEMBLER/LOADER/RUNTIME environment, so that the entire system is written in NIL itself. The compiler is machine-independent; its output is called "LLCODE" for "linearized LISP code", and runs in an idealized LISP machine, a large portion of which may actually be constructed within the VAX WCS. The NIL project intends to develop WCS support for a good portion of the LLCODE by the end of the year. Currently the assembler has a sub-module which expands the machine-independent output of the compiler into VAX instructions, and only the LOADER and certain critical runtime-support routines (collectively called the "VM" for "Virtual Machine") are written in some language other than NIL (although they are written in BLISS and MACRO, they could potentially be written in C, and thus transported to any system with a C compiler; however there is a certain technical limitation to existing C compilers which would defeat a major optimization necessary when the WCS is not used, so we have not attempted to put the "VM" into C as of this moment). The assembler and LLCODE expander are written NIL - they are the logical points at with certain "compilation" decisions are to be made (e.g., should a "CAR" check the type of its argument or no, should it be turned into a call to the "CAR" subroutine, or use the section of the Writeable-control-store which performs a NIL "car" operation, or merely be turned into a couple native VAX instructions). We anticipate speed-ups up to a factor of 2 by using the WCS, in addition to the extra facility provided by dynamic type checking. 3) Loadable segments from the file system, such as in MULTICS. The NIL compiler/assembler will produce an object format which can be dynamically linked into a running NIL, and all the code parts will be read-only and shared with other NIL users; this is a standard feature of MULTICS, and of some of the VMS system library routines. [As of this time, I don't believe FRANZ is capable of such a thing]. To be able to run more that one user of a *big* system, such as MACSYMA, it will be required to share as much as possible; not only will MACSYMA users be sharing among themselves the MACSYMA code, but they will be sharing the LISP system code, and other random LISP utilities, with any other lisp user who happens to come on the sytem. Such facility will be critical to a SAVE/SUSPEND feauture; NIL will have a "SUSPEND" function, which permits a job to be "dumped" out to disk, and then restarted at a later time; parts of the core image which are read-only and are shared with the file system will not be included in the "dump" file image, but will be re-linked at load-up time. 4) EMACS in NIL; One of the most powerful ideas to arise in the world of text editors is that of a real-time display coupled with a decent program interpretor and flexible keyboard command assignments. This means having user-writeable sub-programs (or "editor commands") and having them "on the fly" when desired. Althought it might appear that the extensibility of the editor would be of interest only to the person who programmed the editor, this is most definitly not so; *no* programmer, however bright, can anticipate all future editing environments. The end-user of the editor must be able to extend it to meet the particular needs of his work - for example, when someone develops a new programming language with curly-braces used to represent a BEGIN/END pair, then likely the editor will need commands which seek out text-blocks marked by such pairs, and operate on them. The point of all this is that NIL/LISP is the ideal language in which to write an extensible text editor; such has already been done on the MIT LISP-machine (the ZWEI editor) and on the multics version of MACLISP (a version of EMACS). The latter code is propietary to Honeywell, and is somewhat MULTICS-dependent; during the summer of 1980, we have some MIT students who are familiar with similar kinds of code who are going to implement EMACS in NIL, and we expect this to be the most convenient editor to use on the VAX. 5) A great deal of software has been developed on the MIT LISP-machine. NIL will be able to absorb most of it, but a maclisp system could take only the more primitive pieces. LISP-machines will continue to be an important vehicle for both research and education at MIT, with about a dozen machines operative now, and several dozen more expected in the near future. Some other laboratories are also getting units - notably IBM's Thomas J. Watson Research Lab, and Xerox Palo Alto Research Center. 6) Better numeric capabilities. There will be a Fast-numeric compiler forthcoming, as in current PDP-10 MACLISP; furthermore, VAX/NIL will also interface to VAX/FORTRAN. It may be possible to critise the NIL-to-FORTRAN interface, as requiring a certain number of micro-seconds overhead beyond what is absolutely necessary, but this time will be found to be truly inconsequential for all except FORTRAN routins which do almost *nothing*. As an example of data-abstraction, consider the NIL structure defining command: (DEFVST TURTLE NOSE-HEADING (SPEED .15) PEN-POSITION) this defines a record-like object, called a "TURTLE" with three components; usage is by means of automatically-produced macro functions, which act as selectors and constructors, and there is a generally-available function STRUCT-TYPEP to obtain the name of a structure (or null, if the argument is not a structure). The constructor function, named by default to be CONS-A-TURTLE, will initialize the components as requested in the definition - SPEED is set to .15, and the others to null. Consider as an example a function which takes in a turtle, and creates one which is going twice as fast, with its pen in the opposite position: (DEFUN MAKE-FASTER-TURTLE (X) (COND ((NOT (EQ (STRUCT-TYPEP X) 'TURTLE)) (ERROR X '|Not a TURTLE|))) (CONS-A-TURTLE SPEED (TIMES 2 (TURTLE-SPEED X)) PEN-POSITION (COND ((EQ (TURTLE-PEN-POSITION X) 'UP) 'DOWN) (T 'UP)))) As an example of object-oriented programming, consider the class of objects called COMPLEX, and how various subroutines are linked into the general system routines PLUS, TIMES, PRINT etc. [** Warning! the syntax of this example does not reflect the actual NIL implementation, since it is still under development right now, but tries to be explanatory **] (DEFCLASS COMPLEX ;name of class (NUMBER MATH-THINGS) ;considered a subclass of both ; NUMBERs and MATH-THINGS REAL ;each object in the class needs two IMAGINARY) ; "instance variables", or compnents (DEFUN TIMES->COMPLEX (PERM-TABLE C1 MESSAGE-KEY C2) (DECLARE (METHOD-FUNCTION)) (SEND COMPLEX-CLASS 'CREATE (DIFFERENCE (TIMES (COMPLEX-REAL C1) (COMPLEX-REAL C2)) (TIMES (COMPLEX-IMAGINARY C1) (COMPLEX-IMAGINARY C2))) (PLUS (TIMES (COMPLEX-REAL C1) (COMPLEX-IMAGINARY C2)) (TIMES (COMPLEX-IMAGINARY C1) (COMPLEX-REAL C2))))) (ADD-METHOD 'TIMES->COMPLEX COMPLEX-CLASS) The last line will add this particular method (function?) to the CLASS, but of course, any class "inherits" various properties and methods from its superior classes, including the method for CREATE.