22

I was wondering about the following questions:

  1. What does it mean "some language is a subset/superset of another"? Can it be defined in mathematics? Is it related to the subset/superset concept in elementary set theory?

  2. Are almost all existing languages implemented/written in some small number of low-level languages? For example, are most languages written in C? Is C++ written in C?

    Is there some relation between the implementation relation and the concept of subset/superset of languages?

  3. In terms of language features, some languages have more than some other. In some cases, some has all the features of some other, for example, does C++ have all the features of C?

    Is there some relation between the subset/superset relation in terms of the set of features and the subset/superset relation between languages?

  4. Are there other aspects that characterize relation between languages?

Thanks and regards!

Tim
  • 1
  • 141
  • 372
  • 590
  • 2
    C++ is a language, it isn't written in anything (except English), as is C. – Rafe Kettler Mar 25 '11 at 23:33
  • 1
    @Rafe: Thanks! is Matlab implemented in C? How about Java, Python, R, D, ...? – Tim Mar 25 '11 at 23:40
  • 1
    That's a big question. I hope some of those academic types take some time responding. :) – Teekin Mar 25 '11 at 23:43
  • 1
    It depends on what you meant by "Is C++ written in C?" C++ itself is a language, it's not written in anything. A C++ compiler can be written in any language. – CanSpice Mar 25 '11 at 23:43
  • 2
    Mind if you explain why such question is off topic? Do you know where I can ask such questions? Thanks! Added: I guess cstheory.SE will not welcome such rookie questions. – Tim Mar 25 '11 at 23:49

4 Answers4

21

What does it mean "some language is a subset/superset of another"?

Syntactically a language A is a subset of a language B if every program that is valid in language A is also valid in language B. Semantically it is a subset if it is a syntactic subset and each valid A program also exhibits the same behavior in language B.

Can it be defined in mathematics? Is it related to the subset/superset concept in elementary set theory?

Syntactic subset: If P_A is the set of all valid programs in language A and P_B is the set of all valid programs in language B, then language A is a syntactic subset of language B exactly if P_A is a subset of P_B.

Semantic subset: Let A(p) be a function which describes the behavior of program p in language A, and B(p) describe the behavior of program p in language B. A is a subset of B if and only if for all p for which A(p) is defined, B(p) is also defined and A(p) = B(p).

Are almost all existing languages implemented/written in some small number of low-level languages?

This depends on your definition of "almost all" of course, but I'm inclined to say no. Many compilers and interpreters are written in C and C++ (simply because a lot of software in general is implemented in C and C++), but by far not all.

For example, are most languages written in C? Is C++ written in C?

As has been pointed out in comments already, C++ is a language not a piece of software. g++ which is the GNU C++ compiler is written in C, but there are also C++ compilers which are written in different languages (probably).

In terms of language features, some languages have more than some other. In some cases, some has all the features of some other, for example, does C++ have all the features of C?

Yes (unless you count simplicity as a feature).

Is there some relation between the subset/superset relation in terms of the set of features and the subset/superset relation between languages?

If a language is a superset of another language, the set of that language's features will also have to be a superset of the other language's features (again unless you count simplicity or things like "the language does not allow X" as a feature).

This is not applicable in the other direction however (i.e. just because A's features are a superset of B's features, A does not have to be a superset of B).

