Name: Pattern Calculus
ISBN: 9783540891840

What Hacker News says

tikhonjSep 2015

Decorators in Python are basically special syntax for higher-order functions, so I don't think there's much there to evaluate. The lambda calculus is usually used when you want to ignore syntax.

Introductory resources on programming language theory usually have examples, after giving you a thorough grounding in the basic untyped lambda calculus. In particular, this is how they usually introduced type system features, but there are interesting things like continuations that don't necessarily involve types. Types and Programming Languages by Benjamin Pierce is a great resource, but you can probably find free lecture notes to the same effect. (I'd look them up, but I'm on my phone so it's a bit of a hassle.)

The most interesting non-introductory (but still self-contained) example I've seen was Barry Jay's Pattern Calculus book. He introduces pattern matching and first class patterns, first without types and then with, all building upon the lambda calculus. His ideas cover functional, imperative and object-oriented features, and it's fascinating to see a whole language developed piece-by-piece like that. If you're curious about PL theory and want to dive pretty deep, I think this is a book worth looking at.

thread

tikhonjSep 2015

Coincidentally, if you're thinking of adding pattern matching to the underlying calculus (not just as syntactic sugar), the book I mentioned in another comment (Pattern Calculus) is worth a look. The author explores what a language could look like of patterns were first-class and used to express arbitrary computations.

At the very least, it could be fun to have an extended version of the system (or a plugin of some sort, perhaps) using his ideas about pattern matching.

thread

tikhonjJul 2012

Instead of giving you an example that anybody actually uses, I'm going to tell you about a cool idea I've been reading about that hasn't gotten much actual use.

