Annotation of 43BSD/contrib/icon/docs/tr83-3, revision 1.1.1.1

1.1       root        1: .so tmac.tr
                      2: .DA "May 13, 1983"
                      3: .TR 83-3a
                      4: .GR MCS81-01916
                      5: .GE
                      6: .TL
                      7: An Overview of the Icon Programming Language
                      8: .AU
                      9: Ralph E. Griswold
                     10: .AE
                     11: .tr *\(**
                     12: .NH
                     13: Introduction
                     14: .PP
                     15: Icon is a high-level programming language with extensive facilities for
                     16: processing strings and lists. Icon has several novel features, including
                     17: expressions that may produce sequences of results, goal-directed
                     18: evaluation that automatically searches for a successful result, and
                     19: string scanning that allows operations on strings to be formulated at
                     20: a high conceptual level.
                     21: .PP
                     22: Icon resembles SNOBOL4 [1] in its emphasis on high-level string
                     23: processing and a design philosophy that allows ease of programming
                     24: and short, concise programs. Like SNOBOL4, storage allocation and
                     25: garbage collection are automatic in Icon, and there are few restrictions on the
                     26: sizes of objects. Strings, lists, and other structures are created
                     27: during program execution and their size does not need to be known when
                     28: a program is written.
                     29: Values are converted to expected types automatically; for example,
                     30: numeral strings read in as input can be used in numerical computations
                     31: without explicit conversion.
                     32: Whereas SNOBOL4 has a pattern-matching facility that is separate from
                     33: the rest of the language, string scanning is integrated with the
                     34: rest of the language facilities in Icon.
                     35: Unlike SNOBOL4,
                     36: Icon has an expression-based syntax with reserved words;
                     37: in appearance, Icon programs resemble those of several other conventional programming
                     38: languages.
                     39: .PP
                     40: Examples of the kinds of problems for which Icon is well suited are:
                     41: .in .5i
                     42: .IP \(bu
                     43: text analysis, editing, and reformatting
                     44: .IP \(bu
                     45: document preparation
                     46: .IP \(bu
                     47: symbolic mathematics
                     48: .IP \(bu
                     49: text generation
                     50: .IP \(bu
                     51: program parsing and translation
                     52: .IP \(bu
                     53: data laundry
                     54: .IP \(bu
                     55: graph manipulation
                     56: .in 0
                     57: .PP
                     58: Icon is implemented in C [2] and runs under UNIX\u*\d
                     59: .FS
                     60: \u*\dUNIX is a trademark of Bell Laboratories.
                     61: .FE
                     62: on the PDP-11, VAX-11, and Onyx C8002 computers. Implementations for
                     63: other computers and operating systems are presently underway.
                     64: An earlier version of Icon [3] is available on several large-scale
                     65: computers, including the CRAY-1, DEC-10, IBM 360/370, PRIME 450/550/650, DG
                     66: MV8000,
                     67: and CDC Cyber/6000.
                     68: .PP
                     69: A brief description of some of the representative features of Icon
                     70: is given in the following sections. This description is not rigorous
                     71: and does not include many features of Icon. See [4] for a
                     72: complete description.
                     73: .NH
                     74: Strings
                     75: .PP
                     76: Strings of characters may be arbitrarily long, limited only by the
                     77: architecture of the computer on which Icon is implemented. A string
                     78: may be specified literally by enclosing it in double quotation marks,
                     79: as in
                     80: .Ds
                     81: greeting := "Hello world"
                     82: .De
                     83: which assigns an 11-character string to \*Mgreeting\fR, and
                     84: .Ds
                     85: address := ""
                     86: .De
                     87: which assigns the zero-length \fIempty\fR string to \*Maddress\fR.
                     88: The number of characters in a string \*Ms\fR, its size, is given
                     89: by \*M*s\fR. For example, \*M*greeting\fR is 11 and \*M*address\fR
                     90: is 0.
                     91: .PP
                     92: Icon uses the ASCII character set, extended to 256 characters.
                     93: There are escape conventions, similar to those of C, for representing
                     94: characters that cannot be keyboarded.
                     95: .PP
                     96: Strings also can be read in and written out, as in
                     97: .Ds
                     98: line := read()
                     99: .De
                    100: and
                    101: .Ds
                    102: write(line)
                    103: .De
                    104: Strings can be constructed by concatenation, as in
                    105: .Ds
                    106: element := "(" || read() || ")"
                    107: .De
                    108: If the concatenation of a number of strings is to be written
                    109: out, the \*Mwrite\fR function can be used with several arguments
                    110: to avoid actual concatenation:
                    111: .Ds
                    112: write("(",read(),")")
                    113: .De
                    114: .PP
                    115: Substrings can be formed by subscripting strings with range
                    116: specifications that indicate, by position, the desired range of
                    117: characters. For example,
                    118: .Ds
                    119: middle := line\^[10:20]
                    120: .De
                    121: assigns to \*Mmiddle\fR the string of characters of \*Mline\fR between
                    122: positions 10 and 20.
                    123: Similarly,
                    124: .Ds
                    125: write(line\^[2])\fR
                    126: .De
                    127: writes the second character of \*Mline\fR.
                    128: The value 0 is used to refer to the position after the last character
                    129: of a string. Thus
                    130: .Ds
                    131: write(line\^[2:0])
                    132: .De
                    133: writes the substring of \*Mline\fR from the second character to the end, thus
                    134: omitting the first character.
                    135: .PP
                    136: An assignment can be made to the substring of string-valued variable
                    137: to change its value. For example,
                    138: .Ds
                    139: line[2] := "..."
                    140: .De
                    141: replaces the second character of \*Mline\fR by three dots. Note that
                    142: the size of \*Mline\fR changes automatically.
                    143: .PP
                    144: There are many functions for analyzing strings. An example is
                    145: .Ds
                    146: find(s1,\*bs2)
                    147: .De
                    148: which produces the position in \*Ms2\fR at which \*Ms1\fR occurs as
                    149: a substring. For example, if the value of \*Mgreeting\fR is as
                    150: given earlier,
                    151: .Ds
                    152: find("or",\*bgreeting)
                    153: .De
                    154: produces the value 8.
                    155: See Section 4.2 for the handling of situations in which \*Ms1\fR does not
                    156: occur in \*Ms2\fR, or in which it occurs at several different positions.
                    157: .NH
                    158: Character Sets
                    159: .PP
                    160: While strings are sequences of characters, \fIcsets\fR are sets of characters
                    161: in which membership rather than order is significant. Csets are
                    162: represented literally using single enclosing quotation marks, as
                    163: in
                    164: .Ds
                    165: vowels := 'aeiouAEIOU'
                    166: .De
                    167: Two useful built-in csets are \*M&lcase\fR and \*M&ucase\fR, which
                    168: consist of the lowercase and uppercase letters, respectively.
                    169: Set operations are provided for csets. For example,
                    170: .Ds
                    171: letters := &lcase ++ &ucase
                    172: .De
                    173: forms the cset union of the lowercase and uppercase letters and assigns the
                    174: resulting cset to \*Mletters\fR, while
                    175: .Ds
                    176: consonants := letters -- 'aeiouAEIOU'
                    177: .De
                    178: forms the cset difference of the letters and the vowels and assigns the
                    179: resulting cset to \*Mconsonants\fR.
                    180: .PP
                    181: Csets are useful in situations in which any one of a number of characters
                    182: is significant. An example is the string analysis function
                    183: .Ds
                    184: upto(c,\*bs)
                    185: .De
                    186: which produces the position \*Ms\fR at which any character in \*Mc\fR occurs.
                    187: For example,
                    188: .Ds
                    189: upto(vowels,\*bgreeting)
                    190: .De
                    191: produces 2. Another string analysis function that uses csets is
                    192: .Ds
                    193: many(c,\*bs)
                    194: .De
                    195: which produces the position in \*Ms\fR after an initial substring consisting
                    196: only of characters that occur in \*Ms\fR.
                    197: An example of the use of \*Mmany\fR is in locating words. Suppose, for
                    198: example, that a word is defined to consist of a string of letters.
                    199: The expression
                    200: .Ds
                    201: write(line\^[1:many(letters,\*bline)])
                    202: .De
                    203: writes a word at the beginning of \*Mline\fR. Note the use of the
                    204: position returned by a string analysis function to specify the
                    205: end of a
                    206: substring.
                    207: .NH
                    208: Expression Evaluation
                    209: .NH 2
                    210: Conditional Expressions
                    211: .PP
                    212: In Icon there are \fIconditional expressions\fR that may \fIsucceed\fR and
                    213: produce a result, or may \fIfail\fR and not produce any result. An example
                    214: is the comparison operation
                    215: .Ds
                    216: i > j
                    217: .De
                    218: which succeeds (and produces the value of \*Mj\fR) provided that the value
                    219: of \*Mi\fR is greater than the value of \*Mj\fR, but fails otherwise.
                    220: .PP
                    221: The success or failure of conditional operations is used instead of
                    222: Boolean values to drive control structures in Icon. An example is
                    223: .Ds
                    224: if i > j then k := i else k := j
                    225: .De
                    226: which assigns the value of \*Mi\fR to \*Mk\fR if the value of \*Mi\fR
                    227: is greater than the value of \*Mj\fR, but assigns the value of \*Mj\fR to
                    228: \*Mk\fR \%otherwise.
                    229: .PP
                    230: The usefulness of the concepts of success and failure is illustrated by
                    231: \*Mfind(s1,\*bs2)\fR, which fails
                    232: if \*Ms1\fR does not occur as a substring of \*Ms2\fR.
                    233: Thus
                    234: .Ds
                    235: if i := find("or",line) then write(i)
                    236: .De
                    237: writes the position at which \*Mor\fR occurs in \*Mline\fR, if it occurs,
                    238: but does not write a value if it does not occur.
                    239: .PP
                    240: Many expressions in Icon are conditional. An example is \*Mread()\fR,
                    241: which produces the next line from the input file, but fails when the
                    242: end of the file is reached. The following expression is typical of
                    243: programming in Icon and illustrates the integration of conditional
                    244: expressions and conventional control structures:
                    245: .Ds
                    246: while line := read() do
                    247:    write(line)
                    248: .De
                    249: This expression copies the input file to the output file.
                    250: .PP
                    251: If an argument of a function fails, the function is not called,
                    252: and the function call fails as well. This ``inheritance'' of failure allows the
                    253: concise formulation of many programming tasks. Omitting the optional
                    254: \f3do\fR clause in \f3while-do\fR, the previous expression can be
                    255: rewritten as
                    256: .Ds
                    257: while write(read())
                    258: .De
                    259: .NH 2
                    260: Generators
                    261: .PP
                    262: In some situations, an expression may be capable of producing more than
                    263: one result. Consider
                    264: .Ds
                    265: sentence := "Store it in the neighboring harbor"
                    266: find("or",\*bsentence)
                    267: .De
                    268: Here \*Mor\fR occurs in \*Msentence\fR at positions 3, 23, and 33. Most
                    269: programming languages treat this situation by selecting one of the
                    270: positions, such as the first, as the result of the expression. In Icon,
                    271: such an expression is a \fIgenerator\fR and is capable of producing
                    272: all three positions.
                    273: .PP
                    274: The results that a generator produces depend on context. In a situation
                    275: where only one result is needed, the first is produced, as in
                    276: .Ds
                    277: i := find("or",\*bsentence)
                    278: .De
                    279: which assigns the value 3 to \*Mi\fR.
                    280: .PP
                    281: If the result produced by a generator does not lead to the success of
                    282: an enclosing expression, however, the generator is \fIresumed\fR
                    283: to produce another value. An example is
                    284: .Ds
                    285: if (i := find("or",\*bsentence)) > 5 then write(i)
                    286: .De
                    287: Here the first result produced by the generator, 3, is assigned to
                    288: \*Mi\fR, but this value is not greater than 5 and the comparison
                    289: operation fails. At this point, the generator is resumed and
                    290: produces the second position, 23, which is greater than 5. The
                    291: comparison operation then succeeds and the value 23 is written.
                    292: Because of the inheritance of failure and the fact that comparison
                    293: operations return the value of their right argument, this expression
                    294: can be written in the following more compact form:
                    295: .Ds
                    296: write(5 < find("or",\*bsentence))
                    297: .De
                    298: .PP
                    299: Goal-directed evaluation is inherent in the expression evaluation
                    300: mechanism of Icon and can be used in arbitrarily complicated situations.
                    301: For example,
                    302: .Ds
                    303: find("or",\*bsentence1) = find("and",\*bsentence2)
                    304: .De
                    305: succeeds if \*Mor\fR occurs in \*Msentence1\fR at the same position
                    306: as \*Mand\fR occurs in \*Msentence2\fR.
                    307: .PP
                    308: A generator can be resumed repeatedly to produce all its results by
                    309: using the \f3every-do\fR control structure. An example is
                    310: .Ds
                    311: every i := find("or",\*bsentence)
                    312:    do write(i)
                    313: .De
                    314: which writes all the positions at which \*Mor\fR occurs in \*Msentence\fR.
                    315: For the example above, these are 3, 23, and 33.
                    316: .PP
                    317: Generation is inherited like failure, and this expression can be written
                    318: more concisely by omitting the optional \f3do\fR clause:
                    319: .Ds
                    320: every write(find("or",\*bsentence))
                    321: .De
                    322: .PP
                    323: There are several built-in generators in Icon. One of the most frequently
                    324: used of these is
                    325: .Ds
                    326: i to j
                    327: .De
                    328: which generates the integers from \*Mi\fR to \*Mj\fR. This generator can be
                    329: combined with \f3every-do\fR to formulate the traditional \f3for\fR-style
                    330: control structure:
                    331: .Ds
                    332: every k := i to j do
                    333:    f(k)
                    334: .De
                    335: Note that this expression can be written more compactly as
                    336: .Ds
                    337: every f(i to j)
                    338: .De
                    339: .PP
                    340: There are a number of other control structures related to generation.
                    341: One is \fIalternation\fR,
                    342: .Ds
                    343: \*1 | \*2
                    344: .De
                    345: which generates the results of \*1 followed by the results of \*2.
                    346: Thus
                    347: .Ds
                    348: every write(find("or",\*bsentence1) | find("or",\*bsentence2))
                    349: .De
                    350: writes the positions of \*Mor\fR in \*Msentence1\fR followed by
                    351: the positions of \*Mor\fR in \*Msentence2\fR. Again, this sentence can
                    352: be written more compactly by using alternation in the second
                    353: argument of \*Mfind\fR:
                    354: .Ds
                    355: every write(find("or",\*bsentence1 | sentence2))
                    356: .De
                    357: .PP
                    358: Another use of alternation is illustrated by
                    359: .Ds
                    360: (i | j | k) = (0 | 1)
                    361: .De
                    362: which succeeds if any of \*Mi\fR, \*Mj\fR, or \*Mk\fR has the value 0 or 1.
                    363: .NH
                    364: String Scanning
                    365: .PP
                    366: The string analysis and synthesis operations described in
                    367: Sections 2 and 3 work best for relatively simple operations on strings.
                    368: For complicated operations, the bookkeeping involved in keeping track of
                    369: positions in strings becomes burdensome and error prone.
                    370: In such cases, Icon has a string scanning facility that is
                    371: analogous in many respects to pattern matching in SNOBOL4. In string
                    372: scanning, positions are managed automatically and attention is
                    373: focused on a current position in a string as it is examined by a sequence of
                    374: operations.
                    375: .PP
                    376: The string scanning operation has the form
                    377: .Ds
                    378: s ? \*0
                    379: .De
                    380: where \*Ms\fR is the \fIsubject\fR string to be examined and \*0 is an expression that
                    381: performs the examination.
                    382: A position in the subject, which starts at 1, is the focus of examination.
                    383: .PP
                    384: \fIMatching functions\fR change this position.
                    385: One matching function, \*Mmove(i)\fR, moves the position by \*Mi\fR and
                    386: produces the substring of the subject between the previous and new
                    387: positions. If the position cannot be moved by the specified amount
                    388: (because the subject is not long enough), \*Mmove(i)\fR fails. A
                    389: simple example is
                    390: .Ds
                    391: line ? while write(move(2))
                    392: .De
                    393: which writes successive two-character substrings of \*Mline\fR, stopping
                    394: when there are no more characters.
                    395: .PP
                    396: Another matching function is \*Mtab(i)\fR, which sets the position in the
                    397: subject to \*Mi\fR and also returns the substring of the subject between
                    398: the previous and new positions.
                    399: For example,
                    400: .Ds
                    401: line ? if tab(10) then write(tab(0))
                    402: .De
                    403: first sets the position in the subject to 10 and then to the end of the subject, writing
                    404: \*Mline\^[10:0]\fR.
                    405: Note that no value is written if the subject is not long enough.
                    406: .PP
                    407: String analysis functions such as \*Mfind\fR
                    408: can be used in string scanning. In this context, the string that they
                    409: operate on is not specified and is taken to be the subject. For example,
                    410: .Ds
                    411: line ? while write(tab(find("or")))
                    412:    do move(2)
                    413: .De
                    414: writes all the substrings of \*Mline\fR prior to occurrences of \*Mor\fR.
                    415: Note that \*Mfind\fR produces a position, which is then used by \*Mtab\fR
                    416: to change the position and produce the desired substring. The \*Mmove(2)\fR
                    417: skips the \*Mor\fR that is found.
                    418: .PP
                    419: Another example of the use of string analysis functions in scanning is
                    420: .Ds
                    421: line ? while tab(upto(letters)) do
                    422:    write(tab(many(letters)))
                    423: .De
                    424: which writes all the words in \*Mline\fR.
                    425: .PP
                    426: As illustrated in the examples above, any expression may occur in
                    427: the scanning expression. Unlike SNOBOL4, in which the operations that
                    428: are allowed in pattern matching are limited and idiosyncratic, string
                    429: scanning is completely integrated with the rest of the operation
                    430: repertoire of Icon.
                    431: .NH
                    432: Structures
                    433: .NH 2
                    434: Lists
                    435: .PP
                    436: While strings are sequences of characters, lists in Icon are sequences
                    437: of values of arbitrary types. Lists are created by enclosing the lists
                    438: of values in brackets. An example is
                    439: .Ds
                    440: car1 := ["buick",\*b"skylark",\*b1978,\*b2450]
                    441: .De
                    442: in which the list \*Mcar1\fR has four values, two of which are strings
                    443: and two of which are integers. Note that the values in a list need not
                    444: all be of the same type. In fact, any kind of value can occur in a list
                    445: \(em even another list, as in
                    446: .Ds
                    447: inventory := [car1,\*bcar2,\*bcar3,\*bcar4]
                    448: .De
                    449: .PP
                    450: Lists also can be created by
                    451: .Ds
                    452: a := list(i,\*bx)
                    453: .De
                    454: which creates a list of \*Mi\fR values, each of which has the value
                    455: \*Mx\fR.
                    456: .PP
                    457: The values in a list can be referenced by position much like the
                    458: characters in a string. Thus
                    459: .Ds
                    460: car1\^[4] := 2400
                    461: .De
                    462: changes the last value in \*Mcar1\fR to 2400.
                    463: A reference that is out of the range of the list fails. For example,
                    464: .Ds
                    465: write(car1\^[5])
                    466: .De
                    467: fails.
                    468: .PP
                    469: The values in a list \*Ma\fR are generated by \*M!a\fR. Thus
                    470: .Ds
                    471: every write(!a)
                    472: .De
                    473: writes all the values in \*Ma\fR.
                    474: .PP
                    475: Lists can be manipulated like stacks and queues. The function
                    476: \*Mpush(a,\*bx)\fR
                    477: adds the value of \*Mx\fR to the left end of the list \*Ma\fR,
                    478: automatically increasing the size of \*Ma\fR by one. Similarly,
                    479: \*Mpop(a)\fR removes the leftmost value from \*Ma\fR, automatically
                    480: decreasing the size of \*Ma\fR by one, and produces the removed value.
                    481: .PP
                    482: A list value in Icon is a pointer (reference) to a structure. Assignment
                    483: of a structure
                    484: in Icon does not copy the structure itself but only the pointer to it. Thus the
                    485: result of
                    486: .Ds
                    487: demo := car1
                    488: .De
                    489: causes \*Mdemo\fR and \*Mcar1\fR to reference the same list. Graphs with
                    490: loops can be constructed in this way. For example,
                    491: .Ds
                    492: node1 := ["a"]
                    493: node2 := [node1,\*b"b"]
                    494: push(node1,\*bnode2)
                    495: .De
                    496: constructs a structure that can be pictured as follows:
                    497: .if \n(Ex .ig
                    498: .Ds
                    499: .ta 1.2i
                    500: .sp 2
                    501: node1  a
                    502: .sp 2
                    503: node2  b
                    504: .sp 2
                    505: .De
                    506: ..
                    507: .if !\n(Ex .ig
                    508: .ne 2i
                    509: .nf
                    510: .in 1i
                    511: .ft B
                    512: .sp 2
                    513: .cs B 20
                    514: node1  .->a--.
                    515:        |     |
                    516:        |     |
                    517: node2  '--b<-'
                    518: .sp 2
                    519: .cs B
                    520: .in 0
                    521: .fi
                    522: ..
                    523: .NH 2
                    524: Tables
                    525: .PP
                    526: Icon has a table data type similar to that of SNOBOL4. Tables essentially
                    527: are sets of pairs of values, an \fIentry value\fR and a corresponding
                    528: \fIassigned value\fR. The entry and assigned values may be of any type,
                    529: and the assigned value for any entry value can be looked up automatically.
                    530: Thus tables provide a form of associative access in contrast with the
                    531: positional access to values in lists.
                    532: .PP
                    533: A table is created by an expression such as
                    534: .Ds
                    535: symbols := table(x)
                    536: .De
                    537: which assigns to \*Msymbols\fR a table with the default assigned value
                    538: \*Mx\fR.
                    539: Subsequently, \*Msymbols\fR can be referenced by any entry value, such as
                    540: .Ds
                    541: symbols\^["there"] := 1
                    542: .De
                    543: which assigns the value 1 to the \*Mthere\fRth entry in symbols.
                    544: .PP
                    545: Tables grow automatically as new entry values are added.
                    546: For example, the following program segment produces a
                    547: table containing a
                    548: count of the
                    549: words that appear in the input file:
                    550: .Ds
                    551: words := table(0)
                    552: while line := read() do
                    553:    line ? while tab(upto(letters)) do
                    554:       words\^[tab(many(letters))] +:= 1
                    555: .De
                    556: Here the default assigned value for each word is 0, as given
                    557: in \*Mtable(0)\fR, and \*M+:=\fR is an augmented assignment operation that
                    558: increments the assigned values by one.
                    559: There are augmented assignment operations for all binary operators.
                    560: .PP
                    561: Tables can
                    562: be converted to lists, so that their entry and assigned values can be
                    563: accessed by position.
                    564: This is done by \*Msort(t)\fR, which produces a list of two-element
                    565: lists from \*Mt\fR, where each two-element list consists of an
                    566: entry value and its corresponding assigned value. For example,
                    567: .Ds
                    568: wordlist := sort(words)
                    569: every pair := !wordlist do
                    570:    write(pair\^[1],\*b" : ",\*bpair\^[2])
                    571: .De
                    572: writes the words and their counts from \*Mwords\fR.
                    573: .NH
                    574: Procedures
                    575: .PP
                    576: An Icon program consists of a sequence of procedure declarations.
                    577: An example of a procedure declaration is
                    578: .Ds
                    579: procedure max(i,\*bj)
                    580:    if i > j then return i else return j
                    581: end
                    582: .De
                    583: where the name of the procedure is \*Mmax\fR and its formal parameters
                    584: are \*Mi\fR and \*Mj\fR. The \f3return\fR expressions return the value of
                    585: \*Mi\fR or \*Mj\fR, whichever is larger.
                    586: .PP
                    587: Procedures are called like built-in functions. Thus
                    588: .Ds
                    589: k := max(*s1,\*b*s2)
                    590: .De
                    591: assigns to \*Mk\fR the size of the longer of the strings \*Ms1\fR and
                    592: \*Ms2\fR.
                    593: .PP
                    594: A procedure also may suspend instead of returning. In this case, a
                    595: result is produced as in the case of a return, but the procedure
                    596: can be resumed to produce other results. An example is
                    597: the following procedure that generates the words in the input file.
                    598: .Ds
                    599: procedure genword()
                    600:    local line, letters, words
                    601:    letters := &lcase ++ &ucase
                    602:    while line := read() do
                    603:       line ? while tab(upto(letters)) do {
                    604:          word := tab(many(letters))
                    605:          suspend word
                    606:          }
                    607: end
                    608: .De
                    609: The braces enclose a compound expression.
                    610: .PP
                    611: Such a generator is used in the same way that a built-in generator is
                    612: used. For example
                    613: .Ds
                    614: every word := genword() do
                    615:    if find("or",\*bword) then write(word)
                    616: .De
                    617: writes only those words that contain the substring \*Mor\fR.
                    618: .NH
                    619: An Example
                    620: .PP
                    621: The following program sorts graphs topologically.
                    622: .Ds
                    623: .ta 3.5i
                    624: .Px
                    625: procedure main()
                    626:    local sorted, nodes, arcs, roots
                    627:    while nodes := read() do {  # get next node list
                    628:       arcs := read()   # get arc list
                    629:       sorted := ""     # sorted nodes
                    630:        # get nodes without predecessors
                    631:       while *(roots := nodes -- snodes(arcs)) > 0 do {
                    632:          sorted ||:= roots     # add to sorted nodes
                    633:          nodes --:= roots      # delete these nodes
                    634:          arcs := delarcs(arcs,\*broots)        # delete their arcs
                    635:          }
                    636:       if *arcs = 0 then write(sorted)  # successfully sorted
                    637:       else write("graph has cycle")    # cycle if node remains
                    638:    }
                    639: end
                    640: .De
                    641: .Ds
                    642: .Px
                    643: procedure snodes(arcs)
                    644:    local nodes
                    645:    nodes := ""
                    646:    arcs ? while move(1) do {   # predecessor
                    647:       move(2)  # skip "->"
                    648:       nodes ||:= move(1)       # successor
                    649:       move(1)  # skip ";"
                    650:       }
                    651:    return nodes
                    652: end
                    653: .De
                    654: .Ds
                    655: .Px
                    656: procedure delarcs(arcs,\*broots)
                    657:    local newarcs, node
                    658:    newarcs := ""
                    659:    arcs ? while node := move(1) do {   # get predecessor node
                    660:       if many(roots,\*bnode) then move(4)      # delete arc from root node
                    661:       else newarcs ||:= node || move(4)        # else keep arc
                    662:       }
                    663:    return newarcs
                    664: end
                    665: .De
                    666: Graph nodes are represented
                    667: by single characters with a list of the nodes on one input line followed by
                    668: a list of arcs. For example, the graph
                    669: .if \n(Ex .ig
                    670: .Ds
                    671: .ta .75i +.75i +.75i
                    672: \0
                    673: \0
                    674: \0
                    675:        a       b       c
                    676: .sp 2
                    677:        d       e
                    678: .sp 2
                    679: .De
                    680: ..
                    681: .if !\n(Ex .ig
                    682: .nf
                    683: .ft B
                    684: .cs B 20
                    685: .in 1i
                    686: .ne 2i
                    687: .sp 2
                    688:         .---------------.
                    689:         |               |
                    690:         |               \o'v|'
                    691:         a------>b------>c
                    692:         \o'^|'       |       \o'^|'
                    693:         |       |       |
                    694:         |       \o'|v'       |
                    695:         d------>e-------'
                    696: .sp 1
                    697: .cs B
                    698: .fi
                    699: .in 0
                    700: .sp 1
                    701: .ft R
                    702: ..
                    703: is given as
                    704: .Ds
                    705: abcde
                    706: a\*(->b;a\*(->c;b\*(->c;b\*(->e;d\*(->a;d\*(->e;e\*(->c;
                    707: .De
                    708: for which the output is
                    709: .Ds
                    710: dabec
                    711: .De
                    712: .PP
                    713: The nodes are represented by csets and automatic type conversion
                    714: is used to convert strings to csets and vice versa.
                    715: Note the use of augmented assignment operations for concatenation and in the computation of
                    716: cset differences.
                    717: .SH
                    718: Acknowledgement
                    719: .PP
                    720: Icon was designed by the the author in collaboration with Dave Hanson,
                    721: Tim Korb, Cary Coutant, and Steve Wampler. The current implementation is
                    722: largely the work of Cary Coutant and Steve Wampler with recent
                    723: contributions by Bill Mitchell.
                    724: Dave Hanson and Bill Mitchell also made several helpful suggestions on the presentation
                    725: of material in this paper.
                    726: .SH
                    727: References
                    728: .LP
                    729: .IP 1.
                    730: Griswold, Ralph E., Poage, James F., and Polonsky, Ivan P.
                    731: \fIThe SNOBOL4 Programming Language\fR, second edition.
                    732: Prentice-Hall, Inc., Englewood Cliffs, New Jersey. 1971.
                    733: .IP 2.
                    734: Kernighan, Brian W. and Ritchie, Dennis M. \fIThe C
                    735: Programming Language\fR. Prentice-Hall, Inc.,
                    736: Englewood Cliffs, New Jersey. 1978.
                    737: .IP 3.
                    738: Griswold, Ralph E. \fIDifferences Between Versions 2 and 5 of Icon\fR,
                    739: Technical Report TR 83-5, Department of Computer Science, The University
                    740: of Arizona. 1983.
                    741: .IP 4.
                    742: Griswold, Ralph E. and Griswold, Madge T. \fIThe Icon Programming
                    743: Language\fR. Prentice-Hall, Inc., Englewood Cliffs, New Jersey.
                    744: 1983.

unix.superglobalmegacorp.com

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