sepp2k
  • 363,768
  • 54
  • 674
  • 675
  • 1
    Thanks! The definition of subset in semantics is very impressive. – Tim Mar 26 '11 at 00:26
  • 1
    I was wondering if the subset/superset relation and the “higher/lower level“ relation between programming languages are related somehow? How is the latter defined actually? Thanks！ – Tim Mar 26 '11 at 00:57
  • 1
    "How is the latter defined actually?" Very vaguely. Conceptually a language is higher level than some other language if it is further removed from the hardwarei, i.e. it offers more abstractions. However there is no precise definition to measure the "height" of a language. There isn't much of a relationship between the height of a language and the sub/superset relationship. – sepp2k Mar 26 '11 at 01:03
  • 2
    your definition of semantic subset differs from mine, since mine tries to take account of languages which leave some freedom to the implementation, so a program can have more than one possible output. Is mine wrong, or is it just that yours doesn't try to account for that? For example, if you were to modify the C language definition to say that signed integer types *must* be 2's complement, I would say that the resulting language is a superset of C. Under your definition, if `A(p)` is "either X, Y or Z is output", and `B(p)` is "X is output", then does `A(p)==B(p)`? – Steve Jessop Mar 26 '11 at 13:43
  • 1
    @Steve: I actually just didn't consider that case. My first thought was that if the behavior of `p` could be one of multiple options, `A(p)` is just undefined. However that would make a language which changes the behavior of `p` from "either X or Y" to "Z" also a superset of A, so it's probably not a perfect definition. – sepp2k Mar 26 '11 at 15:31
  • Do you have any examples of languages which are a superset of another language? – Oliver Nybroe Sep 27 '19 at 18:54
  • @OliverNybroe Languages that are defined in terms of a core language plus desugaring are often a superset of their core language. Similarly with languages that are defined "in stages", each stage tends to be a superset of the previous stage. For example System F is a superset of the simply typed lambda calculus. On the less academic side, Objective C is a superset of C (unlike C++ it doesn't introduce any additional alphanumeric keywords that could conflict with identifiers nor does it disallow anything that was legal in C such as implicitly casting void pointers). – sepp2k Oct 03 '19 at 13:42
5

I wanted to pick up this:

Are almost all existing languages implemented/written in some small number of low-level languages? For example, are most languages written in C? Is C++ written in C?

As far as I know, in practice almost all languages that originated after C are written in C, due to C's overwhelming popularity during a certain period in time- until they are ready to implement their own compilers. Most languages that compile to native code implement themselves- that is, modern C++ compilers are written in C++. This is achieved by compiling the new compiler with a previous version of the compiler that is known to be good- the LKG or "Last Known Good" compiler. I know for a fact that the Visual C++ compiler is done this way, and I recall that there are Haskell IDEs which are also done like this and even PROLOG. The original C++ compiler was written in C- but since C++ became a general-purpose powerful language in it's own right, people wrote C++ compilers in it.

Of course, this process is impossible for languages which do not compile to native code, as they must always have some underlying interpreter or virtual machine to execute their code which cannot be written in that language, making it impossible to invalidate native languages with managed or interpreted languages.

Is there some relation between the implementation relation and the concept of subset/superset of languages?

Yes, there is. If you're implementing C#, why ditch the many years of good experience of C++ of making polymorphic function calls fast? The easiest thing to do would be to just fall back on that implementation- and it's my understanding that in C# running on .NET framework, that this is indeed what happens- they use an implementation basically taken straight from C++. If you're implementing a language feature that already exists in a certain language, you're losing out on experience and innovation if you roll a new implementation from scratch. Of course, this is different if those implementations are proprietary or something, but in general.

Are there other aspects that characterize relation between languages?

Yes, there are. The most obvious one is syntactic- consider the syntactic relations between C, C++, C#, and Java, even though Java and C# are clearly not supersets of C. Then consider the approach to major issues in software development. For example, Java and C# are both statically typed, garbage collected, virtual-machine based languages. Then you could consider design mistakes. In my opinion, design mistakes is one of the biggest hints that two languages are much more closely related than they really should be. Here, you can consider Java and C# again. Covariant arrays are broken. A Giraffe[] is not an Animal[], but both Java and C# allow the conversion. This is a clear design mistake, yet both languages have it, which is a sign that they are much too closely related.

Of course, C++ is in a bit of a unique position here, I don't know of any languages that directly succeeds another language quite like that, and C/C++ are the closest thing you'll ever find to language superset. The C++ Standard committee is still Standardising features in C++ purely to keep compatibility with C99.

Puppy
  • 144,682
  • 38
  • 256
  • 465
  • Thanks! Hope you don't mind, there are some questions (1) In"as they must always have some underlying interpreter or virtual machine to execute their code which cannot be written in that language", does it mean that "interpreter or virtual machine cannot be written in that language"? (2) what does "to invalidate native languages with managed or interpreted languages” mean? (3) Was the original version of C implemented in assmeply? Thanks! – Tim Mar 26 '11 at 08:01
  • @Tim - it means that, as much of the low level parts of Sun's Java VM is actually written in C++, it would be hard for Java to fulfill the claim of replacing C++ everywhere. (3) The early C compilers were actually written in C, possibly with some support from it's predecessor the B language. :-) You don't need the full langauage to start a simple compiler. Some of that history is told by Dennis Richie [right here](http://cm.bell-labs.com/cm/cs/who/dmr/primevalC.html). – Bo Persson Mar 26 '11 at 09:39
