Icon (programming language)

From Bauman National Library
This page was last modified on 1 June 2016, at 17:16.
Icon
Iconlogo.gif
Paradigm multi-paradigm: imperative, logical
Designed by Ralph E. Griswold
First appeared 1977
Stable release 9.5.1 / June 6, 2013
Typing discipline dynamic
Website Icon
Dialects
Icon, Jcon, Unicon
Influenced by
SNOBOL, SL5, ALGOL

Icon is a high-level programming language with extensive facilities for processing strings and structures. Icon has several novel features, including expressions that may produce sequences of results, goal-directed evaluation that automatically searches for a successful result, and string scanning that allows operations on strings to be formulated at a high conceptual level. Icon also provides high-level graphics facilities. Main features of this language are generators and string scanning. Icon is not used much nowadays and it has more scientific and historic than applied value. It's successor, Unicon, is being used in real world projects and constantly develops.

History

Icon is a derivation of SNOBOL, a language originally designed by Bell Telephone Laboratories in the early 60s to promote development of string and structure intensive applications. Further implementations of Icon have been produced by The University of Arizona . The name Icon was chosen before the term "icon" became popular for GUI images in use today and does not stand for anything correlating to the language (apparently it is just a catchy name). The Latest Implementations of Icon and the Icon program library are 9.1 and 9.2, respectively. Version 9.3 of Icon and the next version of the Icon Library is scheduled for release in the fourth quarter of 1996. Platforms supported include UNIX, MS-DOS, MS-DOS 32-bit, VAX/VMS, Macintosh/MPW, and Acorn Archimedes, while versions for Microsoft Windows and NT are in beta testing. Icon can be implemented as an interpreted or compiled language. Interpreting Icon is useful for small programs, or when debugging. Compiling Icon will first translate to C code, which must then be recompiled as C.

Areas of application

  • text analysis
  • text editing
  • document formatting
  • artificial intelligence
  • expert systems
  • rapid prototyping
  • symbolic mathematics
  • text generation
  • data laundry

Expression evaluation

Conditional expressions

In Icon there are conditional expressions that may succeed and produce a result, or may fail and not produce any result. An example is the comparison operation

i > j

which succeeds (and produces the value of j) provided that the value of i is greater than the value of j, but fails otherwise. Similarly,

i > j > k

succeeds if the value of j is between i and k.

The success or failure of conditional operations is used instead of Boolean values to drive control structures in Icon. An example is

if i > j then k := i else k := j

which assigns the value of i to k if the value of i is greater than the value of j, but assigns the value of j to k otherwise.

The usefulness of the concepts of success and failure is illustrated by find(s1,s2), which fails if s1 does not occur as a substring of s2. Thus

if i := find("or",line) then write(i)

writes the position at which "or" occurs in line, if it occurs, but does not write a value if it does not occur.

Many expressions in Icon are conditional. An example is read(), which produces the next line from the input file, but fails when the end of the file is reached. The following expression is typical of programming in Icon and illustrates the integration of conditional expressions and conventional control structures:

while line := read() do
   write(line)

This expression copies the input file to the output file.

If an argument of a function fails, the function is not called, and the function call fails as well. This "inheritance" of failure allows the concise formulation of many programming tasks. Omitting the optionaldo clause in while-do, the previous expression can be rewritten as while write(read())

Generators

In some situations, an expression may be capable of producing more than one result. Consider

sentence := "Store it in the neighboring harbor" 
find("or", sentence)

Here "or" occurs in sentence at positions 3, 23, and 33. Most programming languages treat this situation by selecting one of the positions, such as the first, as the result of the expression. In Icon, such an expression is a generator and is capable of producing all three positions.

The results that a generator produces depend on context. In a situation where only one result is needed, the first is produced, as in

i := find("or", sentence)

which assigns the value 3 to i.

If the result produced by a generator does not lead to the success of an enclosing expression, however, the generator is resumed to produce another value. An example is

if (i := find("or", sentence)) > 5 then write(i)

Here the first result produced by the generator, 3, is assigned to i, but this value is not greater than 5 and the comparison operation fails. At this point, the generator is resumed and produces the second position, 23, which is greater than 5. The comparison operation then succeeds and the value 23 is written. Because of the inheritance of failure and the fact that comparison operations return the value of their right argument, this expression can be written in the following more compact form:

write(5 < find("or", sentence))

Goal-directed evaluation is inherent in the expression evaluation mechanism of Icon and can be used in arbitrarily complicated situations. For example,

find("or", sentence1) = find("and", sentence2)

succeeds if "or" occurs in sentence1 at the same position as "and" occurs in sentence2.

A generator can be resumed repeatedly to produce all its results by using the every-do control structure. An example is

every i := find("or", sentence)
   do write(i)

which writes all the positions at which "or" occurs in sentence. For the example above, these are 3, 23, and 33.

Generation is inherited like failure, and this expression can be written more concisely by omitting the optional do clause:

every write(find("or", sentence))

