LOOP (programming language) explained
LOOP is a simple register language that precisely captures 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 (like 'CleaR', 'INCrement', 'DECrement', 'CoPY', ...) operate on the registers. The only control flow instruction is 'LOOP x DO ... END'. It causes the instructions within its scope to be repeated x times. (Changes of the content of register x during the execution of the loop do not affect the number of passes.)
History
The LOOP language was formulated in a 1967 paper by Albert R. Meyer and Dennis M. Ritchie.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.[1] [2]
It was also presented by Uwe Schöning, along with GOTO and WHILE.
Design philosophy and features
In contrast to GOTO programs and WHILE programs, LOOP programs always terminate. 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).
Meyer & Ritchie proved that each primitive recursive function is LOOP-computable and vice versa.
An example of a total computable function that is not LOOP computable is the Ackermann function.
Formal definition
Syntax
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:
\begin{array}{lrl}
P&::=&xi:=0\\
&|&xi:=xi+1\\
&|&P;P\\
&|&LOOPxiDOPEND
\end{array}
Here,
are variable names and
are constants.
Semantics
If P is a LOOP program, P is equivalent to a function
. The variables
through
in a LOOP program correspond to the arguments of the function
, and are initialized before program execution with the appropriate values. All other variables are given the initial value zero. The variable
corresponds to the value that
takes when given the argument values from
through
.
A statement of the form xi := 0means the value of the variable
is set to 0.
A statement of the form xi := xi + 1means the value of the variable
is incremented by 1.
A statement of the form P1; P2represents the sequential execution of sub-programs
and
, in that order.
A statement of the form LOOP x DO P ENDmeans the repeated execution of the partial program
a total of
times, where the value that
has at the beginning of the execution of the statement is used. Even if
changes the value of
, it won't affect how many times
is executed in the loop. If
has the value zero, then
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.
Creating "convenience instructions"
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'.
- Example
The k-ary projection function
extracts the i-th coordinate from an ordered k-tuple.
In their seminal paper Meyer & Ritchie made the assignment
a basic statement.As the example shows the assignment can be derived from the list of basic statements.
To create the
instruction use the block of code below.
xj:=\operatorname{assign}(xi)
=
equivxj := 0; LOOP xi DO xj := xj + 1 END
Again, all of this is for convenience only; none of this increases the model's intrinsic power.
Example Programs
Addition
Addition is recursively defined as:
\begin{align}
a+0&=a,&rm{(1)}\\
a+S(b)&=S(a+b).&rm{(2)}
\end{align}
Here, S should be read as "successor".
In the hyperoperater sequence it is the function
can be implemented by the LOOP program ADD(x
1, x
2)
LOOP x1 DO x0 := x0 + 1 END; LOOP x2 DO x0 := x0 + 1 END
Multiplication
can be implemented by the LOOP program MULT(x
1, x
2)
x0 := 0; LOOP x2 DO x0 := ADD(x1, x0) ENDThe 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.
More hyperoperators
, one can construct a LOOP program for the next level
for instance (which stands for
exponentiation) can be implemented by the LOOP program POWER(x
1, x
2)
x0 := 1; LOOP x2 DO x0 := MULT(x1, x0) END
The exponentiation program, expanded, has three nested LOOP instructions.
Predecessor
The predecessor function is defined as
\operatorname{pred}(n)=\begin{cases}0&ifn=0,\ n-1&otherwise\end{cases}
.This function can be computed by the following LOOP program, which sets the variable
to
.
/* precondition: x2 = 0 */ LOOP x1 DO x0 := x2; x2 := x2 + 1 END
Expanded, this is the program
/* precondition: x2 = 0 */ LOOP x1 DO x0 := 0; LOOP x2 DO x0 := x0 + 1 END; x2 := x2 + 1 ENDThis 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: x0 := x1 ∸ 1Remark: 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.
Cut-off subtraction
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
and
. x
0 := x
1 LOOP x
2 DO x
0 := x
0 ∸ 1
ENDLike before we can extend the LOOP syntax with the statement: x0 := x1 ∸ x2
If then else
An if-then-else statement with if x1 > x2 then P1 else P2:
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;
See also
Bibliography
- Axt. Paul . Iteration of relative primitive recursion . . 1966 . 167 . 53–55 . 10.1007/BF01361215. 119730846 .
- Axt. Paul . Iteration of primitive recursion . . 1970 . 35 . 3 . 253–255 . 10.1002/malq.19650110310.
- Book: Calude, Cristian . Theories of Computational Complexity . . Annals of Discrete Mathematics . 1988 . 35 . 9780080867755.
- Cherniavsky . John Charles . Simple Programs Realize Exactly Presburger Formulas . . 1976 . 5 . 4 . 666–677 . 10.1137/0205045.
- Cherniavsky . John Charles . Kamin . Samuel Noah . A Complete and Consistent Hoare Axiomatics for a Simple Programming Language . . 1979 . 26 . 1 . 119–128 . 10.1145/322108.322120. 13062959 . free .
- Constable . Robert L. . Borodin . Allan B . Subrecursive programming languages, part I: Efficiency and program structure . . 1972 . 10.1145/321707.321721 . 19 . 3 . 526–568 . 42474303 . free .
- Crolard . Tristan . Lacas . Samuel . Valarcher . Pierre . On the expressive power of the loop language . Nordic Journal of Computing . 2006 . 13 . 46–57 .
- Crolard . Tristan . Polonowski . Emmanuel . Valarcher . Pierre . Extending the loop language with higher-order procedural variables . . 2009 . 10 . 4. 1–37 . 10.1145/1555746.1555750 . 1367078 .
- Book: Enderton, Herbert . Computability Theory. Academic Press . 2012 . 10.1145/1555746.1555750 . free.
- Fachini . Emanuela . Maggiolo-Schettini . Andrea . A hierarchy of primitive recursive sequence functions . R.A.I.R.O. - Informatique Théorique - Theoretical Informatics . 1979 . 13 . 1 . 49–67 . 10.1051/ita/1979130100491 . free.
- Fachini . Emanuela . Maggiolo-Schettini . Andrea . Comparing Hierarchies of Primitive Recursive Sequence Functions . Zeitschrift für mathematische Logik und Grundlagen der Mathematik . 1982 . 28 . 27–32 . 431–445 . 10.1002/malq.19820282705.
- Goetze . Bernhard . Nehrlich . Werner . The Structure of Loop Programs and Subrecursive Hierarchies . Zeitschrift für mathematische Logik und Grundlagen der Mathematik . 1980 . 26 . 14–18 . 255–278 . 10.1002/malq.19800261407 . free.
- Ibarra . Oscar H. . Leininger . Brian S. . Characterizations of Presburger Functions . . 1981 . 10 . 1 . 22–39 . 10.1137/0210003.
- Ibarra . Oscar H. . Rosier . Louis E. . Simple Programming Languages and Restricted Classes of Turing Machines . . 1983 . 26 . 1–2 . 197–220 . 10.1016/0304-3975(83)90085-3. free .
- Book: Kfoury . A.J. . Moll . Robert N. . Arbib . Michael A. . A Programming Approach to Computability . Springer, New York, NY . 1982 . 978-1-4612-5751-6 . 10.1007/978-1-4612-5749-3.
- Machtey . Michael . Augmented loop languages and classes of computable functions . . 1972. 6 . 6 . 603–624 . 10.1016/S0022-0000(72)80032-1. free .
- Web site: PlanetMath . primitive recursive vector-valued function . 2021-08-21.
- Web site: Matos . Armando B. . Closed form of primitive recursive functions: from imperative programs to mathematical expressions to functional programs . 2014-11-03 . 2021-08-20.
- Matos . Armando B. . The efficiency of primitive recursive functions: A programmer's view . . 2015 . 594 . 65–81 . 10.1016/j.tcs.2015.04.022. free .
- Meyer . Albert R. . Albert R. Meyer . Ritchie . Dennis MacAlistair . Dennis Ritchie . The complexity of loop programs . ACM '67: Proceedings of the 1967 22nd national conference . 1967 . 10.1145/800196.806014. free .
- Book: Minsky, Marvin Lee <!--. Marvin_Minsky--> . Computation: finite and infinite machines . Prentice Hall . 1967 . 10.1017/S0008439500029350. 227917578 .
- Book: Ritchie, Dennis MacAlistair <!--. Dennis_Ritchie-->
. Dennis_Ritchie--> . Program structure and computational complexity (draft) . 1967 .
- Ritchie . Robert Wells . Classes of recursive functions based on Ackermann's function . . November 1965. 15 . 3 . 1027–1044 . 10.2140/pjm.1965.15.1027. free .
- Book: Schöning, Uwe . Theoretische Informatik-kurz gefasst . 4 . Oxford University Press . London . 2001 . 3-8274-1099-1.
- Book: Schöning, Uwe . Theoretische Informatik-kurz gefasst . 5 . Oxford University Press . London . 2008 . 978-3-8274-1824-1 . DNB 986529222.
- Tsichritzis . Dennis C . The Equivalence Problem of Simple Programs . . 1970 . 17 . 4 . 729–738 . 10.1145/321607.321621. 16066171 .
- Tsichritzis . Dennis C . A note on comparison of subrecursive hierarchies . . 1971 . 1 . 2 . 42–44 . 10.1016/0020-0190(71)90002-0.
External links
Notes and References
- Web site: 2020-06-19. Discovering Dennis Ritchie's Lost Dissertation. 2020-07-14. CHM. en.
- Book: Program structure and computational complexity draft 102790971 Computer History Museum. 2020-07-14. www.computerhistory.org. 1967 .