![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to snocone.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / vol2 / snocone|
Return to snocone.ms CVS log | Up to [Research Unix] / researchv10dc / vol2 / snocone |
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.