CLooP

CLooP is a C-like language, inspired by Douglas Hofstadter's languages BLooP, FLooP and GLooP (used in his book Gödel, Escher, Bach). It was created in December 2008 by User:Alksentrs.

CLooP has three dialects, each with a different computational power, chosen by a pragma at the start of each program.

Lexical syntax

Very similar to Java or C.

Keywords:

break      goto
const      if
continue   infinity
else       int
for        pforeach
foreach    return
forever    with

Predeclared identifiers (note that * is not valid syntax):

true   false   io.*   conv.*

The sets of valid and reserved identifiers is the same as in C, but . is allowed in names as well.

The top level

At the beginning of the file, there is a dialect pragma. This is followed by a list of global variable declarations and function declarations.

Dialect pragma

One of:

• #bound n;    ("BLooP mode"; n is a positive integer)
• #no bound;   ("FLooP mode")
• #hyper;      ("GLooP mode")

These specify the computational power of the language (see below).

Global variables

Like in C/Java, you write the type of the new variable, followed by its name, then an optional initializer, then ;.

The valid types are:

• unbounded integer (int)
• immutable unbounded integer (const int)
• array of n elements of type T (T[n])

Because global variables and arrays are created and initialized at program startup, their initializers and array sizes (n in the above) must be constant expressions, and can use any expression whose value is known at compile-time.

