10 ms·

What type of Machine is the C Preprocessor?

62 points by cremno 13y ago

jerf 13y ago
"We imagine Turing Machine memory having an infinite tape which is just there, not having a tape that must be generated as the head moves." This is one of those times when you're probably better off saying and thinking "unbounded" rather than "infinite". The point of a TM is not that it "literally" (to the extent that term applies anyhow) has "infinite" cells in it, the point is that there is no point in the computation in which it will reach for another cell and be told that there isn't one. (So there isn't even a way to represent that.) Many "infinite" things are better conceived of as "unbounded". For another example, "infinite lists" in Haskell. Obviously, they can not concretely manifest infinitely many cells in memory, but there is no point at which the runtime will reach for "the next cell" and be told it has reached the end of the list. That is also why it's better to model our real computers with TM math, even though they obviously do not have literally infinite amounts of memory. As long as a software process runs along and is never told that it is out of memory when it asks for more, we get fairly TM-like behavior, or we get a crash if it does run out. By contrast, while the FSM model is in some sense more mathematically accurate, it is less useful for modeling real computers, since it is so weak. I think this formulation also better intuitively explains why we use infinity so often in our proofs; by saying "and there's always another one if you want it", we remove the case where we have to handle there not being another one. And that case can get quite hairy, as anyone who has watched their machine self-immolate after it discovers it is out of RAM can attest to. :) (It can also be every bit as mathematically tedious to deal with, too.) The further I got through grad school, the more I said "unbounded" rather than "infinite".
- grannyg00se 13y ago
  "The further I got through grad school, the more I said "unbounded" rather than "infinite"." I think there's a huge difference between simply saying "unbounded" compared to going through that detailed explanation you just gave. In the latter case, it's very clear what the difference is. But without the explanation I'd guess that people will think something like this: unbounded -> without bound -> infinite In other words, without the explanation "unbounded" becomes a synonym for "infinite".
  - danbruc 13y ago
    Depending on the context unbounded and infinite may mean very different things, for example the surface of a sphere being unbounded but finite.
    - gohrt 13y ago
      A sphere is bounded but infinite* http://en.wikipedia.org/wiki/Compact_space http://en.wikipedia.org/wiki/Compact_space *Infnite cardinality of points, not infinite in measure.
    - jerf 13y ago
      That's why I didn't simply drop the word infinite. There are cases where it is appropriate. What is the cardinality of the natural numbers? Infinite... "unbounded" is definitely not right there. But when we use infinity in proofs, we are more often using it to mean "unbounded" rather than truly a "manifested infinity", to use a sloppy phrase; we're using it to get rid of the nasty edge case, not because we expect a real implementation of whatever the proof is proving to actually require infinite RAM. Also, by "we", I should clarify I mean discrete mathematicians and computer scientists, who are usually dealing in the discrete case. In the continuous case, infinities come up "for real" more often.
  - gohrt 13y ago
    The relevant distinction isn't between "bounded" and "finite", but between the size of a container and the size of its elements. The difference between "bounded" and "infinite" is the difference between "measure" and "cardinality". That is , "bounded" refers to a notion of distance, while "finite" refers to a measure of count. There are bounded infinities (such as the set of all rational or numbers between 0 and 1), but there are no unbounded finities. A container that contains finite objects of all sizes must be an infinite/unbounded container.
  - baddox 13y ago
    "Unbounded" means "any finite number, no matter how large." For many people, this might be what they think of when they hear "infinite," but in mathematics, "infinity" is an entirely different concept.
- csense 13y ago
  I once read an analogy that said to think of the "infinite tape" of a Turing machine as similar to how physicists think about infinite parallel plates, etc. The infinite case can be easier to treat theoretically, and also give key insights, that might not be attained in the finite case. Even though you have an understanding that any real system is finite, imagining an infinite system is a useful approximation. And as long as you're operating in a region that's not close to the edge, the edges don't make a difference to the outcome. Likewise, while real machines are really DFA's since they have a finite amount of memory, thinking of them as having infinite memory is a much better approximation. And as long as you don't "get close to the edges" by e.g. trying to allocate more memory than your machine has available, it works perfectly.
