2
\$\begingroup\$

What do people think about defining the encoding of a character in a given language as taking place in less than a byte?

For example, take Brainfuck. Brainfuck has exactly 8 possibilities per character, (+, -, [, ], >, <, ., ,), so each character can be easily encoded into 3 bits. Given that, would it be valid to count the best Brainfuck Hello World program, here, which is 78 characters, as 78 * 3 = 234 bits = 29.25 bytes?

This already seems to be accepted practice for at least one language, namely Binary Lambda Calculus, and there hasn't been much if any pushback over its use.

Of course, this is also applicable to ASCII-only languages (e.g. most of them), where for almost all programs, characters can be encoded in 7 bits.

I personally think that defining character encodings in bits rather than bytes should be fine. What are other opinions?

| |
\$\endgroup\$
  • 7
    \$\begingroup\$ Too tired to write a full answer now, but my opinion is that you can only claim a byte/bit count if there is an interpreter that handles code of this size. Unless a language has an interpreter for a platform where you can store fractional bytes, you can't claim a fractional byte count. \$\endgroup\$ – Dennis Jul 22 '16 at 5:23
  • \$\begingroup\$ Yeah, I agree with Dennis. Using that as a standard would also go well with our standard of "languages are defined by their implementation". \$\endgroup\$ – James Jul 22 '16 at 5:40
  • 2
    \$\begingroup\$ I agree with Dennis. I think this would open up more problems than it solves. People would start counting programs that use only printable ASCII with 6.something bits per character even though those languages could potentially contain other characters inside string literals for example. The definition of "your byte count is the physical size of the file you feed to your interpreter/compiler" is the simplest, most objective and last surprising one. If you're bothered that Brainfuck requires 8 bits per character, use Sesos or write your own compressed BF-derivative. \$\endgroup\$ – Martin Ender Jul 22 '16 at 5:40
  • \$\begingroup\$ @Dennis If that's the case, I'd be happy to write an interpreter for Pyth that interprets the source code as packed 7 bit ascii. Sure, it won't get 6.125 bytes for a 7 character program, but would it get 7 bytes for an 8 character program (that is packed into 7 bytes)? \$\endgroup\$ – isaacg Jul 22 '16 at 5:43
  • 3
    \$\begingroup\$ One more point that didn't fit into that comment: using sub-byte encodings essentially gives a fixed factor on your score. So it only matters for comparison between various languages, it won't affect ordering within one language at all, and since languages still won't all be equally competitive as a result, I'm not sure there's a point to it. \$\endgroup\$ – Martin Ender Jul 22 '16 at 5:43
  • 1
    \$\begingroup\$ @MartinEnder I think a lot of people do cross-language comparison, especially among golfing languages. You can see this in upvote patterns, where a 9 byte answer in one language will typically get many more upvotes than a 10 byte answer in another, if they're both golfing languages. \$\endgroup\$ – isaacg Jul 22 '16 at 5:45
  • 1
    \$\begingroup\$ @isaacg Cross-language comparison between golfing languages is certainly a thing (and makes a lot more sense than comparing non-golfing languages). If you pack Pyth code into 7 bits for each character, the score will be the actual size of the resulting binary file, and nobody can make a case against it. A 7 byte file is a 7 byte file. This would have to be the default option for the interpreter though (or get detected automatically), since you'd need to add bytes for a command-line switch otherwise. \$\endgroup\$ – Dennis Jul 22 '16 at 19:16
  • \$\begingroup\$ @isaacg Cross-language comparison between golfing languages is certainly a thing (and makes a lot more sense than comparing non-golfing languages). If you pack Pyth code into 7 bits for each character, the score will be the actual size of the resulting binary file, and nobody can make a case against it. A 7 byte file is a 7 byte file. This would have to be the default option for the interpreter though (or get detected automatically), since you'd need to add bytes for a command-line switch otherwise. \$\endgroup\$ – Dennis Jul 22 '16 at 19:16
  • \$\begingroup\$ Maybe just invent a "platform where you can store fractional bytes"? There are existing interpreters using bits after the program as input, so the program is in fractional bytes and the trailing bits are in the convenient input format for that language. But that's quite inconvenient if we require everyone doing this. Better we just define the code with fractional bytes as a function. If it can be merged with other functions together in the obvious way, then it's better to allow it to only count the part it contributes. \$\endgroup\$ – jimmy23013 Jul 30 '16 at 11:22
  • \$\begingroup\$ Not using custom scoring criteria is mostly for convenience's sake, and to avoid inviting useless arguments. It's quite different if the language spec/implementation defined it in this way. \$\endgroup\$ – jimmy23013 Jul 30 '16 at 11:24

Browse other questions tagged .