In my last post, I said I’d talk about what I’ve been working on.
I started working on cleaning up my version of OMeta, but I found fnparse and that looks way better than my parser. It’s different two important ways: OMeta was a DSL for writing parsers, not a monadic parser; and OMeta could not combine parsers. I think in the end, having parsers defined in the host language is important. I needed to define a way to distinguish variables from keywords and other parts of the language. Not fun, especially when it’s already in Clojure.
So go use fnparse. I’m not developing OMeta anymore.
Then I started cleaning up my Link Grammar parser. It’s not exactly the same as theirs, and it’s still immature. I worked on it all day yesterday and today, trying out different strategies for structuring the code.
I was having trouble with stack overflow errors on larger sentences. After trying all of these things, I must have hit on something, because the problem just disappeared. I don’t know why.
Here are some of the ways I tried:
- Continuation passing with trampolines to make it lazy. I thought this was necessary, but it turned out not to be, surprisingly.
- Adding lazy-seq before everything to make it lazy. This worked faster.
- Using sets instead of lists to build up the solutions. I was surprised to learn that this was the fastest.
- Memoizing two key functions that get called repeatedly. Fastest, but uses lots of memory.
- Trying to avoid making a globally memoized function (to save memory) by caching some things locally in a function. Not quite as fast.
I’ve got all of those versions pushed to the clj-link-grammar repository.
I also looked around my ~/clojure directory and remembered I had done a cool little graph reasoner in Clojure. It’s really simple. It is not nearly OWL complete, but it does most of the interesting stuff. It doesn’t do math or anything. It just matches strings. Given an appropriate graph, it can answer questions like “Who has a girlfriend who likes apples?” And it’s less than 100 lines. Please check it out at the clj-reasoner repository.
