An extensible type system for meaning-preserving modularity

I’m gradually figuring out a foundation for a general-purpose programming language, and I think I just laid a great cornerstone,  which seems to solve the expression problem for dependent type theory. My pseudocode is in this long GitHub Gist, which comes with a long revision history showing my progress over the last 12 days.

I haven’t yet looked for a proof of strong normalization, consistency, and whatnot (and I don’t even intend for my theory to be expressive enough to support induction!), but the final insight has turned out to be very straightforward: If we can extend an extensible type and reimplement its interface (and re-prove its invariant) so that the new implementation/proof is observationally equal to the original as far as the original cases are concerned, then our extension may as well have been part of the type all along.

I’m using the observational equality infrastructure described by Altenkirch and McBride in “Observational Equality, Now!” and the way I think of the expression problem pretty much lines up with the requirements listed in Zenger and Odersky’s “Independently Extensible Solutions to the Expression Problem.”

Continue reading

Advertisements

Reactive Knowledge Networking

On December 20, just in time for the Mayan apocalypse, I thought of an approach to computer programming that unites my meaning-preserving modularity, some of David Barbour‘s RDP vision, and my own philosophical worldview.

I’m calling it Reactive Knowledge Networking. It takes the philosophical idea that a person does nothing with the world except observation and action, and it uses that idea to facilitate people’s communication with each other, with minimal (if any) computer configuration bureaucracy along the way. Its network structure is very similar to RDP, and it uses meaning-preserving modularity to encode the partial knowledge a person has observed.

Continue reading