Icon(ID:510/ico002)String manipulation language with generator capabilitiesGriswold Indiana 1980 ICON is an imperative, procedural descendant of SNOBOL4 with a syntax reminiscent of C and PASCAL, but with semantics at a much higher level. It was written by Griswold et al to get around the GOTO-intensive style of SNOBOL. The OO extension is Idol. Icon is a general-purpose language with special features for string scanning. Dynamic types. The central theme of Icon is the generator: when an expression is evaluated it may be suspended and later resumed, producing a result sequence of values until it fails. Resumption takes place implicitly in two contexts: iteration which is syntactically loop-like ('every-do'), and goal-directed evaluation in which a conditional expression automatically attempts to produce at least one result. Expressions that fail are used in lieu of Booleans. Data backtracking is supported by a reversible assignment. Icon also has co-expressions, which can be explicitly resumed at any time. Places People: Structures: Related languages
References: in SIGPLAN Notices 14(04) April 1979 including The first ACM SIGPLAN conference on History of programming languages (HOPL) Los Angeles, CA, June 1-3, 1978 view details SNOBOL4 (Griswold, Poage and Polonsky, 1971) has an operation for mapping strings according to correspondences between sets of characters and it has pattern matching operations that deal implicitly with sets of characters. SNOBOIA, however, has no character set type per se, although typical implementations of SNOBOL4 support character sets internally (Griswold, 1972; Gimpel, 1974). The emergence of character sets in the Icon programming language (Griswold, Hanson and Korb, 1979) represents the linguistic elevation of an implementation mechanism to full status as a source language feature. The consequences of this elevation have exceeded the mechanisms for which they were originally developed, however. The character set and character mapping facilities in Icon, used in conjunction with its string processing facilities, support a number of unusual programming techniques that can be used to advantage in a variety of non-numerical programming problems. ' This paper describes the features of Icon that are important to these techniques and characterises their usage. Examples are given to illustrate the major paradigms. Extract: An overview of Icon An overview of Icon Icon is a programming language that is intended primarily for non-numerical applications with an emphasis on string processing. While Icon resembles SNOBOL4 in the level of its language features and in its support for ease of programming, it has a modem syntax and traditional control structures. An example is if el then e2 else e3 where el, e2, and e3 are arbitrary expressions. Control strdctures such as if-then-else and while-do are driven by conditional expressions that signal success or failure as in SNOBOL4. Relational expressions are typical: i f x e ythenz := xelsez := y As a result of executing this construction, z is assigned the value of x or the value of y depending on whether or not x is less than or equal to y. One iterative control structure is every el do e2 where el is a generator that produces a sequence of values. One commonly used generator is itojbyk which generates the integer values from i to j in increments of k. This generator, used in the everydo control structure, produces the effect of the familiar for statement of ALGOL: every n := i to j by k do e2 For other examples of generators, see Griswold, Hanson and Korb (1979). Icon has a large repertoire of string operations. Some representative operations are: size (s) number of characters in s sl 1 1 s2 concatenation of sl and s2 rep1 (s, i) concatenation of i copies of s s[il ith character of s substr(s,i,j) substring of s starting at i of length j String-valued keywords provide some useful constants: &case string of lower case letters &ucase string of upper case letters An Icon program is composed of a sequence of procedures. An example of a procedure is procedure max (i, j) if i > j then return i else return j end The return expression returns the value of the procedure call, as indicated. Procedures may have local identifiers. Local identifiers are ordinarily dynamic (automatic) and exist only during an invocation of the procedure. Local identifiers may be declared to be static, however, in which case they survive from one invocation of the procedure to the next. Procedures may also have an initial clause that specifies expressions to be executed on the first invocation of the procedure. Uses of these features of procedures are illustrated in subsequent examples. Extract: Character sets Character sets There are a variety of character sets in use on different kinds of computers. They differ in size, in the relationship between the internal representations of characters for control functions and external graphics, and (hence) in collating sequence. The most commonly used character sets are ASCII (American National Standards Institute, 1977), EBCDIC (IBM Corporation, 1976) and various forms of BCD (Control Cata Corporation, 1971). Internally, a character is simply an integer in the range from 0 to one less than the size of the character set. Thus in ASCII, there are 128 characters with internal representations from 0 to 127 (decimal), inclusive. Most of the programming techniques described in this paper depend on the use of characters within a program, rather than their input or output. Where graphic representations are important, upper and lower case letters are useful, but not essential. Any of the common collating sequences suffice. The size of the character set is significant, however, since in a number of applications individual characters are used to represent or label other objects. The internal character set of Icon has 256 members. This character set is independent of the size of the character set for the host computer on which Icon runs. The internal character set and the host character set are interfaced only by input and output routines. Although its character set has 256 members, *This work was supported by the National Science Foundation under Grants MCS75-01307 and MCS79-03890. The Computer Journal Volume 23 Number 2 Icon is ASCII based and the first 128 characters have ASCII interpretations. The usefulness of the remaining characters is illustrated in subsequent examples. It is assumed for ease of presentation that both upper and lower case letters are available on the host machine. This assumption is not essential, however, since Icon provides escape conventions for the literal representation of any internal character, regardless of input limitations that may be imposed by the host computer (Griswold and Hanson, 1979). Character sets in Icon, called csets for short, may have from 0 to 256 members. The value of the keyword &cset is a cset containing all 256 characters. Csets are constructed from strings using the built-in function cset(s), which produces a cset consisting of the characters in the strings. While a string may contain duplicate characters, a cset cannot, of course. Similarly, the order of characters in s is irrelevant to the resulting cset. Thus cset ('armada') cset ('ramada') cset ('drama') cset ('dram') all produce equivalent csets. Aside from type conversions, there are four built-in operations defined on csets: - c complement with respect to &set c, + + c2 union c1 ** C2 intersection c1 -- C2 difference The creation of a cset from a string may be considered to be type conversion. Conversely, a cset may be converted to a string using the built-in function string(c). In this operation, the resulting string is alphabetised, that is, the characters of c are placed in the string according to their relative position in the collating sequence. For example, alpha : = string (&cset) assigns to alpha a string consisting of all the available characters in order of their collating sequence. This string has a number of computational uses and is referred to from place to place throughout this paper. As a consequence of the properties of these conversions, the result of s2 : = string (cset(s,)) is a string s2 that contains every distinct character of s, arranged in alphabetical order. This transformation can be used to advantage, as is described in later sections. Icon also supports implicit type conversions, coercing arguments to expected type as the context demands. For example, if c, and c2 are csets, c, 11 c2 produces a string that is the concatenation of the results of converting c, and c2 to strings. in The Computer Journal 23(2) 1980 view details in TOPLAS 2(2) April 1980 view details in TOPLAS 3(2) April 1981 view details in RAIRO - Informatique, 15(2) 1981 view details Here the central concept of generators is studied in detail. Expressions which are evaluated from left to right have a two-fold result: a value and a signal, the latter being a Boolean item indicating whether the evaluation was successful or not. Flow of control is driven by signals and not by values. Generators are expressions capable of producing not only a single but a sequence of values. After having delivered a result the generator becomes dormant. A failure of a subsequent operation within an expression initiates backtracking in which dormant generators are activated in a LIFO manner to produce alternative values. The evaluation continues from the point of the reactivated generator. Backtracking only corresponds to control here; intermediate changes of the data storage, e.g., by assignments, are not reversed. If all alternatives have failed, control is transferred to the right end of the expression. The paper then explains the built-in generators, which are of enumeration or string analysis type, constructs to suppress alternatives of a generator or to force a generator through all alternatives, and programmer-defined generators. Finally, the following examples string processing, data structure traversal, and the eight queens problem are studied to show how to program in ICON. in ACM Computing Reviews 22(07) July 1981 view details in TOPLAS 4(4) October 1982 view details Introduction While it is not yet clear whether Ada, BLISS, Mary/2, Modula-2, Mesa, C, CLU, Edison, Concurrent Euclid, Icon, Newton, PLAIN, PLUS, Praxis, Smalltalk, SQURL, Y, or some other language is "best" for systems programming, each language represents an advance towards the goal of supporting an understandable and efficient organization of the many details and relationships inherent in systems programming. Unfortunately, no one language has yet achieved the delicate balance between simplicity and power that would distinguish it as ideal, but it appears that Modula-2 comes quite close. Modula-2 represents a step forward in language design, both because it incorporates existing features instead of inventing its own, and because of its evident concern for simplicity. Modula-2 offers the following valuable language features: Simplicity. Few primitive datatypes are defined, few control constructs are supported (there is no "go to"), and input-output operations are not provided as part of the language (they can be provided via extensions written in Modula-2). This simplicity allows for easier standardization and better portability than can be achieved with most other languages. Modules A module is a named collection of variables and procedures, similar to an Ada package. It controls the interfacing and encapsulation of the conceptual parts making up large software systems. Modules provide a more flexible solution to the problem of partitioning the name space of a large program than does the more familiar hierarchical nesting of procedures. They are so valuable they are even being force-fitted onto existing languages. Separate Compilation. Modules may be compiled separately, providing good management for large programsr and definition modules allow for specifying interfaces without giving implementation details. Flexible Datatypes. Strong datatypes are enforced, but this can be relaxed when necessary in systems programming to just declaring a parameter to be a word, an address, or an array of words. Machine Access. Access to specific memory addresses and other characteristics of the underlying machine is supported. Tasking. Flexible and efficient tasking is provided by coroutine management routines. in SIGPLAN Notices 17(08) August 1982 view details in IEEE Transactions on Software Engineering (TSE) 9(1) 1983 view details in Computer Languages 8(2) view details in Software — Practice and Experience 13(06) June 1983 view details in The Computer Journal 26(1) 1983 view details in Proceedings of the 1984 ACM Symposium on LISP and functional programming, , August 06-08, 1984, Austin, Texas, view details in Proceedings of the 10th International Conference on Software Engineering, IEEE Computer Society Press, 1988 view details in The Icon Analyst 7, August 1988 view details in Computing Systems 2(4)(1989) view details in Computer Languages 14(3) view details in Computer Languages 14(3) view details in Computer Languages 14(3) view details in The Computer Journal 33(2) April 1990 Special issue on procedural programming view details This paper is an application of the "literate programming" paradigm to language definition. It was generated by Eli from a specification. A complete "lint" processor for the language it defines was also generated by Eli from that specification. The generated processor detects and reports invalid tokens, syntax errors, undefined and multiply-defined identifiers, and type errors. In other words, it verifies that a program conforms to the syntax and complete static semantics of the language. When you read this paper, you are reading a complete, formal definition of a language. Nothing is left out, and nothing is left to your imagination. The formalisms used in this definition are context-free grammars, attribute grammars in the style of LIDO, and a notation for describing operator overloading. Formal definitions of various aspects of the language appear as macros embedded in the natural-language description. These embedded macros are numbered sequentially, and the numbers are used to cross-reference macro definitions and uses. Eli's library has been used to advantage in several places. For example, macros 2, 5 and 6 use "canned descriptions" to avoid the need for repeating well-known regular expressions for C basic symbols, and macro 9 invokes library routines for name analysis [7]. Error reports like the one in macro 10 are output by a library module. The definition has been tested by generating the processor and processing a suite of programs, some of which conform to the language definition and others of which deviate from it. Admittedly, the language being defined is a simple one. Its translation provides a project for an undergraduate compiler construction course in which no tools are used [11]. It illustrates an appropriate set of compilation problems without introducing uninteresting complications. How does the approach represented by this paper scale up? I can't answer that question precisely, because this paper is our first attempt at formalizing an existing natural-language definition. We do have other language definitions, but they consist solely of the formal specifications without the descriptive text. For example, a specification for Icon from which Eli generates a processor that verifies Icon programs and translates them into the standard interpretive representation consists of just over 3400 lines of text. (The translator generated from the Icon specification runs only about 15% slower than the hand-coded translator distributed by the Icon group.) Eli is a joint project of the Universities of Colorado and Paderborn. It consists of a collection of off-the-shelf tools managed by an expert system. The form of specification illustrated by this paper was made possible by our recent integration of FunnelWeb. Extract: The C-- Language The C-- Language C-- is a scaled-down version of C. The features selected illustrate basic problems for compiler designers: scanning, parsing, name analysis, overload resolution, static storage allocation and code generation. Features that merely increase the implementation effort without illustrating such techniques were excluded. This chapter defines the structure and meaning of a C-- program. It has five sections, each dealing with one aspect of the language: basic symbols and comments, program structure, declarations, expressions and statements. Basic symbols are the indivisible atoms of the language, and their meanings are defined by relating them to our shared experience with programming languages. All other constructs are composite; each is formed by combining parts. Their meanings can thus be defined in terms of the meanings of their components and fundamental concepts such as "sequence of execution". in [ACM SIGPLAN] SIGPLAN Notices 28(02) February 1993 view details in Software: Practice and Experience 22(08), August 1992 view details in Software: Practice and Experience 22(08), August 1992 view details As the name suggests, Seque is concerned with sequences. The road that leads to Seque goes roughly as follows: Generators in Icon are capable of producing sequences of alternative results. Generation usually is defined in operational terms, as in "find(s) produces all the positions at which s occurs as a substring of the subject". The results that a generator actually produces depend on the context in which the generator is evaluated; a generator only produces alternative results if it is resumed by an outer expression that needs them. In order to use sequences as a conceptual tool, it?s useful to think of the results that a generator is capable of producing, even if it does not produce all of them in a given context. This leads to the idea of result sequences [1] as an abstract characterization of sequences. An abstract characterization suggests a concrete one. Why not design a programming language in which sequences are actual first-class values? Thus, Seque was motivated by the idea of sequences as data objects that could be manipulated by a program. Seque cannot be separated from Icon. Seque builds on Icon and although Seque has it own syntax and semantics for matters related to sequences, it uses Icon control structures and expressions freely. In particular, Seque relies on Icon generators for constructing sequences. Extract: Streams Streams In Seque, sequences are called streams. There is a stream data type and numerous operations on streams. There are several ways of creating streams. The simplest stream-valued operation is analogous to the creation of an Icon list with specific values. The expression {expr1, expr2, -> exprn} creates a stream based on the values that expr1, expr2, ? exprn are capable of producing. For example, Primaries := {"cyan", "magenta", "yellow"} assigns to Primaries a stream that consists of three strings, "cyan", "magenta", and "yellow". In this simple example, each of the three expressions is capable of producing only a single value. But generators can be used when creating a stream, as in Index := {1 to 3, 6 to 9} which assigns to Index a string of seven values that is equivalent to {1, 2, 3, 6, 7, 8, 9}. Similarly, the stream Primaries could have been created by {"cyan" | "magenta" | "yellow"} Any Icon generator can be used in the construction of a stream, as in Naturals := {seq()} which creates an infinite stream consisting of the natural numbers 1, 2, 3, ? . Extract: Referencing the Elements of a Stream Referencing the Elements of a Stream An element of a stream can be referenced by its position in the stream, much like a list is subscripted by position, although the syntax is different. For example, the value of Primaries ! 2 is "magenta". An element of a stream can be changed by assignment, as in Index ! 4 := 5 which changes the stream Index to {1, 2, 3, 5, 7, 8, 9} As you?d expect, an out-of-bounds stream reference fails. Extract: The Dynamic Nature of Streams The Dynamic Nature of Streams At this point you may have lots of questions if not serious reservations. For example, it's obvious that all the values in {seq()} are not computed when the stream is formed. But it's possible to reference any element in this sequence. The underlying idea is that a stream consists of two components: a computational component that is capable of producing values and a storage component that holds values that have been computed. A newly created stream has a computational component based on the expressions specified for it, and its storage component is empty. The computational component subsequently produces elements as they are needed and their values are put in the storage component. Some consequences of this approach have serious implications. For example, Naturals ! 100000 results in the computation and storage of 100,000 integers, provided none have been computed before. If you need to do something like this in Seque, you need a platform with lots of memory. In practice, however, although it's possible to reference streams at arbitrarily chosen positions, most references are in order from the beginning. Extract: Operations on Streams Operations on Streams Seque provides several operations for creating streams from existing ones. Most of these operations are based on the mathematical properties of sequences as ordered series of values. Concatenation of streams is an obvious example, and is represented by S1 -> S2 which creates a new stream whose elements consist of those of S1 followed by those of S2. An example is Nonnegatives := {0} -> Naturals It?s also possible to form subsequences ('substreams') in various ways. Operations that can be performed on the elements of a stream also can be performed on the entire stream, as in Negatives := -Naturals Similarly, {1, 2, 3} + {10, 100, 1000} produces the stream {11, 102, 1003}. Extract: Derived Streams Derived Streams Many sequences can be represented compactly as values of a operation performed over the positive integers. For example, the cubes of the positive integers, 1, 8, 27, ... Can be represented by I 3 I = 1, 2, 3, ... Seque supports such derived streams, using square brackets to enclose the operation, as in Cubes := [i ^ 3] which assigns to Cube a stream consisting of the cubes of the positive integers. The bound variable i is distinguished in such contexts and is implicitly associated with the natural numbers. Seque provides ways of specifying different underlying streams and other bound variables. Extract: Other Features Other Features Seque has many other features; too many to describe in detail here. But we'll mention a few that are important. Streams, like data structures in Icon, can be heterogeneous and contain values of different types. Since streams are first-class data values, the elements of a stream can be other streams. As indicated above, streams can be infinite. Seque also provides a way to declare recurrence relations that can be used to create streams. Seque has several functions that operate on streams. For example, Copy(S) produces a copy of the stream S and Simage(S, i) produces a string image of S limited to I elements. See References 2 and 3 for more information about Seque's computational repertoire. Extract: Implementation Implementation Since Seque is a subset of Icon, you might expect it to be implemented on top of Icon. It is, in a sense, but not as extension of the implementation of Icon itself. Instead, a variant translator [4] translates a Seque program into an Icon program, which is linked with a library of Icon procedures that perform run-time operations. For example, the Seque expression {1 to 3, 6 to 9} is translated into stream([ ], create (1 to 3) | (6 to 9)) where stream() is a record constructor for the declaration record stream(store, compute) Thus, the storage component is an empty list initially and the computational component is a coexpression, which, when activated, produces the elements of the stream which then are pushed onto the list. This makes the implementation sound simple. In fact, it?s complex and must deal with many difficult conceptual problems. For example, all Icon operations can be applied to streams as well as to the types to which they can be applied in Icon. The variant translator converts an operation into a call of a procedure that handles the details. To give you an idea of what's involved, 'x is translated into Unop_("?", x), where Unop_() is a Seque library procedure that implements unary operators. The procedure looks roughly like this: procedure Unop_(op, arg) if type(arg) ~== "stream" then suspend op(arg) else return stream( [ ], create op(|@^arg.compute) ) end If arg is not a stream, op is applied to it using string invocation, being careful to suspend, since op might be a generator. Otherwise, a new stream is created with an empty list. The computational component of this stream is more complicated. A refreshed copy of the co-expression from arg is created so that the two streams will be independent. The expression op(|@^arg.compute) repeatedly activates this new co-expression and applies op to the results. The create constructs a co-expression for the computational component of this new stream. If you're not an expert on co-expressions, don't worry about the details. We have an upcoming article for the Analyst that will help illuminate such arcane matters. Extract: Conclusions Conclusions The implementation of Seque is what's called a 'proof-of-concept' implementation (a term we detest, since it's a euphemism that often is used to make failed work sound credible). The use of a variant translator in combination with a library of Icon procedures allowed experimentation with language design with a manageable amount of effort. Although Seque worked, it was only used by a handful of local persons. We declined outside requests for Seque, since we lacked the resources to package, distribute, and maintain such an implementation. It's been some seven years since we used Seque ourselves. We didn't know Seque was really lost until we started to write this article and could find only traces of it - the procedure library, but not the variant translator, and only a few small test programs. It appears that in a combination of comings and goings of the persons involved, as well as a coincident change in our local computer system, most of the original files were lost. It is one of those "I thought you had it. Gee, no, I thought you did" situations. That's why there are no examples of Seque programs here. Maybe it's just as well that Seque is lost. We're spared an attempt to rehabilitate old software. But we not-so-secretly wish we could run Seque and see if programming with sequences really is useful. in Software: Practice and Experience 22(08), August 1992 view details in [ACM SIGPLAN] SIGPLAN Notices 28(03) March 1993 The second ACM SIGPLAN conference on History of programming languages (HOPL II) view details in [ACM SIGPLAN] SIGPLAN Notices 28(03) March 1993 The second ACM SIGPLAN conference on History of programming languages (HOPL II) view details in Software - Practice and Experience 23(04) April 1993 view details in Computer Languages 18(4) view details in Software — Practice and Experience 24(11) November 1994 view details in Software — Practice and Experience 24(11) November 1994 view details in Software — Practice and Experience 24(11) November 1994 view details in Software — Practice and Experience 24(11) November 1994 view details in Software — Practice and Experience 24(11) November 1994 view details Resources
|