DIPSY

[ Bristol CS | Index ]

DIPSY: A Declarative Internet Programming System

Background of the research

The study of concurrent and distributed programming has become dramatically more important in recent years, thanks largely to the rapidly increasing use of computer networks. Examples of distributed systems, comprising multiple processes interacting via the Internet, are now ubiquitous. At the same time, programming distributed systems is an inherently more difficult task than conventional sequential programming, in respect of both correctness (to achieve correct synchronization) and efficiency (to minimize slow interprocess communication).

Most current Internet applications are simple client/server systems, such as World Wide Web browsers and servers. However, as the technology matures, more complex applications are likely to be developed. This will increase the demand for programming languages and systems that ease the task of constructing correct, reliable, and efficient distributed software. Declarative programming languages are well placed to fulfil this need. For example, languages like KL1 and Parlog already provide a high-level concurrent programming style and can be implemented efficiently on many platforms.

Tempo (Gregory and Ramirez, 1995; Gregory, 1996; 1997) is a new declarative concurrent programming language that has much in common with KL1 and Parlog, but several key differences:

Tempo is significantly more declarative: programs explicitly describe the execution times of events, as well as values, instead of relying on control features like modes, sequential operators, etc. This means that all safety properties are preserved by parallel execution, transformation, etc.
The language provides a novel constraint-oriented programming style: programs are composed by conjoining (temporal) constraints on the execution times of events.
Constraints in a program can be optionally grouped into processes. This does not affect the observable behaviour of the program, but constraints in different processes are solved independently, with shared events representing interprocess communication.

A prototype implementation of Tempo exists as an interpreter written in Parlog, and has been widely distributed.

References

Gregory, S. and Ramirez, R. 1995. Tempo: a declarative concurrent programming language. In Proceedings of the 12th International Logic Programming Conference, L. Sterling (Ed.). MIT Press, pp. 515-529.

Gregory, S. 1996. Derivation of concurrent algorithms in Tempo. In Proceedings of the 5th International Workshop on Logic Program Synthesis and Transformation, M. Proietti (Ed.). Springer-Verlag, pp. 46-60.

Gregory, S. 1997. A declarative approach to concurrent programming. In Proceedings of the 9th International Symposium on Programming Languages, Implementations, Logics, and Programs, H. Glaser (Ed.). Springer-Verlag.

Purpose of the research

The aim of the proposed research is to design and implement a programming language suitable for the construction of distributed Internet applications in a declarative style. This language will be based on Tempo, which should be an ideal starting point, for the following reasons:

The constraint-oriented programming style allows processes to be "plugged together" simply by conjunction, without changing their definitions; this is a major advantage if they are running on different processors.
The language follows the Linda principle of distinguishing between fast local (intraprocess) communication and slower remote (interprocess) communication; this distinction will be crucial to efficient implementation. (Some implementations of concurrent logic programming (e.g., distributed KLIC and KL1 on PIMs) allow the programmer to specify that a goal should run on a remote processor, but it is then impossible in general to predict which variables are shared between processors.)

The specific aims of the research are to design and implement features that are currently lacking from Tempo. For example:

An ability to execute Tempo processes on different Internet hosts.
Language features to perform input and output, particularly with processes running on other Internet hosts.
Real-time programming features, which are essential for Internet programming.
Language features for mobile software.

Contents of the research

The research will consist of designing new language features and implementing them, and finally testing them on appropriate applications.

As a testbed for the language extensions, we will convert the existing Tempo implementation, which is written in Parlog, to KLIC. KLIC is an ideal vehicle for this purpose because (like Parlog but unlike C or Java, etc.) it provides the symbolic concurrent programming facilities that Tempo inherits from logic programming. In addition, KLIC is extremely fast, powerful, and robust; it provides an interface to C programs; it has built-in procedures to perform TCP/IP communication via sockets; and it can easily be extended if required.

The language features will then be designed and implemented as follows.

