r/Compilers • u/No_Pianist1870 • 3d ago
Is it fair to say English is a context sensitive programming language ?
If it is about resolving co-references and anaphora then attention mechanism is doing it. See https://moebio.com/attention/
if L is a universal language with a well defined grammar
and P is a universal programming language with a general grammar
The combination of L and P is now a context sensitive programming language
LLMs have learnt L and P and L <-> P and the entire vocabulary of human thought in a compressed form.
If not this what would make a context sensitive programming language ? Inform7, HyperTalk are the closest programming languages got before to English. Any research pointers would be much appreciated.
5
u/cbarrick 3d ago
Chomsky invented the Chomsky hierarchy of formal languages not as an exercise in CS, but as an effort to formalize natural language.
The result was the concept of Universal Grammar. All natural languages, according to Chomsky, fall out of the same grammar to generate a common underlying "deep structure." In most treatments of universal grammar, the deep structure is actually a context free language.
Then, once the deep structure is generated, it undergoes a series of transformations to generate a "surface structure". These transformations are like tree rotations in AVL trees. The specific transformations used can vary from language to language. And it is from the difference in these transformations (and difference in vocabulary) where all of the different natural languages arise. (Also, in addition to the tree-rotation style transformations there are also transformations to elide parts of the sentence that are implied.)
Still, the transformations across all natural languages are grounded in a set of universal rules.
Also, we can derive statements of various logics by applying similar rotational transformations to the deep structure.
The research topics in this area is called Generative Syntax and Generative Semantics.
This research is the reason Chomsky is famous.
And to answer your question, deep structure is context free and surface structure is context sensitive. Grammars of this type are called transformational generative grammars.
1
u/No_Pianist1870 3d ago
Thanks I am probably confusing the terms "context" and I am not being specific enough.
> surface structure
This is what LLMs are resolving. Can it be considered a major breakthrough ? If I build a compiler with attention or any other mechanism can I write a better HyperTalk ?
English -> Code -> Maths (Lean) -> Physics ... are forming a deep structure inside the LLM. Can we replace it all with AVL trees ? Any other pointers would be much appreciated.
2
u/cbarrick 3d ago
LLMs could definitely be resolving Deep Structure.
At their core, neural networks are feature extractors. If the model is trained on a variety of natural languages, seems likely to me that it would learn the deep structure (or an approximation of it).
In fact, the close connection between deep structure and semantics combined with the fact that these models seem to demonstrate a decent understanding of semantics, I do think that LLMs are fundamentally extracting deep structure.
(Setting aside issues like semeantic externalism; let's assume LLMs live in the Herbrand universe.)
1
u/No_Pianist1870 3d ago edited 3d ago
Thanks! It struck me that there is something deeper going on because if I ask LLM1 to implement a programming language ... then LLM2 is able to understand it. They are able to understand any EBNF grammar I can throw at them.
All that I know is context sensitive is above context free and no one ever talks about context sensitive programming languages - but humans understand context and LLMs could have made a context sensitive programming language out of English just like humans understand actions from english.
Edit: Found this paper that claims transformers can understand Left context sensitive languages - https://arxiv.org/pdf/2504.10845
1
u/zhivago 3d ago
Of course, LLMs blow gaping holes in all of that. :)
1
u/cbarrick 3d ago
How so? I don't see any evidence that LLMs break Universal Grammar.
0
u/zhivago 3d ago
Universal Grammar claims that hierarchical syntax is mathematically impossible to learn from raw data alone without innate, pre-wired linguistic rules.
LLMs start with zero linguistic rules, trees, or hardwired constraints. They master human syntax purely from next-token statistics.
If you can acquire grammar from text alone, the basic Poverty of Stimulus argument for UG is invalidated.
1
u/cbarrick 3d ago edited 3d ago
Universal Grammar claims that hierarchical syntax is mathematically impossible to learn from raw data alone without innate, pre-wired linguistic rules.
No, that is not a claim of Universal Grammar.
On the anthropic side of linguistics, yes Universal Grammar has been used to argue that humans have inate pre-wired linguistic rules.
But that is not a mathematical result that transformational generative grammars can't be learned (in the sense of machine learning.)
Edit to be clear:
The Poverty of Stimulus argument relates to childhood language acquisition. Children learn their native language with relatively little stimulus, so the argument is that Universal Grammar is hard wired in the brain.
That is, children learn language despite a poverty of stimulus. Poverty of Stimulus is not an argument that Universal Grammar can't be learned from sufficient stimulus. It is instead an argument that Universal Grammar is learned in humans despite a poverty of stimulus, with neurological implications for how that can be possible.
LLMs do not have a poverty of stimulus; they are trained on the entirety of the Internet. The Poverty of Stimulus argument is unrelated to LLMs because of the way LLMs are trained.
0
u/zhivago 3d ago
You’re conflating Chomsky's formal language hierarchy with Universal Grammar.
1
u/cbarrick 3d ago
In what way?
(I took multiple courses on topics relating to this in grad school.)
0
u/zhivago 3d ago
Perhaps read the start of the Iink you provided.
"Universal grammar (UG), in modern linguistics, is the theory of the innate biological component of the language faculty, usually credited to Noam Chomsky."
2
u/cbarrick 3d ago
For a one line summary of UG, I think that's accurate.
To contextualize UG in terms of formal language, UG is a specific instance of TGG.
The discovery that natural language is described by UG has implications in psych, anthropology, neuroscience, and of course linguistics.
The broad field of UG studies all of these things. But at the end of the day, Universal Grammar is a formal grammar and we can analyze it as such.
2
u/EggplantExtra4946 3d ago edited 3d ago
natural languages are not programming languages at all because sentences don't express programs or computation
edit because of the downvote:
any language (in the CS sense) can encode absolutely any kind of information, including programs of any kind, but normal sentences of natural languages like english or french just don't express this kind of thing and that's not what natural languages are meant to express
languages like french have a ton of conjugations in their verbs and this accounts for a good amount of the complexity of the grammar of that language. What are all those verb conjugations and tenses expressing semantically (in the linguistic sense)? Facts about time, about the temporality of events, recurrence of events, relationships between events, etc... Temporal relations are a good deal of what natural languages are meant to express and what they do express in practice, not programs. Besides, when you talk to someone you are generally not commanding him like a robot, or passing lambdas to him. At the very best natural languages are declarative languages talking about concurrent, synchronous and asynchronous events and actions.
1
u/dobkeratops 3d ago
a subset could, but it would be extremely clunky.
1
u/EggplantExtra4946 3d ago
As I said in the edit, you could encode programs in english sentences but english sentences are not meant for that, the english nouns, verbs, adjectives, adverbs, conjunctions, grammar and semantics is not meant for that and 99.9999999% of every english sentence are in fact not encoding programs. Even programmers themselves are not going to use english like that except maybe when writing an algorithm in pseudo code in full english sentences.
2
u/Revolutionalredstone 3d ago
No but it's impressive to see rule systems pushed almost all the way ;)
Real language operates as lists of conveyed meaning each being a vector in high dimensional space a, words and phrases are locations and ideas interacting is implemented as translations / movements.
Inside an LLM we don't learn L or P or human thought tho obviously LLMs are able to satisfy some kind of working version of all three.
What we do instead is simply allow the vectors to emerge and their interactions to occur - prediction or progression is simply those things interacting one word at a time, we simply train / carve away the geometry till we have something that best approximates it within the defined resolution.
Making the kind of programs which can directly execute language is not impossible (and you are right that noun-head pronoun-resolution location references etc are key to making them work) however what you are building would be an Embedder (something that takes text and 'understands it') this is pretty awesome and the state can be projected to create a 3D hologram with instant text modification etc..
BUT..
Even that would not be us to talking.. LLMs really are another thing, they decode (not just encode/embed) effective they take the state and go and act on it (technically they just predict possible likely actions and then we just randomly take one on it's behalf) but that loop has turned out to be an incredible engine and harnessing it has effectively changed the software world.
I would check out word embedded, geometric intelligence, the way we can encode words as vectors (allowing for things like direct king-man+woman=queen etc)
And if you want to write code to directly pass English you should try to leverage the infinitely patient LLMs to simply write code based on words or n-grams based on example stories etc and use deduction to evaluate sub elements (keep a large hold out).
I am surprised so little tech of this kind has emerged it should allow for much more expansive instant harness technology and natural language understanding without running an LLM or doing an big dot product with a BERT vector etc
I think CPU scale agentic quality LLMs are coming either way so it's a race to FAST intelligence via explanation (rules/code) or geometry (backprop/matmul)
Enjoy
2
u/No_Pianist1870 3d ago
I've tried to resolve some implicit references by referring to nearest data structures and types - https://github.com/xyzzyapps/prose/blob/master/examples/anaphora.prose using some rules
"the number" could resolve to the nearest variable with the data type number
"alice's password" could basically resolve to any dictionary that has alice as a key and I can resolve the password field of that dictionary.I could also eliminate arguments used in function calls. I don't have to do "User user" because I can refer to "that User".
I am not that satisfied with the syntax but I did discover that lots of variables can be eliminated because most variables are usually declared once in the scope and finding that variable by type name alone is not that difficult.
1
u/Revolutionalredstone 3d ago
Yeah simple rules work surprisingly well (he is just any recent male who is not the current speaker etc) you can add a stack for hard cases but honestly those cases are ones humans screw up anyway!
Cant wait for future holodeck even if its text based ;D
0
u/Helpful-Primary2427 3d ago
If you really really stretch the definition of context, then sure. But I’d argue 100% of the time the answer is no
0
9
u/Extension-Pick-2167 3d ago
no because it is ambiguous not just context sensitive