There are several built-in generators in Icon. One of the most frequently used of these is

i to j

which generates the integers from i to j. This generator can be combined with every-do to formulate the traditional for-style control structure:

every k := i to j do
   f(k)

Note that this expression can be written more compactly as every f(i to j) There are several other control structures related to generation. One is alternation,

expr1 | expr2

which generates the results of expr1 followed by the results of expr2. Thus

every write(find("or", sentence1) |
   find("or", sentence2))

writes the positions of "or" in sentence1 followed by the positions of "or" in sentence2. Again, this sentence can be written more compactly by using alternation in the second argument of find():

every write(find("or", sentence1 | sentence2))

Another use of alternation is illustrated by

(i | j | k) = (0 | 1)

which succeeds if any of i, j, or k has the value 0 or 1.

Procedures can be used to add generators to Icon's built-in repertoire. For example,

procedure findodd(s1, s2)
   every i := find(s1, s2) do
      if i % 2 = 1 then suspend i
end

is a procedure that generates the odd-valued positions at which s1 occurs in s2. The suspend control structure returns a value from the procedure, but leaves it in suspension so that it can be resumed for another value. When the loop terminates, control flows off the end of the procedure without producing another value.

String scanning

For complicated operations, the bookkeeping involved in keeping track of positions in strings becomes burdensome and error prone. Icon has a string scanning facility that is manages positions automatically. Attention is focused on a current position in a string as it is examined by a sequence of operations.

The string scanning operation has the form

s ? expr

where s is the subject string to be examined and expr is an expression that performs the examination. A position in the subject, which starts at 1, is the focus of examination.

Matching functions change this position. One matching function, move(i), moves the position by i and produces the substring of the subject between the previous and new positions. If the position cannot be moved by the specified amount (because the subject is not long enough), move(i) fails. A simple example is

line ? while write(move(2))

which writes successive two-character substrings of line, stopping when there are no more characters.

Another matching function is tab(i), which sets the position in the subject to i and also returns the substring of the subject between the previous and new positions. For example,

line ? if tab(10) then write(tab(0))

first sets the position in the subject to 10 and then to the end of the subject, writing the remaining characters. Note that no value is written if the subject is not long enough.

String analysis functions such as find() can be used in string scanning. In this context, the string that they operate on is not specified and is taken to be the subject. For example,

line ? while write(tab(find("or")))
   do move(2)

writes all the substrings of line prior to occurrences of "or". Note that find() produces a position, which is then used by tab() to change the position and produce the desired substring. The move(2) skips the"or" that is found.

Another example of the use of string analysis functions in scanning is

line ? while tab(upto(&amp;letters)) do
   write(tab(many(&amp;letters)))

which writes all the words in line.

As illustrated in the examples above, any expression may occur in the scanning expression.

Data Structures

Icon supports several kinds of structures with different organizations and access methods. Lists are linear structures that can be accessed both by position and by stack and queue functions. Sets are collections of arbitrary values with no implied ordering. Tables provide an associative lookup mechanism.

Lists

While strings are sequences of characters, lists in Icon are sequences of values of arbitrary types. Lists are created by enclosing the lists of values in brackets. An example is

car1 := ["buick", "skylark",  1978, 2450]

in which the list car1 has four values, two of which are strings and two of which are integers. Note that the values in a list need not all be of the same type. In fact, any kind of value can occur in a list -- even another list, as in

inventory := [car1, car2, car3, car4]

Lists also can be created by

L := list(i, x)

which creates a list of i values, each of which has the value x.

The values in a list can be referenced by position. Thus,

car1[4] := 2400

changes the last value in car1 to 2400. A reference that is out of the range of the list fails. For example,

write(car1[5])

fails.

The values in a list L are generated by !L. Thus

every write(!L)

writes all the values in L.

Lists can be manipulated like stacks and queues. The function push(L, x) adds the value of x to the left end of the list L, automatically increasing the size of L by one. Similarly, pop(L) removes the leftmost value from L, automatically decreasing the size of L by one, and produces the removed value.

Sets

A set is a collection of values. An empty set is created by set(). Alternatively, set(L) produces a set with the values in the list L. For example,

S := set([1, "abc", []])

assigns to S a set that contains the integer 1, the string "abc", and an empty list.

The set operations of union, intersection, and difference are provided. The function member(S, x) succeeds if x is a member of the set S but fails otherwise. The function insert(S, x) adds x to the set S, whiledelete(S, x) removes x from S. A value only can occur once in a set, so insert(S, x) has no effect if x is already in S. !S generates the members of S.

A simple example of the use of sets is given by the following segment of code, which lists all the different words that appear in the input file:

words := set()
while line := read() do
   line ? while tab(upto(&amp;letters)) do
      insert(words, tab(many(&amp;letters)))
every write(!words)

Tables

Tables are sets of pairs each of which consists of a key and a corresponding value. The key and its corresponding value may be of any type, and the value for any key can be looked up automatically. Thus, tables provide a form of associative access in contrast with the positional access to values in lists.

