"When a Fuun has suffered a severe crash abnormal RNA may be produced. This 'hiccup' RNA is nothing to worry about and doesn't serve any purpose for morphing. It's not entirely clear what the real purpose of the RNA is, but it does seem to be related to the morphing process, because peculiar patterns have been observed. For example, the RNA code CFPICFP occurs very often and seems to indicate a small part of the morphing process is done. There are also other RNA codes, all starting with a C, that most likely indicate the start of a morphing process. Their exact meaning hasn't been figured out, though."

We log into ohmega's account and we find a specification, an interpreter, and a couple of problem statements for a perverse programming language called 2d, in which programs are drawn out as "ASCII art" flowcharts. Hilariously the specification explains, "This language frees the programmer from the shackles of linear programming by allowing programs to occupy two dimensions. However, unlike 3- and 4- dimensional languages like CUBOL and Hypercard, it does not distract the programmer's attention with needless dimensional abandon." The flowchart describes not just the data flow, but also the control flow of a program, because boxes aren't evaluated until all of their inputs have values.

The specification for 2d is available on Wikipedia.

I found it useful to first write my programs in Scheme, and then translate them into 2d. For example, here's a function that concatenates two lists, written first in Scheme and then in 2d:

(define (append listA listB)
  (if (empty? listA)
      listB
      (cons (car listA)
            (append (cdr listA) listB))))

The same program, implemented in 2d:

       ,..........................|........................................,
       :append                    |                                        :
       :                          v                                        :
       :                     *==================*                          :
       :                     !send [(N,S),(N,E)]!-----+                    :
       :                     *==================*     |                    :
       :                          |                   v                    :
       :   *=============*        |            *============*              :
       --->!case W of S,E!--------#----------->!send [(N,E)]!---------------
       :   *=============*        |            *============*              :
       :      |                   |                                        :
       :      v                   v                                        :        
       :   *=======*         *==========*                                  :
       :   !split N!-------->!use append!------------+                     :
       :   *=======*         *==========*            |                     :
       :      |                                      v                     :
       :      |                                *====================*      :
       :      +------------------------------->!send [(Inl (W,N),E)]!-------
       :                                       *====================*      :
       ,...................................................................,  

We received the Alien Codex, we implemented that civilization's Universal Machine. ( contains spoilers )

When describing my implementation of the Universal Machine virtual machine for the ICFP contest, I noted that it was disappointingly slow in running the benchmark. It turned out to be perfectly zippy enough to run the Codex with no noticable lag. However, it required a couple of times as much time to run the benchmark as some reported implementations, and a few optimizations were easy and obvious, so I implemented them. I also tried compiling my program with various flavors of compiler optimizations. The gcc compiler supports four levels of optimization, ranging from "-O0" (no optimization) to "-O3" (maximum strength). Moreover, the three versions of my program were:

1. A naïve implementation that did everything in the safest, easiest-to-debug, easiest-to-read, easiest-to-write way (or what seemed so at the time of writing). In particular, this involved calling a function every time the virtual machine wanted to allocate an array, and my program did bounds checking and all that.

2. In the next version, I took out all my array-handling functions. Instead of numbering arrays created in the virtual machine sequentially, I just handed back pointers to the virtual machine—conveniently the virtual machine operates on 32-bit values and pointers are 32 bits on my machine. In this version, it's possible for the program running in the VM to cause a segfault, but as long as the program running in the VM is well-behaved, it should run faster, since all function calls are eliminated.

3. For a third and further optimized version, I eliminated the switch statement in favor of a jump table with lots of duplicated code and gotos, which minimizes the number of jumps taking place. This was totally inspired by a thread in evan_tech's journal, since I didn't know about gcc's support for computed gotos.

The resulting code is about as optimized as I can imagine writing in C. (Though there's still a lot of bit-shifting that could be reduced.) There's really not too much in this program in the beginning to take out! ( To see the relative merit of these manual optimizations in conjunction with various levels of compiler optimization, I wrote a tiny shell script to compile and test each of the three versions of my program with each of the four levels of compiler optimization. The results are summarized in the table below. The numbers are the numbers of seconds required to execute the SANDmark benchmark, so lower numbers are better:

The results are an impressive victory for compiler optimizations. With -O3 there's virtually no difference between the "naïve implementation" and the most hand-optimized version.