Home

The JoCaml language Release 3.11 - The JoCaml system

1. lt fun gt The following collect_as_sum will collect n integers on channel add and send their sum as the result of synchronous wait let collect_as_sum n let add wait create_collector O n in add wait val collect_as_sum int gt int Join chan unit gt int lt fun gt One now easily computes the sum of the n first integers as follows let n 10 Fo val n int 10 20 let add wait collect_as_sum n Fo val add int Join chan lt abstr gt val wait unit gt int lt fun gt spawn for i 0 to n 1 do add i done unit print int wait unit 0 45 It is to be noticed that collectors are provided by the JoCaml standard library mod ule JoinCount Collector module Col JoinCount Collector 55 module Col sig type Ca b t Ca b JoinCount Collector t collect a Join chan wait unit gt b val create a gt b gt b gt b gt int gt a b t end Generally speaking the standard library of JoCaml makes heavy use of records as illustrated by the type of collectors JoinCount Collector t above As a matter of fact records offer a convenient way to pack together the public channels of join definitions Here is another way of summing the first n integers asynchronouosly that time relying on the collectors of the standard library let col Col create On val col i
2. The Unix command arch echoes a conventional string that describes the architecture of the ma chine such as alpha 1686 etc The Unix command rsh host cmd performs the remote execution of command cmd on host In particular rsh copies the standard output of the remote command to its standard output Hence by issuing the command rsh host arch we get the architecture of host By a using a bit of classical Unix programming the following function forks an Unix process that performs command arch on a remote host let rsh_arch host JoinProc open_in usr bin rsh host arch 5 val rsh_arch string gt int in_channel lt fun gt 40 The rsh_arch function is in charge of forking the concurrent Unix process that performs the remote arch command To that end it calls open_in from the standard library module JoinProc Observe that the function rsh_arch returns a process id and an input IO channel Thanks to the Unix plumbing that JoinProc open_in performs the output of the remote arch command can be read on this channel Moreover the process id is the information needed to kill an Unix process as we should do when timeout expires Now to use the timeout function of the previous section we disguise the remote call to arch into a pair of a run function and of a kill channel let create_arch host let pid inchan rsh_arch host in def result r amp wait amp ok reply r to wait or killQ amp
3. end unit A RARA AAA A AAA AA AAA AAA A RA Barriers A barrier is another common synchronization mechanism Basically barriers define synchronization points in the execution of parallel tasks Here is a simple barrier that synchronizes two threads def joini amp join2 reply to joini amp reply to join2 55 val joini unit gt unit lt fun gt val join2 unit gt unit lt fun gt The following two threads print ba or ab between matching parenthesis spawn begin print string joint O print string a joini print_string 0 join2 O print string b join2 0 end 5 unit ab Waiting for n events to occur A frequent idiom is for a program to fork n concurrent tasks and then to wait for those to complete We can reformulate the informal fork s and wait as follows channel count holds an integer that records the number of events still to be waited for Events to be counted are materialized by sending empty messages on channel tick 18 def count n amp tick count n 1 or count 0 amp wait val tick unit Join chan lt abstr gt val count int Join chan lt abstr gt val wait unit gt unit lt fun gt reply to wait By sending an initial message n on count we enable counting n events let n 5 val n int 5 spawn count n unit Finally one can wait
4. gt b gt b gt b gt a b t create comb y0 returns a dynamic collector of events of type a with combining function comb and initial result yO end Dynamic collectors 5 3 Module JoinFifo Concurrent fifo buffers Concurrent fifo s offer blocking get operations More precisely get operations on active empty fifo s are blocking Fifo behavior can be observed in the simple situation where one agent producer is putting elements while another agent consumer is getting them Then the following guarantees hold e The consumer see the elements in producing order 76 e If the producer closes the fifo and does not put any additional elements then the consumer will have retrieved all elements when the call to close returns type a t put a bool Join chan Join chan Put element into fifo get a option Join chan Join chan Get element from fifo close unit gt unit Close fifo returns only when the fifo is empty kill unit Join chan Close fifo returns immediately discarding any pending element The type of fifo buffer val create unit gt at Create a new fifo buffer Interface to concurrent fifo s is mostly asynchronous Let f be a fifo e f put x k put v into the fifo f The channel k receives a boolean message b where If b is true then v was succesfully entered into f If b is false then v could not be added to f That is f have bee
5. The syntax for such message sending is the same as the one for function call in Objective Caml Hence writing echo 1 and echo 2 is correct However in this manual we conventionally write message sending with argument between parenthesis Concurrent execution also occurs inside processes using the parallel composition operator amp This provides a more concise semantically equivalent alternative to the previous example spawn echo 1 amp echo 2 Ho unit 12 Composite processes also include conditionals if s matching match s and local binding let in s and def in s Process grouping is done by using brackets and or the equivalent begin and end just as in Objective Caml Chapter 1 Concurrent programming 9 spawn begin let x 1 in let y x 1 in echo y amp echo y 1 amp echo x end to unit 231 Once again the program above may echo the integers 1 2 and 3 in any order Grouping is necessary around the process let y in to restrict the scope of y such that its evaluation occurs independently of the process echo x Processes may also include sequences The general form of a sequence inside a process is expression process where the result of expression will be discarded As expression can itself be a sequence thus one may write spawn begin print int 1 print int 2 echo 3 end 35 unit 123 seq
6. again the JoCaml encoding of a reference cell def state x get state x reply x to get or state _ set x state x amp reply to set 35 val get unit gt _a lt fun gt val state _a Join chan lt abstr gt val set _a gt unit lt fun gt The type variable _a that appears inside the types for state get and set is prefixed by an underscore _ Such type variables are non generalized type variables that are instantiated only once That is all the occurrences of state must have the same type Moreover once _a is instantiated with some type this type replaces _a in all the types where _a appears here the types for get and set This wide scope instantiation guarantees that the various port names whose type contains _a state get and set here are used consistently More specifically if a is instantiated to some type int by sending the message O on state Then the type for get is unit gt int in the rest of the program as shown by the type for x below As a consequence the following program does not type check and a runtime type error printing an integer while believing it is a string is avoided def state x amp get state x amp reply x to get or state _ amp set x state x amp reply to set 3 Chapter 1 Concurrent programming 35 val get unit gt _a lt fun gt val state _a Join chan lt abst
7. end a val create sync unit gt a S t Records of type a S t offer the same fields as the ones of type a t but they hold synchronous channels of functional type 77 78 e put of type a gt unit either returns when successful or raise the exception S Closed e get follows the same behavior e close of type unit gt unit closes the fifo returning when the fifo is empty 5 4 Module JoinProc Convenience functions for forking Unix commands All functions fork commands given in the style of the Unix execvp function That is a command is a program name plus an array of command line arguments and the program name is searched in path Functions return the pid of the child process that executes the program and some I O channels exactly which ones depends on the function val command string gt string array gt int command prog args executes program prog with arguments args in a child process Standard channels stdin stdout and stderr are the ones of the parent process val open_in string gt string array gt int Pervasives in_channel Same as JoinProc command 5 4 above except that the forked process standard output is redirected to a pipe which can be read via the returned input channel val open_out string gt string array gt int Pervasives out_channel Same as JoinProc command 5 4 above except that the forked process standard input is redirected to a pipe which can be w
8. int lt fun gt spawn count 0 to unit count n amp reply n to get This definition calls for two remarks First join pattern may mix synchronous and asynchronous message Second the usage of the name count above is a typical way of ensuring mutual exclusion For the moment assume that there is at most one active invocation on count When one invocation is active count holds the counter value as a message and the counter is ready to be incremented or examined Otherwise some operation is being performed on the counter and pending operations are postponed until the operation being performed has left the counter in a consistent state As a consequence the counter may be used consistently by several threads spawn inc incQ 0 amp inc 0 35 unit def wait let x get in if x lt 3 then wait else begin print string three is enough print newline O 0 end 35 val wait unit Join chan lt abstr gt spawn wait 33 unit three is enough Ensuring correct counter behavior in the example above requires some programming discipline only one initial invocation on count has to be made If there are more than one simultaneous invocations on count then mutual exclusion is lost If there is no initial invocation on count then the counter will not work at all This can be avoided by making the count inc and get names local to a create_
9. HH H HOF OF 23 val il int list Join chan lt abstr gt val i2 int list Join chan lt abstr gt spawn i1 1 3 4 amp 12 2 31 unit 1234 It is important to notice that by contrast with Objective Caml pattern matching ambiguous matching are indeed ambiguous as soon as a message matches a pattern it may be consumed regardless of other receivers on the same channel def c echo string Nil or c _ echo string Anything 55 val c a list Join chan lt abstr gt spawn c Ho unit Anything In the example above you can see either Anything or Nil depending upon unspecified imple mentation details To get the textual priority rule of Objective Caml matching semantics use the match construct def c x match x with gt echo_string Nil _ gt echo string Anything 33 val c a list Join chan lt abstr gt spawn c Fo unit Nil 1 3 3 Mixing asynchronous and synchronous channel definitions Join patterns are the programming paradigm for concurrency in JoCaml They allow the encoding of many concurrent data structures For instance the following code defines a counter Chapter 1 Concurrent programming 15 def count n amp inc count n 1 amp reply to inc or count n amp get 5 val inc unit gt unit lt fun gt val count int Join chan lt abstr gt val get unit gt
10. In other words channel definitions are recursive by default There may be several sets of competing behaviors several reactions in a join definition separated by the keyword and Then the set of channel names defined by the various reactions must be pairwise disjoint Moreover in a reaction join pattern process the scope of the variables inside the formal arguments ocaml pattern in channel decl extends to process Those are bound by following the usual rules of the pattern matching of Objective Caml All such variables must be pairwise distinct in a given join pattern 3 6 3 Asynchronous and synchronous channels A reaction join pattern process defines a channel ident to be synchronous when reply toident occurs inside process The reply construct can be seen as an asynchronous message sending on some implicit continuation channel The scope of this continuation channel does not extend over def join definition that occur inside process above If another reaction defines the channel ident in the set of competing behaviors reactions then ident must also be defined as synchronous there 3 7 Module expressions Definitions in structures modules are extended as follows definition ocaml definition join definition def exception constr name Toplevel definition in structure can of course be join definition The additional def exceptionexception constructs enables matching by structure in try with handlers The const
11. Objective Caml standard library directory if any jocamlopt The native code compiler Added or modified options are the same as for jocamlc except for the vmthread option which does not exist jocamllex and jocamlyacc Lexer and parser generators Those two tools are unchanged except for their names jocamldep The dependency generator The jocamldep progam accepts JoCaml sources as input This default behavior can be changed by the following option nojoin Act over pure Objective Caml files jocamlmklib The tool to build mixed C JoCaml libraries There are two additional cosmetic options jocamlc cmd Alias for ocamlc cmd jocamlopt cmd Alias for oocamlopt cmd jocamlmktop The tool for building custom toplevels The produced toplevels accept and execute JoCaml source code Chapter 5 The JoCaml library JoCaml core library Join provides the built in types for channels and sites and basic operations on those Some additional modules are provided that capture common JoCaml programming patterns All the following modules are automatically linked with the user s object code files by the JoCaml compilers Chapter 4 5 1 Module Join The JoCaml core library This module offers basic functionalities for JoCaml type a chan The type of asynchronous channels carrying values of type a exception Exit Raised by the JoCaml runtime system when some remote synchronous call cannot be completed because of the fail
12. Some x gt x xs None gt xs n 33 Chapter 1 Concurrent programming 41 val collector int gt a option a list Col t lt fun gt A collector is setup for collecting n values sent on channel add Values may be worth collecting or not Some x or None but n messages must be sent on add before the list of collected values can be returned by wait We now spawn n concurrent tasks one per host in the list hosts let archs hosts let col collector List length hosts in List iter fun host gt let arch kill create_arch host in spawn begin match timeout 1 0 arch kill with Some a gt col Col collect Some host a None gt prerr_endline Timeout for host col Col collect None end hosts col Col wait 5 val archs string list gt string string list lt fun gt And here we go archs saumur beaune yquem macao Timeout for macao string string list beaune alpha yquem i686 saumur x86_64 42 Chapter 2 Distributed programming This chapter presents the distributed and mobile features of JoCaml JoCaml is specifically designed to provide a simple and well defined model of distributed programming Since the language entirely relies on asynchronous message passing programs can either be used on a single machine as described in the previous sections or th
13. about three times the speed of the slow consumer We assume that element order is critical consumers must compute the reversed list of producer output Consumers also differ marginally as regards console output the fast consumer prints recieved value x as x while the slow consumer prints lt x gt We do not intend the consumers to compete for producer output Instead they should get their own copy Of course we wish not change the producer Hence we insert the following duplicator between the producer and the consumers let dup ci c2 let dup send x ci send x c2 send x in send dup_send Fo val dup a consumer gt a consumer gt a consumer lt fun gt Clearly given the type above the producer should not notice that its messages are duplicated the combined consumers act as single consumer We marginally alter the producer so as it shows timing information let producer c let t_start Unix gettimeofday in for k 1 to 5 do c send k done let t_end Unix gettimeofday O in print string Printf sprintf Time elapsed 0 2f t end t_start 5 val producer int consumer gt unit lt fun gt And then we connect the producer and both consumers producer dup slow_consumer fast_consumer Ho unit lt 1 gt 1 lt 2 gt 2 lt 3 gt 3 lt 4 gt 4 lt 5 gt 5 Time elapsed 2 00 Integers are consummed and printed in the right order However there is no concu
14. as a pair of lists we write let create_buffer def alive xs y ys get alive xs ys amp reply y to get or alive _ _ as xs getQ alive List rev xs amp reply get to get or alive xs ys amp put x alive x xs ys amp reply to put in spawn alive 1 1 put put get get 35 val create_buffer unit gt a buffer lt fun gt We shall assume that the buffer is used by two communicating agents one writer that performs put and one reader that performs get The buffer then posseses the property that the reader reads the Chapter 1 Concurrent programming 29 elements in the same order as the writer wrote them More precisely the channel alive xs ys is used in internally to encode the state of the buffer the ordered list of elements seen from reader s side get being ys List rev xs One may observe that calls on get are blocked when the buffer is empty i e when alive is active 1 6 A serious example connecting a producer with consumers To demonstrate that our buffer is useful we consider a simple producer consumer s problem our producer feeds our consumer with 1 2 3 4 5 type a consumer send a gt unit type a consumer send a gt unit let producer c for k 1 to 5 do c send k done 55 val producer int consumer gt unit lt fun gt And here is a simple consumer that prints its input on the console l
15. correct Composite join definitions can specify several synchronization patterns def apple amp pie print_string apple pie 0 or raspberry pie print string raspberry pie 0 35 val apple unit Join chan lt abstr gt val raspberry unit Join chan lt abstr gt val pie unit Join chan lt abstr gt Observe that the name pie is defined only once Thus pie potentially takes part in two synchro nizations This co definition is expressed by the keyword or Again internal choice is performed when only one invocation of pie is present spawn apple raspberry amp pie 33 unit raspberry pie Chapter 1 Concurrent programming 13 1 3 2 ML pattern matching in join patterns Up to now we saw that the formal argument of a channel definition can be a variable or a tuple of variables More generally such a formal argument can be a pattern in the Objective Caml pattern matching sense type fruit Apple Raspberry Cheese and desert Pie Cake 5 type fruit Apple Raspberry Cheese and desert Pie Cake def f Apple amp d Pie echo_string apple pie or f Raspberry d Pie echo_string raspberry pie or f Raspberry amp d Cake echo_string raspberry cake or f Cheese amp d Cake echo_string cheese cake 5 val f fruit Join chan lt abstr gt val d desert Join chan lt abstr gt The definition above vields f
16. delay let squarel i print string let r i i in print_string r Chapter 1 Concurrent programming 25 Fo val squarel int gt int lt fun gt let square2 i print string lt let r i i in Thread delay 0 5 print string gt r Fo val square2 int gt int lt fun gt Additionally squarei and square2 differ marginally by their console output the fast square1 prints when it starts and when it s done while square2 uses lt and gt for the same purpose Sharing a loop between several agents is allocating the iterations to be performed to them The following channel create_sum returns a register channel and a wait channel An agent registers by sending its computing channel on register The final loop result is returned on wait let create_sum n let add wait collect_as_sum n in def add_square x amp register square add square x amp register square in for i 0 to n 1 do spawn add square i done register wait 5 val create_sum int gt int gt int Join chan unit gt int lt fun gt The key difference with the asynchronous sum loop from the previous section resides in an indi rection instead of sending x squared directly on the channel add the new add_square channel extracts a squaring function from the channel register As a consequence the agents squarel and square2 may now compete for loop iterations
17. exception E Fo exception E def raise E let x raise E in reply to raise E 3 val raise_E unit gt unit lt fun gt Join Ns register Join Ns here raise E raise E unit gt unit 3 unit On runtime B we also define exception E retrieve channel raise_E from A and then send a synchronous message on it Runtime B exception E Fo exception E let raise E Join Ns lookup ns raise E unit gt unit Fo val raise E unit gt unit lt fun gt try raise E with E gt print string E is raised _ gt print string An exception is raised Fo unit An exception is raised This behavior can be sumarized by saying that exceptions are generative the execution of exception E yields a unique exception and executing exception E twice moreover on two different runtimes yields two different exceptions which happen to have the same name E Maybe we can live with such a notion Unfortunately this is not the whole story when they travel from one runtime to another exeception are copied which contradicts generativity Consider a similar example where another synchronous channel is defined on A as follows 58 Runtime A def raise_e e let _x raise e in reply to raise_e 5 val raise_e exn gt unit lt fun gt Join Ns register Join Ns here raise_e raise_e exn gt unit 55 unit O While on B we define the exception E ret
18. exception raised in process that includes the reply construct behaves differently the process waiting for the result will receive the exception which will be propagated as in an Objective Caml function def die failwith die reply to die 3 val die unit gt unit lt fun gt try die with Failure msg gt print string Printf sprintf dead on s n msg Chapter 1 Concurrent programming 37 unit dead on die Synchronous processes may be in charge of replying to more than one synchronous call at the time when an exception is raised In other words there can be several reply constructs that are syntactically guarded by a shared expression that raises the exception In such cases the exception is duplicated and thrown at all threads reversing joins into forks def a amp b failwith die reply to a amp reply to b 5 val a unit gt unit lt fun gt val b unit gt unit lt fun gt spawn begin try aQ with Failure gt print string a failed n 0 amp try bO with Failure gt print string b failed n 0 end 23 unit a failed b failed Transmission of exceptions by reply constructs follow relatively straightforward rules Let us first define a channel protect to control our experiments def protect name c begin try cO print string name success n with Failure _ gt print string na
19. sends a function let ns Join Ns of_sockaddr Unix ADDR INET Join Site get_local_addr 12345 3 val ns Join Ns t lt abstr gt let main let compute Join Ns lookup ns server int gt int int gt int in print int compute fun x gt x 1 2 to val main unit If we try to run this example we obtain a runtime error here gt jocamlc server ml o s out here gt s out there gt jocamlc client ml o c out there gt c out Fatal error exception Invalid_argument output_value functional value 2 3 2 References and exceptions The behavior of a channel can change if it is called from the same JoCaml runtime or not We first define a simple synchronous channel who returns its message def id x reply x to id val id a gt a lt fun gt Then we send a mutable value on this channel from the same runtime let r ref 21 val r int ref contents 21 let r id r Ho val r int ref contents 21 r Ir 2 56 print_int r Ho unit 42 We can observe that r and r are the same reference Now we execute the same program except that the id function is computed in an other runtime let ns Join Ns of_sockaddr Unix ADDR_INET Join Site get local addr 12345 3 val ns Join Ns t lt abstr gt let id Join Ns lookup ns id int ref gt int ref Fo val id in
20. Caml system see Section 4 1
21. Fifo Concurrent fifo buffers 75 5 4 Module JoinProc Convenience functions for forking Unix commands 78 Foreword This manual documents the release 3 11 of the JoCaml system JoCaml is an extension of Objective Caml License As an extension JoCaml includes much source code from Objective Caml It should be no surprise that JoCaml license is exactly Objective Caml license The JoCaml system is open source and can be freely redistributed See the file LICENSE in the distribution for licensing information The present documentation is copyright 2008 Institut National de Recherche en Informatique et en Automatique INRIA The JoCaml documentation and user s manual may be reproduced and distributed in whole or in part subject to the following conditions e The copyright notice above and this permission notice must be preserved complete on all complete or partial copies e Any translation or derivative work of the JoCaml documentation and user s manual must be approved by the authors in writing before distribution e If you distribute the JoCaml documentation and user s manual in part instructions for ob taining the complete version of this manual must be included and a means for obtaining a complete version provided e Small portions may be reproduced as illustrations for reviews or quotes in other works without this permission notice if proper citation is given Availability The com
22. Join chan unit gt int lt fun gt In the new definition register square is launched again only once square x is computed This is so because of the semantics of let x E in P which says that process P executes only once expression E is evaluated let register wait create sum 32 55 val create_sum int gt int gt int Join chan unit gt int lt fun gt val register int gt int Join chan lt abstr gt val wait unit gt int lt fun gt spawn register squarel amp register square2 unit print_int wait unit QO 0000000000000000000000000000000010416 Finally at the fine tuning level one may object that messages on the add_square channel are a bit out of control we send a burst of such message with a for loop and they probably accumulate in some internal queue waiting for agents to retrieve them A final version of create_sum takes care not to send too many messages on add_square con currently Basically we only have to send a new message as soon as a registred agent has retrieved one message let create_sum n let add wait collect_as_sum n in def add_square x amp register square if x gt O then add_square x 1 4 let r square x in register square amp add r in spawn add_square n 1 register wait 35 val create_sum int gt int gt int Join chan unit gt int lt fun gt Chapter 1 C
23. The JoCaml language Release 3 11 Documentation and user s manual Louis Mandel and Luc Maranget December 12 2008 Copyright c 2008 Institut National de Recherche en Informatique et en Automatique Contents I An introduction to JoCaml 5 1 Concurrent programming 7 1 1 Jonventions ee 7 PSS am p 6 Se bak ee EEE ME E A ee Bt a E E E 7 ees ee ce ye a ee ae om Oe Ge ee da ds ce ee dy 11 1 4 Control structures 2 A 16 1 5 Data structures ines PAY de A woke owe Ee owe ae 2 A obs ents 29 de To AModulES sea e doh ee Go bo Bed Foe Ei oe a Se ee oe eS 32 1 8 A word on typing 34 1 9 EXC PUONS s e a awe Bis he o e e el es de 36 a 38 2 Distributed programming 43 2 1 The Distributed Model 43 She Eee SD Goines CE oe O fr eye ae SU a Ge ee o A 49 2 3 Limitations a sor sa sokie g pokok ie Gop abea 4 4 54 II User Manual 61 63 3 1 Lexical issues 63 32 Val esj 4 4 4 4 0 A bk ue due Dh EAU ee dun Be RE die da de ee 63 3 3 AS sob bk ee ae A DA a E DA a 64 3 4 Expressions 2 1 a 64 3 0 Processesl 4 5 44 dara Ae dE Ge a a DA we a 64 3 6 Join denmitions assa sa k a Le So ee Ace ee we eee Bo ees 66 3 7 Module expressions 67 4 JoCaml Tools 69 4 1 A few words on implementation s 69 Ses est caem a EN Gt cee a 69 5 The JoCaml library 71 A SN TN 71 ee 74 5 3 Module Join
24. a x if x gt O then a loop a x 1 55 val loop unit Join chan int Join chan lt abstr gt Chapter 1 Concurrent programming 23 def echo_star print_string 0 3 val echo_star unit Join chan lt abstr gt spawn loop echo star 5 3 unit ES There is also a for loop at the process level def loop a x for i 1 to x do a done 3 val loop unit Join chan int Join chan lt abstr gt spawn loop echo star 5 3 unit 2K 2K 2k KK List iterator In this section we examine the asynchronous counterpart of the list iterator List iter let iter f xs List iter fun x gt spawn f x xs val iter a Join chan gt a list gt unit lt fun gt Hence iter c e1 e2 en will act as c e1 amp c e2 amp amp c en let digits 0 1 2 3 4 5 6 7 8 9 Ho val digits int list 0 1 2 3 4 5 6 7 8 9 iter echo digits Ho unit 0 0213897654 Of course iter can be written as a channel and without using List iter let iter c def do_iter x xs c x amp do_iter xs or do_iter O in fun xs gt spawn do_iter xs val iter a Join chan gt a list gt unit lt fun gt iter echo digits unit 0213548967 24 For the iteration over a list to produce a result i e to get the asynchronous counterpart of List fold one combines the asynchronous
25. ait amp finished r reply Some r to wait or wait amp timeout kill amp reply None to wait in spawn begin finished f x amp begin Thread delay t timeout end end wait 55 val timeout float gt a gt b gt a gt unit Join chan gt b option lt fun gt match timeout 0 5 run kill with None gt print_string Timeout Some _ gt print string No timeout 3 unit 0 Thread 10 killed on uncaught exception Killed FEI AO CAO ACTOR A ARR ACR ACR ON OR OR REX Timeout The message Thread X killed on uncaught exception Killed above is issued by the JoCaml system as an indication that some of the underlying threads terminated on an abnormal condition Here the killed thread is in charge of executing the process finished f x However the evaluation of f x does not result in a value to be sent on channel finished instead exception Killed is raised and the thread in charge terminates abnormally since there is no value to send To get rid of the message one may use the Join Exit exception see Section L 9 However it may be advisable not to use system exception in place of users exception Thus one can also replace the simple process finished f x by the more complex one let r try Some f x with Killed gt None in match r with Some r gt finished r None gt 0 1 10 2 Forking an Unix process under timeout control
26. al syntax 66 Conditional Executing the process if expr then process else process executes process if expr evaluates to the boolean true and process if expr evaluates to the boolean false The else process part can be omitted in which case it defaults to else 0 Pattern matching and let definitions in processes Those two constructs are like their Objective Caml expression counterpart except that they are processes and that they introduce bindings of names to values over processes in place of expressions Concurrent for loop The process equivalent of the traditional for loop Iterations are executed concurrently Local definition of channels in processes Local definition of channels by a join definition is possible inside processes 3 6 Join definitions Join definitions reflect the key idea behind the join calculus They define channels bind them to names and define the receptors on channels join definition def reactions and reactions reactions reaction or reactions reaction join pattern process join pattern channel decl amp channel decl channel decl lowercase ident ocaml pattern 3 6 1 Informal semantics The channels defined and bound are the set of lowercase ident in channel decl above Channel names cannot be repeated inside the join pattern of a given reaction but can appear in several reaction in a reactions A reaction define both a synchronization behavior as its join pattern an
27. alive 1 0 put put get get val create_buffer unit gt a buffer lt fun gt let bufferize user let buff create buffer in def transmit user write buff get transmit in spawn transmit Chapter 2 Distributed programming 51 user with write buff put val bufferize t_user gt t_user lt fun gt Bufferized users can be used with both broadcast definitions 2 2 2 Add and remove users We want to remove automatically a user when it is unreachable So we use the Join Site at_fail function introduced in section to fired a channel that removes the unreachable user from the set of users let at_fail user def remove_user print_endline user name leaves the room remove user site in Join Site at_fail user site remove_user val at_fail t_user gt unit lt fun gt Now we define how to add a user to the set of users known by the client This channel add the user to the set of clients and record the behavior to executes when the user is unreachable def new_user user_there let user_there bufferize user_there in print_endline user_there name is in the room add user_there at_fail user_there 0 val new_user t_user Join chan lt abstr gt 2 2 3 Connect two clients together To create a connection the clients need to exchange their user information a value of type t_user Th
28. aries 4 2 Summary of tool modifications 66599 All JoCaml tools are Objective Caml tools with an initial j jocamlc jocaml etc jocamlc The bytecode compiler By default jocamlc assumes compilation with respect to the system threads library In that aspect it behaves like ocamlc with command line options thread with libraries unix cma and threads cma added at link time New or modified options are v Print the version number of the compiler the location of the standard library directory and the location of the companion Objective Caml if any then exit nojoin Act as an Objective Caml compiler as much as possible e Do not recognize the keywords that are specific to JoCaml def spawn and reply e Cancel the effect of thread and vmthread 69 70 e Suppress implicit link arguments unix cma and thread cma This option is useful mostly for system bootstrap thread resp vmthread Compile or link multithreaded programs in combination with the system resp virtual machine level threads library By contrast with ocamlc thread is the default jocaml The interactive toplevel By defaults this toplevel includes the system level threads library and the unix library jocamlrun The JoCaml virtual machine that executes bytecode files produced by jocamlc C shared library are searched as ocamlrun does with an additional step beetween step 4 and 5 4 bis Directories specified in the file 1d conf of companion
29. ce as the defining process Here every call to square in sqr 3 and within sum 5 will be evaluated as a remote function call to here inria fr The actual localization of processes is revealed by the print_int statements f aliased to sqr on there inria fr always prints on machine here and log always prints on machine there no matter where the messages are posted The result on machine here inria fr is 31 5 4 3 2 1 while the result on machine there inria fr is sqr 3 9 sum 5 55 2 1 3 Manage site termination When a distributed application runs some sites can terminate fail or be unreachable Hence sending a message to a site which is not available on a synchronous channel raises the exception Join Exit Let us define a function that test if a site is available or not On the machine here inria fr we define two synchronous channels living that always returns true and kill that kills the JoCaml runtime Chapter 2 Distributed programming 47 def living O reply true to living 3 val living unit gt bool def kill wait reply to kill reply to wait 5 val kill unit gt unit val wait unit gt unit let main Join Ns register Join Ns here living living unit gt bool Join Ns register Join Ns here kill kill unit gt unit Join Site listen Unix ADDR_INET Join Site get_local_addr 12345 wait HH H 339 val main unit On the machine there
30. contain different type variables unfortunately all type variables 36 appear as _a Namely once the variables are instantiated by sending messages on p1 and p2 the types of al and a2 are instantianted accordingly Thereby programmers make explicit the different type instantiations that are performed silently by the compiler in the case of generalized type variables 1 9 Exceptions Since processes are mapped to several threads at run time 1t is important to specify their behaviors in the presence of exceptions Exceptions behave as in Objective Caml for Objective Caml expressions If the exception is not caught in the expression the behavior will depend on the way the process as been spawned In the following processes that must reply to a synchronous channel are called synchronous processes and the others are asynchronous processes If the process is asynchronous the exception is printed on the error output and the asynchronous process terminates No other process is affected spawn begin 4 failwith Bye bye 0 amp for i 1 to 10 do print_int i done 0 end 3 Thread 3 killed on uncaught exception Failure Bye bye unit 12345678910 To avoid the error message one can raise the Join Exit exception Then the process that commits suicide does so silently spawn begin raise Join Exit 0 amp for i 1 to 10 do print_int i done 0 end 35 unit 12345678910 An
31. counter definition and then by exporting inc and get while hiding count taking advantage of lexical scoping rules let create_counter def count n amp incO count n 1 amp reply to incO or count n amp getO count n reply n to getO in spawn count 0 incO get0 val create_counter unit gt unit gt unit unit gt int lt fun gt 16 let inc get create_counter val inc unit gt unit lt fun gt val get unit gt int lt fun gt This programming style is reminiscent of object oriented programming a counter is a thing called an object it has some internal state count and its argument and it exports some methods to the external world here inc and get The constructor create_counter creates a new object initializes its internal state and returns the exported methods As a consequence several counters may be allocated and used independently 1 4 Control structures Join pattern synchronization can express many common programming paradigms either concurrent or sequential 1 4 1 Some classical synchronization primitives Locks Join pattern synchronization can be used to emulate simple locks let new lock def free lock reply to lock and unlock free reply to unlock in spawn free lock unlock 5 val new_lock unit gt unit gt unit unit gt unit lt fun gt Threads try to acquire the loc
32. d a receptor as its process More precisely when messages are present on all the channels of a given reaction and that their values match the corresponding formal arguments ocaml pattern above then the reaction is active and the guarded process may be executed A reactions is a list of competing reaction as suggested by the keyword or Implementation offers the limited guarantee that if exactly one reaction in a list of competing reactions is active then the execution of its guarded process starts If several reactions are active at the same time then one of them is selected which one being left unspecified purposely For example the construct Chapter 3 The JoCaml language 67 def ident patt process or identi patt amp ident2 patt process in process defines two channels ident and ident2 locally to process These channels are defined by two join patterns The first join patter n matches when there is a message on the channel ident and that the content of the message matches the pattern patt The second join pattern matches when there is a message on both channels and the content of each message matches its pattern When a message is sent to the channel ident if one of the two join pattern matches its associated process is executed If the two join patterns match one of the two process is executed 3 6 2 Scopes The scope of the channel names defined by join definition extends to all receptors process in reaction
33. d messages on the channel Such messages can be received by making a synchronous call to the other port name receive Let us now translate the pi calculus process new c d in c 1 c 2 c x d x x d y print y We get spawn begin let sc rc new_pi_channel and sd rd new pi channel in 4 sc 1 amp sc 2 amp let x rc Q in sd x x amp let y rdO in print int y 0 end 5 unit 4 Observe that by contrast with the JoCaml semantics of receptors the process that performs x x runs only once Synchronous pi calculus channels are encoded just as easily as asynchronous ones it suffices to make send synchronous let new_pi_sync_channel def send x amp receive reply x to receive amp reply to send in send receive 35 val new pi sync channel unit gt a gt unit unit gt a lt fun gt 1 4 2 Timeout We can define a function timeout which tries to compute a function f If the computation of f is too long we do not wait for the result Instead we acknowledge that a timeout occurred by returning value None 22 let timeout t f x def wait amp finished r reply Some r to wait or wait amp timeout reply None to wait in spawn begin finished f x amp begin Thread delay t timeout end end wait 5 val timeout float gt a gt b gt a gt b option lt fun gt It is to be noticed t
34. e in JoCaml polyadic channels are simply expressed as monadic channels that carry tuples Port names are first class values in JoCaml They can be sent as messages on other port names As a result higher order ports can be written such as def tuice f x f x amp f x 55 val twice a Join chan a Join chan lt abstr gt The type for twice is polymorphic it includes a type variable a that can be replaced by any type Thus twice is a channel that takes a channel of type a Join chan and a value of type a as arguments For instance a can be the type of integers or the type of strings def echo_string s print_string s 0 55 val echo_string string Join chan lt abstr gt spawn twice echo 0 amp twice echo_string X 5 unit OOXX 1 2 4 Synchronous channels One perfectly can have a process to return a value it suffices to parameterize it with a continu ation def succ x k print_int x k x 1 val succ int int Join chan Join chan lt abstr gt Here succ prints the value of x and then sends the message x 1 to its continuation k We insist on then when the message is received by whoever is waiting at the other end we can be sure that x has been printed Or more precisely if the receiver also prints something something should appear on the console after x Let us define a continuation for succ Chapter 1 Concurrent programming 11 def k
35. e closing parenthesis is printed only after wait O has returned let n 5 val n int 5 let tick wait create_countdown n Ess val tick unit Join chan lt abstr gt val wait unit gt unit lt fun gt Chapter 1 Concurrent programming 19 print_string for i O to n 1 do spawn begin print int i tick end done wait O print_string OH HO H HH unit 02134 As a result the numbers 0 1 2 3 4 appear in any order between parenthesis Collecting n results A frequent variation on the idea of waiting for n events is collecting n results Let us write slightly abstract code We wish to combine n results using function f let create_collector f yO n def count y n amp collect x count f x y n 1 or count y 0 amp wait reply y to wait in spawn count y0 n collect wait 35 val create_collector Ca gt b gt b gt b gt int gt a Join chan unit gt b lt fun gt The create_collector function is quite similar to the create_countdown function Additionnaly it accumulate messages sent to collect tick in the case of countdown into the first component of the internal message on count Incidentally observe that create_countdown can be implemented by using the more general create_collector let create_countdown n create_collector fun O O gt On 55 val create_countdown int gt unit Join chan unit gt unit
36. e illustrates a distributed computation with two machines Let us assume that we have a single machine here inria fr that is particularly good at computing squares of integers on this machine we define a square function that also prints something when it is called so that we can keep track of what is happening and we register this function with key square tt def f x print string string_of_int x flush stdout reply x x to f in Join Ns register Join Ns here square f 3 unit let wait def x O amp y O reply to x in x 3 val wait unit gt unit let main Join Site listen Unix ADDR_INET Join Site get local addr 12345 wait 3 val main unit The function Join Site listen creates a socket waiting connections to the local site Here the server waits connections on the default Internet addresses of the host Join Join get local addr is the first returned by Unix gethostbyname on port 12345 The call to the synchronous channel wait primitive tells the program to keep running after the completion of all local statements so that it can serve remote calls On machine here inria fr we compile the previous program p ml and we execute it here gt jocamlc p ml o p out here gt p out We also write a program that relies on the previous machine to compute squares this program first looks up for the name registered by here inria fr then pe
37. erators and amp amp 3 2 Values JoCaml has an additional kind of values channels or port names Channels have a sending side and a receiving side and can be seen as carrying messages from one side to the other Channels come in two flavors asynchronous and synchronous Sending a message on an asynchronous channel always succeeds but this tells little about whether the message is received or not at the other side of the channel Synchronous channels behave like functions 63 64 3 3 Types JoCaml has an additional primitive type the type typexpr Join chan of asynchronous channels that carry values of type typexpr The type is primitive in the sense that compiler knows about it Synchronous channels are typed as functions 3 4 Expressions ocaml expr spawn process join definition in expr expr Objective Caml expressions are extended with the expression spawn process which evaluates to O and executes process asynchronously Local definition of channels by a join definition is possible inside expressions 3 5 Processes process O process amp process expr expr expr process reply expr to lowercase ident if expr then process else process match expr with ocaml pattern when expr gt process let rec ocaml let binding and ocaml let binding in process for lowercase ident expr to downto expr do process done process begin process end join definition in process The class of p
38. erface of the name server mostly consists of two functions to register and look up arbitrary values in a global table indexed by plain strings For instance the following program contains two processes running in parallel One of them locally defines some resource a function that squares integers and registers it under the string square The other process is not within the scope of it looks up for the value registered under the same string locally binds it to sgr then uses it to print something spawn begin def f x reply x x to f in Join Ns register Join Ns here square f int gt int 0 end 55 unit spawn begin let sqr Join Ns lookup Join Ns here square int gt int in print int sqr 2 0 end 5 unit 4 lookup and register functions are parameterized by a name server Here both processes are executed in the same runtime such that they have a direct access to the local name server Join Ns here Communications through the name server are untyped This weakness involves a good pro gramming discipline 2 1 2 Running several programs in concert The runtimes that participate to a distributed computation are launched as independent executa bles e g bytecode executables generated by the compiler and linked to the distributed runtime a site Join Site is associated to each runtime Chapter 2 Distributed programming 45 The following exampl
39. ers let bufferize c let buff create_buffer in def transmit c send buff get transmit in spawn transmit send buff put 339 val bufferize a consumer gt a consumer lt fun gt The bufferize function takes a consumer as its argument and return another consumer The returned consumer simply puts messages into an internal buffer buff A concurrent agent transmit extracts the messages from the buffer and forwards them to the initial consumer c The bufferizing duplicator inserts a buffer in front of each consumer let dup_buffered c1 c2 dup bufferize c1 bufferize c2 3 val dup_buffered a consumer gt a consumer gt a consumer lt fun gt producer dup_buffered slow_consumer fast_consumer 3 unit 1 lt 1 Time elapsed 0 017 2 3 gt lt 2 4 5 gt lt 3 gt lt 4 gt lt 5 gt From the point of view of the producer a buffer is a fast consumer hence the producer still runs at full speed But now between the producer and a consumer there is a buffer that preserves ordering in place of a soup that mixes everything Additionally the consumer is now a concurrent agent that attempt to get a new value from the buffer as soon as it is done with the previous value As a result consumers execute concurrently and consume producer output in the issuing order We may feel satisfied but we are not done yet we may now consider that the producer i
40. et consumer send print_int SS val consumer int consumer send lt fun gt We connect the producer and the consumer by the means of ordinary function application producer consumer 55 unit 12345 We introduced the record type a consumer for getting the compiler to issue significant types However a consumer is nothing more than a function of type a gt unit Thus we have just explained function application in a rather contrieved manner Now we start complicating things we want to feed two consumers Those consumers are concurrent agents and we encode them as join definitions let fast_consumer let fast cons x xs Thread delay 0 1 x xs in def put x state xs print string string_of_int x let xs fast_cons x xs in print_string state xs amp reply to put in spawn state 1 send put and slow_consumer let slow_cons x xs Thread delay 0 3 x xs in def put x state xs HE OH OH FH HH HH H OH OF OF OF print string lt string_of_int x let xs slow_cons x xs in print_string gt state xs amp reply to put in spawn state 1 send put OH H HH H H OF 35 val fast_consumer int consumer send lt fun gt val slow_consumer int consumer send lt fun gt Both consumers accept integers on the synchronous channel put and accumulate integers as a list in some internal channel state However the fast consumer builds lists at
41. executed asyn chronously and produce no result whereas expressions are evaluated synchronously and their evalu ation produces values For instance Objective Caml expressions are JoCaml expressions Processes communicate by sending messages on channels a k a port names Messages carried by channels are made of zero or more values and channels are values themselves In contrast with other pro cess calculi such as the pi calculus and its derived programming language Pict channels and the processes that listen on them are defined in a single language construct This allows considering and implementing channels as functions when they have the same usage JoCaml programs are first organized as a list of top level statements A Top level statement is a declaration such as an Objective Caml binding let x 1 or a channel binding or an expression Top level statements are terminated by an optional that triggers evaluation in interactive mode 1 2 1 Simple channel declarations Channels or port names are the main new primitive values of JoCaml Users can create new channels with a new kind of def binding which should not be confused with the ordinary value let binding The right hand side of the definition of a channel a is a Y process that will be spawned whenever some message is sent on a Additionally the contents of messages received on a are bound to formal parameters For instance here is the definition of an echo channel de
42. ey can be executed in a distributed manner on several machines In this section we describe support for execution on several machines To this end we interleave a description of the model with a series of examples that illustrate the use of these primitives 2 1 The Distributed Model The execution of JoCaml programs can be distributed among numerous machines possibly running different systems new machines may join or quit the computation At any time every process or expression is running on a given machine In this implementation the runtime support consists of several system level processes that communicate using TCP IP over the network In JoCaml the execution of a process or an expression does not usually depend on its local ization Indeed it is equivalent to run processes P and Q on two different machines or to run the compound process P amp Q on a single machine In particular the scope for defined names and values does not depend on their localization whenever a port name appears in a process it can be used to form messages using the name as the address or as the message contents without knowing whether this port name is locally or remotely defined So far locality is transparent and programs can be written independently of their run time distribution Of course locality matters in some circumstances side effects such as printing values on the local terminal depend on the current machine besides efficiency can be af
43. f echo x print_int x 0 val echo int Join chan lt abstr gt The new channel echo has type int Join chan which is the type of channels carrying values of type int Sending an integer on echo fires an instance of the guarded process print_int x 0 which prints the integer on the console Since the Objective Caml expression print_int x returns the value it is necessary to append a O that discards this value O is the empty process As a regards syntax the parenthesis around the formal argument x are mandatory Channel echo is an asynchronous channel since sending a message on this channel is a non blocking operation and it is not possible to know when the actual printing takes place 1 2 2 Processes Processes are the new core syntactic class of JoCaml The most basic process sends a message on an asynchronous channel such as the channel echo just introduced Since only declarations and expressions are allowed at top level processes are turned into expressions by spawning them they are introduced by the keyword spawn spawn echo 1 unit QO spawn echo 2 unit 12 Processes introduced by spawn are executed concurrently The program above may either echo 1 then 2 or echo 2 then 1 Thus the output above may be 12 or 21 depending on the implementation The processes echo 1 and echo 2 are examples of the the most basic process sending a message on some channel
44. fected because message sending over the network takes much longer than local calls finally the termination of some un derlying runtime will affect all its local processes An important issue when passing messages in a distributed system is whether the message contents is replicated or passed by reference This is the essential difference between functions and synchronous channels When a function is sent to a remote machine its code and the values for its local variables are also sent there and any invocation will be executed locally on the remote machine When a synchronous port name is sent to a remote machine only the name is sent and invocations on this name will forward the invocation to the machine were the name is defined much 43 44 as in a remote procedure call In the current implementation of JoCaml passing a function in a distributed system is not yet implemented 2 1 1 The name server Since JoCaml has lexical scoping programs being executed on different machines do not initially share any port name therefore they would normally not be able to interact with one another To bootstrap a distributed computation it is necessary to exchange a few names and this is achieved using a built in library called the name server Once this is done these first names can be used to communicate some more names and to build more complex communication patterns To export names the JoCaml library provides a name server Join Ns The int
45. for the n events to occur by calling the synchronous channel wait The reaction rule count 0 amp wait reply to wait is to be noticed the formal argument of count is a pattern here the integer constant 0 This means that the guarded process will be firable only when message O is pending on channel count See Section 1 3 2 Beware if at some time count 0 tick and wait are active then the clause count n amp tick count n 1 can be selected As an imediate consequence count 0 will never be active again and the agent waiting on wait will stay blocked However if at most n messages are sent on tick then the device above works as expected The count n events idiom is so frequent that we build a countdown generator as follows let create_countdown n def count n tick count n 1 or count 0 wait reply to wait in spawn count n tick wait 3 val create_countdown int gt unit Join chan unit gt unit lt fun gt Now we get a fresh countdown started at n by create_countdown n More precisely a fresh countdown is the pair of asynchronous tick and synchronous wait where wait will answer once n messages are sent on tick Also observe that the internal channel count is now kept secret and that the countdown generator takes care of initialisation In the following code n messages are sent on tick by n asynchronous agents once they have printed one digit while th
46. gt 2 2 4 Build a chat room The last point to build a chat room is to know the sites that participate to the chat We use a centralize approach where each site register to a server and get in return the list of sites already registered Let s define the server part let register def state xs amp get_and_add x state x xs amp reply xs to get_and_add amp begin Join Site at_fail x def rm remove x in rm 0 end or state xs amp remove x state List filter fun x gt not Join Site equal x x xs in spawn state get and add 5 val register Join Site t gt Join Site t list lt fun gt let server Join Ns register Join Ns here register register Join Site t gt Join Site t list Join Site listen Unix ADDR_INET Join Site get_local_addr 12345 54 def waitQ abs reply to wait in wait Fo val server unit gt unit lt fun gt The register channel defines a shared data structure that store the sites registered A call to register adds a new site to the data structure and returns the previous state Sites unreachable are automatically remove from the set of sites thanks to the behavior recorded by Join Site at fail The server function exports the register channel does the call to Join Site listen and wait forever We define now the client part let client server site let ns Join Ns of site server site in let reg
47. handlers There is no miracle here the JoCaml runtime system of B intercepts exceptions raised by A and makes all exceptions whose name are E become an unique exception As a result there is only one exception E on runtime B Observe that the def exception construct is a non trivial semantical change over Objective Caml it more or less introduces matching of exception by structure but only for exceptions raised from one runtime to another Be cautious Notice that applying def construct twice to the same exception yields a fatal error By default JoCaml runtimes share all built in exception such as Not found Invalid_argument etc and the Join Exit exception 2 3 3 Typing Communications through the name service are not typed In the following example we define a synchronous channel of type int gt int and register it on the name service tt def f x reply x 1 to f 3 val f int gt int lt fun gt Join Ns register Join Ns here incr f int gt int 5 unit Then we retrieve the channel and use it with type float gt float let g Join Ns lookup Join Ns here incr float gt float 35 val g float gt float lt fun gt print_float g 0 5 unit 9 35959773756e 232 We obtain an indeterministic value and we do not have type error Notice that in most situations JoCaml will crash A good programming discipline is to define shared types in a separate file and to ann
48. hat in case a timeout occurs the computation of f is not interrupted Namely there is no way to kill a running agent However if computing f x takes more time than the timeout value timeout f x will return None It should perhaps be observed that we here rely upon the underlying Objective Caml thread implementation e we use the function Thread delay from the Thread library As an example of a computation that takes a long time to execute we select an infinite loop let rec loop Thread yield loop 5 val loop unit gt a lt fun gt Observe that we call Thread yield so as to give other threads a chance to be scheduled Here again we rely upon the underlying thread scheduler Finally we execute loop under the control of a timeout of 0 5 second match timeout 0 5 loop with None gt print_string Timeout Some _ gt print_string No timeout 3 unit O Timeout Timeout occurred in the sense that the call to the timeout function returns after about half a second However the controlled computation is still alive consuming resources For solving this issue see Section 1 10 1 1 4 3 Iterations Join patterns are also useful for expressing various programming control structures Our first example deal with iterations on an integer interval Simple loop Asynchronous loops can be used when the execution order for the iterated actions is irrelevant def loop
49. inria fr we get the two synchronous channels defined on here inria fr and define a function is_available that calls living If living returns a value then the JoCaml runtime on here inria fr is available Otherwise living raises the exception Join Exit let ns let server addr Unix gethostbyname here inria fr in Join Ns of_sockaddr Unix ADDR_INET server_addr Unix h_addr_list 0 12345 3 val ns Join Ns t let living Join Ns lookup ns living unit gt bool and kill Join Ns lookup ns kill unit gt unit 3 val living unit gt bool val kill unit gt unit let is_available try living with Join Exit gt false Ho val is_available unit gt bool let main if is_available then print_string OK else print_string KO kill O if is available then print string OK else print string KO 5 val main unit The output of this program on there inria fr is OK KO 48 The first time is_available is called the JoCaml runtime on here inria fr is running Then the call to kill stops the execution of this runtime such that the second call to is_available returns the value false Another way to deal with site termination is to use the function Join Site at_fail This function records an asynchronous channel to call when a site fails Let us define a simple example where two runtimes run on the same computer The first runtime wait
50. is value can be created as follows let name_here Unix gethostname val name_here string saumur def write_here msg reply print_endline msg to write_here val write_here string gt unit lt fun gt let here t name name here site Join Site here write write_here 52 35 val here t_user name saumur site lt abstr gt write lt fun gt Here we define only one write channel on the client This channel will be shared by all the other users In this case we cannot distinguish the user that sends the message on this channel An other solution is to create one channel by user and prefix each message by the name of the user let write_from name def write_here msg reply print endline name gt msg to write here in write here 35 val write_from string gt string gt unit lt fun gt let make_here name_there name name_here site Join Site here write write_from name_there val make_here string gt t_user lt fun gt Let s see now how two clients can exchange their user information Suppose that a client B wants to build a symmetric connection with a client A A must be added to the set of user of B and B must be added to the set of user of A The protocol is the following B sends its name name_there and a channel connect_there to A through a listen channel on A Then A uses the con
51. ister Join Ns lookup ns register Join Site t gt Join Site t list in let others register Join Site here in List iter fun site gt spawn connect to site others read par_broadcast to val client Join Site t gt unit lt fun gt The client is parameterized by the site of the server Its behavior is to get the register channel of the server Then to register and get the list of the other sites Try to connect to these sites and to executes the read function At last the main function choose the behavior to execute depending on the command line options 2 3 Limitations The actual implementation of JoCaml has some limitations Most of them comes from the messages marshaling 2 3 1 Code mobility Code mobility is not yet implemented It means that a function can not be sent on a distributed channel We illustrate this point with a JoCaml program server ml which awaits a function and a value and then does the application def apply f x reply f x to apply in Join Ns register Join Ns here server apply int gt int int gt int 339 unit let wait def x O y O reply to x Chapter 2 Distributed programming 55 in x val wait unit gt unit lt fun gt let main Join Site listen Unix ADDR_INET Join Site get_local_addr 12345 wait val main unit Then we define the following client program which connects to the server and
52. iterator and the collector of Section 1 4 1 For instance here is how one can sum the squares of all the integers in a list let square x X x 5 val square int gt int lt fun gt let sum xs let add wait collect_as_sum List length xs in def add_square x add square x in iter add_square xs wait 5 val sum int list gt int lt fun gt print_int sum digits 3 unit 285 Another variation on the same idea is making a list of squares order being irrelevant let squares xs let add wait create _ collector fun x xs gt x xs List length xs in def add_square x add square x in iter add_square xs wait val squares int list gt int list lt fun gt squares digits 5 int list 81 49 64 25 36 16 0 1 9 4 As such the functions sum and squares are not very interesting however they may act as an introduction to the more involved topic of distributed iteration Distributed iterations Sharing iterations between several agents requires more work Let us informally define an agent as some computing unit In this section an agent is represented by a synchronous channel In a more realistic setting different agents would reside on different computers For instance here are two agents squarel and square2 The agent squarel models a fast machine whereas square2 models a slow machine thanks to an artificial
53. k by performing a synchronous call on channel lock Due to the definition of lock this consumes the name free and only one thread can get a response at a time Another thread that attempts to acquire the lock is blocked until the thread that has the lock releases it by the synchronous call unlock that fires another invocation of free As in Objective Caml it is possible to introduce several bindings with the and keyword These bindings are recursive To give an example of lock usage we introduce a function that output its string argument several times let print_nns for i 1 ton do print_string s Thread delay 0 01 done 5 val print_n int gt string gt unit lt fun gt The Thread delay calls prevents the same thread from running long enough to print all its strings Now consider two threads one printing s the other printing s Chapter 1 Concurrent programming 17 spawn print_n 21 x 0 amp print_n 21 0 unit EIRP EN EN NUE NUE NUE ES MECS APR PAPER EAE As threads execute concurrently their outputs may mix depending upon scheduling However one can use a lock to delimit a critical section and prevent the interleaving of s and s let lock unlock new_lock Fo val lock unit gt unit lt fun gt val unlock unit gt unit lt fun gt spawn begin lock print_n 21 unlock 0 amp lockO print_n 21 unlock 0
54. me failure n end 0 5 val protect string unit gt a Join chan lt abstr gt Then the rule is as follows basically the exception is transmitted if the reply is to be executed after the exception following standard evaluation rules For instance in E P expression E evaluates before process P executes while in P amp P2 processes P and Pz execute independantly def a amp b failwith die reply to a amp reply to b val a unit gt unit lt fun gt val b unit gt unit lt fun gt spawn protect a a amp protect b b unit a failure b success And here is another test with three channels def a amp b amp c reply to c amp 38 if failwith die then reply to a amp reply to b else reply to b reply toa 55 val a unit gt unit lt fun gt val b unit gt unit lt fun gt val c unit gt unit lt fun gt spawn protect a a amp protect b b amp protect c c 5 unit c success a failure b failure 1 10 A complete example controlling several remote shell execu tions 1 10 1 Realistic timeouts In section we introduced the basics of programming a timeout in JoCaml A first step in a more realistic timeout is for the controlled computation to abort when the timeout expires To that aim the controlled computation must give a means to kill itself He
55. me service by socket address Basically there addr is of_site Site there addr of_sockaddr Unix sockaddr gt t Synonym for there lookup t gt string gt a Find value raise Not_found when not present or Join Exit 5 1 if attemping to lookup on a failed remote name service register t gt string gt a gt unit Register binding returns when done Raise J oin Exit 5 1 if attempting to register on a failed remote name service 74 5 2 Module JoinCount Counting n asynchronous events The following submodules are succesive refinements of the count n events programming idiom Here an event is a message sent on an asynchronous channel JoinCount Down 5 2 just counts n messages sent on a tick channel o JoinCount Collector 5 2 additionnaly computes a resut from the nessages sent on a collect channel e JoinCount Dynamic 5 2 is a refinment of Collector where n is not known in advance module Down sig type Ca b t tick unit Join chan wait unit gt unit val create int gt a b t create n returns a countdown c for n events That is after n messages on c tick the call c wait will return Observe that at most one call c wait returns end Simple countdowns module Collector sig type Ca b t collect a Join chan wait unit gt b Type of collectors Collectors are refinements of countdowns which collect and combine n pa
56. ml let definitions channel definitions are always potentially recursive Since synchronous channels have the same type and behave like functions they seem useless However there are significant differences as explained by the next section on join patterns and by the next chapter on distributed programming 1 3 Join patterns Join patterns significantly extend port name definitions 12 1 3 1 Basics A join pattern defines several ports simultaneously and specifies a synchronization pattern between these co defined ports For instance the following source fragment defines two synchronizing port names fruit and cake def fruit f amp cake c print_endline f c 0 55 val fruit string Join chan lt abstr gt val cake string Join chan lt abstr gt To trigger the guarded process print endline f c 0 messages must be sent on both fruit and cake spawn fruit apple amp cake pie 5 unit apple pie The parallel composition operator amp appears both in join patterns and in processes This high lights the kind of synchronization that the pattern matches Join definitions such as the one for fruit and cake provide a simple mean to express non determinism spawn fruit apple amp fruit raspberry cake pie amp cake crumble 5 unit raspberry pie apple crumble Two cake names must appear on the console but both combinations of fruits and cakes are
57. n closed or killed e f get k retrieve one element from the fifo The channel k receives a a option message where None expresses that the fifo is closed Some x expresses that element x is retrieved from the fifo Operations close and kill both close the fifo but with different behaviors as regards non empty fifos e f close waits for the fifo to be empty before closing it and returning e f kil10 is an asynchronous channel sending a message on f kill closes the fifo immedi ately In the producer consumer scheme f close is for the producer to signal the end of produced elements while f ki11 is for the consummer to signal that it will not accept more elements Chapter 5 The JoCaml library Producer consumer interface module P sig type at put a bool Join chan Join chan close unit gt unit end Type of producers module C sig type at get a option Join chan Join chan kill unit Join chan end Type of consumers val create prod cons unit gt a P t a C t Create a pair of producer consumer connected by a fifo Producer have the put and close operations while consumer have the get and kill operations Synchronous interface Type of fifo with synchronous operations module sig exception Closed type at put a gt unit get unit gt a close unit gt unit kill unit gt unit
58. nect_there channel to send back to B its user information and A obtains in return the B user information So the listen channel on A and the connect channel on B are defined as follows def listen name_there connect_there let here name name_here site Join Site here write write_from name_there in let user_there connect_there here in new user user there val listen string t_user gt t_user Join chan lt abstr gt def connect_here user_there let here name name_here site Join Site here write write_from user_there name in reply here to connect here HH HH Chapter 2 Distributed programming 53 amp new_user user_there val connect_here t_user gt t_user lt fun gt The listen channel is exported through the name server to allow to create some connections type t_connect t_user gt t_user 5 type t_connect t_user gt t_user type t_listen string t_connect Join chan 5 type t_listen string t_connect Join chan let Join Ns register Join Ns here listen listen t_listen to So to build a connection from a site identity we define the channel connect_to as follows def connect_to site let ns Join Ns of_site site in let listen_there Join Ns lookup ns listen t_listen in listen_there name_here connect_here 3 val connect_to Join Site t Join chan lt abstr
59. nit lt fun gt This function terminates when there are no more characters to read To implement the broadcast we first have to define a type that represents a user and a data structure that allows to store the other users type t_user name string site Join Site t write string gt unit Fo type t user name string site Join Site t write string gt unit let get add remove def state x amp get state x amp reply x to get or state x amp add user state user x amp reply to add or state x amp remove s state List filter fun user gt not Join Site equal user site s x in spawn state get add remove HH H HH 33 val get unit gt t_user list lt fun gt val add t_user gt unit lt fun gt val remove Join Site t Join chan lt abstr gt Each user is defined by his name the site where he executes its client and the channel that allows to write on console of his client To manipulate the set of users there are the channels get add and remove get returns the list of the other users add puts a new user into the set of users and remove remove the user executed on a given site Notice that to test the equality of two sites we have to use the function Join Site equal we cannot use and may return a wrong value A simple way to broadcast a message is to send the message to each user in a sequential way 50 let seq_broadcas
60. nt int Col t Col collect lt abstr gt Col wait lt fun gt spawn for i 0 to n 1 do col Col collect i done unit QO print_int col Col wait unit 45 In the code above one should probably noticed that the field names of records are given in fully qualified notation as for instance col Col wait Bi directional channels Bi directional channels appear in most process calculi In the asynchronous pi calculus for instance and for a given channel c a value v can be sent asynchronously on c written c v or received Chapter 1 Concurrent programming 21 from c and bound to some variable x in some guarded process P written c x P Any process can send and receive on the channels they know In contrast A JoCaml process that knows a channel can only send messages on it whereas a unique channel definition receives all messages Finally the scope of a pi calculus channel name c is defined by the new c in P operator Such an operator does not exist in JoCaml since join definitions are binding constructs Nonetheless bi directional channels can be defined in JoCaml as follows let new_pi_channel def send x amp receive reply x to receive in send receive 5 val new_pi_channel unit gt a Join chan unit gt a lt fun gt A pi calculus channel is implemented by a join definition with two port names The port name send is asynchronous and is used to sen
61. okQ begin try Unix kill pid Sys sigkill with _ gt end 0 in spawn begin ok amp let a try Some input_line inchan with End_of_file gt None in close_in inchan match a snd Unix waitpid pid with Some a Unix WEXITED O gt result a _ _ gt 0 end wait kill val create_arch string gt unit gt string unit Join chan lt fun gt The function create_arch first performs the remote call by calling rsh_arch The run function is the synchronous wait channel As shown by its synchronization pattern it transmits one result one message on the internal channel result to its caller The message on result is sent by another concurrent agent that reads one line from from the remote arch output and then check the proper termination of the forked command by Unix waitpid Additionally a kill channel offers the ability to kill the forked Unix process Finally thanks to the internal channel ok either wait will return a valid value or the forked process will be destroyed as the result of a timeout 1 10 3 Collecting results We intend to execute arch on several remote machines all those executions being performed con currently Hence we need a way to collect n results produced concurrently The task of collecting those results is performed by using the collectors of the standard library see section let collector n Col create fun x xs gt match x with
62. on cannot be established listen Unix sockaddr gt unit Start to listen for connections on the socket address given as argument Raises Failure in case of failure where from a Join chan gt t where_from c returns the identity of the remote site where reception on channel c takes place equal t gt t gt bool Test the equality of two sites compare t gt t gt int Compare two sites order is arbitrary at_fail t gt unit Join chan gt unit at_fail s c registers channel c as a guard on failure of site s If s failure is detected a message is sent on channel c At the moment site failure detection is a bit unsafe due to naive routing A failure may express the impossibility to contact a remote site for the first time get_local_addr unit gt Unix inet_addr Chapter 5 The JoCaml library 73 end Returns the default Internet address of the local site never fails At worst get_local_addr returns the loopback address Unix inet_addr_loopback Dynamic unsafe value repository module Ns sig Dynamic unsafe value repository Every site offers a name service T he name service provides a mapping from strings to values type t Val Val Val Val Val Val end Abstract type for the name service here t The local name service of site Join Site t gt t Get remote name service by site identity there Unix sockaddr gt t Get remote na
63. oncurrent programming 27 let register wait create_sum 32 o val register int gt int Join chan lt abstr gt val wait unit gt int lt fun gt spawn register squarel amp register square2 unit QO print_int wait Ho unit QO 00000 lt 00000000000000000000000000 gt 10416 1 5 Data structures 1 5 1 A concurrent reference cell Object states represented as join patterns can be altered by invoking the appropriate methods Here is a definition for a reference cell One method get examines the content of the cell while another put alters it let create_ref yO def state y amp get state y amp reply y to get or state _ amp put y state y amp reply to put in spawn state y0 get put Ho val create ref a gt unit gt a a gt unit lt fun gt Here the internal state of a cell is its content its is stored as a message y on the channel state Lexical scoping is used to keep the state internal to a given cell let gi pi create_ref 0 and gs ps create_ref val gi unit gt int lt fun gt val pi int gt unit lt fun gt val gs unit gt string lt fun gt val ps string gt unit lt fun gt 1 5 2 A concurrent stack A stack is a data structure that provide push and pop operations with LIFO Last In First Out semantics let new_stack def state s amp push v
64. otate the functions Join Ns register and Join Ns lookup with these types Exceptions transmitted as ordinary messages are not intercepted 60 Part II User Manual Chapter 3 The JoCaml language This document is intended as a reference manual for the JoCaml language JoCaml is an extension of Objective Caml and this manual addresses only the constructs which are new with respect to Objective Caml introducing syntax and informal semantics for the new constructs A good working knowledge of Objective Caml is assumed Notations The syntax of the language is given in BNF like notation Terminal symbols are set in typewriter font like this Non terminal symbols are set in italic font like that Square brackets denote optional components Curly brackets denotes zero one or several repetitions of the enclosed components Curly bracket with a trailing plus sign denote one or several repetitions of the enclosed components Parentheses denote grouping 3 1 Lexical issues JoCaml has the same lexical conventions as Objective Caml with additional keywords spawn def and reply Keywords or and amp exist in both languages but with very different meanings As a consequence JoCaml users cannot use or and amp for the boolean connectors or and and Notice that this practice is deprecated in Objective Caml to express boolean connectors one should in Objective Caml and must in JoCaml use the op
65. our competing behavior on the pair of channels f and d For instance spawn f Raspberry amp d Pie amp d Cake 3 unit raspberry pie And we get either raspberry pie or raspberry cake The formal argument of channels can be any Objective Caml pattern Here by using or patterns and as bindings for fruits we can be more concise let string_of_fruit function Apple gt apple Raspberry gt rasperry Cheese gt cheese 5 val string_of_fruit fruit gt string lt fun gt def f ApplelRaspberry as x amp d Pie echo_string string_of_fruit x pie or f Raspberry Cheese as x amp d Cake echo_string string_of_fruit x cake 35 val f fruit Join chan lt abstr gt val d desert Join chan lt abstr gt spawn f Raspberry amp d Pie amp d Cake os unit rasperry pie And again the above display can be either desert with raspberry As another example the following definition prints the sorted merge of two sorted lists sent as messages on channels i1 and i2 E Aa def i1 i2 0 or il x xs amp i2 print int x i1 xs i2 or i1 1 i2 y ys print_int y i1 amp i2 ys or il x xs amp i2 y ys if x lt y then begin print_int x il xs amp i2 y ys end else if y lt x then begin print int y il x xs i2 ys end else begin print int x i1 xs amp i2 ys end OH H
66. p s loop 5 def k Semaphore v s O in k HH H val agent int Join chan lt abstr gt spawn agent 1 amp agent 2 amp agent 3 to unit 233333222211111 As to semaphore semaphore semantics in the ouput above there must be an initial value maybe 1 and a final value maybe 3 such all instances of the initial value apear before the instances of the final value 34 1 8 A word on typing The JoCaml type system is derived from the ML type system and it should be no surprise to ML programmers The key point in typing la ML is parametric polymorphism For instance here is a polymorphic identity function def id x reply x to id 35 val id a gt a lt fun gt The type for id contains a type variable a that can be instantiated to any type each time id is actually used Such a type variable is a generalized type variable For instance in the following 448 mI program variable a is instantiated successively to int and string let i id 1 and s id coucou 55 val i int 1 val s string coucou print_int i print_string s 55 unit 1coucou In other words the first occurrence of id above has type int gt int while the second has type string gt string Experienced ML programmers may wonder how JoCaml type system achieves mixing parametric polymorphism and mutable data structures There is no miracle here Consider
67. plete JoCaml distribution can be accessed via the Web site http jocaml inria fr This Web site contains some additional information on JoCaml Acknowledgements We thank the whole Objective Caml development team and in particular Xavier Leroy for giving us full access to source code computer resources names logos etc All bugs we have introduced are ours JoCaml and this manual owe much to previous work by numerous people including Fabrice Le Fessant C dric Fournet and Alan Schmitt The software authors are Luc Maranget Ma Qin and Louis Mandel Part I An introduction to JoCaml Chapter 1 Concurrent programming This part of the manual is a tutorial introduction to JoCaml This chapter starts with small local examples Then it deals with the distributed features It is assumed that the reader has some previous knowledge of Objective Caml 1 1 Conventions Examples are given as JoCaml source followed by the output of the top level or of the compiler when prompted to print types The JoCaml top level provides an interactive environment much as the Objective Caml top level In order to try the examples you can either type them in a top level launched by the command jocaml or concatenate the sources chunks in some file a m1 then compile a ml1 by the command jocamlc a ml and finally run the produced code by the command a out 1 2 Basics JoCaml programs are made of processes and expressions Roughly processes are
68. provided two invocations register square1 and register square2 are active let register wait create_sum 32 5 val register int gt int Join chan lt abstr gt val wait unit gt int lt fun gt spawn register square2 amp register squarel 5 unit print_int wait 5 unit lt lt O lt lt O lt O OK lt KO OK lt KO OK OK lt 0 O lt lt O OKO O OC lt lt gt gt gt gt gt gt gt gt gt gt gt gt gt gt gt gt 10416 The distributed loop above is not satisfactory since it does not take the relative computing speed of square1 and square2 into account while allocating iterations The add square x jobs are spawned asynchronously so that all iterations are performed concurrently As a result the iteration space is partitioned randomly between squarei and square2 as illustrated by the output above which can be about anything This leads to a poor load balance in fact to no load balance at all 26 A better solution is for an agent to execute its share of work in sequence rather than concurrently This is achieved by the slightly modified definition for def add square x amp register square below let create_sum n let add wait collect_as_sum n in def add_square x amp register square let r square x in add r amp register square in for i 0 to n 1 do spawn add_square i done register wait 33 val create_sum int gt int gt int
69. r gt val set a gt unit lt fun gt spawn state 0 unit let x get val x int 0 print string x 3 Error This expression has type int but is here used with type string Non generalized type variables appear when the type of several co defined port names share a type variable Such a type variable is not generalized def port p amp arg x p x 5 val port _a Join chan Join chan lt abstr gt val arg _a Join chan lt abstr gt A workaround is to encapsulate the faulty names into a function definition This restores polymor phism let create it def port p arg x p x in port arg 35 val create_it unit gt a Join chan Join chan a Join chan lt fun gt Non generalized type variables also appear in the types of the identifiers defined by a value binding let pi al p2 a2 create_it create_it 33 val pi _a Join chan Join chan lt abstr gt val al _a Join chan lt abstr gt val p2 _a Join chan Join chan lt abstr gt val a2 _a Join chan lt abstr gt spawn pl echo amp p2 echo string 3 unit O ai a2 339 int Join chan string Join chan lt abstr gt lt abstr gt spawn al 1 amp a2 coucou 35 unit coucoul It is interesting to notice that invoking create_it twice yields two different sets of port and arg port names whose types
70. re we define a infinite loop that computes a function step at each iteration and that can be killed between two iterations exception Killed Ho exception Killed let create_loop step def run ok ok amp reply step run to run or run killed reply raise Killed to run or kill okQ killed in let loop spawn ok run in loop kill HH HH 35 val create loop unit gt a gt unit gt b unit Join chan lt fun gt let run kill create_ loop fun gt print_string Thread delay 0 01 5 val run unit gt a lt fun gt val kill unit Join chan lt abstr gt The channels ok and killed are used internally they express the status of the computing agent At a given time there is a message pending on either ok or killed In the first situation computation can go on while in the second situation computation is interrupted and an exception is raised as a reply to whoever called run The computation is controlled from outside by the means of one function loop to compute a result here to loop and of one asynchronous channel kill to stop computing Chapter 1 Concurrent programming 39 The new timeout function is a small improvement over the previous one when the delay has expired we also kill the computation by sending a message on the adequate channel ki11 which is passed to timeout for that purpose let timeout t f x kill def w
71. rforms some computations and reports their results let server let server_addr Unix gethostbyname here inria fr in Join Site there Unix ADDR_INET server_addr Unix h_addr_list 0 12345 val server Join Site t let ns Join Ns of_site server val ns Join Ns t let sqr Join Ns lookup ns square int gt int 46 33 val sqr int gt int let log s x print string q s string of int x An flush stdout 35 val log string gt int gt unit let rec sum s n if n 0 then s else sum stsgr n n 1 35 val sum int gt int gt int log sqr 3 sqr 3 log sum 5 sum O 5 35 unit This program first connects to here inria fr 12345 with the function Join Site there to get the abstract value server which represents the JoCaml runtime on here inria fr and it gets the name server with the function Join Ns of_site notice that there is the function Join Ns of_sockaddr to get directly the name server from the socket address Then it defines sqr as the square channel of here inria fr The sum function computes the sum of squares using the sqr function On another machine there inria fr we compile and run our second program q m1 there gt jocamlc q ml o q out there gt q out What is the outcome of this computation Whenever a process defines new port names this is done locally that is their guarded processes will be executed at the same pla
72. rieve raise_e from the name service of A and send E on channel raise_e On runtime B exception E 33 exception E let raise_e Join Ns lookup ns raise_e exn gt unit 35 val raise_e exn gt unit lt fun gt try raise_e E with E gt print string E is raised gt print string An exception is raised 55 unit O An exception is raised And here although the remote site A apparently raises an exception defined on site B it in fact raises a copy of it This copy is then copied once more while transmitted back to site B Since exception matching is performed by using pointer equality it makes the difference beetween those two copies A specific mecanism somehow solves the problem of exceptions raised by remote runtimes One may apply the mecanism to any pre existing exception by the declaration def exception for instance on runtime B Runtime B def exception E 3 Then we can try our two examples again still on runtime B try raise_E with E gt print string E is raised gt print string An exception is raised 5 unit E is raised try raise_e E with E gt print string E is raised gt print string An exception is raised Chapter 2 Distributed programming 59 unit E is raised And now both the copy of the other E defined on site A raise_E and the copy of copy of E match E in the exception
73. ritten to via the returned output channel val open_in_out string gt string array gt int Pervasives in_channel Pervasives out_channel Redirects both standard output and input of the forked command to pipes Returns pid outch inch where outch is for reading the forked command standard output and inch is for writing the forked command standard input val open_full string gt string array gt int Pervasives in_channel Pervasives out_channel Pervasives in_channel Redirects all three standard channels of the forked command to pipes Returns pid outch inch errch where outch and errch permit reading the forked command standard output and standard error respectively while inch permits writing on the forked command standard input Chapter 5 The JoCaml library 79 Some of Objective Caml modules are included in the JoCaml distribution The core library Pervasives The whole standard library The Unix library By contrast with Objective Caml users programs are linked with the Unix library by default The threads libraries are present in a different form By contrast with Objective Caml users programs are linked with one of threads library by default All the functionalities of Objective Caml threads are present However users should probably refrain from creating threads explicitely The Graphics library The Dynlink library Other Objective Caml libraries are available through a companion Objective
74. rocess reply expr to lowercase ident sends the value of expr as a reply on the synchronous channel lowercase ident which must be the name of a synchronous channel The reply construct is of course to be used while defining the receiving side of a synchronous channel On the other side sending a message on a synchronous channel is very similar to calling a function and the replied expr is like the value returned by a function call There are severe linearity constraints over the usage of reply Linearity constraints here mean that the compiler enforces that exactly one reply to a given channel is allowed For instance in process amp process the processes process and process must reply to disjoint sets of channels while in ifexpr thenprocess elseprocess the processes process and process must reply to the same channels 3 5 2 Composed processes Composed processes are the equivalent of some of the control structures of Objective Caml but at the process level Sequence The process expr process evaluates expr first then it executes process The expression must be of unit type by contrast with Objective Caml Notice that the item before the semicolon is an expression not a process a process there would be meaningless Operator binds tighter than operator As a result expr process amp process is legal syntax and expr evaluates before both process and process execute Moreover process amp expr processo is illeg
75. rocesses is the main syntactical extension of JoCaml with respect to Objective Caml Processes have no result By convention we say that processes are executed while expressions are evaluated to some result Moreover expressions may fail to produce a result and instead raise an exception The matching concept for processes is abnormal termination When a process terminates abnormally the JoCaml runtime system issues a warning message 3 5 1 Basic processes Those are directly inspired from the join calculus Inert process The simplest process is 0 concrete syntax is the digit 0 This process does nothing Chapter 3 The JoCaml language 65 Grouping The processes process and begin process end execute as process does Both constructs are semantically equivalent using one construct or the other is a matter of style Asynchronous send Asynchronous send expr expr evaluates expr to an asynchronous channel and expr to a value Then the value is sent on the channel Notice that the syntax is the one of func tion application but in process context Although the syntax is quite general common us age is simpler Most often expr is a channel name while expr is a tuple of expressions lowercase ident expr expro CXpr Concurrent execution The operator amp is the parallel composition Executing process amp process amounts to executing process and process concurrently Reply to synchronous sends The p
76. rrency at all consumers execute sequentially and the producer waits for both consumers A first idea to have consumers to execute concurrentlty is to send the integers to them asynchronously Ideally we should change the type of consumers making it to be send a Join chan So as not to rewrite everything we write a wrapper that simply spawns calls to the send function of consumers Chapter 1 Concurrent programming 31 let asynchronyze c send fun x gt spawn c send x 0 5 val asynchronyze a consumer gt a consumer lt fun gt let async_slow asynchronyze slow_consumer and async_fast asynchronyze fast_consumer to val async_slow int consumer send lt fun gt val async_fast int consumer send lt fun gt producer dup async_slow async_fast 5 unit lt 1 1 Time elapsed 0 017 5 4 gt lt 5 3 2 gt lt 4 gt lt 3 gt lt 2 gt Now consumers execute concurrently and producer speed is unconstrained From the point of view of the producer we are connected to a fast consumer From the point of view of a consumer we select integers at random amongst a soup of asynchronous messages Consumers can execute concurrently because they are messages for both of them in the soup simultaneously However as a result of all messages being sent asynchronously the ordering on producer output is lost To recover that ordering while preserving concurrent execution we can use buff
77. rtial results type a into a final result type b Given a collector c for n events with combining function comb and initial result yO e The n events x1 xn are sent as n messages on c collect Notice that the notation xi does not imply any kind of ordering e Then c wait returns the value comb x1 comb x2 comb xn y0 Again at most one call c wait returns val create Ca gt b gt b gt b gt int gt Ca b t Chapter 5 The JoCaml library 75 create comb yO n returns a collector of n events of type a with combining function comb and initial result yO end Collecting countdowns or collectors module Dynamic sig type Ca b t enter unit gt unit leave a Join chan wait unit gt b finished unit Join chan Dynamic collectors are refinement of simple collectors for which the number of events to collect need not be given in advance Given a dynamic collector c defined as create comb y0 e c is informed of the future occurence of an event xi by sending an unit message on c enter e c is informed of the occurence of event xi by sending a message c leave xi e cis informed that no more event will occur by sending a message c finished Then the call c wait O will return the combined result comb x1 comb x2 comb xn y0 once all the announced events have occured Observe that at most one such call is allowed val create a
78. ruct somehow aleviates the burden of having generative exceptions in a dis tributed context The name exception must be the name of a pre existing exception and def exceptionexception must be executed at most once See Section for an example 68 Chapter 4 JoCaml Tools 4 1 A few words on implementation s The JoCaml system is structured as the Objective Caml system with a bytecode compiler jocamlc and a native code compiler jocamlopt In fact JoCaml is a modified Objective Caml The JoCaml compilers translate Join constructs into function calls to an ad hoc library The ad hoc library is an extension of the thread library of Objective Caml which we simply call the threads library The threads library comes in two flavors virtual machine level threads and system level threads JoCaml uses system level threads by default As a result of its design JoCaml inherits the limita tions of Objective Caml thread implementations In particular there can be at most one thread actually executing at a time even on multi core machines The compilers jocamlc and jocamlopt should be binary compatible with Objective Caml More precisely while installing JoCaml a companion Objective Caml is defined The companion system must have the same version number as the JoCaml system Then the search paths for the compiler are completed by the ones of the companion system For that reason JoCaml distribution includes a limited subset of Objective Caml libr
79. s for some connections let wait def x O y O reply to x in x Ho val wait unit gt unit let main Join Site listen Unix ADDR_INET Join Site get_local_addr 12345 wait Ho val main unit The second runtime gets the site listening on port 12345 and registers the channel echo_failure on the failure of this site let server Join Site there Unix ADDR_INET Unix inet_addr_loopback 12345 3 val server Join Site t lt abstr gt def echo_failure print string FAILURE print newline 0 in Join Site at_fail server echo_failure 35 unit let wait def x O y O reply to x in x Hs val wait unit gt unit lt fun gt let main wait Ho val main unit If we execute these two runtimes and kill the first one with Ctrl c for example then the second runtime prints FAILURE Chapter 2 Distributed programming 49 2 2 A complete example We want to build a very simple chat system where each user can broadcast a message to all the others 2 2 1 Behavior of a client The client is the part of the system executed by each user The behavior of the client is to read messages from the user and broadcast them to the other clients let read broadcast try while true do let msg input_line stdin in broadcast msg done with End_of_file gt HH HH 339 val read string gt a gt u
80. s too fast and that it fills the buffers needlessly It may be a good idea for the producer to wait for one 32 message to be consumed by someone before issuing the next message That way we avoid filling up buffers To that aim we attach a fresh tick channel to each message issued by the producer and then wait for a message on tick let add_tick c let send_ticked x def wait tick reply to wait in c send tick x wait in send send_ticked 35 val add_tick unit Join chan a consumer gt a consumer lt fun gt let ticked_producer c producer add_tick c Ho val ticked_producer unit Join chan int consumer gt unit lt fun gt At the consuming end we remove the tick transmit the actual message to the actual consumer and then once the messsage is accepted issue a message on tick let remove_tick c let send_unticked tick x c send x spawn tick in send send_unticked val remove_tick a consumer gt unit Join chan a consumer lt fun gt let ticked_slow remove_tick slow_consumer and ticked fast remove tick fast consumer val ticked_slow unit Join chan int consumer send lt fun gt val ticked_fast unit Join chan int consumer send lt fun gt Then we combine the ticked producer and the ticked consumers as we did for unticked ones ticked_producer dup_buffered ticked_slow ticked_fas
81. state v s amp reply to push or state x s amp pop state s amp reply x to pop in 28 spawn state pop push Hs val new stack unit gt unit gt a a gt unit lt fun gt The first join pattern state s amp push v is an ordinary one it is matched whenever there are messages on both state and push The second join pattern state x s amp pop uses algebraic pattern matching This pattern is matched only when there are messages on both state and pop and the state content is an non empty list As a consequence an attempt to retrieve an element from an empty stack is not an error answering to pop is simply postponed until the stack fills in let pop push new_stack 35 val pop unit gt _a lt fun gt val push a gt unit lt fun gt spawn echo pop 35 unit 0 push 1 33 unit 1 1 5 3 Buffers A buffer is some kind of double ended queue Elements are added at the one end with put and retrieved at the other end with get That is a buffer preserves elements ordering type a buffer put a gt unit get unit gt a 35 type a buffer put a gt unit get unit gt a For us put and get are synchronous channels and a get attempt on an empty buffer is blocking By contrast a put attempt always succeeds our buffer is unbounded Using the trick of encoding a FIFO queue functionnaly
82. t Ho unit O lt 1 1 2 3 gt lt 2 4 5 Time elapsed 0 52 gt lt 3 gt lt 4 gt lt 5 gt As we can see producer speed is now more or less the speed of the fast consumer 1 7 Modules JoCaml relies on the same module system as Objective Caml For example a Semaphore module can be defined with the following interface module type Semaphore sig type t val create int gt t Chapter 1 Concurrent programming 33 val p t gt unit val v t gt unit end to module type Semaphore sig type t val create int gt t val p t gt unit val v t gt unit end The type t of a semaphore is an abstract type Function create n returns a new semaphore initialized with the value n p and v are the atomic functions to manipulate semaphores The implementation of semaphores can be done as the one of locks see section 1 4 1 module Semaphore Semaphore struct type t unit gt unit unit gt unit let create n def p s reply to p and v s reply to v in for i 1 to n do spawn s done p v let p prolagen _ prolagen and v _ verhogen verhogen end 5 module Semaphore Semaphore And here an example of the usage of module Semaphore let s Semaphore create 2 3 val s Semaphore t lt abstr gt def agent x def loop n k match n with 0 gt KO n gt print int x loop n 1 k in Semaphore
83. t msg List iter fun user gt try user write msg with _ gt get Ho val seq_broadcast string gt unit lt fun gt We can also implement a parallel broadcast using countdown introduced section let create_countdown n def count n amp tick count n 1 or count 0 wait reply to wait in spawn count n tick wait Fo val create countdown int gt unit Join chan unit gt unit lt fun gt let par broadcast msg let others get in let tick wait create_countdown List length others in List iter fun user gt spawn begin begin try user write msg with _ gt end tick end others HO HH H HH H OH OF val par_broadcast string gt unit lt fun gt Here the broadcast terminates when all the messages are sent An other solution that does not wait that all the messages are sent and that preserves the order of the messages is to use the buffer introduced section in So we define a function that replace the write channel of a user by a write channel with a buffer type a buffer put a gt unit get unit gt a to type a buffer put a gt unit get unit gt a let create_buffer def alive xs y ys amp get alive xs ys amp reply y to get or alive _ _ as xs amp get alive List rev xs reply get to get or alive xs ys amp put x alive x xs ys amp reply to put in spawn
84. t ref gt int ref lt fun gt let r ref 21 val r int ref contents 21 let r id r Ho val r int ref contents 21 r Ir 2 print_int r Ho unit 21 Here we can see that r is not modified by r r 2 because r and r are two different reference cells When a mutable value go through the network a new copy is created We can notice that we have the same behavior for exceptions let ns Join Ns of_sockaddr Unix ADDR_INET Join Site get local addr 12345 3 val ns Join Ns t lt abstr gt let id Join Ns lookup ns id exn gt exn Ho val id exn gt exn lt fun gt exception E 55 exception E try raise id E with E gt print_string E is raised gt print_string An exception is raised 33 Chapter 2 Distributed programming 57 unit 0 An exception is raised Another similar more frequent situation occurs when the remote site raises an exception as an answer to a synchronous call When all executions take place in the same runtime everything is fine def f let _x raise E in reply to f 5 val f unit gt unit lt fun gt try f O with E gt print string E is raised _ gt print string An exception is raised 33 unit E is raised But now assume the following code on one runtime A whose name service is used Runtime A
85. uence may be terminated by an empty process that does nothing and is denoted by 0 Thus an alternative to the previous example is as follows spawn begin print int 1 print int 2 print int 3 O end Ho unit 123 This is why print int x O in the definition of the echo channel is considered as a process 1 2 3 More on channels The guarded process in a channel definition can spawn several messages as in a stuttering echo channel def echo_twice x echo x echo x 55 val echo_twice int Join chan lt abstr gt It is also possible to define directly such a channel without referring to the channel echo but by using the Objective Caml function print_int In this case it is necessary to enclose each use of print_int in and as in this new definition of echo_twice def echo_twice x print_int x 0 print_int x 0 35 val echo_twice int Join chan lt abstr gt 10 Such grouping is necessary because amp binds more tightly than as in def echo3 x print_int x echo x amp echo x 35 val echo3 int Join chan lt abstr gt Channels may accept tuple of values as arguments and those arguments can be destructured with pattern matching notation For example the following channel f accepts pairs as shown by its type def strange_echo x y echo x y amp echo y x 3 val strange_echo int int Join chan lt abstr gt Henc
86. ure of the remote site val exit hook unit gt unit Hook to be given as argument to Pervasives at exit This will somehow control termination of program More precisely program terminates when they is no more work to achieve This does not apply to program engaged in distribution See also Pervasives at exit caml inria fr pub docs manual ocaml libref Pervasives html VALat_exit type a debug string gt a unit string unit Pervasives format4 gt a The type of the argument of J oin debug 5 1 val debug a debug Print a message on standard error Usage debug tag fmt e fmt is in printf style e tag is a string A lock is taken so that messages do not interleave 71 72 See also The Printf module http caml inria fr pub docs manual ocam1 libref Printf html Site definition module Site sig Sites are abstractions of JoCaml runtimes Sites have unique identities which can be passed on channels computed from Internet addresses or extracted from asynchronous channels Sites must be compared with the equal and compare functions of this module Sites are useful for performing crude failure detection See J oin Site at fail 5 1 below type t val val val val val val val val The type of site identities here t Local site identity there Unix sockaddr gt t Get identity of the remote site listening on sockaddr Raise Failure if the connecti
87. x succ x echo val k int Join chan lt abstr gt spawn succ 1 k Ho unit 123 And we have yet another example of printing 123 in that order Although it can be fun continuation passing style is not very convenient JoCaml provides synchronous channels to define processes that return values more directly The previous example can be written as follows def succ x print_int x reply x 1 to succ 5 val succ int gt int lt fun gt The type of succ is the functional type int gt int that takes one integer as argument and returns an integer However succ is not a function because it is introduced by a def binding Since the process terminates with reply x 1 to succ succ is a synchronous channel which returns the x 1 value The mechanism to return values for synchronous channels is different from the one for functions it uses a reply to construct whose semantics is to send back some values as result This is the first difference with plain Objective Caml functions which implicitly return the value of the guarded expression instead of using the explicit reply to Synchronous names can be used to support a functional programming style A traditional example is the Fibonacci function def fib n if n lt 1 then reply 1 to fib else reply fib n 1 fib n 2 to fib 3 val fib int gt int lt fun gt print_int fib 10 3 unit 89 In contrast with Objective Ca

The JoCaml language Release 3.11 - The JoCaml system

Contents

Download Pdf Manuals

Related Search

Related Contents