# Can String be a subtype of Character in a programming language?

Could a programming language be designed so that there is an inheritance relationship between string and character (both of which are native types), such that the inheritance alone resolves the use of an arbitrary binary operator between the two types: <string> @ <character>; coercion and overloading cannot be used. My intuition is that string would be a subtype of character because a string may be composed of characters, and all basic methods defined for a character work with a string. As a subtype, string could have very specific functionaity such as a length method or attribute. On the other hand, I can see how it might make sense that string is the supertype and character is the subtype. Namely, a character could be thought of as a string of length 1. Which interpretation is correct, or at least which interpretation is more sound?

• Note that LSP easily shows that a character (or any fixed-length string) is not a subtype of a mutable arbitrary-length string, because they can't support any operations that change the string length. But immutable strings don't support those problematic operations. On the other hand, how do you implement the character operations for strings such that they succeed on a string of length zero? – Ben Voigt Apr 17 '17 at 21:53
• @BenVoigt yes that is what I am confused about. This is actually a question in the practice section in my textbook. My professor told me the answer should be clear... If inheritance is strictly defined as an is a relationship, then I do not see how a string could be a character – tpm900 Apr 18 '17 at 23:35

Character and String are conceptually very, very different. Google for "inheritance vs. composition" - you seem to think that Character and String should be connected via inheritance, but in reality a String is composed of 0, 1 or more Characters.

And to throw a spanner in the works: Strings are often large, and String operations must be very efficient. Therefore, even though conceptually a String is an array of Characters, it will not be implemented as a sequence of objects, but as an array of somehow simpler elements, for example UTF-16 codes.

And then you can think about how to implement Character efficiently if you use Unicode and an emoji character can easily be made up of a dozen Unicode code points - but the huge majority of Characters doesn't need that complexity, and you want an implementation that is space efficient and fast.

• Thank you for the great answer, this is actually from a practice question in my textbook. When I asked my professor, he told me the answer should be clear if string and character are clearly defined. However, an inheritance should be an is a relationship, so clearly a string cannot be a character, but a string defines additional methods not defined for a character. – tpm900 Apr 18 '17 at 23:34
1. Subtyping is conceptually very different from inheritance.
Subtyping refers to shared interfaces; $\tau$ is a subtype of $\tau'$, i.e. $\tau <: \tau'$, then all expressions of type $\tau$ could be used when one of type $\tau'$ is expected. Inheritance refers to the reuse of implementation; if class A inherits class B then A reuses the implementation of B. A doesn't have to be a subtype of B. For example, a "Stack" class might inherit from and reuse the implementation of a "List" class, but it "Stack" can't be a subtype of "List".
For more on subtyping and inheritance, see, e.g., Turbak, Gifford and Sheldon, Design Concepts in Programming Languages, pp. 701-25.

2. "Character" can't be a subtype of "String" if the implementation is to be useful
Sure you could design a language with "Character" as the subtype of "String". However, how useful would this design be? It is easy to find a function that you couldn't implement under this design, e.g. convert a character to a hex code based on its encoding; a "String" wouldn't be valid input to this function.
But you are be right the other way. A "Character" could be thought of as a "String" of length 1; but that would imply $\mathtt{Character} <: \mathtt{String}$, not the other way. This is probably not the best programming language design decision you could make, but it'd work.