Internet process location
Tempo already allows constraints to be grouped into processes, each solved by a separate concurrent invocation of the sequential Tempo interpreter. The interpreters communicate by means of a message passing protocol to execute events shared between them. The language extension required here is simply an annotation to allow a process to be spawned to another Internet host. For example, suppose that a WWW server is defined as a constraint webserver(M) where M is an event structure containing URLs and files sent in reply. We could then define an alternative "load balancing" server lb_webserver(M), which forwards some of the requests received to a server running on another local host named www2:
```
   lb_webserver(M) :-
      split(M,M1,M2), webserver(M1), {webserver(M2)}@www2.
```
The main effort required here will be in implementation. When a Tempo process is spawned, it must be sent to the specified host together with the definitions of all constraints appearing in the process. Shared events (e.g., M in the example) will be represented by global names and executed by TCP/IP communication between the hosts that share them. Work will be needed to design the architecture of the distributed Tempo system, especially to handle the case where KLIC or C code needs to be sent with a process.
Input/Output
Most Internet applications are actually "open systems": the processes involved are not all part of a single program (as above). A process may need to interact with an unknown process which may be written in a completely different language, provided that it uses a standard protocol. Tempo currently lacks any facilities for I/O, so we will need to design language features to interface between programs and their environment. This includes interaction with the terminal and disk files etc., but particularly processes running on other Internet hosts.
The natural way to handle I/O in Tempo is by event structures shared with I/O constraints representing the environment (analogous to KLIC's use of streams shared with the klicio predicate). A TCP/IP stream socket, for example, may be represented in Tempo by two linear event structures I and O, in which each event is labelled by a single byte, that satisfies a constraint like socket(I,O). For example, an echo server might be defined in Tempo as a constraint copy(I,O):
```
   :- socket(I,O), copy(I,O).
   copy(I,O) :- I << O, O^:=I^, copy(I#1,O#1).
```
The I/O constraint socket has no logical meaning: it just represents the unknown constraint provided by the environment. However, there is a logical meaning if the process to which the socket is connected happens to be programmed in Tempo. For example, if the above socket is connected to another Tempo process defined as
```
   :- socket(I1,O1), c(I1,O1).
```
then, because of the asynchronous communication between the sockets, we have the implicit constraints copy(O,I1), copy(O1,I), so the meaning of the two processes combined is
```
   :- copy(I,O), c(I1,O1), copy(O,I1), copy(O1,I).
```
The three copy constraints imply, inter alia, that O1 << I1. So, for example, it is easy to see that replacing c(I1,O1) by I1 << O1 would lead to deadlock. In most languages, this would only be detected at run-time or by a complicated proof.
Real-time programming
Basic concurrent programming languages control only the order of execution of events and whether events eventually happen. However, many interactive applications, including those that we have in mind, deal with an unpredictable environment; then it is necessary to provide some notion of real time.
The execution time of events is a first class entity in Tempo, so it should be natural to extend the language to handle real time. For example, consider a constraint interface(I,O) which passes requests received on I} to the output O}, and copies replies received on O#2 (the second offspring of O) to I#2. This could be defined as
```
   interface(I,O) :-
      I << O, O^:=I^, O#2 << I#2, I#2^:=O#2^, interface(I#1,O#1).
```
To introduce a timeout, such that a reply `NO REPLY' is given on I#2 if no reply is received on O#2 within five seconds of the request, the above definition could be modified to something like the following (where I!} denotes the execution time of I):
```
   interface(I,O) :- I << O, O^:=I^,
      ( O#2 << I#2, I#2^:=O#2^, interface(I#1,O#1);
        after(I!+5 sec,I#2), I#2^:='NO REPLY', interface(I#1,O#1) ).
```
Mobile software
A more speculative extension to the language would allow a process to transmit software, in the form of Tempo constraints, to other existing Tempo processes to execute. This has obvious applications, such as to perform a search on a remote machine and send the results back to the original client process. As well as the above, this would also require some higher-order feature, so that Tempo constraints can be handled as first-class objects in the language. More research on this subject, and investigation of existing (non-declarative) mobile software languages, will be required before the language design can be finalized.

Resulting Software: DIPSY

The Tempo implementation produced during the course of the research will be made available as a toolkit, named DIPSY, which will allow the construction of distributed Internet applications in a declarative manner.

Tempo programs define temporal constraints, which are relations between the execution times and values of event structures. Computation is performed by function constraints} and test constraints, which are simply relations between data values (numbers, strings, etc.), and can be defined in any (preferably declarative) language. In DIPSY, the test and function constraints will be defined in KLIC. Primitive constraints like `+' and `<' will be built into the system, but others can be defined by the programmer in KLIC (and hence also in C).

The first version of the DIPSY system (DIPSY-1) will be a single program that executes programs in Tempo (extended with I/O and real-time programming features). Since it will be an interpreter, Tempo programs can be created dynamically, but KLIC and C code called from Tempo programs will need to be compiled and linked with the DIPSY system in advance. This system will be able to interact with other Internet processes, including other invocations of DIPSY itself.

The intermediate version of DIPSY (DIPSY-2) will be a basic distributed system featuring the Internet process location feature. This will be able to spawn processes on other (properly configured) Internet hosts by sending them the processes' constraints together with their defining code. To simplify the implementation, any KLIC and C code must have been compiled and linked with the DIPSY system on every host, in advance of execution.

In the final version of DIPSY (DIPSY-3), all of the code needed by a process, including KLIC and C code, will be sent to the remote host at the time the process is spawned. This version will also include full mobile software features.

The DIPSY system will be distributed as a set of KLIC source files, which can be compiled to produce executable programs on any machine that will run KLIC programs.

DIPSY-1 will comprise a single program that executes extended Tempo programs. If user-defined KLIC/C code is to be used, the user's KLIC/C source programs must first be compiled and linked with the DIPSY system.

The distributed versions, DIPSY-2 and DIPSY-3, will each comprise two executable programs:

An interactive front-end program which allows the user to supply programs written in Tempo (and KLIC and C, in the case of DIPSY-3), and enter Tempo queries to be executed.

A server program running as a demon on any hosts on which the user wishes to run Tempo processes. The server will receive Tempo processes (the constraints and the code that defines them) in an encoded form, and execute them, communicating with other hosts when necessary to execute shared events.

The server will be significantly more complex in DIPSY-3 than in DIPSY-2, since KLIC/C code may be included with the processes. The server will then need to dynamically compile and link the KLIC/C code and invoke a Tempo interpreter as a new Unix process to execute the new process.

Advantage of the software from users' point of view

DIPSY will provide an easy way to construct correct, reliable distributed Internet applications:

The underlying Tempo language is extremely simple and uniform. The syntax is that of logical clauses, with no implicit control language. Processes are just groups of constraints, and communicate via shared events. This is much simpler than the plethora of low-level details that need to be mastered in order to program similar applications in C, for example.
Tempo is declarative in the sense that safety properties of a program are explicit in the program itself. This makes it easier to develop a program that satisfies the intended specification, increasing the chances of correctness. One application of this will be in teaching: it will be possible to demonstrate the benefits of the declarative programming approach on "interesting" applications, rather than the toy algorithms usually used.
Tempo can be viewed as a coordination language, to compose processes (written in KLIC/C) that perform the actual computation. This means that existing code can be reused. The only additional effort required from the programmer is to write the top-level coordination code in Tempo, but even this should be easier than using a conventional language to do the same job.
Applications produced using DIPSY should be reasonably efficient in terms of speed. Although the sequential Tempo interpreter has not been optimized, Tempo code will probably only be used at the top level of a program, to coordinate processes. Because coordination involves inherently slow network communication, the sequential execution speed of Tempo will have little impact on the overall speed of the application.