chriswarbo 13y ago
I don't think there's a specific name for this kind of Turing Machine, but it looks to me like it's primitive-recursive, similar to Hofstadter's BLooP ('bounded loop') language. It's basically the difference between for loops, which specify up-front how many times to loop, and while loops, which keep going until some dynamic condition is met. For loops are total, while loops are Turing complete. Note that these are the CompSci definitions of for and while; most languages with "for" syntax are actually implemening while loops. There are some interesting kinds of Turing Machine which use limited tapes, rather than limited transition tables. For example, a monotone Turing machine can have heads which only move one way. They're useful for modelling demand-driven input and output (one read-only, monotone input tape, one write-only, monotone outpu tape and one read-write non-monotone work tape). Other machines that I've seen in research are 'enumerable-output machines', which can only edit their previous output if it ends up lexicographically higher, and 'Generalised Turing Machines' which can edit their output as long as each bit takes a finite number of steps to 'stabilise'. These machines have been investigated by Jurgen Schmidhuber, among others.
- gus_massa 13y ago
  I agree. After reading in the article that: > The main argument against Turing completeness was that my implementation did not support unbounded recursion. I’m almost sure they are Primitive recursive function, but I didn’t have time to write the complete proof. http://en.wikipedia.org/wiki/Primitive_recursive_function#Limitations http://en.wikipedia.org/wiki/Primitive_recursive_function#Li...
  - gus_massa 13y ago
    From a previous article of the same author: http://theorangeduck.com/page/c-preprocessor-turing-complete http://theorangeduck.com/page/c-preprocessor-turing-complete > This is a fairly clear distinction and a compelling argument. Clearly there are languages where you can effectively express unbounded recursion function() { function() } and the C preprocessor is not one of them. >* But there are a number of subtleties going on here. For example, if we consider the set of macros I created to be the "machinery", and the "language" to be the Brainfuck input to my system, then it is indeed Turing complete. That is - I have created machinery which can simulate Turing complete languages. Taking all the above definitions into account, consider how odd it is that Turing complete machinery can be expressed in a non Turing complete language.* And from the “Brainfuck interpreter written in the C preprocessor”: https://github.com/orangeduck/CPP_COMPLETE https://github.com/orangeduck/CPP_COMPLETE > Currently the maximum recursion depth is set to around 1000 and the data array size around 100. These can be easily extended but for now, as a general rule of thumb computations exceeding 1000 steps may not run. Here is the problem. We can consider the one-step-interpreter: it’s a function that has as arguments a program, the current instruction index and the whole memory state, and this function computes the next instruction index and the next whole memory state. This one-step-interpreter is primitive recursive. He put that function inside a bounded loop, which is also implementable as a primitive recursive function. So essentially he created an interpreter that runs a program for at most a fixed number of steps, where this number is an argument of the function (or worse, in this case a constant). Interpreter(Program, Memory, MaxSteps) is a recursive primitive function. To be Turing complete, he needs to write InterpreterForEverIfNecesary(Program, Memory). With a fixed MaXSteps value, it can’t compute all recursive primitive function.
lisper 13y ago
"What we are missing is the ability to re-enter old states." That's deadly. Any machine with a finite number of states that cannot re-enter a state it has previously been in must necessarily halt on all input. That makes it strictly less powerful than even an FSM.
- caf 13y ago
  It is worth noting that must necessarily halt on all input is quite a desirable property in a macro language evaluated at compile time.
  - gus_massa 13y ago
    On the other hand, in Lisp/Scheme/... language family you have a Turing complete language for macro language, Lisp/Scheme/... respectively. In those languages, macros are powerful and must be used with care. The advantage is that complex macros are easy to write.
  - lisper 13y ago
    That is arguable. All else being equal it might be true, but all else is not equal. The benefit of never having your compiler enter an infinite loop may not be worth the cost in terms of lost expressive power.
    - mtdewcmu 13y ago
      Has it been proven that the ability to write undecidable programs confers expressive power such that you can't have one without the other? It seems self-evident that running forever can't be useful, so you should be able to say WLOG that useful programs always halt. So the set of all useful programs is strictly smaller than the set of Turing machines. Is there a formal reason why Turing machines are desirable?
      - lisper 13y ago
        > Has it been proven that the ability to write undecidable programs confers expressive power such that you can't have one without the other? Yes. > It seems self-evident that running forever can't be useful Really? Do you not think that it might be useful for, say, an operating system to run forever?
