perm filename RAFAEL.PUB[L70,TES] blob sn#009957
filedate 1972-08-29 generic text, type T, neo UTF8
00100 August 29, 1972
00300 Dear Bert:
00500 There are lots of working documents about LISP70, and you may have
00600 got hold of some that we distributed privately. However, we request
00700 that you do not publish any of the material in them, as they are
00800 obsolete and emphasize many areas of little importance.
01000 We do not plan to publish anything about LISP70 until it works. We
01100 are rather annoyed when we read about new systems and then discover
01200 that they were never really implemented successfully. Nevertheless,
01300 some ideas going into LISP70 are of general interest and some have
01400 been tested extensively in 1.5 years of experience with MLISP2.
01500 Therefore I am enclosing two short working papers of this type. The
01600 rest of this letter is a blurb about LISP70 culled from various other
01700 sources and tailored to your purpose.
01900 LISP70 is based on LISP. The design goals, most important first,
02100 (1) Extensibility
02200 (2) Inter-machine transferability
02300 (3) Facilititated Debugging
02400 (4) Convenient input and output
02500 (5) Efficiency of Operation
02700 At first glance, these goals seem orthogonal to those of PLANNER,
02800 QA-4, SAIL, etc. However, extensibility includes the ability do
02900 define new control structures, and it is achieved by rewrite rule
03000 tables which build pattern-matching and backtracking into the core
03100 language. The core also includes a variety of data types, extensive
03200 monitoring capabilities, and an MLISP notation.
03400 Input and output are facilitated by "streaming". Any list, file,
03500 string, or other "sequence" can be pointed to by a "pointer" which
03600 scans it left to right but can be backed up on failure. Input streams
03700 are scanned by "source pointers" and output streams are generated by
03800 "destination pointers". Intrinsic functions move the pointers,
03900 extracting or inserting data as the case may be. These intrinsics
04000 are called implicitly by rewrite rules, which are the basis of the
04100 pattern matcher. Thus, the matcher can stream from core to core,
04200 core to file, file to core, or file to file, depending on the targets
04300 of the source and destination pointers. In particular, file to file
04400 operations such as compilation avoid nearly all cons'es by using
04700 Efficiency is achieved in the pattern matcher by grouping rewrite
04800 rules into tables. Each table is called an "extendable function",
04900 because new rules may be added to it at any time, and the rules may
05000 be applied by use of a function call. Tables are compiled, not
05100 interpreted. During compilation, factoring of common parts of rules
05200 and hashing of atomic elements is performed to attain processing
05300 speeds comparable to precedence-type compilers. Backtracking in most
05400 cases is instantaneous because of detection of special cases during
05500 compilation. Complex backtracking is made fairly rapid by techniques
05600 discussed in one of the enclosed papers.
05800 The first version of LISP70 does not use the "staging area" or
05900 "activation record" control structure mechanism described by numerous
06000 authors during the last ten years. To woo users away from LISP and
06100 SAIL, we are keeping a multi-stack structure for now so they can
06200 maintain their accustomed efficiency with existing programming
06300 styles. Multiple processes are implemented by separate
06400 non-hierarchial stacks; the specification of inter-process control
06500 conventions is extensible. Activation record control structure will
06600 be added later as an optional mode for those who have a need for
06700 hierarchial processes.
06900 Important differences from the "other" languages:
07100 Patterns are compiled, not interpreted; ordered automatically by the
07200 compiler according to definite but extensible rules, not randomly
07300 ordered; able to process streams to avoid most cons'ing; able to
07400 parse strings as well as decompose lists.
07600 Backtracking is automatic but "fast"; tree search can be "suspended"
07700 to achieve occasional breadth-first search; multiple processes can be
07800 used alternatively to search goal trees.
08000 The language is truly extensible: data types can be created not only
08100 by cartesian product and union but also from scratch; extensions can
08200 be made at the M-notation level, at the S-notation level, at the
08300 idealized LISP machine level.
08500 The language is machine-independent but can take advantage of special
08600 facilities of individual machines by adding special rewrite rules to
08700 any program.
08900 A single implementation will run on several machines, except for a
09000 small machine-dependent portion. The implementations can be
09100 generated and maintained at a central location.
09300 It can be run in compiler-compiler mode to generate systems for other
09400 languages, thus allowing rapid implementation of other languages.
09600 The interpreter is normally not used. EVAL calls the compiler, thus
09700 insuring consistent results, allowing extensions to the compiler to
09800 be recognized by EVAL, and permitting EVAL to operate in the correct
09900 scope of lexical declarations. Thus, functions may be declared
10000 within functions and variables may have lexical scope. The compiler
10100 is always around so compilation entails no overhead.
10300 We don't have paging on our PDP-10. Instead, we are using dynamic
10400 storage allocation within an expandable/contractable block of core,
10500 segmentation, and relocatable code and data. Shared code and tables
10600 are in a read-only second segment.
10800 I hope it is clear that these facilities are useful for artificial
10900 intelligence. LISP70 should be able to do anything that can be done
11000 in PLANNER, QA-4, or SAIL, and will shine in its own special ways.
11100 The easiest way to approach theorem proving and planning in LISP70
11200 will be different than the easiest way in PLANNER and QA-4, namely by
11300 use of rules of inference organized into groups corresponding to
11400 Extendable Functions.
11600 There are lots more interesting concepts in LISP70 too numerous to
11700 describe, and many implementation clevernesses that are not relevent
11800 to your purpose. Someday we expect to have it working and produce a
11900 manual and some papers. The state of implementation is as follows:
12000 most of the system has been completely coded at least once; most of
12100 the language features have been compiled successfully; much of the
12200 storage allocation has been tested; some object code has been
12300 executed. The backtracking scheme is similar to but an improvement of
12400 that used since early 1971 in MLISP2 (Horace J. Enea and David C.
12500 Smith). LISP70 was designed by and is being implemented by Horace J.
12600 Enea, David C. Smith, and Lawrence G. Tesler. If you need an
12700 estimated completion date, say "1973", but I'd rather you didn't need
13000 Sincerely yours,
13200 Larry Tesler