Implementation notes Horizontal programming. ---------------------------------------------------------------------- 0. Concept Two straightforward goals: - Write a tool that concatenates files horizontally. - Write C code that still compiles when concatenated horizontally. The first goal was due to idle speculation: I see that most programs line-orientated, where programmers expand code by adding more lines, thus growing the text file vertically. I always wondered if this just because we don't have practical tools for programming horizontally. The simplest tool for manipulating text vertically is "cat", so I thought I would implement a horizontal cat tool. The second goal was due to IOCCC: I knew a "horizontal cat" tool wouldn't win anything. We will at least need some sample input that demonstrated horizontal programming techniques. If this experiment didn't coincide with IOCCC, I might have created a new language, perhaps something like Befunge. For IOCCC, it's only natural to try writing horizontal programs with C code. ---------------------------------------------------------------------- 1. "Parallel" programming Writing a tool that concatenate files horizontally is fairly easy. In Perl it would have been ~50 lines of code that probably takes most engineers no more than 10 minutes to write. In C it takes a bit longer due to manual memory management, but it's not particularly difficult. What's more difficult is writing horizontal concatenation code that concatenates horizontally. In a sense, we need new techniques to write multiple columns of code in parallel and see if they have the desired effect. Some patterns are immediately obvious: execute_twice(); execute_twice(); execute_once(); // execute_once(); // Note that single line comments is supported in C99 onwards. If we want to be C90 compliant, we will need something like this: execute_once(); /* execute_once(); /* /* ignored */ /* ignored */ Which works, but costs an extra line. Also, gcc will warn about enclosing "/*" inside comments by default. Block comment is a slight disappointment for horizontal programming, except this weird trick: *ptr=1; execute_once(); var=2/*ptr=1; execute_once(); var=2/ 2/**/; // 2/**/; // "var" has the value of 1 single column mode, or 2 in parallel mode. Best of all, it's not so obvious where the comment started in the first line if it was wide enough. This pattern seems tailor made for IOCCC. Besides using comments to avoid repeated expressions, it helps to have some idempotent operations. This is good: ptr = NULL; ptr = NULL; ptr = realloc(ptr, size); ptr = realloc(ptr, size); This wastes some memory, but still works: ptr = malloc(size); ptr = malloc(size); This is no good: free(ptr); free(ptr); Conditionals works magically, as long as the braces are carefully placed: if( condition() ) { if( condition() ) { twice(); twice(); } else { once(); } } else { once(); } x = 1; x = 1; if( x ) { once(); x = 0; } if( x ) { once(); x = 0; } Loops works better than expected. These both output "0 1 2 3": i = 0; i = 0; for(; i < 3; i++) { for(; i < 3; i++) { printf("%d\n", i); } printf("%d\n", i); } for(i = 0; i < 3; i++) { for(i = 0; i < 3; i++) { printf("%d\n", i); } printf("%d\n", i); } Some things might be unexpected. This outputs "0 1 2 4": for(i = 0; i < 3; i++) for(i = 0; i < 3; i++) { printf("%d\n", i); } { printf("%d\n", i); } Nested loops are even more amazing, let's just leave it at that. It gets unwieldy fairly quickly, especially if the lines are long. In the end, recognizing some patterns will help a bit in debugging, but the best technique is actually to just throw random code permutations at the compiler and hope for the best. This actually works surprisingly well in practice, horizontal programming or not. It helps to write good unittests beforehand (unobfuscated, of course). ---------------------------------------------------------------------- 2. Feature creep Having figured out how to write code that concatenates horizontally, the next question is what should be written. We could just make the same horizontal concatenation program idempotent when concatenated horizontally, but that would be rather boring. The most obvious thing to write is a vertical concatenation program. This is especially convenient since it's almost a strict subset of the existing code for horizontal concatenation. That was easy, but now we have replaced the problem with finding an interesting code that concatenates *vertically*. Since there are now two "cat" programs inside this code, I thought it has to be cat all the way, so I implemented the bits that outputted long cat when the original program is concatenated horizontally or vertically. I also generalized the implementation such that concatenating more programs vertically or horizontally results in a longer or wider long cat. This removes the need to think up more programs that resulted in additional file concatenation combinations. Having planned what the programs are, now would be a good time to decide what template to fit the code to. Also coincidentally, "Toaru Kagaku no Railgun" was running and had this really nice stackable figure of Misaka, and that became the template. Note that I had planned to write ASCII art since the very beginning, non-ASCII art was simply never considered. The rationale being that I will eventually publish the code regardless of what IOCCC judges think, and my site mostly hosts ASCII art code. Using the same technique as akari.c, I generated the largest template that would fit under IOCCC rules, then fit the code to it. And just like last time, there was a bit of slack left but not a whole lot, just enough for a brainfuck program. There are *still* space left after that, so I added the CRC32 of the source code as well. Despite the 4K size limit, I ended up with lots of extra minor features not part of the two original goals. That's how software engineering works sometimes. ---------------------------------------------------------------------- 3. The making Process of implementing the code was exactly what was described earlier: write good unittests, then throw random permutation of code to compiler until all test passes. It took a long but reasonably predictable amount of time, and I was able to finish the code with some margin before the IOCCC deadline. One key difference between professional code and recreational code is that people always ask me when something will be done for the former, and the same people ask me how long I took to do the latter. Some of my coworkers knew that I was participating in IOCCC and would regularly check on my progress, to which I would respond with something like "I finished 25 out of 45 lines!" I already knew how many lines the final finished code will occupy, filling in each line just takes some patience. Time to type up the entry (as seen in replay.html) was about 2.5 hours, but that doesn't include all the failed and reverted changes. Actual time taken was more like 40 hours spread over 3 weeks. ---------------------------------------------------------------------- 4. Finally... Misaka was a winning entry for IOCCC 2013. This made the few weeks spent on this entry totally worth it. It was almost as rewarding as watching Hyperdimension Neptunia all over again.