Return to snocone.ms CVS log

Up to [Research Unix] / researchv10dc / vol2 / snocone

Annotation of researchv10dc/vol2/snocone/snocone.ms, revision 1.1

1.1     ! root        1: .so ../ADM/mac
        !             2: .XX snocone 297 "The Snocone Programming Language"
        !             3: .nr dP 2
        !             4: .nr dV 3p
        !             5: .EQ
        !             6: delim $$
        !             7: .EN
        !             8: .ds S4 \s-2SNOBOL4\s0
        !             9: .de Sx
        !            10: .P1 0
        !            11: ..
        !            12: .de Sy
        !            13: .P2
        !            14: ..
        !            15: .de Tx
        !            16: .IP "" 5
        !            17: ..
        !            18: .de Ty
        !            19: .PP
        !            20: ..
        !            21: .TL
        !            22: The Snocone Programming Language
        !            23: .AU
        !            24: Andrew Koenig
        !            25: .AI
        !            26: .MH
        !            27: .AB
        !            28: .PP
        !            29: \*(S4 is a well-known programming language with convenient
        !            30: semantics and clumsy syntax.
        !            31: Following the pattern of Ratfor and \s-2EFL\s0,
        !            32: we have added ``syntactic sugar'' to
        !            33: \*(S4, with an eye toward making it easier to use.
        !            34: We call the result
        !            35: .I Snocone.
        !            36: .PP
        !            37: This paper describes the Snocone language in enough
        !            38: detail that people not familiar with \*(S4 can
        !            39: learn to use it, although previous familiarity
        !            40: with \*(S4 will help.
        !            41: .AE
        !            42: .2C
        !            43: .NH 1
        !            44: Introduction
        !            45: .PP
        !            46: The semantics of the \*(S4 programming language |reference(poage griswold)
        !            47: include such unusual and useful
        !            48: features as
        !            49: dynamic typing,
        !            50: a general-purpose garbage collector,
        !            51: excellent character string facilities,
        !            52: associative arrays,
        !            53: and strong run-time diagnostics.
        !            54: Griswold|reference(snobol4 applications),
        !            55: Gimpel|reference(gimpel snobol4),
        !            56: and others have documented many ways of
        !            57: doing things in \*(S4 that can only be accomplished
        !            58: with much more difficulty in other languages.
        !            59: .PP
        !            60: Unfortunately, the control structures of
        !            61: \*(S4 are archaic, and the fact that
        !            62: blank is an operator tends to encourage certain types
        !            63: of errors that are hard to detect.
        !            64: Other aspects of the language make it a nuisance
        !            65: to construct large programs out of small parts.
        !            66: .PP
        !            67: To ameliorate some of these problems,
        !            68: we have designed and implemented a new language
        !            69: that provides some syntactic sugar for \*(S4.
        !            70: The obvious name for such a language is
        !            71: .I Snocone .
        !            72: .PP
        !            73: The design of the Snocone language was inspired by
        !            74: Ratfor|reference(kernighan ratfor)
        !            75: and \s-2EFL\s0|reference(efl cstr).
        !            76: Like \s-2EFL\s0, and unlike Ratfor, Snocone is a self-contained
        !            77: programming language, rather than a proper superset of
        !            78: \*(S4.
        !            79: Like Ratfor, and unlike \s-2EFL\s0, the Snocone translator
        !            80: makes no attempt to produce \*(S4 output that is
        !            81: easy for humans to understand.
        !            82: .PP
        !            83: Hanson|reference(ratsno)
        !            84: has written a similar, but simpler preprocessor
        !            85: for \*(S4.
        !            86: His preprocessor is like Ratfor
        !            87: in that it does not change the statements in
        !            88: the basic language but rather adds new syntax.
        !            89: .PP
        !            90: Griswold|reference(rebus)
        !            91: has written a preprocessor for a language
        !            92: similar to Snocone,
        !            93: the syntax of which is based on Icon|reference(icon language)
        !            94: rather than on C or \s-2EFL\s0.
        !            95: His preprocessor is written in C,
        !            96: and uses Yacc for its parsing.
        !            97: .PP
        !            98: In contrast, Snocone has a syntax roughly
        !            99: based on C and is written in Snocone.
        !           100: .SH
        !           101: What's nice about \*(S4
        !           102: .PP
        !           103: Variables in \*(S4 are dynamically typed:
        !           104: the type of any variable is the type of the
        !           105: value most recently assigned to it.
        !           106: Thus, declarations are unnecessary, and, in fact,
        !           107: \*(S4 has no declarations as such
        !           108: (except that procedures can have local variables).
        !           109: .PP
        !           110: All operators and built-in functions check
        !           111: their argument types;
        !           112: each argument is converted automatically
        !           113: to an appropriate type.
        !           114: A run-time diagnostic message results
        !           115: if a conversion is impossible.
        !           116: For instance, if an addend
        !           117: is a string, \*(S4 will try
        !           118: to convert it to an integer or real number,
        !           119: depending on the form of its value.
        !           120: If the value is inappropriate to convert to
        !           121: a numeric type, the program will halt.
        !           122: .PP
        !           123: Like Lisp, and unlike most other languages,
        !           124: \*(S4 does not have any explicit mechanism for
        !           125: returning memory to the system.
        !           126: Rather, the implementation must detect
        !           127: when memory is no
        !           128: longer needed and make that memory available
        !           129: for re-use.
        !           130: This makes the language harder to implement,
        !           131: but easier to use.
        !           132: One nice by-product of this sort of memory
        !           133: allocator is that \*(S4 programs tend
        !           134: to be free of arbitrary size limitations.
        !           135: .PP
        !           136: One \*(S4 data type is the
        !           137: .I pattern ,
        !           138: which describes an (arbitrarily complex)
        !           139: set of character strings.
        !           140: Briefly, the language incorporates a general
        !           141: top-down backtracking parser.
        !           142: This parser is so easy to use that it
        !           143: is the usual way of dealing with strings
        !           144: in \*(S4.
        !           145: .PP
        !           146: Another useful data type is the
        !           147: .I table .
        !           148: A table is like a one-dimensional array, except that
        !           149: its subscripts are not limited to being integers.
        !           150: For instance, a compiler symbol table might be maintained
        !           151: as a \*(S4 table, with the subscript being the identifier
        !           152: and the value being some structure which holds the desired
        !           153: information about that identifier.
        !           154: .PP
        !           155: An interesting and unusual semantic idea in \*(S4 is
        !           156: that of
        !           157: .I "statement failure" .
        !           158: Many operations can easily encounter conditions that
        !           159: preclude their execution.
        !           160: For example, an attempt may be made to access a non-existent
        !           161: array element, read beyond the last record of a file,
        !           162: search a string for a pattern that it does not contain,
        !           163: or even make a comparison that gives an unexpected result.
        !           164: When this happens, the operation
        !           165: .I fails .
        !           166: Usually, the failure of an operation implies the failure
        !           167: of the statement of which it is a part.
        !           168: While statement failure is not an error condition,
        !           169: it can be tested.
        !           170: In fact, conditional transfer on the success or
        !           171: failure of a statement is virtually the only
        !           172: kind of control structure in \*(S4.
        !           173: .PP
        !           174: A good implementation of \*(S4 is
        !           175: Macrospitbol, by Dewar and McCann|reference(spitbol).
        !           176: This is a portable threaded-code interpreter, which
        !           177: is fast and robust enough to be used for ``production''
        !           178: purposes.
        !           179: For example, on a VAX-11/780 it translates about 150
        !           180: statements per second and executes about 5,000.
        !           181: .PP
        !           182: \*(S4 implementations in general have excellent
        !           183: run-time diagnostic facilities.
        !           184: The language definition includes ways of tracing
        !           185: programs for debugging, and of trapping almost any
        !           186: kind of run-time error.
        !           187: .SH
        !           188: What's not nice about \*(S4
        !           189: .PP
        !           190: Here is a simple \*(S4 program to add the
        !           191: integers between 1 and 1000:
        !           192: .P1 0
        !           193:        sum = 0
        !           194:        term = 1
        !           195: loop   sum = sum + term
        !           196:        term = term + 1
        !           197:        LE(term,1000)           :s(loop)
        !           198:        OUTPUT = "The sum is " sum
        !           199: END
        !           200: .P2
        !           201: .PP
        !           202: The first two lines of this program assign values to
        !           203: variables.
        !           204: The name
        !           205: .CW loop
        !           206: in the third line is a label; it is recognized as such
        !           207: because it begins the line without any white space
        !           208: ahead of it.
        !           209: .PP
        !           210: The fifth line calls a built-in function to compare the
        !           211: value of the variable
        !           212: .CW term
        !           213: to 1000.
        !           214: \*(S4 has no comparison operators: all comparisons are
        !           215: done by
        !           216: .I predicate
        !           217: functions that either return the null string if the condition
        !           218: being tested is true or fail if the condition is false.
        !           219: The \f(CW:s(loop)\fP at the end of the line
        !           220: is a conditional
        !           221: .B "go to" :
        !           222: it causes control to transfer to the label
        !           223: .CW loop
        !           224: if the statement succeeds, and to the following
        !           225: statement if it fails.
        !           226: .PP
        !           227: In contrast, the program looks like this in Snocone:
        !           228: .P1 0
        !           229: sum = 0
        !           230: term = 1
        !           231: do {
        !           232:        sum = sum + term
        !           233:        term = term + 1
        !           234: } while (term <= 1000)
        !           235: OUTPUT = "The sum is " && sum
        !           236: .P2
        !           237: .PP
        !           238: In the past fifteen years, the trend in programming
        !           239: language design has been overwhelmingly toward
        !           240: programming languages with control structures that
        !           241: make it reasonable to write programs with at most
        !           242: a very few
        !           243: .B "go to"
        !           244: statements.
        !           245: \*(S4 exhibits almost the exact opposite of this trend:
        !           246: essentially the only control structure in \*(S4 is
        !           247: a form of conditional
        !           248: .B "go to"
        !           249: statement.
        !           250: There is no block structure, and all labels are global.
        !           251: Thus, writing a \*(S4 program requires a constant effort
        !           252: to invent new label names, and to choose names that have
        !           253: at least some chance of telling the reader whether their
        !           254: use is local or global.
        !           255: .PP
        !           256: The programmer's job is not made any easier by the peculiar way
        !           257: \*(S4 handles subroutines.
        !           258: \*(S4 subroutines are defined at run time by a built-in
        !           259: function called \f(CWDEFINE\fP.
        !           260: Its argument is a
        !           261: .I prototype
        !           262: of the subroutine to be defined \-
        !           263: a character string that describes how the
        !           264: subroutine is to be used.
        !           265: The subroutine's entry point is the label with the same name.
        !           266: Because the statement bearing this label is not special
        !           267: in any other way, it must be placed where it will not
        !           268: be executed in the ordinary course of events.
        !           269: The call to \f(CWDEFINE\fP, on the other hand, must
        !           270: be executed before the subroutine it defines can be used.
        !           271: .PP
        !           272: This leads \*(S4 programmers into contortions.
        !           273: To keep the \f(CWDEFINE\fP call near the subroutine body,
        !           274: one must invent yet another label:
        !           275: .P1 0
        !           276:         DEFINE("square(x)")    :(square.end)
        !           277: square  square = x * x         :(RETURN)
        !           278: square.end
        !           279: .P2
        !           280: Alternatively, one can put all the \f(CWDEFINE\fP calls
        !           281: in one place, at the cost of moving the body of each
        !           282: subroutine arbitrarily far from where its prototype appears.
        !           283: .PP
        !           284: The Snocone programmer has an easier job:
        !           285: .P1 0
        !           286: procedure square (x) {
        !           287:        return x * x
        !           288: }
        !           289: .P2
        !           290: .SH
        !           291: Motivation
        !           292: .PP
        !           293: Snocone's purpose, then, is to make it easy for a
        !           294: programmer used to a block-structured language like C
        !           295: to write programs that have the freedom and semantic flexibility
        !           296: of \*(S4.
        !           297: To this end, we have changed the \*(S4 language in several ways.
        !           298: .PP
        !           299: First, we introduced an explicit concatenation operator.
        !           300: \*(S4 uses blank for concatenation, so
        !           301: .P1 0
        !           302: y = f(x)
        !           303: .P2
        !           304: is a function call, but
        !           305: .P1 0
        !           306: y = f (x)
        !           307: .P2
        !           308: assigns to \f(CWy\fP the concatenation of the 
        !           309: values of the variables
        !           310: \f(CWf\fP and \f(CWx\fP.
        !           311: We chose \f(CW&&\fP to represent concatenation because
        !           312: \*(S4 programs often use concatenation for the same purpose
        !           313: that C programs use \f(CW&&\fP.
        !           314: .PP
        !           315: Second, we allow much the same freedom with spaces that
        !           316: C does, with one exception:  newline ends a statement.
        !           317: Statements may be continued onto multiple lines in much the
        !           318: same way as in \s-2EFL\s0 programs: a line is continued
        !           319: if it ends with an
        !           320: operator or some kind of open bracket.
        !           321: .PP
        !           322: Third, we have added procedure and structure declarations.
        !           323: These things are accomplished in \*(S4 by calling built-in
        !           324: subroutines, and the context of the calls is often obscure.
        !           325: .PP
        !           326: Finally, we have introduced control structures similar to
        !           327: those in C and other block-structured languages: the
        !           328: \f(CWif\fP, \f(CWwhile\fP, \f(CWfor\fP, and \f(CWdo\fP statements.
        !           329: .NH 1
        !           330: Language Description
        !           331: .NH 2
        !           332: Lexical Conventions
        !           333: .PP
        !           334: Blanks (spaces and tabs, but not newlines) may not appear within a
        !           335: token, but may freely separate tokens.
        !           336: Comments begin with a \f(CW#\fP
        !           337: character and end at the end of the line.
        !           338: .PP
        !           339: Constants may be integers, reals, or strings.
        !           340: There are no signed
        !           341: numeric constants.
        !           342: Integers range from 0 to $2 sup 31 - 1$.
        !           343: Real constants
        !           344: are short-precision only, and must contain either a decimal point or an
        !           345: \f(CWE\fP (or \f(CWe\fP).
        !           346: String constants may be delimited by single or double quotes
        !           347: with the same meaning.
        !           348: Characters in quotes receive no special
        !           349: interpretation.
        !           350: A single quote may appear in strings delimited by
        !           351: double quotes, and vice versa.
        !           352: .EQ
        !           353: delim off
        !           354: .EN
        !           355: .PP
        !           356: Identifiers may be of any length.
        !           357: All characters in an identifier are
        !           358: significant, but their case is presently not significant.
        !           359: Case may
        !           360: become significant in the future.
        !           361: An identifier is a non-empty
        !           362: sequence of letters and digits, beginning with a letter.
        !           363: Underscore
        !           364: (_) is a letter.
        !           365: The same identifier may be used independently to
        !           366: represent a procedure, label, or variable.
        !           367: .NH 2
        !           368: Statement Separation
        !           369: .PP
        !           370: Snocone delimits statements much like the Shell|reference(bstj shell)
        !           371: (the command interpreter in the
        !           372: .UX
        !           373: operating system)|reference(unix cacm ritchie thompson)
        !           374: or \s-2EFL\s0.
        !           375: A statement is
        !           376: ended either by a semicolon or newline, except that if the last token
        !           377: on a line is an operator or open parenthesis or bracket, the next line
        !           378: is automatically considered as part of the current statement.
        !           379: Newlines
        !           380: may also separate clauses of compound statements, so
        !           381: .P1 0
        !           382: if (a < 0)
        !           383:        a = 0
        !           384: .P2
        !           385: is acceptable and means the same as
        !           386: .P1 0
        !           387: if (a < 0) a = 0
        !           388: .P2
        !           389: or, spreading things as much as possible:
        !           390: .P1 0
        !           391: if (
        !           392: a <
        !           393: 0)
        !           394: a =
        !           395: 0
        !           396: .P2
        !           397: .NH 2
        !           398: File Inclusion
        !           399: .PP
        !           400: The contents of an arbitrary file can be incorporated into
        !           401: the program by writing an
        !           402: .I "include line"
        !           403: in one of the following four forms:
        !           404: .P1 0
        !           405: #include "\fIfile\fP"
        !           406: #include '\fIfile\fP'
        !           407: #include <\fIfile\fP>
        !           408: #include {\fIfile\fP}
        !           409: .P2
        !           410: Spaces may appear between \f(CW#\fP and \f(CWinclude\fP.
        !           411: The contents of the named file are substituted for
        !           412: the \f(CWinclude\fP line.
        !           413: .PP
        !           414: The exact behavior of an \f(CWinclude\fP line depends
        !           415: on the delimiters surrounding the file name.
        !           416: If quotes are used (single or double), the file is
        !           417: sought in the current directory.
        !           418: If brackets are used (angle brackets or curly braces),
        !           419: the file is sought in an installation-dependent
        !           420: system library
        !           421: (\f(CW/usr/lib/snocone\fP on our systems).
        !           422: If double quotes or angle brackets are used, the
        !           423: file is included unconditionally, even if the same
        !           424: file is included several times.
        !           425: If single quotes or curly braces are used,
        !           426: the file will only be included once, even if it
        !           427: is named in several \f(CWinclude\fP lines.
        !           428: .PP
        !           429: This latter behavior is useful in the following sort of situation.
        !           430: Suppose that procedure
        !           431: .I proc1
        !           432: is defined in
        !           433: file
        !           434: .I proc1.h ,
        !           435: and procedure
        !           436: .I proc2
        !           437: is defined
        !           438: in file
        !           439: .I proc2.h .
        !           440: A program that calls both
        !           441: .I proc1
        !           442: and
        !           443: .I proc2
        !           444: might then contain:
        !           445: .P1 0
        !           446: #include "proc1.h"
        !           447: #include "proc2.h"
        !           448: .P2
        !           449: Now, suppose that
        !           450: .I proc1
        !           451: is changed to call
        !           452: .I proc2 .
        !           453: If
        !           454: .I proc1.h
        !           455: is made to contain
        !           456: .P1 0
        !           457: #include "proc2.h"
        !           458: .P2
        !           459: then our hypothetical sample program will wind
        !           460: up with two copies of
        !           461: .I proc2.h
        !           462: and will therefore run into trouble with duplicate
        !           463: procedure definitions.
        !           464: If, however,
        !           465: .I proc1.h
        !           466: contains:
        !           467: .P1 0
        !           468: #include 'proc2.h'
        !           469: .P2
        !           470: and the main program contains:
        !           471: .P1 0
        !           472: #include 'proc1.h'
        !           473: #include 'proc2.h'
        !           474: .P2
        !           475: then
        !           476: .I proc2
        !           477: will be defined only once.
        !           478: .NH 2
        !           479: Expression Evaluation, Success, and Failure
        !           480: .PP
        !           481: Evaluating an expression has one of three
        !           482: outcomes: a value, failure, or error.
        !           483: .PP
        !           484: Errors normally result in a diagnostic message
        !           485: and termination of the program, and arise
        !           486: from the usual sorts of things:
        !           487: overflow, underflow,
        !           488: division by zero, impossible conversions,
        !           489: running out of memory, and so on.
        !           490: .PP
        !           491: Failure, on the other hand, is not an error
        !           492: condition.
        !           493: An expression that fails is merely one that
        !           494: does not yield a value.
        !           495: Examples of expressions that fail include
        !           496: attempts to refer to non-existent array
        !           497: elements,
        !           498: attempts to read beyond end of file,
        !           499: and even comparisons that yield unexpected results.
        !           500: For instance, the expression
        !           501: .P1 0
        !           502: a < b
        !           503: .P2
        !           504: yields a null string if \f(CWa\fP is indeed less than \f(CWb\fP,
        !           505: and fails otherwise.
        !           506: .PP
        !           507: Most operators fail if any of their operands fails.
        !           508: The few exceptions will be noted below.
        !           509: .PP
        !           510: An expression that always either yields a null string or fails
        !           511: is sometimes called a
        !           512: .I predicate .
        !           513: Testing such expressions for success or failure in \f(CWif\fP,
        !           514: \f(CWwhile\fP, and \f(CWdo\fP statements is the primary way
        !           515: of affecting the flow of control
        !           516: in Snocone.
        !           517: .NH 2
        !           518: Data Types, Declarations, and Scope
        !           519: .PP
        !           520: Variables in Snocone are dynamically typed: a variable has the type of
        !           521: the value most recently assigned to it.
        !           522: Except for a few predefined variables
        !           523: (described under
        !           524: .I "pattern matching" ),
        !           525: all variables have the null string as their initial values.
        !           526: All variables are global, but procedures
        !           527: can nominate variables whose
        !           528: values will automatically be saved at
        !           529: entry and restored at exit.
        !           530: The only declarations define
        !           531: structures:
        !           532: .P1 0
        !           533: struct cons {car, cdr}
        !           534: .P2
        !           535: In effect, this declaration defines three procedures named
        !           536: \f(CWcons\fP, 
        !           537: \f(CWcar\fP,
        !           538: and \f(CWcdr\fP.
        !           539: The value of \f(CWcons(a,b)\fP is a newly-created
        !           540: \f(CWcons\fP object with \f(CWa\fP and \f(CWb\fP
        !           541: as the values of its \f(CWcar\fP and \f(CWcdr\fP fields,
        !           542: respectively.
        !           543: The fields, in turn, are accessed by similarly-named
        !           544: functions.
        !           545: For instance, the \f(CWcdr\fP field of \f(CWcons\fP structure \f(CWx\fP
        !           546: is accessed as \f(CWcdr(x)\fP.
        !           547: Thus this program:
        !           548: .P1 0
        !           549: struct cons {car, cdr}
        !           550: a = cons (3, cons (4, 5))
        !           551: OUTPUT = car (cdr (a))
        !           552: .P2
        !           553: prints \f(CW4\fP.
        !           554: The procedures corresponding to field names may
        !           555: be used as the target of an assignment:
        !           556: .P1 0
        !           557: car (a) = "Hello"
        !           558: .P2
        !           559: Snocone offers other data types than those described above.
        !           560: While
        !           561: numeric constants cannot be negative, variables and expressions
        !           562: suffer from no such restriction.
        !           563: Strings may be of any length up
        !           564: to an implementation-defined upper bound, usually many thousands
        !           565: of characters.
        !           566: All variables have the null string as their
        !           567: initial value.
        !           568: .PP
        !           569: Aggregate values come in two types: arrays and tables.
        !           570: Each type
        !           571: is created by a built-in procedure with the same name.
        !           572: Thus:
        !           573: .P1 0
        !           574: a = ARRAY (20)
        !           575: .P2
        !           576: creates a 20-element array, initializes each element to the null
        !           577: string, and assigns it to a.
        !           578: The second argument to the array
        !           579: procedure is an initializing value:
        !           580: .P1 0
        !           581: a = ARRAY (20, -1)
        !           582: .P2
        !           583: makes a an array of 20 elements, each with value \-1.
        !           584: To get
        !           585: multi-dimensional arrays, express the dimensions as a string:
        !           586: .P1 0
        !           587: a = ARRAY ('4,5', -1)
        !           588: .P2
        !           589: One can also give explicit lower bounds:
        !           590: .P1 0
        !           591: a = ARRAY ('-10:10')
        !           592: .P2
        !           593: The default lower bound is 1.
        !           594: .PP
        !           595: Array elements are referenced by Algol-like subscripts:
        !           596: .P1 0
        !           597: a[i,j] = a[i,j] + b[i,k] * c[k,j]
        !           598: .P2
        !           599: Each array element behaves as a variable, and can therefore have
        !           600: a value of any data type, independently of any other element.
        !           601: .PP
        !           602: A table is like a one-dimensional array whose subscripts are not
        !           603: restricted to integers:
        !           604: .P1 0
        !           605: t = TABLE (20)
        !           606: .P2
        !           607: The argument to the \f(CWTABLE\fP procedure is an estimate of the maximum
        !           608: number of elements that will actually be stored in the table.
        !           609: If substantially more elements than
        !           610: this are stored, access will
        !           611: begin to slow down.
        !           612: On the other hand, giving too large an
        !           613: initial value wastes space.
        !           614: Once a table has been created, any
        !           615: value can be used for a subscript.
        !           616: \f(CWt[a]\fP and \f(CWt[b]\fP will refer to
        !           617: the same element if and only if a and b are identical.
        !           618: The
        !           619: precise meaning of ``identical'' is given with the description of
        !           620: the \f(CW::\fP and \f(CW:!:\fP operators;
        !           621: suffice it to say that \f(CW3\fP and \f(CW"3"\fP are
        !           622: not identical, and that after executing
        !           623: .P1 0
        !           624: a = b
        !           625: .P2
        !           626: \f(CWa\fP and \f(CWb\fP are
        !           627: identical regardless of what values they had before.
        !           628: .NH 2
        !           629: Binary Operators
        !           630: .PP
        !           631: The following operators are grouped in order of decreasing priority.
        !           632: Unless otherwise stated, they are left-associative.
        !           633: .IP "\f(CW. $\fP"
        !           634: Pattern value assignment (see Patterns)
        !           635: .IP "\f(CW^\fP"
        !           636: Exponentiation (right-associative).
        !           637: The right argument
        !           638: must be an integer.
        !           639: If both arguments are integers,
        !           640: the right argument must be non-negative
        !           641: .IP "\f(CW* / %\fP"
        !           642: .br
        !           643: Multiplication, division, and remainder.
        !           644: As in C,
        !           645: and as not in \*(S4, multiplication and
        !           646: division have the same precedence.
        !           647: .IP "\f(CW+ -\fP"
        !           648: Addition and subtraction.
        !           649: .IP "\f(CW== != < > <= >= :==: :!=:\fP"
        !           650: .IP "\f(CW:<: :>: :<=: :>=: :: :!:\fP"
        !           651: .br
        !           652: Comparison predicates.
        !           653: Each of these operators returns
        !           654: a null string if the indicated relation holds,
        !           655: and fails if not.
        !           656: The first six do
        !           657: numeric comparisons: an error results if either
        !           658: operand cannot be converted to a number.
        !           659: The next six do string comparisons: an error results
        !           660: if either operand cannot be converted to a string.
        !           661: The last two test if the two operands are identical.
        !           662: Values of different data types are never identical.
        !           663: Strings and numbers are identical if their data types and values match.
        !           664: Other values are identical if they refer to the same object.
        !           665: .IP "\f(CW&&\fP"
        !           666: Concatenation.
        !           667: The left operand is evaluated
        !           668: first; if its evaluation fails, the \f(CW&&\fP operator fails.
        !           669: Otherwise, the right operand is
        !           670: evaluated, and \f(CW&&\fP fails if the right operand fails.
        !           671: If either operand is the null string, the
        !           672: result is the other operand, even if that operand is not a string.
        !           673: Otherwise, both operands are
        !           674: converted to strings and the result is their concatenation.
        !           675: An error results if either
        !           676: operand cannot be converted to a string.
        !           677: Note that if the operands of \f(CW&&\fP are predicates,
        !           678: \f(CW&&\fP can be used as a kind of logical conjunction.
        !           679: .IP "\f(CW||\fP"
        !           680: Logical disjunction.
        !           681: The left operand is evaluated first; if it
        !           682: succeeds, its value is the value of \f(CW||\fP.
        !           683: Otherwise, the value is that of the right operand.
        !           684: If both operands fail, \f(CW||\fP fails.
        !           685: .IP "\f(CW|\fP"
        !           686: Pattern alternation.
        !           687: See
        !           688: .I "pattern matching"
        !           689: for details.
        !           690: .IP "\f(CW=\fP"
        !           691: Assignment.
        !           692: This operator is right-associative.
        !           693: .IP "\f(CW?\fP"
        !           694: Pattern match operator.
        !           695: The left operand is
        !           696: converted to a string and searched for the first
        !           697: substring that matches the pattern given by the right operand.
        !           698: If no such substring is found, the operator fails.
        !           699: If the left operand is a variable, \f(CW?\fP may be used on the left
        !           700: side of an assignment.
        !           701: .NH 2
        !           702: Unary Operators
        !           703: .PP
        !           704: Unary operators bind more tightly than all binary
        !           705: operators.
        !           706: .IP "\f(CW+ -\fP"
        !           707: Unary plus and minus.
        !           708: The result is always
        !           709: numeric, so unary plus is sometimes used for type conversion.
        !           710: Because unary operators bind so tightly, expressions that look like negative
        !           711: constants behave that way for all practical purposes.
        !           712: .IP "\f(CW.\fP"
        !           713: Name operator.
        !           714: The operand must be a variable;
        !           715: the result is essentially a pointer to the variable, similarly
        !           716: to the unary & operator in C.
        !           717: The result of applying the \f(CWDATATYPE\fP function
        !           718: to the result of the \f(CW.\fP operator is the string \f(CW"NAME"\fP.
        !           719: .IP "\f(CW$\fP"
        !           720: Indirection.
        !           721: The operand is converted to a name;
        !           722: the result is the object thus named.
        !           723: \f(CW$\fP always yields an lvalue.
        !           724: .IP "\f(CW?\fP"
        !           725: Query.
        !           726: If its operand fails, \f(CW?\fP fails.
        !           727: If its operand succeeds, \f(CW?\fP yields a null string.
        !           728: Useful for evaluating an expression solely for
        !           729: its side effects.
        !           730: .IP "\f(CW~\fP"
        !           731: Logical negation.
        !           732: If its operand fails, \f(CW~\fP yields a null string.
        !           733: If the operand succeeds, \f(CW~\fP fails.
        !           734: .IP "\f(CW&\fP"
        !           735: Keyword value.
        !           736: The operand must be the name of one of a restricted set of variables.
        !           737: The lvalue result is a system variable, whose value affects the
        !           738: execution of the program in some way.
        !           739: System variables are discussed separately.
        !           740: .IP "\f(CW@\fP"
        !           741: Pattern cursor assignment.
        !           742: See
        !           743: .I "pattern matching"
        !           744: for details.
        !           745: .IP "\f(CW*\fP"
        !           746: Deferred evaluation.
        !           747: Returns a value of type \f(CWEXPRESSION\fP that
        !           748: contains all the information necessary to evaluate the operand.
        !           749: The operand is not actually evaluated at this time, but can be
        !           750: evaluated later,
        !           751: either by the \f(CWEVAL\fP procedure or implicitly during pattern matching.
        !           752: .NH 2
        !           753: Statements
        !           754: .PP
        !           755: Elements in brackets are optional.
        !           756: If the description of a statement
        !           757: is split over more than one line, the statement itself may be split
        !           758: analogously.
        !           759: Snocone does not have a null statement.
        !           760: .Sx
        !           761: \fIexpression\fP
        !           762: .Sy
        !           763: .Tx
        !           764: The expression is evaluated for its side effects.
        !           765: The result, if any, is discarded.
        !           766: .Tm if S
        !           767: .Ty
        !           768: .Sx
        !           769: if (\fIexpression\fP)
        !           770:        \fIstatement1\fP
        !           771: [ else
        !           772:        \fIstatement2\fP ]
        !           773: .Sy
        !           774: .Tx
        !           775: The parenthesized
        !           776: .I expression
        !           777: is evaluated.
        !           778: If it
        !           779: succeeds,
        !           780: .I statement1
        !           781: is executed, otherwise
        !           782: .I statement2
        !           783: is executed.
        !           784: .Ty
        !           785: .Sx
        !           786: while (\fIexpression\fP)
        !           787:        \fIstatement\fP
        !           788: .Sy
        !           789: .Tx
        !           790: Behaves similarly to C: the
        !           791: .I expression
        !           792: is evaluated,
        !           793: and if it succeeds, the
        !           794: .I statement
        !           795: is executed and
        !           796: control passes back to the beginning of the \f(CWwhile\fP
        !           797: statement.
        !           798: Unlike C, Snocone has no
        !           799: .I break
        !           800: or
        !           801: .I continue
        !           802: statements.
        !           803: .Ty
        !           804: .Sx
        !           805: do
        !           806:        \fIstatement\fP
        !           807: while (\fIexpression\fP)
        !           808: .Sy
        !           809: .Tx
        !           810: Behaves similarly to C: the
        !           811: .I "statement"
        !           812: is executed, then the
        !           813: .I expression
        !           814: is evaluated, and if the
        !           815: .I expression
        !           816: succeeds, control passes back to the beginning of the \f(CWdo\fP
        !           817: statement.
        !           818: .Tm for        S
        !           819: .Ty
        !           820: .Sx
        !           821: for (\fIexpression1\fP, \fIexpression2\fP, \fIexpression3\fP)
        !           822:        \fIstatement\fP
        !           823: .Sy
        !           824: .Tx
        !           825: Equivalent to:
        !           826: .P1 0
        !           827: \fIexpression1\fP
        !           828: while (\fIexpression3\fP) {
        !           829:        \fIstatement\fP
        !           830:        \fIexpression2\fP
        !           831: }
        !           832: .P2
        !           833: .Ty
        !           834: .Sx
        !           835: {
        !           836:        \fIstatement list\fP
        !           837: }
        !           838: .Sy
        !           839: .Tx
        !           840: The statements in the list, which may contain zero or
        !           841: more statements, are executed in sequence.
        !           842: .Ty
        !           843: .Sx
        !           844: \fIlabel\fP: \fIstatement\fP
        !           845: .Sy
        !           846: .Tx
        !           847: All labels are global (because all \*(S4
        !           848: labels are global), even across procedure boundaries,
        !           849: so they must be chosen with care.
        !           850: A useful convention is
        !           851: to begin a label inside a procedure body with the name
        !           852: of the procedure and an underscore.
        !           853: .Ty
        !           854: .Sx
        !           855: go to \fIlabel\fP
        !           856: .Sy
        !           857: .Tx
        !           858: The space between \f(CWgo\fP and \f(CWto\fP is optional.
        !           859: It is wise
        !           860: not to jump from a point inside one procedure into another.
        !           861: Program
        !           862: execution may be terminated by jumping to the reserved
        !           863: label \f(CWEND\fP.
        !           864: Labels \f(CWRETURN\fP, \f(CWFRETURN\fP, \f(CWNRETURN\fP, \f(CWABORT\fP, and
        !           865: \f(CWCONTINUE\fP are also reserved.
        !           866: .Ty
        !           867: .Sx
        !           868: return [ \fIexpression\fP ]
        !           869: .Sy
        !           870: .Tx
        !           871: The current procedure returns to its caller.
        !           872: If the
        !           873: .I expression
        !           874: is given, the procedure yields that value.
        !           875: If no
        !           876: .I expression
        !           877: is given, the value returned is that of
        !           878: the variable with the same name as the procedure; if
        !           879: that variable was not assigned in the procedure, the
        !           880: null string is returned.
        !           881: .Ty
        !           882: .Sx
        !           883: freturn
        !           884: .Sy
        !           885: .Tx
        !           886: The current procedure returns and fails.
        !           887: .Ty
        !           888: .Sx
        !           889: nreturn [ \fIexpression\fP ]
        !           890: .Sy
        !           891: .Tx
        !           892: The current procedure returns \f(CW$(\fP\fIexpression\fP\f(CW)\fP as an
        !           893: lvalue.
        !           894: If the
        !           895: .I expression
        !           896: is not given, the indirection
        !           897: is applied to the variable with the same name as the
        !           898: procedure.
        !           899: An error results if this variable was not
        !           900: given a value inside the procedure.
        !           901: .NH 2
        !           902: Procedures
        !           903: .PP
        !           904: Here is an example of a procedure declaration:
        !           905: .P1 0
        !           906: procedure gcd (m, n) {
        !           907:        while (m != n) {
        !           908:                if (m > n)
        !           909:                        m = m % n
        !           910:                else
        !           911:                        n = n % m
        !           912:        }
        !           913:        return m
        !           914: }
        !           915: .P2
        !           916: .PP
        !           917: Arguments are passed by value, but note that the value passed for
        !           918: an aggregate argument (array, table, or structure) is really a
        !           919: pointer to the aggregate itself.
        !           920: .PP
        !           921: If a procedure is called with too few arguments, extra null strings
        !           922: are supplied as necessary.
        !           923: If called with too many arguments, the extras
        !           924: are quietly ignored.
        !           925: .PP
        !           926: Local variables can be nominated for a procedure:
        !           927: .P1 0
        !           928: procedure f(x) y, z {...
        !           929: .P2
        !           930: All variables are global, but name scoping is dynamic.
        !           931: One way to look
        !           932: at it is to imagine that when a procedure
        !           933: is entered, all the variables defined in that procedure are saved and
        !           934: set to null.
        !           935: Those variables are then restored when the procedure returns.
        !           936: .PP
        !           937: Thus, the following example prints 5 and then 1:
        !           938: .P1 0
        !           939: a = 1
        !           940: f()
        !           941: g()
        !           942: 
        !           943: procedure f() a {
        !           944:        a = 5
        !           945:        g()
        !           946: }
        !           947: 
        !           948: procedure g() {
        !           949:        OUTPUT = a
        !           950: }
        !           951: .P2
        !           952: The following example also prints 5 and then 1:
        !           953: .P1 0
        !           954: a = 1
        !           955: b = .a
        !           956: f()
        !           957: g()
        !           958: .P3
        !           959: procedure f() a {
        !           960:        a = 5
        !           961:        g()
        !           962: }
        !           963: .P3
        !           964: procedure g() {
        !           965:        OUTPUT = $b
        !           966: }
        !           967: .P2
        !           968: Local variables can only be associated with procedures.
        !           969: Procedures are
        !           970: recursive.
        !           971: .NH 2
        !           972: Input-Output
        !           973: .PP
        !           974: All I/O is done through ``associated variables''.
        !           975: A variable may be
        !           976: input-associated or output-associated (or both).
        !           977: Whenever a value is
        !           978: assigned to an output-associated variable, that value is automatically
        !           979: written in the file associated with that variable.
        !           980: Whenever a value
        !           981: is requested for an input-associated variable, a line is read from the
        !           982: file associated with that variable, and the contents of the line are
        !           983: used for the value.
        !           984: When the end of an input file is reached,
        !           985: any attempts to access variables associated
        !           986: with that file will fail.
        !           987: .PP
        !           988: Initially, the variable \f(CWOUTPUT\fP is output-associated with the standard
        !           989: output file, the variable \f(CWINPUT\fP is input-associated with the standard
        !           990: input file, and the variable \f(CWTERMINAL\fP is both input-
        !           991: and output-associated
        !           992: with the user's terminal.
        !           993: .PP
        !           994: Thus, the following program copies its standard
        !           995: input to its standard output, a line at a time:
        !           996: .P1 0
        !           997: while (OUTPUT = INPUT) {}
        !           998: .P2
        !           999: .PP
        !          1000: New associations are formed by the \f(CWINPUT\fP
        !          1001: and \f(CWOUTPUT\fP procedures:
        !          1002: .P1 0
        !          1003: INPUT  (\fIname\fP, \fIchannel\fP, \fIfile\fP)
        !          1004: OUTPUT (\fIname\fP, \fIchannel\fP, \fIfile\fP)
        !          1005: .P2
        !          1006: In both cases, 
        !          1007: .I name
        !          1008: is the name of the variable to be associated (the
        !          1009: name of the variable
        !          1010: .I x
        !          1011: is \f(CW.x\fP), and
        !          1012: .I file
        !          1013: is the file to be used.
        !          1014: .I Channel
        !          1015: is a string that you will use to identify subsequent operations
        !          1016: on that file.
        !          1017: Internally, there is a one-to-one correspondence between
        !          1018: channel names and file descriptors.
        !          1019: .PP
        !          1020: The file argument must not be given for other than the first call to
        !          1021: \f(CWINPUT\fP or \f(CWOUTPUT\fP on a given channel, as a channel can only be
        !          1022: connected to a single file.
        !          1023: .PP
        !          1024: Other procedures dealing with input-output are:
        !          1025: .Tm SET        S
        !          1026: .Sx
        !          1027: SET (\fIchannel\fP, \fIoffset\fP, \fIwhence\fP)
        !          1028: .Sy
        !          1029: .Tx
        !          1030: This function repositions the file specified by its
        !          1031: first argument in a system-dependent manner.
        !          1032: In implementations running under the
        !          1033: .UX
        !          1034: system, the behavior is similar to the
        !          1035: .I lseek
        !          1036: system call.
        !          1037: .Ty
        !          1038: .Sx
        !          1039: REWIND (\fIchannel\fP)
        !          1040: .Sy
        !          1041: .Tx
        !          1042: Repositions the named channel to the beginning of the file.
        !          1043: .Ty
        !          1044: .Sx
        !          1045: ENDFILE (\fIchannel\fP)
        !          1046: .Sy
        !          1047: .Tx
        !          1048: Indicates that you are done using the given channel.
        !          1049: All variables associated through that channel are
        !          1050: disassociated, output buffers are flushed (if any),
        !          1051: and the file is closed.
        !          1052: .Ty
        !          1053: .Sx
        !          1054: DETACH (\fIname\fP)
        !          1055: .Sy
        !          1056: .Tx
        !          1057: Disassociates the named variable.
        !          1058: Does not close
        !          1059: the file: a later call to \f(CWINPUT\fP or \f(CWOUTPUT\fP can reassociate it.
        !          1060: .NH 2
        !          1061: Pattern Matching
        !          1062: .PP
        !          1063: A
        !          1064: .I pattern
        !          1065: is a data structure that describes a class of strings.
        !          1066: Patterns
        !          1067: are used by the \f(CW?\fP operator,
        !          1068: which determines if the string given as its
        !          1069: left operand contains a substring described by the pattern given as its
        !          1070: right operand.
        !          1071: The part of the Snocone system that
        !          1072: does this is called the
        !          1073: .I scanner .
        !          1074: The input to the scanner is the string to be searched,
        !          1075: called the
        !          1076: .I subject ,
        !          1077: and the pattern sought.
        !          1078: .PP
        !          1079: The scanner tries to find a substring of the
        !          1080: subject that is matched by the pattern.
        !          1081: It first looks at substrings starting at
        !          1082: the first character of the subject.
        !          1083: If it doesn't find one, it tries the ones
        !          1084: starting at the second subject character,
        !          1085: and so on.
        !          1086: If the scanner cannot find an appropriate
        !          1087: substring, the pattern match fails.
        !          1088: .PP
        !          1089: If the \f(CW&ANCHOR\fP system variable is
        !          1090: nonzero, the scanner only looks at substrings
        !          1091: that start at the first character of the
        !          1092: subject.
        !          1093: This is said to be an
        !          1094: .I anchored
        !          1095: pattern match.
        !          1096: The \f(CW&ANCHOR\fP variable is zero at the
        !          1097: start of program execution.
        !          1098: .PP
        !          1099: The important part of pattern matching is therefore
        !          1100: determining whether the subject contains a
        !          1101: substring that starts at a given character
        !          1102: and matches a given pattern.
        !          1103: To understand how this is done, we must
        !          1104: take a closer look at patterns.
        !          1105: .PP
        !          1106: Every pattern is a concatenation of one or more
        !          1107: .I elements ,
        !          1108: each of which has zero or more
        !          1109: .I alternatives .
        !          1110: Each alternative may itself be an arbitrarily complicated pattern.
        !          1111: Some patterns have alternatives that are determined
        !          1112: dynamically as they are needed during pattern matching.
        !          1113: .PP
        !          1114: If a pattern has only one element, the scanner determines
        !          1115: if it matches at a given point by trying to match each
        !          1116: of the pattern's alternatives at that point.
        !          1117: If no alternative matches at that point, the element
        !          1118: cannot be matched.
        !          1119: .PP
        !          1120: If the pattern has more than one element,
        !          1121: matching that pattern at a given point means:
        !          1122: (a) finding an alternative for the first element
        !          1123: of the pattern that matches a subject substring
        !          1124: starting at the given point, and that also (b) allows
        !          1125: the remaining elements of the pattern to match
        !          1126: a substring that starts immediately after the
        !          1127: substring matched in (a).
        !          1128: .PP
        !          1129: During pattern matching, the scanner keeps its place
        !          1130: by means of an internal value called the
        !          1131: .I cursor ,
        !          1132: which represents the number of characters in the
        !          1133: subject that precede the current location.
        !          1134: These characters are counted from the beginning
        !          1135: of the subject even when the scanner is trying
        !          1136: to match a substring that starts at some other place
        !          1137: in the subject.
        !          1138: .PP
        !          1139: The concatenation of two patterns \f(CWP1\fP and \f(CWP2\fP
        !          1140: is a pattern whose elements
        !          1141: are \f(CWP1\fP and \f(CWP2\fP.
        !          1142: The alternation operator \f(CW|\fP similarly constructs alternatives.
        !          1143: When a string is used as a pattern, it matches only itself.
        !          1144: Thus,
        !          1145: .P1 0
        !          1146: "a" | "e" | "i" | "o" | "u"
        !          1147: .P2
        !          1148: is a pattern that matches any lower-case vowel.
        !          1149: .PP
        !          1150: Consider the following
        !          1151: statement:
        !          1152: .P1 0
        !          1153: P1 = ("ab" | "a") && ("b" | "c")
        !          1154: .P2
        !          1155: This assigns to \f(CWP\fP a pattern with two elements.
        !          1156: The first one matches
        !          1157: either \f(CWab\fP or \f(CWa\fP, and the second matches either
        !          1158: \f(CWb\fP or \f(CWc\fP.
        !          1159: Look at:
        !          1160: .P1 0
        !          1161: "ab" ? P1
        !          1162: .P2
        !          1163: The scanner first tries the first alternative of the first element of
        !          1164: P1 by matching \f(CWab\fP in the subject with \f(CWab\fP in the pattern.
        !          1165: This alternative matches, so the element (\f(CW"ab"|"a"\fP) matches, and
        !          1166: the scanner goes on to the second element (\f(CW"b"|"c"\fP).
        !          1167: Here, it will be unsuccessful
        !          1168: in matching both \f(CWb\fP and \f(CWc\fP,
        !          1169: because it has already exhausted all the
        !          1170: characters of the subject.
        !          1171: Thus the scanner fails to match the second element of
        !          1172: \f(CWP1\fP, and must back up and rematch the first element.
        !          1173: Fortunately, the
        !          1174: first element has an alternative in \f(CWa\fP;
        !          1175: this matches, and now the scanner
        !          1176: can try to match the second element (\f(CW"b"|"c"\fP) again.
        !          1177: The first alternative (\f(CWb\fP) succeeds, so
        !          1178: the \f(CW?\fP operator therefore succeeds.
        !          1179: If we wanted to examine just how the pattern elements matched,
        !          1180: we could have written:
        !          1181: .P1 0
        !          1182: P1a = ("ab"|"a").OUTPUT && ("b"|"c").OUTPUT
        !          1183: "ab" ? P1a
        !          1184: .P2
        !          1185: This would print \f(CWa\fP and \f(CWb\fP on separate lines,
        !          1186: showing that \f(CW"ab"|"a"\fP matched \f(CWa\fP and
        !          1187: \f(CW"b"|"c"\fP matched \f(CWb\fP.
        !          1188: .PP
        !          1189: When any pattern is first encountered
        !          1190: during pattern matching, it will match some string, and when the scanner
        !          1191: backs into it, it may match some other string.
        !          1192: Because many patterns behave
        !          1193: differently on their initial match than when rematched, it is useful to
        !          1194: describe the two cases separately.
        !          1195: .PP
        !          1196: For instance, when a string is used as a pattern, it initially matches
        !          1197: itself.
        !          1198: If the scanner later backs into it, it fails.
        !          1199: .PP
        !          1200: As another example, consider \f(CWP1|P2\fP.
        !          1201: This pattern matches every
        !          1202: possibility for \f(CWP1\fP, and when it has exhausted \f(CWP1\fP,
        !          1203: then matches every
        !          1204: possibility for \f(CWP2\fP before finally failing.
        !          1205: .PP
        !          1206: With this in mind, we can describe the various pattern-matching operators,
        !          1207: procedures, and pre-defined variables:
        !          1208: .IP "\f(CWP1 && P2\fP" 10
        !          1209: Tries to match \f(CWP1\fP, fails if it can't.
        !          1210: Then tries to match \f(CWP2\fP.
        !          1211: If \f(CWP2\fP fails, tries the next alternative for
        !          1212: \f(CWP1\fP, and then tries \f(CWP2\fP again.
        !          1213: Eventually, it either
        !          1214: runs out of alternatives for \f(CWP1\fP, in which case \f(CWP1&&P2\fP
        !          1215: fails, or it finds alternatives for both \f(CWP1\fP and \f(CWP2\fP which
        !          1216: allow them to match.
        !          1217: .IP "\f(CWP1 | P2\fP"
        !          1218: Tries to match \f(CWP1\fP.
        !          1219: If successful, \f(CWP1|P2\fP matches the
        !          1220: string that was matched by \f(CWP1\fP.
        !          1221: Otherwise, matches whatever
        !          1222: \f(CWP2\fP matches, and fails if \f(CWP2\fP fails.
        !          1223: .IP "\f(CWP $ V\fP"
        !          1224: Tries to match \f(CWP\fP.
        !          1225: If \f(CWP\fP matches, a copy of the substring
        !          1226: matched by \f(CWP\fP is immediately assigned to the variable \f(CWV\fP.
        !          1227: .IP "\f(CWP . V\fP"
        !          1228: Tries to match \f(CWP\fP.
        !          1229: If the entire pattern match of which
        !          1230: this element is a part is ultimately successful, a copy
        !          1231: of the substring matched by \f(CWP\fP is assigned to \f(CWV\fP after
        !          1232: the entire match completes.
        !          1233: .IP "\f(CW@N\fP"
        !          1234: Matches a null string, and immediately assigns
        !          1235: cursor position to the variable \f(CWN\fP.
        !          1236: The cursor position is
        !          1237: the number of characters that precede this null string
        !          1238: in the subject of the entire pattern match.
        !          1239: Thus:
        !          1240: .P1
        !          1241: "abcde" ? @OUTPUT && "c"
        !          1242: .P2
        !          1243: prints \f(CW0\fP, \f(CW1\fP, and \f(CW2\fP on separate lines.
        !          1244: .IP "\f(CWABORT\fP"
        !          1245: The entire pattern match is aborted.
        !          1246: .IP "\f(CWARB\fP"
        !          1247: A pre-defined variable that matches anything at all.
        !          1248: More specifically, it initially matches the null string.
        !          1249: When backed into, it matches a string one character longer
        !          1250: than the one it matched last time.
        !          1251: .IP "\f(CWBAL\fP"
        !          1252: A pre-defined variable that matches a non-empty parenthesis-
        !          1253: balanced string.
        !          1254: This string is balanced only with respect to parentheses,
        !          1255: and not any other kinds of brackets.
        !          1256: .IP "\f(CWFAIL\fP"
        !          1257: A pre-defined variable that always fails to match.
        !          1258: It
        !          1259: is sometimes useful to force the scanner to try all
        !          1260: alternatives for a pattern.
        !          1261: For instance:
        !          1262: .P1
        !          1263: s ARB $ OUTPUT && FAIL
        !          1264: .P2
        !          1265: prints all substrings of \f(CWs\fP.
        !          1266: .IP "\f(CWFENCE\fP"
        !          1267: Initially matches the null string, but if the scanner
        !          1268: backs into it, the entire pattern match is aborted.
        !          1269: Identical to to \f(CW""|ABORT\fP.
        !          1270: .IP "\f(CWREM\fP"
        !          1271: Matches from the current position to the end of the
        !          1272: subject.
        !          1273: Identical to \f(CWRTAB(0)\fP.
        !          1274: .IP "\f(CWSUCCEED\fP"
        !          1275: Identical to \f(CWARBNO("")\fP
        !          1276: .IP "\f(CWANY(s)\fP"
        !          1277: Matches any single character in \f(CWs\fP.
        !          1278: .IP "\f(CWARBNO(p)\fP"
        !          1279: A pre-defined procedure that yields a pattern that matches
        !          1280: zero or more copies of the pattern \f(CWp\fP.
        !          1281: Initially matches
        !          1282: the null string.
        !          1283: Each time the scanner backs into it,
        !          1284: it tries to extend the substring already matched by
        !          1285: matching one more instance of \f(CWp\fP.
        !          1286: .IP "\f(CWBREAK(s)\fP"
        !          1287: Matches a string starting at the current position up to
        !          1288: but not including the next character in the subject
        !          1289: that is also found somewhere in \f(CWs\fP.
        !          1290: Failure
        !          1291: if no such character is found.
        !          1292: No alternatives.
        !          1293: .IP "\f(CWBREAKX(s)\fP"
        !          1294: Like \f(CWBREAK\fP, but if backed into, it matches up to the
        !          1295: next subject character also found in \f(CWs\fP, and so on.
        !          1296: .IP "\f(CWLEN(n)\fP"
        !          1297: Matches exactly \f(CWn\fP characters.
        !          1298: .IP "\f(CWNOTANY(s)\fP"
        !          1299: Matches any single character not in \f(CWs\fP.
        !          1300: .IP "\f(CWPOS(n)\fP"
        !          1301: If exactly \f(CWn\fP subject characters precede the current
        !          1302: position, \f(CWPOS\fP matches the null string.
        !          1303: Otherwise it
        !          1304: fails.
        !          1305: .IP "\f(CWRPOS(n)\fP"
        !          1306: If exactly \f(CWn\fP subject characters remain to be matched,
        !          1307: \f(CWRPOS\fP matches the null string.
        !          1308: Otherwise it fails.
        !          1309: .IP "\f(CWRTAB(n)\fP"
        !          1310: If at least \f(CWn\fP subject characters remain in the subject,
        !          1311: \f(CWRTAB\fP matches characters until exactly \f(CWn\fP remain.
        !          1312: Otherwise
        !          1313: it fails.
        !          1314: .IP "\f(CWSPAN(s)\fP"
        !          1315: Starting at the current position, matches as many characters
        !          1316: as possible taken from \f(CWs\fP.
        !          1317: .IP "\f(CWTAB(n)\fP"
        !          1318: \f(CWTAB\fP matches from the current position forward up to
        !          1319: and including the \f(CWn\fPth character of the subject.
        !          1320: If more than \f(CWn\fP characters have already been matched
        !          1321: in the subject string, \f(CWTAB\fP fails.
        !          1322: .PP
        !          1323: All pattern-valued procedures can take an unevaluated expression as argument.
        !          1324: The expression will be evaluated when the pattern element is matched.
        !          1325: .SH
        !          1326: System Variables
        !          1327: .PP
        !          1328: The \f(CW&\fP operator looks at the name of its operand,
        !          1329: not its value.
        !          1330: For each of a small set of names, \f(CW&\fP yields a
        !          1331: .I "system variable" ,
        !          1332: whose value affects the operation of the system in some way.
        !          1333: For instance, we have already seen \f(CW&ANCHOR\fP, which
        !          1334: controls whether or not the scanner is restricted to examining
        !          1335: initial substrings of the subject.
        !          1336: The complete list of system variables is:
        !          1337: .IP "\f(CW&ABORT\fP" 13
        !          1338: The same value as the pre-defined variable \f(CWABORT\fP.
        !          1339: .IP "\f(CW&ALPHABET\fP"
        !          1340: A string that contains all the characters of the machine's
        !          1341: collating sequence, in order.
        !          1342: .IP "\f(CW&ANCHOR\fP"
        !          1343: If zero, all pattern matches are unanchored,
        !          1344: otherwise they are anchored.
        !          1345: .IP "\f(CW&ARB\fP"
        !          1346: The same value as the pre-defined variable \f(CWARB\fP.
        !          1347: .IP "\f(CW&BAL\fP"
        !          1348: The same value as the pre-defined variable \f(CWBAL\fP.
        !          1349: .IP "\f(CW&CODE\fP"
        !          1350: This variable is initially zero.
        !          1351: Its value is returned to the operating system when the
        !          1352: program finishes executing.
        !          1353: .IP "\f(CW&DUMP\fP"
        !          1354: This variable is initially zero.
        !          1355: If it is 1 at the end of execution, the values of
        !          1356: all variables are printed.
        !          1357: If it is 2, the values of all array, table, and structure
        !          1358: elements are also printed.
        !          1359: .IP "\f(CW&FAIL\fP"
        !          1360: The same value as the pre-defined variable \f(CWFAIL\fP.
        !          1361: .IP "\f(CW&FENCE\fP"
        !          1362: The same value as the pre-defined variable \f(CWFENCE\fP.
        !          1363: .IP "\f(CW&FNCLEVEL\fP"
        !          1364: The current level of procedure nesting.
        !          1365: .IP "\f(CW&INPUT\fP"
        !          1366: If this variable is set to 0, all
        !          1367: input association is suspended.
        !          1368: .IP "\f(CW&MAXLNGTH\fP"
        !          1369: The maximum length of a string.
        !          1370: This value cannot be increased beyond its
        !          1371: initial value.
        !          1372: .IP "\f(CW&OUTPUT\fP"
        !          1373: If this variable is set to 0, all output is suppressed
        !          1374: until it is again set nonzero.
        !          1375: .IP "\f(CW&REM\fP"
        !          1376: The same value as the pre-defined variable \f(CWREM\fP.
        !          1377: .IP "\f(CW&STCOUNT\fP"
        !          1378: A count of how many statements have been executed so far.
        !          1379: Because this counts \*(S4 statements, not
        !          1380: Snocone statements, it should be considered only approximate.
        !          1381: .IP "\f(CW&STLIMIT\fP"
        !          1382: When \f(CW&STCOUNT\fP reaches this value,
        !          1383: execution terminates with an error message.
        !          1384: It is initially 50000, and may be set freely.
        !          1385: If it is set to a negative value, statement
        !          1386: counting is disabled.
        !          1387: .IP "\f(CW&SUCCEED\fP"
        !          1388: The same value as the pre-defined variable \f(CWSUCCEED\fP.
        !          1389: .NH 1
        !          1390: Examples
        !          1391: .NH 2
        !          1392: Hello World
        !          1393: .PP
        !          1394: This is the canonical sample program:
        !          1395: .P1 0
        !          1396: OUTPUT = "Hello world!"
        !          1397: .P2
        !          1398: The present implementation of Snocone is case-insensitive
        !          1399: in identifiers, but future versions may well become
        !          1400: case-sensitive.
        !          1401: If so, it is likely that pre-defined names, such as
        !          1402: \f(CWINPUT\fP and \f(CWOUTPUT\fP, will have to be written
        !          1403: in upper case.
        !          1404: Keywords, such as \f(CWif\fP and \f(CWwhile\fP, will be
        !          1405: written in lower case.
        !          1406: .NH 2
        !          1407: Topological Sorting
        !          1408: .PP
        !          1409: We now develop
        !          1410: a topological sorting program based on the algorithm
        !          1411: described on page 262 of
        !          1412: .I "Fundamental Algorithms" |reference(knuth volume1).
        !          1413: The reader may wish to compare this program with the
        !          1414: \*(S4 program based on the same algorithm
        !          1415: that appears on pages 221-222 of
        !          1416: .I "The \*(S4 Programming Language" .
        !          1417: .PP
        !          1418: The input is
        !          1419: a set of pairs of objects,
        !          1420: where the first object in each pair
        !          1421: is considered to precede the second.
        !          1422: The output is a list of objects
        !          1423: in a sequence that meets all the constraints
        !          1424: implied by the input.
        !          1425: In other words, the program generates
        !          1426: a total ordering that includes a given
        !          1427: partial ordering.
        !          1428: .PP
        !          1429: If the input contains a loop, the program
        !          1430: will detect this fact and complain.
        !          1431: .PP
        !          1432: For example, given the following input:
        !          1433: .P1
        !          1434: letters alphanum
        !          1435: numbers alphanum
        !          1436: blanks optblanks
        !          1437: numbers real
        !          1438: numbers integer
        !          1439: letters variable
        !          1440: alphanum variable
        !          1441: binary binaryop
        !          1442: blanks binaryop
        !          1443: unqalphabet dliteral
        !          1444: unqalphabet sliteral
        !          1445: sliteral literal
        !          1446: dliteral literal
        !          1447: integer literal
        !          1448: real literal
        !          1449: .P2
        !          1450: the program will produce the following output:
        !          1451: .P1
        !          1452: letters
        !          1453: numbers
        !          1454: blanks
        !          1455: binary
        !          1456: unqalphabet
        !          1457: alphanum
        !          1458: real
        !          1459: integer
        !          1460: optblanks
        !          1461: binaryop
        !          1462: dliteral
        !          1463: sliteral
        !          1464: variable
        !          1465: literal
        !          1466: .P2
        !          1467: .PP
        !          1468: The basic strategy of the program is simple:
        !          1469: for each object, we remember how many immediate predecessors
        !          1470: it has, and store a list of all its immediate successors.
        !          1471: When we have finished reading the input,
        !          1472: we can immediately output the objects that have
        !          1473: no predecessors.
        !          1474: Each time we output an object, we remove it from
        !          1475: the data structure and decrement the predecessor
        !          1476: count of each of its immediate successors.
        !          1477: .PP
        !          1478: We will eventually reach a state in which we run
        !          1479: out of objects without predecessors.
        !          1480: When that happens, we are done.
        !          1481: If any objects remain, they form a loop.
        !          1482: .PP
        !          1483: To reduce the time spent searching for objects
        !          1484: without predecessors, we keep a queue of such
        !          1485: objects.
        !          1486: We must also keep a queue of the successors
        !          1487: of each object.
        !          1488: In both cases, we could use a stack instead of
        !          1489: a queue, but using a queue tends to favor the
        !          1490: order in which objects appeared in the input,
        !          1491: which makes the output more intuitively useful.
        !          1492: .PP
        !          1493: The following structure declarations and subroutines
        !          1494: manipulate queues.
        !          1495: A queue consists of a header (of type \f(CWqueue\fP)
        !          1496: which points to the first and last elements of
        !          1497: a singly-linked list of queue elements (of type \f(CWqel\fP).
        !          1498: .P1 0
        !          1499: struct queue {head, tail}
        !          1500: struct qel {obj, link}
        !          1501: 
        !          1502: .P3
        !          1503: procedure enqueue (q, x) y {
        !          1504:        if (head(q) :: "")
        !          1505:                head(q) = tail(q) = qel(x)
        !          1506:        else {
        !          1507:                y = qel(x)
        !          1508:                link(tail(q)) = y
        !          1509:                tail(q) = y
        !          1510:        }
        !          1511: }
        !          1512: .P3
        !          1513: 
        !          1514: procedure dequeue (q) x {
        !          1515:        if (head(q) :: "")
        !          1516:                freturn
        !          1517:        x = head(q)
        !          1518:        if ((head(q) = link(x)) :: "")
        !          1519:                tail(q) = ""
        !          1520:        return obj(x)
        !          1521: }
        !          1522: .P2
        !          1523: .PP
        !          1524: By convention, we use the null string to indicate
        !          1525: the end of a list.
        !          1526: This is convenient because uninitialized variables
        !          1527: and structure fields and missing arguments are automatically set to
        !          1528: the null string.
        !          1529: Thus, the test
        !          1530: .P1
        !          1531: head(q) :: ""
        !          1532: .P2
        !          1533: is a convenient way of testing whether \f(CWhead(q)\fP
        !          1534: has been set or not.
        !          1535: .PP
        !          1536: We represent each object as a structure containing
        !          1537: the object's name (so we can print it), the count of
        !          1538: immediate predecessors, and the queue of successors:
        !          1539: .P1
        !          1540: struct object {name, count, suc}
        !          1541: .P2
        !          1542: .PP
        !          1543: Since we will be reading the names of objects
        !          1544: rather than the objects directly, we will need
        !          1545: to map names to objects.
        !          1546: This can easily be done with a table and a mapping subroutine
        !          1547: that creates elements in the table as needed:
        !          1548: .P1 0
        !          1549: namemap = TABLE()
        !          1550: objects = queue()
        !          1551: 
        !          1552: procedure getobj (name) {
        !          1553:     if ((getobj = namemap[name]) :: "") {
        !          1554:         getobj = namemap[name] =
        !          1555:             object (name, 0, queue())
        !          1556:         enqueue (objects, getobj)
        !          1557:         nobj = nobj + 1
        !          1558:     }
        !          1559: }
        !          1560: .P2
        !          1561: .PP
        !          1562: This procedure uses the feature that if no return value
        !          1563: is explicitly given, the value of the variable with the
        !          1564: same name as the procedure is used.
        !          1565: If an appropriate table element already
        !          1566: exists, the \f(CW::\fP operator will fail
        !          1567: and the value of \f(CWgetobj\fP will be the
        !          1568: value retrieved from the table.
        !          1569: As a side effect, we maintain a global queue of
        !          1570: all known objects in \f(CWobjects\fP and
        !          1571: count them in \f(CWnobj\fP.
        !          1572: .PP
        !          1573: Now that we can map from names to objects, it is
        !          1574: an easy matter to enter a new relation into
        !          1575: our data structure.
        !          1576: Procedure \f(CWenter\fP takes the
        !          1577: names of two objects:
        !          1578: .P1 0
        !          1579: procedure enter (p, q) {
        !          1580:        p = getobj (p)
        !          1581:        q = getobj (q)
        !          1582:        count(q) = count(q) + 1
        !          1583:        enqueue (suc(p), q)
        !          1584: }
        !          1585: .P2
        !          1586: .PP
        !          1587: We first locate the objects to which \f(CWp\fP
        !          1588: and \f(CWq\fP refer, creating them if necessary.
        !          1589: Since \f(CWp\fP precedes \f(CWq\fP, we increment
        !          1590: the predecessor count of \f(CWq\fP and append
        !          1591: \f(CWq\fP to the successor list of \f(CWp\fP.
        !          1592: .PP
        !          1593: Building the data structure is now just a matter of
        !          1594: scanning the input file:
        !          1595: .P1 0
        !          1596: while (line = INPUT) {
        !          1597:    if (line ? FENCE && BREAK(' ').p &&
        !          1598:                SPAN(' ') && rem.q)
        !          1599:         enter (p, q)
        !          1600:     else
        !          1601:         TERMINAL = "bad input line: " && line
        !          1602: }
        !          1603: .P2
        !          1604: .PP
        !          1605: The pattern match assumes that everything up to the first
        !          1606: blank in the input line is the first object in a
        !          1607: relation, and everything after the first blank is
        !          1608: the second object.
        !          1609: If the match fails, the program complains.
        !          1610: .PP
        !          1611: Once all the input has been read, we must initialize
        !          1612: the queue of minimal objects (objects without predecessors).
        !          1613: This was the reason for keeping a queue of all objects,
        !          1614: which is now destroyed to build the queue of minimal objects.
        !          1615: It is not necessary to destroy the queue, but it is more
        !          1616: convenient because it is then possible to use \f(CWdequeue\fP:
        !          1617: .P1 0
        !          1618: zeroes = queue()
        !          1619: 
        !          1620: while (x = dequeue (objects))
        !          1621:        if (count (x) == 0)
        !          1622:                enqueue (zeroes, x)
        !          1623: .P2
        !          1624: .PP
        !          1625: As long as there is a minimal object,
        !          1626: we can print its name, delete it, and
        !          1627: decrement the predecessor count of each
        !          1628: of its successors.
        !          1629: If we decrement a predecessor count to
        !          1630: zero, that object is now minimal.
        !          1631: .P1 0
        !          1632: while (x = dequeue (zeroes)) {
        !          1633:     nobj = nobj - 1
        !          1634:     OUTPUT = name(x)
        !          1635:     while (y = dequeue (suc (x))) {
        !          1636:         if ((count(y) = count(y) - 1) == 0)
        !          1637:             enqueue (zeroes, y)
        !          1638:     }
        !          1639: }
        !          1640: .P2
        !          1641: .PP
        !          1642: This loop runs until there are no more minimal objects.
        !          1643: If there are still elements remaining (\f(CWnobj\fP is nonzero),
        !          1644: then those elements form a loop.
        !          1645: .P1 0
        !          1646: if (nobj != 0)
        !          1647:     TERMINAL = "The ordering contains a loop."
        !          1648: .P2
        !          1649: .NH 1
        !          1650: References
        !          1651: .LP
        !          1652: |reference_placement

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.