///// // Musa Al-hassy // February 2017 // McMaster University ///// /* * This is header is for an embedded domain specific language: Dijkstra's guarded command language. * * In doubt, run * * gcc -E myfile.c * * to and look at the offending line to find out what's wrong! * * See here for a quick and accessible introduction to the C preprocessor: * http://www.cprogramming.com/tutorial/cpreprocessor.html * * The earlier version alhassy_gcl.h only provides notation, a syntax for GCL. * In contrast, this version not only provides an honest syntax but also a somewhat * honest semantics: guarded commands are evaluated non-deterministicly. * * Example usage: this little program sorts 3 integers and prints out the trace of how * it did its sorting. The trace output is non-deterministic :-) int a = 6, b = 4, c = 2; printf("a,b,c = %d, %d, %d\n", a, b,c); DO GUARD b < a HAS printf("We swap a(%d) and b(%d)\n", a, b); swap(a,b); GUARD c < b HAS printf("We swap b(%d) and c(%d)\n", b, c); swap(b, c); OD printf("Sorting by looping yields a,b,c = %d, %d,%d\n", a,b,c); * */ #include // to use exit(-) #include // to use time(-) #include // to use NULL typedef int bool; #define true 1 #define false 0 #define BEGIN { #define END } #define TERMINATOR ; /* How to pick a guard at random. * * Whenever a guarded command list is occurs, we keep track of a list of guards that * have been tried and failed. We then randomly choose one of the non-tried guards to * try. If all the guards have been tried, we return -1 and let the enclosing construct * handle it. In particular, an alternative (if..fi) construct will crash if all guards * have been tried and none succeeded; whereas, an iterative (do..od) construct will * do nothing if all guards fail. * */ /* returns a random integer `i : 0..N-1` such that `tried[i] != true` * returns -1 if all `tried[i] == true` */ int rndm(int N, bool tried[]) { // check if any are even false, otherwise we'll loop forever so instead return -1 bool all = true; for(int i = 0; i < N; i++) all = all && tried[i]; if(all) return -1; srand(time(NULL)); int pos = -1; PickI: pos = rand() % N; if(tried[pos]) goto PickI; return pos; } /* Anonymous functions from `Src` to `Tgt` can be made using the syntax: lambda( Tgt, Src, {...; return s;} ) * The implementation of `lambda` ensures that the braces `{` and `}`, and the final terminator `;` are * unnecessary ---this is handy for small functions that only return an expression. * * Along with the combinator below, we can write, for example * * int z = apply( lambda(int, (int x), printf("I add 7 to the arg! \n"); int y = x + y; return y) , 0 ); */ #define lambda(resType, args, body) ({ resType _ args { body ; } & _; }) /* Apply function pointer `f` to argument `x`. * * If `f` takes no arguments, then `apply(f,())` works, which will not if we had written `(*f)(x)` * in the implementation. */ #define apply(f,x) (*f)x /* GCL notation is implemented by realising each guarded command as a ``function pointer'' that returns a Boolean * indicating whether the guard is true or false. * * As mentioned earlier, when an alternative/iterative construct begins we actually keep track of which guards have been * tried, initally all false since none tried, then as the guarded commands are written, we surround with them with the * necessary syntax so that they are function pointers behind the scenes. Afterwards, the closing pieces of the alternative/iterative * construct randomly selects one of the guarded commands to try and applies the corresponding code. * * In the alternative case, if all guarded commands have been tried and so are false, then the system crashes, `exit(-1)`, * as per the GCL definition. In the iterative case, when all the guarded commands fail, it does nothing. * * For a uniform syntax, both constructs begin with an implicitly false guard, which is marked as ``already tried''. * * Finally, both constructs begin with a `BEGIN` and end with an `END`, that is are blocks. * This way, their variables have limited scope and do not pollute the namespace; more importantly, * doing so ensures there's no name-clashes when multiples instances of a construct occur in sequence. */ #define IF \ BEGIN \ bool __tried[100] = {0}; __tried[0] = true; \ bool (*__codes[])(void) = { ({ bool _ (void) { if(false){ return false; \ // Do the necessary plumbing needed to close a previous guarded-command arm #define _CLOSE ; return true;} else{return false;} ; } & _; }) #define GUARD _CLOSE , ({ bool _ (void) { if( #define HAS ){ /* We close the most-recent arm, pick a guard to perform and crash if none are valid, * then we end the scope of the alternative construct. */ #define FI \ _CLOSE}; \ int __len = sizeof __codes / sizeof *__codes; \ while(true){ \ int __pos = rndm(__len, __tried); \ if(__pos == -1) exit(-1); \ bool __success = apply(__codes[__pos], ()); \ if(!__success){ __tried[__pos] = true; } else break; \ } \ END // Notice that this `END` aligns with the `BEGIN` above in the definition of `IF`. /* * Likewise for the iterative constructs, but we skip if no guard succeeds. */ #define DO \ BEGIN \ bool __done = false; while(!__done) { IF #define OD \ _CLOSE}; \ int __len = sizeof __codes / sizeof *__codes; \ while(true){ \ int __pos = rndm(__len, __tried); \ if(__pos == -1){ __done = true; break;} \ bool __success = apply(__codes[__pos], ()); \ if(!__success){ __tried[__pos] = true; } else break; \ } \ }}END // end the IF, end the while-loop, end the block defining `done` et al. /// ///////////////// Other GCL like tidbits ///////////////////////////////////////// /// // type agnostic swap operation #define swap(x, y) { typeof(x) temp = x; x = y; y = temp; } // parallel assignemnt: x,y := exp1, exp2 #define becomes(x, y , exp1, exp2) { typeof(x) temp1 = exp1; typeof(y) temp2 = exp2; x = temp1; y = temp2; } // // consequently, swap(x,y) == becomes(x,y , y,x) #define donothing ; #define SKIP ;