BlooP and FlooP: Difference between revisions
Ref |
correction |
||
Line 4: | Line 4: | ||
<!-- End of AfD message, feel free to edit beyond this point --> |
<!-- End of AfD message, feel free to edit beyond this point --> |
||
'''BLooP''' and '''FLooP''' are simple [[programming language]]s designed by [[Douglas Hofstadter]] to illustrate a point in his book ''[[Gödel, Escher, Bach]]''.<ref>[[Douglas Hofstadter]] (1979), ''[[Gödel, Escher, Bach]]'', Basic Books, Chapter XIII.</ref> BLooP is a [[Turing completeness|non-Turing-complete programming language]] whose |
'''BLooP''' and '''FLooP''' are simple [[programming language]]s designed by [[Douglas Hofstadter]] to illustrate a point in his book ''[[Gödel, Escher, Bach]]''.<ref>[[Douglas Hofstadter]] (1979), ''[[Gödel, Escher, Bach]]'', Basic Books, Chapter XIII.</ref> BLooP is a [[Turing completeness|non-Turing-complete programming language]] whose main control flow structure is a bounded [[loop (computing)|loop]] (i.e. recursion is not permitted). All programs in the language must terminate, and this language can only express [[primitive recursive function]]s.<ref>[http://plato.stanford.edu/entries/computability/ Stanford Encyclopedia of Philosophy: Computability and Complexity]</ref> |
||
FLooP is identical to BLooP except that it supports unbounded loops; it is a Turing-complete language and can express all [[computable function]]s. For example, it can express the [[Ackermann function]], which (not being primitive recursive) cannot be written in BLooP. |
FLooP is identical to BLooP except that it supports unbounded loops; it is a Turing-complete language and can express all [[computable function]]s. For example, it can express the [[Ackermann function]], which (not being primitive recursive) cannot be written in BLooP. |
Revision as of 00:45, 29 August 2011
An editor has nominated this article for deletion. You are welcome to participate in the deletion discussion, which will decide whether or not to retain it. |
BLooP and FLooP are simple programming languages designed by Douglas Hofstadter to illustrate a point in his book Gödel, Escher, Bach.[1] BLooP is a non-Turing-complete programming language whose main control flow structure is a bounded loop (i.e. recursion is not permitted). All programs in the language must terminate, and this language can only express primitive recursive functions.[2]
FLooP is identical to BLooP except that it supports unbounded loops; it is a Turing-complete language and can express all computable functions. For example, it can express the Ackermann function, which (not being primitive recursive) cannot be written in BLooP.
BLooP and FLooP can be regarded as models of computation, and have sometimes been used in teaching computability.[3]
BLooP examples
The only variables are output
(the return value of the procedure) and cell(i)
(an unbounded sequence of natural-number variables, indexed by constants, as in the Unlimited Register Machine[4]). The only operators are ⇐
(assignment), +
(addition), ×
(multiplication), <
(less-than), >
(greater-than) and =
(equals).
Each program uses only a finite number of cells, but the numbers in the cells can be arbitrarily large. Data structures such as lists can be handled by interpreting the number in a cell in specific ways, that is, by Gödel numbering the possible structures.
DEFINE PROCEDURE ''FACTORIAL'' [N]: BLOCK 0: BEGIN OUTPUT ⇐ 1; CELL(0) ⇐ 1; LOOP N TIMES: BLOCK 1: BEGIN OUTPUT ⇐ OUTPUT × CELL(0); CELL(0) ⇐ CELL(0) + 1; BLOCK 1: END; BLOCK 0: END.
Subtraction function (this is not a built-in operation):
DEFINE PROCEDURE ''MINUS'' [M,N]: BLOCK 0: BEGIN IF M < N, THEN: QUIT BLOCK 0; OUTPUT ⇐ 0; LOOP AT MOST M + 1 TIMES: BLOCK 1: BEGIN IF OUTPUT + N = M, THEN: ABORT LOOP 1; OUTPUT ⇐ OUTPUT + 1; BLOCK 1: END; BLOCK 0: END.
References
- ^ Douglas Hofstadter (1979), Gödel, Escher, Bach, Basic Books, Chapter XIII.
- ^ Stanford Encyclopedia of Philosophy: Computability and Complexity
- ^ David Mix Barrington (2004), CMPSCI 601: Theory of Computation, University of Massachusetts Amherst, Lecture 27.
- ^ Hofstadter refers to these cells as a set of "auxiliary variables."
External links
- Dictionary of Programming Languages - BLooP
- Dictionary of Programming Languages - FLooP
- The Retrocomputing Museum
- Portland Pattern Repository: Bloop Floop and Gloop
- A compiler for BlooP and FlooP