LOOP (programming language)
   HOME

TheInfoList



OR:

LOOP is a simple register language that precisely captures the
primitive recursive functions In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
. The language is derived from the
counter-machine model Although some authors use the name "register machine" synonymously with "counter machine", this article will give details and examples of only of the most primitive speciesthe "counter machine"of the genus "register machine." Within the species "co ...
. 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 In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an ''im ...
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 Albert Ronald da Silva Meyer (born 1941) is Hitachi America Professor emeritus of computer science at Massachusetts Institute of Technology (MIT). Biography Meyer received his PhD from Harvard University in 1972 in applied mathematics, under t ...
and Dennis M. Ritchie. They showed the correspondence between the LOOP language and
primitive recursive function In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
s. The language also was the topic of the unpublished PhD thesis of Ritchie. 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 function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
s (and thus a subset of the computable by WHILE and GOTO program functions). Meyer & Ritchie proved that each
primitive recursive function In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
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 P & ::= & x_i := 0 \\ & , & x_i := x_i + 1 \\ & , & P;P \\ & , & \mathtt \, x_i \, \mathtt \, P \, \mathtt \end Here, Var := \ are variable names and c \in \mathbb are constants.


Semantics

If P is a LOOP program, P is equivalent to a function f: \mathbb^k \rightarrow \mathbb. 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 xi := 0 means the value of the variable x_i is set to 0. A statement of the form xi := xi + 1 means the value of the variable x_i is incremented by 1. A statement of the form ''P''1; ''P''2 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 A branch, sometimes called a ramus in botany, is a woody structural member connected to the central trunk of a tree (or sometimes a shrub). Large branches are known as boughs and small branches are known as twigs. The term ''twig'' usually r ...
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 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 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 \operatorname instruction use the block of code below. x_j := \operatorname(x_i) =equiv xj := 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 Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
defined as: : \begin a + 0 &= a , & \textrm\\ a + S (b) &= S (a + b). & \textrm \end Here, S should be read as "successor". In the hyperoperater sequence it is the function \operatorname \operatorname(x_1,x_2) can be implemented by the LOOP program ADD( x1, x2) LOOP x1 DO x0 := x0 + 1 END; LOOP x2 DO x0 := x0 + 1 END


Multiplication

Multiplication is the hyperoperation function \operatorname \operatorname(x_1,x_2 ) can be implemented by the LOOP program MULT( x1, x2 ) x0 := 0; LOOP x2 DO x0 := ADD( x1, x0) 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.


More hyperoperators

Given a LOOP program for a hyperoperation function \operatorname, one can construct a LOOP program for the next level \operatorname(x_1,x_2) for instance (which stands for
exponentiation Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to r ...
) can be implemented by the LOOP program POWER( x1, x2 ) 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(n) = \begin 0 & \mboxn=0, \\ n-1 & \mbox\end. This function can be computed by the following LOOP program, which sets the variable x_0 to pred(x_1). ''/* 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 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: x0 := x1 ∸ 1 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. #


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 x_1 and x_2. x0 := x1 LOOP x2 DO x0 := x0 ∸ 1 END Like 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

*
μ-recursive function In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as i ...
*
Primitive recursive function In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
*
BlooP and FlooP and (Bounded loop and Free loop) are simple programming languages designed by Douglas Hofstadter to illustrate a point in his book ''Gödel, Escher, Bach''. BlooP is a non-Turing-complete programming language whose main control flow structure is ...


Notes and references


Bibliography

* * * * * * * * * * * * * * * * * * * * * * * * * * * {{refend


External links


Loop, Goto & While
Computability theory