I now want to show, concretely, how pattern matching works in the Newspeak extension I mentioned in an earlier post. The material from here on is more or less stolen from Felix Geller’s thesis.
Here are some simple pattern literals
<1> // matches 1
<‘a’> // matches ‘a’
< _> // matches anything
Each of these is simply a sugared syntax for an instance of class Pattern (or some subclass thereof). Pattern supports a protocol for matching. When a pattern is asked to match an object, it invokes the object’s match: method, sending itself (the pattern) as the argument. It’s then up to the the match: method to decide if the pattern is something that matches the object. This is somewhat similar to how extractors work in Scala; you should be able to see that such a protocol preserves data abstraction.
Any class can implement matching logic as needed, just as any class can declare support for an interface in a statically typed setting.
Patterns support methods that correspond to combinators, such as
p1 | p2 // matches anything that either p1 or p2 matches
p1 & p2 // matches whatever both p1 and p2 match
p not // matches if p doesn’t
p => actionBlock // matches if p matches; if so, execute actionBlock
As a simple example
fib: n = (
n case: < 1> | < 2> => [^n-1]
otherwise: [^(fib: n-1) + (fib: n-2)]
)
The method case:otherwise: is defined in Object. It takes a pattern as its first argument, and a closure as its second. If the pattern does not match the receiver, the closure is invoked .
In our example < 1 > | < 2 > matches 1 or 2, as you expect. < 1 > | < 2 > => [^n-1] matches 1 or 2 as well; if that succeeded, it will invoke the closure [^n-1]. Evaluating the closure [^n-1] will cause the enclosing fib: method to return with the result n-1. So fib: 1 yields 0, and fib: 2 yields 1, as expected. For k > 2, fib:k yields (fib: n-1) + (fib: n-2).
Note: much of the examples below are derived from the Scala extractor paper.
Here are some other pattern literals, known as keyword patterns:
< num: 1> // a keyword pattern (user-defined)
< multiply: left by: < num: 1>> // nested patterns - this is where you win over visitors
A keyword pattern literal evaluates to an instance of KeywordPattern, a subclass of Pattern. A keyword pattern literal specifies a method name (such as num: in the first example, and multiply:by: in the second); the resulting keyword pattern object supports a method of the same name. For example < num: 1> responds to num:. What this method does is check if its argument matches the argument specified in the pattern literal - in our example, checking that it equals 1. If the pattern specifies a nested pattern literal as an argument, the method matches the argument against that pattern recursively.
An object that wants to match < num: 1> will define its match: method thus:
match: p = (^p num: 1)
Similarly, < multiply:< _> by: 1> supports a method multiply:by: that tests its arguments to see if they match the pattern. In this example, the first argument of multiply:by: would be recursively matched against the nested pattern < _> (which always succeeds) and the second argument would be tested for equality against 1.
Imagine a class hierarchy for arithmetic expressions. There are several kinds of terms: numbers, products of terms, and likely other things, like variables. Assume numbers match patterns of the form < num: n> for some n, and assume products are represented using a class Product with two slots for the product term’s subtrees, operand1 and operand2. Instances of Product will match patterns of the form < multiply: x by: y > for some x and y. The match: method for Product can be written as
match: pat = (
^pat multiply: operand1 by: operand2
)
The result of a match is a binding. This is an object that can tell you what the original object being matched was and how it matched - what values are associated with the various names specified in the pattern.
We’ll use pattern matching to define a method simplify: that transforms product terms of the form X*1 to X.
simplify: expr = (
^expr case: < multiply: ?x by: < num: 1>> => [x]
otherwise: [expr].
)
If expr is a product of some term t and the number 1, simplify: will return t, otherwise it will return expr.
Note: The syntax ?id is allowed inside pattern literals and will make the corresponding matched value matched available under the name id in other parts of the pattern. How? Read the tech report.
How does x end up available in the closure? Well, the => combinator manipulates the scope of the closure to ensure that the desired accessors are available to it. Groovy programmers will recognize this idea, as will Smalltalkers familiar with GLORP. If it turns your stomach - well, I had reservations at first too, but all power corrupts, and dynamic languages give you a lot of power :-). This kind of trick must be used with great restraint. In Newspeak, the object capability model is intended to give us control over who can access the required reflective capabilities, so it is not a free-for-all.
The only language extension needed here are the pattern literals. All the rest is library code. We could dispense with the language extension entirely and just use the library, but things would be slightly more awkward - say
Pattern multiply: (Pattern variable: #x) by: (Pattern num: 1)
instead of
< multiply: ?x by:< num: 1>>
In principle, you could add such a library to a mainstream language such as Java. Of course, the typechecking, the absence of doesNotUnderstand:, the inability to add methods dynamically etc. would be crippling to the point where you wouldn’t really want to pursue the idea.
There is a lot of potential for refinement here. Patterns can be used as first class queries in LINQ like APIs that connect to databases or Prolog style rule engines, for example.
Check out Felix’s work if you want to understand it all. Or wait for the updated Newspeak documentation that will accompany the next release.
Saturday, June 19, 2010
Thursday, June 03, 2010
A Nest of Classes
Nested classes, like classes and OO in general, come to us from Scandinavia. The language Beta introduced nested classes in a stunningly elegant way; Java popularized nested classes in a rather different way; and Newspeak builds on them pervasively, in a manner similar to Beta, but still distinct. In this post, I want to explore these variations on nested classes.
Traditional OO is built on classes. We note an obvious property:
(1) Classes contain methods.
Beta’s core idea is something they call a pattern. A pattern in this context has nothing to do with pattern matching as we know it in functional programming. Instead, a pattern unifies classes and methods (and types and functions and procedures, but never mind all that).
Since class = pattern = method, we can perform some substitutions on the remark given above
(2) Patterns contain patterns.
This is true in Beta, even if reading this right now, you aren’t clear what it means. Let’s do a few other substitutions of equals for equals:
(3) Classes contain classes.
(4) Methods contain classes.
(5) Methods contain methods
Item (3) gives us member classes (using Java terminology); (4) gives us local classes; and (5) gives us nested procedures, like Pascal used to have.
The nice things is that all of these features come for free! This is the power of composition. Furthermore, they are all governed by consistent rules, because they fall out of the same definitions.
One can push this even further - the language gBeta unifies patterns with mixins as well.
But wait - isn’t this going a bit too far? After all, there is abundant evidence suggesting that the distinction between nouns and verbs, or objects and procedures, is fundamental to human cognition. I know some very good (former) Beta programmers who confess that the uniformity can be confusing.
That is why Newspeak doesn’t unify classes and methods this way. However, thinking about the unification is valuable even if you don’t go through with it. It will help you produce a consistent and flexible result.
To be fair, there is a school of thought that argues that different things must be kept very different, and that they can then be specialized so that they are finely tuned to a specific need. The Modula-3 report made this point nicely with the following quote:
Look into any carpenter's tool-bag and see how many different hammers, chisels, planes and screw-drivers he keeps there - not for ostentation or luxury, but for different sorts of jobs.
- Robert Graves and Alan Hodges
Language design isn't carpentry however.
Beta’s ideas served as inspiration for Java’s nested classes. However, Java is a language in the mainstream tradition, with a philosophy closer to Modula than to Beta. When nested classes were being added to Java, Java already had distinct concepts for classes, methods and variables, and even distinct namespaces for them. This makes it hard to ensure that the rules are uniform and consistent. One tries; some of the smartest people I’ve ever met recommend building tables and cross checking systematically - but really, it is incredibly difficult.
Hence, the rules for nested classes are quite different from those for methods nested in classes for example. Consider the effect of a modifier such as final. A final class means one thing (a class that may not be subclassed) a final variable another (an immutable variable) and a final method yet another (a method that may not be overridden).
One of the most important discrepancies has to do with the instance vs. static distinction. A static variable is property of a class, but an instance variable is a property of a specific instance. Conceptually, this is true of methods as well - instance methods are considered a property of an object. That is why they must be dynamically bound - two objects might have different methods. Therein lies the power of object-oriented programming. However, in Java, a nested class is never a property of an individual object. This is different from Beta (and Newspeak) and carries major implications.
If a class is a property of an object, then virtual classes arise naturally. Furthermore, the power of polymorphism applies to classes as well. Since we can abstract over objects, we can abstract over their members; those members are typically methods, which is why object oriented and functional programming are not as a different as some would make them out to be. If the members of an object (rather than a class) can be classes, we can abstract over classes. This can help avoid the difficulties that dependency injection frameworks try so awkwardly to address. We’ve realized these benefits in Newspeak.
Altogether, lack of uniformity prevents a language’s constructs from composing together easily to produce an exponential takeoff in expressivity. Instead, the rules themselves compose, yielding an exponential takeoff in interactions between the them. That is why simplicity is so crucial in language design.
Newspeak obtains its power not from unifying classes and methods, but from unifying the mechanisms by which they are referenced. Names are always treated the same - as properties of objects, which are therefore late bound and subject to override by a single set of rules.
a. A name refers to the nearest lexically enclosing declaration of that name, if there is one; otherwise, it refers to a declaration inherited from the immediately surrounding classes’ superclass.
b. Every declaration is subject to override; if you override a declaration in a subclass, it takes effect wherever the overridden declaration is used.
That’s it. Note that for a name defined by an enclosing class to be visible, it must be declared in the lexically surrounding environment; it isn’t enough for it to be inherited. You must be able to see the declaration in the surrounding classes. If you don’t see it, it isn’t there.
This is deliberate, and different from the rules you may know from Java (assuming you ever figured out what those really are) or even Beta. One advantage of this rule is that you cannot capture a name referred to in a nested class when you add a member to a superclass.
From these very simple rules (and the lack of a global namespace) we get virtual classes, mixins, class hierarchy inheritance, and powerful modularity, as I’ve described in a number of forums.
There is the small issue of specifying this behavior precisely, and beyond that, the small matter of making it work. These are not totally trivial. The spec describes the rules. As for the implementation, I plan to describe it in a paper; in the meantime, the source is out there. You want to look at changes we’ve made to the Squeak Interpreter, in particular the pushImplicitReceiver byte code as implemented in Squeak’s Interpreter class.
I hope I have convinced you that nested classes are at once simpler and more powerful than you might have imagined. As always, keeping language design simple results in a more powerful language.
Traditional OO is built on classes. We note an obvious property:
(1) Classes contain methods.
Beta’s core idea is something they call a pattern. A pattern in this context has nothing to do with pattern matching as we know it in functional programming. Instead, a pattern unifies classes and methods (and types and functions and procedures, but never mind all that).
Since class = pattern = method, we can perform some substitutions on the remark given above
(2) Patterns contain patterns.
This is true in Beta, even if reading this right now, you aren’t clear what it means. Let’s do a few other substitutions of equals for equals:
(3) Classes contain classes.
(4) Methods contain classes.
(5) Methods contain methods
Item (3) gives us member classes (using Java terminology); (4) gives us local classes; and (5) gives us nested procedures, like Pascal used to have.
The nice things is that all of these features come for free! This is the power of composition. Furthermore, they are all governed by consistent rules, because they fall out of the same definitions.
One can push this even further - the language gBeta unifies patterns with mixins as well.
But wait - isn’t this going a bit too far? After all, there is abundant evidence suggesting that the distinction between nouns and verbs, or objects and procedures, is fundamental to human cognition. I know some very good (former) Beta programmers who confess that the uniformity can be confusing.
That is why Newspeak doesn’t unify classes and methods this way. However, thinking about the unification is valuable even if you don’t go through with it. It will help you produce a consistent and flexible result.
To be fair, there is a school of thought that argues that different things must be kept very different, and that they can then be specialized so that they are finely tuned to a specific need. The Modula-3 report made this point nicely with the following quote:
Look into any carpenter's tool-bag and see how many different hammers, chisels, planes and screw-drivers he keeps there - not for ostentation or luxury, but for different sorts of jobs.
- Robert Graves and Alan Hodges
Language design isn't carpentry however.
Beta’s ideas served as inspiration for Java’s nested classes. However, Java is a language in the mainstream tradition, with a philosophy closer to Modula than to Beta. When nested classes were being added to Java, Java already had distinct concepts for classes, methods and variables, and even distinct namespaces for them. This makes it hard to ensure that the rules are uniform and consistent. One tries; some of the smartest people I’ve ever met recommend building tables and cross checking systematically - but really, it is incredibly difficult.
Hence, the rules for nested classes are quite different from those for methods nested in classes for example. Consider the effect of a modifier such as final. A final class means one thing (a class that may not be subclassed) a final variable another (an immutable variable) and a final method yet another (a method that may not be overridden).
One of the most important discrepancies has to do with the instance vs. static distinction. A static variable is property of a class, but an instance variable is a property of a specific instance. Conceptually, this is true of methods as well - instance methods are considered a property of an object. That is why they must be dynamically bound - two objects might have different methods. Therein lies the power of object-oriented programming. However, in Java, a nested class is never a property of an individual object. This is different from Beta (and Newspeak) and carries major implications.
If a class is a property of an object, then virtual classes arise naturally. Furthermore, the power of polymorphism applies to classes as well. Since we can abstract over objects, we can abstract over their members; those members are typically methods, which is why object oriented and functional programming are not as a different as some would make them out to be. If the members of an object (rather than a class) can be classes, we can abstract over classes. This can help avoid the difficulties that dependency injection frameworks try so awkwardly to address. We’ve realized these benefits in Newspeak.
Altogether, lack of uniformity prevents a language’s constructs from composing together easily to produce an exponential takeoff in expressivity. Instead, the rules themselves compose, yielding an exponential takeoff in interactions between the them. That is why simplicity is so crucial in language design.
Newspeak obtains its power not from unifying classes and methods, but from unifying the mechanisms by which they are referenced. Names are always treated the same - as properties of objects, which are therefore late bound and subject to override by a single set of rules.
a. A name refers to the nearest lexically enclosing declaration of that name, if there is one; otherwise, it refers to a declaration inherited from the immediately surrounding classes’ superclass.
b. Every declaration is subject to override; if you override a declaration in a subclass, it takes effect wherever the overridden declaration is used.
That’s it. Note that for a name defined by an enclosing class to be visible, it must be declared in the lexically surrounding environment; it isn’t enough for it to be inherited. You must be able to see the declaration in the surrounding classes. If you don’t see it, it isn’t there.
This is deliberate, and different from the rules you may know from Java (assuming you ever figured out what those really are) or even Beta. One advantage of this rule is that you cannot capture a name referred to in a nested class when you add a member to a superclass.
From these very simple rules (and the lack of a global namespace) we get virtual classes, mixins, class hierarchy inheritance, and powerful modularity, as I’ve described in a number of forums.
There is the small issue of specifying this behavior precisely, and beyond that, the small matter of making it work. These are not totally trivial. The spec describes the rules. As for the implementation, I plan to describe it in a paper; in the meantime, the source is out there. You want to look at changes we’ve made to the Squeak Interpreter, in particular the pushImplicitReceiver byte code as implemented in Squeak’s Interpreter class.
I hope I have convinced you that nested classes are at once simpler and more powerful than you might have imagined. As always, keeping language design simple results in a more powerful language.