sonnyOrullivan 13y ago
Wouldn't it simply be a linear bounded automaton (LBA)? I understand you can implement recursion via some tricks but only as many steps as you predefine (see e.g. https://stackoverflow.com/questions/7508475/is-c-preprocessor-metaprogramming-turing-complete https://stackoverflow.com/questions/7508475/is-c-preprocesso...) This reeks like an LBA to me.
- roywiggins 13y ago
  My first instinct is that you're right- at least, I don't think it can be any more powerful than an LBA: if there's a finite number of state transitions it can make, then it can only actually "get to" a certain distance along the tape, and you can just chop the tape at that point.
  - lisper 13y ago
    Nope, a cpp-machine is strictly less powerful than an LBA, or even an FSA. An LBA (and an FSA) can enter an infinite loop. A cpp-machine can't.
NAFV_P 13y ago
A few months ago I got fed up with losing track of what I had written in C. So I knocked up some python scripts to write templates for me, it displays the date and time the file was created and the filename in a comment. This concept can be taken much further. CPP has been known to be abused by programmers as a general text processor, has anyone else started using another language to help them write C?
- akjj 13y ago
  C++ and Objective-C both began as preprocessors for C.
  - NAFV_P 13y ago
    Wow, it's surprising what you can do with it.
    - tbirdz 13y ago
      Just to clarify a bit, C++ and Objective were not written in the C pre-processor, but rather implemented as their own pre-processor program, analogous to Qt's moc.
      - craigching 13y ago
        Yes like Cfront [1]. I used that back in the day, the pain of it caused me to rewrite all my C++ in C though :p Call me a coward! [1] -- http://en.wikipedia.org/wiki/Cfront http://en.wikipedia.org/wiki/Cfront
      - NAFV_P 13y ago
        > Just to clarify a bit, C++ and Objective were not written in the C pre-processor, but rather implemented as their own pre-processor program, analogous to Qt's moc. I bet these pre-processor programs were themselves written in C.
- ChuckMcM 13y ago
  You mean like $ SCCS %G% %M% %W% $ ?

62 points by cremno 13y ago

jerf 13y ago

"We imagine Turing Machine memory having an infinite tape which is just there, not having a tape that must be generated as the head moves." This is one of those times when you're probably better off saying and thinking "unbounded" rather than "infinite". The point of a TM is not that it "literally" (to the extent that term applies anyhow) has "infinite" cells in it, the point is that there is no point in the computation in which it will reach for another cell and be told that there isn't one. (So there isn't even a way to represent that.) Many "infinite" things are better conceived of as "unbounded". For another example, "infinite lists" in Haskell. Obviously, they can not concretely manifest infinitely many cells in memory, but there is no point at which the runtime will reach for "the next cell" and be told it has reached the end of the list. That is also why it's better to model our real computers with TM math, even though they obviously do not have literally infinite amounts of memory. As long as a software process runs along and is never told that it is out of memory when it asks for more, we get fairly TM-like behavior, or we get a crash if it does run out. By contrast, while the FSM model is in some sense more mathematically accurate, it is less useful for modeling real computers, since it is so weak. I think this formulation also better intuitively explains why we use infinity so often in our proofs; by saying "and there's always another one if you want it", we remove the case where we have to handle there not being another one. And that case can get quite hairy, as anyone who has watched their machine self-immolate after it discovers it is out of RAM can attest to. :) (It can also be every bit as mathematically tedious to deal with, too.) The further I got through grad school, the more I said "unbounded" rather than "infinite".

