8
\$\begingroup\$

(See also this question, which is similar, but talks about the situation where the language is normally stored on disk with one command per byte.)

This question originally came up in connection with 7, but might be relevant to other languages.

In 7, each command is only three bits long (it only has 8 commands which can be specified in source files). It accepts multiple input formats; one uses one byte per command (for ease of editing and testing), one reads the sequence of bits formed by the input file and interprets every three bits as a command. Because most computer systems don't allow a file to contain a fractional number of bytes, any amount of "trailing whitespace" (in this case, 1 bits) can be placed at the end of a file, and is ignored by the interpreter's file reading routines.

The information content of the language is obviously 3 bits (i.e. ⅜ of a byte) per command. Dennis has suggested that the length of a program should be rounded up to a whole number of bytes, because that's how file storage works. Alternatively, you could the length down by removing trailing 1 bits (as the program considers them not to exist). How should this be counted?

As a final question to consider: if the interpreter was changed to accept programs over an RS-232 interface (which is physically capable of sending an arbitrary number of bits), would that change the scoring?

\$\endgroup\$
3
  • \$\begingroup\$ Yours is essentially the same question as Sub-byte character encodings which was closed as a duplicate of them question you mention in the first paragraph. \$\endgroup\$
    – Dennis Mod
    Commented Dec 6, 2016 at 20:22
  • \$\begingroup\$ It differs in that that question was asking about languages which don't "naturally" have an encoding down to a few bits. In other news, that question could do with some good answers too; its answers are mostly negatively voted or vague. \$\endgroup\$
    – user62131
    Commented Dec 6, 2016 at 20:24
  • 4
    \$\begingroup\$ My humble opinion is that answers can have fractional byte counts iff the program runs correctly no matter what the last few bits of the last byte are. For example, a ⅜-byte program is valid if it runs correctly for every possible combination of the last 5 bits. \$\endgroup\$
    – ETHproductions
    Commented Dec 7, 2016 at 1:27

1 Answer 1

Reset to default
15
\$\begingroup\$

The answer's score is the source code's size

Unless you can store your program somehow by using only 3 bits, you cannot claim a size of ⅜ bytes. That's the only rule that makes sense in the long run, since claiming scores that cannot actually be achieved by any implementation will inevitably lead to endless discussion about the scores of post X and language Y.

The analogy with trailing whitespace for padding bits is a good one, but I don't agree with your conclusion. If a program has to be stored with a trailing newline, that trailing newline contributes to the byte count. If it doesn't require the newline, remove it so it won't count towards the score. However, you cannot remove your padding bits in the Perl implementation of 7.

\$\endgroup\$
12
  • \$\begingroup\$ I haven't fully grasped the RS-232 scenario yet. For now, I won't answer that part. \$\endgroup\$
    – Dennis Mod
    Commented Dec 6, 2016 at 20:37
  • \$\begingroup\$ Hmm, by this argument, aren't all the programs that use more memory than any practical computer has invalid because no interpreter can run them? That seems to be an exception to the "languages are defined by their implementation" rule that's in use at the moment. \$\endgroup\$
    – user62131
    Commented Dec 6, 2016 at 23:04
  • \$\begingroup\$ The reason we like to define languages by their implementations isn't only because we can run the code to test it, but to have an definitive interpretation of the specification in a programming language. Based solely on a specification in a natural language, judging whether some code would work or not can be difficult/debatable (poorly written spec) or downright impossible (explicitly implementation-defined). \$\endgroup\$
    – Dennis Mod
    Commented Dec 6, 2016 at 23:18
  • \$\begingroup\$ But you can't determine from the implementation whether the code would work or not either, as the implementation would print an out of memory error when reading it. An implementation is useful in that it sets out the language spec in a more rigorous language than English, but you still have to interpret that specification to "see what would happen" on a hypothetical computer that had a large amount of memory. So presumably you could also do the same for a computer with a different number of bits per byte. (In case it matters, I've changed the interpreter to detect bits-per-byte at runtime.) \$\endgroup\$
    – user62131
    Commented Dec 6, 2016 at 23:46
  • \$\begingroup\$ Or in other words: the way to count bytes is wc \$\endgroup\$
    – Peter Taylor
    Commented Dec 7, 2016 at 21:31
  • 3
    \$\begingroup\$ I feel like this argument can be extended to say that the size of a program is the number of bytes on the disk allocated to the source file. I believe this is the number of bytes rounded up to a multiple of the computer's cluster size (meaning that if your computer has a cluster size of 4096, all non-empty programs with 4096 bytes or less actually use 4096 bytes). I don't know very much about computers interally, though, so feel free to correct me... \$\endgroup\$
    – ETHproductions
    Commented Dec 9, 2016 at 18:50
  • 1
    \$\begingroup\$ @ETHproductions It's not so much about the size the file occupies on the disk (cluster size is arbitrary, there's some overhead too, and there are compressed file systems that could actually lower your byte count), but about the bytes the program reads from the disk. \$\endgroup\$
    – Dennis Mod
    Commented Dec 9, 2016 at 20:14
  • \$\begingroup\$ What about functions (or lambdas)? Can they have a fractional byte count? In Java, a function is only a portion of a runnable source file. There has to have a boiler plate in order for that function to execute. This padding bits with zeroes seems similar to me. \$\endgroup\$
    – NonlinearFruit
    Commented Mar 14, 2017 at 17:09
  • \$\begingroup\$ @Dennis CP-1610 programs can be physically stored in 10-bit ROM. Would it be a valid exception to this rule? (Example 1, example 2 -- both with comments about that.) \$\endgroup\$
    – Arnauld
    Commented Apr 12, 2019 at 11:07
  • 2
    \$\begingroup\$ @Arnauld It's not really an exception. If you can actually store the program in 60 bits in some implementation, that's your source code's size and your score. \$\endgroup\$
    – Dennis Mod
    Commented Apr 12, 2019 at 13:44
  • \$\begingroup\$ Whether we can store or can't store individual bits seems to depend on the file system. If Microsoft comes out with NTBFS (New Technology Bit File System), maybe it's possible. \$\endgroup\$
    – Thomas Weller
    Commented Oct 13, 2022 at 16:52
  • \$\begingroup\$ "can store your program somehow" - in a zip file, the byte count might be lower than original ASCII-like source code. I don't think that's how we count the bytes either. \$\endgroup\$
    – Thomas Weller
    Commented Oct 13, 2022 at 16:53