LOOP (programming language)

The LOOP language was formulated in a 1967 paper by Albert R. Meyer and Dennis M. Ritchie.{{sfn|Meyer|Ritchie|1967}}

They showed the correspondence between the LOOP language and primitive recursive functions.

The language also was the topic of the unpublished PhD thesis of Ritchie.{{sfn|Brock|2020}}{{sfn|Ritchie|1967}}

It was also presented by Uwe Schöning, along with GOTO and WHILE.{{sfn|Schöning|2008|p=105}}

In contrast to GOTO programs and WHILE programs, LOOP programs always terminate.{{sfn|Schöning|2008|p=93}} 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).{{sfn|Schöning|2001|p=122}}

Meyer & Ritchie proved that each primitive recursive function is LOOP-computable and vice versa.{{sfn|Meyer|Ritchie|1967}}{{sfn|Schöning|2008|p=105}}

An example of a total computable function that is not LOOP computable is the Ackermann function.{{sfn|Schöning|2008|p=112}}

LOOP-programs consist of the symbols LOOP, DO, END, :=, + and ; as well as any number of variables and constants. LOOP-programs have the following syntax in modified Backus–Naur form:

:$\backslash 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}

Here, $Var\; :=\; \backslash \{\; x\_0,\; x\_1,\; ...\; \backslash \}$ are variable names and $c\; \backslash in\; \backslash mathbb\{N\}$ are constants.

If P is a LOOP program, P is equivalent to a function $f:\; \backslash mathbb\{N\}^k\; \backslash rightarrow\; \backslash mathbb\{N\}$. The variables $x\_1$ through $x\_k$ in a LOOP program correspond to the arguments of the function $f$, and are initialized before program execution with the appropriate values. All other variables are given the initial value zero. The variable $x\_0$ corresponds to the value that $f$ takes when given the argument values from $x\_1$ through $x\_k$.

A statement of the form

x_i := 0

means the value of the variable $x\_i$ is set to 0.

A statement of the form

x_i := x_i + 1

means the value of the variable $x\_i$ is incremented by 1.

A statement of the form

P₁; P₂

represents the sequential execution of sub-programs $P\_1$ and $P\_2$, in that order.

A statement of the form

LOOP x DO P END

means the repeated execution of the partial program $P$ a total of $x$ times, where the value that $x$ has at the beginning of the execution of the statement is used. Even if $P$ changes the value of $x$, it won't affect how many times $P$ is executed in the loop. If $x$ has the value zero, then $P$ is not executed inside the LOOP statement. This allows for branches in LOOP programs, where the conditional execution of a partial program depends on whether a variable has value zero or one.

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 {{spaced ndash}}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'.

; Example

The k-ary projection function $U\_i^k\; (x\_1,\; ...,\; x\_i,\; ...,\; x\_k)\; =\; x\_i$ extracts the i-th coordinate from an ordered k-tuple.

In their seminal paper {{sfn|Meyer|Ritchie|1967}} Meyer & Ritchie made the assignment $x\_j\; :=\; x\_i$ a basic statement.

As the example shows the assignment can be derived from the list of basic statements.

To create the $\backslash operatorname\{assign\}$ instruction use the block of code below.

$x\_j\; :=\; \backslash operatorname\{assign\}(x\_i)$ =_equiv

x_j := 0;

LOOP x_i DO

x_j := x_j + 1

END

Again, all of this is for convenience only; none of this increases the model's intrinsic power.

Addition is recursively defined as:

: $\backslash begin\{align\}$

a + 0 &= a , & \textrm{(1)}\\

a + S (b) &= S (a + b). & \textrm{(2)}

\end{align}

Here, S should be read as "successor".

In the hyperoperater sequence it is the function $\backslash operatorname\{H\_1\}$

$\backslash operatorname\{H\_1\}(x\_1,x\_2)$ can be implemented by the LOOP program ADD( x₁, x₂)

LOOP x₁ DO

x₀ := x₀ + 1

END;

LOOP x₂ DO

x₀ := x₀ + 1

END

Multiplication is the hyperoperation function $\backslash operatorname\{H\_2\}$

$\backslash operatorname\{H\_2\}(x\_1,x\_2\; )$ can be implemented by the LOOP program MULT( x₁, x₂ )

x₀ := 0;

LOOP x₂ DO

x₀ := ADD( x₁, x₀)

END

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.

Given a LOOP program for a hyperoperation function $\backslash operatorname\{H\_i\}$, one can construct a LOOP program for the next level

$\backslash operatorname\{H\_3\}(x\_1,x\_2)$ for instance (which stands for exponentiation) can be implemented by the LOOP program POWER( x₁, x₂ )

x₀ := 1;

LOOP x₂ DO

x₀ := MULT( x₁, x₀ )

END

The exponentiation program, expanded, has three nested LOOP instructions.

The predecessor function is defined as

:.

This function can be computed by the following LOOP program, which sets the variable $x\_0$ to $pred(x\_1)$.

/* precondition: x2 = 0 */

LOOP x₁ DO

x₀ := x₂;

x₂ := x₂ + 1

END

Expanded, this is the program

/* precondition: x₂ = 0 */

