LOOP (programming language)

<h2 id="history">History</h2>
<p>The LOOP language was formulated in a 1967 paper by <a href="/facts/Albert_R._Meyer/31B10sEp">Albert R. Meyer</a> and <a href="/facts/Dennis_M._Ritchie/I1yu1UWU">Dennis M. Ritchie</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
They showed the correspondence between the LOOP language and <a href="/facts/Primitive_recursive_function/4z97gRnl">primitive recursive functions</a>.
</p><p>The language also was the topic of the unpublished PhD thesis of Ritchie.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p><p>It was also presented by <a href="/facts/Uwe_Sch%25C3%25B6ning/7lr9al3u">Uwe Schöning</a>, along with <a href="/facts/Goto/V3bV9yVn">GOTO</a> and <a href="/facts/While_loop/hLrKdAFo">WHILE</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h2 id="design-philosophy-and-features">Design philosophy and features</h2>
<p>In contrast to <a href="/facts/Goto/V3bV9yVn">GOTO</a> programs and <a href="/facts/While_loop/hLrKdAFo">WHILE</a> programs, LOOP programs always <a href="/facts/Terminating_computation/RmN14Gft">terminate</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> Therefore, the set of functions computable by LOOP-programs is a proper subset of <a href="/facts/Computable_function/dzwBlLGn">computable functions</a> (and thus a subset of the computable by WHILE and GOTO program functions).<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p><p><a href="/facts/Albert_R._Meyer/31B10sEp">Meyer</a> & <a href="/facts/Dennis_M._Ritchie/I1yu1UWU">Ritchie</a> proved that each <a href="/facts/Primitive_recursive_function/4z97gRnl">primitive recursive function</a> is LOOP-computable and vice versa.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a>
</p><p>An example of a total computable function that is not LOOP computable is the <a href="/facts/Ackermann_function/WQNpCWHn">Ackermann function</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a>
</p>
<h2 id="formal-definition">Formal definition</h2>
<h3>Syntax</h3>
<p>LOOP-programs consist of the symbols LOOP, DO, END, :=, + and ; as well as any number of variables and constants. LOOP-programs have the following <a href="/facts/Syntax/6PxSV98p">syntax</a> in modified <a href="/facts/Backus%25E2%2580%2593Naur_form/xbMXDntc">Backus–Naur form</a>:
</p>

P
              
              
                ::=
              
              
                
                  x
                  
                    i
                  
                
                :=
                0
              
            
            
              
              
                
                  |
                
              
              
                
                  x
                  
                    i
                  
                
                :=
                
                  x
                  
                    i
                  
                
                +
                1
              
            
            
              
              
                
                  |
                
              
              
                P
                ;
                P
              
            
            
              
              
                
                  |
                
              
              
                
                  
                    L
                    O
                    O
                    P
                  
                
                
                
                  x
                  
                    i
                  
                
                
                
                  
                    D
                    O
                  
                
                
                P
                
                
                  
                    E
                    N
                    D
                  
                
              
            
          
        
      
    
    {\displaystyle {\begin{array}{lrl}P&::=&x_{i}:=0\\&|&x_{i}:=x_{i}+1\\&|&P;P\\&|&{\mathtt {LOOP}}\,x_{i}\,{\mathtt {DO}}\,P\,{\mathtt {END}}\end{array}}}

<p>Here, 
  
    
      
        V
        a
        r
        :=
        {
        
          x
          
            0
          
        
        ,
        
          x
          
            1
          
        
        ,
        .
        .
        .
        }
      
    
    {\displaystyle Var:=\{x_{0},x_{1},...\}}
  
 are variable names and 
  
    
      
        c
        ∈
        
          N
        
      
    
    {\displaystyle c\in \mathbb {N} }
  
 are constants.
</p>
<h3>Semantics</h3>
<p>If P is a LOOP program, P is equivalent to a function 
  
    
      
        f
        :
        
          
            N
          
          
            k
          
        
        →
        
          N
        
      
    
    {\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }
  
