1) Memory-safe (can't touch memory that you don't own)
2) Opaque (standard library can change the implementation later)
3) Immutable (can be passed around like values)
4) Unicode (no fixed width chars, no default conversion to bytes)
I don't know any good reason to deviate from these rules. Even systems languages would do well to follow them, IMO.
1) Memory-safe costs a lot and gives me little. If I know I'm not going to touch memory incorrectly I should be able to take advantage of that.
2) Knowing the cost of operations is essential to do any kind of performant programming in a reasonable amount of time; e.g. whether `length(x)` is O(N) or O(1). The operations specified is hugely important.
3) When I've got a 300GB log to update, an in-place algorithm will be better for everybody. Microcontrollers don't want to waste space with extra copies either, and a better algorithm wins.
4) I'm not sure having an opinion about Unicode in the language is ideal: You can either store an array of bytes, or you can store an array of code points, or you could store a list of UTF8 "characters", and I see value in all of these interpretations (comparison/copying, rendering, transcoding). I'd prefer flexibility, and the language not switching them around on me behind my back (see #2)
2) I agree that time and space complexity should be part of the contract.
3) I agree that escape hatches are needed, but they shouldn't be the default. Most code isn't performance sensitive, but all code is bug sensitive.
4) The best internal representation is probably UTF-8, but I don't feel strongly about that. What matters is that the available string operations are specified in terms of Unicode, not bytes.
I grew up in Russia and I remember very well the "fun" of programming with Cyrillic strings in a mixture of Win-1251, KOI8-R, and Unicode. Working with strings as untagged bytes is a disaster everywhere except English speaking countries.
An array of bytes is a storage medium. If you don't need the number of utf-8 characters (and given things like combining characters and invisible spaces, it's rare that's what I actually need) and just need to print and compare, byte-strings are efficient and acceptable. The text remains utf-8 encoded, but `length` is `O(1)` or a simple scan, and `substr` (or similar) are `O(1)`+the cost of allocating.
However if I need to recode things, an array of 32-bit (or 64-bit hah) ints is sometimes better. If the language has a real iterator, UTF-8 might still be okay, but then you are still using a bytestring anyway.
Lastly, if the "string" actually knows its character set, then using things besides UTF-8 might be good because it saves a lot of space. Maybe. I'm not really convinced because the tag for the character set (as you rightly think necessary) takes up space too. Dealing with these kinds of "strings" is really complicated, so I'd agree that anyone who would jump into complexity without some real justification is, as you say, a bozo.
I think a lot of trouble showed up when people thought "string" meant "text", and new programmers learned (in a 7-bit world) how to make programs this way. And then unicode.
I try to be specific and say "array of bytes" (or sometimes "bytestring") if I mean something that's accessed a byte-at-a-time, but since most text is just copied; sent verbatim to the screen, to the HTTP response, etc, I worry about the `O(N)` access and counting algorithms showing up in languages.
Java recently (JEP 254) moved to internal flag for Strings (ISO-8859-1 or UTF16) as most memory was used by strings without any special characters. It was decided that additional complexity was worth it. I guess that getting rid of UTF-16 would be even better as it is the worst Unicode encoding.
1) Memory buffer errors cost a lot. Kernel panic or a frozen device after overwriting its whole memory. Having some low cost safety would be very much welcome. One of the biggest reasons I'm interested in Rust.
2) Well, I guess you can peek at the implementation, no? Strlen doesn't give you any guarantees either -- different implementations over an order of magnitude in performance.
3) Having a 300GB log to update, what happens when your update process step 2 out of 3 fails? In-place updates are risky on shared or persistent data. And this is a low frequency corner case anyways. Most strings don't need to be mutated. So it's reasonable to default to that.
4) Array of bytes is usually good enough. When it's text, it encoding should just always be UTF-8 except when not practical for some external reason.
I think about programming a lot.
I don't do much programming since my programs usually work correctly the first time, but when I do I write fast web servers and operating systems and text editors and language bindings and compilers and interpreters and compressors/decompressors and image editing tools, backup tools, system administration tools, reverse engineering network protocols, reverse engineering file formats, invoice generation tools, billing and accounting packages, mobile apps, high volume mail servers, mp4 decoders, 1wire (dallas) drivers, ad servers, ad players, web applications like email clients and web stores, windows device drivers, linux device drivers, and other things that I can't remember right now.
I have observed that the bugs I tend to make have more to do with my failing memory (i.e. what I can remember), than overflowing buffers that I allocated. Maybe memory buffer errors happen to other programmers often enough that it's worth worrying about for other people, but I'd argue this says more about those other programmers, and I propose that the techniques I use to avoid making those mistakes are more valuable than memory protection since it clearly allows me to have my cake and eat it too.
I've observed a great deal of performance can be gained by controlling how my structure is laid out in memory, but in order to do that, the compiler needs to trust me.
Maybe.
Some languages are experimenting with algebraic types and what they're doing might be a good-enough middle ground such that they can actually get zero-cost buffer protection, but I haven't played with them much to know for certain. I'm willing to be convinced, but I haven't yet, so I continue to maintain that enforced memory protection is not ideal.
Re 2) I think the original point is that the implementation should be free to change it however (and whenever) they like. That's why they wanted opaque strings, such that you access them from the interface itself.
Re 3) It depends. If it fails, then we've lost however long it takes to scan 300GB (a few minutes), but just because we copied it once from the disk, doesn't mean we need to copy it again and again: That turns minutes into hours. I agree that most strings don't need to be mutated, and that it's reasonable to default to it, however order-of-magnitude performance gains are worth spending a little time thinking about, and they often require mutating-in-place.
Traversing a tree is another good example, and the Schorr-Deutsch-Waite link-inversion algorithm (Knuth, TAOCP vol.1 § 2.3.5) is essential for constrained-memory devices when you need a tree-walker. Sometimes I need to mutate, so I think enforcing immutability is simply not valuable.
I didn't want to invoke any contest, but to remind C is used a lot in those contexts and zero termination seems to be one of the bug magnets. A very common source for security vulnerabilities as well, pretty large portion of them are related to string processing.
> Maybe memory buffer errors happen to other programmers often enough that it's worth worrying about for other people
Yup. Maybe a large part of how I think of this to protect the other people. It's not rare someone messes up on an embedded system and writes a bit somewhere else in memory. Often it won't crash, but the bugs you get take ages to hunt down.
There's just no way around it. I do want to delegate things to other people. Defensive coding tends to catch and prevent a lot of mistakes at that point. Many of them have pretty cowboy attitudes towards details such as parameter validation or error checking. Some of them will need to maintain it in the distant future.
> I've observed a great deal of performance can be gained by controlling how my structure is laid out in memory, but in order to do that, the compiler needs to trust me.
Yeah, performance is often about cache, locality of reference. Pointer chasing and other random access destroys performance. Applying SIMD without penalties requires at least 16 byte alignment. In 2016, 64 byte align is even better. SIMDs are getting pretty wide.
Re 3)...
I still think that 300GB string example is esoteric, even off topic. You're not going to put 300GB string in any standard string abstraction. There are probably a lot of other worries, such as running out of disk space, undetected data corruption on disk (happens pretty often), failure in the middle of the modification process, etc.
> Sometimes I need to mutate, so I think enforcing immutability is simply not valuable.
I don't think anyone wanted to enforce immutability. Just to have it default.
I understand. I think the gross majority of this comes from the C standard library though, and not from the C language.
qmail for example had no buffer overflow problems -- the first security vulnerabilities found 10 years after release wouldn't affect any system that qmail was developed to run on simply because nobody gave their mail server 4GB of ram! Surely the author should have predicted this problem, but it demonstrates methodology can protect against this issue.
KDB takes an interesting approach of reference counting in all operators. Operators can then be optimised for situations where one argument (or both) have a reference-count of exactly one. This means writing C code with KDB's memory management library can make things very simple.
Antirez also has an interesting string library that uses a combination of length+null-termination specifically for the purpose of finding bugs.
> There's just no way around it. I do want to delegate things to other people. Defensive coding tends to catch and prevent a lot of mistakes at that point. Many of them have pretty cowboy attitudes towards details such as parameter validation or error checking. Some of them will need to maintain it in the distant future.
I understand what you're saying, but I think technique can help a lot more than we think: Most of the software engineering industry wants to move to smarter and better tooling, and I'm just proposing we upgrade our brains some too.
I don't have all the answers yet.
> You're not going to put 300GB string in any standard string abstraction.
In KDB this is actually pretty common, but it doesn't have a "standard string abstraction" because while it meaningfully supports byte-arrays that are in the 300GB range, the string-atoms (symbols) which are used similar to strings in python et al, never approach 1MB let alone 300GB.
However in C I just did mmap() and updated the file. It took about 15 minutes to write and debug, and a few minutes to run on the server.
> I don't think anyone wanted to enforce immutability. Just to have it default.
I don't know. I parsed I don't know any good reason to deviate from these rules. as "enforce". I might be wrong, you'd have to ask "cousin_it" what he/she meant at the time. I know at least later they either were convinced, or clarified[1] this position.
However what I meant was that I don't want to enforce those rules because I can think of an exception for each, and they understood that. Sorry I was unclear though.
Wut? Memory safety costs very little and gives you a lot in terms of buffer over flow vuls, remote code execution, use after frees. Running a single in range check costs 1-5 processor cycles which will be branch predicted out of existence.
You may be that legendary programmer who writes code "without bugs" and everything works correctly on the first run. I don't doubt a handful of "real programmers" like that exist. But most of us make mistakes, and we want the compiler to protect us. Just look at the endless stream of memory-related vulnerabilities at CERT. Nearly all of them could have been prevented in a memory-safe language.
2) That is a non-issue. All serious standard libraries define operation complexity at the Big O granularity. Sometimes they go even further and the spec (especially in C++'s case) gurantees some implementation details.
Anyway, if you're not happy with the proper characteristic of a standard data structure for a certain use, there's nothing preventing you from creating your own data structure with your preferred behavior pattern. You can even use an 'unsafe' override - at least you'd isolate unsafety to a very small and manageable part of the code that way.
3) Again, nothing prevents you from optimizing for special cases. But that are many more programs (e.g. parsers) that deal with short and repetetive strings which can benefit from an implementation that passes them as value-types on the stack (this is essentially which most C++ implementations do).
4. I'm all for a default unicode string type and a separate "raw bytes" type. But the you should either store the string as unicode codepoints (UTF-32) or as UTF-8. UTF-16 is pure evil, since then people tend to assume UTF-16 elements are codepoints and surrogates break spectacularly.
Most of the bugs I create seem to have to do with my limited memory: I forget things when I scroll, or (more often) I misremember things. These bugs are still very embarrassing, but are something I'm working on by scrolling less.
Re 2) I agree it should be a non-issue, but the parent wanted to make the implementation fully opaque which hides operation complexity.
Re 3, 4) Agreed completely. I think these are easier to get with increased flexibility, not with stronger harnesses though.
> I don't know any good reason to deviate from these rules. Even systems languages would do well to follow them, IMO.
Systems-languages are used for things like OS kernels and god knows what where other equally important rules apply:
1. being able to manipulate things directly, in place, without having to allocate additional memory (i.e. creating a new copy)
2. efficiency may be more crucial than type-system guaranteed safety.
Not saying I disagree with your general position, I'm just open to the fact that there's always valid exceptions to any rules.
But, importantly, they don't do it by default as C does.
Not saying it doesn't happen, only that it is rarely needed.
Usually when you can't allocate memory (like IRQ handler), you don't do string processing either.
1) No protection exists there.
2) Abstraction costs too much.
3) Store it in Flash.
4) Be happy your characters may even use the 8th bit.