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