Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I wonder which one of the two needs a larger input to achieve a decent accuracy:
programming language detection or natural language detection?


More details:

Definition of Language detection:

In natural language processing, language identification or language guessing is the problem of determining which natural language given content is in. Computational approaches to this problem view it as a special case of text categorization, solved with various statistical methods.

The question I was asking can be written bit more formally as: let $x$ be a substring from some text $X$ written in natural language, and $y$ a substring from some source code $Y$ written a programming language. Assume a $X$ and $Y$ are each written in one language only (natural language or programming language).

Let $f(X)$ be the size of $x$ so that on average (i.e. trying on a bunch of different X) I correctly predict the language with accuracy $p$. Does $f(X) < f(Y)$ or $f(X) > f(Y)$ ?

share|improve this question
1  
A string describing a program would have to follow a rigorous syntax; there shouldn't be a room to discuss about accuracy of detection, unless you're allowing input to be sub-string of the real program. or something similar. I feel the need to clarify the question. –  Billiska Jul 23 at 15:47
1  
I find the problem statement unclear. Should we assume we know what the two languages are and have a model of them? In other words, is the problem "given that one of $x$/$y$ is English and the other is Java, tell which came from which language?" Or is the problem "given that one of $x$/$y$ is from some unknown human natural language and the other is from some unknown computer programming language, which came from which?" Those two problems seem very different. When you talking about "predicting a language", what is the hypothesis space of possible languages we're selecting from? –  D.W. Jul 23 at 22:08
1  
This question is perfectly clear. One has to understand what language detection (or identification) is. See wikipedia, second answer by Google. It is a standard problem in natural language processing, and people make money on good technology for it. It usually concerns simultaneously a large number of natural languages. The question is whether programming languages can be discriminated more or less efficiently than natural languages (each kind separately, of course)- cc @D.W. –  babou Jul 23 at 22:13
1  
1) If I only have one language to detect, I can always say "it is" and not make any mistake. What are the alternatives? Do we get multiple models and have to decide, or do we have to separate one language from "everything else"? 2) Why is the question not trivial for programming languages? We have a formal specification; run the parser(s) and see what happens. Do we have to deal with inaccuracies? –  Raphael Jul 24 at 16:04
1  
3) In order to talk about accuracy in any meaningful way, you need a stochastic model. What do you assume, uniform distribution over texts of some fixed size $N$? Exponential law? –  Raphael Jul 24 at 16:20

3 Answers 3

Answering knowingly this question would require experiments. I am sure there is some data for natural languages, where it is a common problem. I recall from memory that one study gave ridiculously small figures for natural language, which is not too surprising. If you take 5 consecutive word in a sentence (the figure I recall, without being sure), there is a good chance that one of them belongs to a single language, and even more that the fragment can syntactically belong to only one language (parsing fragments without context is possible with existing technology). To me the problem is not so much the size of the input as the size of the recognition program and its data. There is a compromise there. Actually my guess is that keeping all the relevant data is far too costly, and that the actual techniques are statistical ones, such as checking n-grams of letters. (see Wikipedia), which are extremely effective.

Regarding programming languages, the problem is a bit different. The size of the vocabulary is ridiculously small, and identifiers do not give any indication (or very little with the allowed mophology: a language could forbid to use dask inside identifiers, for example). Furthermore, what fixed vocabulary there is (keywords) is often the same in many programming languages. However, programming languages have a very strict syntax, which will certainly distinguish them rather quickly. It is not so much how long a fragment as the kind of fragment. A long succession of assignments might look the same in many programming languages. Buit I would not venture any figure, and I am not even sure statistics would make sense.

Then there is the issue of parenthood. A fragment of Pascal may look very much like a fragment of Algol 60 or Simula 67. Is American English to be distinguished from British or Autralian English?

To conclude, without any hard knowledge on facts:

The problem should be stated with a word regarding the space cost (and possibly time-cost) of the identification program.

Identification for natural language is essentially morphology or lexically based, and will use statistical techniques if space costs are to be acceptable. They can recognize fairly short sequences (a few words as I recall) with good accuracy.

Identification for programming languages is essentially syntax based, and probably needs larger fragments in number of tokens, in order to have enough syntax substance, despite the intentional similarities between programming languages. But it can probably be 100% accurate, without excessive size of the identification program. I would however be more confident if I had actual data to back my guesswork. I do not know of any work on this topic.

Considering only fragments is not an issue. It is obviously not an issue when only lexical information is used. It is not an issue either when syntactic information dominates, as the technology to parse fragments is working well.


Afterthoughts, after the question was completed.

