%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This code implements a simple CTR interpreter. % % It assumes that backtrackable updates are provided. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This version implements exceptions and interupts by using updates. % Most of the exception handling code deals with events, of which % exceptions and interupts are special cases. % % EVENT HANDLING: % To throw an event, E, a CTR program executes the predicate throw(E). % The predicate try(G,E,A) catches and handles thrown events. % Intuitively, this predicate means that if goal G throws an event that % unifies with E, then action A is excecuted to handle the event. (If % the event does not unify with E, then it is passed up to the next % level.) If the event is an exception, then execution of the goal is % terminated and the handler is executed. If the event is an interupt, % then execution of the goal is suspended, the handler is executed, and % execution of the goal is then resumed. If the goal consists of % several processes, then each one is terminated or suspended, depending % on the event. % % IMPLEMENTATION: % Each thrown event takes place in the context of an enclosing try % predicate. To catch the event, each try has its own communication % channel. Each time a try is executed, a new channel is created. When % an event is thrown, the atom event(C,E) is inserted into the database. % Here, C is the communication channel for the enclosing try, and E is a % function term of the form exception(X) or interupt(X) representing the % event. The enclosing try reads the atom event(C,E), deletes it from % the database, and then processes the event. Communication channels % are represented as natural numbers, and the base predicate % maxChannel(N) records maximum channel number so far created. This % number is initialized to 0 and is incremented each time a new channel % is created. :- import ins/1, del/1 from updates. :- import append/3 from basics. % USER INTERFACE: To execute a goal, the user types exec(Goal). In % addition to executing the goal, this predicate creates the first % communication channel for catching events. It also surrounds the goal % by a try to handle any uncaught exceptions. exec(Goal) :- C=0, ins(maxChannel(C)), execute(all, C, try(Goal,E,write([uncaught,event,E]))), del(maxChannel(_)). % THE INTERPRETER: The predicate execute(Flag,C,Goal) executes Goal by % recursively executing hot components one at a time until the empty % goal (state) is reached. Here, C is a communication channel for % handling events. % % The variable Flag affects concurrency. Given a set of concurrent % processes, Flag specifies how many different interleavings of these % processes should be checked. The value of Flag (and thus the % treatment of concurrency) is fixed within the scope of each % isolation operator. At present, regardless of the value of Flag, % the first interleaving to be checked is always based on round-robin % scheduling. % % At present, Flag can take two values, "all" and "one." When Flag=all, % the interpreter checks all possible interleavings of the processes until % one is found that succeeds. When Flag=one, the interpreter checks % only one interleaving. This is useful for commutative transactions, % where all interleavings give the same result. In this case, if one % interleaving fails, then they all fail, so there is no point of % checking more than one interleaving. The value of flag is initially % "all" (see above), and can be changed by each isolation operator (see % below). execute(Flag,C,state) :- !. execute(Flag,C,Goal1) :- oneStep(Flag,C,Goal1,Goal2), execute(Flag,C,Goal2). % Execute one hot component of Goal1. In the process, Goal1 is % transformed into Goal2, which is then simplified to Goal3. % As described above, C is a communication channel for handling % events, and Flag affects concurrency. oneStep(Flag,C,Goal1,Goal3) :- doOne(Flag,C,Goal1,Goal2), simplify(Goal2,Goal3). % ISOLATION: An isolated goal is a hot component; so, to execute one % step, the entire goal is executed, and the empty goal is returned. % % There are two modalities of isolation, isolate(G) and isolate1(G), % which affect the interleaving of concurrent processes in G. % isolate(G) causes all interleavings to be checked, while isolate1(G) % causes only one interleaving to be checked. doOne(Flag,C,isolate(G),state) :- !, execute(all,C,G). doOne(Flag,C,isolate1(G),state) :- !, execute(one,C,G). % SEQUENTIAL COMPOSITION: Execute one step of a sequential goal. The % value of Flag is irrelevant. doOne(Flag,C,seq([]),state) :- !. % Special case. Do nothing, but simplify the goal. doOne(Flag,C,seq([G1|Goals]),seq([G2|Goals])) :- !, oneStep(Flag,C,G1,G2). % DISJUNCTIVE GOALS: A disjunctive goal is a list of processes. To % execute the goal, we must execute one of its disjuncts, chosen % non-deterministically. The rules below first choose a disjunct, % then execute one step, and then return the rest. (More precisely, % the rules choose the first disjunct, and on backtracking, they % choose other disjuncts.) The value of Flag is irrelevant. doOne(Flag,C,or([]),G) :- !, fail. % No disjuncts. Fail. doOne(Flag,C,or([G1]),G2) :- !, oneStep(Flag,C,G1,G2). % Only 1 disjunct to choose from. doOne(Flag,C,or([G1|Goals]),G2) :- oneStep(Flag,C,G1,G2). % Many disjuncts: choose the first one. doOne(Flag,C,or([G1|Goals]),G2) :- !, doOne(Flag,C,or(Goals),G2). % Choose another one. % conc1 is a form of concurrent conjunction for transactions that % commute (ie, for transactions for which the order of execution does % not matter). In this case, the interpreter tries only one interleaving. % doOne(Flag,C,conc1(Goals1),conc1(Goals2)) :- !, doOne(one,C,conc(Goals1),conc(Goals2)). % CONCURRENT COMPOSITION: A concurrent goal is a list of processes. % To execute one step of the goal, we execute one step of some process % in the list. After execution, we rotate the list by 1 position, which % assures round-robin scheduling in the absense of backtracking. doOne(Flag,C,conc([]),state) :- !. % Special case. Do nothing, but simplify the goal. % If Flag=one, then we always choose the first process in the goal list. doOne(one,C,conc(Goals1),conc(Goals4)) :- !, [Ga|Goals2] = Goals1, % Extract the first process. oneStep(one,C,Ga,Gb), % Execute one step of the process. Goals3 = [Gb|Goals2], % Put first process back into the list. rotate1(Goals3,Goals4). % Rotate list by 1 position. % Rotate a list by 1 position. If the first list element is state, % then simply chop it off. rotate1([state|Goals],Goals) :- !. rotate1([G|Goals1],Goals2) :- !, append(Goals1,[G],Goals2). % If Flag=all, then on backtracking, we will eventually choose every % process in the goal list. (This guarantees that all interleavings of % the processes are eventually generated.) To choose a process, we % rotate the list by some amount, and select the first process in the % rotated list. More precisely, we initially rotate the list by 0 % positions; then, on backtracking, we rotate it by 1 position, 2 % positions, 3 positions, etc. In this way, every process is eventually % rotated to the front of the list. Moreover, in the absense of % backtracking, the first process in the list is always chosen. doOne(all,C,conc(Goals1),conc(Goals5)) :- !, rotate(Goals1,Goals2), % Rotate the list of processes. [Ga|Goals3] = Goals2, % Extract the first process. oneStep(all,C,Ga,Gb), % Execute one step of the process. Goals4 = [Gb|Goals3], % Put first process back into the list. rotate1(Goals4,Goals5). % Rotate list by 1 position. % Rotate list L1 by some amount, to give list L2. rotate(L1,L2) :- split(L1,L1a,L1b), not(L1b = []), append(L1b,L1a,L2). % Split list L into two sublists, L1 and L2. split(L,L1,L2) :- append(L1,L2,L). % THROWING AN EVENT: To throw event E on channel C, insert the atom % event(C,E) into the database. doOne(Flag,C,throw(E),state) :- ins(event(C,E)), !. % EVENT HANDING: When execution of the goal try(G,E,A) first begins, % create a new communication channel, C, and convert the goal to % try(C,G,E,A). All subsequent execution takes place on this expanded % goal. Any events that occur during the execution of G are thrown into % the new communication channel. doOne(Flag,C1,try(G1,E,Act),G2) :- !, newChannel(C2), doOne(Flag,C1,try(C2,G1,E,Act),G2). % If executing one step of goal G1 produces G2, then executing one % step of the larger goal try(C,G1,E,A) produces try(C,G2,E,A). If any % events took place during the execution of this step, then they must be % handled. This is done by transforming the latter goal into G3. doOne(Flag,C1,try(C2,G1,E,Act),G3) :- !, oneStep(Flag,C2,G1,G2), transform(C1,try(C2,G2,E,Act),G3). % No event occured on channel C2, so the goal, G, remains unchanged. transform(C1,G,G) :- G = try(C2,_,_,_), not event(C2,_), !. % An event is caught on channel C2 and handled, transforming the goal % from G1 to G2. The event is also deleted from the database. transform(C1,G1,G2) :- G1 = try(C2,_,E,Act), event(C2,E), !, del(event(C2,E)), response(E,Act,G1,G2). % To handle an exception, goal G is replaced by Act. ie, G is % terminated, and Act is executed. response(exception(_),Act,G,Act) :- !. % To handle an interupt, goal G is replaced by Act*G. ie, G is % suspended, Act is executed, and then G resumes. response(interupt(_),Act,G,seq([Act,G])) :- !. % Any other kind of event is an error. response(E,_,_,_) :- nl, write('Undefined event '), write(E), nl, !. % Some other event occurs, and is thrown up to the next level for % handling. This is done by changing the communication channel % associated with the event. The goal, G, is not changed. transform(C1,G,G) :- G = try(C2,_,_,_), !, event(C2,E), !, del(event(C2,E)), ins(event(C1,E)). % Communication channels are represented as natural numbers, and the % largest number used so far is stored in the base predicate % maxChannel(C). To create a new channel, C is incremented. newChannel(C2) :- maxChannel(C1), del(maxChannel(C1)), C2 is C1+1, ins(maxChannel(C2)). % TRANSACTION BASE: Search the transaction base for rules of the form % Head<-Body. If such a rule is found, then, to execute one step of % "Head", we execute one step of "Body". This transforms "Body" into % "Goal". Note that the CTR rule Head<-Body is implemented as the % Prolog rule trans(Head):-Body. The value of Flag is irrelevant. doOne(Flag,C,Head,Goal) :- clause(trans(Head),Body), oneStep(Flag,C,Body,Goal). % doOne(Flag,Head,Goal) :- clause(trans(Head),Body), !, fail. % STATE: An empty goal does nothing and always succeeds. % doOne(Flag,C,state,state) :- !. % PROLOG COMMANDS in CTR formulas: If the interpreter gets this far, % then assume that P is a Prolog command and execute it, leaving the % empty goal (state). doOne(Flag,C,P,state) :- !, P. % SIMPLIFICATION: Here are some basic rules for simplifying a goal % after a single step has been executed. Intuitively, simplify(G1,G2) % means that goal G2 is equivalent to but syntactically simpler than % goal G1. simplify(try(state,E,Act),state) :- !. simplify(try(C,state,E,Act),state) :- !. simplify(seq([]),state) :- !. simplify(seq([state]),state) :- !. simplify(seq([state|Goals]),seq(Goals)) :- !. simplify(conc([]),state) :- !. simplify(conc([state]),state) :- !. simplify(conc([state|Goals]),conc(Goals)) :- !. simplify(conc1([]),state) :- !. simplify(conc1([state]),state) :- !. simplify(conc1([state|Goals]),conc1(Goals)) :- !. simplify(G,G) :- !. % MONITORING EXECUTION: The command monitor(Task) helps a user to % monitor the execution of the various tasks that make up a CTR program. % It prints a message when a task is committed, and then prints another % message if the task is later rolled back and undone. Specifically, % when monitor(Task) is executed, it prints "committing Task" on the % screen. During backtracking, it prints "Undoing Task". monitor(Task) :- write('committing '), write(Task), nl, !, onBacktracking(Task). onBacktracking(Task). onBacktracking(Task) :- write('undoing '), write(Task), nl, !, fail.