home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
snobol
/
aisnobol
/
report1.doc
< prev
next >
Wrap
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