Seque(ID:1433/seq002)Experimental language for manipulating sequencesExperimental language for manipulating sequences Places Structures: Related languages
References: in The Icon Analyst 7, August 1988 view details in The Icon Analyst 7, August 1988 view details INTRODUCTION INTRODUCTION Many programming problems deal with values that are produced in sequence by some computational process. The most common of these, perhaps, is processing the lines of a sequential file in order. Other examples of sequences include the values produced by recurrence relations and the values of physical quantities sampled at time intervals. While many sequences of values are finite, others are potentially infinite or are most easily characterized in unbounded terms. These considerations motivate programming language facilities for dealing with sequences. Several programming languages have been designed for dealing with sequences, or "streams" as they are often called [1-4]. The programming language described here, Seque, treats streams in a more central and general way than previous languages and concentrates on the direct manipulation of streams. In Seque, streams are first-class data objects. There are several ways of creating streams, numerous operations on them, and various ways of producing their elements. Such streams can be finite or infinite. Streams also can be elements of streams, allowing the construction of stream hierarchies. A stream in Seque can be viewed as a composite of elements that have already been produced and elements that may be produced. In this sense, streams have a storage component and a computational component. The storage component of a stream corresponds to ordered structures such as lists, arrays, and vectors that are supported by most programming languages. Such structures can be referenced by position. The computational component of streams in Seque is based on the expression evaluation mechanism of the Icon programming language [5-7], in which a generator is capable of producing a sequence of results as demanded by context. This aspect of streams is fundamental to the material that follows, which assumes a familiarity with Icon. Seque has been implemented by imbedding its features in Icon. The result is a prototype for a native implementation, but it is nonetheless fully functional. Many programming problems deal with values that are produced in sequence by some computational process. The most common of these, perhaps, is processing the lines of a sequential file in order. Other examples of sequences include the values produced by recurrence relations and the values of physical quantities sampled at time intervals. While many sequences of values are finite, others are potentially infinite or are most easily characterized in unbounded terms. These considerations motivate programming language facilities for dealing with sequences. Several programming languages have been designed for dealing with sequences, or "streams" as they are often called [1-4]. The programming language described here, Seque, treats streams in a more central and general way than previous languages and concentrates on the direct manipulation of streams. In Seque, streams are first-class data objects. There are several ways of creating streams, numerous operations on them, and various ways of producing their elements. Such streams can be finite or infinite. Streams also can be elements of streams, allowing the construction of stream hierarchies. A stream in Seque can be viewed as a composite of elements that have already been produced and elements that may be produced. In this sense, streams have a storage component and a computational component. The storage component of a stream corresponds to ordered structures such as lists, arrays, and vectors that are supported by most programming languages. Such structures can be referenced by position. The computational component of streams in Seque is based on the expression evaluation mechanism of the Icon programming language [5-7], in which a generator is capable of producing a sequence of results as demanded by context. This aspect of streams is fundamental to the material that follows, which assumes a familiarity with Icon. Seque has been implemented by imbedding its features in Icon. The result is a prototype for a native implementation, but it is nonetheless fully functional. Extract: Summary Summary The Seque programming language is motivated by situations in which sequences of values are natural objects for computational manipulation. In Seque, streams are data objects corresponding to such sequences. Streams can be infinite and heterogeneous with respect to type. Since streams are data objects, there can be streams containing streams. A stream has both a storage component, which corresponds to values that have been computed, and a computational component from which new values can be produced. Streams in Seque can be constructed by specifying their values explicitly or in terms of expressions that produce the values in a variety of ways. Derived streams, in particular, provide a concise way of representing many commonly encountered sequences. Streams corresponding to recurrence relations can be written in the form the relation is given. Icon, as the base language, contributes in a significant way both to the power and to the character of Seque. Icon's string-processing repertoire makes it easy to deal with streams of strings. More importantly, Icon's expression evaluation mechanism, in which an expression may produce a sequence of values, meshes naturally with the concept of streams. in Computer Languages 13(1) 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 Computer Languages 13(1) view details |