LOOP x₁ DO

x₀ := 0;

LOOP x₂ DO

x₀ := x₀ + 1

END;

x₂ := x₂ + 1

END

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:

x₀ := x₁ ∸ 1

Remark: Again one has to mind the side effects. The predecessor program changes the variable x₂, which might be in use elsewhere. To expand the statement x₀ := x₁ ∸ 1, one could initialize the variables x_n, x_n+1 and x_n+2 (for a big enough n) to 0, x₁ and 0 respectively, run the code on these variables and copy the result (x_n) to x₀. A compiler can do this.

If in the 'addition' program above the second loop decrements x₀ instead of incrementing, the program computes the difference (cut off at 0) of the variables $x\_1$ and $x\_2$.

x₀ := x₁

LOOP x₂ DO

x₀ := x₀ ∸ 1

END

Like before we can extend the LOOP syntax with the statement:

x₀ := x₁ ∸ x₂

An if-then-else statement with if x₁ > x₂ then P1 else P2:

x_n1 := x₁ ∸ x₂;

x_n2 := 0;

x_n3 := 1;

LOOP x_n1 DO

x_n2 := 1;

x_n3 := 0

END;

LOOP x_n2 DO

P1

END;

LOOP x_n3 DO

P2

END;

• μ-recursive function
• Primitive recursive function
• BlooP and FlooP

{{reflist}}

{{refbegin}}