The basic idea is to use a generalization of pattern matching. Languages like ML and Haskell support pattern matching, but in rather limited ways. Crucially, patterns are not first-class citizens of the language. (For Haskell, at least, there are some libraries to remedy this, but I don't know how effective they are.)

So how can we generalize pattern matching to help you solve your book problem? Normal patterns allow you to match data types in the form C x₁ x₂... where C is some constructor and x₁ x₂... are either matchable symbols or arbitrary patterns. An example of a pattern would be Chapter (Cons (Section content) rest). We differentiate between the matchable symbols and the constructors on case: lowercase means matchable, uppercase means constructor. This is somewhat limited: you cannot easily write code that is generic over the constructor at the head of the pattern. You could write a function that counts the sections in a chapter, but you could not write a function that counts the sections in anything.

So let's relax the restriction that patterns have to be headed by a constructor. We can now have patterns in the form x y. These are static patterns: you can match data against them without evaluating the pattern. With this, we can imagine writing a function to count sections generically:

    count_sections x = 0 -- If this is some terminal, it cannot be a section
    count_sections (Section content) = 1 + count_sections content
    count_sections (x rest) = count_sections rest

This goes through the entire data type you passed in and counts all the sections it sees. It assumes sections can be nested. This will let you count the sections in a Book or a Chapter or a Series or whatever you want.

So, this is generic over the data you pass in. However, if you wanted a function to count Chapters or Sentences or what have you, you would be forced to write it. This calls for another extension to pattern matching: dynamic patterns. Patterns are now in the form x ŷ where x is a variable and ŷ is a matchable symbol. Constructors are still uppercase, so Section is a constructor and not a variable.

A variable in a pattern can be instantiated with another pattern. So now we can write a truly generic count function:

    count constructor (constructor) = 1
    count constructor (constructor x̂) = 1 + count x̂
    count _ (x̂ ŷ) = count ŷ

So now if you want to count chapters in your book, you would just invoke count Chapter book. If you want to count sections in your chapter? Easy: count Section chapter.

You can also use patterns and constructors for polymorphism by overloading functions on different constructors. One interesting idea is to allow adding cases to functions after their definition. This way you could have an existing toString function and then, when you've defined a book, add a new case to it:

    toString += | Book title content -> "Book: " ++ title

This way you can have a toString function that works on any type of data.

All my examples are obviously in pseudocode. (And hey, it looks nothing like Python! The whole "runnable pseudocode mantra annoys me.) I haven't covered all the edge-cases, and I haven't even begun talking about a type system for this mess. Happily, there's somebody who has, and wrote a book about it (that's where I got all these ideas): Pattern Calculus by Barry Jay[1].

[1]: http://www.amazon.com/Pattern-Calculus-Computing-Functions-S...

I'm also not sure whether this is the best possible approach. However, I think it's certainly very neat. If you like this idea, the book is definitely worth a look.

thread

tikhonjJul 2012

I think the main advantage is what I pointed out before--being able write functions that work on a wide variety of data types. I think my count example is something that could not be done with GADTS:

    count constructor (constructor) = 1
    count constructor (constructor x̂) = 1 + count x̂
    count _ (x̂ ŷ) = count ŷ

Keep in mind that this is pseudocode, so some of the semantics may not be perfect. The basic idea is this: the first argument count takes is a pattern, like a constructor. The second argument is matched against the dynamic pattern (constructor x̂). This pattern has one matchable variable x̂ and one free variable constructor. This free variable is bound in the previous argument to the function.

So this lets you use the count function to count any sort of sub-pattern in its argument. Let's imagine you have some hierarchy like (Book (Cons (Chapter stuff) (Cons (Chapter stuff) nil))). You could use the count function to count the number of chapters like this:

    count Chapter book

Basically, you're parametrizing your count function on the pattern you want to count. So count can work on any data type and any pattern. If you wanted to count sections, you could:

    count Section book

Now lets pretend that sections have numbers. Instead of (Section content) we have (Section number content). You can now count something like how many sections have the number 5:

    count (Section 5) book

I think you could generalize this even further, but it would be more complicated.

I'm not sure how this is typically implemented, largely because it typically isn't :P. I think there's essentially one implementation in a language called bondi[1] but I don't know how it is implemented.

[1]: http://bondi.it.uts.edu.au/

As for decidability, I'm not sure. The entire pattern calculus--that is, an extension of lambda calculus supporting this sort of pattern matching--is Turing-complete. I don't know if just the pattern matching part is undecidable though.

As I said in my original post, there is a nice book on this called Pattern Calculus. I think you can read it online[2], which is nice because it turns out to be fairly expensive on Amazon.

[2]: http://www.springerlink.com/content/978-3-540-89184-0

thread

jfaucettJul 2012

I like your enthusiasm! I was at the same point a while back. Here's some of the things I did to broaden my horizons and expand my knowlege:

In my teens I moved to argentina and got a job there which forced me to learn spanish well ( still stuck with el accento porteno ). In my opinion there's nothing better for opening up your mind like moving to another country, experiencing other world views, literatures, culture, etc.

Make a choice to learn something and stick with it until you master it (but make sure its something you enjoy). The toughest for me was sticking with Mathematics, because apart from trig, relational algebra, and discreet maths I hardly ever have a chance to apply the rest. So I just set apart some time daily and worked from the bottom up, its constantly more fascinating and I really miss it when I can't spend my daily time with my mathbook (currently 'pattern calculus' by barry jay - highly recommend.

I'd say delve into diverse subjects but don't try to be a master of all. Its one thing to know who decartes was, how he arrived at cogito ergo sum, and yea the cartesian plane, but you'll never be able to know it all and a lot of its completely useless. For me, after a year long period where I read into philosophy in depth I pretty much decided the whole field was pointless (for me), and decided to concentrate on disciplines that were more applicable and enjoyable for me such as physics and political history.

Lastly, to quickly answer your question about which subjects to learn I'd say the following a good for getting an overall understanding (and will keep you more than busy for quite a while :)

1. The world of the abstract - Math

2. Understanding the universe and our relationship to it - Physics

3. Life and living organisms - Biology and evolutionary theory (Dawkins, Dennett )

4. Humans and our cultures - History in tandem with at least near native fluency in one foreign language (and accompaning culture, literature, films)

5. The Mind and brain how we think and are - Cognitive Science - Gödel, Escher, Bach (GEB)

Best of luck its a very fun path learning things and then applying what you've learned!

thread

pufuwozuJul 2012

I started reading this comment and immediately knew you were talking about Pattern Calculus. Awesome to see someone else interested in the idea.

I live a couple of blocks over from UTS and went to a programming language event there. I only found out about pattern calculus after talking to Barry Jay. Turns out UTS students have been working on an implementation, called Bondi:

http://bondi.it.uts.edu.au/

If you're interested in playing around, Eric Torreborre posted some of the UTS lab tutorials online and some of his solutions:

https://github.com/etorreborre/bondi-tutorial

thread