Note: An array variable is a reference to some dynamically-allocated memory (the way Java does it). An array variable can refer to different arrays, which can be different sizes. The size of the array is stored with its data (in position −1, but you should use one of the # operators to access it). An array can be "infinite" in length; use infinity for its size. An implementation may manage this by extending (and maybe moving) the array as needed.

The comma can be used to combine several declarations into one, like in C.

Examples of global variable declarations:

int a;
int b = 5;
const int c = 4;
int[4] d;
int[c] e = { 2, 4, c };
const int f[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };    // you can put the [] after f
int[] g = { 3, -1 };         // size can be inferred
int h = 0xf;                 // hexadecimal
int i = 'A';                 // 'A' is a const int equal to 65
int j[] = "Hello, world\n";  // i.e. int[13] j = {72,101,108,108,111,44,32,119,111,114,108,100,10};
int k, l[3];                 // integer k, array of integers l
int[infinity] m;             // infinite array of integers
int[][5] n;                  // array of 5 arrays
int[][] p = { "-o", "myout", "-v" };     // array of arrays
int[] const [] q;            // mutable array of constant arrays of mutable integers

Functions

Again, like in C/Java:

return_type name_of_function( ) compound_statement
return_type name_of_function(arg1) compound_statement
return_type name_of_function(arg1, arg2) compound_statement
etc

Arguments are passed by value. (Arrays are effectively passed by reference, and can be modified by the function, if the element type isn't const.)

Examples:

void f1(int a1, int a2) { } // no-op function; 2 integer arguments

int f2() { return 3; }      // function that returns 3; no arguments

// return the n-th number in the Fibonacci sequence
int fib(int n) {
   int a = 0;
   int b = 1;
   if (n < 0) return -1;
   else for (n) {
      int c = a+b;
      a = b;
      b = c;
   }
   return a;
}

int sum(const int[] arr) {
  int s = 0;
  foreach (int i = 1 .. #arr)
     s += arr[i-1];
  return s;
}

Compound statements

A compound statement consists of a {, a list of statements and (local) declarations, and then a }.

A local declaration looks exactly the same as a global declaration, except it is lexically scoped to the block. A local variable has automatic storage [it is allocated/deallocated when program flow enters/leaves its scope].

The initializer of a local variable can be any expression (not necessarily const).

Statements

A statement looks like one of the following:

• compound_statement

Run the statements in the compound statement.

• ;

The empty statement: do nothing.

• label: statement

Provide a label to a statement. These are visible throughout a function body. If a loop is labelled, you can break/continue it from within nested loops.

• expression ;

Evaluate the expression, and ignore the result.

• return;
• return expression;

Exit a function, optionally providing a return value.

• break;
• break label;
• break keyword;

Prematurely end a loop. No argument: innermost loop; label argument: loop with that label; keyword argument: innermost loop using that keyword.

• continue;
• continue label;
• continue keyword;

Prematurely end a single iteration of a loop.

• goto label;

Jump to a label. You can only jump forwards, not backwards.

• for (expression) statement

Repeat the statement expression times. Negative values are not allowed.

• forever statement

Short for for (infinity).

• foreach (variable: expression .. expression) statement
• foreach (type variable: expression .. expression) statement

Repeat the statement for each value in the given range, assigning the variable the value each time. The second expression can be infinity, in which case the loop goes on forever, unless it is broken out of. If a type is given, the variable is declared, and is scoped to the loop body. In all cases, the variable is const inside the loop body.

• pforeach (variable: expression .. expression) statement
• pforeach (type variable: expression .. expression) statement

Same as above, but the statements can be executed in parallel (and so cannot depend on each other). continue will end the current thread; breaking from and returning from within a pforeach are undefined actions. infinity is only allowed sometimes (see below).

• if (expression) statement

If the expression is non-zero, do the statement. Otherwise do nothing.

• if (expression) statement else statement

If the expression is non-zero, do the first statement. Otherwise do the second.

• with identifier statement

Inside the statement, every variable starting with . has the identifier's name prefixed to it.

Example

a: for (2) {
   b: forever {
      c: foreach (int i = 0..1) {
         d: for (i) {
            break;           // break from 'd: for (i)' loop
            break d;         //  "
            break for;       //  "
            
            break c;         // break from 'c: foreach' loop
            break foreach;   //  "
            
            break b;         // break from 'b: forever' loop
            break forever;   //  "
            
            break a;         // break from 'a: for (2)' loop
         }
      }
   }
}

goto a;  // ** not allowed (backwards jump) **
goto e:  // OK

if (true)
   e: ;

Expressions

An expression can be one of:

• a numeric literal, in decimal
• a numeric literal, in hex (start it with 0x)
• a character literal, in single quotes (equal to the Unicode codepoint of the character)
• an array literal, a ,-separated list of expressions, in braces
• a string literal, a C string (which is an array of the codepoints of the characters)
• infinity
• true
• false
• the name of a variable
• an operator applied to some expression(s).

Most of the operators from C are available, along with a few extra ones (#, **, ^^, &&=, ^^= and ||=):

• increment and decrement (postfix and prefix ++ and --)
• number of elements in an array (prefix #)
• function call* (postfix ( ))
• array subscripting, from zero (postfix [ ])
• index of the last element of an array (postfix #)
• unary plus and minus (prefix + and -)
• bitwise and logical NOT (prefix ! and ~)
• raise to a power (infix **)
• multiply, divide and modulo (infix *, / and %)
• add and subtract (infix + and -)
• bitwise shift (infix << and >>)
• relations, returning 0/1 (infix <, >, <=, >=, == and !=)
• bitwise boolean (infix &, ^ and |)
• logical boolean (infix &&, ^^ and ||)
• ternary (? :)
• assignment (infix =, +=, -=, *=, /=, %=, <<=, >>=, &=, ^=, |=, &&=, ^^= and ||=)
• comma operator (infix ,)

* A function cannot call itself (directly or indirectly). The graph of function calls must be a finite tree, rooted at main.

True, false and infinity

The following is implicitly present in any program:

const int false = 0;
const int true = 1;

infinity is not an integer, but can be used in some places where integers are allowed. In array bounds, it means an auto-extending array of arbitrary length (applying # to such an array will give some unspecified value). In loop bounds, its meaning varies with the dialect pragma.

I/O, etc.

There are some pre-declared functions for I/O, etc:

with conv
{
      int .intFrom.str(const int[] str, int radix) {
         // Convert string to int
      }
      
      int .intFrom.decimal(const int[] str) {
         return .intFrom.str(str, 10);
      }
      
      int[] .strFrom.int(int val, int radix) {
         // Convert int to string
      }
      
      int[] .decimalFrom.int(int val) {
         return .strFrom.int(val, 10);
      }
}

with io.put
{
      void .char(int ch) {
         // implementation-specific, e.g.:
         __internal.stdout.putChar(ch);
      }
      
      void .nl() {
         .char('\n');
      }
      
      void .str(const int[] str) {
         foreach (int i = 0..str#)
            .char(str[i]);
      }
      
      void .strnl(const int[] str) {
         .str(str);
         .nl();
      }
      
      void .int(int num, int radix) {
         .str(conv.strFrom.int(num, radix));
      
      void .decimal(int num) {
         .str(conv.decimalFrom.int(num));
      }
}

const int io.eof = -1;

with io.get
{
      // returns io.eof to mean EOF
      int .char() {
         // implementation-specific, e.g.:
         return __internal.stdin.getChar();
      }
      
      int[] .str(int numChars) {
         int[numChars] str;
         foreach (int i = 0..str#) {
            int ch = .char();
            str[i] = ch;
            if (ch == io.eof) {
               str# = i;      // truncate array
               break;
            }
         }
         return str;
      }
      
      int[] .strnl(int numChars) {
         int[numChars] str;
         foreach (int i = 0..str#) {
            int ch = .char();
            str[i] = ch;
            if (ch == io.eof || ch == '\n') {
               str# = i;     // truncate array
               break;
            }
         }
         return str;
      }
      
      int .decimal(int numChars, int radix) {
         return conv.intFrom.str(.str(numChars), radix);
      }
      
      int .decimal(int numChars) {
         return conv.intFrom.decimal(.str(numChars));
      }
}

Entry point

int main(int[][] args)
{
   // etc.
}

Computational class

The computational power of this language varies with the dialect pragma.

#bound n;

In loop bounds, infinity means n, where n was the bound given in the dialect pragma. (In array bounds, it still means infinity.)

Every loop can take at most a finite number of iterations. Therefore, this dialect is not Turing-complete, and can only compute primitive recursive functions. However, if the bound is set to a high enough value (say 10¹⁰⁹, well into the Heat Death of our universe, if each iteration takes at least a billionth of a second), then any for (infinity) loop is practically infinite.

In fact, every halting program halts in some finite time, so there is a bound within which it will halt.

It is recommended that an implementation be able to accept insanely large loop bounds without crashing.

#no bound;

In loop bounds, infinity actually means infinity, so a forever loop actually loops forever. This dialect is Turing-complete. The pforeach loop does not allow infinity and so can only do a finite amount of work.

#hyper;

Same as #no bound;, but the pforeach loop does allow infinity and so can do an infinite amount of work in a finite time. This dialect is believed to be unimplementable on any normal computer.

Examples

Hello, world

#bound 1;

int main(int[][] args) {
   io.put.strnl("Hello, world");
   return 0;
}

Cat

#no bound;

int main(int[][] args) {
   forever {
      int ch = io.get.char();
      if (ch == io.eof) break;
      io.put.char(ch);
   }
}

External resources

• Wikipedia: Bloop and Floop
• Wikipedia: Primitive recursive function
• Wikipedia: Machine that always halts
• c2.com: Bloop, Floop and Gloop
• c2.com: Pimc (Parallel Infinite Mapcar), Pifl (Parallel Infinite Filter) and Pire (Parallel Infinite Reduce)