IO(ID:4671/io:001)A language with rational continuations, inspired by Ivan Sutherland's Turing lecture, but designed with an eye towards making the clearest and simplest possible representation. Related languages
References: Introduction Many years before the first computer was built, or the first programming notation designed, Alan Turing proved that all computers, and by extension, all programming notations, are capable of solving all the same types of problems (known as computable problems). What this means in practice is that we can have almost any programming notation we want. Programming notations have been designed to support existing, familiar notations, to be appropriate for a specific class of applications, to resemble English, and countless other purposes. The author set out to design the simplest practical programming notation possible. The result is the new programming notation Io, which is described in this paper. Extract: Historical background Historical background If the complexity of a programming notation is measured by the number of mechanisms, then clearly the simplest programming notation would consist of one single mechanism. A typical pitfall of such efforts is to design a notation that is mathematically self-contained, but with no facilities for input or output. In order to use such a notation in practice, it is necessary to forcibly graft input and output commands onto the notation. In order to avoid this, it is clear that the single mechanism of the programming notation should be able to support communication with the outside world. For this reason, Hoare's Communicating Sequential Processes were considered. However, Hoare's mechanisms are rather complex and awkward, so this was ultimately rejected. It is also required, of course, that the mechanism also be able to support ordinary computations. In addition, it would be nice if it were also possible to construct large systems out of smaller components, with a mechanism similar to a procedure call. All of these requirements were reconciled with a mechanism referred to in this paper as 'performing an action.' Output is accomplished by simply performing an action corresponding to an output device. Input is accomplished by specifying an action for the input device to perform whenever it has an input value. Buffered and blocked communication can beaccomplished by adding a buffer or blocker in series with an action. Procedure call can be accomplished by specifying a 'return action' to be performed when the procedure is to return. It is a very simple mechanism, but can be assembled into patterns of any size and complexity. It is interesting that many of the important concepts in computing science show up as particularly simple patterns. Extract: Coroutines in Io Coroutines Coroutines are an important concept of computing science, but few programming notations properly support them. It is surprising how easy they are to implement in Io. The idea of coroutines is to have two (or more) routines. When one of the routines gets to a point where it can no longer proceed (such as, when it needs more input), it is suspended, and another routine continues until it, in turn, can no longer continue (such as, when it has a value to output). Then, it is suspended and another routine is resumed. This is used, for example, in creating a stream. A stream carries a sequence of numbers, without consuming storage. Therefore, it can be infinite. Even in the case of a finite stream, though, it has an advantage over a linked list, because computation can begin immediately after the first number is known. The Io implementation of streams is analogous to linked lists. A stream takes two arguments. If there is no more data in the stream, it performs its first argument. Otherwise, it performs the second argument, with a data value and the continuation of the stream. Here we define the operator count-stream, and bind an infinite counting stream to the variable s. count-streamO: ~ x out; out x ~ null out; +xl~x; count-streamO x out. count-stream: -..) ret; ret .-9 null full; count-streamO 0 full. count-stream ~ s S has exactly the same structure as a linked list. In fact, writelist s will write 0 1 2 3 4 5... on the screen. Extract: A note on implementation A note on implementation An important consideration in any programming notation is how close the mechanisms are to the implementation platform. This is mistakenly known as the speed of the notation. For example, C was originally designed partly as a fancy assembler for the PDP-11. Mechanisms such as *p++ correspond exactly to PDP-I1 instructions. Performing an action in Io is actually similar to a goto. However, passing an action as an argument is similar to closure formation. In a naive implementation, a dynamic allocation would be necessary for every time an action was used as an argument. However, even this is not too expensive, and garbage collection is not required. Because Io is such a simple notation, the prospects for a very efficient implementation are good, even without a complex compiler. It seems likely that a large proportion of the time spent by a naive implementation would be for the dynamic allocation. This can be greatly reduced by combining the space required for several (or many) closures into one dynamic allocation. It may also be possible to allocate some space in a stack, if the platform does this efficiently. Another important optimization is to code some operators in-line, rather than to code a goto or call to the operator. This is particularly important for the built-in operators. With these and other optimizations, it should be possible to implement Io at least as efficiently as other programming notations. Another intriguing possibility is the compilation of Io programs directly to hardware. The idea of performing an action is probably best implemented with transition signalling. As a matter of fact, the author got the idea for Io immediately after reading Ivan Sutherland'sTuring Award Lecture about transition signalling and micropipelines. in SIGPLAN Notices 24(12) December 1989 view details FORTRAN demonstrates that is possible to build a perfectly usable programming language with only procedure calls and conditional goto as control structures. The IO language reflects the hope that a usable programming language can result from only a single control structure: a goto with parameters. I will call the targets of these jumps procedures even though they do not return to the calling point. The parameters passed to procedures are not restricted to simple values. They may also be continuations, which represent the remainder of the computation to be performed after the called procedure is finished with its other work. Instead of returning, procedures just invoke their continuation. Continuations are explored formally in Chapter 10; here I will show you a practical use. IO manages to build remarkably sophisticated facilities on such a simple foundation. It can form data structures by embedding them in procedures, and it can represent coroutines. IO programs do not contain a sequence of statements. A program is a procedure call that is given the rest of the program as a continuation parameter. A statement continuation is a closure; it includes a procedure, its environment, and even its parameters. IO's syntax is designed to make statement continuations easy to write. If a statement continuation is the last parameter, which is the usual case, it is separated from the other parameters by a semicolon, to remind the programmer of sequencing. Continuations and procedures in other parameter positions must be surrounded by parentheses. I will present IO by showing examples from [Levien 89]. write 5; write 6; terminate As you expect, this program prints 5 6. But I need to explain how it works. The predeclared wri te procedure takes two parameters: a number and a continuation. The call in line 1 has 5 as its first parameter and write 6 terminate as its second. The write procedure prints 5 and then invokes the continuation. It is a call to another instance of write (line 2), with parameters 6 and terminate. This instance prints 6 and then invokes the parameterless predeclared procedure terminate. This procedure does nothing. It certainly doesn't return, and it has no continuation to invoke. Procedures can be declared as follows: declare writeTwice: ~ Number; write Number; write Number; terminate. That is, the identifier writeTwice is associated with an anonymous procedure (introduced by ~) that takes a single formal parameter Number (the parameter list is terminated by the first;) and prints it twice. The period, . , indicates the end of the declaration. This procedure is not very useful, because execution will halt after it finishes. Procedures do not return. So I will modify it to take a continuation as well: declare writeTwice: ~ Number Continuation; write Number; write Number; Continuation. writeTwice 7; write 9; terminate Lines 1-2 declare writeTwice, and line 3 invokes it with a 7 and a continuation composed of lines 4-5. in SIGPLAN Notices 24(12) December 1989 view details Resources
|