About 6 months ago, I created the prototype for a sentence generator which takes a user-inputted set of POS tags and outputs a sentence based on them, naming it "Chomskers" (not to be confused with the Chomskers Sentence Generator, this project). For example, if you input:
Det N V Det Adj N
You get:
The man obfuscates the unhygienic farmer (though I'm not sure if that exact sentence was able to be generated with it, the lexicon was VERY small).
It was only made of the lexicon, a main function to input a set of POS tags, and then a set of constraints (e.g. you can't do N Adj). It was quite primitive and I wanted to improve upon it by creating an actual generator for it. It used regexes for this, which looking back wasn't too good; if I used list slicing and checked if a sequence was in the list, I could have the same thing without requiring another module. You learn, I suppose, and I'd just finished CS50P at that point, and just used regexes for the Akkadian noun analyzer, my CS50P "final project".
I wanted to build on the lexical approach of taking POS tags and picking random words in their respective categories by making it so that the program, rather than the user, generate sentences. But it felt far-away; from what I'd heard from other people, recursion and searching are some of the hardest things in programming. No way a guy who just finished CS50P could do it. Recursion was only touched on in the last bonus short of the entire course for only about 10 minutes, and I actually didn't even watch it. I don't remember why. But looking back, if I did, I would've probably found this project much easier and implemented it earlier than I did, maybe.
About 5 days ago or so, I revisited the idea of creating a new version of Chomskers (which you can find at the bottom of the page) with the automatic sentence generation I thought about prior. I thought about the correspondence between lists and trees I only learned about from phrase structure diagrams as well as my Lisper friends (important later), my understanding being that the node depth has a direct correspondence to how many parentheses the thing is surrounded by.
I began thinking about a function that expands terms according to a context-free grammar, imagining a tree starting with S, then expanding it to NP and VP, then looping through NP and VP, expanding NP and VP into their respective right-hand sides, then looping through each right-hand side recursively. This was the basic intuition for this project, basically checking and expanding depth-first.
I had the idea in my mind for about 2 days before I opened my IDE. I was originally planning on not doing any more programming until I get a far better grounding in discrete math and algebra so I can get back to programming with a far clearer sense for what I'm doing and why, since I generally spend more time architecting on pen and paper than I do writing code when I want to build something.
But this time, I felt a strange attraction. This time, I didn't even draw it out; I went straight for my IDE. I knew exactly what the implementation would entail, though I didn't know the exact way I was to go about it in Python; after all, this is a language without tail-call optimization and a recursion limit. You can, of course, write recursive algorithms, but a lot of the time tuple unpacking and loops do what recursion would do elsewhere. I think that's what makes it attractive to beginners.
The recursion limit I didn't need to worry about; the maximum node depth of a constituency tree doesn't often come close to 100, let alone 1000, performance can't allow that, at least in accordance with Chomskyan syntax. But recursion was a concept I felt like I needed to truly use somewhere original, and a CFG is the perfect place given its already recursive nature. Not a Fibonacci or factorial function, not a file finder, but something that both relates to my love for linguistics and creates a fun product that I can get some entertainment out of. So, I decided to create a random sentence generator.
I'm not a linguist, just a guy who likes linguistics. Any mistakes I may make here I'd like you to email me at codexderelict@proton.me; let's talk about it!
One of the debates between so-called "functionalist" linguists and "formalist"/"generative" linguists, and indeed as well between generative linguists, is the role of syntax, the structure of sentences, in relation to semantics, the meaning of sentences. I'd like to write an entire article on the gamut of views from the generative side (including the categorial grammar folks who believe syntax and semantics combine as functions and arguments, oh my!) as well as the usage-based side's quite fruitful dialogue with the generativists (such as Ivan Sag's SBCG).
But in short, syntax was posited as a self-contained system, interfacing with meaning but unaffected by it, in some manner it's said that syntax is "blind" to semantics. To give you an example of a semantically well-formed sentence that isn't syntactically well formed, maybe something like: "Never he talk, mouth like clam closed he is." You might understand that this sentence is about someone who is tight-lipped. In contrast, the sentence used by Chomsky in Syntactic Structures (1957) was this: "Colorless green ideas sleep furiously." How can an idea be green? How can it simultaneously be colorless? I dare you to try and imagine a "colorless green idea"; you might think of a green lightbulb but one that's transparent, but that's not colorless. I guess it's not, at least.
So, creating a sentence generator was partly motivated by seeing how often a sentence has some semblance of meaning. One example of a sentence generated by my generator is this: "an offensively lithe nun delegitimizes our suddenly offensive lifestyle coach furiously" "Offensively lithe" is nonsensical, but a nun delegitimizing a suddenly offensive lifestyle coach? It makes sense; a coach who suddenly breaks into a racist rant being told off by a woman of Christ as his rambling is contradictory to his work, which is supposed to be to help people in varying life situations no matter what they are.
I noticed a semantic gradient in how much sense they make in terms of the sentences generated; not sure if this is because I stared at it too long, or something about the pseudorandom nature of the random module, or just pure convergence given a finite lexicon inspired by my own thoughts to some extent. I can't really test that out statistically for now, though...
The module that's at the center of the entire program. It includes a class Grammar that takes only one argument, that being one of the context-free grammars in grammar.py, calling it rules, which I'll touch on later. The other attributes defined in __init__ are POSTags, the list of possible POS tags from lexicon.py, which I'll also touch on later, lexicon, which is the lexicon taken from lexicon.py.
The first method is expand, which recursively expands terms depth-first in accordance with the defined phrase structure rules in rules until no more expansions are possible. For example, a grammar like:
S | NP VP
NP | DP N
VP | V
DP | Det Adj
would work in the following way:
First, S is expanded into NP VP. Then, since NP comes first, NP is expanded into DP N, then since DP comes first, it's expanded into Det Adj. At that level, there's no more phrase-structure rules to apply, so it moves onto N. No phrase structure rules apply, so it moves onto VP and does the same. It's a depth-first search and expansion, basically. At each level, the symbols are collected into a list and the entire list of lists is returned to the highest level when there aren't any more transformations. You can see it this way:
[S]
[NP VP]
Now we focus on NP alone:
NP
[DP N]
[[Det Adj] N]
Only then is it returned:
[[[Det Adj] N] VP]
This recursive list-in-list approach will be relevant later...
In any case, the second one is validate. It searches depth-first in the same manner as expand to check if all phrase structure rules are applied, which is only true if all symbols are POS tags and therefore terminal. However, they are non-terminal at the lexical level when they're replaced with a random word.
flatten is a similarly depth-first algorithm which creates a list and adds the symbols individually, therefore "flattening" it from the list-in-list structure they're in. It uses Python's extend function to recursively add individual elements within lists, as at each level there could be a mix of lists and symbols, so extending their contents "moves" them out of the list.
pickWords takes the flattened list of POS tags and switches them out with a random word from the lexicon that fits the tag using random.choice. The grammars and lexicon are represented as key-value pairs, and I'll talk more about them when we get to grammar.py and lexicon.py... which is right now!
As I mentioned before, the POS tags are terminal at the context-free grammar's level, but are not so lexically. So, the lexicon is a dictionary. The keys are POS tags, and the values are lists of words. It went through multiple iterations, getting more granular though there's a limit to the granularity until I probably decide to rewrite it later in another language using feature structures and unification.
One example is distinguishing transitive from intransitive verbs; there's two keys, V_trans and V_intr; there's also a distinction between conjunctions that are permitted to connect incomplete phrases (e.g. "and") and ones that can't. I'm always adding new words to it (a good bit of it is Claude, because I'm not very funny).
grammar.py has all of the CFGs in dicts, wherein the keys are the left-hand side and the values are the right-hand side. As this is context-free grammar based, the LHS is always a solitary symbol, hence why it's called "context-free", it doesn't matter what other symbols surround it or its position, the transformation remains the exact same.
All grammars are connected in a list called grammarList, such that random.choice can choose from them. Moreover, the non-terminals' names don't matter so long as they bottom out into terminal symbols whose names do matter, lest a KeyError come up as it doesn't exist in lexicon.
The grammars are deterministic and not contingent on input. Any LHS needs to correspond to one single RHS. If you want an DP to transform into Det Adj or just Det, you need to define two separate grammars, which is fine for me, if I'm honest.
While I'd architected the depth-first recursion algorithm prior, I didn't know the exact Python implementation; Claude helped me with figuring out how to say specific things in Python by helping me rewrite my algorithms. Translating from Cognitivese to Python was difficult; I tried a good bit before Claude came along. It was a learning opportunity to see how to implement recursion in Python specifically, where for loops are generally preferred where recursion may be found in a functional programming language. I now understand how it's done, but in honesty, I don't want to work with Python for something like this again.
On the topic of functional languages, I understand why Lisp remains big with computational linguists (not the modern deep learning folks, but the ones who wish to construct formal, well-defined frameworks to explain and describe natural language. No knock to them, I think there should be more dialogue between the new-school ML folks and the old-school symbolicians). Recursing over symbols practically screams for a list-in-list approach, and there's a clear tether between the code itself and what you want to represent (e.g. recursion, unification, etc).
I also realized that one of the things I feared about learning a Lisp dialect, the atom/list system and homoiconicity, I'd already implemented in Python. I used a formal language to reason over formal languages, and Lisp is built upon doing exactly that. It gave me a good bit of confidence in learning a Lisp dialect, though I need to get used to a good bit of it, including the macro system. I've decided on Racket, specifically because of its ease of use, rich resources (HtDP and the Guide, the former uses what is basically dialects of Racket that are intentionally limited for pedagogical reasons, and the latter is Racket's documentation that's made specifically to learn from). I've installed DrRacket today and have been messing around with it with BSL while reading HtDP and putting down notes.
I'm excited to start working on my CFG-based generator in Racket, which would allow me to extend it with feature structures using Racket's structs, association lists and hash tables for transformation rules, and its great pattern matching functions and macro system which is meant to build new languages overtop, including logic programming (which would be great for unification or formal semantic representations of the generator's outputs). Lisp doesn't feel scary anymore, it feels liberating to see how much easier I could do a lot of this kind of work with it. The learning curve is well worth it.
I learned a lot from this project, and I'd say that I also learned a lot about programming languages, too, at least more than I originally knew. I'm very proud of it, too, as I never believed I could architect and build something like this. I also can't wait to get good enough with Racket to implement my own macros, use structs and build a syntax-semantics interface for the generator. One interesting thought I had (for far far in the future) was actually integrating distributional semantics; using a pre-trained model to measure the embedding distances between the words used would give me an interesting semantic gradient, and possibly even answer the question I had earlier about how some sentences could make a little sense, a good bit of sense, and a lot of sense.
You can find the source code for the project right here.