Google
 

Trailing-Edge - PDP-10 Archives - decuslib10-04 - 43,50322/intro.doc
Click 43,50322/intro.doc to see without markup as text/plain
There are no other files named intro.doc in the archive.








                                  INTRODUCTION



               UCI LISP is a compatible extension of the Stanford LISP
          1.6 programming system  for the DEC PDP-10.   The extensions
          make  UCI  LISP  a   powerful  and   convenient  interactive
          programming  environment  for  research   and   teaching  in
          artificial  intelligence   and   advanced   list  processing
          applications.   All Stanford  LISP  programs,  (except those
          using the BIGNUM package)  can be run directly in  UCI LISP.
          In addition,  the extended features of UCI LISP make it much
          easier  to transfer interpreted  LISP programs from BBN LISP
          and  MIT  AI  LISP  (we have already converted several large
          programs,  including  a  version  of  the  Woods'  Augmented
          Transition Network Parser from  BBN LISP,  and a  version of
          Micro-Planner from MIT AI LISP.)


               This  manual  describes the  extensions to the Stanford
          LISP 1.6 system, and should thus be read in conjunction with
          the latest Stanford LISP 1.6 manual,  currently  SAILON 28.6
          (Stanford Artificial  Intelligence Laboratory Operating Note
          28.6).   As can  be  seen from the relative sizes of the two
          documents  UCI LISP represents  a  substantial  extension to
          Stanford LISP,  and from our own experience presents a major
          improvement in the habitability of the system for both naive
          and experienced users.   (A  majority of the extensions were
          suggested by  the features  of  BBN  LISP, probably the best
          interactive  LISP  system  in  existence,  but unfortunately
          available  at  the  time  UCI  LISP  was implemented only on
          TENEX,  a  paged  virtual  memory  system  for  the  PDP-10,
          produced by Bolt,  Beranek and Newman Inc.; this LISP system
          is now or soon will be available  on the BURROUGHS B6700 and
          the IBM S/360 and S/370  series machines,  and is now called
          INTERLISP.)


               The  major extensions to Stanford LISP  can  be briefly
          described as follows:

                 1) Improvements in storage utilization:
                     a) UCI LISP is reentrant and compiled code may be
                        placed in the sharable high segment
                     b) The   allocator  allows  reallocation  of  all
                        spaces (including Binary Program Space) at any
                        time,  and new  versions  of GETSYM and PUTSYM
                        are  now  available  to  permit  relocation of




                                      0 . 1













                        MACRO-10 and FORTRAN coded routines
                     c) A new  data type, the BLOCK, which allow users
                        freer  access  to  Binary  Program  Space  and
                        permits the construction of data items such as
                        the system OBLIST,  which is both a list and a
                        contiguous   block  of   storage  (to  provide
                        efficient use as a sequential hash table)

                 2) Powerful    interactive    debugging   facilities,
                    including:
                     a) Sophisticated   conditional   breakpoint   and
                        function tracing facilities
                     b) A powerful  list structure editor  for editing
                        function definitions and data
                     c) Facilities  for   examining,   correcting  and
                        continuing to run in the context of  a program
                        which has been interrupted by an error or by a
                        user initiated temporary interrupt

                 3) Extensions to the I/O facilities available  in the
                    basic system, including:
                     a) Convenient I/O to disk files, including use of
                        project/programmer  designations  and  ways to
                        save and restore functions and data
                     b) Read Macros (patterned  after MIT AI LISP) for
                        extending the LISP READ routine
                     c) A  routine  for  printing  circular  or deeply
                        nested expressions
                     d) Routines  to modify the control  table  of the
                        LISP READ routine
                     e) The  ability  to  change  the  OBLIST  used by
                        INTERN  (and,  hence,  READ)  at  any  time by
                        changing  the value of the  atom  OBLIST  to a
                        properly structured BLOCK  list (see  1c above
                        and Chapter 11)
                     f) The  ability to  RENAME and DELETE  files from
                        within LISP
                     g) The  ability to read  file directories for any
                        accessible  project-programmer number,  to see
                        if a file exists in a directory
                     h) Several   useful   functions    for   carriage
                        positioning,    teletype   echo   and   prompt
                        character control,  reading input a line  at a
                        time,    reading   list   structures   without
                        interning their atoms, etc.

                 4) Functions for examining and modifying  the special
                    pushdown  stack which holds the context of ongoing




                                      0 . 2













                    computations

                 5) Error protection facilities:
                     a) NIL,  T  and  other  atoms  cannot  be  easily
                        damaged by RPLACA, RPLACD, SETQ and SET
                     b) The system will  no longer go into an infinite
                        loop   when   searching   for   the   function
                        definition of the CAR of a form
                     c) Changes  to the disk output  routine DSKOUT so
                        that it uses the RENAME facility to  provide a
                        backup for user  files (minimizing the risk of
                        unintentionally clobbering files)

                 6) Extended basic functions including:
                     a) New  predicates  for  data  types,   and  most
                        predicates  now  return useful non-NIL values,
                        rather than T
                     b) New   list   construction   and   modification
                        functions
                     c) Multiple sequential form evaluation  in LAMBDA
                        expressions
                     d) An efficient n-way switch
                     e) Availability   of  the   FORTRAN  mathematical
                        functions
                     f) Mapping functions with  several arguments, and
                        ones which build new lists using NCONC to join
                        segments

                 7) The  ability  to  use  many  of  the  system Queue
                    Manager's   facilities   without   leaving   LISP,
                    allowing:
                     a) Listing of files on the line printer
                     b) Initiation of batch jobs


               As mentioned,  we have made UCI LISP a reentrant system
          which  may be  used by  several users simultaneously.  Thus,
          while  the new features of UCI  LISP require a larger system
          than the original Stanford LISP, this impact is minimized in
          any  environment with more than one LISP user.  In addition,
          since  the   basic  LISP  system   contains   many  features
          previously  available only  in  the  various extension files
          (such as SMILE,  ALVINE,  TRACE,  etc.)  or  which had to be
          written  by  the  user,  it  is  possible to write and debug
          meaningful  jobs in the basic system,  without getting extra
          core.   The UCI LISP system  has a sharable high  segment of
          14K and  a user specific low segment  of 8K.  Thus, if there
          are two users  the virtual core  load is 30K,  while getting




                                      0 . 3













          the  same capabilities in Stanford LISP would require a load
          of 32K  for the two users,  and of course the improvement is
          even more noticeable with more users sharing UCI LISP (about
          8K is saved for each additional user).


               The  ability  to  put  compiled  code  in  the sharable
          segment  and to  reallocate  Binary  Program Space  makes it
          possible to build systems in which much of the  systems code
          is compiled  LISP expressions.   All  of  the  advantages of
          higher level coding  are  obtained,  and  the  LISP compiler
          (borrowed  from  Stanford  with  some  small  modifications)
          produces better  results than most assembly language coders.
          Such partially  compiled  systems  can now  be  used without
          closing off  the  possibility  of the user  extending Binary
          Program Space to store  his own compiled code.   In general,
          it is now possible to  compile a  system incrementally.  The
          user can save the  low segment which contains  the partially
          compiled system,  then test out  new material in interpreted
          form  before  extending  the  Binary  Program  Space  in the
          segment to load the new compiled material.


               The  debugging  facilities   form  the   bulk   of  the
          extensions to Stanford  LISP,  and  are  identical  with the
          equivalent facilities available in BBN LISP in the summer of
          1971.   (BBN  LISP  has  been  extended  in  the intervening
          period.)  They make it  possible for the user  to track down
          bugs in complicated recursive programs by  making  it easier
          for him to investigate the context in which the bug occurred
          (e.g.  to see at what point erroneous data was passed  as an
          argument,  or at what point the  flow of control  went awry,
          etc.)  The user  does  not have  to  plan  in advance or set
          breakpoints to get access to the context of the  error.  The
          system   holds  the  context  of  any  error  automatically,
          allowing  the  user  to perform  whatever  investigations he
          wishes,  and make any corrections which may be useful.  This
          also  makes  it possible to patch  up a small error, like an
          unbound atom or simple undefined  function, in the middle of
          a  large computation and to continue the computation without
          having to  start  from scratch.  Similarly, the user can try
          out ideas for  correcting  the  error,  without  leaving the
          context of the error, and go on only when he has pinned down
          the  error and its  possible solution.   If  the information
          available at the time the LISP system discovers the error is
          insufficient to pin down  the  cause  of the error, the user
          can  have the system  repeat the computation, with a special
          trace feature  that  prints out whatever the user  wishes to




                                      0 . 4













          know at  various  points in the  computation.  (The user can
          specify both what  data  is  to  be  printed  and under what
          conditions he wishes it printed.)  The  user can  also force
          the  system  to  establish  a  breakpoint  anywhere  in  his
          computation,  so he can  investigate the context  before the
          error has covered its tracks.


               The  UCI LISP  editor (borrowed with some modifications
          from  the  BBN  LISP  system)  is  actually  a  language for
          incremental modification of list structures.  It can be used
          by a user at a terminal to modify function definitions (even
          during the middle of a break while the function is  still on
          the context stack) or to change complicated data structures.
          It  can  also be  used  as a  subroutine by other functions,
          making it convenient  for  one  function  to  modify another
          function.   This  is actually done by the BREAK  package, to
          implement the function BREAKIN which inserts a breakpoint at
          any arbitrary point in a user function.
               The  editor  can move around in  a  structure  by small
          local  motions,  or  by  searching  for  a  portion  of  the
          structure which matches some given pattern.   It  can insert
          new  items,  delete  old  ones,  interchange  items,  change
          structure,  embed old items in new structure or extract them
          from  old  structure,  etc.   In order to be able  to edit a
          function which is still on the context stack and to have all
          of the portions on the context stack be changed at once, the
          modifications performed by  the  editor are physical changes
          of the existing structure.   Although  all the modifications
          are  "destructive",  using RPLACA and RPLACD to make changes
          in the given structure,  all  of  the  modifications  can be
          selectively reversed by means of the UNDO feature.  Thus the
          user   can   make   modifications   without  worrying  about
          completely destroying his function definitions by accident.


          The  editor is  a very large,  complicated function, and its
          documentation  indicates that fact.  However, the first part
          of the editor  documentation gives  a  convenient rundown on
          how to  use  the editor  as  a  novice,  and  with  that the
          beginning user can get quite a bit  done.   By  skimming the
          remainder of the editor chapter the user can  get  some idea
          of the many extra  useful features available, and can slowly
          extend his capabilities  with  the  editor.   It  has been a
          common  observation  that  in  the  process  of  writing and
          debugging  a large system,  or  even  a  small  program, the
          average  user  spends  most  of  his  time  in  editing  his
          functions.   By becoming familiar with  all  the features of




                                      0 . 5













          the list  structure editor the user can cut his editing time
          considerably,  and make large or subtle changes easily.  The
          user should  also  bear in mind that the editor is available
          as a  function which can be used by  other  functions.  This
          can make many jobs substantially easier.


               NOTE: ALVINE is no  longer  available  in  the standard
          version of UCI LISP because we believe  that the  new editor
          and  I/O  facilities  are  substantially  better  than those
          provided  by  ALVINE.   (There is an  assembly  switch which
          makes it possible to run ALVINE in UCI LISP if necessary.)


               Some of the  extended  I/O facilities of  UCI LISP were
          available in SMILE,  etc.,  but  putting  them in the shared
          system  saves  core.   The  Read  Macro  facility is a great
          convenience and makes using Micro-Planner much simpler.  The
          user-modified READ control  table is more  general than that
          available in  the  Stanford  SCAN  package  (which  is still
          useful and available), and the new SPRINT is faster than the
          original.   The other  functions  are  quite convenient, and
          will make many tasks simpler.


               The special pushdown list has been extended  to provide
          the equivalent of  the  BBN LISP context stack.  This is the
          backbone  of the ERROR and  BREAK packages, since it enables
          running programs  to examine their context, and to change it
          if necessary.  The stack functions, particularly RETFROM and
          OUTVAL make  it possible to experiment  with various control
          regimes,  where subordinate  functions  can abort and return
          from   higher   level  functions  on   the  basis  of  local
          information.   Indiscriminate fooling  around with the stack
          is likely to produce peculiar  and unwanted results, but the
          stack functions can be extremely helpful at times.


               The error protection facilities are an attempt to catch
          some of the common errors of novices (and  experienced users
          too)  which can clobber  the  system.   There are few things
          more  confusing than what  happens  to  the system  when the
          value of NIL is no longer NIL,  or if the value of T becomes
          NIL.   In Stanford LISP  this could easily happen if SETQ or
          SET received a list as a first argument.  This can no longer
          happen in UCI LISP.   Similarly,  Stanford LISP occasionally
          went into infinite loops because a form  had a CAR which was
          NIL or  had no  function  definition  and evaluated  to NIL.




                                      0 . 6













          This has been corrected.


               The  extended  basic functions  are ones which  were of
          great use in writing the editor, BREAK package, etc., and in
          bringing up translated versions of BBN LISP and MIT  AI LISP
          programs.  The multiple form LAMBDA expression and the n-way
          switch  SELECTQ should  make many programming jobs much more
          convenient,  as should the availability of mapping functions
          with several  arguments.   The  user  will  almost certainly
          profit  from skimming through the chapters on these extended
          features, just to know what is available.








































                                      0 . 7













                          Credits and Acknowledgements



               The design and overall  direction of the implementation
          of this system are the responsibility of Robert  Bobrow, who
          also   made  the  first  modifications  to   Stanford  LISP,
          including  the original  error  package,  accessible context
          stack and storage reallocator.   In large part the existence
          of the final system and its  extensive documentation  is due
          to the  Herculean efforts of Daryle Lewis,  who did the bulk
          of  the  modifications  to   the   assembly   language  code
          (including making Stanford LISP reentrant) and corrected the
          compiler and LAP systems.  He singlehandedly transferred the
          entire BBN  LISP editor and its documentation to our system,
          and  in  general  performed   vital   and   arduous  design,
          programming and documentation tasks too numerous to mention.
          Richard  Burton  did  yeoman's  labor  by  transferring (and
          extending)  the  BBN  LISP  ERROR  and  BREAK  packages, and
          providing their documentation.   Jeff  Jacobs maintained the
          system for many months, correcting may old Stanford compiler
          and  garbage  collector  bugs;   he  also  implemented  many
          extensions, such as the interface to the Queue Manager, disk
          file  directory functions,  the  user-switchable OBLIST, and
          the  BLOCK  data type.   Bill  Earl has  also provided great
          service  in maintaining  the system  and  its documentation.
          Whitfield Diffie of Stanford has helped  us  out  of several
          sticky problems with the LISP system and  its compiler.  The
          original  implementation  of  the  editor  and  several  I/O
          functions is due to Rodger  Knaus,  as well  as many helpful
          suggestions.   Finally,  but  of vital  importance,  is Alan
          Bell,  whose great knowledge  of the PDP-10 operating system
          helped us through many rough times, and who has done much of
          the transferring of BBN LISP and MIT AI LISP programs.


               We are  triply indebted to the  designers, implementers
          and documenters of BBN LISP,  particularly Daniel Bobrow and
          Warren  Teitelman.   Most of  the  debugging and interactive
          facilities as well  as the general  design philosophy of UCI
          LISP  were inspired by the BBN  LISP  system.   Secondly, we
          were able to use much of  their code directly,  since it was
          written in  LISP,  making  it  possible  to  obtain a large,
          well-written  and  debugged system in a fraction of the time
          and effort it  would have  taken to  write  it from scratch.
          Finally,  we have made  extensive use of the BBN  LISP TENEX
          REFERENCE  MANUAL  as  a  source  of  raw  material  for our
          documentation.   In particular,  much of the material in the




                                      0 . 8













          chapters on the BREAK and ERROR packages and the editor is a
          revised version of the material in the BBN LISP  MANUAL.  We
          take full  responsibility for  the  errors  and deficiencies
          produced   by   such   an   arrangement,   while  greatfully
          acknowledging  BBN's  aid  in  providing  much of  the basic
          documentation.  We are also in debt to several people at BBN
          for  their aid  in  obtaining and explaining  this material,
          particularly Jim Goodwin,  Alice Hartley and the director of
          the Artificial Intelligence Group, Jaime Carbonell.


               This manual  is the work of many people  as well as the
          listed authors - in particular Warren Teitelman, formerly of
          BBN and now at Xerox Palo Alto Research Center, who produced
          the original BBN LISP  documentation and the lions  share of
          the  original  code.   We are also in debt to Marion Kaufman
          and Phyllis Siegel  who did  daily battle with the PDP-10 to
          produce the RUNOFF files  from  which this  documentation is
          produced.


               Last,  but most assuredly not least  in  the  roster of
          those who  have made this  system  possible are Kathy Burton
          and Connie Lewis who lived through the many discussions, all
          night  programming  sessions and battle-fatigue  of the year
          during which this system was implemented.


          ENJOY, ENJOY!























                                      0 . 9