LOOP (programming language)

LOOP is a language that precisely captures primitive recursive functions.[1] The only operations supported in the language are assignment, addition, and looping a number of times that is fixed before loop execution starts.

The LOOP language was introduced in a 1967 paper by Albert R. Meyer and Dennis M. Ritchie. [2] Meyer and Ritchie showed the correspondence between the LOOP language and primitive recursive functions.

Dennis M. Ritchie formulated the LOOP language, which was also the topic of his unpublished Ph.D. thesis.[3][4]

It was also presented by Uwe Schöning, along with GOTO and WHILE.[5]

Features

Each primitive recursive function is LOOP-computable and vice versa.[6]

In contrast to GOTO programs and WHILE programs, LOOP programs always terminate.[7] 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).[8]

An example of a total computable function that is not LOOP computable is the Ackermann function.[9]

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:

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 := 0

means the value of the variable is set to 0.


A statement of the form

xi := xi + 1

means the value of the variable is incremented by 1.


A statement of the form

P1; P2

represents the sequential execution of sub-programs and , in that order.


A statement of the form

LOOP x DO P END

means 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.

Example programs

Assignment

The following LOOP program assigns the value of variable xi to variable xj.

xj := 0;
LOOP xi DO
  xj := xj + 1
END

In their seminal paper [10] Meyer & Ritchie made the assignment a basic statement. As the program above shows the assignment is redundant and can be removed from the list of basic statements. It 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:

xj := xi

Remark: One has to keep in mind that all variables are global. That the new statement is equivalent to a subroutine does not mean that it is a subroutine. Normally an activation record prevents all side effects. In this case however no other variable but xj is affected, so side effects do not occur, provided that xj, which at this point in the execution of the program might contain a nonzero value, is initialized to 0.

Projection

A special case of the assignment program is the program (we use the extended notation):

x0 := xi

This program computes the k-ary projection function , which extracts the i-th coordinate from an ordered k-tuple.

Predecessor

The predecessor function is defined as

.

This function can be computed by the following LOOP program, which sets the variable to .

/* 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.

Addition

In the following program, the variable is set to the sum of the variables and .

LOOP x1 DO
  x0 := x0 + 1
END;
LOOP x2 DO
  x0 := x0 + 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 + x2

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 .

x0 := x1
LOOP x2 DO
  x0 := x0 ∸ 1
END

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

x0 := x1 ∸ x2

Multiplication

The following LOOP program sets the value of the variable to the product of the variables and .

LOOP x1 DO
  x0 := x0 + x2
END

This multiplication program uses the syntax introduced by the addition subroutine from the previous example. The multiplication is performed here by adding the value of a total of times, storing results in .

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

Notes and references

  1. Herbert Enderton (2012). Computability Theory. Academic Press.
  2. Meyer, Albert R.; Ritchie, Dennis M. (1967). The complexity of loop programs. ACM '67: Proceedings of the 1967 22nd national conference. doi:10.1145/800196.806014.
  3. "Discovering Dennis Ritchie's Lost Dissertation". CHM. 2020-06-19. Retrieved 2020-07-14.
  4. "Program structure and computational complexity draft | 102790971 | Computer History Museum". www.computerhistory.org. Retrieved 2020-07-14.
  5. Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. p. 105. ISBN 978-3-8274-1824-1. DNB 986529222.
  6. Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. p. 105. ISBN 978-3-8274-1824-1. DNB 986529222.
  7. Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. p. 93. ISBN 978-3-8274-1824-1. DNB 986529222.
  8. Schöning, Uwe (2001). Theoretische Informatik-kurz gefasst (4 ed.). London: Oxford University Press. p. 122. ISBN 3-8274-1099-1.
  9. Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. p. 112. ISBN 978-3-8274-1824-1. DNB 986529222.
  10. Meyer & Ritchie: The complexity of loop programs, ACM 1967
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.