my trouble with types

I have a few standard projects I fall back on whenever I’m learning a new programming language. My current favorite is parser combinators but lately I’ve been hitting a brick wall when trying to implement parser combinators in a statically typed language.

The way I build parser combinators in a dynamically typed language is quite simple. I first define matchers, then I build the basic parsers on top of those, and finally I add sequencing, alternation, repetition, etc. The input to the parsers is a wrapper around an indexable object and the wrapper simply keeps track of the index. Spelling things out with TypeScript’s syntax looks as follows

Using the above definitions implementing the actual parsers is quite simple. You just do the obvious thing and things just work

That’s pretty much it. Implementing the other kinds of parsers is just as simple. Try to parse and advance the input or rewind and retry. In any case the entire library is only about 250 lines with spaces and comments and implements a few extra features that allows one to build recursive parsers as well. The best part is that the whole thing is completely generic. Any object that supports indexing can be used as input for the parsers and you are not just restricted to parsing strings. You can also parse lists, trees, graphs, and anything else for that matter if you can figure out a sensible way to index the structure. Don’t let the object-oriented nature of the code confuse you. The translation into a functional language like Erlang would be pretty straightforward and could be done in a single afternoon.

I’m not sure what the lesson is here. If you know how to assign types to everything and have it still be as generic then I want to know.