A table is created by an expression such as

symbols := table(0)

which assigns to symbols a table with the default value 0. The default value is used for keys that are not assigned another value. Subsequently, symbols can be referenced by any key, such as

symbols["there"] := 1

which assigns the value 1 to the key "there" in symbols.

Tables grow automatically as new keys are added. For example, the following program segment produces a table containing a count of the words that appear in the input file:

words := table(0)
while line := read() do
   line ? while tab(upto(&amp;letters)) do
      words[tab(many(&amp;letters))] +:= 1

Here the default value for each word is 0, as given in table(0), and +:= is an augmented assignment operation used to increment the values. There are augmented assignment operations for all binary operators.

A list can be obtained from a table T by the function sort(T, 1). The form of the list depends on the value of i. For example, if i is 3, the list contains alternate keys and their corresponding values in T. For example,

wordlist := sort(words, 3)
while write(pop(wordlist), " : ", pop(wordlist))

writes the words and their counts from the table words.

Graphic Facilities

Icon supports high-level graphics facilities:

  • Windows can be opened and closed as desired.
  • Text can be written to windows in a variety of type faces and sizes, including proportional-width faces.
  • Characters from the keyboards can be processed as they are typed.
  • Points, lines, polygons, circles, ares, and smooth curves can be freely mixed with text.
  • Colors can be used for both text and graphics.
  • Image files can be read and written.

Co-expressions[1]

A co-expression can be thought of as an independent, encapsulated thread-like context, where the results of the expression can be picked off one at a time. Let us consider an example: suppose you are writing a program that generates code, and you need something that will generate names for you. This expression will generate names:

   "name" || seq()

(seq produces an infinite sequence of integers, by default starting at 1.) Of course, an expression exists at one point in the code; we need to separate the evaluation of the expression from its textual position in the program. We do this by creating a co-expression:

   c := create ("name" || seq())

Now wherever a label name is desired, it can be obtained by activating the co-expression c:

   tempvar_name := @c

After a co-expression has produced all its results, further evaluation with @ will fail. The ^ operator produces a new co-expression with the same expression as its argument, but `rewound' to the beginning.

   c := ^c

Parallel evaluation

Coexpressions can be used to evaluate a number of expressions `in parallel' or in lock-step. We want to create a table of the ASCII characters with the hex, decimal and octal equivalents:

   dec := create(0 to 255)
   hex_dig := "0123456789abcdef"
   hex := create(!hex_dig || !hex_dig)
   oct := create((0 to 3) || (0 to 7) || (0 to 7))
   char := create image(!&amp;cset)
   while write(@dec, "\t", @oct, "\t", @hex, "\t", @char)

Every invocation of write results in all the coexpressions being activated once, so they are all run in lock-step. Parallel evaluation can also be used to assign to a set of variables:

   s := @ create !stat(f)
   every (dev | ino | mode | link |  uid | gid) := @ s

(The stat function returns information about a file.)

User-defined control structures

Since an expression (not just the value that it evaluates to) can be an argument to a procedure, coexpressions can be used to implement new control structures. Consider a control structure that selects values from the first expression at the positions specified by the second. This could be invoked as:

  seqsel([create fibonacci(), create primes()])

Assuming that we have already written generators that produce the fibonacci numbers and the primes, this expression should produce the numbers . Here is the implementation of seqsel:

procedure seqsel(a)
   (*a = 2) | stop(...)

   e1 := a[1]; e2 := a[2]
   index := 1

   repeat {
      (i := @e2 ) | fail
      every index to i do
         (value := @e1) | fail
      suspend value
      index := i+1
   }
end

Icon provides a syntactic short-cut for this kind of usage:

   proc([create e1, create e2, ..., create en])

can also be written as

   proc{e1, e2, ..., en}

Co-routines

In a convential procedure invocation scenario, the procedures have an asymmetric relationship; every time control is transferred from the calling procedure to the callee, the slave procedure starts execution at the top. Coroutines have an equal relationship: when control is transferred from one coroutine to another, it starts executing from the previous point that its execution was suspended from. This process is called resumption. The `producer/consumer problem' is a good example of procedures that have an equal relationship. Here's an example:

procedure main()
   ...
   C1 := create consumer(args...)
   C2 := create producer(args..., C1)
   @C2
end

procedure producer(args...)
   repeat {
      val := ...
      ret := val @ &amp;source
   }
end

procedure consumer(args..., c)
   value := @c
   repeat {
      # process value
      ...
      value := retval @ &amp;source
   }
end

When producer resumes consumer, it passes it a value of value; the consumer gets this value, and passes a return code (retval) back. &source is the coexpression that activated the current coexpression. Note: This should not be taken to mean that the producer/consumer problem should be done with coroutines! It is hard to find short examples that require coroutines for a clear solution.

References

  1. Coexpressions in Icon

External links

  1. Icon home page
  2. Unicon programming language
  3. http://conservancy.umn.edu/handle/11299//107697