2 of 11
added 4726 characters in body
Martin Ender
  • 196.6k
  • 65
  • 444
  • 969

#2005 - Prelude

Prelude is a very fun language, whose source code consists of several "voices" which are executed in parallel and which I really enjoy solving problems in. It is meant to be the ASCII representation of its sister language Fugue, which actually takes .midi files as its source code and encodes the instructions found in Prelude as intervals in the melodies of the voices.

Prelude is fairly minimalistic, yet Turing complete (provided you are using at least 2 voices). As I said, the voices (lines of code) are executed simultaneously, column by column. Each voice operates on its own stack, which is initialised to an infinite number of zeroes. Prelude supports the following instructions:

0-9 ... Push the corresponding digit.
+   ... Add the top two numbers on the stack.
-   ... Subtract the top number from the one beneath.
#   ... Discard the top of the stack.
^   ... Copy the top value from the voice above.
v   ... Copy the top value from the voice below.
?   ... Read a number and push it onto the stack.
!   ... Print the top number (and pop it from the stack).
(   ... If the top of the stack is zero, jump past the matching ')'.
)   ... If the top of the stack is zero, jump to the column after the matching '('.

Some additional notes:

  • The voices are cyclic, so ^ on the top voice copies from the bottom voice (and vice versa).
  • Multiple ? and ! in the same column are executed top to bottom.
  • As per the language specification, ? and ! read and write characters with the corresponding character code. However, the Python interpreter also has a switch in its code to print the numbers themselves instead. For testing purposes I am actually using a modified version which can also read numbers instead of characters. But consensus around here is that numerical input/output can actually be given as byte values, hence these modifications are not necessary to make valid programs dealing with numbers.
  • Matching ( and ) do not need to be on the same voice. The voice used for the condition is always the one where the ( appears. Hence, the vertical position of the ) is completely irrelevant.
  • Due to the nature of Prelude's simultaneous execution, any instruction in the same column as a ( is executed only once before the loop starts, and regardless of whether the loop is entered. Similarly, any instruction in the same column as a ) is executed at the end of each iteration, regardless of whether the loop will be exited after this iteration.

I'll first show you the three programs without much commenting. You can find extensive explanations below.

The Programs

"Hello, World!" Variant

9(1-)v98+^++!9v+!  v88++2+!^  ! ^9-3-! v      !    v2-!55+!
8 8+ !     7v+! 1v+!88+^+!^4-!^ v8-^ !!!9v+  !^9+9+!  v5+!
     ^98++4+! ^8-! ^4-   ^ #!^6-!    ^^  #5+! v    ^2-!1+!

If you are using the Python interpreter, make sure that NUMERIC_OUTPUT = False.

ASCII Art N

      v2-(1-)v         
9(1-)?1-( v!  (1-55+!      0     (0)#  ))55+!
4-4+                  v^-#
     v!      v! v1-v!(1- ^(#^!0)# v! )v!
6 8+           v#

For ease of use, this program benefits from reading input as numbers, but output must not be numeric. So if you are using the modified Python interpreter, set

NUMERIC_INPUT = True
NUMERIC_OUTPUT = False

GCD

?(                         v)
? (^-(0 # v   #       ^+0)#^ !
     ^^ (##v^v+)#  0 (0 )   
      1) ^ #  - 1+(#)#

This is best used with all numeric input/output i.e.

NUMERIC_INPUT = True
NUMERIC_OUTPUT = True

Explanations

"Hello, World!" Variant

This is fairly straight-forward. I'm using 3 voices to successively generate the character codes for all the characters in Prelude was made in 2005!. I start by computing 8 + 9*8 = 80, which is the character code of P:

 9(1-)
 8 8+

After that I mostly just copy the previous character code and add or subtract the difference to the next one. Here is the code, but with each ! replaced with the character that is being printed (and _ for spaces and % for the digits):

9(1-)v98+^++r9v+u  v88++2+w^  _ ^9-3-a v      _    v2-%55+!
8 8+ P     7v+l 1v+e88+^+_^4-s^ v8-^ de_9v+  n^9+9+%  v5+%
     ^98++4+e ^8-d ^4-   ^ #a^6-m    ^^  #5+i v    ^2-%1+!

The final 55+! prints a trailing newline, just because it's nicer.

As a side note, the number of voices is pretty arbitrary for this task, but 3 is fairly convenient because it's the largest number in which every voice can directly access each other voice.

ASCII Art N

      v2-(1-)v         
9(1-)?1-( v!  (1-55+!      0     (0)#  ))55+!
4-4+                  v^-#
     v!      v! v1-v!(1- ^(#^!0)# v! )v!
6 8+           v#

With 5 voices, this is definitely one of the most complex programs I've written so far. The voices roughly have the following purposes:

  1. Merely a helper voice which stores N-1 for use in the inner loop.
  2. This is sort of the "main" voice, which reads input, contains an important switch and also contains the outer loop (i.e. the one over the rows).
  3. This stores a 32 to conveniently print spaces.
  4. This contains the inner loop (the one over the columns).
  5. This stores a 78 to conveniently print Ns.

Let's go through the code part by part. First, I'm creating the 32 as -4 + 9*4 and the 78 as 6 + 9*8:

9(1-)
4-4+

6 8+

Now I'm printing a single N (because we always need one) while reading the input N and storing N-1 and N-2 in the first two voices:

      v2-
     ?1-

     v!

Next, there is a "loop" conditioned on N-1. At the end of the loop, the second voice is always reduced to 0, and the loop exits after the first iteration. So essentially, this only if(N > 1){...}. After the loop we print a single trailing newline. To recap, we've now got the following framework:

      v2-
9(1-)?1-(                               )55+!
4-4+
     v!
6 8+

Inside this conditional, we first N-2 spaces and a single N to complete the first row, and we also store N-1 on the first voice for future use:

         (1-)v         
          v!  

             v!

Now the real meat of the code. First, there is an outer loop, which prints N-1 rows. For each row, we first print a newline, and an N. Then we loop N-2 times, printing either spaces or Ns (more on that later). And finally we print another N:

               1-55+!  

                v1-v!(               )v!
               v#

Finally, the fun part: printing each row (and getting the position of the N right). There is not really an if/else in Prelude, so I have to build it myself using two loops on different voices. The condition can easily be obtained by subtracting the inner and outer loop variable - we get 0 if we want to print N and something non-zero if we want to print a space.

The basic idea of an if/else in Prelude is to put a loop after the relevant value - the "if" (or non-zero) code, and exit it immediately by pushing a 0. On another voice, you keep a non-zero value, and another loop after the "if" loop. During the "if" loop you put a zero on top of that other voice, so as to prevent the "else" from being executed. There is some flexibility in whether you push zero values on top of non-zero values or simply discard the non-zero value if there's a zero beneath, but this is the general idea. You might also have to do some cleanup afterwards, if you want to keep using the relevant voice. This is what the code looks like:

                           0     (0)#
                      v^-#
                      1- ^(#^!0)# v! 

And that's it!

GCD

I will add an explanation for this one later.

Martin Ender
  • 196.6k
  • 65
  • 444
  • 969