{
  "id": "enwiki-001374184925",
  "slug": "loop-programming-language",
  "title": "LOOP (programming language)",
  "qid": "",
  "lead": "LOOP is a simple register language designed to precisely capture the primitive recursive functions. The language is derived from the counter-machine model. Like the Counter machines the LOOP language comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer. A few arithmetic instructions operate on the registers: inc x (increment), dec x (decrement: \\operatorname{max}(0, x - 1) ), x = 0 (clear), and x = y (copy). The only control flow instruction is LOOP x: ... . It causes the instructions within its scope to be repeated x times. In contrast to GOTO programs and WHILE programs, LOOP programs always terminate. The running time is known in advance. Therefore, the set of functions computable by LOOP-programs is a proper subset of computable functions (and thus a subset of the computable by WHILE and GOTO program functions). The LOOP language admits several variants, distinguished by their set of basic instructions. Four such variants, L0 – L3, are distinguished in this article. Despite differences in syntactic convenience and loop-nesting depth, all variants compute exactly the primitive recursive functions. At shallow nesting depths, the choice of basic instructions affects which functions are reachable.…",
  "body": "LOOP is a simple register language designed to precisely capture the primitive recursive functions. The language is derived from the counter-machine model. Like the Counter machines the LOOP language comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer. A few arithmetic instructions operate on the registers: inc x (increment), dec x (decrement: \\operatorname{max}(0, x - 1) ), x = 0 (clear), and x = y (copy). The only control flow instruction is LOOP x: ... . It causes the instructions within its scope to be repeated x times. In contrast to GOTO programs and WHILE programs, LOOP programs always terminate. The running time is known in advance. Therefore, the set of functions computable by LOOP-programs is a proper subset of computable functions (and thus a subset of the computable by WHILE and GOTO program functions). The LOOP language admits several variants, distinguished by their set of basic instructions. Four such variants, L0 – L3, are distinguished in this article. Despite differences in syntactic convenience and loop-nesting depth, all variants compute exactly the primitive recursive functions. At shallow nesting depths, the choice of basic instructions affects which functions are reachable. The simple functions are exactly the functions computable at depth 1 in L1; the Presburger-definable functions are exactly the functions computable at depth 1 in L3; the Kalmár elementary functions are exactly the functions computable at depth 2 in L1, L2, and a fortiori L3. From depth 3 onward all variants agree. An example of a total computable function that is not LOOP-computable is the Ackermann function. P Q is in Li. 3. If , then LOOP x: P is in Li. Indentation determines block structure in a Python-like notation. For brevity, a short body may be written on the same line as its LOOP header, and consecutive instructions on one line are separated by semicolons. A LOOP program may be associated with a signature specifying input and output registers: signature ::= 'def' program_name '(' input ')' '->' '(' output ')' ':' input ::= [ register (',' register)* ] output ::= register (',' register)* Notes The signature is not part of the program. As and can be any lists of registers, in general P can compute several functions, depending on the chosen mapping. So, multiple signatures can be associated to one single LOOP program. In this presentation an intended signature is placed before the program. Registers range over \\mathbb{N} = \\{0, 1, 2, \\dots\\} . Execution proceeds sequentially. A loop of the form LOOP x: ... executes its body exactly x times, where x is the value of the register at loop entry. A LOOP program P is said to compute a function f \\colon \\mathbb{N}^m \\to \\mathbb{N}^n when: \\mathtt{input} , an m-tuple, specifies m registers which contain the arguments of f(x_1, \\dots, x_m) ; the remaining registers contain 0 ; \\mathtt{output} , an n-tuple, specifies n registers; after the execution of P the output registers contain (y_1, \\dots, y_n) = f(x_1, \\dots, x_m) . Note When \\mathtt{output} specifies a single register, P defines a scalar-valued function; otherwise, P defines a vector-valued function. Definition This definition agrees with the following: A (vector-valued) function f : \\mathbb{N}^m \\to \\mathbb{N}^n is primitive recursive if it can be written as f(x_1, \\dots, x_m) = (f_1(x_1, \\dots, x_m), \\dots, f_n(x_1, \\dots, x_m)) where each component f_i : \\mathbb{N}^m \\to \\mathbb{N} is a (scalar-valued) primitive recursive function. x = y is definable in L0 and in L2, dec x is definable in L0 and in L1. === Bootstrapping x = y === In L0 or L2 x = y can be implemented by the program def copy(y) -> (x): LOOP y: inc x We will write x = y in all languages, understanding that this instruction denotes x = copy(y) in L0 and in L2. Wherever x = y appears in L0 or in L2 code, one has to add 1 to the local loop depth. The overall nesting depths are \"\"\" Loop nesting: 1 (L0), 0 (L1) \"\"\" x \\mathbin{\\dot{-}} 1 = \\operatorname{max}(0, x - 1) = \\begin{cases} 0 & \\mbox{if }x=0 \\\\ x-1 & \\mbox{otherwise}\\end{cases} can be implemented by the programs We will write dec x in all languages, understanding that this instruction denotes dec_L0(x) in L0 and dec_L1(x) in L1. Wherever dec x appears in L0 or in L1 code, one has to add 2 respectively 1 to the local loop depth. The overall nesting depths are \"\"\" Loop nesting: 2 (L0), 1 (L1), 0 (L2) \"\"\" where an upward edge denotes that the upper variant has strictly more primitive instructions than the lower. L1 and L2 are incomparable: L1 has x = y but not dec x ; L2 has dec x but not x = y ; L3 has both; L0 has neither. For nesting depth k k (L1) and Loop k (L2) incomparable. The strict inclusions reflect the cost of simulating missing base instructions by extra loop nesting. At depth 2 the variants L1, L2 and L3 collapse; from depth 3 onward the choice of basic instructions ceases to matter and all four variants agree. In particular: At depth 1, Loop 1 (L1) = simple functions, Loop 1 (L3) = Presburger functions: At depth 2, Loop 2 (L1) = Loop 2 (L2) = Kalmár elementary functions: The example programs below track loop nesting depth explicitly for each variant. (y_1, \\ldots, y_n) = q(x_1, \\ldots, x_m) . Suppose m input registers of P supply the inputs x_1, \\ldots, x_m , and we wish to use Q as a subroutine inside P. Then the code of Q can be embedded (\"macro-expanded\") into P as follows: rename all registers of Q to avoid collisions with registers of P; initialize all registers of Q to 0 ; copy the input values x_1, \\ldots, x_m from P into the input registers of Q; execute the program Q; copy the output values y_1, \\ldots, y_n from the output registers of Q into the designated registers of P. This construction allows Q to be used as a subprogram of P, simulating an activation record in the sense required here. Notes In P only the output registers are updated. This macro expansion does not alter the LOOP language. The notation is meant to improve the readability of the software and to facilitate the separate discussion of the inserted code. goes further. His function calls enhance the language to augmented loop programs. Machtey allows calls to general recursive functions. By convention, \\left\\lfloor x / 0 \\right\\rfloor = 0 . \\left\\lfloor x / k \\right\\rfloor can be computed by the LOOP program def divk(x) -> (c1): \"\"\" Loop nesting: 2 (L0), 1 (L1), 2 (L2) \"\"\" LOOP x: c0 = c1 # add to loop depth: 1 (L0), - (L1), 1 (L2) c1 = c2 # add to loop depth: 1 (L0), - (L1), 1 (L2) ... # ... ... ck = c0 # add to loop depth: 1 (L0), - (L1), 1 (L2) inc ck def div4(x) -> (c1): \"\"\" Loop nesting: 2 (L0), 1 (L1), 2 (L2) \"\"\" LOOP x: c0 = c1 # add to loop depth: 1 (L0), - (L1), 1 (L2) c1 = c2 # add to loop depth: 1 (L0), - (L1), 1 (L2) c2 = c3 # add to loop depth: 1 (L0), - (L1), 1 (L2) c3 = c4 # add to loop depth: 1 (L0), - (L1), 1 (L2) c4 = c0 # add to loop depth: 1 (L0), - (L1), 1 (L2) inc c4 Note The variables c0 , c1 , ..., ck form a cyclic shift chain, rotated one link to the left each iteration; ck is then incremented. Every k iterations, the incremented value returns to c1 , so c1 counts complete groups of k iterations. By convention, x \\operatorname{mod} 0 = x . For k > 0 : \\begin{aligned} x \\operatorname{mod} k &= x \\mathbin{\\dot{-}} k \\left\\lfloor x / k \\right\\rfloor \\\\[2mm] &= \\begin{cases} x & \\text{if } x def modk(x) -> (r): \"\"\" Loop nesting: 2 (L0), 1 (L1) \"\"\" # Step 1: Initialize the state ring inc c0 # Step 2: Cycle the states x times LOOP x: # Shift the ring forward: # (c0, c1, c2, ..., c{k-1}) = (c{k-1}, c0, c1, ..., c{k-2}) t0 = c0 t1 = c1 # add to loop depth: 1 (L0), - (L1), 1 (L2) t2 = c2 ... t{k-1} = c{k-1} c0 = t{k-1} c1 = t0 # add to loop depth: 1 (L0), - (L1), 1 (L2) c2 = t1 ... c{k-1} = t{k-2} # Step 3: Extract the final answer. LOOP c1: r = 1 LOOP c2: r = 2 ... LOOP c{k-1}: r = {k-1} def mod5(x) -> (r): \"\"\" Loop nesting: 2 (L0), 1 (L1) \"\"\" # Step 1: Initialize the state ring for k=5 inc c0 # Step 2: Cycle the states x times LOOP x: # Shift the ring forward: # (c0, c1, c2, c3, c4) = (c4, c0, c1, c2, c3) t0 = c0 t1 = c1 # add to loop depth: 1 (L0), - (L1), 1 (L2) t2 = c2 t3 = c3 t4 = c4 c0 = t4 c1 = t0 # add to loop depth: 1 (L0), - (L1), 1 (L2) c2 = t1 c3 = t2 c4 = t3 # Step 3: Extract the final answer. LOOP c1: r = 1 LOOP c2: r = 2 LOOP c3: r = 3 LOOP c4: r = 4 x \\mathbin{\\dot{-}} y = \\operatorname{max}(0, x - y) = \\begin{cases} x - y & \\mbox{if } x \\ge y \\\\ 0 & \\mbox{if } x def monus(x, y) -> (x): \"\"\" Loop nesting: 3 (L0), 2 (L1), 1 (L2) \"\"\" LOOP y: dec x # add to loop depth: 2 (L0), 1 (L1) The expanded L1 code is listed by Meyer & Ritchie and by Matos: def monus(x, y) -> (x): LOOP y: a = 0 LOOP x: x = a inc a \\operatorname{w}(x, y)= \\begin{cases} x, & \\text{if } y = 0,\\\\ 0, & \\text{if } y \\neq 0. \\end{cases} def w(x, y) -> (x): \"\"\" Loop nesting: 1 (L0) \"\"\" LOOP y: x = 0 Kronecker delta The equality of two variables x and y is tested with the Kronecker delta \\delta_{xy} = \\begin{cases} 0 &\\text{if } x \\neq y \\\\ 1 &\\text{if } x=y \\end{cases} def eq(x, y) -> (result): \"\"\" Loop nesting: 3 (L0), 2 (L1), 1 (L2) \"\"\" inc result # assume equal test = monus(x, y) # loop depth: 3 (L0), 2 (L1), 1 (L2) LOOP test: result = 0 # x > y test = monus(y, x) # loop depth: 3 (L0), 2 (L1), 1 (L2) LOOP test: result = 0 # y > x If ... then ... else ... A conditional statement IF x = y THEN execute P1 ELSE execute P2 can be translated to test = eq(x, y) # add to loop depth: 3 (L0), 2 (L1), 1 (L2) LOOP test: P1 test = monus(1, test) # add to loop depth: 3 (L0), 2 (L1), 1 (L2) LOOP test: P2 Note The auxiliary register test must not appear in P1 or P2 . This is guaranteed in macro-expanded code by renaming registers to avoid collisions. By convention, x \\operatorname{mod} 0 = x . For y > 0 : \\begin{aligned} x \\operatorname{mod} y &= x \\mathbin{\\dot{-}} y \\left\\lfloor x / y \\right\\rfloor \\\\[2mm] &= \\begin{cases} x & \\text{if } x def mod(x, y) -> (r): \"\"\" Loop nesting: 3 (L0), 2 (L1), 2 (L2) Invariant: c = (y-1) - r \"\"\" LOOP y: inc ym1 # registers not listed as input hold 0 dec ym1 # ADD TO LOOP DEPTH: 2 (L0), 1 (L1) LOOP ym1: inc c # c = y-1 = initial countdown z0 = 1 LOOP y: z0 = 0 # z0 = 1 iff y = 0 LOOP x: nz = 0 p = 0 LOOP c: nz = 1; inc p # nz = sg(c), p = c dec p # p = c-1; ADD TO LOOP DEPTH: 2 (L0), 1 (L1) z = 1 LOOP nz: z = 0 # z = 1 iff c = 0 (wrap) t = 0 LOOP ym1: inc t LOOP nz: t = 0 # t = y-1 on wrap, else 0 c = 0 LOOP t: inc c # c ⇐ y-1 on wrap, LOOP p: inc c # c-1 otherwise LOOP z: r = 0 # wrap: reset r LOOP nz: inc r # step: increment r LOOP z0: # y = 0: r = x r = 0 LOOP x: inc r \\operatorname{exp}_2(x) = 2^x can be implemented by the LOOP 2 program def exp2(x) -> (y): \"\"\" Loop nesting: 2 (L0) \"\"\" inc y LOOP x: LOOP y: inc y Notes See also Meyer & Ritchie (1967a). \\operatorname{exp}_2 grows exponentially, yet is computable by a LOOP 2 program. def add(x, y) -> (x): \"\"\" Loop nesting: 1 (L0) \"\"\" LOOP y: inc x x \\cdot0 & = & 0 \\\\ x \\cdot ( y + 1 ) & = & (x \\cdot y) + x \\end{array} H_2(x, y) can be computed by the LOOP 2 program def mult(x, y) -> (z): \"\"\" Loop nesting: 2 (L0) \"\"\" LOOP y: z = add(z, x) x^0 & = & 1 \\\\ x^{y+1} & = & x^y \\cdot x \\end{array} H_3(x, y) can be computed by the LOOP 3 program def power(x, y) -> (z): \"\"\" Loop nesting: 3 (L0) \"\"\" inc z LOOP y: z = mult(z, x) This program expands to def power(x, y) -> (z): inc z LOOP y: temp = 0 LOOP x: LOOP z: inc temp z = temp Note Via superposition, the loop nesting of the exponentiation program reduces to 2 in L1 or L2, see below. \\operatorname{F}_{0}(n) & = & n+1 \\\\ \\operatorname{F}_{m+1}(n) & = & \\operatorname{F}_{m}^{n}(n) \\\\ \\end{array} where \\operatorname{F}_m^{n} is the n-th iterate of \\operatorname{F}_m . For fixed k , \\operatorname{F}_{k}(n) can be computed by the LOOP k program \"\"\" Loop nesting: k (L0) \"\"\" def F_k(n) -> (n): LOOP n: # loop depth: 1 LOOP n: # loop depth: 2 ... # ... LOOP n: # loop depth: k inc n # Note The diagonal function D(n) = \\operatorname{F}_n(n) grows faster than \\operatorname{F}_k for every fixed k , and is a version of the Ackermann function. It is not LOOP-computable: any LOOP program has a fixed, finite nesting depth k , so it can only compute functions dominated by \\operatorname{F}_k for that particular k . \\operatorname{w}(x, y) = \\begin{cases} x & \\text{if } y = 0 \\\\ 0 & \\text{if } y \\neq 0 \\end{cases} is the conditional selection function defined above. All five basis operations are computable in Loop 1 (L1): x + y : the addition; x \\mathbin{\\dot{-}} 1 : the predecessor program dec_L1 ; \\lfloor x/k \\rfloor : the rotating counter programs; x \\bmod k : the modulo-k programs; \\operatorname{w}(x, y) : the w program. Since all basis functions are Loop 1 (L1) computable, and superposition does not increase nesting depth, the simple functions are exactly the Loop 1 (L1) computable functions. Loop 1 (L1) \\subsetneq Loop 1 (L3) = Presburger Note that Loop 1 (L1) falls short: in L1 x \\mathbin{\\dot{-}} y requires depth 2; Loop 1 (L2) falls short: in L2 \\left\\lfloor x / k \\right\\rfloor requires depth 2. \\mathcal{E}^3 = \\langle \\, n + m, \\; n \\bmod m, \\; 2^n \\, \\rangle Since these functions are Loop 2 computable in L1 as well as in L2 check the examples above Kalmár elementary functions can be computed by (loop-free) concatenation of Loop 2 programs in L1 or L2. Furthermore: Loop 2 (L1) = Loop 2 (L2) = Loop 2 (L3) = Kalmár elementary functions. Example The identity x^y = 2^{(x y + x + 1) y} \\bmod ( 2^{x y + x + 1} \\mathbin{\\dot{-}} x ) allows x^y to be computed by superposition from the substitution basis \\langle \\, n + m, \\; n \\mathbin{\\dot{-}} m, \\; n m, \\; n \\bmod m, \\; 2^n \\, \\rangle ,{{refn|name=functions_added| derived n \\mathbin{\\dot{-}} m and n m from the basis \\langle n + m, \\; n \\bmod m, \\; 2^n \\rangle . These functions can be added to the basis to simplify the computation.}} yielding a Loop 2 program in L1 or L2: def power_by_superposition(x, y) -> (result): \"\"\" Loop nesting: 3 (L0), 2 (L1), 2 (L2) \"\"\" base = mult(x, y) # will become xy+x+1 base = add(base, x) base = add(base, 1) # base = xy+x+1 e = mult(base, y) # e = (xy+x+1)y dividend = exp2(e) divisor = exp2(base) divisor = monus(divisor, x) # loop depth: 3 (L0), 2 (L1), 1 (L2) result = mod(dividend, divisor) # loop depth: 3 (L0), 2 (L1), 2 (L2) Let H_k denote the k -th hyperoperation ( H_1 = addition, H_2 = multiplication, H_3 = exponentiation, H_4 = tetration, …). Prunescu, Sauras-Altuzarra and Shunia (2026) proved that the Kalmár elementary functions are generated by three functions: \\mathcal{E}^3 = \\langle \\, x \\bmod y,\\; x + y,\\; 2^x \\, \\rangle, simplifying the base \\langle x \\bmod y,\\; x + y,\\; x \\cdot y,\\; 2^x \\rangle of Mazzanti (2002) by showing multiplication to be redundant. Mazzanti's base theorem extends this to every level of the hierarchy: for n \\geq 3 , \\mathcal{E}^n = \\langle \\bmod,\\; H_1,\\; H_3,\\; \\ldots,\\; H_n \\rangle, and in the limit a base for all primitive recursive functions: \\mathbf{PR} = \\langle \\, \\bmod,\\; H_1,\\; H_3,\\; H_4,\\; H_5,\\; \\ldots \\, \\rangle. Multiplication H_2 appears at no level of the Mazzanti hierarchy. In particular, exponentiation H_3 is reachable at depth 2 directly from the basis \\langle x \\bmod y,\\; x + y,\\; 2^x \\rangle — not via repeated multiplication — through the identity x^y = 2^{(xy+x+1)y} \\bmod (2^{xy+x+1} \\mathbin{\\dot{-}} x) . The bases translate directly into LOOP nesting depths via the example programs above, since superposition corresponds to loop-free concatenation of programs. At the elementary level, \\mathcal{E}^3 = \\text{Loop}_2(\\mathbf{L1}) = \\text{Loop}_2(\\mathbf{L2}) (see above). From depth 3 onward the choice of variant is irrelevant, and for n \\geq 3 : \\text{Loop}_n(\\mathbf{L0}) = \\mathcal{E}^{n+1}, one new loop per level. In particular tetration H_4 requires nesting depth exactly 3.",
  "categories": [
    "23603337",
    "26220375",
    "26868936",
    "52022518",
    "63697623"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374184925",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789028539.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001374184925",
    "type": "webpage",
    "title": "LOOP (programming language)",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/loop-programming-language",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001374184925",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1374184925",
    "note": "Immutable snapshot enwiki-001374184925"
  }
}