Concurrent Objects à la Carte - PDF

Description
Concurrent Objects à la Carte Dave Clarke 1, Einar Broch Johnsen 2, and Olaf Owe 2 1 CWI, Amsterdam, the Netherlands 2 Dept. of Informatics, University of Oslo, Norway

Please download to get full document.

View again

of 21
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Crafts

Publish on:

Views: 20 | Pages: 21

Extension: PDF | Download: 0

Share
Transcript
Concurrent Objects à la Carte Dave Clarke 1, Einar Broch Johnsen 2, and Olaf Owe 2 1 CWI, Amsterdam, the Netherlands 2 Dept. of Informatics, University of Oslo, Norway Abstract Services are autonomous, self-describing, technology-neutral software units that can be described, published, discovered, and composed into software applications at run-time. Designing software services and composing services in order to form applications or composite services requires abstractions beyond those found in typical object-oriented programming languages. In this paper, we explore a number of the abstractions used in service-oriented computing and related Internet- and web-based programming models in the context of Creol, an executable concurrent object-oriented modeling language with active objects and futures; i.e., features capable of expressing and dealing with asynchronous actions. By adding various abstractions to the modeling language, we demonstrate how a concurrent object language may naturally address many of the requirements of service-oriented computing. The study of language extensions in the restricted setting of a small, high-level modeling language, such as Creol, suggests a cheap way of developing new abstractions for emerging application domains. In this paper, we explore abstractions in the context of service-oriented computing, particularly with regard to dynamic aspects such as service discovery and structuring mechanisms such as groups. 1 Introduction Service-oriented computing is an emerging computational model in which services are autonomous, self-describing, technology-neutral software units that can be described, published, discovered, and composed into software applications at run-time. A service provides specific functionality to clients in its external environment. In particular, a client may detect new services or better service providers, and negotiate the use of services at run-time, depending on the quality and cost of the services currently available in the environment. This makes service-oriented computing an attractive model for distributed applications such as Web services, e-business, and e-government, but also for ad-hoc, self-configuring, and loosely-coupled networks, such as peer-to-peer networks, sensor-based applications, and mobile systems. Research on service-oriented computing typically focuses on three aspects: service and data interchangeability (or platform-neutrality), technologies for service detection, and mechanisms for service composition and orchestration. Interchangeability is achieved through XML-related technologies which support the exchange of structured or semi-structured data through a shared data model, as well as the publication and description of services. Service discovery (or openendedness) is typically achieved through events and event-handling architectures, and via standards such as UDDI and service repositories. Industrial proposals for the description of orchestration mechanisms include BPML, WSFL, XLANG, and BPEL. These languages typically combine communication primitives with work-flow constructs in order to describe the distributed flow of control in flexible ways. Service-oriented computing has been formally studied through a plethora of process algebras (e.g., [8, 9, 24]), which mostly address aspects of orchestration. However, two approaches to service discovery in this context have recently been developed, extending process algebras with Linda tuple spaces to represent service repositories [9] and with semantic subtyping of channels [11]. Object orientation has been criticized for its apparent mismatch with serviceoriented computing, partly due to a lack of advanced data types, which makes new solutions necessary to elegantly handle XML documents [6], and partly due to its traditionally restrictive communication and concurrency abstractions. The venue of truly parallel (distributed or multicore) systems challenges the multithread concurrency model which is predominant in object-oriented systems today and provided by Java and C#. This has lead to recent interest in concurrent objects and more flexible object interaction mechanisms [5, 10, 13, 18]. Concurrent objects are reminiscent of the concurrency model of Actors [2] and Erlang [3] and seem promising for deployment on multicore and distributed platforms, as well as for embedded systems (see Hooman and Verhoef [17]). Interestingly, concurrent objects have many of the properties described above for service-oriented computing. In particular, they interact via asynchronous communication and do not assume a tight coupling between caller and callee. This leads to a natural notion of asynchronous method call based on so-called futures [4, 22, 25, 29]. Creol is a concurrent object-oriented language which combines asynchronous method calls with controlled process release [18]. This decouples concurrency, communication, and synchronization in a very flexible way, while supporting a simple proof theory [13] compared to the proof theory of multithread concurrency [1]. The strict encapsulation of fields is enforced by using interfaces for typing objects; these interfaces include a so-called cointerface for callbacks between interacting objects. In this paper, we argue that this flexibility makes it easy to express orchestration patterns. Furthermore, we extend Creol with highlevel primitives for service publishing and discovery, and for delegation and a hierarchical notion of service discovery based on groups. We give a type system and formal semantics for this extended language. Finally, we argue through a series of examples for its suitability for service-oriented computing. The paper is structured as follows. Section 2 introduces Creol with primitives for service-oriented computing, its syntax and type system. Section 3 gives a reduction semantics for the language, in the style of Felleisen and Hieb [15]. Section 4 presents service-oriented computing flavored examples. Section 5 introduces abstractions for groups and their use through another example. Section 6 discusses our approach and some possible extensions in relation to existing work. 2 Service-Oriented Concurrent Objects In this section, we present an extension of the concurrent object-oriented language Creol to address dynamic service publication and discovery. A concurrent object represents a separate computational unit, conceptually encapsulating its own processor. In Creol, method calls are asynchronous and object variables (references) are typed by interfaces. We use different interfaces to represent the different services offered by a concurrent object. In particular, an interface may require that a cointerface is offered by the service demander. 2.1 Syntax The language syntax is given in Fig. 1. A program P is a list of interface and class definitions, followed by a method body corresponding to the main method. An interface D may inherit other interfaces and specify a set of method signatures. An interface is a subtype of all the interfaces it inherits. A class L may implement a set of interfaces and provide local fields and method definitions. For simplicity, we ignore class inheritance in this paper. We emphasize the differences with Java. As usual, a method signature declares the return type of the method, its name, and the types of its formal parameters. In addition, the method signature specifies the cointerface for the method; i.e., the required type of the object calling the method. Expressions e are standard apart from the asynchronous method call e!m(e), the (blocking) read operation e.get, the asynchronous bind operation bind I, and the service announcement operation announce I. Statements s are standard apart from release points await g and release, the delegation statement forward e!m(e) and the service removal statement retract e. Guards g are conjunctions of Boolean expressions bv and polling operations v? on futures v. When the guard in an await statement evaluates to false, the processor is released and the active process is suspended, otherwise computation proceeds in the active process. A release statement suspends the active process and another suspended process may be rescheduled, similar to a yield in Java. (Each object has an associated processor, so locks, signaling or other forms of process control are not needed.) Non-deterministic choice s s allows either branch to be selected. The branches of a merge s s are interleaved at release points, influencing the control flow within a process without allowing other processes to execute, unless neither branch is enabled. In addition, the intermediate statement s /s appears during reduction; it corresponds to the activation of statement s in the merge of statements s and s, where statement s is delayed. The sequence t := e!m(e ); await t?; v := t.get, where t is a future variable, corresponds to a non-blocking method call, while t := e!m(e ); v := t.get (or simply v := e!m(e ).get) corresponds to a blocking method call. 2.2 Typing The typing rules are given in Fig. 2. Let Γ be a typing context which binds names to types (e.g., x : T ) and write Γ (x) for the type bound to x in Γ, which may P ::= D L {T x; s D ::= interface I extends I {M s M s ::= T m (T x) with I L ::= class C implements I {T f; M M ::= M s{t x; s e ::= bv new C( ) e.get e!m(e) null v ::= f x bind I announce I b ::= true false s ::= v := e await g if bv then s else s fi bv ::= b v release forward e!m(e) retract e T ::= I bool fut(t ) s; s s s s s s /s return e skip T + ::= T ad g ::= bv v? g g Figure 1. The language syntax. Variables v are fields (f) or local variables (x), C is a class name, and I an interface name. Lists are indicated by overlining, as in e. The type language is restricted to booleans, interfaces and futures. (Data types may be added.) be undefined. For simplicity, we elide the checking of interface declarations, and assume that all methods declared in an interface have distinct names and that interface extensions are non-circular. Futures have explicit types; i.e., fut(t ) is the type for futures holding values of type T. In addition, the type ad is used to denote the type of service announcements and ok is the type of well-typed statements. Furthermore, if a class C implements interfaces I, we conventionally use C as the name for the type interface C extends I {. The subtype relation I J is induced by the reflexive and transitive closure of the interface extension relation. Data types as well as ad are only subtypes of themselves; i.e., bool bool, ad ad. In addition, if T T then fut(t ) fut(t ). In the typing rules for expressions, new C gets type C, null can get any interface type, and announce I gets type ad. We assume given an implicit table for interface declarations, so the auxiliary function lookup(i, m, T ) gives us the return and cointerface types of method m with formal parameters of types T in interface I, if such an m is declared in I. The typing of an asynchronous method call e!m(e), where e has type I and e have types T, can then be explained as follows: If method m is declared in the interface I of the callee e, with return type T and cointerface type J, then the asynchronous operation e!m(e) is typed by fut(t ) if the caller this can provide the required cointerface. Similarly, the asynchronous operation bind I is typed by fut(i). Similarly, e.get is of type T if e is a future of type fut(t ). In the typing of guards, the polling of a field f gets type bool provided that f is a future. For the typing of statements, note that the delegation statement forward e!m(e) is well-typed if the caller of the current method could have called e!m(e) instead of the call to the current method. It follows in typing rule Forward that forward e!m(e) is well-typed provided that m has an adequate return type and that the current caller has a type which satisfies the cointerface of m. The service revocation statement retract v is well-typed if v has type ad. Note that rule Assign allows expressions of type T + (in contrast to, e.g., Call). The typing of the remaining statements is standard. For the typing of methods, note that the typing context is extended with the two variables destiny, which provides the type of the method call s associated future, and caller, which is typed by the method s cointerface and (Var) Γ v : Γ (v) (New) Γ new C : C (Null) Γ null : I (Get) Γ e : fut(t ) Γ e.get : T (Await) Γ g : bool Γ await g : ok (Call) Γ e : I Γ e : T Γ (this) J lookup(i, m, T )) = T, J Γ e!m(e) : fut(t ) (Announce) Γ (this) I Γ announce I : ad (Bool) Γ b : bool (Assign) T + Γ (v) Γ e : T + Γ v := e : ok (Subsumption) Γ e : T T T Γ e : T (Cond) Γ bv : bool Γ s 1 : ok Γ s 2 : ok Γ if bv then s 1 else s 2 fi : ok (Forward) Γ e : I lookup(i, m, T )) = T, J Γ e : T Γ (caller) J T returntype(γ ) Γ forward e!m(e) : ok (Retract) Γ e : ad Γ retract e : ok (Choice) Γ s : ok Γ s : ok Γ s s : ok (G-Conj) Γ g : bool Γ g : bool Γ g g : bool (Merge) Γ s : ok Γ s : ok Γ s s : ok (Bind) Γ bind I : fut(i) (Poll) Γ v : fut(t ) Γ v? : bool (Release) Γ release : ok (Skip) Γ skip : ok (Method) Γ, destiny : fut(t ), caller : I, x 1 : T 1, x 2 : T 2 s : ok Γ T m (T 1 x 1) with I{T 2 x 2; s : ok (Return) Γ e returntype(γ ) Γ return e : ok (Class) implements(c, I) for all M M Γ, this : C, x : T M : ok Γ class C implements I {T x; M : ok (Comp) Γ s : ok Γ s : ok Γ s; s : ok Figure 2. The typing rules. The predicate implements(c, I) compares the method signatures of C with those of each interface I in I with respect to co- and contravariance requirements for formal parameters and cointerfaces. Function returntype(γ ) = T whenever Γ (destiny) = fut(t ). provides support for callback, in addition to types for formal parameters and locally declared variables. As usual, the typing rule for classes extends the typing environment with a type for this and types for the fields declared in the class. In addition, rule Class includes a check for compatibility with the declared interfaces I of the class C by means of an auxiliary predicate implements(c, I) which ensures that for all method signatures T 1 m (T 2 x) with A declared in an interface I or a superinterface of I (for I I), there is a method declaration T 3 m (T 4 x) with B {T y; s in C such that T 3 T 1, T 2 T 1, and A B. config ::= ɛ object msg service config config fds ::= f d object ::= (obj oid, C, processq, fds, active) active ::= process idle processq ::= ɛ process processq processq service ::= (ad adid, I, oid) msg ::= (fut fid, cmd, oid, mode, d) process ::= (T x d, s) d ::= oid fid adid null b cmd ::= oid!m(d) bind I Figure 3. Syntax for runtime configurations. Here, d denotes data, including Boolean values (b) and identifiers for objects (oid), futures (fid), and service announcements (adid). Processes include code and local state, i.e. local variables with types and values. 3 Operational Semantics The semantics is a small-step reduction relation on configurations of objects, messages, and services (see Fig. 3). An object has an identifier, a class, a queue of suspended processes, fields, and an active process. The process idle indicates that no method is running in the object. We introduce the notion of a command, cmd, to model asynchronous actions. Commands are reduced using a single rule which spawns off a new thread, in effect, to execute the command. Initially, commands include asynchronous method calls and bind requests. A future (fut fid, cmd, oid, mode, d) captures the state of command: initially sleeping, the command may later becomes active, and finally, when completed, it stores its result in the future. The value mode {s, a, c represents these three states. A bind request does not use the mode a. Default values for types are given by a function default (e.g., default(i) = null, default(bool) = false, and default(fut(t )) = null). The initial configuration of a program L {T x; s contains one object (obj o,, ɛ, (T x default(t ), s)). Reduction takes the form of a relation config config. Rules apply to partial configurations and may be applied in parallel. This differs from the semantics of object-oriented languages with a global store [16], but is consistent with Creol s [19] executable Maude semantics [12] and allows true concurrency in the distributed or multicore setting. The main rules are given in Figs. 4, 5, and 6. The context reduction semantics decomposes a statement into a reduction context and a redex, and reduces the redex [15]. Reduction contexts are statements S, expressions E, and guards G with a single hole denoted by : S ::= v := E S; s S /s if G then s 1 else s 2 fi return E forward E retract E await G E ::= E.get E!m(e) oid!m(d, E, e) G ::= E? G g b G Redexes reduce in their respective contexts; i.e., stat-redexes in S, exprredexes in E, and guard-redexes in G. Redexes are defined as follows: stat-redexes ::= x := d f := d await g skip; s if b then s 1 else s 2 fi release forward oid!m(d) retract aid return d expr-redexes ::= x f fid.get oid!m(d) new C() bind I announce I guard-redexes ::= fid? b g (Red-Cmd) fid is fresh (obj oid, C, pq, fds, (l, S[cmd)])) (obj oid, C, pq, fds, (l, S[fid])) (fut fid, cmd, oid, s, null) (Red-Get) (obj oid, C, pq, fds, (l, S[fid.get])) (fut fid, cmd, oid, c, d) (obj oid, C, pq, fds, (l, S[d])) (fut fid, cmd, oid, c, d) (Red-New) oid is fresh fds = defaults(c ) (obj oid, C, pq, fds, (l, S[new C ()])) (obj oid, C, pq, fds, (l, S[oid ]))(obj oid, C, ɛ, fds, proc(c, run, null, oid, ε)) (Red-Poll) b = (mode c) (obj oid, C, pq, fds, (l, S[fid?])) (fut fid, cmd, oid, mode, d) (obj oid, C, pq, fds, (l, S[b])) (fut fid, cmd, oid, mode, d) (Red-Await) (obj oid, C, pq, fds, (l, S[await g])) (obj oid, C, pq, fds, (l, S[if g then skip else release; await g fi])) (Red-Release) S[release] S [release; s /s ] (obj oid, C, pq, fds, (l, S[release])) (obj oid, C, pq :: (l, S[skip]), fds, idle) (Red-Reschedule) (obj oid, C, pq :: p :: pq, fds, idle) (obj oid, C, pq :: pq, fds, p) Figure 4. The context reduction semantics (1/4). In the last rule, pq and pq may be empty. In Red-New, the proc function gives an activation of run (with oid as caller). Filling the hole of a context S with an expression r is denoted S[r]. Expressions and guards. Red-Cmd spawns asynchronous actions by adding a sleeping future to the configuration, returning its identifier to the caller. In Red-Get, a read on a future variable blocks the active process until the future is in completed mode (since no other rule applies to this redex). Blocking does not reschedule a suspended process. Object creation in Red-New introduces a new instance of a class C into the configuration (with fields collected from C), and the run method is called. In Red-Poll, a future variable is polled to see if the asynchronous action has completed. Release and rescheduling. Guards determine whether a process should be released. In Red-Await, a process at a release point proceeds if its guard is true and otherwise releases. When a process is released, its guard is reused to reschedule the process. When an active process is released in Red-Release or terminates, it is replaced by the idle process, which allows a process from the process queue to be scheduled for execution in Red-Reschedule. The rule given (Red-Method-Bind) (obj oid, C, pq, fds, p) (fut fid, oid!m(d), oid, s, null) (obj oid, C, pq :: proc(c, m, fid, oid, d), fds, p) (fut fid, oid!m(d), oid, a, null) (Red-Return) l(destiny) = fid (obj oid, C, pq, fds, (l, S[return d])) (fut fid, oid!m(d), oid, a, null) (obj oid, C, pq, fds, idle) (fut fid, oid!m(d), oid, c, d) (Red-Forward) l(destiny) = fid l(caller) = oid (obj oid, C, pq, fds, (l, S[forward oid!m(d)])) (fut fid,,,, ) (obj oid, C, pq, fds, idle) (fut fid, oid!m(d), oid, s, null) (Red-Announce) adid is fresh (obj oid, C, pq, fds, (l, S[announce I])) (obj oid, C, pq, fds, (l, S[adid])) (ad adid, I, oid))
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks