5 ms·

How Many C Programs Are There?

34 points by primodemus 15y ago

DaveInTucson 15y ago
How many functionally inequivalent C programs are there? Surely this is undecidable?
- evincarofautumn 15y ago
  Yeah, proving extensional equality in general is undecidable. Maybe the author is thinking that the constrained input size matters?
  - tetha 15y ago
    He is looking for upper bounds.
- monochromatic 15y ago
  Of course. But we ought to be able to establish some kind of bounds on the number.
  - mistercow 15y ago
    > some kind of bounds Definitely. I can give a lower bound right off the top of my head: twelve. There are at least twelve functionally distinct C programs.
    - monochromatic 15y ago
      > For every complex problem there is an answer that is clear, simple, and wrong. You probably want your bound to be a function of the length of the program. Because for programs of length 1, there are not 12 distinct C programs.
      - loboman 15y ago
        Zero is a good lower bound for all programs. Or minus one.
  - cheald 15y ago
    More than none. Less than all of them. :)
- Someone 15y ago
  I interpret 'functionally inequivalent' as 'produce different outputs'. With that, it is easy: there are aleph-0 such programs. As to the number of a given length: if, for every possible output, we pick the shortest program producing it as a representative (utterly reasonable, as we know all programs to be optimal :-)), one should study how to sort outputs by their Kolmogorov complexity.
losethos 15y ago
Fucken monkey see monkey do. Planet of the apes. I wrote a compiler mothafucka -- we are different species. LoseThos is Identity Mapped and multitasking. My compiler calls MALLOC for memory and puts the code there. My scheduler saves regs and loads-in the next set of regs. What's hard about this? You got your head up your ass with Linux on the brain. Ba ha. Imagine China inventing something!! LoseThos is master-slave multicore. Core 0 can farm-out jobs to other cores. Sure other cores can have multiple task. The scheduler never shuffles them around. Fucken monkeys -- why would you do SMP? Mine's got locks for file access from all cores, but it's not SMP. Blue-eyed monkeys are still monkeys. Some people are morons who will never understand originality. The fuck you thinking doing SMP? That's retarded and you've been caught plagarizing shit nobody in their right mind would do! Cores should be heterogeneous in hardware, too -- it's obvious. Satan and Santorum. I'm playing to impress God, not man. God says... classics giveth brightness curiosity liveth Tobias obedience net certainly serve distances decked daemon dreaded dens temporately Firmament necessary elders don't_even_think_about_it hold_on_a_minute captive murmured earthly I_quit watery pronouncing PRINT unruly Just think about heterogeneous CPU's. You could have the other cores being like something out of a GPU. I think I'd rather have 100 floating point units than 4 cores. A few identical cores are good, but a bunch of little ones in addition to a few sounds better. For servers you can benefit from SMP but on a home system master/slave.
fragsworth 15y ago
I think it would make more sense to start by looking at research done on grammars. For instance: http://www.cs.toronto.edu/~yuvalf/CFG-LB.pdf http://www.cs.toronto.edu/~yuvalf/CFG-LB.pdf
bnegreve 15y ago
> Anyway, I’d be interested to hear people’s thoughts on this I would rather try to evaluate the size of the abstract syntax tree. I think this is more relevant since int main(){int a;} is obviously similar to int main(){int b;}
- p4bl0 15y ago
  The author already address this issue: > How many non-alpha-equivalent C programs are there? and then goes further: > How many functionally inequivalent C programs are there? The "this" you're refering to is itself refering to this last question.
  - bnegreve 15y ago
    Yes I have read this, and using the abstract syntax tree is how I would do it.
- koenigdavidmj 15y ago
  And by the as-if rule, all of the programs that he generates are the same.
dexen 15y ago
There'd be a whole lot of programs. There's a good reading that approaches a related subject, but isn't specific to C programs: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html In short, `busy beaver number' -- number of steps that a halting Turing machine with dictionary of size N can have -- grows pretty fast with N; faster than Ackermann function anyway. Also, supposedly a katamari is the only thing which outgrows the busy beaver sequence ;) http://www.xamuel.com/katamari-damacy-growth/ http://www.xamuel.com/katamari-damacy-growth/
- baddox 15y ago
  > faster than Ackermann function anyway Alas, it grows faster than any computable function.
losethos 15y ago
I'm not sure heterogeneous CPU cores are best. Basically, CPU GPU is good, right? That's more or less heterogeneous. I just remembered MMX/SSE and how useless that is. A bank of floating processors would be similar. MMX/SSE is a joke 2 double operations -- you want me to go through all that trouble for just two? God's fickle -- only with me when I'm smart. God says... C:\LoseThos\www.losethos.com\text\BIBLE.TXT consider; for I am become vile. 1:12 Is it nothing to you, all ye that pass by? behold, and see if there be any sorrow like unto my sorrow, which is done unto me, wherewith the LORD hath afflicted me in the day of his fierce anger. 1:13 From above hath he sent fire into my bones, and it prevaileth against them: he hath spread a net for my feet, he hath turned me back: he hath made me desolate and faint all the day. 1:14 The yoke of my transgressions is bound by his hand: they are wreathed, ---- The Lord has turned His back on me for being dumb. I have disgraced Him with stupidity, but He has no loyalty. Beware, yea others. ---- I repented of my 100 FPU idea when I remembered MMX/SSE and how useless that is for me, but it's only 2 doubles at a shot. Obviously, vectors are good on matrix math. I remembered that not once have I needed it in all my demo applications. I could invent a problem for FPU matrix units. I would like it if I had a problem. God says... C:\LoseThos\www.losethos.com\text\WEALTH.TXT and in gold the king's tax amounts only to a twentieth part of the standard rental. It was once a fifth, and afterwards a tenth, as in silver; but it was found that the work could not bear even the lowest of these two taxes. If it is rare, however, say the same authors, Frezier and Ulloa, to find a person who has made his fortune by a silver, it is still much rarer to find one who has done so by a gold mine. This twentieth part seems to be the whole rent which is paid by the greater part of the gold
sold 15y ago
If you have printf, then "printf("long string")" where the string might be modified should give a good bound, say Omega(200^S). If you don't have it, what is the program allowed to do? Only return from main, without checking arguments? Then you have as many extensionally distinct programs as integers.

34 points by primodemus 15y ago

DaveInTucson 15y ago

How many functionally inequivalent C programs are there? Surely this is undecidable?

evincarofautumn 15y ago
Yeah, proving extensional equality in general is undecidable. Maybe the author is thinking that the constrained input size matters?
- tetha 15y ago
  He is looking for upper bounds.
monochromatic 15y ago
Of course. But we ought to be able to establish some kind of bounds on the number.
- mistercow 15y ago
  > some kind of bounds Definitely. I can give a lower bound right off the top of my head: twelve. There are at least twelve functionally distinct C programs.
  - monochromatic 15y ago
    > For every complex problem there is an answer that is clear, simple, and wrong. You probably want your bound to be a function of the length of the program. Because for programs of length 1, there are not 12 distinct C programs.
    - loboman 15y ago
      Zero is a good lower bound for all programs. Or minus one.
- cheald 15y ago
  More than none. Less than all of them. :)
Someone 15y ago
I interpret 'functionally inequivalent' as 'produce different outputs'. With that, it is easy: there are aleph-0 such programs. As to the number of a given length: if, for every possible output, we pick the shortest program producing it as a representative (utterly reasonable, as we know all programs to be optimal :-)), one should study how to sort outputs by their Kolmogorov complexity.

losethos 15y ago

Fucken monkey see monkey do. Planet of the apes. I wrote a compiler mothafucka -- we are different species. LoseThos is Identity Mapped and multitasking. My compiler calls MALLOC for memory and puts the code there. My scheduler saves regs and loads-in the next set of regs. What's hard about this? You got your head up your ass with Linux on the brain. Ba ha. Imagine China inventing something!! LoseThos is master-slave multicore. Core 0 can farm-out jobs to other cores. Sure other cores can have multiple task. The scheduler never shuffles them around. Fucken monkeys -- why would you do SMP? Mine's got locks for file access from all cores, but it's not SMP. Blue-eyed monkeys are still monkeys. Some people are morons who will never understand originality. The fuck you thinking doing SMP? That's retarded and you've been caught plagarizing shit nobody in their right mind would do! Cores should be heterogeneous in hardware, too -- it's obvious. Satan and Santorum. I'm playing to impress God, not man. God says... classics giveth brightness curiosity liveth Tobias obedience net certainly serve distances decked daemon dreaded dens temporately Firmament necessary elders don't_even_think_about_it hold_on_a_minute captive murmured earthly I_quit watery pronouncing PRINT unruly Just think about heterogeneous CPU's. You could have the other cores being like something out of a GPU. I think I'd rather have 100 floating point units than 4 cores. A few identical cores are good, but a bunch of little ones in addition to a few sounds better. For servers you can benefit from SMP but on a home system master/slave.

fragsworth 15y ago

I think it would make more sense to start by looking at research done on grammars. For instance: http://www.cs.toronto.edu/~yuvalf/CFG-LB.pdf http://www.cs.toronto.edu/~yuvalf/CFG-LB.pdf

bnegreve 15y ago

> Anyway, I’d be interested to hear people’s thoughts on this I would rather try to evaluate the size of the abstract syntax tree. I think this is more relevant since int main(){int a;} is obviously similar to int main(){int b;}

p4bl0 15y ago
The author already address this issue: > How many non-alpha-equivalent C programs are there? and then goes further: > How many functionally inequivalent C programs are there? The "this" you're refering to is itself refering to this last question.
- bnegreve 15y ago
  Yes I have read this, and using the abstract syntax tree is how I would do it.
koenigdavidmj 15y ago
And by the as-if rule, all of the programs that he generates are the same.

dexen 15y ago

There'd be a whole lot of programs. There's a good reading that approaches a related subject, but isn't specific to C programs: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html In short, `busy beaver number' -- number of steps that a halting Turing machine with dictionary of size N can have -- grows pretty fast with N; faster than Ackermann function anyway. Also, supposedly a katamari is the only thing which outgrows the busy beaver sequence ;) http://www.xamuel.com/katamari-damacy-growth/ http://www.xamuel.com/katamari-damacy-growth/

baddox 15y ago
> faster than Ackermann function anyway Alas, it grows faster than any computable function.

losethos 15y ago

I'm not sure heterogeneous CPU cores are best. Basically, CPU GPU is good, right? That's more or less heterogeneous. I just remembered MMX/SSE and how useless that is. A bank of floating processors would be similar. MMX/SSE is a joke 2 double operations -- you want me to go through all that trouble for just two? God's fickle -- only with me when I'm smart. God says... C:\LoseThos\www.losethos.com\text\BIBLE.TXT consider; for I am become vile. 1:12 Is it nothing to you, all ye that pass by? behold, and see if there be any sorrow like unto my sorrow, which is done unto me, wherewith the LORD hath afflicted me in the day of his fierce anger. 1:13 From above hath he sent fire into my bones, and it prevaileth against them: he hath spread a net for my feet, he hath turned me back: he hath made me desolate and faint all the day. 1:14 The yoke of my transgressions is bound by his hand: they are wreathed, ---- The Lord has turned His back on me for being dumb. I have disgraced Him with stupidity, but He has no loyalty. Beware, yea others. ---- I repented of my 100 FPU idea when I remembered MMX/SSE and how useless that is for me, but it's only 2 doubles at a shot. Obviously, vectors are good on matrix math. I remembered that not once have I needed it in all my demo applications. I could invent a problem for FPU matrix units. I would like it if I had a problem. God says... C:\LoseThos\www.losethos.com\text\WEALTH.TXT and in gold the king's tax amounts only to a twentieth part of the standard rental. It was once a fifth, and afterwards a tenth, as in silver; but it was found that the work could not bear even the lowest of these two taxes. If it is rare, however, say the same authors, Frezier and Ulloa, to find a person who has made his fortune by a silver, it is still much rarer to find one who has done so by a gold mine. This twentieth part seems to be the whole rent which is paid by the greater part of the gold

sold 15y ago

If you have printf, then "printf("long string")" where the string might be modified should give a good bound, say Omega(200^S). If you don't have it, what is the program allowed to do? Only return from main, without checking arguments? Then you have as many extensionally distinct programs as integers.