3

There is a strict definition for formal languages - a language L1 is a subset of language L2 if and only if every well-formed formula of L1 is a well-formed formula of L2.

In the case of programming languages a "well-formed formula" means a syntactically valid program, and you may or may not want your definition of "subset" to say not only that a valid program of L1 is also a valid program of L2, but also that it has the same semantics in L2 as in L1. Since C and C++ both have a semantic notion of undefined behavior, you would also then say that for L1 to be a subset of L2, it is only necessary that every syntactically valid program with defined behavior is valid in L2 with the same defined behavior - it's not required that every program with UB in L1 also has UB in L2. Formal languages don't define semantics, just grammar, which is why this isn't part of the first definition.

C++ is not truly a superset of C. It's very easy to write valid C programs which are not valid C++ programs, perhaps the most obvious way being that C++ reserves some keywords that are not reserved in C, so a valid C program using new as a variable name isn't valid C++. In practice, people talk about a slightly looser notion of a language being a superset, and might say that C++ is "almost" a superset of C, to mean that a great many valid C programs are also valid C++. Of course loose notions can lead to errors (both of communication and of programming).

A proper definition of subset is important when you are trying to change a language (to create a new version) while maintaining so-called "backward compatibility". For your new version to be truly backward-compatible with the old one, an implementation of the new one should run every program from the old one exactly as before (at least, as far as the language defines its meaning), because this means users can update to the new version and all their old programs will still work (at least, assuming they relied only on guaranteed behavior). The same applies with, say, a library API, except that then you aren't worried about the whole language, you're just worried about interaction with your interface.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • Thanks! I was hoping you won't mind, but do you mean that the subset relation for programming languages is not only the subset concept between formal languages (grammar), but also the subset concept in terms of semantics? If yes, how is the subset concept in terms of semantics defined? Thanks! – Tim Mar 25 '11 at 23:55
  • @Tim: I don't know how semantics are formally defined by language theorists, but in the case of C and C++, a program has "observable behavior". Then L1 is a semantic subset of L2 only if every strictly conforming program in L1 has the same observable behavior in L2. Further, for every program that's well-formed but not strictly conforming (meaning that its observable behavior is affected by implementation-specific factors), the set of legal behaviours in L2 must be a *subset* of the set of legal behaviours of L1. Or something like that, I'm making this definition up rather than quoting it. – Steve Jessop Mar 26 '11 at 00:06
2
  1. Although the term and general concept comes from set theory (and if you defined a programming language as a number of sets you could take the term literal and see subset/superset relationships between some of these sets), for all practical purposes the definition is much more informal: Language L1 is a superset of language L2 if programs valid in L2 are valid in L1 as well.
  2. Don't confuse languages with language implementation. C++ is just an abstract specification, but it has been implemented in numerous ways - propably C first, nowadays propably in C++. But basically, yes - since the first implementation of L can't be written in L, you have to write it in something else. That something else is usually a widely-used, mature language. In the case of interpreters/VMs, it's usually C or C++ for raw speed and to have control over memory management.
  3. There's very rarely "more" or "less", there's always "different". C++ is built on top of C, so of course it has most of its features. But even in that case, we don't have a real superset relation and not just "more" features - C++ doesn't have all C features (anymore, at least) - just think of C99, variable length arrays to give a concrete example. To be a full superset of another language, a language of course needs to be support all of that language. In that case one could indeed talk about it having "more" features, I suppose.
  4. Countless. Take your pick, use your imagination. Few of them are useful or interesting though.