4 ms·

What a ridiculous assertion. Category Theory and Chomsky Hierarchy are two easy to understand and key theories of Computer Science. If you don't have any unde

What a ridiculous assertion. Category Theory and Chomsky Hierarchy are two easy to understand and key theories of Computer Science. If you don't have any understanding of these, you're not a professional programmer. Maybe it's "even abstract for mathematicians" should be "too abstract for detail oriented math nerds, but pretty easy to comprehend at a basic level"

jfarmer 13y ago
I'm not sure what the Chomsky Hierarchy has to do with what we're talking about, but re: category theory, there's a difference between "understanding" and "familiarity." I agree that the definition of a category is not a hard thing to learn. However, can you give me, say, three non-trivial examples of categories you'd expect a "professional programmer" to know? How about three non-trivial examples of functors? If understanding category theory is a pre-requisite for being a professional programmer then 95% of the people I know who get paid to program aren't "professional programmers. You're just being silly. Or trolling. Probably trolling.
- deleted 13y ago
  [deleted]
haberman 13y ago
I don't think the Chomsky hierarchy is very useful for Computer Science, except the distinction between regular and context-free languages (which is extremely useful). "Context-sentitive language" in the Chomsky hierarchy is not the same as what a programmer means when they say a language is context-sensitive. In programming languages, "context-sensitive" nearly always refers to semantic context-sensitivity (for example, the set of symbols that are defined at this point and their types), not the syntactic context-sensitivity described by the Chomsky hierarchy. For example, none of the context-sensitivity described on this page has anything to do with Chomsky context-sensitivity: http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar/ http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv... I can't think of a single case where Chomsky type-0 or type-1 grammars are relevant to any practical concept in computer science. And due to overloading of the term "context-sensitive" learning about the Chomsky hierarchy can be actively misleading unless you are aware of this distinction.
- ggchappell 13y ago
  > I can't think of a single case where Chomsky type-0 or type-1 grammars are relevant to any practical concept in computer science. Not the grammars per se, but the notion that there are things computer programs cannot do -- and that we have a good handle on what these things are -- is an important one. As for Chomsky's Type 1, I've seen no evidence that the concept of a context-sensitive language has been of practical use to anyone, ever. It looks like an idea that turned out to be a dead end. EDIT. To clarify: Certainly there are CSLs that have been of practical use. But the fact that a certain language is or is not a CSL, does not seem to be something worth knowing.
  - Fasebook 13y ago
    This is exactly what I'm talking about, but because people already have a basic understanding of context and so on, they don't appreciate the significance of Chomsky's work. I don't know how anyone can even argue with me about category theory, I just want to put it off on them being disingenuous instead of thinking about it further or trying to argue with them. When I see that replies about Chomsky Hierarchy being "extremely useful" and "not very useful" in the same sentence, while I'm downvoted for suggesting otherwise.. Obviously, other commentators need to get their opinion straight before trying to impress their opinion upon mine.
    - haberman 13y ago
      Wow, I actually think you are trolling. I never thought that trolling HN about obscure technical concepts would be a worthwhile use of someone's time. Just in case you're not, and in case anyone else is following along at home, here is my position. The Chomsky Hierarchy draws three distinctions or boundaries between grammars: 1. type-0 (unrestricted, recursively enumerable) vs type-1 (context-sensitive) 2. type-1 (context-sensitive) vs type-2 (context-free) 3. type-2 (context-free) vs type-3 (regular) Distinction 3 is a deep and practical concept that all programmers should know. Distinction 1 is practically useless. Distinction 2 is actively misleading. Also, when Chomsky developed this hierarchy it was in the context of natural language. He was trying to generate English sentences, not programming languages (which were still rather primitive in 1956 when Chomsky wrote his paper). It is not surprising that most of Chomsky's hierarchy is of limited use to Computer Science, since it was never intended to be.
anaphor 13y ago
Others have explained why the Chomsky Hierarchy isn't particularly useful to people working on designing or implementing languages. What IS useful and which developed around the same time as Chomsky's theories is BNF notation: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form

jfarmer 13y ago

I'm not sure what the Chomsky Hierarchy has to do with what we're talking about, but re: category theory, there's a difference between "understanding" and "familiarity." I agree that the definition of a category is not a hard thing to learn. However, can you give me, say, three non-trivial examples of categories you'd expect a "professional programmer" to know? How about three non-trivial examples of functors? If understanding category theory is a pre-requisite for being a professional programmer then 95% of the people I know who get paid to program aren't "professional programmers. You're just being silly. Or trolling. Probably trolling.

deleted 13y ago
[deleted]

haberman 13y ago

I don't think the Chomsky hierarchy is very useful for Computer Science, except the distinction between regular and context-free languages (which is extremely useful). "Context-sentitive language" in the Chomsky hierarchy is not the same as what a programmer means when they say a language is context-sensitive. In programming languages, "context-sensitive" nearly always refers to semantic context-sensitivity (for example, the set of symbols that are defined at this point and their types), not the syntactic context-sensitivity described by the Chomsky hierarchy. For example, none of the context-sensitivity described on this page has anything to do with Chomsky context-sensitivity: http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar/ http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv... I can't think of a single case where Chomsky type-0 or type-1 grammars are relevant to any practical concept in computer science. And due to overloading of the term "context-sensitive" learning about the Chomsky hierarchy can be actively misleading unless you are aware of this distinction.

ggchappell 13y ago
> I can't think of a single case where Chomsky type-0 or type-1 grammars are relevant to any practical concept in computer science. Not the grammars per se, but the notion that there are things computer programs cannot do -- and that we have a good handle on what these things are -- is an important one. As for Chomsky's Type 1, I've seen no evidence that the concept of a context-sensitive language has been of practical use to anyone, ever. It looks like an idea that turned out to be a dead end. EDIT. To clarify: Certainly there are CSLs that have been of practical use. But the fact that a certain language is or is not a CSL, does not seem to be something worth knowing.
- Fasebook 13y ago
  This is exactly what I'm talking about, but because people already have a basic understanding of context and so on, they don't appreciate the significance of Chomsky's work. I don't know how anyone can even argue with me about category theory, I just want to put it off on them being disingenuous instead of thinking about it further or trying to argue with them. When I see that replies about Chomsky Hierarchy being "extremely useful" and "not very useful" in the same sentence, while I'm downvoted for suggesting otherwise.. Obviously, other commentators need to get their opinion straight before trying to impress their opinion upon mine.
  - haberman 13y ago
    Wow, I actually think you are trolling. I never thought that trolling HN about obscure technical concepts would be a worthwhile use of someone's time. Just in case you're not, and in case anyone else is following along at home, here is my position. The Chomsky Hierarchy draws three distinctions or boundaries between grammars: 1. type-0 (unrestricted, recursively enumerable) vs type-1 (context-sensitive) 2. type-1 (context-sensitive) vs type-2 (context-free) 3. type-2 (context-free) vs type-3 (regular) Distinction 3 is a deep and practical concept that all programmers should know. Distinction 1 is practically useless. Distinction 2 is actively misleading. Also, when Chomsky developed this hierarchy it was in the context of natural language. He was trying to generate English sentences, not programming languages (which were still rather primitive in 1956 when Chomsky wrote his paper). It is not surprising that most of Chomsky's hierarchy is of limited use to Computer Science, since it was never intended to be.

anaphor 13y ago

Others have explained why the Chomsky Hierarchy isn't particularly useful to people working on designing or implementing languages. What IS useful and which developed around the same time as Chomsky's theories is BNF notation: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form