Static Types for Parsers

All of our Seran outpost experiments teach about the tools and libraries preferred by deno. Here I report some ups and downs writing a parser in typescript and then not typescript and then in typescript again.

We deviated from our intended method by writing the parser using deno to evaluate a script full of console.log, rather than using wiki pages for the same purpose. The typescript type unions of tag|text and tree|text proved challenging.

Here I quote offline conversation.

Ward: > I wrote a minimal html parser and then added some tree traversal functions that would extract the very text we were going to need today. I had trouble writing in typescript so I reverted to javascript. This was a mistake as it was much harder to integrate the code without types associated with each function argument and return. In my pull request I proved that it worked. But I didn't show how it worked. Today rebuilding the call sequence in the new application lead to many type and runtime errors that could have been avoided. github > From this experience I conclude, for a page of code it might be faster to write it in javascript, but it will be faster to move a page of code to a new environment if I bothered to wrap up my coding work by adding types before sharing.

Joshua:

> Example of where types are more trouble than they are worth: `Page | () => Page`. This is a type that can either be a page or a function that produces a page. In JavaScript, you simply check for the presence of a property that only pages have, call the function if it is missing, and then use the page normally from there on out as you know it will always be a page object. Doing the same in TypeScript required three fairly ugly casts. I wasn't able to find a nicer way to do it and kept running into situations where it would start complaining again so I dropped the types for that parameter. >Even with the approach I outlined, types result in more work (especially when refactoring code that merely passes references around). There's probably some minimal number of places one could get away with typing that could further reduce the overhead.

Ward:

> I've tried hard to revise parse.js to be typescript. I can't get it to work. Help me out. github

Joshua:

> This illustrates my point. If you relax the type checker, what you have will compile just fine. > `deno -c .\tsconfig.json ...` > That works without error. If I remove the config (the thing that relaxes the type checker), I get three errors. If you are just looking to leverage types when and where they help you catch casual type errors, I recommend using a setup like the tsconfig.json in the seran-wiki repo. > If this is more of an academic exercise to understand how to satisfy all of the type checking rules, I can help dig in there. My impression was you were after the former.

Ward:

> Did you read the types and agree that they would have made our work today go faster? This is a little tricky in that the scanner finds two kinds of nodes, tags and text between them. Then parse reorganize these into a nested structure where the text between open and close tags is similarly composed of two kinds of nodes, trees and text. I work though the cases so that I know I have text when I try to move it from token stream to parse tree. I take it as a personal challenge to describe this partial equivalence in the type system. This might be foolish but I feel like have to prove my worth to the type checker.

Eric:

> Some years ago I took a coursera introduction to scala. The course itself was very well constructed. There was a point when I was taking that course that I could make sense of complex types and the syntax needed to specify them. I think if it were closer to the time when I had taken that course or if I'd stayed longer with a strictly typed language I might be able to make sense of the types needed to make this work. When I tried last night, some of that understanding returned, but not enough to get me to a solution before I began to doze off.

Joshua:

> That brings back memories. I had several co-workers who took that course. I had already read a book on Scala by the time I heard about it. I think Clojure caught my eye soon after that.

Ward:

> Too much good thought is happening here to have it lost in a chat room. Tactical coordination is ok here, but strategic thinking would be better served by wiki and we have a pod for that already. I have a page, Dream Big, there but I don't think it is thinking big enough. Today I started a new list, Outpost Thinking, where Seran experiments can be cataloged.

Having thought about this more I realize that the types a scanner might add to tokens must be dynamic types for a parser to branch on type as they must do.

When I created the static union types I was enabling implicit assertions that would distinguish tokens from trees but nothing that would effect the control flow of a type correct program.

type token = tag | text type tree = ... (tree | text)[] ...