. The variables 
  
    
      
        
          x
          
            1
          
        
      
    
    {\displaystyle x_{1}}
  
 through 
  
    
      
        
          x
          
            k
          
        
      
    
    {\displaystyle x_{k}}
  
 in a LOOP program correspond to the arguments of the function 
  
    
      
        f
      
    
    {\displaystyle f}
  
, and are initialized before program execution with the appropriate values. All other variables are given the initial value zero. The variable 
  
    
      
        
          x
          
            0
          
        
      
    
    {\displaystyle x_{0}}
  
 corresponds to the value that 
  
    
      
        f
      
    
    {\displaystyle f}
  
 takes when given the argument values from 
  
    
      
        
          x
          
            1
          
        
      
    
    {\displaystyle x_{1}}
  
 through 
  
    
      
        
          x
          
            k
          
        
      
    
    {\displaystyle x_{k}}
  
.
</p><p>A statement of the form
</p>
xi := 0

<p>means the value of the variable 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
  
 is set to 0.
</p><p>A statement of the form
</p>
xi := xi + 1

<p>means the value of the variable 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
  
 is incremented by 1.
</p><p>A statement of the form
</p>
<i>P</i>1; <i>P</i>2

<p>represents the sequential execution of sub-programs 
  
    
      
        
          P
          
            1
          
        
      
    
    {\displaystyle P_{1}}
  
 and 
  
    
      
        
          P
          
            2
          
        
      
    
    {\displaystyle P_{2}}
  
, in that order.
</p><p>A statement of the form
</p>
LOOP x DO <i>P</i> END

<p>means the repeated execution of the partial program 
  
    
      
        P
      
    
    {\displaystyle P}
  
 a total of 
  
    
      
        x
      
    
    {\displaystyle x}
  
 times, where the value that 
  
    
      
        x
      
    
    {\displaystyle x}
  
 has at the beginning of the execution of the statement is used. Even if 
  
    
      
        P
      
    
    {\displaystyle P}
  
 changes the value of 
  
    
      
        x
      
    
    {\displaystyle x}
  
, it won't affect how many times 
  
    
      
        P
      
    
    {\displaystyle P}
  
 is executed in the loop. If 
  
    
      
        x
      
    
    {\displaystyle x}
  
 has the value zero, then 
  
    
      
        P
      
    
    {\displaystyle P}
  
 is not executed inside the LOOP statement. This allows for <a href="/facts/Conditional_(programming)/8gDQTqUD">branches</a> in LOOP programs, where the conditional execution of a partial program depends on whether a variable has value zero or one.
</p>
<h3>Creating "convenience instructions"</h3>
<p>From the base syntax one create "convenience instructions". These will not be subroutines in the conventional sense but rather LOOP programs created from the base syntax and given a mnemonic. In a formal sense, to use these programs one needs to either (i) "expand" them into the code  – they will require the use of temporary or "auxiliary" variables so this must be taken into account, or (ii) design the syntax with the instructions 'built in'.
</p>
Example
<p>The k-ary projection function 
  
    
      
        
          U
          
            i
          
          
            k
          
        
        (
        
          x
          
            1
          
        
        ,
        .
        .
        .
        ,
        
          x
          
            i
          
        
        ,
        .
        .
        .
        ,
        
          x
          
            k
          
        
        )
        =
        
          x
          
            i
          
        
      
    
    {\displaystyle U_{i}^{k}(x_{1},...,x_{i},...,x_{k})=x_{i}}
  
 extracts the i-th coordinate from an ordered k-tuple.
</p><p>In their seminal paper <a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> Meyer & Ritchie made the assignment 
  
    
      
        
          x
          
            j
          
        
        :=
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{j}:=x_{i}}
  
 a basic statement.
As the example shows the assignment can be derived from the list of basic statements.
</p><p>To create the 
  
    
      
        assign
      
    
    {\displaystyle \operatorname {assign} }
  
 instruction use the block of code below.

x
          
            j
          
        
        :=
        assign
        ⁡
        (
        
          x
          
            i
          
        
        )
      
    
    {\displaystyle x_{j}:=\operatorname {assign} (x_{i})}
  
 =equiv