One minor remark concerns the concept of substring size: is it measured in characters, in bytes, in lexical elements? Size of character encoding is variable. Characters take diacritical marks. Lexical elements have different average size in natural and programming languages.

A more important remark concerns the mode of measurement. Natural language will use statistical methods to avoid the problem of natural language huge specification. Hence the answer is accordingly accurate with some probability that may depend on substring length (different techniques produce different types of mis-detection).

In the case of programming languages, the specifications are small enough that they can probably be used exactly. Hence the answer could possibly be always 100% exact at acceptable cost. The problem would not be with the detection procedure inaccuracies as in natural language, but in the question itself. If a string does not discriminate two languages because it can belong to both, no amount of technology will help you solve the problem. In such a case, the detection software should not guess, which would be meaningless, but it should just list, with a 100% accuracy, all the programming languages the substring can belong to.

In other words, the case of natural language and the case of programming languages are very different technically. I am not sure it makes sense to compare them.

share|improve this answer

I understand the problem as follows:

Given a text $t$ and models $M_1, \dots, M_k$ for languages, detect which of the $M_i$ generated $t$ or, alternatively, that none did.

I move that the problem is so different for natural $M_i$ and programming $M_i$ that a comparison makes little sense.

The main reason is: programming languages have specifications that enable us to solve the word problem effectively, and often even efficiently¹. In that case, the solution is simple:

  • Run parsers for all $M_i$.
  • If exactly one $M_i$ answers "yes", output $i$.
  • If none answer "yes", output "none".
  • If multiple answer "yes", output "underspecified" (and maybe the list of accepting $i$).

In the case of natural languages, this is clearly not possible since we have no formal, effectively parseable representation and hence have to use a whole different set of techniques.

Now, regarding the length of the sample necessary to distinguish two languages. Even for programming languages, there is no universal answer: if you only have Lisp, Java and Malbolge in your list of models, things will be easy. If you have Pascal and Delphi or C and C++, there are (probably) arbitrarily long texts that can not be uniquely classified.

I imagine that the situation is similar for natural languages. English, Mandarin and Icelandic are probably easy to distinguish -- a single word may usually suffice -- but Norwegian and Swedish (or Danish, no idea which is closer in writing) can give you a hard time.

In other words, the question can not be answered in its generality.


  1. Usually.
share|improve this answer
    
+1 I agree with the first half the this answer, where it formulates the question more precisely and give the algorithm for programming language case. For the later half, saying can not be answered might be too hasty. I think the OP is interested in average of $f$ over texts in current practical use, which I think can be calculated. –  Billiska Jul 24 at 16:48
    
@Billiska: How so? The set of "texts in current practical use" is not well-defined. Of course, you can calculate such a score for every given algorithm and set of texts, but the OP gives neither. It's unlikely that either type of language can be detected better always, that is for every combination of any algorithm and any choice of texts. (No free lunch!) –  Raphael Jul 24 at 17:43
    
I wanted to change the word "calculated" to "estimate". Just like how we estimate the dose needed to cure a disease, for example. We could sample, during some period of time, texts from twitter (or sources from github). Then uniformly sample the substring. Then get an estimate, together with some degree certainty. It's not my kind of research, but this kind of estimation with help of statistics can be done. –  Billiska Jul 24 at 20:20

the idea that human languages are similar to programming languages is encouraged by the use of the term "language" in theoretical computer science but there which (also) has a very specific technical/mathematical meaning. this blurring was encouraged by ideology associated with one of the rare crosscutting pioneers in CS/linguistics, Chomsky. a computer science "language" refers to a set of strings, possibly infinite. however, there is no ambiguity involved in these mathematical sets. human language has ambiguity. human language recognition is an imperfect/ imprecise/ inaccurate exercise even for humans and it is an open question in AI whether there is an algorithm for it.

a similar analogy can be made to Turing machines. real PCs are alternatively sometimes considered equivalent, or inequivalent. sometimes the analogy breaks down. another case study here is ambiguity in CFLs. programming languages, all basically/roughly CFLs, are carefully built to avoid ambiguity. all human languages have ambiguity that even humans imperfectly parse. so in short, the question mixes up apples and oranges. but this is not uncommon in even some professional/ scientific writing on the subject of AI-related topics.

share|improve this answer
1  
Almost none of this answer is relevant to the question. –  David Richerby Jul 24 at 7:40
    
I think there is one applicable sentence in here, "the question mixes up apples and orange", but that's merely a comment in that form. –  Raphael Jul 24 at 16:18
    
the commenters narrow responses misunderstand the wider abstractions, history, scope, trends, & research programs/ themes (etc) admittedly quite briefly sketched/ outlined –  vzn Jul 24 at 22:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.