DFPL(ID:6538/dfp001)Pure graphical dataflow languagefor Data Flow Programming Language Kosinki's dataflow language Related languages
References: DOI in SIGPLAN Notices 8(09) June 1973 Proceedings of ACM SIGPLAN - SIGOPS interface meeting on Architectural Support for Programming Languages and Operating Systems, Savannah, Georgia, 1973 view details in SIGPLAN Notices 8(09) June 1973 Proceedings of ACM SIGPLAN - SIGOPS interface meeting on Architectural Support for Programming Languages and Operating Systems, Savannah, Georgia, 1973 view details in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details DOI in [ACM SIGACT-SIGPLAN] Proceedings of the 3rd ACM SIGACT-SIGPLAN Annual Symposium on Principles of Programming Languages (POPL) 1976 view details in [ACM SIGACT-SIGPLAN] Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages 1978 , Tucson, Arizona view details Introduction In this thesis we are concerned with issues arising from the need to achieve concurrency of operation within a computation on a large scale. Several factors contribute toward increasing interest in systems capable of exploiting the concurrency of computation. Concurrency provides the potential for performance improvement through concurrent operation of hardware components such as processors and memory modules. This results in better utilization of total resources and in faster response if a computation has a high level of concurrency. The dramatic progress of technology has made concurrent systems more attractive as an alternative for high performance systems. In particular, systems that have many replicated hardware modules can take advantage of the projected potential of the processing capability of a single chip device which can be very economically produced. Such systems may further offer better fault-tolerance capability and extendibility of system performance. So far, concurrent programming has not been adequately dealt with in conventional programming languages. It is our belief that future systems must depart from the prevalent view of sequential computation both at the programming language level and at the machine organization level if a substantial progress is to be made toward practical large concurrent systems. The goal of this thesis is to demonstrate that an adequate computation model can provide a basis both for a good programming language and for an architecture that can fully exploit the inherent concurrency in algorithms expressed in the language. To this end, we show how a value-oriented language can be implemented based on a model of concurrent computation known as dataflow schemas and how this implementation can guide the design of an architecture that achieves a high level of concurrent operations. The model of computation is based on the notion of data driven computation, in the sense that an operation in a computation is executed as soon as all of the required operands become available. Thus, there is no notion of sequential control of execution. Data flow schemas allow many concurrent subcomputations to take place without creating side-effects. The lack of side-effects is essential for several reasons. First, the existence of side-effects among concurrent processes may cause the outcome of the computation to be dependent on the order in which the processes are executed -- that is, the computation is nondeterminate. In most applications, it is desirable to achieve concurrent operation while preserving the uniqueness of the result of the computation. From the semantic point of view, a language that is free of side-effects is easily formalized using denotational semantics. Furthermore, when a computation is expressed in a side-effect-free language, concurrency in the computation is easily recognized as subcomputations which do not depend on results of other subcomputations - and this data dependency is manifest in the program structure. We introduce a simple value-oriented language that has two important features: streams which are sequences of values communicated between computations and forall constructs in which one can express concurrent operations on components of data structures. A computation expressed in this language is guaranteed determinate unless explicit forms of nondeterminacy are used. In this thesis, we consider a (united form of nondeterminacy that merges two sequences of values in a nondeterminate manner. We discuss limitations of the language in Section 1.4. The architecture presented in this thesis is based on a form of data flow processor proposed by Dennis and Misunas. We show how the language can be effectively implemented on this architecture such that concurrency of a computation can be exploited. The main extension includes suggestions for the design of the storage of a targe number of activations of procedures and data structures such that contentions in accessing data structures can be alleviated. Extract: Rationale for TDFL Data Flow Languages Because the data flow model is graphical in nature, numerous studies have attempted to define textual programming languages based on these models. While it is possible to define an algorithm that transforms programs written in existing sequential programming, languages into data flow schemas, such an algorithm is complex because of the semantics of the sequential programming languages. Furthermore, the inherent concurrency of a computation is often hidden from the translator because there are additional constraints that are built-in in the expressiveness of sequential programming languages. We believe that high level data flow programming languages will allow algorithms for concurrent computation to be easily expressible. Programming languages based on the data flow concept are sufficiently expressive to encompass conventional programming language constructs such as iterations, while-loops, conditionals, procedures, and data types such as date structures and procedure values. These constructs, however, are embedded in a semantics which is free of both side-effects and the sequential control of execution. The distinctive tack of control transfer primitives such as GOTO's and operations which introduce side-effect allows compilers to easily detect data dependencies between operations in a program. Languages with these characteristics have been shown to have simple denotational formal semantics. Additional features such as forall constructs, primitives for stream values, and constructs for nondeterminate computations are found to be natural extensions to these languages. The forall constructs allow programmers to specify concurrent operations on all components of a data structure. The notion of stream provides an alternative to the use of coroutines and synchronization primitives for expressing computations passing sequences of values among their component modules. A very important characteristic of these languages is that the determinacy of a computation is guaranteed when the computation is expressed not using primitives or features explicitly provided for situations where non-determinacy is required. In conventional languages, nondeterminate computations are expressed using semaphore primitives, call and wait primitives, and monitors. The semantics of these primitives, however, are not consistent with the semantics of data flow languages. Because there are significant applications where nondeterminacy is necessary, the formal semantics of languages with non-determinate primitives is still an active area of research. In this thesis, we have chosen a very primitive form of nondeterminacy which seems essential as a basis for higher level constructs for nondeterminate computations. in [ACM SIGACT-SIGPLAN] Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages 1978 , Tucson, Arizona view details The major group in America is that led by Jack Dennis at MIT, and many of the other groups in the USA have used the MIT work as a basis. Jack Dennis's group are currently partially funded by the Lawrence Livermore Laboratory, and have built a simple version of their data flow machine. [Dataflow] Work is also in progress in the field of programming language design [Val], and in application areas. Kosinski has also worked at MIT looking into the formal semantics of data flow programming languages [DFPL] Extract: Id languages Another large data flow research project in America was the one at the University of California at Irvine [Id]. They originally took Dennis?s graphical notation as a base language, and designed a high-level language which could be compiled into the MIT notation. Since then they have made many changes to the base language - adding and deleting features to fit more closely the view of data flow that they developed - so that it is now significantly different to Dennis's. Various designs for machine architectures have been produced, and work has been done on simulating them. As far as I am aware there is as yet no intention to build an actual machine. Around 1980 both the main researchers, Arvind and Gostelow, left Irvine, but the project is continuing on a smaller scale with Lubomir Bic being the main faculty member involved. Arvind moved to MIT, and is pursuing his research separately from Jack Dennis there, though obviously there is some interaction between the groups. A report on Arvind's ideas for a data flow computer was given in a paper by Arvind and Kathail in 1981. in [ACM SIGACT-SIGPLAN] Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages 1978 , Tucson, Arizona view details |