grannyg00se 13y ago
"The further I got through grad school, the more I said "unbounded" rather than "infinite"." I think there's a huge difference between simply saying "unbounded" compared to going through that detailed explanation you just gave. In the latter case, it's very clear what the difference is. But without the explanation I'd guess that people will think something like this: unbounded -> without bound -> infinite In other words, without the explanation "unbounded" becomes a synonym for "infinite".
- danbruc 13y ago
  Depending on the context unbounded and infinite may mean very different things, for example the surface of a sphere being unbounded but finite.
  - gohrt 13y ago
    A sphere is bounded but infinite* http://en.wikipedia.org/wiki/Compact_space http://en.wikipedia.org/wiki/Compact_space *Infnite cardinality of points, not infinite in measure.
  - jerf 13y ago
    That's why I didn't simply drop the word infinite. There are cases where it is appropriate. What is the cardinality of the natural numbers? Infinite... "unbounded" is definitely not right there. But when we use infinity in proofs, we are more often using it to mean "unbounded" rather than truly a "manifested infinity", to use a sloppy phrase; we're using it to get rid of the nasty edge case, not because we expect a real implementation of whatever the proof is proving to actually require infinite RAM. Also, by "we", I should clarify I mean discrete mathematicians and computer scientists, who are usually dealing in the discrete case. In the continuous case, infinities come up "for real" more often.
- gohrt 13y ago
  The relevant distinction isn't between "bounded" and "finite", but between the size of a container and the size of its elements. The difference between "bounded" and "infinite" is the difference between "measure" and "cardinality". That is , "bounded" refers to a notion of distance, while "finite" refers to a measure of count. There are bounded infinities (such as the set of all rational or numbers between 0 and 1), but there are no unbounded finities. A container that contains finite objects of all sizes must be an infinite/unbounded container.
- baddox 13y ago
  "Unbounded" means "any finite number, no matter how large." For many people, this might be what they think of when they hear "infinite," but in mathematics, "infinity" is an entirely different concept.
csense 13y ago
I once read an analogy that said to think of the "infinite tape" of a Turing machine as similar to how physicists think about infinite parallel plates, etc. The infinite case can be easier to treat theoretically, and also give key insights, that might not be attained in the finite case. Even though you have an understanding that any real system is finite, imagining an infinite system is a useful approximation. And as long as you're operating in a region that's not close to the edge, the edges don't make a difference to the outcome. Likewise, while real machines are really DFA's since they have a finite amount of memory, thinking of them as having infinite memory is a much better approximation. And as long as you don't "get close to the edges" by e.g. trying to allocate more memory than your machine has available, it works perfectly.

chriswarbo 13y ago

I don't think there's a specific name for this kind of Turing Machine, but it looks to me like it's primitive-recursive, similar to Hofstadter's BLooP ('bounded loop') language. It's basically the difference between for loops, which specify up-front how many times to loop, and while loops, which keep going until some dynamic condition is met. For loops are total, while loops are Turing complete. Note that these are the CompSci definitions of for and while; most languages with "for" syntax are actually implemening while loops. There are some interesting kinds of Turing Machine which use limited tapes, rather than limited transition tables. For example, a monotone Turing machine can have heads which only move one way. They're useful for modelling demand-driven input and output (one read-only, monotone input tape, one write-only, monotone outpu tape and one read-write non-monotone work tape). Other machines that I've seen in research are 'enumerable-output machines', which can only edit their previous output if it ends up lexicographically higher, and 'Generalised Turing Machines' which can edit their output as long as each bit takes a finite number of steps to 'stabilise'. These machines have been investigated by Jurgen Schmidhuber, among others.

gus_massa 13y ago
I agree. After reading in the article that: > The main argument against Turing completeness was that my implementation did not support unbounded recursion. I’m almost sure they are Primitive recursive function, but I didn’t have time to write the complete proof. http://en.wikipedia.org/wiki/Primitive_recursive_function#Limitations http://en.wikipedia.org/wiki/Primitive_recursive_function#Li...
- gus_massa 13y ago
  From a previous article of the same author: http://theorangeduck.com/page/c-preprocessor-turing-complete http://theorangeduck.com/page/c-preprocessor-turing-complete > This is a fairly clear distinction and a compelling argument. Clearly there are languages where you can effectively express unbounded recursion function() { function() } and the C preprocessor is not one of them. >* But there are a number of subtleties going on here. For example, if we consider the set of macros I created to be the "machinery", and the "language" to be the Brainfuck input to my system, then it is indeed Turing complete. That is - I have created machinery which can simulate Turing complete languages. Taking all the above definitions into account, consider how odd it is that Turing complete machinery can be expressed in a non Turing complete language.* And from the “Brainfuck interpreter written in the C preprocessor”: https://github.com/orangeduck/CPP_COMPLETE https://github.com/orangeduck/CPP_COMPLETE > Currently the maximum recursion depth is set to around 1000 and the data array size around 100. These can be easily extended but for now, as a general rule of thumb computations exceeding 1000 steps may not run. Here is the problem. We can consider the one-step-interpreter: it’s a function that has as arguments a program, the current instruction index and the whole memory state, and this function computes the next instruction index and the next whole memory state. This one-step-interpreter is primitive recursive. He put that function inside a bounded loop, which is also implementable as a primitive recursive function. So essentially he created an interpreter that runs a program for at most a fixed number of steps, where this number is an argument of the function (or worse, in this case a constant). Interpreter(Program, Memory, MaxSteps) is a recursive primitive function. To be Turing complete, he needs to write InterpreterForEverIfNecesary(Program, Memory). With a fixed MaXSteps value, it can’t compute all recursive primitive function.

