Computation is Pattern Matching

This is my favorite single slide from the emerging languages conference.

I think this sums up the struggle developers of today regularly encounter quite nicely. This image comes from Jonathan Edwards’ Coherence/Subtext talk slides. He went on to then propose some very interesting ideas on how to solve this problem by managing pointers and memory in a new scheme. I’m not able to really comment on his recommendations because I didn’t fully understand them. But what I would like to propose is that there actually might be another way to solve this same problem.

I believe that Pattern Calculus (or Pattern Matching) is a unification of these three problems. It’s a superset of lambda calculus and data structures.

Pattern Calculus Computing with Functions and Structures Jay, Barry 2009, XVII, 213 p. 58 illus., Hardcover ISBN: 978-3-540-89184-0

I have yet to read this entire book but the foreward and introduction alone provide some deep gems, such as:

This book develops a new programming style, based on pattern matching,
from pure calculus to typed calculus to programming language. It can be viewed as
a sober technical development whose worth will be assessed in time by the programming
community. However, it actually makes a far grander claim, that the pattern matching
style subsumes the other main styles within it. This is possible because it
is the first to fully resolve the tension between functions and data structures that has
limited expressive power till now. This introduction lays out the general argument,
and then surveys the contents of the book, at the level of the parts, chapters and
results.

The pattern calculus is a new foundation for computation, in which the expressive
power of functions and of data structures are fruitfully combined within pattern matching
functions. The best of existing foundations focus on either functions (in
the λ -calculus) or on data structures (in Turing machines) or compromise on both
(as in object-orientation). By contrast, a small typed pattern calculus supports all
the main programming styles, including functional, imperative, object-oriented and
query-based styles.

The pattern calculus is the result of a profound re-examination of a 50-year development.
It attempts to provide a unifying approach, bridging the gaps between
different programming styles and paradigms according to a new slogan – computation
is pattern matching.

It is surprising how this elementary principle allows one to uniformly and elegantly
cover the various programming paradigms, not only concerning execution
but also typing, which itself is also realized following the idea of pattern matching.

(emphasis mine)

Code itself can be thought of as data when viewed from inside a compiler. A compiler can transform that data into something executable. This process can be repeated any number of times. Alessandro Warth of OMeta contributes to this idea in his phd dissertation.

OMeta’s key insight is the realization that all of the passes in a traditional compiler are essentially pattern matching operations:

• a lexical analyzer finds patterns in a stream of characters to produce a stream of
  tokens;
• a parser matches a stream of tokens against a grammar (which itself is a collection
  of productions, or patterns) to produce abstract syntax trees (ASTs);
• a typechecker pattern-matches on ASTs to produce ASTs annotated with types;
• more generally, visitors pattern-match on ASTs to produce other ASTs;
• finally, a (naive) code generator pattern-matches on ASTs to produce code.

And I agree with these guys. I have been working on a MetaSharp for a while now and on some of my more ponderous days I have seen to the bottom of the rabbit hole and come to the conclusion that they are right. I’m able to see a world where an application is entirely based upon pattern matching principles. Starting with a core of Patterns you can represent and transform to and from any design pattern imaginable including those needed to create traditional compilers. Essentially this gives you the ability to author an entire application as essentially tiers of patterns and projections.

I would like to contribute to the area of Pattern Matching by talking about the promise of scalability. In traditional general purpose programming as your application grows larger it becomes more and more difficult to maintain it. The sheer volume of code becomes infeasible to make broad changes with refactoring tools, the application becomes harder and harder to grasp in its entirety. Also, design patterns implied in the code become harder to enforce as developers begin to encounter new areas for the first time. There are many challenges that arise as an application grows.

Roman Ivantsov gave an interesting talk on ERP software and the scalability challenges it faces at the 2008 Lang.Net Symposium. Basically ERP programs are humongous applications, they are complex, costly and risky. What I took away from Roman’s talk, however, is that the solution to the problem is that we need a new approach to address applications of this scale. We cannot develop these applications purely as general purpose languages and succeed.

And again, I believe him. I think he is correct. As applications get bigger they can actually take so long to develop that they are obsolete before they are actually done. This is a problem.

Maintenance cost in Volume, for traditional applications.

Which is to say as your application becomes larger and you add more and more tiers the complexity also grows. The cost is like a pyramid. There are many things that go into Maintainability but in a general sense it might be said that maintainability is a function of code size and complexity.

Pattern matching offers an alternative to this traditional conundrum. It’s maintainability illustration is more columnar.

Maintenance cost in Volume, for pattern matching based applications.

Which is to say, that at each tier of an application the complexity could be about the same as the previous tier, thus increasing the functionality of an application for the same volume (cost) of maintainability. Interestingly enough, for small applications or applications with only a single tier the cost is probably higher. But as you grow  you begin to reap benefits.

This is a hypothesis of mine currently, it has yet to be proven however. Also, given the state of Pattern Matching as it exists today the above promises are definitively false. However I don’t think it needs to be this way. I think it is possible to change solve this problem and usher in a new era of software development paradigms.