/* Design Tool Studio Taught by Patrick Hebron How Low Can You Go?: The Turing Tarpit Conceptual Overview: http://esolangs.org/wiki/Turing_Tarpit "Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy." - Alan Perlis PLEASE NOTE: This example demonstates some dangerous techniques! In general, you should stay away from macros and goto statements. This code is meant as a conceptual exploration only. */ #include int main(int argc, const char * argv[]) { // Let's look at a tool that we might easily // take for granted, the while-loop: { // Initialize counter: int i = 0; // Initialize counter limit: int n = 5; // Peform loop: while( i < n ) { // Perform loop body: printf( "Version A: i = %i \n", i ); i++; } // Print newline: printf( "\n" ); } // If the C language didn't implement while-loops, // we could manually unroll the loop in the above // example to produce equivalent behavior // with something like: { // Perform loop body (sorta): printf( "Version B: i = %i \n", 0 ); printf( "Version B: i = %i \n", 1 ); printf( "Version B: i = %i \n", 2 ); printf( "Version B: i = %i \n", 3 ); printf( "Version B: i = %i \n", 4 ); // Print newline: printf( "\n" ); } // Obviously, this is a terrible solution. // It only solves the unique case in which // i = 0 and n = 5 and requires pointless // effort by the programmer. // Though the next solution isn't great, // it's at least slightly more generalized // than the previous: { // Initialize counter: int i = 0; // Initialize counter limit: int n = 5; // Check condition and perform loop body a set number of times: if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } if( i < n ) { printf( "Version C: i = %i \n", i ); i++; } // Print newline: printf( "\n" ); } // Using this approach, with i = 0, we could // set n to any value in the range [ 0 .. 10 ] and // get an output equivalent to the original while() example // From the previous example, it should be clear that a // while-loop is really just a repeated conditional expression. // We could simulate this by manually repeating the conditional. // Or... // By combining the conditional statement used above with two // other C language features - goto and labeled statements - // we can implement something very much like a while-loop: { // Initialize counter: int i = 0; // Initialize counter limit: int n = 5; // Insert a labeled statement: LOOP_LABEL: // Check condition: if( i < n ) { // Perform loop body: printf( "Version D: i = %i \n", i ); i++; // Goto labeled entry point: goto LOOP_LABEL; } // Print newline: printf( "\n" ); } // The thing we were missing before was a way to get back // to the top of our conditional statement. goto gives us that. // In this limited example, it's easy enough to keep track // of the program's behavior. But with nested loops or loops // than span much larger blocks of code, this approach // would become increasingly confusing. // See Edsget Dijkstra's "A Case against the GO TO Statement": // http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF // To improve on this situation, we might try to encapsulate // the ideas shown above into something a bit neater. // The problem is that we want to hardcode as little as possible // for each individual usecase but C/C++ does not allow us // to rewrite code at runtime. So, how could we generalize // our implementation such that it could take any valid // conditional statement and loop body? // One approach we might try is to use a preprocessor macro. // Macros allow the programmer to do something like code rewriting. // However, the "rewriting" happens at compile-time rather than run-time. // In this example, it almost seems like we've solved the problem // entirely. The syntax of our macro function is a little different // from the native C while-loop syntax, but it allows us to inject // any conditional expression and loop body: { // Define a macro to encapsulate goto approach: #define while_loop_attempt(CONDITION,BODY) \ WHILE_LABEL: \ if( CONDITION ) { \ BODY \ goto WHILE_LABEL; \ } \ // Initialize counter: int i = 0; // Initialize counter limit: int n = 5; // Call macro: while_loop_attempt( i < n, { // Perform loop body: printf( "Version E: i = %i \n", i ); i++; } ) // Print newline: printf( "\n" ); // Unfortunately, there's a problem. It's not reusable // because the labeled statement 'WHILE_LABEL' used // in the macro above has to be a unique point in the code. // So, if we tried to use the macro again: /* // Call macro again: int j = 0; while_loop_attempt( j < n, { // Perform loop body: printf( "Version E: j = %i \n", j ); j++; } ) */ // We would get a compiler error: // "Redefinition of label 'WHILE_LABEL'" } // We could go a little further down the macro rabbit hole // and generate a unique label statement for each each instance // of the while-loop in a way that will be largely invisible // to the user. { // Initialize counter: int i = 0; // Initialize counter limit: int n = 5; // Define a macro to format a unique label identifier: #define format_unique_label(IDX) \ UNIQUE_LABEL_##IDX \ // Define a macro to encapsulate goto approach: #define while_loop_impl(CONDITION,BODY,IDX) \ format_unique_label(IDX): \ if( CONDITION ) { \ BODY \ goto format_unique_label(IDX); \ } \ // Use the builtin counter macro to assign a unique ID // to each while-loop that's generated: #define while_loop(CONDITION,BODY) \ while_loop_impl(CONDITION,BODY,__COUNTER__) \ // Call macro: while_loop( i < n, { // Perform loop body: printf( "Version F: i = %i \n", i ); i++; } ) // Print newline: printf( "\n" ); // Call macro again: int j = 0; while_loop( j < n, { // Perform loop body: printf( "Version F: j = %i \n", j ); j++; } ) // Print newline: printf( "\n" ); } // This more or less implements the while-loop // in a flexible and user friendly syntax. // The macros that got us there aren't pretty // and we can't be certain that we've thought of // everything. For instance, what if the loop // body contained a break statement? // We could think about implementing while-loop // behavior in a variety of other ways. But, // in the end, perhaps we can just be glad // that the language we're using has already // implemented it succinctly. return 0; }