SL5(ID:783/sl:001)String and list processing language with expression-oriented syntax. Coroutines. Places People: Structures: Related languages
References: in [ACM SIGACT-SIGPLAN] Proceedings of the 3rd ACM SIGACT-SIGPLAN Annual Symposium on Principles of Programming Languages (POPL) 1976 view details in [ACM] Proceedings of the annual ACM conference 1976 , Houston, Texas, United States view details in [ACM] Proceedings of the annual ACM conference 1976 , Houston, Texas, United States view details in Fifth Texas Conf. on Comptng. Syst., Oct. 1976 view details in Fifth Texas Conf. on Comptng. Syst., Oct. 1976 view details in Fifth Texas Conf. on Comptng. Syst., Oct. 1976 view details in Fifth Texas Conf. on Comptng. Syst., Oct. 1976 view details in SIGPLAN Notices 12(04) April 1977 view details in Computer Languages 3(3) view details in [ACM] CACM 21(01) (January 1978) view details External link: Online copy in The Computer Journal 21(2) May 1978 view details This clearly written and easy to understand paper is recommended for all programming language designers. The design principle of SL5's procedure mechanism is to provide primitives, not packages—a principle which is laudably gaining prominence in language design circles. One possible adverse effect of SL5's procedure primitives, not discussed in this paper, is the invitation to use unstructured coding techniques. In particular, procedures can return control to arbitrary invocation environments (not just to the calling environment), and the use of global variables appears to be almost encouraged. SL5's procedure mechanism is briefly compared to those of LISP, CONNIVER, GEDANKEN, and SIMULA 67. A more substantial exposition, with more examples, is desirable. M. S. Johnson, San Francisco, Calif. in ACM Computing Reviews 20(08) August 1979 view details in RAIRO - Informatique, 15(2) 1981 view details Background As you probably know, Icon is only the latest in a series of programming languages. It all started in 1962 at Bell Labs with the development of a language called SNOBOL [1], which was designed to make it easier to manipulate symbolic information represented by strings of characters. There were three successive SNOBOL languages, culminating in 1968 with SNOBOL4 [2], which added sophisticated data structures. Further work on this kind of programming language moved to The University of Arizona in 1971. This work first used SNOBOL4 as a basis for a number of experiments [3-5]. Eventually, the structure of SNOBOL4 became too limiting, which led to the design of an entirely new programming language called SL5 ("SNOBOL Language 5"). The name, although barely disguising its origins, was chosen to avoid the impression that the new language was just a variant of earlier SNOBOL languages. SL5 was, in fact, very different from its SNOBOL ancestors, although it contained many ideas derived from them. If you?re familiar with SNOBOL4, you?ll see both differences and similarities between SNOBOL4 and SL5 in what follows. Whether or not you know SNOBOL4, you?ll see what preceded and shaped Icon. SL5 eventually became a large language in the sense of having many features and a large computational repertoire [6-10]. We won?t attempt to cover all of SL5 here. Instead we?ll focus on the highlights and those features that are most relevant to Icon. Extract: Basic Features Basic Features Most imperative programming languages (including SNOBOL4) have both expressions (that produce values) and statements (that do something but don?t produce values). SL5, on the other hand, has only expressions, although some of them look like statements. Thus, in SL5 if expr1 then expr2 else expr3 is an expression and it produces a value (the value of expr2 or expr3, depending on which is selected). Icon inherited this way of casting computation. Like SNOBOL4, SL5 stresses run-time flexibility. Structures are created at run-time, the meaning of operations can be changed at run-time, and so on. Not surprisingly, SL5 also has automatic storage management with garbage collection to reclaim space when needed. None of these features is unusual. The unusual features of SL5 are its method of controlling program flow, the way it deals with various aspects of procedures, and its approach to pattern matching. Extract: Control Structures Control Structures In order to understand control structures in SL5, it is helpful to know how flow of control is handled in its predecessor. In SNOBOL4, the execution of a statement may succeed or fail, an idea that originated in COMIT [11]. SNOBOL4, however, does not have conventional control structures like if-then-else and while-do. Instead it has conditional gotos that allow program execution to be directed to different statements depending on the success or failure of the current one, as in IDENT(X, Y) :S(YES)F(NO) In SNOBOL4, success and failure are termed signals. These days gotos are deprecated because of the unstructured, confusing, and error-prone styles of programming that they allow. Furthermore, the absence of conventional control structures in SNOBOL4 makes it necessary to construct even simple loops using gotos and labeled statements. One of the goals of SL5 was to support conventional control structures while preserving the useful concept of signals. In SL5, an expression produces a result that contains both a value and a signal. A result is constructed by the expression v&s, where v is the value and s is the signal. Signals are nonnegative integers and are used in control structures to affect the flow of control. The signal 0 corresponds to failure and any positive signal (normally 1) corresponds to success. For example, the operation i > j produces the signal 1 if i is greater than j but the signal 0 otherwise. In if i > j then expr1 else expr2 the signal produced by i > j determines whether expr1 or expr2 is evaluated. Thus, SL5 avoids Boolean values and allows any kind of expression to be a control expression ? an idea that has been further refined in Icon. SL5 allows a result to be composed from a value and any nonnegative integer signal. The signal component of a result also can be extracted to become a value. Extract: Procedures Procedures The most interesting aspect of SL5 is the way that it deals with programmer-defined procedures. Procedures are created at run-time, as illustrated by gcd := procedure(I, j) while I ~= j do if I > j then I := I ? J else j := j ? I; return I end; Note that a procedure value is assigned to gcd. Such a procedure then can be called in the conventional manner, as in k := gcd(47, 25); Procedure invocation in most programming languages is an atomic operation as illustrated in this example. In SL5, however, procedure invocation can be decomposed into three separate operations: ? Creation of an environment for the procedure ? Binding of arguments to the environment ? ?resuming? The environment to execute the code for the procedure The expression e := create p creates an environment for the procedure p and assigns it to e. (The create operation here is not directly related to Icon?s create for co-expressions.) Arguments are bound (transmitted) to an environment by e with (expr1, expr2, ?, exprn) where expr1, expr2, ?, exprn are evaluated and their values are bound to e. That is, they become the values of the formal parameters of p in e. Finally, the execution of p is initiated with resume e All this is not necessary if all you want to do is call a procedure and get its result back. However, the decomposition of procedure invocation allows more sophisticated use of procedures, as illustrated by the following procedure: genlab := procedure(prefix, i) repeat { return prefix || I; I := I + 1 } end; This procedure might be used as follows: label := create genlab with ("L", 1); … top := resume label; … bottom := resume label; … which assigns L1 to top and L2 to bottom, respectively, assuming there are no intermediate resumptions of label. The crucial point here is that when a procedure returns, its environment remains intact and it can be resumed to continue execution. New arguments can be passed to the environment, as in label with ("P", 100); to change the values produced on subsequent resumptions. It?s easy to see how SL5?s resumption mechanism accomplishes what Icon does with suspend. SL5 is, however, more general than Icon ? Any suspended environment can be resumed at any time. SL5?s return mechanism also is more general than Icon?s. In SL5, it is not necessary for a procedure to return control to the procedure that resumed it. The general form of return in SL5 is return r to e where r is the result (value and signal) to be returned and control is transferred to e, which can be any environment. If you?re familiar with coroutines, you?ll recognize that SL5 provides a very general coroutine mechanism in which many procedure environments can be in existence at any one time and in which control can be transferred among them in any order. A few more aspects of procedures in SL5 need to be mentioned before we go on to other parts of the language. As you?ve probably guessed from the examples above, if no signal is specified in return, 1 (for success) is supplied by default. There also are two abbreviations that make programs easier to read: succeed v is a synonym for return v&1 and fail v is a synonym for return v&0 In both cases, if v is omitted, the empty string is returned. (In SL5, the empty string serves a role similar to that of the null value in Icon.) Identifiers in SL5 can be declared to be global, private, or public. The declaration global has the same meaning as it does in Icon; such identifiers are available throughout a program. Similarly, private is equivalent to local in Icon; such identifiers are available only within a single environment. The public declaration is more interesting. It provides the interpretation of undeclared identifiers. The meaning of an undeclared identifier is determined when an environment is created. This is done by searching for public identifiers in the ancestors of the environment in which the creation is done. An example that illustrates the usefulness of this kind of scoping is given in the section on data structures. Extract: Filters Filters SL5 built on the SNOBOL4 idea of attaching procedural components to variables. The underlying idea is that it's often useful to have something done automatically when a value is assigned to a variable or when a variable is dereferenced to get its value. This is particularly useful in reading and writing. When a value is assigned to out in SL5, that value also is written. For example, out := "Hello world"; writes Hello world. Similarly, when the value of in is used, a new line of input is read and becomes the value of in. If there is no more input, the reference to in fails. Thus, while out := in; copies input to output. In addition to such built-in associations, SL5 allows filters to be associated with variables in two ways: assignment and dereferencing. Filters are simply environments that are resumed automatically when a variable is referenced. A filter for dereferencing is associated with a variable by v :? ? e and a filter is associated with a variable for assignment by v :? e As many filters as are needed can be attached to a variable; they are processed in the order that they are attached. Since filters are environments, filtering actions can be written using procedures. The arguments of a filtering procedure are the value and signal of the result being filtered. For example, to restrict the values assigned to count to positive integers, the following procedure could be used: procedure posint(v, s) repeat if ident(datatype(v), "integer") and v > 0 then return v&s else return v&0 end; ... count :? ? create posint; Positive integers pass through this filter unchanged. Other values are passed through with a failure signal. If the failure signal reaches the assignment, the assignment is not performed and the assignment expression fails. The procedure above reveals some other aspects of SL5; you should be able to figure out their meanings. Filters also can be used in passing values to environments. The default argument transmission method is by value, as in Icon. Values also can be passed by reference. The method of transmission is specified in the procedure heading, as in procedure p(i, x:ref) in which i is passed by value and x is passed by reference. Programmer-defined filters also can be used in argument transmission. For example, to assure that the procedure gcd given earlier is called only with positive integer values, all that?s needed is gcd := procedure(i:posint, j:posint) … Extract: String Scanning String Scanning String scanning in SL5 resembles both pattern matching in SNOBOL4 and string scanning in Icon. It is closer to SNOBOL4 in that SL5 environments, like SNOBOL4 patterns, are data objects that embody scanning operations, while in Icon, scanning operations are applied directly. SL5 has a number of functions and operators that build scanning environments. For example, in pet := ="dog" | ="cat" the alternation operator creates an environment that matches either "cat" or "dog". Subsequently, animal ? pet applies this environment to animal. Other environment constructors include e1 ? ? e2 concatenation of e1 and e2 move(i) move i characters tab(i) move to character i break(s) move up to character in s span(s) move past characters in s The SNOBOL4 and Icon analogies should be obvious. The difference between SL5 and Icon is that in SL5, these expressions create environments; they do not perform any scanning. Scanning occurs when an environment is resumed in a scanning expression. Like patterns in SNOBOL4, however, environments can be combined to form more complex environments. SL5 distinguishes between accepting strings during scanning and synthesizing strings as a result of scanning. Thus, move(i) creates an environment that accepts i characters, but it does not contribute to the result of scanning. The environment created by =move(i), on the other hand, contributes the characters accepted to the result of scanning. SL5 has four public scanning variables: subject string being scanned cursor position in subject scanlength length of subject scanvalue current synthesized result Since SL5 uses environments in string scanning, programmer-defined procedures can be used in scanning. An example is a procedure to pad the result of synthesis to a fixed number of columns: synpad := procedure(i, c) private s; s := scanvalue; scanvalue := rpad(scanvalue, i, c); succeed; scanvalue := s; fail end; Note that the previous value of scanvalue is saved so that it can be restored if synpad() is resumed (as the result of the failure of a subsequent scanning environment). Extract: Data Structures Data Structures It may not surprise you at this point to learn that SL5 also uses environments for programmer-defined data structures. Records are easy, since the identifiers in an environment can be accessed as 'fields' of the environment. For example, a procedure for use with employee records might be employee := procedure(name, age, salary) end; Then hire := create employee; creates an environment, and values can be assigned to its fields as in hire.name := "John Smith"; hire.age := 35; hire.salary := 32500.0; It would be syntactically neater if this could be written as a procedure call: hire := employee( "John Smith", 35, 325000.0) However, since hire needs to be an environment, it is necessary for employee() to return its own environment. This is done using the keyword &self: employee := procedure(name, age, salary) return &self end; To use environments for more complicated data structures, it usually is necessary to perform some initialization before returning &self. For the example above, an additional field might be added for the tax rate: employee := procedure(name, age, salary) private taxrate; taxrate := rate(salary); return &self end; Stacks provide a more interesting example of a programmer-defined data structure: stack := procedure private push, pop; public stk; push := create procedure(x) repeat { stk := node(x, stk); return x } end; pop := create procedure private t; repeat if ident(stk) then fail else { t := stk.value; stk := stk.link; return t } end; return &self end; Here a stack is composed of a linked list of nodes, which are records with two fields, value and link. A stack is created by parse := stack(); The fields push and pop are procedures, so that parse.push(x) pushes x onto parse, and x := parse.pop(); pops a value off of parse and assigns that value to x unless parse is empty, in which case parse.pop() fails. Note that the public identifier stk in stack() provides the interpretation for the undeclared identifiers stk in pop and push, so that they apply to the stack for parse. Extract: Conclusions Conclusions Writing this article has been an interesting experience for us. It's been years since we've given a serious thought to SL5, and we had to forage through old documents to produce the description we've given here. In retrospect, SL5 has many interesting features. (We've only described the main ones here; there's a lot more to SL5). Not surprisingly, on rediscovering some of the features of SL5, we thought 'Gee, those would be neat things to have in Icon.' But Icon has grown large. If there?s anything we think language designers should do is avoid the temptation to 'kitchen sink' (to coin an abominable verb from a noun). Not everything in SL5 is good. It's very general procedure mechanism is appealing, but it's also somewhat overbearing and, because of its generality, inefficient. For better or worse, SL5 was abandoned in favor of Icon, simply because we did not have the resources to support two languages. And SL5 really is dead ? Or so we think. It was implemented only for the DEC-10 and CDC 6000 and we no longer have the code. But who knows what's on a dusty tape in some forgotten cabinet? Although SL5 is gone, it served a useful purpose. It led to Icon and has influenced the design of other programming languages. The most notable of these is EZ [12], a very high-level language with a persistent memory that permits it to double as a programming environment. in RAIRO - Informatique, 15(2) 1981 view details |