Power-Programmierung/CD1.mdf/snobol/aisnobol/report1.doc

Text File | 1987-10-18 | 224KB | 5,677 lines

               Technical Report # 47                      August, 1982




                         ARTIFICIAL INTELLIGENCE PROGRAMMING
                                     IN SNOBOL4


                                  MICHAEL G. SHAFTO
                              GUSTAVUS ADOLPHUS COLLEGE





          Prepared for distribution on diskette by:

                         Catspaw, Inc.
                         P.O. Box 1123
                         Salida, Colorado 81201 U.S.A.
                         303/539-3884

          with assistance from Mark Olsen of Arizona State University and
          Martin Rice of the University of Tennessee.  The cooperation of
          Michael Shafto is also appreciated.


          Preparer's Note:  The programming examples in this paper were
          prepared and run under 370/Spitbol.  Some differences from
          SNOBOL4+ and Macro Spitbol required coding changes for the
          program files included.  Specifically, the latter two systems do
          not support the DREAL datatype, and SNOBOL4+ does not support
          "NUMERIC" as a second argument to the DATATYPE function.  Also,
          the 16-bit integers of SNOBOL4+ were inadequate for the TEST
          program, requiring conversion to real numbers in some places.






















                                      ABSTRACT

            The SNOBOL4 programming language has not been used extensively
          for artificial intelligence (AI) programming.  There are several
          reasons for this.  SNOBOL4 has no built-in list processing func-
          tions.  Therefore, it is widely considered to be strictly a
          string processing language.  Only the most recent version of
          SNOBOL (SNOBOL4) could easily accommodate list processing.  More-
          over, most AI programmers have been trained in LISP programming,
          while most SNOBOL4 experts have shown little interest in AI.  The
          standard texts on SNOBOL4 concentrate on pattern matching, text
          formatting, compiler construction, and software development.

            This paper describes SNOBOL4 from the perspective of AI pro-
          gramming.  SNOBOL4 has several features which make it an excel-
          lent AI language.  It is well standardized, so that programs are
          highly portable.  Efficient optimizing compilers are available
          (SPITBOL, FASBOL).  It supports string, list, and numerical pro-
          cessing, all of which are potentially important in AI.  It also
          supports recursion, associative data structures, backtrack pro-
          gramming, pattern-matching, run-time code construction, and
          "self-modifying" code.  Furthermore, SNOBOL4 is a good language
          in which to write special-purpose compilers, and it is a good
          target language for such compilers.

































       AI Programming in SNOBOL4       - 2 -                     August, 1982








                         ARTIFICIAL INTELLIGENCE PROGRAMMING
                                     IN SNOBOL4

            Many computer programmers have only the most casual acquain-
          tance with SNOBOL4.  A typical conception of the language seems
          to be along the lines of this description (TRS-80 Microcomputer
          News, 1982):

             "SNOBOL: Text manipulation language."

            For example, a computer science graduate student (an AI spe-
          cialist) recently asked me, "But SNOBOL doesn't give you recur-
          sion, does it?"  (All programmer-defined functions in SNOBOL4 are
          recursive.)  Considering the restricted audience within computer
          science itself, it is not surprising that psychologists' knowl-
          edge of SNOBOL4 rarely extends beyond a chuckle at the name.

            (I will use "SNOBOL4" as a generic term covering BTL SNOBOL4,
          SPITBOL, FASBOL, SITBOL, CISBOL, ICEBOL, SNOFLAKE, SNOFLEX,
          ELFBOL, SLOBOL, SNOBAT, SIXBOL, and so on.  The programs
          described below were all implemented in SPITBOL, Version 2.2.6,
          under MTS at the University of Michigan.)

            In this paper, I want to present SNOBOL4 to the psychologist
          who is interested in AI programming, and who has some programming
          experience.  I assume that the reader is not a professional com-
          puter scientist, but is acquainted  with AI programming in LISP,
          as presented in Friedman (1974), Siklossy (1976), Winston and
          Horn (1981), Bundy et al. (1978), Maurer (1973), University of
          Michigan Computing Center (1976), McCarthy et al. (1963), Char-
          niak et al. (1980), Schank and Riesbeck (1981), Shapiro (1979),
          and Winograd (1972).

            I want to present SNOBOL4 as an AI programming language for
          several reasons.  As a practical matter, the reader might have
          access to a good SNOBOL4 system, but not to a good LISP system.
          In fact, the LISP system at the University of Michigan is not a
          top-of-the-line model, but the SNOBOL4 system is.  It was this
          simple, practical consideration that provided my own initial
          motive to explore AI programming in SNOBOL4.

            Beyond pragmatics, there is an aesthetic motive.  I have found
          SNOBOL4 to be an interesting programming language, full of unex-
          pected subtlety and expressive nuance.  I therefore suggest it to
          the reader as a source of intellectual stimulation.

            As Maurer (1976, pp. ix-x) writes,

            "From a theoretical viewpoint, SNOBOL4 addresses all of the
          major issues in programming languages, and provides fresh new
          insights into many of them.  ... [M]uch of the programming world
          is now convinced that SNOBOL4 is not just a good programming lan-
          guage [but] is an important advance in the state of the art of
          programming languages.



       AI Programming in SNOBOL4       - 3 -                     August, 1982








            "SNOBOL4 is more than a string-processing language; it is an
          algebraic language, a pattern-matching language, and an associa-
          tive language, as well."

            Indeed, SNOBOL4 is the Alice's Restaurant of programming
          languages: You can get anything you want.

            Besides proselytizing, I intend simply to provide information.
          SNOBOL4 is not a "new AI language," but rather an old, well-
          established programming language with unexploited potential.  It
          is impossible to anticipate how the special features of SNOBOL4
          might serve the purposes of a creative AI programmer (see, for
          example, Shapiro, 1979, pp. 79-85).  But more psychologists
          should at least be aware of SNOBOL4 as a language worth
          considering for AI applications.

            Finally, along with information comes clarification.  There
          sometimes seems to be a mystique surrounding LISP and AI.  Under-
          lying this mystique seems to be something like the following
          argument: "AI programming is list processing.  LISP is the list
          processing language.  Therefore, LISP is the AI language."

            In fact, LISP does have certain features which make it espe-
          cially suited to AI programming.  By comparative programming in
          LISP and SNOBOL4, we can appreciate more clearly what these spe-
          cial features are.  Comparative programming may help to demystify
          AI.  Problems can be separated from methods, and methods from
          implementations.

            List processing is one important programming technique; but
          string processing, backtrack programming, and even numerical com-
          putation are also important.  Powerful programs depend on a
          "combination of ingredients."

            I will argue that the list vs. string distinction, which
          allegedly separates LISP and SNOBOL4, is a red herring.  The most
          important language characteristics for AI programming are those
          characteristics which are SHARED by LISP and SNOBOL4, and which
          distinguish them from other programming languages.


                        STRING PROCESSING AND LIST PROCESSING


          Nonnumerical Computing
          ----------------------

            In nonnumerical computing the computer is treated as a symbol-
          manipulator rather than a number-cruncher.  Non-numerical pro-
          gramming problems often originate within computer science itself.
          The programming techniques, which involve string and list pro-
          cessing, seem remote from those needed in science and engineer-
          ing.




       AI Programming in SNOBOL4       - 4 -                     August, 1982








            The main topics of nonnumerical computing include the follow-
          ing: graph theory; algebra of strings; construction and searching
          of trees and other list structures; scatter storage techniques;
          database management; sorting; grammatical analysis and compiler
          construction; symbolic mathematics; and artificial intelligence.
          The specialist in nonnumerical computing needs a strong back-
          ground in logic and algebra, but may know little or nothing about
          physics, chemistry or engineering.

            As might be expected, the major nonnumerical programming lan-
          guages (LISP and SNOBOL4) are quite different from the languages
          familiar to scientists and engineers (FORTRAN, ALGOL, BASIC,
          APL).  It is not obvious, however, why LISP and SNOBOL4 are often
          considered quite different from each other.

            Folklore has it that SNOBOL4 is for strings, and LISP is for
          lists; and that this constitutes a significant difference between
          the two languages.  In fact, however, the specialization for
          strings or for lists is only a matter of degree.  LISP can pro-
          cess strings and SNOBOL4 can process lists.  Too much emphasis on
          the string-list distinction has made LISP and SNOBOL4 appear more
          dissimilar than they really are.


          Strings and Lists
          -----------------

            STRINGS.  A string is an ordered set of zero or more charac-
          ters, each character typically occupying one byte of the com-
          puter's memory.  A particular string can be defined by two inte-
          gers, its start address and its length (measured in characters).

            LISTS.  There are many ways to define lists and list-like
          structures.  I will follow LISP conventions, according to which
          lists are linked together by CONS cells.

            (Since I am discussing list processing in general, and not LISP
          in particular, I will use the word "string" where "atom" would be
          more accurate in a discussion of LISP.  Although this oversimpli-
          fies both LISP and SNOBOL4, I don't think that it is misleading
          in the present context.  The reader, however, should not take
          this section to be descriptive of any actual implementation of
          LISP or SNOBOL4.)

            A CONS cell consists of two integers which are pointers to (or
          addresses of) other CONS cells or strings.  The first ("left
          hand") pointer, called the CAR in LISP, points to the first ele-
          ment of the list (the head), which is usually a string.  The sec-
          ond ("right hand") pointer, called the CDR in LISP, points to the
          rest of the list (the tail), which is usually another list.

            In the simplest case, the CAR (head) of a list is a string, and
          the CDR (tail) is another list.  Obviously, this can't go on for-
          ever because we come to the end of the list.  The end of a list



       AI Programming in SNOBOL4       - 5 -                     August, 1982








          is conventionally marked by the list NIL, which is the list of
          zero elements.  (Again, it is beside the point whether in some
          particular version of LISP NIL is an atom, a list, both, or
          neither.)

            The characters of a string are located in adjacent, memory
          locations.  If one character is at memory location n, the next
          character is at location n + 1.  In a list, however, there is no
          natural relation between the addresses of successive elements.
          The links between successive elements must be stored explicitly.
          Thus, there is more to a list than meets the eye: The pointers
          that organize a list -- that enable the program to find the suc-
          cessive elements in the correct order -- do not appear in the
          printed representation of the list.

            In the course of explaining list processing, it is sometimes
          necessary to refer to the complete set of information which is
          stored in the computer's memory, pointers and all.  Suppose we
          consider just two datatypes, "string" and "cons."  Let each
          string identifier have two pointers, labeled "name>" and
          "value>."  The name> pointer is the address of the string of
          characters which would be used to print the name of the identi-
          fier.  (This is called the "print-name" in LISP.)  The value>
          pointer is the address of the current value of the identifier.

            Suppose each cons-cell has two pointers, labeled "car>" and
          "cdr>."  Now any identifier can be represented by its datatype
          (string or cons) and the items pointed to by each of its point-
          ers.  For example, if the identifier L has the value FISH, we can
          show this as

               string:[name> L, value> string:[name> FISH, value>
                   string:[*].

            The notation string:[*] will stand for the null string, i.e.,
          the string of length zero.  Similarly, cons:[x] will represent
          the null list, i.e., the list of zero elements.  I will use the
          period (.) in this context as a right-hand super-bracket, closing
          all the pending left-hand brackets.

            A simple, standard list structure would be stored as

               string:[name> L, value> cons:[car> string:[name> CAT,
                  value> string:[*]], cdr> cons:[car> string:[name> DOG,
                     value> string:[*]], cdr> cons:[*].

            This list would be created in LISP by the expression

               (SETQ L '(CAT DOG)).

            The power and flexibility of list processing comes from the
          simple idea of connecting strings by means of labeled pointers.
          The convenience of programming in a list oriented language
          depends upon creating expressions for lists, in which the labeled



       AI Programming in SNOBOL4       - 6 -                     August, 1982








          pointers do not appear explicitly.  Notice the compactness of the
          LISP expression above in comparison with the more explicit ver-
          sion of the created list.

            LISTS vs. STRINGS. A list has the same structure as a string
          but on a "higher level."  A string is an ordered set of charac-
          ters, and a list is an ordered set of strings.

            List structures, however, can be extended to tree structures
          and even to arbitrary network structures.  Then the list-string
          analogy breaks down.  The greater flexibility of lists comes from
          the fact that their elements are not single characters, but
          rather CONS cells whose pointers can point to other lists.  Hence
          lists can be embedded in other lists indefinitely: Any single
          element of a list can be an arbitrarily complex list structure.

            More importantly, small changes in a complex list structure
          have only local impact.  If the same complex structure were en-
          coded as a string, then almost any change would require repacking
          the string, a costly and inefficient process.  Thus, lists allow
          flexible encoding of complex data structures because lists are
          organized into meaningful subunits and can, therefore, be modi-
          fied efficiently.


          Typical Operations on Strings and Lists
          ---------------------------------------

            The built-in functions of SNOBOL4 are specialized for string
          processing.  Those of LISP are specialized for list processing.
          String processing functions can read or write strings, build new
          strings, decompose old strings, or search existing strings for
          target characters or substrings.  List processing functions per-
          form the analogous operations on lists.

            STRING PROCESSING FUNCTIONS.  The following (typical) string
          processing functions are among the commonly used built-in func-
          tions in SNOBOL4.  They are used here simply as examples of typi-
          cal string processing functions.  The SNOBOL4 language will be
          described in more detail in a later section of the paper.

            1. RECORD = INPUT

               The next logical record is read from the input file.  It is
               stored in memory as a string of adjacent characters.  Its
               address becomes the value> pointer of the identifier RECORD.
               (By "the identifier RECORD," I mean the identifier named
               RECORD, i.e., the identifier whose name> pointer is the
               address of the string RECORD.)

            2. OUTPUT = RECORD

               The string whose address is in the value> field of RECORD is
               written to the output file.



       AI Programming in SNOBOL4       - 7 -                     August, 1982








            3. NEW = OLD1 OLD2

               A new string is constructed by concatenating the strings
               accessed via the value> pointers of OLD1 and OLD2.  The
               address of the newly formed string becomes the value>
               pointer of the identifier NEW.

            4. T = SUBSTR(FS,5,10)

               The string whose address is the value> pointer of FS is
               located in memory.  A new string is defined which has length
               10 and which starts with the fifth character of (the value
               of) FS.  The address of this substring becomes the value>
               pointer of the identifier T.  The value> pointer of PS is
               unchanged.

            5. XYZ '  ' = ' '

               The string addressed by the value> pointer of XYZ is
               located.  It is scanned "from left to right" for a pair of
               adjacent blanks.  The first such pair is replaced by a sin-
               gle blank.  The value> field of XYZ is changed so as to
               point to the altered string.  If no pair of blanks is found,
               then the statement fails and the value of XYZ is not
               changed.

            6. R LEN(10) $ PART1 REM $ PART2 = ''

               The string addressed by the value> pointer of R is located.
               The substring consisting of the first 10 characters of R
               becomes the value of PART1; the rest of R becomes the value
               of PART2.  Then the value of R becomes the null string (the
               string of length 0).  If R has fewer than 10 characters,
               however, the statement fails and the values of PART1, PART2,
               and R remain unchanged.

            LIST PROCESSING FUNCTIONS.  Just as the structure of lists is
          analogous to that of strings, so operations on lists are similar
          to operations on strings.  We can concatenate two strings to get
          a new string, and append one list to another to get a new list.
          We can break a string down into substrings or individual charac-
          ters, and break a list down into sublists or individual elements.
          We can search a string for a target character or substring, and
          search a list for a target element or sublist.

            The following typical LISP commands illustrate some common list
          I/O, composition, decomposition, and search functions:

            1. (SETQ RECORD (READ))

               The next complete list expression is read from the input
               file.  (It may be a single atom or a complex list.)  It is
               converted from its string representation to LISP's internal
               list representation, and the address of this list becomes



       AI Programming in SNOBOL4       - 8 -                     August, 1982








               the value> pointer of the identifier named RECORD.  This
               means that the value> pointer of RECORD is the address of
               the first top-level cons-cell of the list.

            2. (PRINT RECORD)

               The list addressed by the value> pointer of RECORD is con-
               verted to a string, which is written to the output file.
               Note that READing involves string-to-list conversion, and
               PRINTing involves list-to-string conversion.  Lack of aware-
               ness of these conversions, which are handled automatically
               in LISP's top-level READ-EVAL-PRINT loop, can lead to the
               mistaken idea that lists are really strings.  This is incor-
               rect: Lists are not represented internally as strings.  If
               they were (as mentioned above) list processing would be much
               less efficient.

            3. (SETQ NEW (APPEND OLD1 OLD2))

               The value> pointers of OLD1 and OLD2 both point to lists
               stored in memory.  A new list, consisting of the top-level
               elements of OLD1 followed by the top-level elements of OLD2,
               is constructed somewhere in memory.  A pointer to this new
               list is stored in the value> field of the identifier named
               NEW.

            4. (SETQ HEAD (CAR L))

               The value> pointer of L points to a CONS cell which is the
               first top-level element of an existing list.  The car>
               pointer of this cons-cell is the address of a string or
               list.  This address is copied into the value> field of the
               identifier named HEAD.

            5. (SETQ SUBLIST (MEMBER TARGET L))

               The value> pointers of L and TARGET point to existing lists.
               (The value of TARGET may be a string.)  The top-level ele-
               ments of L are examined sequentially.  If one is found which
               is equal to TARGET, then the tail of L starting with that
               element becomes the value of SUBLIST.

            Suppose the following data structures are in memory:

          string:[name> TARGET, value>
             string:[name> DOG, value> string:[*].

          string:[name> L, value>
             cons:[car> string:[name> SHARK, value> string:[*]], cdr>
               cons:[car> string:[name> FISH, value> string:[*]], cdr>
          ***    cons:[car> string:[name> DOG, value> string:[*]],
                   cdr> cons:[car> string:[name> BAD,
                      value> string[*]], cdr> cons:[*].




       AI Programming in SNOBOL4       - 9 -                     August, 1982








            In this context, (MEMBER TARGET L) will return the address of
          the first cons-cell in the list starting at the flagged (***)
          line.

            6. (SETQ REVISED (SUBST L NOW NEW))

               Every sublist of L that matches the value of NOW is replaced
               by the value of NEW.  The address of the revised list is
               stored in the value> field of REVISED, but the value> field
               of L remains unchanged.

            These examples are intended simply to illustrate some typical
          list processing functions.  Note that with lists, as with
          strings, most processing consists of building, decomposing, or
          searching.


                                THE SNOBOL4 LANGUAGE

            The following description of SNOBOL4 is intended to provide a
          quick overview of the language.  It is insufficient as a program-
          mer's guide, but I hope it will serve as adequate background for
          the rest of the paper.


          Datatypes
          ---------

            SNOBOL4 supports a variety of datatypes, including strings,
          integers, floating-point numbers, arrays, tables, expressions,
          patterns, code, and programmer-defined datatypes (Griswold, 1975,
          chapter 3).  Conversion between datatypes, where required, is
          usually automatic.  A concise description of SNOBOL4's structured
          datatypes is given in Lewis and Smith (1976, pp. 248-253).

            ARRAYS may be multidimensional, and subscript bounds may be
          negative.  The TABLE datatype is a one-dimensional array
          "subscripted" by items of any datatype (usually by strings).
          NAMES are similar to strings, though there are some technical
          differences.  PATTERNS, EXPRESSIONS, and CODE are procedural, in
          the sense that their evaluation normally involves more processing
          than simply accessing a value.


          Syntax and Statement Types
          --------------------------

            SNOBOL4 has a simple, statement-oriented syntax.  It is a non-
          interactive, compiled language.  The SPITBOL and FASBOL compilers
          produce efficient, optimized code while still supporting the full
          range of features available in the slower, interpreted version of
          the language.





       AI Programming in SNOBOL4       - 10 -                    August, 1982








            The advantages of compilation are somewhat undermined by the
          fact that subroutines cannot be compiled separately and indepen-
          dently.  According to Maurer (1976, pp. 90-92), this flaw is cor-
          rected in FASBOL.  As in LISP, structured programming devices are
          limited to the programmer-defined function, the statement label,
          and the goto command.  Also as in LISP, there are modifications
          of SNOBOL4 which encourage structured programming (University of
          Michigan Computing Center, 1975 Sommerville, 1979).

            The principal landmarks of the SNOBOL4 statement are the first
          column, the equals (=) sign, and the colon (:). Column 1 is used
          for special control characters which indicate commands to the
          compiler, statement continuation, comments, or statement labels.
          If a statement has a label, then the first character of the label
          must begin in column 1.  A statement may be continued over sev-
          eral input lines by putting a plus (+) in the first column of ev-
          ery line after the first.  Several statements may be placed on a
          single line by using the semicolon (;) as a statement terminator.

            The equals (=) sign separates the two major parts of the state-
          ment, the "pattern matching" part (left-hand side) and the
          "object" (right-hand side).  The pattern matching part may be
          further subdivided into the "subject" and the "pattern."

            The colon (:), if present, delimits the "goto field," which is
          used to control conditional and unconditional branching.

            Thus, the following prototype summarizes the syntax of the
          SNOBOL4 statement:

               <label> <subject> <pattern> = <object>  :<goto field>

            Since any statement may have a label and/or a goto field, the
          important types of statements consist of variations on

                       <subject> <pattern> = <object>

            The full (subject-pattern-object) form is called a "replacement
          statement."  The part of the "subject" string which is matched by
          the "pattern" gets replaced by the "object" string.  If the
          object is null (but the = sign is still present), the matched
          part of the subject is simply deleted.

            The subject-object statement, without a pattern, is an ordinary
          "assignment statement."  It has the same purpose as the assign-
          ment statement in other languages, viz., to change the value of a
          variable.  Since the value of a variable can be an object of any
          datatype, assignment statements can be used to create data struc-
          tures such as arrays and tables.

            The subject-only statement can consist of a single function
          call or several function calls enclosed in parentheses.  In the
          latter case, the function calls will be executed from left to
          right until one of them fails.  It is also possible to have sev-



       AI Programming in SNOBOL4       - 11 -                    August, 1982








          eral function calls in one statement without enclosing them in
          parentheses.  This is stylistically questionable, since the val-
          ues, if any, returned by the second through the last function
          calls will be concatenated to form a "pattern," which will then
          be applied to the "subject" returned by the first function call.
          In this case, it is possible for all the function calls to suc-
          ceed and yet to have the statement fail because of a spurious and
          unintended pattern matching process.

            The subject-pattern statement, without an equals sign, is a
          "pattern matching" statement.  It can control conditional branch-
          ing, depending upon whether or not the pattern "succeeds" in
          matching part of the subject.  Pattern matching statements can
          also control conditional assignment of values to variables.


          Pattern Matching
          ----------------

            Gimpel (1976, p. 11) describes the pattern matching capabili-
          ties of SNOBOL4 as "... so rich as to amount to a language within
          a language."  MTS users can get a sense of SNOBOL4 pattern match-
          ing by looking through the relevant documentation of the MTS sys-
          tem editor (University of Michigan Computing Center, 1979, pp.
          334-345).

            As the most distinctive feature of SNOBOL4, pattern matching
          certainly deserves more attention than I can give it here.  The
          reader is urged to consult Griswold and Griswold (1973, chapter
          4), Griswold, Poage, and Polonsky (1971, chapter 2), and Gimpel
          (1976, chapters 6, 7, 8, and 18).

            Pattern matching is somewhat related to the theory of languages
          and automata, as described, for example, in Denning, Dennis, and
          Qualitz (1978) or Hopcroft and Ullman (1979).  The pattern-build-
          ing functions and the syntax of SNOBOL4 patterns are especially
          adaptable to the implementation of parsers based on syntax graphs
          (compare Wirth, 1976, chapter 5, with Griswold et al., 1971,
          chapter 3).

            A SNOBOL4 pattern can be said to describe a set of strings, in
          the sense that a phrase-structure grammar (for example) describes
          a set of strings.  The pattern

                       POS(0) "*"

          describes the set of strings which have an asterisk as their
          first character.  The pattern

                       RPOS(2) ( LEN(1) $ L ) *L

          describes the set of strings which end with two identical charac-
          ters.




       AI Programming in SNOBOL4       - 12 -                    August, 1982








            Complex patterns are usually defined by a sequence of assign-
          ment statements in which larger patterns are built up from sim-
          pler components.  Besides making the structure of the pattern
          clearer, this method of definition makes it easier to save sub-
          strings by conditional or immediate value assignment (explained
          below) during the pattern matching process.  When a complex pat-
          tern definition is examined, reading the statements in reverse
          order, it often resembles a sequence of rewrite rules of the kind
          used in writing formal grammars.

            After a pattern is defined and assigned to a variable, it can
          be used in a pattern-matching or replacement statement.  The pat-
          tern matching process is best thought of as a special kind of
          function call:  The pattern is the function and the subject
          string is the argument.

            In terms of automata theory: The SNOBOL4 source statements
          which define the pattern give a "grammatical" description of the
          set of strings which that pattern will match.  The SNOBOL4 com-
          piler converts this description into a program (machine, automa-
          ton) which will "accept" just the set of strings described by the
          "grammar."

            This interpretation of SNOBOL4 pattern matching is not seri-
          ously misleading, but neither is it complete.  In addition to
          accepting or failing to accept its subject string, a pattern may
          have a number of side effects, most notably assignments and func-
          tion calls.

            Pattern matching involves scanning the subject string by moving
          a pointer called the "cursor."  The cursor is initially at posi-
          tion 0, immediately to the left of the first character of the
          subject.  Cursor movement is controlled by various pattern ele-
          ments.  The substring to the immediate right of the cursor can be
          tested to determine whether it matches a literal string or
          whether it is one of a specified set of alternatives.  Also, the
          position of the cursor itself can be tested.  The pattern ele-
          ments POS(N) and RPOS(N) succeed if the cursor is N characters
          from the left or right end of the subject string, respectively.

            As these operations -- cursor movement, substring testing, and
          cursor position testing -- are executed, assignments and expres-
          sion evaluations can occur as side effects.  Immediate value
          assignment ($) causes the substring matched by some subpattern to
          be saved as the value of a variable.  Conditional value assign-
          ment (.) is similar, but takes effect only if the entire pattern
          matching process succeeds.  Cursor position assignment (@) saves
          the current cursor position (the number of characters to the left
          of the cursor) as the value of a variable.  Any deferred expres-
          sion (an expression preceded by an asterisk) will be evaluated
          whenever it is encountered during the pattern matching process.






       AI Programming in SNOBOL4       - 13 -                    August, 1982








            For example, the following pattern will set X equal to the
          three-character substring immediately following the first occur-
          rence of 'DOG' in the subject string.

                       'DOG'   ( LEN(3) $ X )

            Here are the results of applying this pattern to each of sev-
          eral subject strings.

                       subject        result
                       -------        ------

                       'DOGMA'        failure
                                      (There are fewer than three
                                      characters after 'DOG'.)

                       'DOGMAN'       success, X = 'MAN'

                       'ADOGOODER'    success, X = 'OOD'

            The following pattern assigns values to P and Q such that the
          first occurrence of 'DOG' in the subject string occurs at loca-
          tions P+1 through Q.

                       @P 'DOG' @Q

            Here are the results of applying this pattern to each of sev-
          eral subject strings.

                       subject        result
                       -------        ------

                       'DOGMA'        success, P=0, Q=3

                       'ADOGOODER'    success, P=1, Q=4

                       'GODOT'        failure
                                      ('DOG' does not occur in the
                                      subject string.)

            The following pattern will evaluate ENEMY('CAT') if
          ENEMIES_LIST = 1 and the subject string contains 'DOG':

               'DOG' *EQ(ENEMIES_LIST,1) *ENEMY('CAT')

            The use of 'DOG' in the examples above shows how a literal
          string can be used as a pattern element.  A string- or pattern-
          valued variable, function call, expression, or deferred expres-
          sion could be used similarly.  Much of the power of pattern
          matching is due to SNOBOL4's built-in pattern elements and pat-
          tern-valued functions.

            The built-in pattern elements include the following: ARB
          matches any substring.  BAL matches any substring which is bal-



       AI Programming in SNOBOL4       - 14 -                    August, 1982








          anced with respect to parentheses.  FAIL causes backtracking.
          FENCE blocks backtracking.  REM matches the substring from the
          current cursor position to the end of the subject.

            The built-in pattern-valued functions include the following:
          ANY(S) matches any single character included in the string S.
          NOTANY(S) matches any character not in S.  BREAK(S) matches the
          substring up to the first occurrence of any of the "break" char-
          acters in S.  SPAN(S) matches up to the first occurrence of a
          character not in S.  LEN(N) matches any substring of length N.
          TAB(N) matches the substring from the current cursor position up
          to cursor position N.  ARBNO(P) matches any sequence of consecu-
          tive substrings, each of which is matched by the pattern P.

            Pattern elements -- built-in elements, built-in functions,
          string constants, string variables, deferred expressions, and so
          on -- can be combined by "concatenation" and "alternation."  Thus
          far, only concatenation has been illustrated.  Two pattern
          elements are concatenated simply by placing them side by side
          with one or more intervening blanks.  Concatenated pattern ele-
          ments must match adjacent substrings.

            The alternation operator (|) separates pattern elements which
          are tried successively.  If the pattern matching process fails at
          some later point, the process backtracks and tries the next al-
          ternative.  If all the alternatives have been tried, then the al-
          ternation expression fails.

            Here are three patterns, each of which matches the same set of
          strings, namely, CAR, CDR, CAAR, CADR, etc. up to four A's and
          D's (i.e., the names of the standard LISP CAR-CDR compounds).

                       'C' ANY('AD')
               +         ('R' | (ANY('AD')
               +           ('R' | (ANY('AD')
               +             ('R' | ANY('AD') 'R')) )) ))

                       'C' ('A' | 'D')
               +         @P ARBNO('A' | 'D') @Q 'R'
               +           *LE(Q - P, 3)

                       'C' *P SPAN('AD') @Q 'R' *LE(Q - P, 4)

            The side effects of pattern matching often involve conditional
          assignment and conditional branching.  The conditions here are
          the "success" or "failure" of the pattern matching process.
          "Predicates" in SNOBOL4 also succeed or fail (rather than return-
          ing T or NIL, 1 or 0, .TRUE. or .FALSE., etc.).  For example,
          EQ(5,5) succeeds, and GT(1,7) fails.  Programmer-defined func-
          tions succeed by executing :(RETURN) and fail by executing
          :(FRETURN).  Therefore, the success or failure of pattern match-
          ing can be controlled by evaluation of expressions as well as by
          testing substrings. Both methods are used in the CAR/CDR examples
          above.



       AI Programming in SNOBOL4       - 15 -                    August, 1982








            Success and failure control "assignment" in that, if any part
          of an assignment or replacement statement fails, then the entire
          statement fails, and no values are changed.  Success and failure
          control "branching" through the selection of "S" or "F" clauses
          in the goto field.  The "S" branch is taken if the statement suc-
          ceeds; the "F" branch is taken if it fails.

            The following program fragment shows a typical SNOBOL4 loop.
          It illustrates the use of a predicate function and conditional
          branching.

                       SUM = 0
                       N = 10
                       I = 0
               SUM.LOOP
                       I = LT(I,N) I + 1        :F(SUM.LOOP.END)
                       SUM = SUM + I            :(SUM.LOOP)
               SUM.LOOP.END

            The interesting statement here is the one at SUM.LOOP.  This
          statement tests the loop index I, terminates the loop if N itera-
          tions have been completed, else increments I and continues.  Syn-
          tactically, this is an assignment statement.  The right-hand side
          consists of a binary expression: a function-call, LT(I,N); a con-
          catenation operator, blank; and a binary arithmetic expression, I
          + 1.  LT is a built-in predicate function.  If I < N, it suc-
          ceeds, returning the null string, which is concatenated with the
          value of I + 1, yielding simply the value of I + 1.  Hence, I is
          incremented and the entire statement succeeds.  There is no "S"
          clause in the goto field, so control passes to the next statement
          in sequence.

            If I >= N, on the other hand, then LT(I,N) fails, the value of
          I + 1 is never computed, the whole statement fails, the value of
          I is unchanged, and the "F" branch is selected.  Control trans-
          fers to the statement labeled SUM.LOOP.END, and execution contin-
          ues from there.

            Patterns may also be used to "drive" programs.  Sometimes side
          effects become the main purpose of the pattern, evoking vague
          images of DNA and RNA, or perhaps punched paper tape.

            As one fairly straightforward example of this technique, con-
          sider how pattern matching can be used to implement the evalua-
          tion of arbitrary Boolean expressions. The atomic units of these
          expressions will be SNOBOL4 predicate functions (possibly pro-
          grammer-defined).  We can use pattern concatenation for "and",
          pattern alternation for "or," and the standard negation operator
          (~) for "not."

            The trick in this case is to use the null string (or any dummy
          string) as the subject, simply as a syntactic place-holder.  No
          "real" pattern matching occurs, yet the pattern gets evaluated,




       AI Programming in SNOBOL4       - 16 -                    August, 1982








          and it succeeds or fails depending upon whether the corresponding
          Boolean expression is true or false.

            For example, consider the LISP expression

                       (OR (EQ V 13)
                           (AND (LESSP V (DIFFERENCE 7 N))
                                (ZEROP (VALUE (POTR PL (PLUS N V))))
                                (NOT (EMPTY (OPP (POTR PL (PLUS N V))))))
                       (AND (GREATERP V (DIFFERENCE 13 N))
                            (LESSP V 13)
                            (EMPTY (POTR PL (PLUS N-13 V))))

            This could be translated into SNOBOL4 as follows:

                       DUMMY.SUBJECT
                       +     POS(0)    EQ(V,13)
                       +     | LT(V, 7 - N)
                       +       EQ(0, VALUE(POTR(PL, N + V)))
                       +       ~EMPTY(OPP(POTR(PL, N + V)))
                       +     | GT(V, 13 - N)
                       +       LT(V,13)
                       +       EMPTY(POTR(PL, N - 13 + V))

            This is just one example of a nonstandard use of pattern match-
          ing.  This particular use seems well motivated: SNOBOL4 has no
          built-in AND or OR functions, evaluation of Boolean expressions
          is often useful, and the resulting pattern expressions serve to
          clarify, not to obscure, what is happening.  The use of nonstan-
          dard pattern matching, however, must be carefully considered:
          "Clever" tricks may be quite costly.

            As Griswold (1975, p.14) remarks: "This kind of programming ...
          appeals to some programmers and repels others.  It offers the ad-
          vantages of compactness, efficiency in some situations, and in-
          tellectual challenge.  On the other hand, such programming meth-
          ods tend to be difficult, obscure, error-prone, inefficient in
          some situations, and particularly susceptible to idiosyncrasies
          [of the implementation]."


          Input and Output
          ----------------

            SNOBOL4 handles input and output by associating variables with
          files.  The built-in functions INPUT and OUTPUT are used for this
          purpose.  After the statements

                       INPUT('XIN',,,'CON:')
                       OUTPUT('YOUT',,,'CON:')

          have been executed, the variables XIN and YOUT are input- and
          output-associated, respectively, with the user's terminal.  This
          means that any request for assignment from XIN will cause a



       AI Programming in SNOBOL4       - 17 -                    August, 1982








          record to be read from the terminal, and any assignment to YOUT
          will cause the assigned value to be written to the terminal.


          Programmer-defined Function
          ---------------------------

            Functions are defined by calling the built-in function DEFINE.
          In SNOBOL4, the argument to DEFINE is a string which is the
          "prototype" of the function.  It specifies the name of the func-
          tion, the names of the dummy arguments, and the names of any
          local variables.  An optional second argument to DEFINE gives the
          label of the entry-point if it differs from the function name.
          Changes in the values of dummy arguments and local variables have
          no effect outside the function itself.

            The function body is not included in the argument to DEFINE.
          When a defined function is called, control branches to the state-
          ment whose label matches the name of the function, or the label
          specified by the second argument to DEFINE.  There must be
          exactly one such statement in the program.  Returning from a
          function is accomplished by a quasi-goto, a branch to one of the
          three reserved labels, RETURN, FRETURN, or NRETURN.

            As in LISP, every successful function call returns a value.
          The value returned is the value assigned to the identifier whose
          name matches the function name.  For example, a function named
          OTTO returns whatever value is assigned to the variable OTTO at
          the time the return is executed.

            All defined functions are recursive.  "Values" are normally
          passed to functions, but "names" may be passed by using the unary
          name operator (.) or by enclosing the name in quotes.  The tech-
          nical details of SNOBOL4 argument-passing are very similar to
          those of LISP (see Winston & Horn, 1981, 419-420.)


          Unary and Binary Operators
          --------------------------

            SNOBOL4 has a number of built-in functions which are invoked by
          operators.  The same characters serve as unary and as binary
          operators, and there is no connection between the two uses of a
          given character.

            The predefined unary operators are negation (~), interrogation
          (?), value ($), name (.), defer (*), unary plus and minus (+ and
          -), cursor position assignment (@), and keyword (&).

            The predefined binary operators are immediate value assignment
          ($), conditional value assignment (.), exponentiation (^, ! or
          **), the standard arithmetic operators (+, -, *, and /), pattern
          and string concatenation (blank), and pattern alternation (|).




       AI Programming in SNOBOL4       - 18 -                    August, 1982








            The following operators are not predefined: unary !, %, /, #,
          and |; binary ~, ?, %, #, @, and &. These operators can be
          defined by the programmer, by using the OPSYN function.  OPSYN
          makes an undefined operator or function name synonymous with a
          defined function.

            For example, in using the technique of Boolean expression eval-
          uation described above, the programmer might want to introduce
          the & operator for "and," in order to make the expressions
          clearer.  This could be accomplished by means of a function and a
          call to OPSYN:

                       DEFINE('AND(Pl,P2)')     :(AND_END)
               AND     AND = Pl P2              :(RETURN)
               AND_END OPSYN('&','AND',2)

            This redefinition would introduce one slight complication:
          Precedence of all operators, even free operators, is predefined.
          It so happens that & has lower precedence than |.  Therefore,
          parentheses would be necessary to ensure that conjunctions were
          performed before disjunctions.


          Programmer-defined Datatypes
          ----------------------------

            Datatypes with labeled fields are convenient for many AI appli-
          cations (Charniak et al., 1980, chapter 4; Shapiro, 1979, pp.
          142-143).  These are easily implemented in SNOBOL4 by means of
          the built-in function DATA.  The CONS datatype, for example,
          could be defined in SNOBOL4 as follows:

                       DATA('CONS(CAR,CDR)')

            After this function-call, T and NIL could be defined as
          follows:

                       NIL = CONS() ; T = CONS()
                       CAR(NIL) = NIL ; CDR(NIL) = NIL
                       CAR(T) = T ; CDR(T) = T


          EVAL and CODE
          -------------

            EVAL and CODE are built-in SNOBOL4 functions which have special
          importance for AI applications.  EVAL takes a string or expres-
          sion argument and interprets it as a SNOBOL4 expression.  It
          returns the value of the expression.  For example,

                       EVAL( *REVERSE('ABCDE'))

          returns 'EDCBA'.




       AI Programming in SNOBOL4       - 19 -                    August, 1982










            CODE takes a string argument and interprets it as a series of
          SNOBOL4 statements.  Each statement but the last must end with a
          semicolon (;).  CODE compiles the program fragment and returns
          the object code, which becomes accessible from the current pro-
          gram.  One way to execute this code would be to branch to a
          statement label it contains.  For example, the following fragment
          would print 76 and then continue execution at the statement
          labeled ZLABEL.

                       CODE('ALABEL SIX = 4 + 2 ; SEVEN = 9 - 2 ; '
               +          ' OUTPUT = SEVEN SIX   :(ZLABEL)'  )
               +               :(ALABEL)
               ZLABEL

            It is pointless to call CODE with a literal string argument, as
          in the example above.  But it can be called with an argument
          which is a string-valued variable.  The program fragment assigned
          to that variable could be an entire subroutine constructed under
          program control and dependent on input of various sorts.  The AI
          potential is obvious.  CODE also has more mundane applications.
          For example, it is instrumental to the function DEXTERN (Gimpel,
          1976), which loads and compiles external functions at run-time.


          Keywords
          --------

            Keywords are special variables preceded by the unary operator
          &.  They control various aspects of program execution.  For exam-
          ple, &TRIM = 1 instructs the program to trim trailing blanks off
          every input record; &DUMP = 1 means  that a dump of all variables
          and their values should be written to OUTPUT at the end of execu-
          tion; &STCOUNT is equal to the number of statements executed at
          any point during a run; &TRACE = 0 turns off all tracing; &FTRACE
          = 100 means that all defined functions should be traced on call
          and return until 100 trace messages have been printed.


          Tracing
          -------

            SNOBOL4 has good facilities for tracing program execution.
          Tracing can be turned on and off selectively, under program con-
          trol, by means of the TRACE and STOPTR functions and the keywords
          &TRACE and &FTRACE.

            The TRACE function allows the programmer to request an informa-
          tive message for every change of value for each of a specified
          subset of variables; for every call and/or every return from each
          of a specified subset of user-defined functions; for every trans-
          fer of control to any of a specified subset of statement labels;




       AI Programming in SNOBOL4       - 20 -                    August, 1982








          and/or for every change of value of any of a specified subset of
          keywords.

            As described above, the &FTRACE keyword allows tracing to be
          turned on for all calls to and returns from each user-defined
          function; and the &TRACE keyword can be used globally to turn on
          and off all tracing except that controlled by &FTRACE.

            Instead of using the default tracing messages, the programmer
          may use tracing interrupts defined by TRACE to activate any pro-
          grammer-defined function.  The following tools are available to
          help the programmer define special-purpose tracing functions:

          ARG(function-name,N) returns the name of the Nth argument for a
          given function.

          LOCAL(function-name,N) returns the name of the N local variable
          for a given function.

          FIELD(datatype,N) returns the name of the Nth field of a pro-
          grammer-defined datatype.

          DATATYPE(X) returns the datatype of the object X.

          &STNO is the statement number of the currently active statement.

          &LASTNO is the statement number of the last completed statement.

          &RTNTYPE is the type of return (RETURN, FRETURN, or NRETURN) from
          the last completed function.


          Features of SNOBOL4 Important for AI Programming
          ------------------------------------------------

            The following characteristics of SNOBOL4 are particularly
          important for AI programming: It is a flexible language because
          it is associative, that is, based on links or pointers which
          associate one data object with another.  Data structures do not
          have to be declared.  Any identifier can have a value of any
          datatype, and that datatype can change freely during program exe-
          cution.  Dynamic storage allocation and automatic "garbage col-
          lection" are transparent to the programmer.

            The function or subroutine is the natural unit of program
          design, and all programmer-defined functions are recursive.
          Arguments are passed to subroutines by reference, although it is
          also possible to pass by name.  Functions have some degree of
          isolation from the rest of the program, though not as much as
          FORTRAN subroutines.  LISP and SNOBOL4 have similar problems with
          respect to the scope of names, name conflicts, the need for
          unique names in certain contexts, and so on.





       AI Programming in SNOBOL4       - 21 -                    August, 1982








            SNOBOL4 allows expressions to be constructed, coded, and evalu-
          ated at run-time.  This means that programs can be self-modify-
          ing, and that the program/data distinction is far less rigid than
          in other programming languages.

            The following built-in functions are particularly useful in AI
          programming: APPLY, CODE, DATA, DATATYPE, EVAL, ITEM, OPSYN,
          PROTOTYPE, and TABLE.  The name (.), value ($), and unevaluated
          expression (*) operators are also handy, as are the free
          operators.

            Pattern matching also has many different uses, including simple
          string processing, mapping functions, compilation, and concept
          learning (see Shapiro, 1979).


          Programming Style
          -----------------

            SNOBOL4 lacks the control structures which have come to be
          expected in a programming language, structures such as
          IF...THEN...ELSE, LOOP...WHILE...UNTIL, BEGIN...END, PROCEDURE,
          CASE, and so on (Dijkstra, 1976; Gries, 1981; Wirth, 1976).  On
          the other hand, there are extensions of SNOBOL4 which permit the
          use of such control structures (Sommerville, 1979; University of
          Michigan Computing Center, 1975).

            Normally, however, in the hands of a novice, SNOBOL4 tends to
          encourage (or to fail to discourage) the writing of ugly, hard-
          to-read, hard-to-debug code.  In developing large programs, the
          programmer must adopt sensible conventions.  Bad practices which
          are permitted must be actively avoided.  For a detailed discus-
          sion of programming style, see Gimpel (1976, pp. 11-21).


          Comparison of SNOBOL4 with Other Languages
          ------------------------------------------

            LISP.  It is clear from the preceding discussion that SNOBOL4
          and LISP share many features which differentiate them from other
          programming languages.  Some features which are widely considered
          unique to LISP turn out to be shared by SNOBOL4, e.g.,
          serviceability as a target language into which "higher level" or
          special-purpose languages can be compiled (McCarthy, 1981;
          Gimpel, 1976, chapter 18; Winston & Horn, 1981; and below).

            Both LISP and SNOBOL4 are nonnumerical, associative, and
          flexible.  Both make frequent use of recursive functions.  Both
          allow the construction and execution of code at run-time.

            What, then, are the major differences between the two
          languages?





       AI Programming in SNOBOL4       - 22 -                    August, 1982








            LISP is primarily interpreted and interactive, though
          compilation is sometimes permitted.  SNOBOL4 is primarily
          compiled and non-interactive, though interpreted, interactive
          versions exist.  Of course, interactive here refers to the
          programming phase.  Once written, programs in either language may
          or may not interact with someone during execution.

            LISP has a uniform, logical syntax: S-expressions represent
          programs and data structures alike.  Semantically, everything is
          done with lists: Data structures are lists, and programs are also
          lists.  Therefore, a given list may be treated as data at one
          point in a program and as a subroutine at another point.

            SNOBOL4 supports a variety of datatypes, including arrays, hash
          tables, patterns, expressions, code, and programmer-defined
          datatypes.  Patterns, expressions, and code are all procedural.
          Each can be defined (that is, constructed) during program
          execution, and then later used procedurally (evaluated or
          executed).  From the programmer's point of view, all this is done
          without list processing. The capacity to build and use procedural
          datatypes is unrelated to the capacity to manipulate lists.

            There are other reasons for downplaying the significance of
          list or string processing per se: Strings can be converted to
          lists, and lists can be converted to strings.  See, for example,
          Gimpel (1976, chapter 5); or consider what goes on during the
          READ and PRINT phases of LISP's READ-EVAL-PRINT loop.
          Furthermore, strings can be processed by LISP as lists of single-
          character atoms, while lists can be implemented in SNOBOL4 as
          programmer-defined datatypes.  In fact, the SNOBOL4 DATA function
          may be more useful in some cases than general purpose list
          processing functions (Shapiro, 1979, pp. 141-143; Charniak,
          Riesbeck, & McDermott, 1980, chapter 4).

            The decision to use strings or lists is often up to the
          programmer.  A specific application may not dictate the use of
          one or the other.  And neither lists nor strings are particularly
          useful for most numerical applications: LISP and SNOBOL4 both
          need their complement of specifically numerical functions.

            Thus, there are two major differences between LISP and SNOBOL4:
          LISP has a simpler syntax and supports fewer datatypes than
          SNOBOL4; and LISP is usually interactive/ interpretive while
          SNOBOL4 is usually compiled.  The practical significance of these
          differences would seem to be dependent upon the aesthetic
          preferences of the programmer and the nature of the specific
          programming task.

            ICON.  The Icon programming language (Griswold, 1978b; Griswold
          & Hanson, 1980; Griswold, Hanson & Korb, 1979) is the most recent
          descendant of SNOBOL4 (see also Griswold & Hanson, 1977b).  It
          differs from SNOBOL4 in two major respects: First, it has control
          structures like those of Algol and PASCAL.  Second, it is
          designed to be small, efficient, and portable (Griswold, Hanson,



       AI Programming in SNOBOL4       - 23 -                    August, 1982








          & Wampler, 1980; Hanson, 1979).  "Unlike SNOBOL4 and SL5, Icon is
          intended to be practical for production applications" (Griswold,
          Hanson, & Korb, 1979).

            Icon supports a variety of datatypes and related functions:
          stacks, lists, programmer-defined records, sets, and tables.

            Programmer-defined functions are recursive and may be suspended
          for later reactivation.  Compared with SNOBOL4, backtracking has
          been refined and is better integrated with the rest of the
          language (Griswold & Hanson, 1977a).  This has been accomplished
          through the use of generators (Griswold, 1978a; Griswold &
          Hanson, 1977; Griswold, Hanson, & Korb, 1981).  Generators are
          designed to facilitate goal-directed programming.  Their
          evaluation is oriented toward seeking successful results in the
          presence of alternative possible values, as do SNOBOL4 pattern
          alternation expressions.

            Griswold, Hanson, and Korb (1981) discuss some AI applications
          of Icon, especially its advantages over CONNIVER (McDermott &
          Sussman, 1973) and PLANNER (Hewitt, 1969).

            It would seem, on balance, that Icon is an improvement over
          SNOBOL4.  Many of the strengths of SNOBOL4 have been retained,
          and some weaknesses (large size, low efficiency, and lack of
          control structures) have been eliminated.

            There are some drawbacks to Icon, however: Code construction
          and execution at run-time are not possible.  This could be seen
          as a fatal flaw as far as AI programming is concerned.  Also, it
          is not clear that Icon would be as suitable as SNOBOL4 for use as
          a target language into which special purpose languages could be
          compiled.

            Although, to the extent that well-structured, goal-directed
          programs are important in AI, Icon may prove useful, it has not
          inherited the full power and flexibility of SNOBOL4: A LISP
          programmer would probably feel restricted by Icon (and liberated
          by SNOBOL4!).


                                      EXAMPLES

            The following five examples of SNOBOL4 programs range from a
          simple sorting program to a special-purpose compiler.  I have
          chosen these examples with two purposes in mind: First, to
          provide some concrete and realistic examples of SNOBOL4 programs;
          and second, to support my claim that SNOBOL4 deserves wider
          consideration as an AI programming language.

            There are three ways in which SNOBOL4 can be used in AI
          programming.  First, it can be used directly, taking advantage of
          its recursive functions, its pattern-matching capabilities, and
          its extendibility by means of user-defined datatypes.  Direct



       AI Programming in SNOBOL4       - 24 -                    August, 1982








          applications of SNOBOL4 to AI programming are illustrated in
          Darlington (1971, 1972), Shapiro (1979), and in the Wang's
          Algorithm, English Morphology, and Kalah examples below.

            Second, SNOBOL4 can emulate LISP.  That is, list-processing
          functions can be written in SNOBOL4 which parallel most of the
          standard LISP functions.  Of course, it would not be too
          difficult to go all the way and implement one's own favorite
          version of LISP in SNOBOL4.  It seems more prudent, however, to
          embed the LISP-like functions in SNOBOL4, so that SNOBOL4's
          intrinsic string-processing and pattern-matching strengths can
          also be exploited.  That is what I have tried to do with the
          SNOLISPIST routines, which are described below and in Appendix F.
          The SIR and TEST programs (see below and Appendices G and H)
          illustrate the use of these routines.

            Finally, rather than using SNOBOL4 directly or quasi-
          implementing LISP in SNOBOL4, the programmer may choose to define
          a special-purpose AI language (e.g., Charniak et al., 1980,
          chapter 17).  SNOBOL4 and LISP are the only two widely available
          languages which can easily be used both as target languages and
          as host languages for compilers (McCarthy, 1981; Uhr, 1973;
          Winston & Horn, 1981). This aspect of SNOBOL4 programming is
          extensively illustrated in Uhr (1973), as well as in the modest
          Augmented Transition Network language described below.

            Uhr used SNOBOL4 to implement a simple, yet powerful,
          programming language which he called EASEy (Encoder for
          Algorithmic Syntactic English).  He then used EASEy to write a
          large number of illustrative AI programs for his book. These
          programs are still valuable as easily comprehended examples of AI
          programming in pattern recognition, visual feature abstraction,
          game playing, theorem proving, and inductive learning.


          Quicksort
          ---------

            C. A. R. Hoare's Quicksort algorithm (Berztiss, 1975; Gimpel,
          1976; Wirth, 1976; Gries, 1981) is an efficient method for
          sorting a one-dimensional array A of N elements with respect to a
          two-place predicate P.  The array A is completely sorted when
          P(A<I>,A<J>) is true for all 1 <= I <= J <= N.

            The program in Appendix A is based on Gimpel's (1976) version
          of Hoare's algorithm.  It is included as an example of a SNOBOL4
          program that is short, simple, instructive, useful, and recursive
          -- though it doesn't have much to do with AI.

            The program consists of four function definitions (statements
          1-4), the sorting subroutine (5-20), three one-line functions
          (21-25), and the main program (27-46).





       AI Programming in SNOBOL4       - 25 -                    August, 1982








            The main program establishes I/O associations (statements 27-
          28), reads the input file once to determine the number of records
          (29-33), allocates an array of the appropriate size (34), rereads
          the input file into the array (35-40), calls the sort routine
          (41), and writes the sorted array to the output file (42-46).
          The function call in statement 41 is set up to do a lexical sort
          in ascending order (SNOBOL4 predicate LLE).

            The sorting routine HSORT calls HSORT.SWAP to interchange two
          values, and it calls HSORT.OK or HSORT.KO to determine whether or
          not two values need to be interchanged.

            After checking for termination (statements 5-9), HSORT picks a
          value C near the middle of the array (11) and initializes two
          indices J and K (12-13) used in the loops at HSORT2 and HSORT3.

            At HSORT2, J is incremented until P(C,A<J>) succeeds, that is,
          until C and A<J> are in the wrong order (14-15).  At HSORT3, K is
          decremented until P(A<K>,C) succeeds, that is, until A<K> and C
          are in the wrong order (16-17).

            If J < K then A<J> and A<K> are in the wrong order.  They are
          swapped (18), and the search for an incorrectly ordered pair
          continues at HSORT2.

            If J >= K then the array segment from I to N has been
          partitioned into two segments such that P(X,Y) is true if X is in
          the lower segment and Y is in the upper segment.  HSORT calls
          itself recursively to partition each of these two segments
          (statements 19-20).

            The recursion terminates when a segment contains two items or
          fewer (statements 6-8).  If there are exactly two items and they
          are in the wrong order, then they must be swapped (8).

            This example illustrates the use of programmer-defined
          functions, recursion, file I/O, dynamic array allocation
          (statement 34), formatted output (45), and several typical loops
          (14-15, 16-17, 32-33, 36-40, and 42-46).  Note that a change in
          the fourth argument to HSORT (at statement 41) is sufficient to
          switch to any combination of ascending or descending sort, with
          string or numeric data.


          Wang's Algorithm
          ----------------

            Wang's Algorithm is a method for proving or disproving formulas
          in the propositional calculus.  The program in Appendix B is a
          modified version of a program from Griswold, Poage, and Polonsky
          (1971).  Shapiro (1979) presents a LISP program for Wang's
          Algorithm.





       AI Programming in SNOBOL4       - 26 -                    August, 1982








            After the definition of the principal function (statement 1),
          several patterns are defined (2-7).  These patterns are used to
          analyze formulas into their component parts, and to sort them
          into two categories, unary or binary.  The body of the function
          WANG extends from statement 8 to statement 41.

            The main program consists of some keyword settings (statements
          42-44), I/O associations (45-46), and one loop (48-54) which
          reads, evaluates, and reports on formulas until an end-of-file is
          detected.  The execution of statement 53 is conditional on the
          success of the call to WANG.  If WANG succeeds, then 'VALID' is
          printed and the :S(READ) branch is taken.  If WANG fails, then
          control passes to the next statement, 'INVALID' is printed, and
          the :(READ) branch is taken.

            Several features of pattern matching are illustrated in the
          patterns UNOP through ATOM (statements 2-7).  Recall that a
          pattern describes a scanning operation on a string (the subject)
          which either succeeds (matches) or fails.

            UNOP (with &ANCHOR=O) will succeed for any subject which
          contains 'NOT' as a substring.  BINOP will succeed for any
          subject containing 'AND', 'OR', 'IMP', or 'EQU'.

            UNOP.FORMULA looks for a blank, followed by UNOP ('NOT'),
          followed by a left parenthesis, followed by a substring that is
          balanced with respect to parentheses (built-in primitive pattern
          element BAL), followed by a right parenthesis -- something like '
          NOT(AND(P,Q))'.  If UNOP.FORMULA succeeds then the substring
          matched by UNOP becomes the value of OP, and the part matched by
          BAL becomes the value of PHI.

            BINOP.FORMULA is similar to UNOP.FORMULA, except that it
          matches strings like ' AND(OR(P,Q),NOT(R))', with the
          assignments, in this case, of OP = 'AND', PHI = 'OR(P,Q)', and
          PSI = 'NOT(R)'.

            FORMULA matches anything matched by UNOP.FORMULA or
          BINOP.FORMULA, and performs the appropriate assignments.

            ATOM matches a substring of one or more non-blanks.  If no
          blank is found, ATOM will match everything up to the end of the
          subject string -- that is the effect of REM.  The substring
          matched by ATOM becomes the value of A.

            The details of WANG will not be discussed except to say that
          ANTECEDENT and CONSEQUENT are processed similarly, at statements
          10 and 25, respectively.  In either case, the first FORMULA on
          the left is dissected and deleted, its OP determining which
          branch will be taken.  Each branch entails one or two recursive
          calls of WANG.

            The recursion terminates when neither the ANTECEDENT nor the
          CONSEQUENT contains a FORMULA.  In this case, the ANTECEDENT and



       AI Programming in SNOBOL4       - 27 -                    August, 1982








          CONSEQUENT both consist entirely of ATOMs. Each ATOM in
          ANTECEDENT is picked off (statement 39) and searched for in
          CONSEQUENT (40).  A match produces success.  A series of non-
          matches finally terminates in failure if ANTECEDENT is reduced to
          the null string.  If any recursive path eventually leads to
          failure, the original function call fails: The formula is not a
          theorem.

            Besides pattern matching and recursion, this example
          illustrates SNOBOL4's version of the computed goto (statements 10
          and 25).  The odd-looking expression in the goto field

                                                S( $('WANG.A.'  OP) )

          means, "On success, take the value of OP, stick 'WANG.A.' on the
          front of it, and jump to the statement with that label."


          English Morphology
          ------------------

            Winograd (1972) gives a flowchart for the analysis of English
          word-endings.  The purpose of this analysis is to reduce the
          number of lexical entries in a natural language understanding
          program.  Many inflected forms do not have to be stored in the
          dictionary.

            The program in Appendix C is based on Winograd's flowchart.
          The program contains one large subroutine, WORDEND (statements 7-
          49), which uses four short subroutines, MATCH, CUT, ADDON, and
          TRY.  Each of these subroutines operates on WRD, the provisional
          root lexical entry.

            MATCH (50-51) tests the end of WRD against a pattern PAT.

            CUT (52-53) deletes the last N letters of WRD.

            ADDON (54-55) appends a string X to WRD.

            TRY (56-57) looks up WRD in the DICTIONARY to see whether or
          not it is a root lexical entry.

            In WORDEND, the following statements deserve special attention:
          In statement 9, the pattern DOUBLE is defined so as to match any
          string which ends with two identical letters.  This is
          accomplished by a combination of immediate value assignment ($)
          and deferred evaluation (*).  When LEN(1) matches a letter, that
          letter immediately becomes the value of the variable L.  *L means
          the value of L at the time it is referenced during pattern
          matching (as opposed to the value L may have had when the pattern
          DOUBLE was initially defined).  Recall that deferred evaluation
          means evaluation at use-time instead of at definition-time.  The
          RPOS(0) element forces the pattern to match at Right POSition
          zero, that is, at the right-hand end of the subject string.



       AI Programming in SNOBOL4       - 28 -                    August, 1982








            Statement 13 determines, in one fell swoop, whether or not
          WORDEND is going to be helpful at all.  If none of the word-
          endings match the end of WRD, then a direct dictionary look-up is
          tried immediately.  If the disjunctive pattern does succeed, then
          WEND records just which ending did match.

            The rest of WORDEND is like a production system.  Each line
          consists of one or more tests which must be conjunctively
          satisfied, followed by one or more operations on WRD, and finally
          a branch to the next appropriate rule. SNOBOL4 is well-suited to
          this type of program structure, since, within each statement,
          function calls are executed from left to right until one fails or
          the statement is completed.

            The unary negation operator (~) used in statements 22, 26, 31,
          33, etc. converts success to failure and vice versa.

            The second argument to MATCH in statement 19 will match 'SS',
          'SZ', 'ZS', or 'ZZ'.

            The main program (59-70) illustrates a typical use of pattern
          matching in setting up the dictionary (63-66): Words are picked
          off one at a time and assigned to W.  They are recorded by
          setting DICTIONARY<W> = 1 (statement 65). DICTIONARY is a hash
          table, defined in statement 61.


          Kalah
          -----

            Kalah is a two-person game of strategy which involves
          distributing "stones" among "pots."  The first player to
          "capture" a majority of the stones wins.  Shapiro (1979, pp. 31-
          55) describes the rules of the game and provides a LISP program
          to play it.  The program uses the alpha-beta algorithm, a
          recursive game-tree searching algorithm.

            The program in Appendix D is a SNOBOL4 program based on
          Shapiro's LISP program.  To facilitate the comparison of LISP and
          SNOBOL4 code, a LISP version of the Kalah program has been
          interleaved with the SNOBOL4 version.

            For most subroutines, the SNOBOL4 code closely parallels the
          LISP code.  The SNOBOL4 code could have been made to parallel the
          LISP code even more closely (see Appendix H), but here no special
          package of list processing functions was used, and no special
          attempt was made to emulate LISP.  The following paragraphs will
          focus on some of the differences between the LISP and SNOBOL4
          programs.

            After the usual preliminaries (statements 1-11), there are two
          datatype definitions (12-13) which replace the LISP functions
          OWNER, NUM, OPP, PLAYER, and MOVEOF.  The PATHs around the




       AI Programming in SNOBOL4       - 29 -                    August, 1982








          playing board are also incorporated into the PPATH and OPATH
          fields of the POT datatype.

            The STACK datatype (14) is used for pushdown stacks. Statements
          15-25 define the global constants null, nil, t, and nilpot.
          Statements 26-29 define some simple utility patterns.

            The function-definition function DEF (30-39) requires some
          explanation.  It takes a function name (NAME), a string of dummy
          arguments separated by blanks (ARGS), a string of local variables
          separated by blanks (LOCALS), a function body (BODY), and a
          return type (RTN).  The return type is null, 'S', 'F', or 'N'.

            DEF does three things.  First, it constructs a prototype for a
          function named NAME with arguments ARGS and locals LOCALS.  The
          blanks in ARGS and LOCALS are changed to commas (statements 31-
          32) and a calI to DEFINE is executed (33).  Second, the
          appropriate type of return is added to BODY (34-37).  Third, the
          function is compiled (38).  There are many examples of the use of
          DEF throughout the program (e.g., statements 47-50).

            APPEND3 (statements 40-46) makes one stack out of three stacks
          (S1, S2, and S3).  It is used in EXPAND1 to effect a simple move-
          ranking strategy: S3, S2, and S1 contain ordinary, better, and
          best moves, respectively.  APPEND3 illustrates both recursion and
          the use of a data structure building function (43-45).

            CNTR (51-55) returns a string V centered in a field of N spaces
          by padding on the left and right with blanks.  PRT (57) uses
          PRT_PAT (56) to write a string to the user's terminal and to a
          "log" file, by means of chained immediate value assignment:

                       $ OUTPUT $ SHADOW

            The SNOBOL4 version of OTHER (86) uses indirect reference via
          the unary value ($) operator.  If PL = 'P', then $( "OTHER" PL )
          evaluates to $"OTHERP", that is, the value of "OTHERP", which is
          'O'.  If PL = 'O', then $( "OTHER" PL ) = $"OTHERO" = 'P'.  In
          general, $<expr> is the value of the string or name which is
          obtained by evaluating the expression <expr>.  Thus, $'X' means
          the value of X, and $X means the value of the value of X.  The
          same device is used in POTR (87), KALAHR (88), and SIDER (97).

            Simple stack operations are defined in VALUE (89), PUSHVAL
          (90), POPVAL (91), and CHANGEVAL (92).  TOP, KVALUE, STACK, and
          REST are all field-access functions which were created by the
          calls to DATA in statements 12 and 13.

            SETPATH (98-103) and SETSYM (104-109) are more obscure than
          they need to be, but they do serve to illustrate some of the
          programming techniques which are possible with SNOBOL4 pattern
          matching.





       AI Programming in SNOBOL4       - 30 -                    August, 1982








            First consider the arguments P and LAT that are passed to
          SETPATH (see statements 216 and 217).  P is the name of a field
          (PPATH or OPATH), and LAT is a list (loosely speaking) of the
          names of all the pots, in order along the path P.  The idea of
          SETPATH is to set the value of field P for each pot A to the
          successor of A along the path P.

            This is accomplished in a two-statement loop (101-102).
          Statement 101 uses SETPATH_PAT to pick off the first two names (A
          and B) in LAT, and to delete the first of these (A) from LAT.
          When LAT is used up, the :F(RETURN) exit is taken.

            Statement 102 is quite exotic: It constructs, compiles, and
          executes a SNOBOL4 statement.  If P = 'OPATH', A = 'O3', and B =
          'O4', then the constructed statement would be

                       OPATH(O3) = O4 ;

            The CODE function compiles the constructed statement, and the
          direct goto --  :< ... > --  causes the code to be executed
          immediately.  Since the created code has no label and is not the
          value of any variable, it goes out with the next garbage
          collection.

            (Editors note: A simpler rendition of this operation, avoiding
          the CODE function entirely, would be:

                       APPLY(P,$A) = $B

          However, the use of the CODE function is far more exotic.)

            SETSYM is similar to SETPATH.  It consists of just one pattern
          matching statement.  The pattern SETSYM_PAT, however, calls the
          function SETSYM1 and calls itself recursively.

            SETSYM is called (statement 215) to link pairs of POTs by the
          OPP (OPPosite) relation, that is, to make it so that OPP(P1) = O6
          and OPP(O6) = P1, OPP(P2) = O5 and OPP(O5) = P2, etc.

            When SETSYM_PAT is applied to L, it matches the POT names two
          at a time (A and B).  It calls SETSYM1, which does the construct-
          compile-execute trick (with two statements instead of one), e.g.,

                       OPP(Pl) = O6 ; OPP(O6) = P1 ;

            SETSYMl returns the null string and the pattern matching
          process continues with *SETSYM_PAT.  This invokes SETSYM_PAT
          recursively to match the next pair of POT names. The process
          continues until the string L is exhausted.

            The asterisks in *SETSYM1() and *SETSYM_PAT cause deferred
          evaluation, that is, use-time evaluation instead of define-time
          evaluation.  Deferred expressions are evaluated from scratch each
          time they are encountered during the pattern matching process.



       AI Programming in SNOBOL4       - 31 -                    August, 1982








            Other cases in which pattern matching is used like a LISP
          mapping function can be seen in MTSIDEP (134-135), MTSIDE (136-
          137), START (141-147), NEND (148-149), EXPAND1 (174-189), and
          INITBRD (203-225).  The FENCE built-in pattern element is used in
          many of these cases to guard against futile backtracking.  The
          pattern matching process will never backtrack through a FENCE.

            SETPATH and SETSYM may seem to be orthogonal to the plane of
          common sense, though I doubt they will confuse or impress
          hardened LISP programmers.  Readers who are upset by such
          nonstructured, freewheeling stuff should be aware that I have not
          written SETPATH and SETSYM in typical, natural, or even good
          SNOBOL4 style.  SNOBOL4 allows these kinds of shenanigans; it
          does not require them.


          Augmented Transition Network Compiler
          -------------------------------------

            Winston and Horn (1981, pp. 251-277) describe a LISP program
          which compiles a simple source language into LISP.  The source
          language is designed to facilitate the writing of programs which
          realize augmented transition networks (ATNs) for use in natural
          language parsing (cf. Winograd, 1972). Such a program consists of
          rules like those of a production system, augmented by arbitrary
          side effects.

            The program in Appendix E is a compiler for a language like
          Winston and Horn's ATN language.  The compiler translates an ATN
          source program into SNOBOL4.  The built-in CODE function then
          completes the translation into executable machine code.

            The source language accepted by this compiler consists of
          "blocks" of various types.  Each block is headed by one of the
          keywords NETWORK, FUNCTION, LEXICON, or SENTENCES, followed by a
          unique name.  A block is terminated by the word END followed by
          its name.

            A NETWORK block consists of one or more Iabeled "rules."  Rule-
          labels are local to the block in which they occur.  A rule
          consists of one or more IF-statements.  An IF-statement has the
          following form:

               IF <condition> GOTO <label> AFTER <side effects> ENDIF

            The condition consists of one or more function calls, including
          possible calls to other NETWORKs, all of which must succeed in
          order to activate the side effects and the state transition.  The
          side effects consist of one or more function calls, which are
          executed if the condition is satisfied.  The entire "AFTER <side
          effects>" clause may be omitted.

            A FUNCTION block consists of a SNOBOL4 function written in a
          slightly modified format.  Statements must be terminated by



       AI Programming in SNOBOL4       - 32 -                    August, 1982








          semicolons and may be continued over several lines without
          placing continuation characters in column 1.  A function begins
          with

               FUNCTION <name> (<arg. list>) (<locals>)

          and ends with

                       END <name>

            The <arg. list> and/or <locals> may be null, but the two sets
          of parentheses are required.

            A LEXICON block consists of a stream of features and words,
          separated by blanks.  A feature is distinguished from a word by
          its being immediately preceded by a pusher (>) or a popper (<).
          If a substring does not begin with one of these two characters,
          it is taken to be a word.

            The LEXICON block works by operating a feature stack.  A
          feature preceded by a pusher (>) gets pushed onto the stack.
          When a feature is preceded by a popper (<), features are popped
          off the stack until that feature is on top, or until the stack is
          empty.

            When a word is encountered, it is entered into the lexicon and
          is "marked" with whatever features are on the stack.  The stack
          itself is not altered.  Words with multiple entries receive the
          union of all the features from their different entries.

            A SENTENCES block contains one or more sentences to be parsed.
          Each sentence ends with a semicolon.  Sentences are added to a
          pushdown stack from which they are later popped and parsed.

            In addition to the four types of blocks, which can be
          intermixed in any order, the compiler recognizes (by ignoring)
          null lines and comments.  A comment is any record which begins
          with an asterisk (*).  Null lines and comments appear in the
          source listing but have no effect on compilation.

            Finally, compilation is terminated, and execution is initiated,
          by the EXEC statement.  The EXEC keyword is followed by a call to
          the top-level NETWORK.

            Appendix E contains a sample source program, based on Winston
          and Horn's clause parser, along with the output from that
          program.  The remainder of the present section refers to the
          compiler itself.

            Statements 1 to 10 are keyword settings.  Note that CODE_PRINT
          and SCREEN_ECHO can be used to control two compiler options.  The
          source input is assumed to be in the temporary file -ATNSOURCE
          (12), and the compilation listing will go into the file -SLIST
          (14).  The STACK datatype (15) is defined as in the Kalah program



       AI Programming in SNOBOL4       - 33 -                    August, 1982








          (Appendix D).  SENTENCES will hold the stack of sentences to be
          parsed.  LEX_STACK (21) is the feature stack used by LEXICON
          blocks.  LEXICAL_FEATURES (22) is a hash table which holds each
          word's lexical features.

            Statements 23-48 define various simple patterns which are used
          by the compiler.

            The PRT function (49-52) uses a tricky pattern matching device
          (51): "$ SLIST" causes the string X, which is always matched by
          REM, to be written immediately and unconditionally to the source-
          listing file (-SLIST) associated with SLIST.  The ". OUTPUT"
          assignment, however, is conditional upon the success of the
          entire match.  The binary operator (.) is the conditional
          assignment operator. The entire match includes the evaluation of
          the deferred expression EQ(SCREEN_ECH0,1).  Thus, the string X
          goes to the user's terminal only if SCREEN ECHO = 1.

            If CODE_PRINT = 1, then DISPLAY (57-72) will be used to PRT the
          SNOBOL4 code which the compiler generates for each block.  The
          code is printed following the block in the compilation listing.
          DISPLAY does some formatting of the code -- enough to make it
          more readable than one long string would be.

            PUT (80-84) and GET (85-89) are used to maintain registers for
          each node of the parse tree.  PROP is a global hash table which
          is reinitialized (statement 250) for each sentence.  PROP is
          indexed by node names, and PROP<NODE_NAME> itself is a hash table
          indexed by register names like 'SUBJECT', 'VERB', 'PARENT', and
          so on.  In SNOBOL4, associative lists can be implemented using
          hash tables.

            Statements 90-95 define string constants which are used to
          generate the code for a NETWORK.  The name of the particular
          NETWORK eventually replaces each occurrence of REPLACE_LIT.

            There are two sets of patterns used by the compiler.  The first
          set (96-102) is used to sort out blocks from comments, to catch
          gross syntactic errors, and to determine whether or not the
          current block is complete.

            The second set (105-151) performs the syntactic analysis and
          code-generation for each complete block.  This set consists of
          five patterns.  EXEC_PAT (105) recognizes the EXEC statement.
          SENTENCES_PAT (111), LEXICON_PAT (121), FUNCTION_PAT (130), and
          NETWORK_PAT (150) each recognize, parse, and generate code for
          the associated type of block.

            Each major block pattern is built up from component patterns.
          If these definitions are read in reverse order, each looks very
          much like a small phrase-structure grammar. In fact, the pattern
          definitions can be written directly from the phrase-structure
          grammars for each of the block types.




       AI Programming in SNOBOL4       - 34 -                    August, 1982








            These patterns, however, do more than simply match blocks.
          First, immediate value assignment ($) is used to save substrings
          needed during code-generation.  Second, the code-generation
          process is integrated with the syntactic analysis by means of the
          functions S and S_.  The method of code-generation is attributed
          to M. J. Rochkind, and is described in Gimpel (1976, Chapter 18).

            The function S evaluates to a pattern element.  The pattern
          element is constructed so that it always succeeds in matching the
          null string.  Hence, it is invisible as far as the syntactic
          analysis is concerned.  In addition, however, this pattern
          element will trigger a call to the function S_.  S_ has many
          small code-generating segments.  Which segment is selected
          depends upon the string argument passed to S ('LEX', 'ENW', 'F',
          etc.)  when the pattern element is generated.

            The code-generating call to S_ is triggered at precisely the
          point where S(...) is embedded in the pattern definition.
          Actually, Rochkind's code-generation method is more general: Code
          generation can be deferred and made conditional upon the success
          of the entire pattern matching operation.  Thus, it could be used
          effectively even with context sensitive grammars.

            Note that, once again, FENCE is used extensively.  It speeds up
          compilation by preventing futile backtracking.

            COMPILE (152-181) reads and compiles blocks until an EXEC
          statement or a fatal error is detected.  MAIN (236-258)
          constitutes the semantics of the EXEC statement.  It applies the
          indicated FIRST_PROCedure to each sentence on the SENTENCES
          stack.  It calls DUMP_PROP to dump the registers for each node
          after a successful parse.  (There is room for improvement in the
          ordering of nodes and registers).

            The main program for the compiler consists of statements 281-
          284.


                             LIST PROCESSING IN SNOBOL4

            Gimpel (1976, p. 80) writes:  "...SNOBOL3 had only one
          datatype, the string.  Even the arithmetic facilities of SNOBOL3
          were implemented as operations on strings of digits rather than
          on machine integers.  Because of this historical bias, and
          because the language is extraordinarily rich in string handling,
          SNOBOL4 is still regarded by some as exclusively a string
          language.  Yet, all the basic facilities which one expects in a
          list processing language have been incorporated into SNOBOL4;
          these include the automatic allocation and freeing of storage,
          recursive functions, the pointer, and the data structure.
          Moreover, the notation is, for the most part, conventional,
          convenient, and flexible.  Were SNOBOL4 suddenly stripped of all
          its pattern matching capabilities, it would still be a powerful
          and convenient list-processing language."



       AI Programming in SNOBOL4       - 35 -                    August, 1982








            There are scattered references to list processing in SNOBOL4
          which suggest, but do not spell out, the language's AI potential.
          For example, Gimpel (1976) devotes one chapter (of 18) to "basic
          list processing," but the topics covered in that chapter have no
          clear connection to AI programming.

            Griswold (1975) provides some examples of list processing in
          SNOBOL4, but he, like Gimpel, seems more interested in string-
          than list-processing.  His most extensive chapters cover
          cryptography, text editing, and software development.

            Shapiro (1979) does present an example (pp. 79-84) of AI
          programming in SNOBOL4, but he focuses on the built-in pattern
          matching functions rather than the list processing potential of
          SNOBOL4.  This gives the misleading impression that SNOBOL4 has a
          few unusual functions which are applicable to one arcane type of
          AI problem.  The fact that the rest of Shapiro's examples are
          programmed in LISP creates the illusion that LISP is
          intrinsically more suitable than SNOBOL4 for the "typical" AI
          problem.

            Why hasn't the list processing potential of SNOBOL4 been
          developed in the direction of artificial intelligence
          applications?  The reasons seem to be historical: The very first
          applications of SNOBOL (1963-1964) were in symbolic manipulation
          of algebraic expressions, conversion of network descriptions to
          FORTRAN programs, generation of IPL-V programs to generate
          assembly code, implementation of a FORTRAN compiler and other
          experimental compilers, text formatting, graph analysis, syntax
          analysis, simulation of automata, and "application to several
          engineering problems of interest to the Bell System" (Griswold,
          1981).

            The list processing capabilities of SNOBOL emerged only in the
          transition from SNOBOL3 to SNOBOL4, particularly with the
          introduction of the DATA function.  This occurred about 1966
          (Griswold, 1981).  Since AI people considered LISP to be an
          adequate language for their purposes, they had little cause to
          investigate SNOBOL's suitability for AI programming.  SNOBOL4
          experts, on the other hand, seemed uninterested in AI, being more
          concerned with text processing, compiler construction, and other
          kinds of traditional software development.

            The remainder of this paper describes a set of list processing
          functions written in SNOBOL4.  I have named this package
          SNOLISPIST to emphasize its SNOBOL-LISP parentage, as well as to
          reflect the solipsistic feeling I get whenever I talk about AI
          programming in SNOBOL4.

            I undertook the SNOLISPIST project when I still believed in
          some kind of intrinsic connection between list processing and AI
          programming.  I no longer believe in such a connection, so I no
          longer think that SNOLISPIST is central to AI programming in
          SNOBOL4.  SNOBOL4 requires no such supplementary subroutines in



       AI Programming in SNOBOL4       - 36 -                    August, 1982








          order to hold its own as an AI language.  Nevertheless, I include
          a description of SNOLISPIST here for several reasons.

            First of all, I have invested a considerable amount of time,
          energy, and computer money in this project.  I also believe (off
          and on) that these list processing functions could help improve
          communication between LISP and SNOBOL4 programmers, and could
          encourage others to undertake comparative programming projects.
          Since the SNOLISPIST functions are extremely easy to use (just
          plug them in and turn them on), and since unused functions do not
          waste space (they aren't in core, thanks to DEXTERN), they may
          have uses even outside AI.


          Overview of SNOLISPIST
          ----------------------

            Appendix F gives an alphabetical listing of all the SNOLISPIST
          functions, along with detailed descriptions, examples, and
          references.  The present section is a general description of the
          various kinds of functions available.

            The SNOLISPIST functions are patterned after typical LISP
          functions.  Their names are the same as the corresponding LISP
          functions, their arguments are the same, their effects (side
          effects and returned values) are largely the same, and they
          "really work" pretty much the same way as their LISP
          counterparts.


          Conversion Between Strings and Lists
          ------------------------------------

            The longest subroutines in SNOLISPIST are concerned with
          string-to-list and list-to-string data conversion.  The string-
          to-list conversion routine is called READ.  It can be invoked by
          means of the # unary operator.  READ (#) interprets a string as a
          list expression and returns the appropriate list structure.  It
          has separate routines for recognizing and interpreting an atom, a
          dotted pair, a list of one element, a list of two or more
          elements, T, or NIL. It correctly interprets literal atoms
          enclosed in single quotes or double quotes.  It also does some
          syntax checking and provides a fatal-error message if the string
          syntax is illegal.  The \ unary operator forces evaluation of its
          argument.  (This operator is effective only in an argument to
          READ.)

            LIST-TO-STRING CONVERSION.  The list-to-string conversion
          routine, which is used mainly in output sequences, is called
          UNREAD.  It can be invoked by the ! unary operator.  It performs
          the inverse of the READ transformation.  It has separate routines
          for converting NIL, T, a dotted pair, a list of one element, a
          list of two or more elements, or an atom.  Literal atoms that




       AI Programming in SNOBOL4       - 37 -                    August, 1982








          contain internal blanks are enclosed in quotes (") unless they
          are already enclosed in quotes (' or ").

            T AND NIL.  T and NIL are used in SNOLISPIST as they are used
          in LISP.  They are defined, however, as dotted pairs of strings:

            T = 'T' ~ 'T', and

            NIL = '' ~ '', where '' is the null string.

            CLASSES OF FUNCTIONS.  Besides the SNOBOL4 built-in functions,
          the following classes of functions are included in SNOLISPIST:

            The I/O and tracing functions include PRT.VIA.OUTPUT (invoked
          by the | unary operator), PRINT, IN, LTRACE, and TDUMP.  The
          default I/O associations for normal I/O and trace messages are to
          the user's terminal.

            Most "predicates" come in pairs.  NULL/NULLP, NOT/NOTP,
          ATOM/ATOMP, NUMBER/NUMBERP, EQU/EQP, EQUAL/EQUALP, NEG/NEGP,
          ZERO/ZEROP, LESS/LESSP, and GREATER/GREATERP have one form (the
          one whose name ends in 'P') which returns T or NIL like a LISP
          predicate.  The other form succeeds or fails like a SNOBOL4
          predicate.  The mapping predicate functions SOME and EVERY return
          T or NIL.  The special functions FAIL.IF.NIL (unary operator /)
          and FAIL.IF.NIL.ELSE.SUCCEED (unary operator %) help convert
          LISP-type predicates to SNOBOL4- type predicates.

            The function definition functions include DEXP and DEXTERN.
          These are due to Gimpel (1976).  DEXP is used to define short
          functions.  DEXTERN is used to define external functions.
          External functions are loaded from SNOLISP/LIB and compiled
          automatically the first time they are called.

            In SNOLISPIST, lists are built from objects having the defined
          datatype 'CONS' with fields 'CAR' and 'CDR'.  CAR and CDR have
          the same meanings as they do in LISP.  CAAR, CADR, etc., up to
          CDDDDR, are predefined, as they are in many LISPs.

            The following arithmetic functions can be used in SNOLISPIST:
          ABS, ADD1, SUB1, SIGN, FLOAT, DFLOAT, FIX, MINUS, ROUND, ADD,
          SUB, MULT, DIV, MAX, MIN, REMAINDER, PLUS, DIFFERENCE, TIMES, and
          QUOTIENT.  The last four of these take list arguments.

            SPITBOL supports the datatypes 'INTEGER', 'REAL', 'DREAL', and
          'NUMERIC'.  In some contexts, 'NUMERIC' can be used to mean
          'INTEGER' or 'REAL' or 'DREAL'.  The numeric functions handle all
          data conversion automatically.  In addition to the binary
          functions ADD, SUB, MULT, and DIV, SNOBOL4 also supports the
          infix operators (+ - * /), with ! or ** being used for integer
          exponentiation.  Unary + and - are also standard.

            The following extended numeric functions have been adapted from
          Gimpel (1976, pp. 327-340): FLOOR, CEIL, SQRT, SIN, COS, TAN,



       AI Programming in SNOBOL4       - 38 -                    August, 1982








          ASIN, ACOS, ATAN, LOG, CLOG, EXP, and RAISE. CLOG(X) returns
          log(X) (base 10).  LOG(X,B) returns log(X) (base B).  LOG(X)
          returns log(X) (base e).  EXP(X) returns e**X.  RAISE(X,Y)
          returns X**Y. (Note that the SNOBOL4 ! and ** operators do not
          permit real exponents, but RAISE does.)

            (Editor's note: SNOBOL4+ provides exponentiation of real
          numbers.)

            The following constants are also available in double precision:
          P...I. (pi), NAT...BASE. (e), and LN...10. [log(10)].  The
          functions RAD and DEG convert degrees to radians and radians to
          degrees, respectively.

            The following list-building functions have been defined: CONS,
          LIST, APPEND, EXCLUDE, INSERT, INTERSECT, UNION, LCOPY, NCONC,
          LREVERSE, RPLACA, RPLACD, RPLACN, SNOC, SUBST, and EXPLODE.
          These work like their LISP counterparts, except that LIST is
          strictly binary.  Long lists can be defined either by means of
          the ~ binary operator or the READ (#) function.  LCOPY and
          LREVERSE are renamed to avoid conflicts with the built-in SNOBOL4
          functions REVERSE and COPY.

            The list searching and decomposition functions include LAST,
          NTH, PRELIST, RAC, RDC, REMOVE, SUFLIST, UNCONS (POP), ASSOC,
          ASSOCL, FIND, MEMBER, and MEMQ.  The MEMBER function returns NIL
          or a non-NIL list; MEMQ succeeds or fails.

            Property-lists are implemented in SNOLISPIST in a way that
          simulates their implementation in LISP.  The following property
          list functions are defined: GET, PUT, GETL, PUTL, GETPROP,
          PUTPROP, ADDPROP, DEFPROP, and REMPROP.  None of these are
          synonyms for each other, though PUT and DEFPROP are near-
          synonyms.  In each of these functions, the name of the identifier
          whose property list is referenced must be passed to the function
          (using quotes or the name [.] operator).

            SNOLISPIST has a full complement of mapping functions,
          including MAP, MAPC, MAPCAR, MAPCARV, MAPLIST, MAPCAN, MAPCON,
          EVERY, EVLIS, SOME, and SUBSET.  The function MAPCARV
          simultaneously performs MAPCAR and LREVERSE.

            Finally, the following miscellaneous functions have been
          defined: GENSYM (synonym: NEWSYM), which creates and returns a
          unique name; LENGTH, which returns the number of top-level
          elements in a list or the number of characters in a string; SET
          and SETL, which work somewhat like the binary and list forms of
          the LISP SET/SETQ commands; EVALCODE, which evaluates an
          expression and returns its value; READLIST, a generalized version
          of the LISP function of the same name; CONCAT, which takes a list
          of strings and concatenates them; and TDUMP, which prints an
          informative message after certain fatal errors.





       AI Programming in SNOBOL4       - 39 -                    August, 1982








            The function CAL converts a one-dimensional array to a list;
          CLA inverts CAL; and SORT sorts a one-dimensional array.

            UNARY AND BINARY OPERATORS.  The following unary operators are
          given special definitions in SNOLISPIST:

                       | # \ / %

            The | operator is used before a literal string, a string-valued
          variable, or a string-valued expression.  It causes one line (one
          string) to be written to the output file associated with OUTPUT.
          (default: the user's terminal).  The function invoked by | is
          called PRT.VIA.OUTPUT.

            The # and ! operators are inverses of each other.  They perform
          string-to-list and list-to-string conversion, respectively.  If S
          is a string which is a legal list expression, then #S is the
          corresponding list; if L is a list, then !L is the corresponding
          string expression; and #!L is similar in effect to LCOPY(L).  The
          functions invoked by these operators are READ (#) and UNREAD (!).

            The \ operator is effective only within an argument to READ.
          This operator causes its argument to be evaluated before it is
          incorporated into the list structure which READ is building.
          Thus \\ATM returns the value of the value of ATM.  In the absence
          of \, READ treats all atoms as quoted, i.e., unevaluated.

            The operators / and % are used in predicate expressions to
          interface between LISP-type predicates, which return T or NIL,
          and SNOBOL4-type predicates, which succeed or fail.  The /
          operator changes NIL to fail, but it passes along any non-NIL
          argument.  The % operator changes NIL to fail and anything else
          to succeed, returning the null string.  For example, /GET could
          be used to retrieve the value associated with a property
          indicator, failing if the property was not defined.  %GET could
          be used to test whether or not a property was defined, but not to
          retrieve its value.

            Two binary operators are given special definitions in
          SNOLISPIST:

                       ~  %

            The ~ operator is the elementary list-building operator in
          SNOLISPIST.  It invokes the LIST function, which works like the
          CONS function in LISP.  The following examples show some list
          construction statements in LISP and their translations into
          SNOLISPIST:

               (SETQ X (LIST A B C))            LISP
               X = A ~ B ~ C ~ NIL              SNOLISPIST

               (SETQ Y '(A B C))                LISP
               Y = 'A' ~ 'B' ~ 'C' ~ NIL        SNOLISPIST



       AI Programming in SNOBOL4       - 40 -                    August, 1982








               (SET W (CONS A B))               LISP
               $W = A ~ B                       SNOLISPIST

            The % binary operator invokes the function PRINT.IN.FIELD.
          This function has no counterpart in LISP.  It is intended to help
          in formatting output.  It allows strings to be left-justified,
          right-justified, or centered in fixed-width fields.


          Programming in SNOBOL4 with SNOLISPIST
          --------------------------------------

            CORE FUNCTIONS AND EXTERNAL FUNCTIONS.  There are two files of
          SNOLISPIST functions.  One file -- SNOLISP/CORE -- contains the
          core functions, which include READ, UNREAD, DEXP, DEXTERN, CAR,
          CDR, LIST, and a few others. All the other functions are stored
          in SNOLISP/LIB.

            During program development, the programmer can rely on
          automatic retrieval of any functions which are called.   When the
          final version of a program is to be compiled, considerable time
          and space can be saved by selecting only the functions that are
          actually used (from SNOLISP/CORE as well as SNOLISP/LIB).  At the
          present time, this can be done only by copying SNOLISP/CORE and
          SNOLISP/LIB and then deleting the unneeded functions.  Though
          this is rather tedious, and should probably be automated somehow,
          it does save up to 25K in a program like SIR (Appendix H).  And
          in SNOBOL4, as in LISP, anything that saves space saves time, by
          reducing the need for garbage-collection.

            If a function from SNOLISP/LIB is included in the final version
          of a program, its DEXTERN statement from SNOLISP/ CORE should be
          deleted, and its DEFINE statement from SNOLISP/LIB should be
          included.

            CONVENTIONS.  The programming conventions recommended by Gimpel
          (1976) have been incorporated into SNOLISPIST.  The name of a
          defined function matches the label on the first statement in the
          function body.  That same name, followed by '.END', is the label
          on the last statement of the function body, which is usually a
          null statement.  Statement labels internal to the function body
          consist of the function name followed by '1', '.2', '.A', or the
          like.

            Names of identifiers used in contexts where name conflicts
          might occur have been chosen so as to reduce the chances of such
          conflicts.  These names contain three embedded periods and a
          terminal period, e.g., READ...SPB., LTRACE1...A., P...I..  This
          makes some parts of the SNOLISPIST source code all but
          unreadable, but it helps prevent name conflicts.  Nevertheless,
          there are still potential problems.  The programmer must be
          careful, for example, not to redefine T or NIL.





       AI Programming in SNOBOL4       - 41 -                    August, 1982








          Generic Bugs
          ------------

            In using SNOLISPIST, the programmer should be aware of the
          following potential problems.  The possible mistakes discussed
          below are easy to make and easy to fix.  They should be checked
          for first when a program behaves very strangely.

            As mentioned in the preceding section, name conflicts can arise
          in many subtle ways.  For example, names which conflict with
          dummy variable names and local variable names can be smuggled
          into a function by means of the name [.] operator.  One way this
          can happen is for a list of names to be passed as an argument to
          a mapping function, along with a function argument that
          implicitly or explicitly evaluates those names.

            Another problem may occur with the predicates NULL, NULLP, NOT,
          NOTP, FAIL.IF.NIL [unary /], and FAIL.IF.NIL.ELSE.SUCCEED [unary
          %].  All these predicates require a list argument (datatype
          CONS).  Any other datatype will cause a fatal error.  The correct
          way to test whether X is NIL, where X can have any datatype, is
          to use DIFFER(NIL,X) or IDENT(NIL,X).

            Sometimes the mixture of string and list datatypes in the same
          statement causes problems, especially if the programmer overlooks
          a concatenation operation.  For example,

                       LINE = 'VALUES = ' SETL(#'(X 5 Y 6 Z 7)')

          will not work, because SETL returns a list, which cannot be
          concatenated with the string 'VALUES = '.  This can be corrected
          by means of the UNREAD [unary !] operator: Use !SETL(...) instead
          of SETL(...).

            If several function calls are combined in the same statement,
          it is safest to enclose them in ?(...), as illustrated in the
          following two examples:

               ?( |'Line 1'  |''  |'Line 2'  |'' )
               ?( ~ATOM(P)  NULL(P)  %RPLACD(L,PNEW) )

            The SNOLISPIST routines do a fair amount of argument checking,
          and TDUMP provides extensive information about the local
          environment of a run-time error.  The programmer should also keep
          in mind the LTRACE function, the &DUMP, &FTRACE, and &TRACE
          keywords, and the other SNOBOL4 debugging facilities described in
          an earlier section of this paper.


                                      EXAMPLES

            The use of the SNOLISPIST routines is illustrated by two
          programs.  The first of these, TEST, simply exercises all the
          functions, sometimes in fairly improbable ways.  The second, SIR,



       AI Programming in SNOBOL4       - 42 -                    August, 1982








          is a more or less literal translation into SNOBOL4 of Shapiro's
          (1979) version of Bertram Raphael's Semantic Information
          Retrieval program.


          TEST
          ----

            The program in Appendix G provides some rudimentary tests and
          demonstrations of the SNOLISPIST function.  Here are a few
          general points about the test program.

            The program is largely self-documenting.  It is intended to
          interact with a user at a terminal.  The PAUSE() statements (8,
          13, etc.)  cause PAWS (statement 1) to be evaluated.  This
          reports the amount of free storage available and prompts the user
          to "Press ENTER to continue."

            Mapping functions are used extensively.  A typical example can
          be seen in statement 7.  DEXP(...) not only defines a function,
          but also returns the name of that function, which becomes the
          first argument to MAPC.  The second argument to MAPC is simply a
          list of expressions.  As MAPC is evaluated, each of these
          expressions is printed and then evaluated.  This same technique
          is used in statement 12, and similar mapping functions are used
          throughout the test program.

            In statement 23, the second argument to MAPC is a list of
          function names; each named function is applied in turn to the
          ARGUMENT.LIST defined in statement 19.

            Mapping is also used to test the extended numerical functions
          (statements 32, 38, 45, 54, 57, 60, 74, 78, and 82).  In
          statement 91, the second argument to MAPC is not a list of
          function names, but a list of middle segments of function names.
          These middle segments are successively assigned to S (statement
          91, second line) to make all the CAR/CDR compounds from CAAR to
          CDDDDR.

            Statements 96-105 test the formatted output function
          PRINT.IN.FIELD (binary $).  Statements 111-153 test some of the
          more complicated list processing functions (LCOPY, SUBST, REMOVE,
          and FIND).

            Statements 165-180 test the SETL and SET functions, using two
          defined functions, PLACE and INTERLEAVE.  In statement 177, AA is
          set to the list of lower-case letters; in 178, VV is set to the
          list of EBCDIC codes for these letters; in 179, the argument to
          SETL is constructed by INTERLEAVE, so that the value of each
          lower-case letter will be set to the EBCDIC code for that letter.
          The lower-case letters and their EBCDIC codes are printed in
          statement 180.





       AI Programming in SNOBOL4       - 43 -                    August, 1982








            Statements 182-196 test the set-manipulation functions UNION,
          EXCLUDE, and INTERSECT.  The MAPC statement (196) says, "For each
          name on the list, print a blank Iine, print the name, evaluate
          it, and print the value."

            All the property list functions are tested in one call to MAPC
          (statement 400), the first argument of which defines a function
          that prints a blank line, prints an expression, evaluates the
          expression, converts the value from list to string, and prints it
          preceded by five blanks.

            Statements 433-446 test the functions CLA (convert list to
          array), CAL (convert array to list), and SORT (sort a segment of
          an array).  Statement 446 makes anagrams by exploding a word into
          a list of single characters, converting the list to an array,
          sorting the array, converting the array back to a list,
          converting the list back to a string, and printing the string.


          SIR
          ---

            Shapiro (1979, pp. 123-140) presents a LISP program for storing
          and retrieving propositional information in a relational network
          (semantic network).  Shapiro's program is based on Bertram
          Raphael's Semantic Information Retrieval (SIR) program (Raphael,
          1968).

            The program in Appendix H is a translation of Shapiro's program
          from LISP into SNOLISPIST.  An attempt was made to follow the
          LISP code as closely as possible.  The reader can consult Shapiro
          (1979) for the original LISP program and documentation.  The
          following discussion will focus on the differences between the
          SNOLISPIST program and the LISP program.

            In statement 8, pattern-matching is used to determine whether
          the initial sentence fragment ends with a terminal punctuation
          mark [! or ?].  The two-statement loop (7-8) keeps S in string
          form until it is complete.  Then it is converted into a list
          (statement 9).

            In PROCESS.1 (statements 12-20), each rule on the list RULES is
          applied to SENTENCE until one matches, or until the list of rules
          is exhausted.  In statements 14-16, RESP is something like "I
          UNDERSTAND.", "INSUFFICIENT INFORMATION", etc.  (See statements
          103-107.)  If RESP is NIL, then the rule (CA) could not be
          applied to SENTENCE.

            Statement 21 defines the datatype RULE.  A RULE consists of a
          PATTERN which may match a phrase, causing some constituents of
          the phrase to be bound to certain VARIABLES. If the values of
          these VARIABLES then pass certain TESTS, the associated semantic
          ACTION will be executed.  If the input sentence was an assertion
          (ending with !), the semantic action will be to add information



       AI Programming in SNOBOL4       - 44 -                    August, 1982








          to the database.  If the input was a question (ending with ?)
          then the semantic action will be to retrieve previously stored
          information.  The operation of the program thus depends, in part,
          on the list of RULEs (statements 185-193).

            APPLY.RULE (22-25) says, "If the pattern PATTERN(RULE) matches
          the input INP, then apply the associated tests, TESTS(RULE), to
          the values of the variables, EVLIS(...), to determine whether
          ACTION(RULE) should be executed."  (The pattern-matching here
          could be handled more efficiently and more transparently by using
          the standard SNOBOL4 pattern- matching facilities, rather than
          using list processing.)

            APPLY.RULE.1 (51-55) builds and evaluates an expression, thus
          executing the semantic action ACT.  CAR(ACT) is the name of a
          function (see statements 108-184), and CONCAT(RMAPCAR(...))
          returns the argument list for the function call.  RMAPCAR (56-61)
          is a kind of reverse MAPCAR, in that it applies each function
          named on the list LF to the list S, returning a list of the
          results.

            The utility functions ADDXRY through COMPLEMENT (statements 62-
          88) are used by the semantic routines.  The semantic routines
          (108-184) are activated by the ACTION fields of the various RULEs
          (statement 193) to modify or interrogate the relational network.

            The program in Appendix H has been tested with Shapiro's test
          dialogue (Shapiro, 1979, 138-140).


                                      FOOTNOTE

            This work was made possible by leave support from Gustavus
          Adolphus College.  It was also supported in part by a grant in
          cognitive science from the Alfred P. Sloan Foundation to the
          University of Michigan.  Computer funds were made available
          through this Sloan grant and through the University of Michigan
          Computing Center.

            The following people have provided help and/or inspiration:

            Robert R. Knight helped me get started programming in SNOBOL4
          at Princeton University around 1972.  He once said, "It's a
          wonder they've made any progress in AI, since they insist on
          using LISP."

            George Georgacarakos, a philosopher, once told me, "It's easy
          to program in LISP because people naturally think in LISP."

            Paul D. Scott, Sandy Nado, and Les Johnson took the time to
          read an earlier draft of this paper.  Their comments have helped
          me to clarify my own thinking about AI programming, and their
          expertise has enabled me to correct some of my errors.  They are




       AI Programming in SNOBOL4       - 45 -                    August, 1982








          not to blame for any new errors I may have introduced without
          their knowledge or consent.

            Ralph E. Griswold called my attention to the work of Leonard
          Uhr and provided information about the Icon programming language.
          Fred Swartz and Paul Pickelmann also provided information about
          Icon.

            Gary M. Olson provided advice and encouragement.

            Sylvia A. S. Shafto provided criticism, perspective, and food.


                                     REFERENCES

            Berztiss, A. T.  "Data structures: Theory and practice" (second
               edition).  New York: Academic Press, 1975.

            Bundy, A., Burstall, R. M., Weir, S., & Young, R. M.
               "Artificial intelligence: An introductory course."  New
               York: North-Holland, 1978.

            Charniak, E., Riesbeck, C. K., & McDermott, D. V. "Artificial
               intelligence programming."  Hillsdale, New Jersey: Lawrence
               Erlbaum Associates, 1980.

            Darlington, J.  A partial mechanization of second-order logic.
               In B. Meltzer & D. Michie (Eds.), "Machine Intelligence 6."
               New York: Wiley, 1971.

            Darlington, J.  Deductive plan formation in higher-order logic.
               In B. Meltzer & D. Michie (Eds.), "Machine Intelligence 7."
               New York: Wiley, 1972.

            Davenport, J. H., & Jenks, R. D.  MODLISP. "SIGSAM Bulletin,"
               1981, 15, 11-20.

            Day,  A. C.  "FORTRAN techniques".  Cambridge, England:
               Cambridge University Press, 1972.

            Denning, P. J., Dennis, J. B., & Qualitz, J. E.  "Machines,
               languages, and computation."  Englewood Cliffs, NJ:
               Prentice-Hall, 1978.

            Dijkstra, E. w.  "A discipline of programming."  Englewood
               Cliffs, NJ: Prentice-Hall, 1976.

            Friedman, D. P.  "The little LISPer."  Palo Alto: Science
               Research Associates, 1974.

            Gimpel J. F.  "Algorithms in SNOBOL4."  New York: John Wiley &
               Sons, 1976. (Editors note: republished by Catspaw, Inc.,
               1986)




       AI Programming in SNOBOL4       - 46 -                    August, 1982








            Gries, D.  "The science of programming."  New York: Springer-
               Verlag, 1981.

            Griffin, R., & Redish, K. A.  Remark on Algorithm 347 [M1]: An
               efficient algorithm for sorting with minimal storage.
               "Collected algorithms from CACM," 1969, Vol. 2.

            Griswold, R. E.  "String and list processing in SNOBOL4:
               Techniques and applications."  Englewood Cliffs, New Jersey:
               Prentice-Hall, 1975.

            Griswold, R. E.  "An alternative to the concept of "pattern" in
               string processing."  Technical Report TR 78-4, Department of
               Computer Science, University of Arizona, Tucson, AZ (April
               10, 1978)a.

            Griswold, R. E.  "User's manual for the Icon programming
               language."  Technical Report TR 78-14, Department of
               Computer Science, University of Arizona, Tucson, AZ (Sept.
               29, 1978)b.

            Griswold, R. E.  A history of the SNOBOL programming languages.
               In Wexelblat, R. L. (Ed.), "History of programming
               languages."  New York: Academic Press, 1981.

            Griswold, R. E., & Griswold, M. T.  "A SNOBOL4 primer."
               Englewood Cliffs, New Jersey: Prentice-Hall, 1973.

            Griswold, R. E., & Hanson, D. R.  Language facilities for
               automatic backtracking.  "SIGPLAN Notices/SIGART Newsletter
               Special Issue.: Proceedings of the Symposium on AI and
               Programming," 1977, 12/No. 64, 94-99. (a)

            Griswold, R. E., & Hanson, D. R.  An overview of SL5. "SIGPLAN
               Notices," 1977, 12, 40-50. (b)

            Griswold, R. E., & Hanson, D. R.  "Reference manual for the
               Icon programming language."  Technical Report TR 79-la,
               Department of Computer Science, University of Arizona,
               Tucson, AZ (January, 1980).

            Griswold, R. E., Hanson, D. R., & Korb, J. T.  "The Icon
               programming language: An overview."  Tucson, AZ: Department
               of Computer Science, University of Arizona, 1979.

            Griswold, R. E., Hanson, D. R., & Korb, J. T.  Generators in
               Icon.  "ACM Transactions on Programming Languages and
               Systems," 1981, 3, 144-161.

            Griswold, R. E., Hanson, D. R., & Wampler, S. B. "Transporting
               the Icon programming language( Version 2.0.  Technical
               Report TR 79-2b, Department of Computer Science, University
               of Arizona, Tucson, AZ (February, 1980).




       AI Programming in SNOBOL4       - 47 -                    August, 1982








            Griswold, R. E., Poage, J. F., & Polonsky, I. P.  "The SNOBOL4
               programming Language" (second edition). Englewood Cliffs,
               New Jersey: Prentice-Hall, 1971.

            Hanson, D. R.  "Transporting Ratfor."  Technical Report TR 79-
               4a, Department of Computer Science, University of Arizona,
               Tucson, AZ (May, 1979).

            Hewitt, C.  PLANNER: A language for proving theorems in robots.
               "Proceedings of the International Joint Conference on
               Artificial Intelligence."  Bedford, Mass.: MITRE, 1969.

            Hopcroft, J. E., & Ullman, J. D.  "Introduction to automata
               theory, languages, and computation."  Reading, Mass.:
               Addison-Wesley, 1979.

            Lewis, T. G., & Smith, M. Z.  "Applying data structures."
               Boston: Houghton Mifflin, 1976.

            Marti, J., Hearn, A. C., Griss, M. L., Griss, C.  Standard LISP
               report.  "SIGSAM Bulletin," 1980, 14, 23-43.

            McCarthy, J.  History of LISP.  In R. L. Wexelblat (Ed.),
               "History of programming languages."  New York: Academic
               Press, 1981.

            McCarthy, J., Abrahams, P. W., Edwards, D. J., Hart, T. P., &
               Levin, M. I.  "LISP 1.5 programmer's manual" (second
               edition).  Cambridge, Massachusetts: The M.I.T. Press, 1969.

            McDermott, D. V., & Sussman, G. J.  "The Conniver reference
               manual."  Cambridge, Mass.: MIT AI Laboratory Memo 259a,
               1973.

            Maurer, W. D.  "A programmer's introduction to LISP."  New
               York: American Elsevier, 1973.

            Maurer, W. D.  "The programmer's introduction to SNOBOL4."  New
               York: American Elsevier, 1976.

            Newsted, P. R.  "SNOBOL: An introduction to programming."
               Hayden Book Co., 1975.

            Peto, R.  Remark on Algorithm 347 [M1]: An efficient algorithm
               for sorting with minimal storage.  "Collected algorithms
               from CACM," 1970, Vol. 2.

            Raphael, B.  SIR:  Semantic information retrieval.  In Minsky,
               M. (Ed.), "Semantic information processing." Cambridge,
               Mass.:  M.I.T. Press, 1968.

            Schank, R., & Riesbeck, C. (Eds.). "Inside computer
               understanding."  Hillsdale, New Jersey:  Lawrence Erlbaum
               Associates, 1981.



       AI Programming in SNOBOL4       - 48 -                    August, 1982








            Shapiro, S. C.  Techniques of artificial intelligence.  New
               York: Van Nostrand, 1979.

            Siklossy, L. S.  "Let's talk LISP."  Englewood Cliffs, NJ:
               Prentice-Hall, 1976.

            Singleton, R. C.  Algorithm 347: An efficient algorithm for
               sorting with minimal storage.  "Collected Algorithms from
               CACM," 1968, Vol. 2.

            Sommerville, I.  S-SNOBOL: Structured SNOBOL4.  SIGPLAN
               Notices, 1979, 14, 91-99.

            Uhr, L.  "Pattern recognition, learning, and thought: Computer
               programmed models of higher mental processes." Englewood
               Cliffs, NJ: Prentice-Hall, 1973.

            University of Michigan Computing Center.  "MTS Volume 8: LISP
               and SLIP in MTS."  Author, 1976.

            University of Michigan Computing Center.  "MTS Volume 9:
               SNOBOL4 in MTS."  Author, 1975.

            University of Michigan Computing Center.  "MTS Volume 1: The
               Michigan Terminal System."  Author, 1979.

            "University of Michigan Computing Center Newsletter."  Icon
               arrives at the Computing Center.  Nov. 11, 1981, p. 3.

            Winograd, T.  "Understanding natural language."  New York:
               Academic Press, 1972.

            Winston, P. H., & Horn, B. P. K.  "LISP." New York: Addison-
               Wesley, 1981.

            Wirth, N.  "Algorithms + Data Structures = Programs." Englewood
               Cliffs, NJ: Prentice-Hall, 1976.




















       AI Programming in SNOBOL4       - 49 -                    August, 1982








                                     APPENDIX A

            This is a compilation listing of a SNOBOL4 version of C.A.R.
          Hoare's Quicksort algorithm.  This program is based on Wirth's
          (1976, p. 79) and Gimpel's (1976, pp. 280-282) programs.

             *
             * Sort array A according to predicate P.
             *
             * P(A<I>,A<J>) true for all I < J.
             *
             * Possible values of P:
             *     .LE, .GE, .LLE, .LGE
             *
             * DO NOT USE:
             *     .LT, .GT, .LLT, .LGT
             *
             *
          1   DEFINE('HSORT(A,I,N,P)J,K,C')
          2   DEFINE('HSORT.KO(V1,V2)')
          3   DEFINE('HSORT.OK(V1,V2)')
          4   DEFINE('HSORT.SWAP(I1,I2)T')              :(HSORT.END)
             *
          5  HSORT
          6        GT(N - I,  1)    :S(HSORT1)
          7        GE(I, N)         :S(RETURN)
          8        (HSORT.KO(A<I>,A<N>)   HSORT.SWAP(I,N))
          9           :(RETURN)
             *
          10 HSORT1
          11       C = A<(I + N) / 2>
          12       J = I - 1
          13       K = N + 1
             *
          14 HSORT2   J = J + 1
          15       HSORT.OK(C,A<J>)                       :F(HSORT2)
          16 HSORT3   K = K - 1
          17       HSORT.OK(A<K>,C)                       :F(HSORT3)
             *
          18       (LT(J,K)    HSORT.SWAP(J,K))           :S(HSORT2)
             *
          19       HSORT(A, I, K, P)
          20       HSORT(A, K + 1, N, P)                  :(RETURN)
             *
          21 HSORT.SWAP  T = A<I1> ; A<I1> = A<I2> ; A<I2> = T :(RETURN)
             *
          24 HSORT.OK      APPLY(P,V1,V2)           :S(RETURN)F(FRETURN)
             *
          25 HSORT.KO      APPLY(P,V1,V2)           :S(FRETURN)F(RETURN)
             *
          26 HSORT.END
             *
             *
             * Begin main program *****



       AI Programming in SNOBOL4       - 50 -                    August, 1982








             *
          27  OUTPUT(.OUTPUT,,80)
          28  INPUT(.INPUT,,80)
             *
          29       SETEXIT( .CONTINUE )
          30       REWIND( 'SFILE' )
          31       N = 0
          32 COUNT
          33       N = ?INPUT   N + 1      :S(COUNT)
             *
          34       A = ARRAY(N)
          35       REWIND( 'SFILE' )
          36       I = 0
          37 INPUT.LOOP
          38       I = LT(I,N) I + 1       :F(INPUT.LOOP.END)
          39       A<I> = INPUT            :(INPUT.LOOP)
          40 INPUT.LOOP.END
             *
          41    HSORT(A,1,N, .LLE)
             *
          42       I = 0
          43 OUTPUT.LOOP
          44       I = LT(I,N) I + 1       :F(OUTPUT.LOOP.END)
          45       OUTPUT = LPAD(I,5) ".   " A<I>    :(OUTPUT.LOOP)
          46 OUTPUT.LOOP.END
          47 END































       AI Programming in SNOBOL4       - 51 -                    August, 1982








                                     APPENDIX B

            This is a compilation listing of a SNOBOL4 version of Wang's
          Algorithm for proving theorems in the propositional calculus.
          The program prints a proof or refutation for any formula.

            This program was adapted from Griswold, Poage, and Polonsky
          (1971, pp. 183-187).  For a LISP version of Wang's Algorithm, see
          Shapiro (1979, pp. 57-62).

             *
             * Wang's algorlthm
             *
             * Adapted from
             *      Griswold, R. E., Poage, J. F., & Polonsky, I. P.
             *          The SNOBOL4 Programming Language.
             *          Pp. 183-185.
             *
          1   DEFINE('WANG(ANTECEDENT,CONSEQUENT)PHI,PSI')
          2   UNOP = 'NOT'
          3   BINOP  = ('AND' | 'IMP' | 'OR' | 'EQU')
          4   UNOP.FORMULA = ' ' (UNOP . OP) '(' (BAL . PHI) ')'
          5   BINOP.FORMULA = ' ' (BINOP . OP) '(' (BAL . PHI) '.'
             +                    (BAL . PSI) ')'
          6   FORMULA = UNOP.FORMULA | BINOP.FORMULA
          7   ATOM = (NOTANY(' ') (BREAK(' ') | REM)) . A
             +                                               :(WANG.END)
             *
          8  WANG
          9         OUTPUT = ANTECEDENT ' >>> ' CONSEQUENT
          10        ANTECEDENT FORMULA = NULL
             +             :F(WANG1)S( $('WANG.A.' OP) )
          11 WANG.A.NOT
          12        WANG(ANTECEDENT, CONSEQUENT ' ' PHI)
             +          :S(RETURN)F(FRETURN)
          13 WANG.A.AND
          14        WANG(ANTECEDENT ' ' PHI ' ' PSI, CONSEQUENT)
             +          :S(RETURN)F(FRETURN)
          15 WANG.A.OR
          16        WANG(ANTECEDENT ' ' PHI, CONSEQUENT)     :F(FRETURN)
          17        WANG(ANTECEDENT ' ' PSI, CONSEQUENT)
             +          :S(RETURN)F(FRETURN)
          18 WANG.A.IMP
          19        WANG(ANTECEDENT ' ' PSI, CONSEQUENT)     :F(FRETURN)
          20        WANG(ANTECEDENT, CONSEQUENT ' ' PHI)
             +          :S(RETURN)F(FRETURN)
          21 WANG.A.EQU
          22        WANG(ANTECEDENT ' ' PHI ' ' PSI, CONSEQUENT)
             +        :F(FRETURN)
          23        WANG(ANTECEDENT, CONSEQUENT ' ' PHI ' ' PSI)
             +          :S(RETURN)F(FRETURN)
          24 WANG1
          25        CONSEQUENT FORMULA =
             +          :F(WANG2)S( $('WANG.C.' OP) )



       AI Programming in SNOBOL4       - 52 -                    August, 1982








          26 WANG.C.NOT
          27        WANG(ANTECEDENT ' ' PHI, CONSEQUENT)
             +          :S(RETURN)F(FRETURN)
          28 WANG.C.AND
          29        WANG(ANTECEDENT, CONSEQUENT ' ' PHI)       :F(FRETURN)
          30        WANG(ANTECEDENT, CONSEQUENT ' ' PSI)
             +          :S(RETURN)F(FRETURN)
          31 WANG.C.OR
          32        WANG(ANTECEDENT, CONSEQUENT ' ' PHI ' ' PSI)
             +          :S(RETURN)F(FRETURN)
          33 WANG.C.IMP
          34        WANG(ANTECEDENT ' ' PHI, CONSEQUENT ' ' PSI)
             +         :S(RETURN)F(FRETURN)
          35 WANG.C.EQU
          36        WANG(ANTECEDENT ' ' PHI, CONSEQUENT ' ' PSI)
             +        :F(FRETURN)
          37        WANG(ANTECEDENT ' ' PSI, CONSEQUENT ' ' PHI)
             +        :S(RETURN)F(FRETURN)
          38 WANG2
          39        ANTECEDENT ATOM =                          :F(FRETURN)
          40        CONSEQUENT A                        :S(RETURN)F(WANG2)
          41 WANG.END
             *
             *
             *
          42  &ANCHOR = 0
          43  &FULLSCAN = 1
          44  &TRIM  = 1
             *
          45  INPUT(.INPUT,,80)
          46  OUTPUT(.OUTPUT,,80)
             *
          47        SETEXIT( .CONTINUE)
          48 READ
          49        EXPRESSION = INPUT                         :F(END)
          50        OUTPUT =
          51        OUTPUT = 'FORMULA:  ' EXPRESSION
          52        OUTPUT =
          53        OUTPUT = WANG( NULL, ' ' EXPRESSION ) 'VALID'
             +        :S(READ)
          54        OUTPUT = 'INVALID'
             +        :(READ)
          55 END














       AI Programming in SNOBOL4       - 53 -                    August, 1982








                                     APPENDIX C

            This is a compilation listing of a program to analyze English
          word endings.  It is based on the flowchart and discussion given
          in Winograd (1972, pp. 73-76).

             *
             *
             * Analysis of English Endings
             *
             * SNO8OL4 implementation of flowchart on p. 74 of
             *     Winograd, T.  Understanding Natural Language.
             *           New York:  Academic Press, 1972.
             *
          1   DEFINE('WORDEND(WORD)L,VOWEL,DOUBLE,LIQUID,NOEND')
          2   DEFINE('MATCH(L,PAT)')
          3   DEFINE('CUT(N)')
          4   DEFINE('ADDON(X)')
          5   DEFINE('TRY()')
          6              :(WORDEND.END)
             *
          7  WORDEND
          8          WRD = WORD
          9          DOUBLE = (LEN(1) $ L) *L RPOS(0)
          10         LIQUID = ANY("LRSVZ")
          11         NOEND = ANY("CGSVZ")
          12         VOWEL = ANY("AEIOUY")
             *
          13         WRD
             +       ("N'T" | "'S" | "S'" | "S" | "LY" |
             +        "ING" | "ED" | "EN" | "ER" | "EST")
             +        $ WEND RPOS(0) =                        :F(WTRY)
             *
          14         WEND POS(0) ("S" | "'S" | "S'" | "N'T") RPOS(0)
             +                                                :F(WORDEND.1)
             *
          15         MATCH(1,"E")                             :F(WTRY)
          16         MATCH(2,"I") CUT(2) ADDON("Y")           :S(WTRY)
          17         MATCH(2,"TH")                            :S(WTRY)
          18         MATCH(2,ANY("HX")) CUT(1)                :S(WTRY)
          19         MATCH(2,ANY("SZ") ANY("SZ")) CUT(1)      :S(WTRY)
          20         MATCH(2,ANY("SZ"))                       :S(WTRY)
          21         MATCH(2,"V")                             :F(WTRY)
          22         ~TRY() CUT(2) ADDON("FE")            :S(WTRY)F(RETURN)
             *
          23 WORDEND.1
          24         IDENT(WEND,"LY")                         :F(WORDEND.2)
          25         MATCH(1,"I") CUT(1) ADDON("Y")           :S(WTRY)
          26         ~TRY() ADDON("LE")                   :S(WTRY)F(RETURN)
             *
          27 WORDEND.2
          28         MATCH(1,VOWEL)                           :F(WORDEND.3)
          29         MATCH(1,"I") CUT(1) ADDON("Y")           :S(WTRY)
          30         MATCH(1,"Y")                             :S(WTRY)



       AI Programming in SNOBOL4       - 54 -                    August, 1982








          31         ~MATCH(1,"E") ADDON("E")                 :S(WTRY)
          32         MATCH(2,"E")                             :S(WTRY)
          33         ~TRY() ADDON("E")                    :S(WTRY)F(RETURN)
             *
          34 WORDEND.3
          35         MATCH(1,"H")                             :F(WORDEND.4)
          36         MATCH(2,"T")                             :F(WTRY)
          37         ~TRY() ADDON("E")                    :S(WTRY)F(RETURN)
             *
          38 WORDEND.4
          39         WRD DOUBLE                               :F(WORDEND.5)
          40         ~MATCH(1,LIQUID) CUT(1)                  :S(WTRY)
          41         ~TRY() CUT(1)                        :S(WTRY)F(RETURN)
             *
          42 WORDEND.5
          43         MATCH(2,VOWEL)                           :S(WORDEND.6)
          44         MATCH(1,"RL")                            :S(WTRY)
          45         MATCH(1,LIQUID | NOEND) ADDON("E")       :(WTRY)
             *
          46 WORDEND.6
          47         ~MATCH(3,VOWEL) ADDON("E")               :S(WTRY)
          48         MATCH(1,NOEND) ADDON("E")                :(WTRY)
             *
          49 WTRY    TRY()                             :S(RETURN)F(FRETURN)
             *
             *
             *
          50 MATCH
          51         WRD PAT RPOS(L - 1)               :S(RETURN)F(FRETURN)
             *
          52 CUT
          53         WRD RPOS(N) REM =                         :(RETURN)
             *
          54 ADDON
          55         WRD = WRD X                               :(RETURN)
             *
          56 TRY
          57         DIFFER(DICTIONARY<WRD>)           :S(RETURN)F(FRETURN)
             *
          58 WORDEND.END
             *
             *
             * Main program starts here
             *
          59  INPUT(.INPUT,,80)
          60  OUTPUT(.OUTPUT,,80)
          61  DICTIONARY = TABLE(101)
          62  WORDS  =
             +     'BASH,BATHE,LEAN,LEAVE,DENT,DANCE,DOG,KISS,CURVE,'
             +     'CURL,ROT,ROLL,PLAY,PLY,REAL,PALE,KNIFE,PRETTY,'
             +     'NOBLE,PATROL,'
          63 DICT.LOOP
          64        WORDS BREAK(',') . W LEN(1) =         :F(DICT.LOOP.END)
          65        DICTIONARY<W> = 1                          :(DICT.LOOP)



       AI Programming in SNOBOL4       - 55 -                    August, 1982








          66 DICT.LOOP.END
             *
          67         SETEXIT( .CONTINUE)
          68 READ   W = INPUT                                  :F(END)
          69        WORDEND(W)
          70        OUTPUT = WRD                               :(READ)
          71 END


















































       AI Programming in SNOBOL4       - 56 -                    August, 1982








                                     APPENDIX D

            This is a compilation listing of a SNOBOL4 program to play the
          game Kalah.  The game and a LISP program to play it are given in
          Shapiro (1979, pp. 31-55).  A LISP program which closely follows
          Shapiro's is included here in boxed groups of comments in order
          to facilitate comparison of LISP and SNOBOL4 code (EDITOR'S NOTE:
          LISP CODE NOT AVAILABLE AT THIS TIME).

              *
              *
              *       KALAH in SNOBOL4 (Spitbol)
              *
              *
              *     The program follows a LISP program which appeared in
              *      Shapiro, S.C., Techniques of Artificial Intelligence,
              *       New York: Van Nostrand, 1979, pp. 31-55.
              *
              * Try it with 4 stones per pot, and a search depth of only 1.
              *
              * This is one of the many variations of Mancala games.
              * Mancala games are popular in Africa and India.  It is a
              * very old game; boards have been found in Ancient Egyptian
              * ruins.  Some of the names of different versions are:
              * Mankala'h, Pallanguli, Wari, Awari, and Ba-Awa.
              * We do not know the precise name of this version
              *
              * The board consists of two rows of six depressions, called
              * 'pits' or 'pots'.  A larger pit at each end holds captured
              * pieces.
              *
              * The board is as follows: (integers are pot numbers, 'P' is
              * the computer, 'O' is the user.
              *
              *         P6  P5  P4  P3  P2  P1
              *  PKALAH                        OKALAH
              *         O1  O2  O3  O4  O5  O6
              *
              *       The move path is counter-clockwise.
              *        For the computer: P1-P6-PKALAH-O1-O6-P1,
              *        and for the user, O1-O6-OKALAH-P1-P6-O1.
              *
              * Initially, P1-P6 and O1-O6 are filled with the desired
              * number of stones.  A move is made by taking all the stones
              * from a numbered pot on your side, and sowing them one-
              * by-one into succeeding pots along your path.  If your last
              * stone went into the KALAH, you get another turn.
              * If the last stone went into a numbered pot ON YOUR SIDE
              * that was empty, you take that stone, and any stones in your
              * opponents opposite pot, place them in your KALAH.  The game
              * ends when one side has a majorityof the stones in their
              * KALAH.  You lose if it is your turn and all of your pots
              * are empty (you have no play).
              *



       AI Programming in SNOBOL4       - 57 -                    August, 1982








              *
              * Keyword settings
              *
          1           &ANCHOR = 0
          2           &DUMP = 0
          3           &FTRACE = 0
          4           &FULLSCAN = 1
          5           &MAXLNGTH = 32758
          6           &STLIMIT = -1
          7           &TRACE = 0
          8           &TRIM = 1
              *
              * I/O Associations.
              *
          9           INPUT(.INPUT)
          10          OUTPUT(.OUTPUT)
          11          OUTPUT(.SHADOW,1,,'SHADOW')
              *
              * Defined datatypes
              *
          12          DATA( 'POT(OWNER,NUM,KVALUE,OPP,PPATH,OPATH)' )
          13          DATA( 'NODE(PLAYER,MOVEOF,NEXT_PLAYER)' )
          14          DATA( 'STACK(TOP,REST)' )
              *
              * Global constants
              *
          15          null = ''
          16          nil = STACK(null,null)
          17          TOP(nil) = nil
          18          REST(nil) = nil
          19          t = COPY(nil)
          20          TOP(t) = t
          21          REST(t) = t
          22          nilpot = POT(null,0,nil,null,null,null)
          23          OPP(nilpot) = nilpot
          24          PPATH(nilpot) = nilpot
          25          OPATH(nilpot) = nilpot
              *
              * Utility patterns
              *
          26          LEFT_END = POS(0)
          27          RIGHT_END = RPOS(0)
          28          TO_NEXT_BLANK = BREAK(' ')
          29          SKIP_BLANKS = SPAN(' ')
              *
              * Utility functions
              *
              * DEF - Define other functions
          30          DEFINE( 'DEF(NAME,ARGS,LOCALS,BODY,RTN)', 'DEF1')
              +            :(DEF_END)
          31  DEF1    ARGS ' ' = ','                            :S(DEF1)
          32  DEF2    LOCALS ' ' = ','                          :S(DEF2)
              *
              * Define new function



       AI Programming in SNOBOL4       - 58 -                    August, 1982








          33          DEFINE( NAME '(' ARGS ')' LOCALS )
              * Build body with proper return
          34          BODY = IDENT( RTN, null) BODY ' :(RETURN)'
              +          :S(DEF3)
          35          BODY = IDENT( RTN, 'S') BODY ' :S(RETURN)F(FRETURN)'
              +          :S(DEF3)
          36          BODY = IDENT( RTN, 'F') BODY ' :F(RETURN)S(FRETURN)'
              +          :S(DEF3)
          37          BODY = IDENT( RTN, 'N') BODY ' :(NRETURN)'
          38  DEF3    CODE(NAME ' ' BODY)            :(RETURN)
          39  DEF_END
              *
              * APPEND3
          40          DEFINE( 'APPEND3(S1,S2,S3)' )  :(APPEND3_END)
          41  APPEND3
          42         APPEND3 = ( NULL(S1) NULL(S2) NULL(S3)) nil :S(RETURN)
          43         APPEND3 = ( NULL(S1) NULL(S2))
              +           STACK( TOP(S3), APPEND3( S1, S2, REST(S3)))
              +            :S(RETURN)
          44          APPEND3 = NULL(S1)
              +           STACK( TOP(S2), APPEND3( S1, REST(S2), S3))
              +            :S(RETURN)
          45          APPEND3 =
              +           STACK( TOP(S1), APPEND3( REST(S1), S2, S3))
              +           :(RETURN)
          46  APPEND3_END
              *
              * NULL - Succeed if stack empty
          47          DEF( 'NULL', 'X',, 'IDENT(X,nil)', 'S')
              *
              * TRUE - Succeed if stack not empty
          48          DEF( 'TRUE', 'X',, 'DIFFER(X,nil)', 'S')
              *
              * MAX   - Maximum of two values
          49        DEF( 'MAX', 'N1 N2',, 'MAX = N1 ; MAX = GT(N2,N1) N2')
              *
              * MIN   - Minimum of two values
          50        DEF( 'MIN', 'N1 N2',, 'MIN = N1 ; MIN = LT(N2,N1) N2')
              *
              * CNTR - Center string in field
          51          DEFINE( 'CNTR(N,V)X' )               :(CNTR_END)
          52  CNTR
          53          X = CONVERT( (N - SIZE(V)) / 2, 'INTEGER')
          54          CNTR = LPAD(RPAD(V, N - X), N)       :(RETURN)
          55  CNTR_END
              *
          56          PRT_PAT = LEFT_END REM $ OUTPUT $ SHADOW
              *
              * PRT - String to OUTPUT and SHADOW
          57          DEF( 'PRT', 'X',, 'X PRT_PAT' )
              *
              * Core functions for alpha-beta serach
              *
              * SEARCH



       AI Programming in SNOBOL4       - 59 -                    August, 1982








          58        DEFINE( 'SEARCH(NODE,LEVEL,ALPHA,BETA)' ) :(SEARCH_END)
          59  SEARCH
          60        NODE = START(NODE)
          61        SEARCH = DEAD(NODE,LEVEL) STATIC(NODE)    :S(SEARCH_A)
          62          SEARCH =
              +        SEARCH1( MAXER(NODE), (LEVEL - 1), ALPHA, BETA,
              +          EXPAND(NODE))
          63  SEARCH_A
          64          NEND(NODE)                               :(RETURN)
          65  SEARCH_END
              *
              * SEARCH1
          66         DEFINE( 'SEARCH1(MAXR,LVL,ALPHA,BETA,NL)' )
              +            :(SEARCH1_END)
          67  SEARCH1
          68          SEARCH1 =
              +         SEARCH2( MAXR, LVL, ALPHA, BETA, REST(NL),
              +            SEARCH( TOP(NL), LVL, ALPHA, BETA))    :(RETURN)
          69  SEARCH1_END
              *
              * SEARCH2
          70          DEFINE( 'SEARCH2(MAXR,LVL,ALPHA,BETA,NL,PBV)' )
              +            :(SEARCH2_END)
          71  SEARCH2
          72          SEARCH2 = NULL(NL) PBV                     :S(RETURN)
          73          SEARCH2 = CUTOFF( MAXR, PBV, ALPHA, BETA ) PBV
              +          :S(RETURN)
          74       SEARCH2 = TRUE(MAXR)
              +     SEARCH2( MAXR, LVL, ALPHA, BETA, REST(NL),
              +     MAX( PBV, SEARCH( TOP(NL), LVL, MAX(ALPHA,PBV), BETA)))
              +               :S(RETURN)
          75       SEARCH2 =
              +     SEARCH2( MAXR, LVL, ALPHA, BETA, REST(NL),
              +     MIN( PBV, SEARCH( TOP(NL), LVL, ALPHA, MIN(BETA,PBV))))
              +               :(RETURN)
          76  SEARCH2_END
              *
              * CUTOFF
          77          DEFINE( 'CUTOFF(MAXR,PBV,ALPHA,BETA)' ) :(CUTOFF_END)
          78  CUTOFF
          79          TRUE(MAXR)                       :F(CUTOFF1)
          80          GE( PBV, BETA)                   :S(RETURN)F(FRETURN)
          81  CUTOFF1
          82          LE( PBV, ALPHA)                  :S(RETURN)F(FRETURN)
          83  CUTOFF_END
              *
              *
              * Functions defining the representations of the board
              *
          84          OTHERP = 'O' ; OTHERO = 'P'
              *
              * OTHER - Other player (P or O)
          86     DEF( 'OTHER', 'PL',, 'OTHER = $( "OTHER" PL)' )
              *



       AI Programming in SNOBOL4       - 60 -                    August, 1982








              * POTR - Player's POT n
          87     DEF( 'POTR', 'PL N',, 'POTR = $( PL N)' )
              *
              * KALAHR - Player's Kalah
          88     DEF( 'KALAHR', 'PL',, 'KALAHR = $( PL "KALAH" )' )
              *
              * VALUE
          89     DEF( 'VALUE', 'POT',, 'VALUE = TOP(KVALUE(POT))' )
              *
              * PUSHVAL
          90     DEF( 'PUSHVAL', 'POT VAL',, 'KVALUE(POT) ='
              +        ' STACK(VAL,KVALUE(POT))' )
              *
              * POPVAL
          91     DEF( 'POPVAL', 'POT',, 'KVALUE(POT) = REST(KVALUE(POT))' )
              *
              * CHANGEVAL
          92     DEF( 'CHANGEVAL', 'POT VAL',, 'TOP(KVALUE(POT)) = VAL' )
              *
              * EMPTY - Succeed if pot empty
          93     DEF( 'EMPTY', 'POT',, 'EQ(VALUE(POT), 0)', 'S')
              *
              * PATHR - Player's move path
          94     DEF( 'PATHR', 'PL',, 'PATHR = PL "PATH" ' )
              *
              *
          95          PSIDE = 'P1 P2 P3 P4 P5 P6 '
          96          OSIDE = 'O1 O2 O3 O4 O5 O6 '
              *
              * SIDER - Get string of player's pots
          97          DEF( 'SIDER', 'PL',, 'SIDER = $( PL "SIDE" )' )
              *
              * SETPATH - Link pots thru PATH fields
          98          DEFINE( 'SETPATH(P,LAT)' )
          99          SETPATH_PAT = LEFT_END ( TO_NEXT_BLANK $ A )
              +                     SKIP_BLANKS
              +                     (( ( TO_NEXT_BLANK $ B) REM) $ C)
              +                        :(SETPATH_END)
          100 SETPATH
          101         LAT SETPATH_PAT = C                       :F(RETURN)
              *
              * xPATH(pot) = pot
          102         :<CODE(' ' P '(' A ') = ' B ' :(SETPATH)')>
          103 SETPATH_END
          104         SETSYM_PAT = FENCE ( TO_NEXT_BLANK $ A)
              +              SKIP_BLANKS ( TO_NEXT_BLANK $ B)
              +              SKIP_BLANKS *SETSYM1()
              +              *SETSYM_PAT
              * SETSYM - Link pots to opposites
              *
          105         DEF( 'SETSYM', 'P L',, 'L SETSYM_PAT')
              *
              * SETSYM1 - Helper for SETSYM
          106         DEFINE( 'SETSYM1()' )                 :(SETSYM1_END)



       AI Programming in SNOBOL4       - 61 -                    August, 1982








              *
              * OPP(pot) = pot
          107 SETSYM1
          108         :<CODE(' ' P '(' A ') = ' B ' ; '
              +          P '(' B ') = ' A ' :(RETURN)')>
          109 SETSYM1_END
              *
              * Functions to define the legal moves
              *
              * MOVE - Make player's move for pot
          110         DEFINE( 'MOVE(PL,POT)' )             :(MOVE_END)
          111 MOVE
          112         MOVE1(PL,POT,TAKE(POT),PATHR(PL),KALAHR(PL))
              +               :S(RETURN)F(FRETURN)
          113 MOVE_END
              *
              * MOVE1 - helper for MOVE
          114         DEFINE( 'MOVE1(PL,POT,STONES,PATH,KALAH)' )
              +              :(MOVE1_END)
              *
              * Distribute all stones
          115 MOVE1
          116         EQ(STONES,0)                              :S(MOVE1A)
              *
              * Next pot along path
          117         POT = APPLY(PATH,POT)
              *
              * Put a stone in it
          118         DROP(1,POT)
              *
              * One less stone
          119         STONES = STONES - 1                      :(MOVE1)
              *
              * Check capture
          120 MOVE1A
          121         CHECKCAP( POT, PL, KALAH, OPP(POT))
              *
              * Check for empty side
          122         CHECKMT()
              *
              * Ck last stone land in Kalah?
          123         IDENT( POT, KALAH)              :S(RETURN)F(FRETURN)
          124 MOVE1_END
              *
              * If there is 1 stone in the pot,
              *  and it is my pot,
              *   and it is not the Kalah,
              *    and the opponent's pot is not empty, THEN
              *     transfer stones from my pot to the Kalah and
              *     transfer stones from opponent's pot to the Kalah.
              *
              * CHECKCAP - Check for capture
          125         DEFINE( 'CHECKCAP(POT,PL,KALAH,OPPOT)' )
              +                  :(CHECKCAP_END)



       AI Programming in SNOBOL4       - 62 -                    August, 1982








          126 CHECKCAP
          127          ( EQ(VALUE(POT), 1)
              +           IDENT(OWNER(POT),PL)
              +            DIFFER(POT,KALAH)
              +             ~EMPTY(OPPOT)
              +              DROP(TAKE(POT), KALAH)
              +               DROP(TAKE(OPPOT), KALAH) )        :(RETURN)
          128 CHECKCAP_END
              *
              * If one side empty, transfer all stones from other side to
              * their Kalah.
              * CHECKMT - Check side empty
          129         DEFINE( 'CHECKMT()' )                 :(CHECKMT_END)
          130 CHECKMT
          131         ( MTSIDEP(PSIDE) MTSIDE(OSIDE,OKALAH) )  :S(RETURN)
          132         ( MTSIDEP(OSIDE) MTSIDE(PSIDE,PKALAH) )
              +               :S(RETURN)F(FRETURN)
          133 CHECKMT_END
              *
              * Use recursive pattern to loop scan
          134         MTSIDEP_PAT = FENCE
              +              TO_NEXT_BLANK $ P  *EMPTY($P)
              +              SKIP_BLANKS (RIGHT_END | *MTSIDEP_PAT)
              *
              * MTSIDEP - Scan side for all empty
          135         DEF( 'MTSIDEP', 'SIDE',, 'SIDE MTSIDEP_PAT', 'S')
              *
              * Use recursive pattern to loop calls
          136         MTSIDE_PAT = FENCE
              +              TO_NEXT_BLANK $ P *DROP(TAKE($P),KALAH)
              +              SKIP_BLANKS *MTSIDE_PAT
              *
              * MTSIDE - Transfer all on side to Kalah
          137      DEF( 'MTSIDE', 'SIDE KALAH',, 'SIDE MTSIDE_PAT' )
              *
              * TAKE - Remove stones from pot
          138      DEF( 'TAKE', 'POT',, 'TAKE = VALUE(POT) ;'
              +       ' CHANGEVAL(POT,0)' )
              *
              * DROP - Add stones to pot
          139      DEF( 'DROP', 'N POT',, 'CHANGEVAL(POT,'
              +       ' (N + VALUE(POT)))' )
              *
              * Functions to operate on game-tree nodes
              *
              * MULT
          140      DEF( 'MULT', 'NODE',,
              +        'IDENT(PLAYER(NODE),NEXT_PLAYER(NODE))', 'S')
              *
              * START
          141         DEFINE( 'START(NODE)' )
          142         START_PAT = FENCE
              +              TO_NEXT_BLANK $ P *PUSHVAL($P,VALUE($P))
              +              SKIP_BLANKS *START_PAT          :(START_END)



       AI Programming in SNOBOL4       - 63 -                    August, 1982








          143 START
          144         (PSIDE 'PKALAH ' OSIDE 'OKALAH ') START_PAT
          145         MOVE( PLAYER(NODE), MOVEOF(NODE))
          146         START =
              +        NODE( NEXT_PLAYER(NODE), MOVEOF(NODE), PLAYER(NODE))
              +          :(RETURN)
          147 START_END
              *
          148         NEND_PAT = FENCE
              +         TO_NEXT_BLANK $ P   *POPVAL($P)
              +         SKIP_BLANKS *NEND_PAT
              *
              * NEND
          149     DEF( 'NEND', 'NODE',, '(PSIDE "PKALAH " OSIDE "OKALAH ")'
              +         ' NEND_PAT' )
              *
              * DEAD
          150         DEFINE( 'DEAD(NODE,LEVEL)' )           :(DEAD_END)
          151 DEAD
          152         ( LE(LEVEL,0) ~MULT(NODE) )            :S(RETURN)
          153         GT( VALUE(PKALAH), HALFSTONES)         :S(RETURN)
          154         GT( VALUE(OKALAH), HALFSTONES)         :S(RETURN)
          155         ( EQ( VALUE(PKALAH), HALFSTONES)
              +       EQ( VALUE(OKALAH), HALFSTONES) ) :S(RETURN)F(FRETURN)
          156 DEAD_END
              *
              * STATIC
          157         DEFINE( 'STATIC(NODE)' )               :(STATIC_END)
          158 STATIC
          159         TNODES = TNODES + 1
          160         STATIC = GT( VALUE(PKALAH), HALFSTONES) INFINITY
              +              :S(RETURN)
          161         STATIC = GT( VALUE(OKALAH), HALFSTONES) -INFINITY
              +              :S(RETURN)
          162         STATIC = VALUE(PKALAH) - VALUE(OKALAH)  :(RETURN)
          163 STATIC_END
              *
              * MAXER
          164         DEFINE( 'MAXER(NODE)' )              :(MAXER_END)
          165 MAXER
          166         MAXER = nil
          167         MAXER = IDENT( PLAYER(NODE), 'P') t  :(RETURN)
          168 MAXER_END
              *
              * EXPAND
          169         DEFINE( 'EXPAND(NODE)' )             :(EXPAND_END)
          170 EXPAND
          171         BNODES = BNODES + 1
          172         EXPAND = EXPAND1( PLAYER(NODE), SIDER(PLAYER(NODE)))
              +            :(RETURN)
          173 EXPAND_END
              *
              * EXPAND1
          174         DEFINE( 'EXPAND1(PL,SIDE)LMULT,LCAP,LREG')



       AI Programming in SNOBOL4       - 64 -                    August, 1982








          175         EXPAND1_PAT = FENCE
              +              TO_NEXT_BLANK $ P  *EXPAND2(PL,$P)
              +              SKIP_BLANKS  *EXPAND1_PAT    :(EXPAND1_END)
          176 EXPAND1
          177         LMULT = nil ; LCAP = nil ; LREG = nil
          180         SIDE EXPAND1_PAT
          181         EXPAND1 = APPEND3( LMULT, LCAP, LREG)   :(RETURN)
          182 EXPAND1_END
              *
              * EXPAND2
          183         DEFINE( 'EXPAND2(PL,POT)' )         :(EXPAND2_END)
          184 EXPAND2
          185         EMPTY(POT)                          :S(RETURN)
          186         LMULT = MULTMOVE(POT)
              +         STACK( NODE(PL,POT,PL), LMULT)    :S(RETURN)
          187         LCAP = CAPMOVE(PL,POT)
              +         STACK( NODE(PL,POT,OTHER(PL)), LCAP) :S(RETURN)
          188         LREG =
              +         STACK( NODE(PL,POT,OTHER(PL)), LREG) :(RETURN)
          189 EXPAND2_END
              *
              * MULTMOVE
          190         DEF( 'MULTMOVE', 'POT',,
              +          'EQ(REMDR(VALUE(POT),13), 7 - NUM(POT))', 'S')
              *
              * CAPMOVE
          191         DEF( 'CAPMOVE', 'PL POT',,
              +         'CAPMOVE1(PL,POT,VALUE(POT),NUM(POT))', 'S')
              *
              * CAPMOVE1
          192         DEFINE( 'CAPMOVE1(PL,POT,V,N)' )    :(CAPMOVE1_END)
          193 CAPMOVE1
          194         EQ(V,13)                            :S(RETURN)
          195         ( LT(V, (7 - N))
              +         EMPTY( POTR( PL, (N + V)))
              +         ~EMPTY( OPP( POTR( PL, (N + V)))) )   :S(RETURN)
          196         ( GT(V, (13 - N))
              +      LT(V, 13)
              +      EMPTY( POTR( PL, (N - 13 + V))) ) :S(RETURN)F(FRETURN)
          197 CAPMOVE1_END
              *
              * Functions for controlling an interactive game
              *
              * KALAH - Play the game
          198         DEFINE( 'KALAH(N,DEPTH)' )            :(KALAH_END)
          199 KALAH
          200         ( INITBRD(N)
              +         PRINTBRD()
              +         ALTMOVE(MEFIRST()) )
          201           KALAH = 'Thanks.'                   :(RETURN)
          202 KALAH_END
              *
              * INITBRD - Iniitalize board
          203         DEFINE( 'INITBRD(VAL)' )



       AI Programming in SNOBOL4       - 65 -                    August, 1982








          204         INITBRD_PAT = FENCE
              +         TO_NEXT_BLANK $ P  *INITBRD1(P)
              +         SKIP_BLANKS  *INITBRD_PAT
          205         INITBRD1_PAT = LEFT_END
              +              ( (LEN(1) $ O) (LEN(1) $ N) )
          206         :(INITBRD_END)
          207 INITBRD
          208         INFINITY = 100
          209         TNODES = 0
          210         BNODES = 0
          211         HALFSTONES = 6 * VAL
          212         (PSIDE OSIDE) INITBRD_PAT
          213         PKALAH = POT('P',0,STACK(0,nil),null,null,null)
          214         OKALAH = POT('O',0,STACK(0,nil),null,null,null)
          215         SETSYM('OPP','P1 O6 P2 O5 P3 O4 P4 O3 P5 O2 P6 O1 ')
          216         SETPATH('PPATH',
              +          'P1 P2 P3 P4 P5 P6 PKALAH O1 O2 O3 O4 O5 O6 P1 ')
          217         SETPATH('OPATH',
              +          'O1 O2 O3 O4 O5 O6 OKALAH P1 P2 P3 P4 P5 P6 O1 ')
          218         REWIND(1)
          219                     :(RETURN)
          220 INITBRD_END
              *
              * INITBRD1
          221         DEFINE( 'INITBRD1(PNAME)' )          :(INITBRD1_END)
          222 INITBRD1
          223         PNAME INITBRD1_PAT
          224         $PNAME = POT(O,N,STACK(VAL,nil),null,null,null)
              +              :(RETURN)
          225 INITBRD1_END
              *
              * PRINTBRD - Print board
          226         DEFINE( 'PRINTBRD()' )            :(PRINTBRD_END)
          227 PRINTBRD
          228         PRT( DUPL(' ',7)
              +            CNTR(7,VALUE(P6))
              +            CNTR(7,VALUE(P5))
              +            CNTR(7,VALUE(P4))
              +            CNTR(7,VALUE(P3))
              +            CNTR(7,VALUE(P2))
              +            CNTR(7,VALUE(P1)) )
          229         PRT( CNTR(7,VALUE(PKALAH))
              +            DUPL(' ',42)
              +            CNTR(7,VALUE(OKALAH)) )
          230         PRT( DUPL(' ',7)
              +            CNTR(7,VALUE(O1))
              +            CNTR(7,VALUE(O2))
              +            CNTR(7,VALUE(O3))
              +            CNTR(7,VALUE(O4))
              +            CNTR(7,VALUE(O5))
              +            CNTR(7,VALUE(O6)) )
          231                    :(RETURN)
          232 PRINTBRD_END
              *



       AI Programming in SNOBOL4       - 66 -                    August, 1982








              * MEFIRST
          233         DEFINE( 'MEFIRST()' )               :(MEFIRST_END)
          234 MEFIRST
          235        PRT( 'Do you want to go first?')
          236        MEFIRST = REPLACE(INPUT,LOWERS,UPPERS)        :F(END)
          237        SHADOW = DUPL(' ',10) 'Answer: ' MEFIRST
          238        MEFIRST (LEFT_END ('YES' | 'NO') RIGHT_END) :S(RETURN)
          239        PRT( 'Please answer YES or NO.')        :(MEFIRST)
          240 MEFIRST_END
              *
              * ALTMOVE
          241         DEFINE( 'ALTMOVE(YN)' )                :(ALTMOVE_END)
          242 ALTMOVE
          243         IDENT(YN,'NO')                         :F(ALTMOVE2)
          244 ALTMOVE1
              *
              * Computer, then user
          245         ( PMOVE() OMOVE() )            :S(ALTMOVE1)F(RETURN)
              *
              * User, then computer
          246 ALTMOVE2
          247         ( OMOVE() PMOVE() )            :S(ALTMOVE2)F(RETURN)
          248 ALTMOVE_END
              *
              * OMOVE - Carry out user's move
          249         DEFINE( 'OMOVE()' )                     :(OMOVE_END)
              * Check for end of game
          250 OMOVE
          251         ENDGAME()                                 :S(FRETURN)
              *
              * Get and make move
          252         MOVE( 'O', GETMOVE() )                    :F(OMOVE1)
              *
              * Landed on kalah
          253         PRINTBRD()
          254         PRT( 'You go again.' )                    :(OMOVE)
              *
              * Did not land on Kalah
          255 OMOVE1
          256         PRINTBRD()                                :(RETURN)
          257 OMOVE_END
              *
              * GETMOVE - Get user's move
          258         DEFINE( 'GETMOVE()N' )             :(GETMOVE_END)
          259 GETMOVE
          260         PRT( "What's your move?" )
          261         N = INPUT                            :F(END)
          262         SHADOW = DUPL(' ',10) 'Answer: ' N
          263         GETMOVE =
              +          ( INTEGER(N) GT(N,0) LT(N,7) ~EMPTY(POTR('O',N)) )
              +         POTR('O',N)                    :S(RETURN)
          264         PRT( "That's illegal.")          :(GETMOVE)
          265 GETMOVE_END
              *



       AI Programming in SNOBOL4       - 67 -                    August, 1982








              * ENDGAME - Check for end of game
          266         DEFINE( 'ENDGAME()' )            :(ENDGAME_END)
          267 ENDGAME
          268         ( GT(VALUE(PKALAH),HALFSTONES) PRT( 'I win.') )
              +            :S(RETURN)
          269         ( GT(VALUE(OKALAH),HALFSTONES) PRT( 'You win.') )
              +            :S(RETURN)
          270         ( EQ(VALUE(PKALAH),HALFSTONES)
              +           EQ(VALUE(OKALAH),HALFSTONES)
              +         PRT( "It's a tie.") )              :S(RETURN)
          271                :(FRETURN)
          272 ENDGAME_END
              *
              * PMOVE - Make computer's move
          273         DEFINE( 'PMOVE()' )                  :(PMOVE_END)
          274 PMOVE
          275         PRT( 'I go.' )
          276 PMOVE1
          277         ENDGAME()                            :S(FRETURN)
          278         PRT( 'Hmmm....' )
          279         COLLECT()
          280         PLAY(-INFINITY,INFINITY,0,0,TIME())  :F(RETURN)
              *
              * If computer landed on PKALAH
          281         PRT( 'I go again.' )                 :(PMOVE1)
          282 PMOVE_END
              *
              * PLAY
          283         DEFINE( 'PLAY(ALPHA,BETA,BNODES,TNODES,SECS)' )
              +              :(PLAY_END)
          284 PLAY
          285         PLAY1(EXPAND(NODE('P',nilpot,'O')))
              +                :S(RETURN)F(FRETURN)
          286 PLAY_END
              *
              * PLAY1
          287         DEFINE( 'PLAY1(LNODES)' )          :(PLAY1_END)
          288 PLAY1
          289         NULL(REST(LNODES))                        :F(PLAY1A)
          290         CHOOSE(REST(LNODES),TOP(LNODES),"not calculated")
              +                  :S(RETURN)F(FRETURN)
          291 PLAY1A
          292         CHOOSE(REST(LNODES),TOP(LNODES),,
              +         SEARCH(TOP(LNODES),DEPTH,ALPHA,BETA))
              +                  :S(RETURN)F(FRETURN)
          293 PLAY1_END
              *
              * CHOOSE
          294         DEFINE( 'CHOOSE(LNODES,BEST,V)NV' )  :(CHOOSE_END)
          295 CHOOSE
          296         NULL(LNODES)                         :S(CHOOSE2)
          297         EQ(V,INFINITY)                       :S(CHOOSE2)
          298         NV = SEARCH(TOP(LNODES),DEPTH,V,BETA)
          299         LE(NV,V)                             :S(CHOOSE1)



       AI Programming in SNOBOL4       - 68 -                    August, 1982








          300         V = NV
          301         BEST = TOP(LNODES)
          302 CHOOSE1
          303         LNODES = REST(LNODES)                       :(CHOOSE)
          304 CHOOSE2
          305         MAKE(BEST,V)                   :S(RETURN)F(FRETURN)
          306 CHOOSE_END
              *
              * MAKE
          307         DEFINE( 'MAKE(CHOSEN,VAL)' )              :(MAKE_END)
          308 MAKE
          309         REPORT(NUM(MOVEOF(CHOSEN)),
              +         VAL, BNODES, TNODES, TIME() - SECS )
          310         MOVE(PLAYER(CHOSEN),MOVEOF(CHOSEN))       :F(MAKE1)
          311         PRINTBRD()                                :(RETURN)
          312 MAKE1
          313         PRINTBRD()                                :(FRETURN)
          314 MAKE_END
              *
              * REPORT - Statistics
          315         DEFINE( 'REPORT(M,V,B,T,S)' )        :(REPORT_END)
          316 REPORT
          317         PRT("I pick pot " M ".  Value " V)
          318         PRT(B " nodes expanded, " T " evaluated")
          319         PRT(S " milliseconds used")               :(RETURN)
          320 REPORT_END
              *
              * Finally, MAIN PROGRAM STARTS HERE.
              ************************************
              *
          321 GET_NUMBER_OF_STONES
          322         PRT( 'Enter number of stones per pot' )
          323         N = INPUT                                 :F(END)
          324         SHADOW = DUPL(' ',10) 'Answer: ' N
          325         ( INTEGER(N) GT(N,0) )      :F(GET_NUMBER_OF_STONES)
          326 GET_SEARCH_DEPTH
          327         PRT( 'Enter maximum search depth' )
          328         D = INPUT
          329         SHADOW = DUPL(' ',10) 'Answer: ' D
          330         ( INTEGER(D) GT(D,0) )       :F(GET_SEARCH_DEPTH)
          331         OUTPUT = KALAH(N,D)          :S(GET_NUMBER_OF_STONES)
          332         ENDFILE(1)
          333 END














       AI Programming in SNOBOL4       - 69 -                    August, 1982








                                     APPENDIX E

            This is a compilation listing of a compiler for an augmented
          transition network (ATN) language like the one described in
          Winston and Horn (1981, pp. 251-277).  The listing of the
          compiler is followed by a sample programming session (input in
          the ATN source language, followed by the output produced by
          executing the ATN program).

            Note that the ATN source language is an extension of Winston
          and Horn's, and that the compiler is not very similar to their
          LISP version.

              * ATN.SPT
              *          SNOBOL4 program to implement a compiler for an
              *               Augmented Transition Network Language.
              *
              * The compiler compiles a network description of English
              * sentence structure into SNOBOL4 code.  Sentences are then
              * the 'source input' to the network, which tries to parse
              * them.
              *
              * A LISP version of the compiler is described in:
              *  Winston, P.H., & Horn, B.P.K, LISP,
              *  New York: Addison-Wesley, 1981.
              *
              *
              * Keyword settings
              *
          1           &ANCHOR = 0
              *
              * Set CODE_PRINT to 1 to get listing of generated code
              *
          2           CODE_PRINT = 0
          3           &DUMP   = 0
          4           &FTRACE = 0
          5           &FULLSCAN = 1
          6           &MAXLNGTH = 32767
              *
              * Set this to 1 to get source listing echoed to terminal
              *
          7           SCREEN_ECHO = 0
          8           &STLIMIT  = -1
          9           &TRACE  = 0
          10          &TRIM   = 1
              *
              *
              * I/O Assoications
              *
          11          INPUT(.INPUT)
          12          INPUT(.ATNSOURCE,2,,'ATN.IN')
          13          OUTPUT(.OUTPUT)
          14          OUTPUT(.SLIST, 1,, 'SLIST')
              *



       AI Programming in SNOBOL4       - 70 -                    August, 1982








              * Defined data types
              *
          15          DATA( 'STACK(TOP,REST)' )
              *
              * Global constants
              *
          16          null = ''
          17          nil  = STACK()
          18          TOP(nil)  = nil
          19          REST(nil) = nil
              *
          20          SENTENCES = nil
          21          LEX_STACK = nil
          22          LEXICAL_FEATURES = TABLE()
              *
              * Utility patterns
              *
          23          BLANK   = ' '
          24          SC      = ';'
          25          Q1      = "'"
          26          Q2      = '"'
          27          COMMA   = ','
          28          STAR    = '*'
          29          LP      = '('
          30          RP      = ')'
          31          UL      = '_'
          32          PUSHER  = '>'
          33          POPPER  = '<'
              *
          34          LEFT_END  = POS(0)
          35          RIGHT_END = RPOS(0)
              *
          36          BLANKS  = SPAN(BLANK)
          37          OPT_BLANKS = BLANKS | null
          38          BB      = BREAK(BLANK)
          39          BXB     = BREAKX(BLANK)
              *
          40          BBSC    = BREAK(BLANK SC)
          41          SPSC    = SPAN(SC)
          42          SPBSC   = SPAN(BLANK SC)
          43          SPBSCN  = SPBSC | null
          44          BSC     = BREAK(SC)
              *
          45          LEN1    = LEN(1)
          46          L1REM   = LEN1 REM
              *
          47          BRP     = BREAK(RP)
          48          BRPN    = BRP | null
              *
              * Utility functions
              *
              * Print X to the source listing file and output file
              *
          49          DEFINE('PRT(X)')                          :(PRT_END)



       AI Programming in SNOBOL4       - 71 -                    August, 1982








          50  PRT
          51          OUTPUT = SLIST = X                        :(RETURN)
          52  PRT_END
              *
              * Error MSG to source listing file and output file
              *
          53          DEFINE('ERROR(MSG)')                     :(ERROR_END)
          54  ERROR
          55          ( PRT() PRT(MSG) PRT() )                  :(RETURN)
          56  ERROR_END
              *
              * Readable display of SNOBOL4 code
              *
          57          DEFINE( 'DISPLAY(SNOCODE)S,L' )      :(DISPLAY_END)
          58  DISPLAY
          59          EQ(CODE_PRINT,0)                     :S(RETURN)
          60          (PRT() PRT('------ Code ------') PRT())
          61  DISPLAY1
          62          SNOCODE LEFT_END (BSC $ S) SPSC =    :F(DISPLAY3)
          63          S LEFT_END (NOTANY(BLANK) (BB | null)) $ L =
              +             :F(DISPLAY2)
          64          PRT('     | ' L)
          65  DISPLAY2
          66          S LEFT_END BLANKS =
          67          S = TRIM(S)
          68          NULL(S)                               :S(DISPLAY1)
          69          PRT('     |  ' S)                     :(DISPLAY1)
          70  DISPLAY3
          71          (PRT() PRT('------ End of Code ------') PRT())
              +           :(RETURN)
          72  DISPLAY_END
              *
              * Succeeds if X is nil, null, or zero
              *
          73          DEFINE('NULL(X)')                         :(NULL_END)
          74  NULL
          75          IDENT(X,nil)                            :S(RETURN)
          76          IDENT(X,null)                           :S(RETURN)
          77          X = CONVERT(X,"INTEGER")                :F(FRETURN)
          78          EQ(X,0)                        :S(RETURN)F(FRETURN)
          79  NULL_END
              *
              * Put COAT on RACK using HANGER
              *
          80          DEFINE( 'PUT(RACK,COAT,HANGER)' )      :(PUT_END)
          81  PUT
          82          PROP<RACK> =
              +         DIFFER('TABLE',DATATYPE(PROP<RACK>)) TABLE()
          83          ITEM(PROP<RACK>,HANGER) = COAT         :(RETURN)
          84  PUT_END
              *
              * Get contents of HANGER off RACK
              *
          85          DEFINE( 'GET(RACK,HANGER)' )           :(GET_END)



       AI Programming in SNOBOL4       - 72 -                    August, 1982








          86  GET
          87          PROP<RACK> =
              +         DIFFER('TABLE',DATATYPE(PROP<RACK>)) TABLE()
              +            :S(RETURN)
          88          GET = ITEM(PROP<RACK>,HANGER)         :(RETURN)
          89  GET_END
              *
              * Program text semi-constants used in code generation
              *
          90          &ALPHABET POS(1) (LEN1 $ MAGIC_CHAR)
              *
          91          REPLACE_LIT = MAGIC_CHAR 'RePlAcE' MAGIC_CHAR
              *
          92          BEGIN_TEXT =
              +         ' HOLD = REMAINING_WORDS ;'
              +         ' REMAINING_WORDS (BREAK(" ") $ CURRENT_WORD) ;'
              +         ' THIS_NODE = GENNAME("' REPLACE_LIT '") ;'
              +         ' :(' REPLACE_LIT '_START) ;'
              *
          93          WIN_TEXT =
              +        REPLACE_LIT '_WIN'
              +        ' TESTF(THIS_NODE,FEATS) :F(' REPLACE_LIT '_LOSE) ;'
              +         ' ATTACH(THIS_NODE,PARENT) ;'
              +         ' LAST_PARSED = THIS_NODE :(RETURN) ;'
              *
          94          LOSE_TEXT =
              +         REPLACE_LIT '_LOSE'
              +         ' REMAINING_WORDS = HOLD ;'
              +         ' REMAINING_WORDS (BREAK(" ") $ CURRENT_WORD)'
              +                 ':(FRETURN) ;'
              *
          95          INITIAL_ROUTINE =
              +         REPLACE_LIT BEGIN_TEXT
              +         WIN_TEXT LOSE_TEXT REPLACE_LIT '_START ;'
              *
              * Patterns used in COMPILE routine
              *
          96          COMMENT_PAT = (LEFT_END OPT_BLANKS STAR) |
              +         (LEFT_END RIGHT_END)
              *
          97          KEYWORD_PAT = 'NETWORK' | 'FUNCTION' | 'LEXICON'
              +         | 'SENTENCES' | 'EXEC'
              *
          98          NAME_PAT    = (BB $ NAME) BLANKS FENCE
              *
          99          LEGAL_PAT   = LEFT_END KEYWORD_PAT . KEYTYPE BLANKS
              +         (BB | REM) . TNAME
              *
          100         COMPLETE_PAT = (LEFT_END 'EXEC' BLANKS)
          101         COMPLETE_PAT = COMPLETE_PAT |
              +           (LEFT_END BB BLANKS (BB $ TNAME) BLANKS FAIL)
          102         COMPLETE_PAT = COMPLETE_PAT |
              +           ('END' OPT_BLANKS *TNAME RIGHT_END)
              *



       AI Programming in SNOBOL4       - 73 -                    August, 1982








              * Definitions of semantic (code-generating) functions
              *
          103         DEFINE( 'S(NA)' )
          104         DEFINE( 'S_(NA)T' )
              *
              * Recognizer/compiler patterns for the five types of blocks:
              *  EXEC, SENTENCES, LEXICON, FUNCTION, and NETWORK
              *
              * Recognizer for EXEC statement
              *
          105        EXEC_PAT = LEFT_END 'EXEC' BLANKS (REM $ NAME) S('EX')
              *
              * Recognizer/Compiler for SENTENCES block
              *
          106         SENTENCES_LIT = 'SENTENCES' BLANKS FENCE
          107         SENTENCES_HEADER = LEFT_END SENTENCES_LIT NAME_PAT
          108         SENTENCE_PAT   = (BSC $ SENT) SPBSC S('SENT')
          109         SENTENCES_BODY = ARBNO(SENTENCE_PAT)
          110         SENTENCES_ENDER = 'END' OPT_BLANKS *NAME RIGHT_END
          111         SENTENCES_PAT = SENTENCES_HEADER SENTENCES_BODY
              +         SENTENCES_ENDER
              *
              * Recognizer/Compiler for LEXICON block
              *
          112         LEXICON_LIT = 'LEXICON' BLANKS FENCE
          113         LEXICON_HEADER = LEFT_END LEXICON_LIT NAME_PAT
          114         LEX_PUSH_PAT = PUSHER (BB $ F) BLANKS S('PSH')
          115         LEX_POP_PAT = POPPER (BB $ F) BLANKS S('POP')
          116         WORD_PAT = NOTANY(PUSHER POPPER) (BB | null)
          117         LEX_W_PAT = (WORD_PAT $ W) BLANKS S('LEX')
          118         ENTRY_PAT = LEX_W_PAT | LEX_PUSH_PAT | LEX_POP_PAT
          119         ENTRIES_PAT = ARBNO(ENTRY_PAT)
          120         LEXICON_ENDER = SENTENCES_ENDER
          121        LEXICON_PAT = LEXICON_HEADER ENTRIES_PAT LEXICON_ENDER
              *
              * Recognizer/Compiler for FUNCTION block
              *
          122         FUNCTION_LIT = 'FUNCTION' BLANKS FENCE
          123         FUNCTION_HEADER = LEFT_END FUNCTION_LIT NAME_PAT
          124         ARG_PAT = (( LP BRPN RP ) $ ARG ) BLANKS S('ARG')
          125         LOC_PAT = LP (BRPN $ LOC) RP BLANKS S('LOC')
          126         FUNCTION_HEADER = FUNCTION_HEADER ARG_PAT LOC_PAT
          127         STATEMENT_PAT = BSC SPSC
          128         STATEMENTS_PAT = ARBNO(STATEMENT_PAT) $ BODY BLANKS
          129         FUNCTION_ENDER = SENTENCES_ENDER
          130         FUNCTION_PAT = FUNCTION_HEADER S('FN') STATEMENTS_PAT
              +         FUNCTION_ENDER S('F')
              *
              * Recongnizer/Compiler for NETWORK block
              *
              * The IF part
              *
          131         IF_LIT = 'IF' BLANKS FENCE
              *



       AI Programming in SNOBOL4       - 74 -                    August, 1982








              * The conditional clause
              *
          132         CLAUSE_PAT = BXB
          133         COND_PAT = (CLAUSE_PAT $ COND) BLANKS
              *
              * The GOTO clause
              *
          134         GOTO_LIT = 'GO' OPT_BLANKS 'TO' BLANKS FENCE
          135         GOTO_LABEL_PAT = (BB $ GOTO_LABEL) BLANKS FENCE
          136         GOTO_PAT = GOTO_LIT GOTO_LABEL_PAT
              *
              * The AFTER clause (which may be null)
              *
          137         AFTER_LIT = 'AFTER' BLANKS FENCE
          138         SIDE_PAT = (CLAUSE_PAT $ SIDE) BLANKS
          139         ENDIF_PAT = 'END' OPT_BLANKS 'IF' BLANKS FENCE
          140         AFTER_PAT =
              +         ((null $ SIDE) ENDIF_PAT)
              +         | (AFTER_LIT SIDE_PAT ENDIF_PAT)
          141         IF_PAT = IF_LIT COND_PAT GOTO_PAT AFTER_PAT S('IF')
              *
              * The labelled set of IF statments (the RULE)
              *
          142         LABEL_PAT = (BB $ LABEL) BLANKS FENCE
          143         IFS_PAT = ARBNO(IF_PAT)
          144         END_LABEL_PAT = 'END' OPT_BLANKS *LABEL BLANKS FENCE
          145         RULE_PAT = LABEL_PAT S('LAB') IFS_PAT END_LABEL_PAT
              +            S('ELB')
              *
              * The set of RULEs (the NETWORK)
              *
          146         NETWORK_LIT = 'NETWORK' BLANKS FENCE
          147         NETWORK_HEADER = LEFT_END NETWORK_LIT NAME_PAT
          148         RULES_PAT = ARBNO(RULE_PAT)
          149         NETWORK_ENDER = SENTENCES_ENDER
          150         NETWORK_PAT = NETWORK_HEADER S('NTW')
              +              RULES_PAT
              +              NETWORK_ENDER S('ENW')
              *
              * Grand pattern for compiling any legal block
              *
          151         COMPILE_PAT = NETWORK_PAT
              +             | FUNCTION_PAT
              +             | LEXICON_PAT
              +             | SENTENCES_PAT
              +             | EXEC_PAT
              *
              * Read and compile all text from ATNSOURCE
              *   (source listing with comments goes to SLIST)
              *
          152         DEFINE( 'COMPILE()NEXT,TEXT' )      :(COMPILE_END)
              *
              * Comment or first line of block
              *



       AI Programming in SNOBOL4       - 75 -                    August, 1982








          153 COMPILE
          154         COLLECT()
          155         SETEXIT(.CONTINUE)
          156         TEXT = ATNSOURCE                     :F(RETURN)
              *
              * List record, trim leading blanks, check for legal syntax
              *
          157 COMPILE1
          158         PRT( TEXT )
          159         TEXT COMMENT_PAT                          :S(COMPILE)
          160         TEXT LEFT_END BLANKS = null
          161         TEXT LEGAL_PAT                           :S(COMPILE2)
          162         ERROR('Illegal record')                   :(FRETURN)
              *
              * Check for complete block. If incomplete, keep reading
              *
          163 COMPILE2
          164         TEXT COMPLETE_PAT                    :S(COMPILE4)
          165         SETEXIT(.CONTINUE)
          166         NEXT = ATNSOURCE                     :S(COMPILE3)
          167         ERROR('Unexpected end of file on ATNSOURCE')
              +            :(FRETURN)
              *
              * List the record, convert leading blanks to a single blank,
              *  and concatenate with TEXT
              *
          168 COMPILE3
          169         PRT( NEXT )
          170         NEXT COMMENT_PAT                     :S(COMPILE2)
          171         NEXT LEFT_END BLANKS = BLANK
          172         TEXT = TEXT NEXT                     :(COMPILE2)
              *
              * Use COMPILE_PAT to compile TEXT
              *
          173 COMPILE4
          174         TIME_ZERO = TIME()
          175         TEXT COMPILE_PAT                     :F(COMPILE5)
          176         PRT()
          177         PRT(TIME() - TIME_ZERO ' milliseconds compile time')
          178         PRT()                                     :(COMPILE)
              *
          179 COMPILE5
          180         ERROR('Compilation failed')               :(FRETURN)
          181 COMPILE_END
              *
              * Semantic (code-generation) functions
              *
          182         :(S_END)
              *
              * For immediate code generation
              *       The code is generated after a part of a syntactic
              *       pattern has successfully matched
              *
          183 S



       AI Programming in SNOBOL4       - 76 -                    August, 1982








          184         S = EVAL( "(NULL $ *S_('"  NA  "')) FENCE " )
              +             :(RETURN)
              *
              * This is a big computed GOTO with a branch for every
              *       semantic contigency.
              *
          185 S_
          186         S_ = .DUMMY                          :($( 'S_' NA ))
              *
              * Initialize the code for a network
              *
          187 S_NTW
          188         DEFINE( NAME '(PARENT,FEATS)THIS_NODE,HOLD' )
          189         DISPLAY(' DEFINE(' Q1 NAME
              +            '(PARENT,FEATS)THIS_NODE,HOLD' Q1 ') ;')
          190         ROUTINE = INITIAL_ROUTINE                 :(NRETURN)
              *
              * The label for a rule
              *
          191 S_LAB
          192         ROUTINE = ROUTINE REPLACE_LIT UL LABEL BLANK
              +              :(NRETURN)
              *
              * One IF statement is a network
              *
          193 S_IF
          194         ROUTINE = ROUTINE
              +         ' ?( ' COND BLANK SIDE ' ) '
              +         ':S(' REPLACE_LIT UL GOTO_LABEL ') ;'  :(NRETURN)
              *
              * The end of a labelled rule:  If none of the IF statements
              *       has been satisfied, then the LOSE branch is take
              *
          195 S_ELB
          196         ROUTINE = ROUTINE ' :(' REPLACE_LIT '_LOSE) ;'
              +           :(NRETURN)
              *
              * Wrap-up network:  (1) insert NAME in all the right places;
              *       (2) translate into machine language via CODE.
              *
          197 S_ENW
          198         ROUTINE REPLACE_LIT = NAME                :S(S_ENW)
          199         DISPLAY( ROUTINE )
          200         CODE( ROUTINE )                           :S(NRETURN)
          201         ERROR('Compilation error')                :(FRETURN)
              *
              * Push a sentence onto the stack of sentences
              *
          202 S_SENT
          203         SENTENCES = STACK(SENT,SENTENCES)         :(NRETURN)
              *
              * Push F onto the stack of lexical features
              *
          204 S_PSH



       AI Programming in SNOBOL4       - 77 -                    August, 1982








          205        LEX_STACK = STACK(F,LEX_STACK)            :(NRETURN)
              *
              * Pop lexical features up to, NOT INCLUDING, F
              *
          206 S_POP
          207        NULL(LEX_STACK)                           :S(NRETURN)
          208         IDENT(F,TOP(LEX_STACK))                   :S(NRETURN)
          209         LEX_STACK = REST(LEX_STACK)               :(S_POP)
              *
              * Attach all stacked features to W
              *
          210 S_LEX
          211         LEX_STACK_SAVE = LEX_STACK
          212 S_LEX1
          213         NULL(LEX_STACK)                           :S(S_LEX2)
          214         LEXICAL_FEATURES<W> = TOP(LEX_STACK) BLANK
              +              LEXICAL_FEATURES<W>
          215         LEX_STACK = REST(LEX_STACK)               :(S_LEX1)
          216 S_LEX2
          217         PRT('     | ' W ':  ' LEXICAL_FEATURES<W>)
          218         LEX_STACK = LEX_STACK_SAVE                :(NRETURN)
              *
              * Remove blanks from the formal argument list for a FUNCTION
              *
          219 S_ARG
          220         ARG BLANKS =                :S(S_ARG)F(NRETURN)
              *
              * Remove blanks from the local variable list for a FUNCTION
              *
          221 S_LOC
          222         LOC BLANKS =                :S(S_LOC)F(NRETURN)
              *
              * Initialize FUNCTION
              *
          223 S_FN
          224         DISPLAY(' DEFINE(' Q1 NAME ARG LOC Q1 ') ;')
          225         DEFINE( NAME ARG LOC )                    :(NRETURN)
              *
              * Compile a FUNCTION
              *
          226 S_F
          227         BODY = BODY " ERROR('No return from ' "
              +         Q1 NAME Q1 ") :(END) ;"
          228         DISPLAY( NAME BLANK BODY )
          229         CODE( NAME BLANK BODY )                   :S(NRETURN)
          230         ERROR('Compilation error')                :(FRETURN)
              *
              * For EXEC, call MAIN with NAME = name of first network
              *
          231 S_EX
          232         ( PRT() PRT() )
          233    PRT( '****** EXECUTION BEGINS WITH ' NAME ' ******') PRT()
          234         MAIN(NAME)                           :(NRETURN)
          235 S_END



       AI Programming in SNOBOL4       - 78 -                    August, 1982








              *
              *
              * This routine is triggered by the EXEC statement
              *
          236         DEFINE( 'MAIN(FIRST_PROC)LAST_PARSED,'
              +       'CURRENT_WORD,REMAINING_WORDS,S,PROP' )   :(MAIN_END)
          237 MAIN
          238         COLLECT()
          239         NULL(SENTENCES)                           :S(RETURN)
          240         S = TOP(SENTENCES)
          241         SENTENCES = REST(SENTENCES)
          242         ( PRT() PRT() )
          243         PRT(DUPL('-',SIZE(S)))
          244         ( PRT() PRT(S) PRT() )
          245         PRT(DUPL('-',SIZE(S)))
          246         PRT()
          247         LAST_PARSED = null
          248         CURRENT_WORD = null
          249         REMAINING_WORDS = S BLANK
          250         PROP = TABLE()
          251         TIME_ZERO = TIME()
          252         EVAL(FIRST_PROC)                          :S(MAIN1)
          253         ( PRT() PRT('Parsing failed') PRT() )     :(MAIN)
              *
          254 MAIN1
          255         ( PRT() PRT('Parsing Succeeded') PRT() )
          256        ( PRT(TIME() - TIME_ZERO ' milliseconds used') PRT() )
          257         DUMP_PROP()                          :(MAIN)
          258 MAIN_END
              *
              * Dump registers after parse is completed
              *
          259         DEFINE( 'DUMP_PROP()T,N,R,M,TN1,TN2,RM1,RM2' )
              +             :(DUMP_PROP_END)
          260 DUMP_PROP
          261         T = CONVERT(PROP, 'ARRAY')                :F(RETURN)
          262         PROP = null
          263         N = 1
              *
          264 DUMP1
          265         TN1 = T<N,1>                              :F(RETURN)
          266         TN2 = T<N,2>
          267         T<N,1> = null
          268         T<N,2> = null
          269         R = CONVERT(TN2, 'ARRAY')                 :F(DUMP3)
          270         PRT()
          271         PRT( 'NODE: ' TN1 )
          272         M = 1
              *
          273 DUMP2
          274           RM1 = R<M,1>                            :F(DUMP3)
          275           RM2 = R<M,2>
          276           PRT( DUPL(' ',10) RM1 ' = ' RM2 )
          277           M = M + 1                               :(DUMP2)



       AI Programming in SNOBOL4       - 79 -                    August, 1982








              *
          278 DUMP3
          279         N = N + 1                                 :(DUMP1)
          280 DUMP_PROP_END
              *
              *
              * Compile main program starts here
              *
          281         REWIND(1)
          282         REWIND(2)
          283         COMPILE()                                 :S(END)
          284         ERROR('****** FATAL ERROR ******')
          285 END

                             SAMPLE PROGRAMMING SESSION

          **********************************
           NETWORK PARSE_CLAUSE
          **********************************
                  S1
                      IF PARSE_NOUN_GROUP(THIS_NODE) GOTO S2
                    AFTER SETR('SUBJECT',LAST_PARSED)
                      ENDIF
                  END S1
          **********************************
                  S2
                      IF PARSE_WORD(THIS_NODE,'VERB TENSED ') GOTO S3
                    AFTER SETR('VERB',LAST_PARSED)
                      ENDIF
                  END S2
          **********************************
                  S3
                      IF TESTF(LAST_PARSED,'BE ')
                    PARSE_WORD(THIS_NODE,'PASTPARTICIPLE ') GOTO S4
                    AFTER     SETR('OBJECT',GETR('SUBJECT'))
                         SETR('SUBJECT')
                         SETR('VERB',LAST_PARSED)
                      ENDIF
                      IF TESTF(GETR('VERB'),'TRANSITIVE ')
                    PARSE_NOUN_GROUP(THIS_NODE) GOTO S4
                    AFTER SETR('OBJECT',LAST_PARSED)
                      ENDIF
                      IF TESTF(GETR('VERB'),'INTRANSITIVE ') GOTO S4 ENDIF
                      IF ~NULL(GETR('OBJECT')) GOTO S4 ENDIF
                  END S3
          **********************************
                  S4
                      IF ~NULL(GETR('SUBJECT'))
                    NULL(REMAINING_WORDS) GOTO WIN
                      ENDIF
                      IF NULL(GETR('SUBJECT'))
                    IDENT(CURRENT_WORD,'BY')
                    PARSE_WORD(THIS_NODE) GOTO S5
                      ENDIF



       AI Programming in SNOBOL4       - 80 -                    August, 1982








                      IF NULL(GETR('SUBJECT')) GOTO S4
                    AFTER SETR('SUBJECT','SOMEONE')
                      ENDIF
                  END S4
          **********************************
                  S5
                      IF PARSE_NOUN_GROUP(THIS_NODE) GOTO S4
                    AFTER SETR('SUBJECT',LAST_PARSED)
                      ENDIF
                  END S5
           END PARSE_CLAUSE


          1550 milliseconds compile time


          **********************************
           NETWORK PARSE_NOUN_GROUP
          **********************************
                  S1
                      IF PARSE_WORD(THIS_NODE,'DETERMINER ') GOTO S2
                    AFTER SETR('NUMBER',
                            SELECT('SINGULAR PLURAL ',
                                GETF(LAST_PARSED)))
                          SETR('DETERMINER',
                            SELECT('DEFINITE INDEFINITE ',
                                GETF(LAST_PARSED)))
                      ENDIF
                  END S1
          **********************************
                  S2
                      IF PARSE_WORD(THIS_NODE,'ADJECTIVE ') GOTO S2
                     AFTER ADDR('ADJECTIVES',LAST_PARSED)
                      ENDIF
                      IF PARSE_WORD(THIS_NODE,'NOUN ') GOTO WIN
                     AFTER SETR('NUMBER',
                             SELECT('SINGULAR PLURAL ',
                                 GETF(LAST_PARSED)))
                           SETR('NOUN',LAST_PARSED)
                      ENDIF
                  END S2
           END PARSE_NOUN_GROUP

          433 milliseconds compile time


          **********************************
           NETWORK PARSE_WORD
                  S1
                      IF NULL(null) GOTO WIN
                    AFTER PARSE_WORD_1()
                      ENDIF
                  END S1
           END PARSE_WORD



       AI Programming in SNOBOL4       - 81 -                    August, 1982









          183 milliseconds compile time


          **********************************
           FUNCTION PARSE_WORD_1 () ()
                  THIS_NODE = CURRENT_WORD ;
                  REMAINING_WORDS BREAK(" ") SPAN(" ") = ;
                  REMAINING_WORDS (BREAK(" ") | null) $ CURRENT_WORD  :(RET
          URN) ;
           END PARSE_WORD_1

          33 milliseconds compile time


          **********************************
           FUNCTION SETR (REGISTER,VALUE) ()
                  PUT(THIS_NODE,VALUE,REGISTER)        :(RETURN) ;
           END SETR

          17 milliseconds compile time


          **********************************
           FUNCTION GETR (REGISTER) ()
                  GETR = GET(THIS_NODE,REGISTER)       :(RETURN) ;
           END GETR

          17 milliseconds compile time


          **********************************
           FUNCTION ADDR (REGISTER,VALUE) ()
                  SETR(REGISTER,GETR(REGISTER) VALUE " ")   :(RETURN) ;
           END ADDR

          17 milliseconds compile time


          **********************************
           FUNCTION GENNAME (X) ()
                  GENNAME =
                      '*' X '_' STATEMENTS(0) '*'
                    :(RETURN) ;
           END GENNAME

          17 milliseconds compile time


          **********************************
           FUNCTION ATTACH (C,P) ()
                  PUT(C,P,'PARENT') ;
                  PUT(P,GET(P,'CHILDREN') C " ",'CHILDREN')
                    :(RETURN) ;



       AI Programming in SNOBOL4       - 82 -                    August, 1982








           END ATTACH

          17 milliseconds compile time


          **********************************
           FUNCTION SELECT (S,T) ()
                  S (BREAK(" ") $ SELECT) SPAN(" ") =  :F(FRETURN) ;
                  T (POS(0) | " ") SELECT " "
                    :S(RETURN)F(SELECT) ;
           END SELECT

          33 milliseconds compile time


          **********************************
           FUNCTION TESTF (X,F) (W,G)
                  NULL(F)          :S(RETURN) ;
                  G = GETF(X) ;
          TESTF1
                  F (BREAK(" ") $ W) SPAN(" ") =  :F(RETURN) ;
                  G (POS(0) | " ") W " "     :S(TESTF)F(FRETURN) ;
           END TESTF

          34 milliseconds compile time


          **********************************
           FUNCTION GETF (X) ()
                  GETF = LEXICAL_FEATURES<X> :(RETURN) ;
           END GETF

          17 milliseconds compile time


          **********************************
           LEXICON L1
                  <* >NOUN >SINGULAR BLOCK BOY
                  <* >DETERMINER >SINGULAR >INDEFINITE A
                           <SINGULAR >DEFINITE THE
                  <* >VERB >TENSED >TRANSITIVE >INTRANSITIVE
          >PASTPARTICIPLE DROPPED
                     <TENSED >BE WAS
                  <* >ADJECTIVE BIG RED
                  <* >PREPOSITION BY
                  <*
           END L1
               | BLOCK:  NOUN SINGULAR
               | BOY:  NOUN SINGULAR
               | A:  DETERMINER SINGULAR INDEFINITE
               | THE:  DETERMINER SINGULAR DEFINITE
               | DROPPED:  VERB TENSED TRANSITIVE INTRANSITIVE
          PASTPARTICIPLE
               | WAS:  VERB TENSED BE



       AI Programming in SNOBOL4       - 83 -                    August, 1982








               | BIG:  ADJECTIVE
               | RED:  ADJECTIVE
               | BY:  PREPOSITION

          84 milliseconds compile time


          **********************************
           SENTENCES S1
                  A BIG RED BLOCK WAS DROPPED BY THE BOY ;
                  THE BOY DROPPED A BIG RED BLOCK ;
                  A BLOCK WAS DROPPED ;
                  THE BLOCK DROPPED ;
           END S1

          0 milliseconds compile time


          **********************************
           EXEC PARSE_CLAUSE("SENTENCE",null)


          ****** EXECUTION BEGINS WITH PARSE_CLAUSE("SENTENCE",null) ******



          ------------------

          THE BLOCK DROPPED

          ------------------


          Parsing Succeeded

          150 milliseconds used


          NODE: SENTENCE
                    CHILDREN =

          NODE:
                    NUMBER = SINGULAR
                    CHILDREN = THE BLOCK  DROPPED
                    DETERMINER = DEFINITE
                    PARENT = SENTENCE
                    VERB = DROPPED
                    NOUN = BLOCK
                    SUBJECT = SOMEONE


          --------------------

          A BLOCK WAS DROPPED



       AI Programming in SNOBOL4       - 84 -                    August, 1982









          --------------------


          Parsing Succeeded

          150 milliseconds used


          NODE: SENTENCE
                    CHILDREN =

          NODE:
                    NUMBER = SINGULAR
                    CHILDREN = A BLOCK  WAS DROPPED
                    DETERMINER = INDEFINITE
                    PARENT = SENTENCE
                    VERB = DROPPED
                    NOUN = BLOCK
                    SUBJECT = SOMEONE


          --------------------------------

          THE BOY DROPPED A BIG RED BLOCK

          --------------------------------


          Parsing Succeeded

          267 milliseconds used


          NODE: SENTENCE
                    CHILDREN =

          NODE:
                    NUMBER = SINGULAR
                    CHILDREN = THE BOY  DROPPED A BIG RED BLOCK
                    DETERMINER = INDEFINITE
                    PARENT = SENTENCE
                    VERB = DROPPED
                    ADJECTIVES = BIG RED
                    NOUN = BLOCK
                    SUBJECT = SOMEONE


          ---------------------------------------

          A BIG RED BLOCK WAS DROPPED BY THE BOY

          ---------------------------------------




       AI Programming in SNOBOL4       - 85 -                    August, 1982









          Parsing Succeeded

          300 milliseconds used


          NODE: SENTENCE
                    CHILDREN =

          NODE:
                    NUMBER = SINGULAR
                    CHILDREN = A BIG RED BLOCK  WAS DROPPED BY THE BOY
                    DETERMINER = DEFINITE
                    PARENT = SENTENCE
                    VERB = DROPPED
                    ADJECTIVES = BIG RED
                    NOUN = BOY
                    SUBJECT = SOMEONE

          533 milliseconds compile time





































       AI Programming in SNOBOL4       - 86 -                    August, 1982