lisper 13y ago

"What we are missing is the ability to re-enter old states." That's deadly. Any machine with a finite number of states that cannot re-enter a state it has previously been in must necessarily halt on all input. That makes it strictly less powerful than even an FSM.

caf 13y ago
It is worth noting that must necessarily halt on all input is quite a desirable property in a macro language evaluated at compile time.
- gus_massa 13y ago
  On the other hand, in Lisp/Scheme/... language family you have a Turing complete language for macro language, Lisp/Scheme/... respectively. In those languages, macros are powerful and must be used with care. The advantage is that complex macros are easy to write.
- lisper 13y ago
  That is arguable. All else being equal it might be true, but all else is not equal. The benefit of never having your compiler enter an infinite loop may not be worth the cost in terms of lost expressive power.
  - mtdewcmu 13y ago
    Has it been proven that the ability to write undecidable programs confers expressive power such that you can't have one without the other? It seems self-evident that running forever can't be useful, so you should be able to say WLOG that useful programs always halt. So the set of all useful programs is strictly smaller than the set of Turing machines. Is there a formal reason why Turing machines are desirable?
    - lisper 13y ago
      > Has it been proven that the ability to write undecidable programs confers expressive power such that you can't have one without the other? Yes. > It seems self-evident that running forever can't be useful Really? Do you not think that it might be useful for, say, an operating system to run forever?

sonnyOrullivan 13y ago

Wouldn't it simply be a linear bounded automaton (LBA)? I understand you can implement recursion via some tricks but only as many steps as you predefine (see e.g. https://stackoverflow.com/questions/7508475/is-c-preprocessor-metaprogramming-turing-complete https://stackoverflow.com/questions/7508475/is-c-preprocesso...) This reeks like an LBA to me.

roywiggins 13y ago
My first instinct is that you're right- at least, I don't think it can be any more powerful than an LBA: if there's a finite number of state transitions it can make, then it can only actually "get to" a certain distance along the tape, and you can just chop the tape at that point.
- lisper 13y ago
  Nope, a cpp-machine is strictly less powerful than an LBA, or even an FSA. An LBA (and an FSA) can enter an infinite loop. A cpp-machine can't.

NAFV_P 13y ago

A few months ago I got fed up with losing track of what I had written in C. So I knocked up some python scripts to write templates for me, it displays the date and time the file was created and the filename in a comment. This concept can be taken much further. CPP has been known to be abused by programmers as a general text processor, has anyone else started using another language to help them write C?

akjj 13y ago
C++ and Objective-C both began as preprocessors for C.
- NAFV_P 13y ago
  Wow, it's surprising what you can do with it.
  - tbirdz 13y ago
    Just to clarify a bit, C++ and Objective were not written in the C pre-processor, but rather implemented as their own pre-processor program, analogous to Qt's moc.
    - craigching 13y ago
      Yes like Cfront [1]. I used that back in the day, the pain of it caused me to rewrite all my C++ in C though :p Call me a coward! [1] -- http://en.wikipedia.org/wiki/Cfront http://en.wikipedia.org/wiki/Cfront
    - NAFV_P 13y ago
      > Just to clarify a bit, C++ and Objective were not written in the C pre-processor, but rather implemented as their own pre-processor program, analogous to Qt's moc. I bet these pre-processor programs were themselves written in C.
ChuckMcM 13y ago
You mean like $ SCCS %G% %M% %W% $ ?