</p>
xj := 0;
LOOP xi DO
  xj := xj + 1
END

<p>Again, all of this is for convenience only; none of this increases the model's intrinsic power.
</p>
<h2 id="example-programs">Example Programs</h2>
<h3>Addition</h3>
<p><a href="/facts/Peano_axioms/DhhDnNug">Addition</a> is <a href="/facts/Recursion/CxSKxJoW">recursively</a> defined as:
</p>

a
                +
                0
              
              
                
                =
                a
                ,
              
              
                
                  
                    (1)
                  
                
              
            
            
              
                a
                +
                S
                (
                b
                )
              
              
                
                =
                S
                (
                a
                +
                b
                )
                .
              
              
                
                  
                    (2)
                  
                
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}a+0&=a,&{\textrm {(1)}}\\a+S(b)&=S(a+b).&{\textrm {(2)}}\end{aligned}}}

<p>Here, S should be read as "successor".
</p><p>In the <a href="/facts/Hyperoperation/XNn1hneN">hyperoperater sequence</a> it is the function 
  
    
      
        
          
            H
            
              1
            
          
        
      
    
    {\displaystyle \operatorname {H_{1}} }

</p><p>
  
    
      
        
          
            H
            
              1
            
          
        
        ⁡
        (
        
          x
          
            1
          
        
        ,
        
          x
          
            2
          
        
        )
      
    
    {\displaystyle \operatorname {H_{1}} (x_{1},x_{2})}
  
 can be implemented by the LOOP program ADD( x1, x2)
</p>
LOOP x1 DO
  x0 := x0 + 1
END;
LOOP x2 DO
  x0 := x0 + 1
END

<h3>Multiplication</h3>
<p><a href="/facts/Multiplication/VtcUjpNv">Multiplication</a> is the <a href="/facts/Hyperoperation/XNn1hneN">hyperoperation function</a> 
  
    
      
        
          
            H
            
              2
            
          
        
      
    
    {\displaystyle \operatorname {H_{2}} }

</p><p>
  
    
      
        
          
            H
            
              2
            
          
        
        ⁡
        (
        
          x
          
            1
          
        
        ,
        
          x
          
            2
          
        
        )
      
    
    {\displaystyle \operatorname {H_{2}} (x_{1},x_{2})}
  
 can be implemented by the LOOP program MULT( x1, x2 )
</p>
x0 := 0;
LOOP x2 DO
  x0 := ADD( x1, x0)
END

<p>The program uses the ADD() program as a "convenience instruction". Expanded, the MULT program is a LOOP-program with two nested LOOP instructions. ADD counts for one.
</p>
<h3>More hyperoperators</h3>
<p>Given a LOOP program for a <a href="/facts/Hyperoperation/XNn1hneN">hyperoperation function</a> 
  
    
      
        
          
            H
            
              i
            
          
        
      
    
    {\displaystyle \operatorname {H_{i}} }
  
, one can construct a LOOP program for the next level
</p><p>
  
    
      
        
          
            H
            
              3
            
          
        
        ⁡
        (
        
          x
          
            1
          
        
        ,
        
          x
          
            2
          
        
        )
      
    
    {\displaystyle \operatorname {H_{3}} (x_{1},x_{2})}
  
 for instance (which stands for <a href="/facts/Exponentiation/pac6QY2g">exponentiation</a>) can be implemented by the LOOP program POWER( x1, x2 )
</p>
x0 := 1;
LOOP x2 DO
  x0 := MULT( x1, x0 )
END

<p>The exponentiation program, expanded, has three nested LOOP instructions.
</p>
<ol><li></li></ol>
<h3>Predecessor</h3>
<p>The predecessor function is defined as
</p>

