1 Introduction and MotivationA pipeline is a popular architecture which connects computational compo-nents (?lters) through connectors (pipes) so that computations are performedin a stream like fashion. The data are transported through the pipes between?lters, gradually transforming inputs to outputs. This kind of stream pro-cessing has been made popular through UNIX pipes that serially connectindependent components for performing a sequence of tasks. Because ofits simplicity and its easy to grasp functionality it is a pet architecture fordemonstrating ideas about formalizing the architectural design space (notunlike the data type Stack for algebraic speci?cations or abstract data types). We will show in this paper how to formalize this architecture interms of monads, hereby including speci?cations through set theoretic orprobabilistic relations as special cases.Software architecturesThe structural aspects of a large programming system are captured throughits (software) architecture. Initially, this term was used rather loosely, workbeing done during the 1990s in particular by M. Shaw and her associates(see e.g. [31,28, 1]) have established a body of knowledge in the softwareengineering community about methods for structuring large systems. Thistranslates into practical tools like architectural design languages.An architecture for a system separates computation from control on thesystem’s level; while the former is represented by algorithms formulated ina programming language, the latter is formulated in terms of components(which carry out the computations) and connectors (which transport datafrom one component to another one). Connectors are elevated to ?rst classrank making it possible to reason explicitly about connecting components.Considering an architecture then means identifying connectors and com-ponents and describing the interplay between them. Since the emphasis ison structure, formalizing an architecture helps in investigating its salientfeatures; formalizations can be done on different levels. Closest to imple-mentations are formulations through an architectural description language([30] discusses and assesses a number of them), but other formalisms areused, too:• the paper [23] investigates the suitability of the Uni?ed Modelling Lan-guage for architectural descriptions (and discusses some desiderata forthe language to be usable for architectural descriptions),• the work reported on through [1, 31] discuss a formulation of pipes and?lters through a denotational framework for developing formal modelsof architectural styles based on the speci?cation language Z,• Arbab and Rutten present Reo, a calculus of component connectors basedon coinduction [3]; coalgebras play a leading role in Barbosa’s work oncomponents [4],• the Focus calculus developed by Broy and Stølen [7] is based on chan-nels that are used by components to exchange information in terms ofmessages,• category theory is used in formalizations e.g. of architectures for mobileprograms based on UNITY [34, 17].The formalization of an architecture permits reasoning about it sinceit provides precise and abstract models that usually come with analytical techniques. This is in marked contrast to architectural techniques wherethe shape of an architecture and its architectural parameters are determinedexperimentally ([16] provides an example for constructing a substantial reallife system). Shaw and Garlan [31, Sect. 6] discuss architectural formalisms,they distinguish three levels of formalization:• The architecture of a speci?c system. This permits a precise character-ization of the system-level functions that determine the overall productfunctionality.• The formalization of an architectural style. Through the description ofarchitectural abstractions it becomes possible to analyze various staticor dynamic properties of common architectural patterns or referencearchitectures which are used informally e.g. as reference architectures.Essential ingredients in such a formalization are provided by connectorsand by components.• A theory of software architecture. By classifying architectures and rep-resenting them with a mathematical machinery a deductive basis foranalyzing systems is provided.We will focus in the present paper on the intermediate level and investigatean architecture where the computational elements are represented throughrelations.RelationsComputations may be modelled through relations, relating e.g. an input to anoutput or to a state. This gives rise to a whole calculus of relations (for whichthe contributions to [6] provides a reference), it draws heavily on ideas fromMathematical Logic in its classic version as embodied by E. Schr¨oder or A.Tarski. This has been outlined in [8].We will not follow this trail but rather capitalize on a common abstractdescription of non-deterministic and stochastic relations through monads.A non-deterministic relation R between sets X and Y , thus R ? X × Yassigns to each x ? X a subset {y| x, y ? R} of possible outcomes. Thusnondeterministic systems may be modelled with these relations. Relation Rmay be represented as a map from X to the power set P (Y ) of Y . Whilenondeterministic relations may be interpreted as assigning equal weight toeach possible outcome, a probabilistic relation assigns to each input x ? X aprobability distribution K(x) on the output, so that K(x)(B) yields the prob-ability that on input x the output is an element of B ? Y . If K(x)(Y ) = 1,it is guaranteed that there will be some output, non-terminating computa-tions may be taken into account by assuming that K(x)(Y ) < 1, so that1?K(x)(Y ) may be interpreted as the probability for no output at all. Hence K can be interpreted as a map from X to the set S (Y ) of a subprobabilitieson Y . For this to permit sensible models, X and Y have to be endowed withmeasurable and sometimes topological structures. Both constructions sharea common structure in representing the Kleisli construction for a monad.The case of non-deterministic relations is covered through the power setfunctor on the category of sets, and the stochastic case through the functorwhich assigns each measurable set the space of all subprobability measures.Thus monads (and their associated Kleisli categories) form the common ab-straction for both cases, bringing us into the realm of Moggi’s argumentation[25,24] that monads form a suitable basis for modelling computations. Con-sequently, our architectural modelling will be done on the basis of a monad.Categories vs. ArchitecturesCategories with their emphasis on structure are a suitable formal tool formodelling software architectures. Focussing on structure implies the inde-pendence on any representation in a speci?cation or programming language;technically this is achieved through the use of morphisms and functors.Synthesizing a design sometimes means formulating the components andamalgamating them through a suitable colimit (cf. [17]). Wermelinger andFiadeiro [34] discuss some salient features of an architectural modellingthrough categories in the context of christian louboutin shoes their modelling mobile programs:• Programs may be represented as objects, morphisms show how programscan be composed; explicit use of connectors facilitates the separation ofcomputation and coordination.• The mechanisms for interconnecting components yielding complex sys-tems are formalized using universal constructs, in this way providing astage for arguing about these mechanisms formally.• Extralogical design principles are internalized through properties of uni-versal constructs (e.g., locality of names),• Different levels of design can be related through functors.• The evolution of architectures is supported.When modelling an architecture, one has at least to take care of the com-putational components and the connectors. Working in a category, the con-nectors may be represented as objects while the computational componentswill be modelled as morphisms between the objects. Since computationswill be represented as monads, the most natural way is representing a component through the work of the corresponding functor T. Here the Kleisliconstruction enters the game: suppose for simplicity that the input and theoutput for a component ? are modelled respectively through the objects xand y, then the computation performed by ? is represented through a Kleisli
No comments:
Post a Comment