Existential Quantification in Type Theory

All of logic can be encoded with a suitable type theory and this includes the usual existential and universal quantifiers. The universal quantifier is easy because it corresponds to Π types but the existential quantifier is a little more tricky. It took me some time to make sense of it so here’s a small outline of how to think about it (this is as much to help me understand as it is for someone else so if you find any issues then let me know).

Continue reading

The Cost of Bad Software Architecture

Let me know if this sounds familiar. You work at a software company that uses a 3/3.5 tier architecture. There are frontend servers, backend servers, some batch work servers, and a database or two. If it doesn’t sound familiar then maybe you have never worked with web application but that’s the predominant architecture at most web shops. In fact, even with all the microservice/devops/container/serverless hype no one has managed to change that 3/3.5 tier architecture. There is always a frontend, there is always a backend, there is always a database. The only differences are in the domain logic and implementation details like which language is used for the backend components and which database is used to hold the data. Let’s now get into some more concrete but still abstract details because I promise there is point at the end of this.

Continue reading

Involutions are Bijections

I’m starting to get more of the pieces of the theorem proving puzzle. Going through “Software Foundations” and having “Type Theory and Formal Proof” as a reference has been very helpful with putting the pieces together. I’m starting to understand why folks like type theory. The encoding of logic and computation with types is surprisingly elegant. Most of the pieces fall out of abstraction and application/beta-reduction which is kinda amazing.

But enough of that. While going through “Software Foundations” I had to do an exercise about reversing lists. More specifically, reversing lists is an involution and involutions more generally are bijections so I wanted to prove this in the more general setting without having to worry about reversing lists.

Continue reading

Some Propositional Logic in Coq

I’ve been told the best way to learn is to do so let’s do some propositional logic with Coq. I got these exercises from the first two sessions of “The Incredible Proof Machine“.

I’m not sure how to translate contexts in sequent calculus other than making everything above the bar an input and everything below the bar an output so some of the exercises did not have analogs (like flipping the order of the premises). I either skipped those or made a best effort translation.

Continue reading

Generators as State Machines

Most implementations of generators end up being state machines. This means instead of implementing explicit state machines one can use generators to keep the state implicit and let the compiler do the hard work of converting the generator to an explicit state machine. The downside of generator based approach is that it becomes much harder to serialize the state for persistence. The upside is there is less juggling of state overall because one can use the control flow facilities of the language in which the generator is embedded to keep track of the state. Continue reading

Static v. Dynamic

It’s time to bury this argument. It is no longer valid. (Actually it was never valid and I’ve just accepted this now).

We now have gradually typed languages that allow for mixing and matching the best aspects of both paradigms. I’ve also recently started to appreciate the value of a good type system. The compiler flagging weird data flow is very valuable and helpful in exploring the problem domain. I now think if given the choice it’s always better to use a statically typed language unless the shape of the data is determined at runtime. If the application is highly dynamic then there isn’t much to be gained from using a statically typed language and the iteration speed of a dynamically typed language is probably more valuable than compiler/type enforced correctness. Then again this trade-off is moot with languages like TypeScript so time to have the cake and eat it too.

Type safe message dispatch in TypeScript

TypeScript continues to be amazing. Anders and team are doing an incredible job making the language accessible and at the same time powerful enough to express interesting invariants that can be encoded with conditional and mapping types.

I’m currently working on a workflow toolkit and building it in TypeScript has allowed me to express the message dispatch logic in a type safe way. Putting the pieces together has been a lot of fun so I’m going to outline the pattern in case others find it useful. Continue reading