I updated my website with a code report about a project, check it out here:
https://codexderelict.github.io/lmc/cfgreport.html
I feel like expanding upon it because I like taking any opportunity to talk about it, but in short, I wrote a random sentence generator that uses a formal grammar (context-free, type 2 on the Chomsky hierarchy) to create well-formed but (potentially) meaningless sentences. It's a quick project and mainly something I did to learn more about automata, formal grammars and programming languages (which to my knowledge mostly fit in type-3, context-sensitive grammars), as I'm using what is practically a formal language to reason about formal languages.
I mentioned in it that working on it is what made me want to pick up a Lisp dialect (I chose Racket because it seems to be a dialect that's built specifically to build other programming languages on top of, also paging my boy
@dokyun who's a Lisper and knows a lot more about Lisp than me). Reasoning about recursion in Python is kind of difficult as while the language does have recursion and it's possible to implement, there's a limit to it and also no tail-call so each "level" creates a new stack frame. Not a problem as English sentence recursion doesn't come even close to the limit of recursion limit of 1000, after all the human brain doesn't come with tail-call recursion either.
(here's where @dokyun could potentially correct me)
Looking at assoc lists, I think I could be able to implement context-sensitive grammars wherein a rule requires multiple symbols on the left hand side. In Python, I have to write out my grammars in key-value pairs (a dictionary), where the left hand side is a symbol (string) and the right hand side is a list (a list...) but seeing Lisp, I can have rules written out in lists of lists, it doesn't matter when everything's lists. It just needs to look up a list and transform it, but with my code recursively accessing a list needs to bottom out in a singular symbol/string before it moves on. When everything's a list, though, I think it's easier to reason through it.
Not to mention, since Racket has Racklog, I can easily implement logic programming to ensure things like agreement (so no "Rats is a good animal" or "I are a good person"). Or I could even roll my own logic DSL out myself! I considered implementing feature structures in Python but that would've been far too messy, I would've needed to make ANOTHER k/v pair list for the words and their properties to ensure agreement. But in Lisp, structs seem as easy to implement as anything else, and Racket's "match" makes pattern matching with them easy, so I can easily just use that for agreement!
Sorry for the massive ramble, but I'm really happy with how this entire thing came out and can't wait to add new features to it when I feel comfortable enough with Racket. I'm doing How to Design Programs which teaches program design in more limited forms of Racket for people who have never written code before, I'm about as a n00b to functional programming as a n00b can be, so I'm doing that before I get into the Racket Guide.
1