• {{cite journal | last=Axt| first=Paul | title=Iteration of relative primitive recursion | journal=Mathematische Annalen | year=1966 | volume=167 | pages=53–55 | doi=10.1007/BF01361215| s2cid=119730846 }}
• {{cite journal | last=Axt| first=Paul | title=Iteration of primitive recursion | journal=Journal of Symbolic Logic | year=1970 | volume=35 | issue=3 | pages=253–255 | url=https://projecteuclid.org/euclid.jsl/1183737320 | doi=10.1002/malq.19650110310}}
• {{Cite web|last=Brock|first=David C.|date=2020-06-19|title=Discovering Dennis Ritchie's Lost Dissertation|url=https://computerhistory.org/blog/discovering-dennis-ritchies-lost-dissertation/|access-date=2020-07-14|website=CHM}}
• {{cite book | last=Calude | first=Cristian | title=Theories of Computational Complexity | publisher=North Holland Publishing Company | series=Annals of Discrete Mathematics | year=1988 | volume=35 | isbn=9780080867755}}
• {{cite journal | last=Cherniavsky | first=John Charles | title=Simple Programs Realize Exactly Presburger Formulas | journal=SIAM Journal on Computing | year=1976 | volume=5 | issue=4 | pages=666–677 |doi=10.1137/0205045}}
• {{cite journal | last1=Cherniavsky | first1=John Charles | last2=Kamin | first2=Samuel Noah | title=A Complete and Consistent Hoare Axiomatics for a Simple Programming Language | journal=Association for Computing Machinery | year=1979 | volume=26 | issue=1 | pages=119–128 | doi=10.1145/322108.322120| s2cid=13062959 | doi-access=free }}
• {{cite journal | last1=Constable | first1=Robert L. | last2=Borodin | first2=Allan B | title=Subrecursive programming languages, part I: Efficiency and program structure | journal=Journal of the ACM | year=1972 | doi=10.1145/321707.321721 | volume=19 | issue=3 | pages=526–568 | s2cid=42474303 | doi-access=free }}
• {{cite journal | last1=Crolard | first1=Tristan | last2=Lacas | first2=Samuel | last3=Valarcher | first3=Pierre | title=On the expressive power of the loop language | journal=Nordic Journal of Computing | year=2006 | volume=13 | pages=46–57 | url=https://www.researchgate.net/publication/220673166}}
• {{cite journal | last1=Crolard | first1=Tristan | last2=Polonowski | first2=Emmanuel | last3=Valarcher | first3=Pierre | title=Extending the loop language with higher-order procedural variables | journal=ACM Transactions on Computational Logic | year=2009 | volume=10 | issue=4| pages=1–37 | doi=10.1145/1555746.1555750 | s2cid=1367078 | url=https://hal.archives-ouvertes.fr/hal-00422158/file/LoopW.pdf }}
• {{cite book | last=Enderton | first=Herbert | title=Computability Theory|publisher=Academic Press | year=2012 | doi=10.1145/1555746.1555750 | doi-access=free}}
• {{cite journal | last1=Fachini | first1=Emanuela | last2=Maggiolo-Schettini | first2=Andrea | title=A hierarchy of primitive recursive sequence functions | journal=R.A.I.R.O. - Informatique Théorique - Theoretical Informatics | year=1979 | volume=13 | issue=1 | pages=49–67 | doi=10.1051/ita/1979130100491 | doi-access=free}}
• {{cite journal | last1=Fachini | first1=Emanuela | last2=Maggiolo-Schettini | first2=Andrea | title=Comparing Hierarchies of Primitive Recursive Sequence Functions | journal=Zeitschrift für mathematische Logik und Grundlagen der Mathematik | year=1982 | volume=28 | issue=27–32 | pages=431–445 | doi=10.1002/malq.19820282705}}
• {{cite journal | last1=Goetze | first1=Bernhard | last2=Nehrlich | first2=Werner | title=The Structure of Loop Programs and Subrecursive Hierarchies | journal=Zeitschrift für mathematische Logik und Grundlagen der Mathematik | year=1980 | volume=26 | issue=14–18 | pages=255–278 | doi=10.1002/malq.19800261407 | doi-access=free}}
• {{cite journal | last1=Ibarra | first1=Oscar H. | last2=Leininger | first2=Brian S. | title=Characterizations of Presburger Functions | journal=SIAM Journal on Computing | year=1981 | volume=10 | issue=1 | pages=22–39 |doi=10.1137/0210003}}
• {{cite journal | last1=Ibarra | first1=Oscar H. | last2=Rosier | first2=Louis E. | title=Simple Programming Languages and Restricted Classes of Turing Machines | journal=Theoretical Computer Science | year=1983 | volume=26 | issue=1–2 | pages=197–220 |doi=10.1016/0304-3975(83)90085-3| doi-access=free }}
• {{cite book | last1=Kfoury | first1=A.J. | last2=Moll | first2=Robert N. | last3=Arbib | first3=Michael A. | title=A Programming Approach to Computability | publisher=Springer, New York, NY | year=1982 | isbn=978-1-4612-5751-6 | doi=10.1007/978-1-4612-5749-3}}
• {{cite journal | last=Machtey | first=Michael | title=Augmented loop languages and classes of computable functions | journal=Journal of Computer and System Sciences | year=1972| volume=6 | issue=6 | pages=603–624 | doi=10.1016/S0022-0000(72)80032-1| doi-access=free }}
• {{cite web | author=PlanetMath | title=primitive recursive vector-valued function | url=https://planetmath.org/primitiverecursivevectorvaluedfunction | access-date=2021-08-21}}
• {{cite web | last=Matos | first=Armando B. | title=Closed form of primitive recursive functions: from imperative programs to mathematical expressions to functional programs | date=2014-11-03 | access-date=2021-08-20| url=https://www.dcc.fc.up.pt/~acm/loops.pdf}}
• {{cite journal | last=Matos | first=Armando B. | title=The efficiency of primitive recursive functions: A programmer's view | journal=Theoretical Computer Science | year=2015 | volume=594 | pages= 65–81 | doi=10.1016/j.tcs.2015.04.022| doi-access=free }}
• {{cite conference | last1=Meyer | first1=Albert R. | authorlink1=Albert R. Meyer | last2=Ritchie | first2=Dennis MacAlistair | authorlink2=Dennis Ritchie | title=The complexity of loop programs | conference=ACM '67: Proceedings of the 1967 22nd national conference | year=1967 | doi=10.1145/800196.806014| doi-access=free }}
• {{cite book | last=Minsky | first=Marvin Lee | title=Computation: finite and infinite machines | publisher=Prentice Hall | year=1967 | doi=10.1017/S0008439500029350| s2cid=227917578 }}
• {{Cite thesis|last=Ritchie | first=Dennis MacAlistair| authorlink=Dennis Ritchie|title=Program structure and computational complexity (draft)|url=https://www.computerhistory.org/collections/catalog/102790971|access-date=2024-10-16|publisher=Computer History Museum (CHM)|pages=181|date=1967}}
• {{cite journal |last=Ritchie | first=Robert Wells | title=Classes of recursive functions based on Ackermann's function | journal=Pacific Journal of Mathematics | date=November 1965| volume=15 | issue=3 | pages=1027–1044 | url=https://msp.org/pjm/1965/15-3/p25.xhtml | doi=10.2140/pjm.1965.15.1027| doi-access=free }}
• {{cite book | last=Schöning | first=Uwe | title=Theoretische Informatik-kurz gefasst | edition=4 | publisher=Oxford University Press | location=London | year=2001 | isbn=3-8274-1099-1}}
• {{cite book | last=Schöning | first=Uwe | title=Theoretische Informatik-kurz gefasst | edition=5 | publisher=Oxford University Press | location=London | year=2008 | isbn=978-3-8274-1824-1 | id=[http://www.dnb.de/EN/Home/home_node.html DNB] [http://d-nb.info/986529222 986529222]}}
• {{cite journal | last=Tsichritzis | first=Dennis C | title=The Equivalence Problem of Simple Programs | journal=Journal of the ACM | year=1970 | volume=17 | issue=4 |pages=729–738 | doi=10.1145/321607.321621| s2cid=16066171 }}
• {{cite journal | last=Tsichritzis | first=Dennis C | title=A note on comparison of subrecursive hierarchies | journal=Information Processing Letters | year=1971 | volume=1 | issue=2 |pages= 42–44 | doi=10.1016/0020-0190(71)90002-0}}

{{refend}}

• [https://web.archive.org/web/20170609213325/http://www.eugenkiss.com/projects/lgw/ Loop, Goto & While]
• [https://programmersshield.blogspot.com/2023/07/loops-in-programming.html Mastering the Art of Loops in Programming: A Step-by-Step Tutorial]

Category:Computability theory