pred
        ⁡
        (
        n
        )
        =
        
          
            {
            
              
                
                  0
                
                
                  
                    
                      if 
                    
                  
                  n
                  =
                  0
                  ,
                
              
              
                
                  n
                  −
                  1
                
                
                  
                    
                      otherwise
                    
                  
                
              
            
            
          
        
      
    
    {\displaystyle \operatorname {pred} (n)={\begin{cases}0&{\mbox{if }}n=0,\\n-1&{\mbox{otherwise}}\end{cases}}}
  
.
<p>This function can be computed by the following LOOP program, which sets the variable 
  
    
      
        
          x
          
            0
          
        
      
    
    {\displaystyle x_{0}}
  
 to 
  
    
      
        p
        r
        e
        d
        (
        
          x
          
            1
          
        
        )
      
    
    {\displaystyle pred(x_{1})}
  
.
</p>
<i>/* precondition: x2 = 0 */</i>
LOOP x1 DO
  x0 := x2;
  x2 := x2 + 1
END

<p>Expanded, this is the program
</p>
<i>/* precondition: x2 = 0 */</i>
LOOP x1 DO
  x0 := 0;
  LOOP x2 DO
    x0 := x0 + 1
  END;
  x2 := x2 + 1
END

<p>This program can be used as a subroutine in other LOOP programs. The LOOP syntax can be extended with the following statement, equivalent to calling the above as a subroutine:
</p>
x0 := x1 ∸ 1

<p><i>Remark: Again one has to mind the side effects. The predecessor program changes the variable x2, which might be in use elsewhere. To expand the statement x0 := x1 ∸ 1, one could initialize the variables xn, xn+1 and xn+2 (for a big enough n) to 0, x1 and 0 respectively, run the code on these variables and copy the result (xn) to x0. A compiler can do this.</i>
</p>
<ol><li></li></ol>
<h3>Cut-off subtraction</h3>
<p>If in the 'addition' program above the second loop decrements x0 instead of incrementing, the program computes the difference (cut off at 0) of the variables 
  
    
      
        
          x
          
            1
          
        
      
    
    {\displaystyle x_{1}}
  
 and 
  
    
      
        
          x
          
            2
          
        
      
    
    {\displaystyle x_{2}}
  
.
</p>
x0 := x1
LOOP x2 DO
  x0 := x0 ∸ 1
END

<p>Like before we can extend the LOOP syntax with the statement:
</p>
x0 := x1 ∸ x2

<ol><li></li></ol>
<h3>If then else</h3>
<p>An if-then-else statement with if x1 > x2 then P1 else P2:
</p>
xn1 := x1 ∸ x2;
xn2 := 0;
xn3 := 1;
LOOP xn1 DO
  xn2 := 1;
  xn3 := 0
END;
LOOP xn2 DO
  P1
END;
LOOP xn3 DO
  P2
END;

<ol><li></li></ol>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/%25CE%259C-recursive_function/pQezUupS">μ-recursive function</a></li>
<li><a href="/facts/Primitive_recursive_function/4z97gRnl">Primitive recursive function</a></li>
<li><a href="/facts/BlooP_and_FlooP/6AxfmUhE">BlooP and FlooP</a></li></ul>
<h2 id="notes-and-references">Notes and references</h2>

<h2 id="bibliography">Bibliography</h2>

<ul><li>Axt, Paul (1966). "Iteration of relative primitive recursion". <i><a href="/facts/Mathematische_Annalen/GPhGaonc">Mathematische Annalen</a></i>. 167: 53–55. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01361215">10.1007/BF01361215</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:119730846">119730846</a>.</li>
<li>Axt, Paul (1970). <a href="https://projecteuclid.org/euclid.jsl/1183737320">"Iteration of primitive recursion"</a>. <i><a href="/facts/Journal_of_Symbolic_Logic/lfXVXcoy">Journal of Symbolic Logic</a></i>. 35 (3): 253–255. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fmalq.19650110310">10.1002/malq.19650110310</a>.</li>
<li>Brock, David C. (19 June 2020). <a href="https://computerhistory.org/blog/discovering-dennis-ritchies-lost-dissertation/">"Discovering Dennis Ritchie's Lost Dissertation"</a>. <i>CHM</i>. Retrieved 14 July 2020.</li>
<li>Calude, Cristian (1988). <i>Theories of Computational Complexity</i>. Annals of Discrete Mathematics. Vol. 35. <a href="/facts/North_Holland_Publishing_Company/jkPSAEmR">North Holland Publishing Company</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780080867755.</li>
<li>Cherniavsky, John Charles (1976). "Simple Programs Realize Exactly Presburger Formulas". <i><a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a></i>. 5 (4): 666–677. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0205045">10.1137/0205045</a>.</li>
<li>Cherniavsky, John Charles; Kamin, Samuel Noah (1979). <a href="https://doi.org/10.1145%2F322108.322120">"A Complete and Consistent Hoare Axiomatics for a Simple Programming Language"</a>. <i><a href="/facts/Association_for_Computing_Machinery/abI2atlP">Association for Computing Machinery</a></i>. 26 (1): 119–128. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F322108.322120">10.1145/322108.322120</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:13062959">13062959</a>.</li>
<li>Constable, Robert L.; Borodin, Allan B (1972). <a href="https://doi.org/10.1145%2F321707.321721">"Subrecursive programming languages, part I: Efficiency and program structure"</a>. <i><a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a></i>. 19 (3): 526–568. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321707.321721">10.1145/321707.321721</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:42474303">42474303</a>.</li>
<li>Crolard, Tristan; Lacas, Samuel; Valarcher, Pierre (2006). <a href="https://www.researchgate.net/publication/220673166">"On the expressive power of the loop language"</a>. <i>Nordic Journal of Computing</i>. 13: 46–57.</li>
<li>Crolard, Tristan; Polonowski, Emmanuel; Valarcher, Pierre (2009). <a href="https://hal.archives-ouvertes.fr/hal-00422158/file/LoopW.pdf">"Extending the loop language with higher-order procedural variables"</a> (PDF). <i><a href="/facts/ACM_Transactions_on_Computational_Logic/A5sM6JrI">ACM Transactions on Computational Logic</a></i>. 10 (4): 1–37. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1555746.1555750">10.1145/1555746.1555750</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1367078">1367078</a>.</li>
<li>Enderton, Herbert (2012). <i>Computability Theory</i>. Academic Press. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1555746.1555750">10.1145/1555746.1555750</a>.</li>
<li>Fachini, Emanuela; Maggiolo-Schettini, Andrea (1979). <a href="https://doi.org/10.1051%2Fita%2F1979130100491">"A hierarchy of primitive recursive sequence functions"</a>. <i>R.A.I.R.O. - Informatique Théorique - Theoretical Informatics</i>. 13 (1): 49–67. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1051%2Fita%2F1979130100491">10.1051/ita/1979130100491</a>.</li>
<li>Fachini, Emanuela; Maggiolo-Schettini, Andrea (1982). "Comparing Hierarchies of Primitive Recursive Sequence Functions". <i>Zeitschrift für mathematische Logik und Grundlagen der Mathematik</i>. 28 (27–32): 431–445. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fmalq.19820282705">10.1002/malq.19820282705</a>.</li>
<li>Goetze, Bernhard; Nehrlich, Werner (1980). <a href="https://doi.org/10.1002%2Fmalq.19800261407">"The Structure of Loop Programs and Subrecursive Hierarchies"</a>. <i>Zeitschrift für mathematische Logik und Grundlagen der Mathematik</i>. 26 (14–18): 255–278. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fmalq.19800261407">10.1002/malq.19800261407</a>.</li>
<li>Ibarra, Oscar H.; Leininger, Brian S. (1981). "Characterizations of Presburger Functions". <i><a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a></i>. 10 (1): 22–39. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0210003">10.1137/0210003</a>.</li>
<li>Ibarra, Oscar H.; Rosier, Louis E. (1983). <a href="https://doi.org/10.1016%2F0304-3975%2883%2990085-3">"Simple Programming Languages and Restricted Classes of Turing Machines"</a>. <i><a href="/facts/Theoretical_Computer_Science/jSkGGuvy">Theoretical Computer Science</a></i>. 26 (1–2): 197–220. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0304-3975%2883%2990085-3">10.1016/0304-3975(83)90085-3</a>.</li>
<li>Kfoury, A.J.; Moll, Robert N.; Arbib, Michael A. (1982). <i>A Programming Approach to Computability</i>. Springer, New York, NY. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-1-4612-5749-3">10.1007/978-1-4612-5749-3</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-4612-5751-6.</li>
<li>Machtey, Michael (1972). <a href="https://doi.org/10.1016%2FS0022-0000%2872%2980032-1">"Augmented loop languages and classes of computable functions"</a>. <i><a href="/facts/Journal_of_Computer_and_System_Sciences/cNek9ego">Journal of Computer and System Sciences</a></i>. 6 (6): 603–624. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0022-0000%2872%2980032-1">10.1016/S0022-0000(72)80032-1</a>.</li>
<li>PlanetMath. <a href="https://planetmath.org/primitiverecursivevectorvaluedfunction">"primitive recursive vector-valued function"</a>. Retrieved 21 August 2021.</li>
<li>Matos, Armando B. (3 November 2014). <a href="https://www.dcc.fc.up.pt/~acm/loops.pdf">"Closed form of primitive recursive functions: from imperative programs to mathematical expressions to functional programs"</a> (PDF). Retrieved 20 August 2021.</li>
<li>Matos, Armando B. (2015). <a href="https://doi.org/10.1016%2Fj.tcs.2015.04.022">"The efficiency of primitive recursive functions: A programmer's view"</a>. <i><a href="/facts/Theoretical_Computer_Science/jSkGGuvy">Theoretical Computer Science</a></i>. 594: 65–81. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.tcs.2015.04.022">10.1016/j.tcs.2015.04.022</a>.</li>
<li><a href="/facts/Albert_R._Meyer/31B10sEp">Meyer, Albert R.</a>; <a href="/facts/Dennis_Ritchie/I1yu1UWU">Ritchie, Dennis MacAlistair</a> (1967). <i>The complexity of loop programs</i>. ACM '67: Proceedings of the 1967 22nd national conference. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F800196.806014">10.1145/800196.806014</a>.</li>
<li>Minsky, Marvin Lee (1967). <i>Computation: finite and infinite machines</i>. Prentice Hall. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1017%2FS0008439500029350">10.1017/S0008439500029350</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:227917578">227917578</a>.</li>
<li><a href="/facts/Dennis_Ritchie/I1yu1UWU">Ritchie, Dennis MacAlistair</a> (1967). <a href="https://www.computerhistory.org/collections/catalog/102790971"><i>Program structure and computational complexity (draft)</i></a> (Thesis). Computer History Museum (CHM). p. 181. Retrieved 16 October 2024.</li>
<li>Ritchie, Robert Wells (November 1965). <a href="https://msp.org/pjm/1965/15-3/p25.xhtml">"Classes of recursive functions based on Ackermann's function"</a>. <i><a href="/facts/Pacific_Journal_of_Mathematics/fBmfJLky">Pacific Journal of Mathematics</a></i>. 15 (3): 1027–1044. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2140%2Fpjm.1965.15.1027">10.2140/pjm.1965.15.1027</a>.</li>
<li>Schöning, Uwe (2001). <i>Theoretische Informatik-kurz gefasst</i> (4 ed.). London: Oxford University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-8274-1099-1.</li>
<li>Schöning, Uwe (2008). <i>Theoretische Informatik-kurz gefasst</i> (5 ed.). London: Oxford University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-8274-1824-1. <a href="http://www.dnb.de/EN/Home/home_node.html">DNB</a> <a href="http://d-nb.info/986529222">986529222</a>.</li>
<li>Tsichritzis, Dennis C (1970). "The Equivalence Problem of Simple Programs". <i><a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a></i>. 17 (4): 729–738. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321607.321621">10.1145/321607.321621</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16066171">16066171</a>.</li>
<li>Tsichritzis, Dennis C (1971). "A note on comparison of subrecursive hierarchies". <i><a href="/facts/Information_Processing_Letters/e2u7fEKe">Information Processing Letters</a></i>. 1 (2): 42–44. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2871%2990002-0">10.1016/0020-0190(71)90002-0</a>.</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://web.archive.org/web/20170609213325/http://www.eugenkiss.com/projects/lgw/">Loop, Goto & While</a></li>
<li><a href="https://programmersshield.blogspot.com/2023/07/loops-in-programming.html">Mastering the Art of Loops in Programming: A Step-by-Step Tutorial</a></li></ul>
<h2 id="mastering-the-art-of-loops-in-programming-a-step-by-step-tutorial">Mastering the Art of Loops in Programming: A Step-by-Step Tutorial</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Enderton 2012. - Enderton, Herbert (2012). Computability Theory. Academic Press. doi:10.1145/1555746.1555750. <a href="https://doi.org/10.1145%2F1555746.1555750" target="_blank">https://doi.org/10.1145%2F1555746.1555750</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Meyer & Ritchie 1967. - Meyer, Albert R.; Ritchie, Dennis MacAlistair (1967). The complexity of loop programs. ACM '67: Proceedings of the 1967 22nd national conference. doi:10.1145/800196.806014. <a href="https://doi.org/10.1145%2F800196.806014" target="_blank">https://doi.org/10.1145%2F800196.806014</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Brock 2020. - Brock, David C. (19 June 2020). "Discovering Dennis Ritchie's Lost Dissertation". CHM. Retrieved 14 July 2020. <a href="https://computerhistory.org/blog/discovering-dennis-ritchies-lost-dissertation/" target="_blank">https://computerhistory.org/blog/discovering-dennis-ritchies-lost-dissertation/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Ritchie 1967. - Ritchie, Dennis MacAlistair (1967). Program structure and computational complexity (draft) (Thesis). Computer History Museum (CHM). p. 181. Retrieved 16 October 2024. <a href="https://www.computerhistory.org/collections/catalog/102790971" target="_blank">https://www.computerhistory.org/collections/catalog/102790971</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Schöning 2008, p. 105. - Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. ISBN 978-3-8274-1824-1. DNB 986529222. <a href="http://www.dnb.de/EN/Home/home_node.html" target="_blank">http://www.dnb.de/EN/Home/home_node.html</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Schöning 2008, p. 93. - Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. ISBN 978-3-8274-1824-1. DNB 986529222. <a href="http://www.dnb.de/EN/Home/home_node.html" target="_blank">http://www.dnb.de/EN/Home/home_node.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Schöning 2001, p. 122. - Schöning, Uwe (2001). Theoretische Informatik-kurz gefasst (4 ed.). London: Oxford University Press. ISBN 3-8274-1099-1. <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Meyer & Ritchie 1967. - Meyer, Albert R.; Ritchie, Dennis MacAlistair (1967). The complexity of loop programs. ACM '67: Proceedings of the 1967 22nd national conference. doi:10.1145/800196.806014. <a href="https://doi.org/10.1145%2F800196.806014" target="_blank">https://doi.org/10.1145%2F800196.806014</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Schöning 2008, p. 105. - Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. ISBN 978-3-8274-1824-1. DNB 986529222. <a href="http://www.dnb.de/EN/Home/home_node.html" target="_blank">http://www.dnb.de/EN/Home/home_node.html</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>Schöning 2008, p. 112. - Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. ISBN 978-3-8274-1824-1. DNB 986529222. <a href="http://www.dnb.de/EN/Home/home_node.html" target="_blank">http://www.dnb.de/EN/Home/home_node.html</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>Meyer & Ritchie 1967. - Meyer, Albert R.; Ritchie, Dennis MacAlistair (1967). The complexity of loop programs. ACM '67: Proceedings of the 1967 22nd national conference. doi:10.1145/800196.806014. <a href="https://doi.org/10.1145%2F800196.806014" target="_blank">https://doi.org/10.1145%2F800196.806014</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
</ol>

LOOP (programming language) open-in-new

LOOP (programming language)