For the past 5 years or so, I (like many others) have argued that Javascript is the assembly language of the internet platform. Over this period, some of the obstacles that limit the applicability of said platform have been slowly pushed aside. Things like client side storage, or decent performance.
However, Javascript remains a seriously limited language for platform implementation. Here are some of the problems.
Concurrency primitives. There aren’t any. Now I really should be thankful for that, as the last thing I want is another shared-state concurrency threading model a la Java. And yet, ingrate that I am, I remain dissatisfied. Yes, I can write my own scheduler to provide pseudo-concurrency, but there are no primitives that let me find out how much true concurrency is available and to let me use it. Nor is there any efficient way for me to preempt an activity.
This lack of appropriate primitives for platform construction is a recurring theme. Take serialization for example. If I need to write a serializer that can incrementally store and retrieve arbitrary objects (say, because I want to implement orthogonal persistence) , I hit difficulties with things like closures. A closure in Javascript is a black box. This makes sense most of the time - but not for the system designer. One wants mechanisms that permit manipulation of the structure of all program elements - closures, prototypes, what have you.
Of course, the challenge is to do this while preserving security. Not everyone should be able to do this - but a program should be able to do it on its own objects, for example.
Another, somewhat related, problem area is stack manipulation. I want to implement an efficient debugger with fix-and-continue debugging for example. Or resumable exceptions.
Weak pointers are another problem. For example, Newspeak mixins need to track all their invocations, so that when a mixin definition is modified, all classes derived from can be updated. You’d like to use a weak collection of these mixin invocations for that purpose.
I’ve never been happy with the approach that says that the only true encapsulation mechanism in the language is closures. I find that very low level. I want objects that can hide their internals directly (private members) - and of course, I want a mechanism to get around that in some ways, so I can program the system in itself (and write things like serialization).
I miss doesNotUnderstand:, which I can emulate by going through certain hoops. There is work going on to alleviate this with proxys but I don’t see them doing what I really want. I can however, use them to implement a mechanism that does.
All of this may be too much to ask of a language where false can sometimes be interpreted as true, and where equality is non-transitive. But it isn’t too much to ask for the backbone of internet programming.
Tangent: the occasional truthiness of false is a case study in the pitfalls of language design. It stems from the interaction of two bad decisions. First, we have the implicit coercion of any type to a boolean - a nasty C legacy. Then we have primitive types, which leads to (non-transparent) autoboxing. Since any object is truthy, and autoboxing false creates an object, you can end up with an automatic, hidden conversion that interprets false as true.
I know that there is a lot of ongoing work to resolve this on the ECMAScript standards committee, whose members seem well aware of many of these issues. The timeline for addressing these problems is however, rather depressing. Between the time it takes to revise a standard, and the time it takes for it to be implemented and widely adopted (so you can actually rely on it) we may see these things fixed by the early 2020s (I kid you not).
Will that make Javascript a language a human should program in? I doubt it, but that shouldn’t be the goal. The goal should be to provide a foundation that will help in building more attractive languages on top of Javascript and the browser.
In this vein, work continues on Newspeak for the browser. We have a pretty solid Newspeak-to-Javascript compiler, though we still need to improve performance and add key platform functionality. At some point, I hope we can release this.
The vision for the Ministry of Truthiness goes beyond just a compiler of course - we want Hopscotch as well of course. Calling the DOM API from Newspeak is possible of course, but not really attractive. We also want the IDE in the browser as well. At least as much of it as possible - debugging might require using a browser extension or something due to the difficulties cited above.
Doing all this on top of Javascript has proven tedious and frustrating, and I hope things improve more quickly in the future; but we will get there in time.
Sunday, March 20, 2011
Monday, February 28, 2011
The Ministry of Nesting & Testing
Unit testing was introduced to the OO world by Kent Beck, in his seminal work on SUnit, the Smalltalk unit testing framework. Other languages have introduced their own unit testing frameworks following SUnit’s lead.
Tangent: Unit testing was part of the overall introduction of extreme programming/agile development, which is just one of the major trends Smalltalk has brought to the world. Along with refactoring (which we all know can’t be done without static types, which is why it was invented in a dynamically typed language), IDEs, reflective OO APIs, GUI builders, pop-up menus and bitmapped GUIs in general. Smalltalk is the veritable Prometheus of OO, and its destiny seems not dissimilar.
Newspeak started out with an adaptation of SUnit, NSUnit, which is what you’ll find in the public release. It has a rather nice Hopscotch based GUI integrated into the IDE, but we always felt we could improve upon it.
Minitest is our revised unit testing framework, which we’ve been using since, oh, mid-2010 or so. Minitest takes the opportunity to rationalize the way we structure unit tests and takes advantage of Newspeak’s support for nesting to make things simpler and easier to use.
Minitest was designed by Vassili Bykov, and the examples below are shamelessly lifted from the superb documentation Vassili wrote for the Minitest class.
In Minitest, you define a testing module, that is designed to test a particular interface (not a particular implementation). To run tests, one needs to feed the testing module with the particular implementation(s) that one wishes to test. A test configuration module does just that. Newspeak naturally enforces this separation of interface and implementation.
The testing module class’s factory typically takes three arguments: the Newspeak platform, the testing framework (a Minitest instance) and a factory for the object under test.
The example shows a hypothetical (and rather simplistic) module definition for testing lists. I’m sure all readers of this blog are fluent in Newspeak, but just in case, the module definition has a factory method that takes the 3 parameters mentioned above: platform (the Newspeak platform, from which all kinds of generally useful libraries might be obtained), minitest (an instance of Minitest, naturally) and listClass, a factory that will produce lists for us to test.
Nested inside the testing module is a test context (aka test fixture) class ListTests, inside of which you write your tests. Test methods are identified by the convention that their names begin with test. Each test will be executed in a test context; that is, for each test method being run, Minitest will instantiate a fresh ListTests object. That is why ListTests is called a test context - it provides a context for a single test.
It is common to define test context classes like ListTests as subclasses of the class TestContext defined by the Minitest framework, but that is not essential. TestContext provides useful methods like deny:, so it is convenient to use it. However, what identifies ListTests as a test context is the marker class method TEST_CONTEXT.
Minitest will do its work by examining the nested classes of the test module and seeing which are test contexts (that is, which have a class method named TEST_CONTEXT). For each test context tc, Minitest will list all its test methods (the ones with names beginning with test) and for each of those, it will instantiate tc and call the selected method on it, gathering data on success or failure.
Minitest does away with concepts like TestResource. that are typically used to hold data for tests.
In the simple case above, the data for the test gets created by the instance initializer of ListTests . However, what if the data for the test needs to be shared among multiple tests (say, because it is expensive to create)?
As an example, suppose we want to test a compiler, and setting up the compiler is relatively costly.
Minitest leverages Newspeak’s nested structure in these cases. A test context (StatementTests above) does not have to be a direct nested class of the test module. Instead, we can nest it more deeply inside another nested class (CompilerHolder). That nested class will serve to hold any state that we want to share among multiple tests - in our case, an instance of the compiler, which it will create and store as part of its initialization.
As you can see there is no need for a special setUp method or a test resource class. Newspeak’s nesting structure and built-in instance initializers take care of all that. If the shared resource is just an object in memory, then it will also be disposed of via garbage collection after the test is run. Of course, some resources cannot be just garbage collected. In that case, one should define a method named cleanUp in the test context class.
As mentioned in the beginning of the post, we need a test configuration to run the tests, as the test module definition is always parametric with respect to any implementation that we would actually test.
A test configuration module is defined by a top level class with the factory method
packageTestsUsing: ideNamespace
The factory takes a namespace object that should provide access to the testing module declaration and to any concrete classes or objects we want to test. This arrangement is very similar to how we package applications from within the IDE.
The method testModulesUsingPlatform:minitest: must be provided by the configuration. It will be called by Minitest to produce a set of testing modules, each of which will be processed by the framework as outlined above (i.e., searched for test contexts to be run). In the example, only one test module is returned, but if we wanted to process multiple List implementations (say ArrayList as well as LinkedList) we could write:
The IDE recognizes test configurations based on the name of the factory method - that is, a class with a class method packageTestsUsing: is considered a test configuration, and the IDE will provide a run tests link in the (upper right hand corner) class browser in that case, as shown in the screenshot below (click on it to enlarge).
Clicking on the link will call the packageTestsUsing: method on the class with an argument representing the IDE’s namespace, and feed the results into Minitest.
This is all you need to know to use Minitest. Actually, it’s considerably more than what you need to know, as I’ve also explained how a bit about how the framework goes about its business.
It is worth noting how Minitest cleanly breaks down the multiple roles an SUnit TestCase has. The definition of a set of tests is done by a test context. The actual configuration is done a test configuration. And the actual command to run a specific test (the thing that should be called TestCase) is not the user’s concern anymore - the test framework handles it but need not expose it. In SUnit these three roles are conjoined. Perhaps this is why I never really felt comfortable with SUnit.
Likewise, no need to worry over test resources and special set up methods. The net result is a framework that is very easy to use and simple to understand.
It’s intriguing to note that one could actually structure a Java unit testing framework this way; we rely on introspection, interfaces and nested (inner) classes. However, it is not natural to do so in Java. Nested classes in Java are usually (and often rightly) regarded a trap to be avoided. A design like Minitest is much more likely to crop up in a setting where nesting is idiomatic, like Newspeak. Language influences thought - or lack of thought, as the case may be.
Tangent: Unit testing was part of the overall introduction of extreme programming/agile development, which is just one of the major trends Smalltalk has brought to the world. Along with refactoring (which we all know can’t be done without static types, which is why it was invented in a dynamically typed language), IDEs, reflective OO APIs, GUI builders, pop-up menus and bitmapped GUIs in general. Smalltalk is the veritable Prometheus of OO, and its destiny seems not dissimilar.
Newspeak started out with an adaptation of SUnit, NSUnit, which is what you’ll find in the public release. It has a rather nice Hopscotch based GUI integrated into the IDE, but we always felt we could improve upon it.
Minitest is our revised unit testing framework, which we’ve been using since, oh, mid-2010 or so. Minitest takes the opportunity to rationalize the way we structure unit tests and takes advantage of Newspeak’s support for nesting to make things simpler and easier to use.
Minitest was designed by Vassili Bykov, and the examples below are shamelessly lifted from the superb documentation Vassili wrote for the Minitest class.
In Minitest, you define a testing module, that is designed to test a particular interface (not a particular implementation). To run tests, one needs to feed the testing module with the particular implementation(s) that one wishes to test. A test configuration module does just that. Newspeak naturally enforces this separation of interface and implementation.
The testing module class’s factory typically takes three arguments: the Newspeak platform, the testing framework (a Minitest instance) and a factory for the object under test.
class ListTesting usingPlatform: platform minitest: minitest listClass: listClass = (
|
private TestContext = minitest TestContext.
private List = listClass.
|
)(
class ListTests = TestContext (
| list = List new. |
) (
testAddition = (
list add: 1.
assert: (list includes: 1)
)
testRemoval = (
list add: 1; remove: 1.
deny: (list includes: 1)
)
) : ( TEST_CONTEXT = () )
)
The example shows a hypothetical (and rather simplistic) module definition for testing lists. I’m sure all readers of this blog are fluent in Newspeak, but just in case, the module definition has a factory method that takes the 3 parameters mentioned above: platform (the Newspeak platform, from which all kinds of generally useful libraries might be obtained), minitest (an instance of Minitest, naturally) and listClass, a factory that will produce lists for us to test.
Nested inside the testing module is a test context (aka test fixture) class ListTests, inside of which you write your tests. Test methods are identified by the convention that their names begin with test. Each test will be executed in a test context; that is, for each test method being run, Minitest will instantiate a fresh ListTests object. That is why ListTests is called a test context - it provides a context for a single test.
It is common to define test context classes like ListTests as subclasses of the class TestContext defined by the Minitest framework, but that is not essential. TestContext provides useful methods like deny:, so it is convenient to use it. However, what identifies ListTests as a test context is the marker class method TEST_CONTEXT.
Minitest will do its work by examining the nested classes of the test module and seeing which are test contexts (that is, which have a class method named TEST_CONTEXT). For each test context tc, Minitest will list all its test methods (the ones with names beginning with test) and for each of those, it will instantiate tc and call the selected method on it, gathering data on success or failure.
Minitest does away with concepts like TestResource. that are typically used to hold data for tests.
In the simple case above, the data for the test gets created by the instance initializer of ListTests . However, what if the data for the test needs to be shared among multiple tests (say, because it is expensive to create)?
As an example, suppose we want to test a compiler, and setting up the compiler is relatively costly.
class CompilerTesting usingPlatform: platform
minitest: minitest
compilerClass: compilerClass = (
| Compiler = compilerClass. | )
(
class CompilerHolder = (
| compiler = Compiler configuredInAParticularWay. |
)(
class StatementsTests ( ...) (....): ( TEST_CONTEXT = ())
)
)
Minitest leverages Newspeak’s nested structure in these cases. A test context (StatementTests above) does not have to be a direct nested class of the test module. Instead, we can nest it more deeply inside another nested class (CompilerHolder). That nested class will serve to hold any state that we want to share among multiple tests - in our case, an instance of the compiler, which it will create and store as part of its initialization.
As you can see there is no need for a special setUp method or a test resource class. Newspeak’s nesting structure and built-in instance initializers take care of all that. If the shared resource is just an object in memory, then it will also be disposed of via garbage collection after the test is run. Of course, some resources cannot be just garbage collected. In that case, one should define a method named cleanUp in the test context class.
As mentioned in the beginning of the post, we need a test configuration to run the tests, as the test module definition is always parametric with respect to any implementation that we would actually test.
A test configuration module is defined by a top level class with the factory method
packageTestsUsing: ideNamespace
The factory takes a namespace object that should provide access to the testing module declaration and to any concrete classes or objects we want to test. This arrangement is very similar to how we package applications from within the IDE.
class ListTestingConfiguration packageTestsUsing: ideNamespace = (
|
private ListTesting = ideNamespace ListTesting.
private Collections = ideNamespace Collections.
| )( ‘required’
testModulesUsingPlatform: platform minitest: minitest = (
^{ ListTesting usingPlatform: platform
minitest: minitest
listClass: (Collections usingPlatform: platform) LinkedList.
}
)
)
The method testModulesUsingPlatform:minitest: must be provided by the configuration. It will be called by Minitest to produce a set of testing modules, each of which will be processed by the framework as outlined above (i.e., searched for test contexts to be run). In the example, only one test module is returned, but if we wanted to process multiple List implementations (say ArrayList as well as LinkedList) we could write:
class ListTestingConfiguration packageTestsUsing: ideNamespace = (
|
private ListTesting = ideNamespace ListTesting.
private Collections = ideNamespace Collections.
| )( ‘required’
testModulesUsingPlatform: platform minitest: minitest = (
| collections = Collections using: platform. |
^{ ListTesting usingPlatform: platform
minitest: minitest
listClass: collections LinkedList.
ListTesting usingPlatform: platform
minitest: minitest
listClass: collections ArrayList.
}
)
)
The IDE recognizes test configurations based on the name of the factory method - that is, a class with a class method packageTestsUsing: is considered a test configuration, and the IDE will provide a run tests link in the (upper right hand corner) class browser in that case, as shown in the screenshot below (click on it to enlarge).
Clicking on the link will call the packageTestsUsing: method on the class with an argument representing the IDE’s namespace, and feed the results into Minitest.
This is all you need to know to use Minitest. Actually, it’s considerably more than what you need to know, as I’ve also explained how a bit about how the framework goes about its business.
It is worth noting how Minitest cleanly breaks down the multiple roles an SUnit TestCase has. The definition of a set of tests is done by a test context. The actual configuration is done a test configuration. And the actual command to run a specific test (the thing that should be called TestCase) is not the user’s concern anymore - the test framework handles it but need not expose it. In SUnit these three roles are conjoined. Perhaps this is why I never really felt comfortable with SUnit.
Likewise, no need to worry over test resources and special set up methods. The net result is a framework that is very easy to use and simple to understand.
It’s intriguing to note that one could actually structure a Java unit testing framework this way; we rely on introspection, interfaces and nested (inner) classes. However, it is not natural to do so in Java. Nested classes in Java are usually (and often rightly) regarded a trap to be avoided. A design like Minitest is much more likely to crop up in a setting where nesting is idiomatic, like Newspeak. Language influences thought - or lack of thought, as the case may be.
Sunday, January 23, 2011
Maybe Monads Might Not Matter
This post isn’t really about the Maybe Monad of course. It is more focused on the State Monad, but I have a weakness for alliteration.
What do
space suits
nuclear waste containers
romantic conquests
monsters
macros
containers
conversations
have in common? They’ve all been used as metaphors for monads.
Last time I looked, the Haskell wiki listed 29 tutorials on the subject, and that is where all these allusions come from.
Such a wealth of explanatory fauna demands its own (meta-)explanation. Maybe monads are so wildly popular that there is monadic gold rush to cash in on the monad education and training market. And yet, the long-awaited landmark tome, “Category Theory for Dummies in 21 days and 1001 nights” is nowhere to be found.
Tangent: There is of course, Benjamin Pierce's delightfully slim book on the topic which is as close to a gentle introduction as one can come.
Could it just be that people just have a hard time understanding monads? If so, what are the prospects of mass adoption? Or making Just(something) out of Nothing am I?
By now you realize that if monads were a stock, I’d be shorting it. I’m going to go get myself in a huge amount of trouble now, just as I did when I took a hideously pragmatic tack on continuations some years ago.
The most important practical contribution of monads in programming is, I believe, the fact that they provide a mechanism to interface pure functional programming to the impure dysfunctional world.
The thing is, you don’t really need them for that. Just use actors. Purely functional actors can interact with the stateful world, and this has been known since before Haskell was even conceived.
Tangent: Before you crucify me for being so narrow minded, pray consider the mitigating circumstance that I have used the words "practical" and "pure functional programming" in the same sentence. There are many who regard that, rather than my disrespectful attitude toward monads, as grounds for my institutionalization.
Some kind soul will doubtless point out to me how you can view actors as monads or some such. Be that as it may, it is beside the point. You can invent, build and most importantly, use, actors without ever mentioning monads. Carl Hewitt and his students did that decades ago.
Tangent: I have to say how amazing that is. Actors were first conceived by Hewitt in 1973(!), and Gul Agha's thesis has been around for 25 years. I firmly believe actors are the best answer to our concurrency problems, but that is for another post.
You can write an actor in a purely functional language, and have it send messages to file systems, databases or any other other stateful actor. Because the messages are sent asynchronously, you never see the answer in the same activation (aka turn) of the actor, so the fact that these actors are stateful and may give different answers to the same question at different times does not stain your precious snow white referential transparency with its vulgar impurity. This is pretty much what you do with a monad as well - you bury the stateful filth in a well marked shallow grave and whistle past it.
Of course, your troubles are by no means over. Actors or monads, the state is out there and you will have to reason about it somewhere. But better you reason about it in a well bounded shallow grave than in C.
What is important to me is that the notion of actors is intuitive (a pesky property of Dijkstra’s hated anthropomorphisms, like self) for many people. Yes, there are many varieties of actors and I have my preferences - but I’ll take any one of them over a sheaf of categories.
Speaking of those preferences, look at the E programming language (I often point at Mark Miller’s PhD thesis) or on AmbientTalk. I would like to have something similar in Newspeak (and in its hypothetical functional subsets, Avarice and Sloth).
Of course, there is much to be said for a programming culture that excludes anyone without at least the potential of a PhD. Indeed, if you can surround yourself with such people, you can do amazing things with just Java, C++ and Python (though they will still be more productive if they have the good taste to use something nicer). So perhaps the true value of monads lies in their exclusionary nature.
Nevertheless, there is more work to be done than some small, celebrated priesthood can or will do all by itself. There is real value in functional programming in some contexts, and it needs to integrate with stateful programming. Actors provide a model that is much easier for most humans to relate to.
What do
space suits
nuclear waste containers
romantic conquests
monsters
macros
containers
conversations
have in common? They’ve all been used as metaphors for monads.
Last time I looked, the Haskell wiki listed 29 tutorials on the subject, and that is where all these allusions come from.
Such a wealth of explanatory fauna demands its own (meta-)explanation. Maybe monads are so wildly popular that there is monadic gold rush to cash in on the monad education and training market. And yet, the long-awaited landmark tome, “Category Theory for Dummies in 21 days and 1001 nights” is nowhere to be found.
Tangent: There is of course, Benjamin Pierce's delightfully slim book on the topic which is as close to a gentle introduction as one can come.
Could it just be that people just have a hard time understanding monads? If so, what are the prospects of mass adoption? Or making Just(something) out of Nothing am I?
By now you realize that if monads were a stock, I’d be shorting it. I’m going to go get myself in a huge amount of trouble now, just as I did when I took a hideously pragmatic tack on continuations some years ago.
The most important practical contribution of monads in programming is, I believe, the fact that they provide a mechanism to interface pure functional programming to the impure dysfunctional world.
The thing is, you don’t really need them for that. Just use actors. Purely functional actors can interact with the stateful world, and this has been known since before Haskell was even conceived.
Tangent: Before you crucify me for being so narrow minded, pray consider the mitigating circumstance that I have used the words "practical" and "pure functional programming" in the same sentence. There are many who regard that, rather than my disrespectful attitude toward monads, as grounds for my institutionalization.
Some kind soul will doubtless point out to me how you can view actors as monads or some such. Be that as it may, it is beside the point. You can invent, build and most importantly, use, actors without ever mentioning monads. Carl Hewitt and his students did that decades ago.
Tangent: I have to say how amazing that is. Actors were first conceived by Hewitt in 1973(!), and Gul Agha's thesis has been around for 25 years. I firmly believe actors are the best answer to our concurrency problems, but that is for another post.
You can write an actor in a purely functional language, and have it send messages to file systems, databases or any other other stateful actor. Because the messages are sent asynchronously, you never see the answer in the same activation (aka turn) of the actor, so the fact that these actors are stateful and may give different answers to the same question at different times does not stain your precious snow white referential transparency with its vulgar impurity. This is pretty much what you do with a monad as well - you bury the stateful filth in a well marked shallow grave and whistle past it.
Of course, your troubles are by no means over. Actors or monads, the state is out there and you will have to reason about it somewhere. But better you reason about it in a well bounded shallow grave than in C.
What is important to me is that the notion of actors is intuitive (a pesky property of Dijkstra’s hated anthropomorphisms, like self) for many people. Yes, there are many varieties of actors and I have my preferences - but I’ll take any one of them over a sheaf of categories.
Speaking of those preferences, look at the E programming language (I often point at Mark Miller’s PhD thesis) or on AmbientTalk. I would like to have something similar in Newspeak (and in its hypothetical functional subsets, Avarice and Sloth).
Of course, there is much to be said for a programming culture that excludes anyone without at least the potential of a PhD. Indeed, if you can surround yourself with such people, you can do amazing things with just Java, C++ and Python (though they will still be more productive if they have the good taste to use something nicer). So perhaps the true value of monads lies in their exclusionary nature.
Nevertheless, there is more work to be done than some small, celebrated priesthood can or will do all by itself. There is real value in functional programming in some contexts, and it needs to integrate with stateful programming. Actors provide a model that is much easier for most humans to relate to.
Saturday, December 11, 2010
Reflecting on Functional Programming
In this post, I wanted to make a case for reflection in the context of pure functional programming. I don’t know that pure functional languages should be different than other languages in this regard, but in practice they are: they generally do not have reflection support.
To demonstrate the utility of reflection, I’m going to revisit one of my favorite examples, parser combinators. In particular, we’ll consider how to implement executable grammars. Executable grammars are a special flavor of a parser combinator library that allows semantic actions to be completely separated from the actual grammar. I introduced executable grammars as part of the Newspeak project.
Consider the following grammar:
In Newspeak, we’d write:
Now let’s define some semantic action, say, creating an AST. The Newspeak library let’s me do this in a subclass, by overriding the code for the production thus:
No prior parser combinator library allowed me to achieve a similar separation of grammar and semantic action. In particular, I don’t quite see how to accomplish this in a functional language.
In the functional world, I would expect one function would define the actual grammar, and another would perform the semantic actions (in our example, build the AST). The latter function would transform the result of basic parsing as defined by the grammar, producing an AST as the result. We’d use pattern matching to define this function. I’d want to write something like:
where makeAST maps a concrete parse tree into an abstract one. Which in this case looks pretty easy.
The question arises: where did the patterns ifStatement, returnStatement, number and identifier come from?
Presumably, our parser combinator library defined them based on our input grammar. The thing is, the library does not know the specifics of our grammar in advance. It cannot predefine data constructors for each conceivable production. Instead, it should create these data constructors dynamically each time it processes a specific grammar.
How does one create datatypes dynamically in a traditional functional language? I leave that as an exercise for the reader.
Ok, so while it is clear that creating datatypes on the fly would be very helpful here, it is also clear that it isn’t easy to do in the context of such languages. How would you describe the type of the library? The datatype it returns is created per grammar, and depends on the names of the grammar production functions. Not easy to characterize via Hindley-Milner. And yet, once the library created the datatype, we actually could utilize it in writing type safe clients.
Instead, our library will probably generate values of some generic datatype for parse trees. A possible representation is a pair, consisting of a tag of type string representing the name of the production used to compute the tree, and a list consisting of the elements of the tree, including vital information such as where in the input stream a given token was found and what string exactly represented it. We cannot elide such lexical information, because some users of our library will need it (say, pretty printers). Then I can write:
Obviously, we’ve lost the type safety of the previous version. Ironically, the inability of the language to generate types dynamically forces code to be less statically type safe.
Now ask yourself - how does our combinator library produce values of type parsetree with an appropriate tag? For each parsetree value p(tag, elements), the tag is a string corresponding to the name of the production that was used to compute p. How does our library know this tag? The tag is naturally specified via the name of the production function in the grammar. To get at it, one would need some introspection mechanism to get the name of a function at run time. Of course, no such mechanism exists in a standard functional language. It looks like you’d have to force the user to specify this information redundantly as a string, in addition to the function name (you still need the function name so that other productions can refer to it).
You might argue that we don’t really need the string tags - just return a concrete parse tree and distinguish the cases by pattern matching. However, it isn’t generally possible to tell the parse tree for a number from that for an identifier without re-parsing. Even when you can tell parse trees apart, the resulting code is ugly and inefficient, as it is repeating some of the parser’s work.
We could approach the problem via staged execution, writing meta-program that statically transformed the grammar into a program that would provide us with the nice datatype constructors I suggested in the beginning. If one goes that route, you might as well define an external DSL based on BNF or PEGs.
So, I assert that reflection is essential to this task, and dynamic type generation would be helpful as well, which would require dependent types and additional reflective functionality. However, maybe I’ve overlooked something and there is some other way to achieve the same goal. I’m sure someone will tell me - but remember, the library must not burden the user by requiring redundant information or work, it must operate independent of the specifics of a given grammar, and it must keep semantic actions entirely separate.
In any case, I think there is considerable value in adding at least a measure of introspection, and preferably full reflection, to traditional functional languages, and interesting work to be done fleshing it out.
To demonstrate the utility of reflection, I’m going to revisit one of my favorite examples, parser combinators. In particular, we’ll consider how to implement executable grammars. Executable grammars are a special flavor of a parser combinator library that allows semantic actions to be completely separated from the actual grammar. I introduced executable grammars as part of the Newspeak project.
Consider the following grammar:
statement -> ifStatement | returnStatement
ifStatement -> ‘if’ expression ‘then’ expression ‘else’ expression
returnStatement -> ‘’return’ expression
expression -> identifier | number
In Newspeak, we’d write:
class G = ExecutableGrammar ( |
(* lexical rules for identifier, number, keywords elided *)
(* The actual syntactic grammar *)
statement = ifStatement | returnStatement.
ifStatement = if, expression, then, expression, else, expression.
returnStatement = returnSymbol, expression.
expression = identifier | number.
|)()
Now let’s define some semantic action, say, creating an AST. The Newspeak library let’s me do this in a subclass, by overriding the code for the production thus:
class P = G ()(
ifStatement = (
super ifStatement wrap:[:if :e1 :then :e2 :else :e3 |
IfStatementAST if: e1 then: e2 else: e3
].
)
returnStatement = (
super returnStatement wrap:[:return :e | ReturnStatementAST return: e].
)
)
No prior parser combinator library allowed me to achieve a similar separation of grammar and semantic action. In particular, I don’t quite see how to accomplish this in a functional language.
In the functional world, I would expect one function would define the actual grammar, and another would perform the semantic actions (in our example, build the AST). The latter function would transform the result of basic parsing as defined by the grammar, producing an AST as the result. We’d use pattern matching to define this function. I’d want to write something like:
makeAST =
fun ifStatement(ifKw, e1, thenKw, e2, elseKw, e3) =
IfStatementAST(makeAST(e1), makeAST(e2), makeAST(e3)) |
fun returnStatement(returnKw, e) = ReturnsStatementAST(makeAST(e)) |
fun identifier(id) = IdentifierAST(id) |
fun number(n) = NumberAST(id)
where makeAST maps a concrete parse tree into an abstract one. Which in this case looks pretty easy.
The question arises: where did the patterns ifStatement, returnStatement, number and identifier come from?
Presumably, our parser combinator library defined them based on our input grammar. The thing is, the library does not know the specifics of our grammar in advance. It cannot predefine data constructors for each conceivable production. Instead, it should create these data constructors dynamically each time it processes a specific grammar.
How does one create datatypes dynamically in a traditional functional language? I leave that as an exercise for the reader.
Ok, so while it is clear that creating datatypes on the fly would be very helpful here, it is also clear that it isn’t easy to do in the context of such languages. How would you describe the type of the library? The datatype it returns is created per grammar, and depends on the names of the grammar production functions. Not easy to characterize via Hindley-Milner. And yet, once the library created the datatype, we actually could utilize it in writing type safe clients.
Instead, our library will probably generate values of some generic datatype for parse trees. A possible representation is a pair, consisting of a tag of type string representing the name of the production used to compute the tree, and a list consisting of the elements of the tree, including vital information such as where in the input stream a given token was found and what string exactly represented it. We cannot elide such lexical information, because some users of our library will need it (say, pretty printers). Then I can write:
makeAST =
fun parsetree(“if”, [ifKw, e1, thenKw, e2, elseKw, e3]) =
IfStatementAST(makeAST(e1), makeAST(e2), makeAST(e3)) |
fun parsetree(“return”, [returnKw, e]) = ReturnsStatementAST(makeAST(e)) |
fun parsetree(“id”,[id]) = IdentifierAST(id) |
fun parsetree(“number”,[in]) = NumberAST(in)
Obviously, we’ve lost the type safety of the previous version. Ironically, the inability of the language to generate types dynamically forces code to be less statically type safe.
Now ask yourself - how does our combinator library produce values of type parsetree with an appropriate tag? For each parsetree value p(tag, elements), the tag is a string corresponding to the name of the production that was used to compute p. How does our library know this tag? The tag is naturally specified via the name of the production function in the grammar. To get at it, one would need some introspection mechanism to get the name of a function at run time. Of course, no such mechanism exists in a standard functional language. It looks like you’d have to force the user to specify this information redundantly as a string, in addition to the function name (you still need the function name so that other productions can refer to it).
You might argue that we don’t really need the string tags - just return a concrete parse tree and distinguish the cases by pattern matching. However, it isn’t generally possible to tell the parse tree for a number from that for an identifier without re-parsing. Even when you can tell parse trees apart, the resulting code is ugly and inefficient, as it is repeating some of the parser’s work.
We could approach the problem via staged execution, writing meta-program that statically transformed the grammar into a program that would provide us with the nice datatype constructors I suggested in the beginning. If one goes that route, you might as well define an external DSL based on BNF or PEGs.
So, I assert that reflection is essential to this task, and dynamic type generation would be helpful as well, which would require dependent types and additional reflective functionality. However, maybe I’ve overlooked something and there is some other way to achieve the same goal. I’m sure someone will tell me - but remember, the library must not burden the user by requiring redundant information or work, it must operate independent of the specifics of a given grammar, and it must keep semantic actions entirely separate.
In any case, I think there is considerable value in adding at least a measure of introspection, and preferably full reflection, to traditional functional languages, and interesting work to be done fleshing it out.
Saturday, July 31, 2010
Meta Morphosis
Recently, I was pointed at rotated Google. This is cool in a perverse sort of way, and it immediately reminded me of Morphic.
For those who don’’t know, Morphic is the name of the Squeak (and in earlier times, Self) GUI. John Maloney (who nowadays does Scratch) introduced the original Morphic GUI back in the halcyon days of Self, and later adapted it to Squeak Smalltalk. The latest incarnation of a Morphic-style UI is Dan Ingalls’ lively kernel, which adapted the ideas to Javascript and the web. You can check it out in your browser right now.
What makes Morphic interesting is that it is compositional. The basic building block is a morph, which is just a graphical entity. The key is that everything in Morphic is a morph - including not just the basic morphs like lines and curves, polygons, circles, ellipses but also text, buttons, lists, windows ... you name it.
All morphs support pretty general graphical combinators - translation, rotation, scaling, non-linear warping, changing color, grouping/ungrouping etc. It follows that one can interactively rotate, scale or non-linearly warp an entire window running a live application.
One of my favorite Squeak demos is a class browser that’s been animated so that it floats around the screen, rotating as it goes, coupled with sound effects (a croaking frog is my preference). Of course you can keep using the browser and add methods or remove instance variables on the fly while it’s doing that. It’s an amazing display of the power of compositionality in action. It’s also perfectly useless (like rotated Google).
When running Morphic, you can always interactively ungroup a composite morph and get at its pieces. So you can disassemble the UI and find out what its made of. You can also do the opposite and assemble a UI out of simpler morphs; in a sense, the GUI is the GUI builder.
The situation is quite analogous to the physical world. A real window (the kind used to let light into your house) is assembled from physical pieces, and can be disassembled as well. The window as a whole, and each of its components, can be manipulated in space in uniform ways.
Thankfully, the laws of physics are compositional, since they were not designed by software engineers on a standards committee.
Put another way, if the universe was built like most software, it would have crashed long ago; the big bang would have a different meaning.
As a demonstration of good computer science, Morphic is brilliant. However, as a working UI it is problematic. You don’t really want your windows to fall apart in the user’s hands because they accidentally pressed some control sequence.
Looking at how physical windows work, we see that when they are assembled, they are secured so they are not disassembled too easily. Things are held together with glue or screws or whatever, and you need to make an effort to take the structure apart, perhaps using special tools.
This points at the way morphic interfaces should evolve. It’s great to have the underlying flexibility that they give you, but we want mechanisms to prevent accidents. We don’t want our applications decomposing by mistake. We also don’t want loose windows rotating by mistake. We need the equivalent of screws to hold things in place. The nice thing about screws is that they can be be used to build things up from parts compositionally, and they can be unscrewed when necessary. That way, we can take advantage of the flexibility of the underlying framework and do cool things with it, while keeping it safe for the end-user.
As rotating Google and (more significantly) Lively show, the web opens up the possibility of such UIs reaching a broad audience. I am sure we will get versions of morphic that are more refined, usable, attractive and polished - all less than three decades since they were introduced in Self. Instant progress!
For those who don’’t know, Morphic is the name of the Squeak (and in earlier times, Self) GUI. John Maloney (who nowadays does Scratch) introduced the original Morphic GUI back in the halcyon days of Self, and later adapted it to Squeak Smalltalk. The latest incarnation of a Morphic-style UI is Dan Ingalls’ lively kernel, which adapted the ideas to Javascript and the web. You can check it out in your browser right now.
What makes Morphic interesting is that it is compositional. The basic building block is a morph, which is just a graphical entity. The key is that everything in Morphic is a morph - including not just the basic morphs like lines and curves, polygons, circles, ellipses but also text, buttons, lists, windows ... you name it.
All morphs support pretty general graphical combinators - translation, rotation, scaling, non-linear warping, changing color, grouping/ungrouping etc. It follows that one can interactively rotate, scale or non-linearly warp an entire window running a live application.
One of my favorite Squeak demos is a class browser that’s been animated so that it floats around the screen, rotating as it goes, coupled with sound effects (a croaking frog is my preference). Of course you can keep using the browser and add methods or remove instance variables on the fly while it’s doing that. It’s an amazing display of the power of compositionality in action. It’s also perfectly useless (like rotated Google).
When running Morphic, you can always interactively ungroup a composite morph and get at its pieces. So you can disassemble the UI and find out what its made of. You can also do the opposite and assemble a UI out of simpler morphs; in a sense, the GUI is the GUI builder.
The situation is quite analogous to the physical world. A real window (the kind used to let light into your house) is assembled from physical pieces, and can be disassembled as well. The window as a whole, and each of its components, can be manipulated in space in uniform ways.
Thankfully, the laws of physics are compositional, since they were not designed by software engineers on a standards committee.
Put another way, if the universe was built like most software, it would have crashed long ago; the big bang would have a different meaning.
As a demonstration of good computer science, Morphic is brilliant. However, as a working UI it is problematic. You don’t really want your windows to fall apart in the user’s hands because they accidentally pressed some control sequence.
Looking at how physical windows work, we see that when they are assembled, they are secured so they are not disassembled too easily. Things are held together with glue or screws or whatever, and you need to make an effort to take the structure apart, perhaps using special tools.
This points at the way morphic interfaces should evolve. It’s great to have the underlying flexibility that they give you, but we want mechanisms to prevent accidents. We don’t want our applications decomposing by mistake. We also don’t want loose windows rotating by mistake. We need the equivalent of screws to hold things in place. The nice thing about screws is that they can be be used to build things up from parts compositionally, and they can be unscrewed when necessary. That way, we can take advantage of the flexibility of the underlying framework and do cool things with it, while keeping it safe for the end-user.
As rotating Google and (more significantly) Lively show, the web opens up the possibility of such UIs reaching a broad audience. I am sure we will get versions of morphic that are more refined, usable, attractive and polished - all less than three decades since they were introduced in Self. Instant progress!
Sunday, July 11, 2010
Converting Smalltalk to Newspeak
One of the things that has surprised me working with Newspeak is how easy it is to convert Smaltalk code to Newspeak. We have converted most of the core libraries of Smalltalk (aka ‘The Blue Book Libraries’) into Newspeak. Most of the conversion was done by people who had never coded in Newspeak before. In some cases, they had never coded in Smalltalk before.
The syntactic differences are fairly trivial (though they will grow in time) and easily handled - either automatically by tools or by very simple transformations in a text editor. Semantically moving from Smalltalk to Newspeak is easy (see this document for a detailed discussion of the mechanics), but the opposite is harder.
The main issues one has are API differences between libraries; but this is no different than converting from one Smalltalk implementation to another.
The converted code may not be the most idiomatic Newspeak. The easiest conversion path sticks a bunch of related Smalltalk classes inside a Newspeak module class, without creating any interesting substructure. Nevertheless, the converted code is invariably better than the original. It becomes very clear what the code’s external dependencies are, what the module boundaries should be, who is responsible for initialization etc. There is no longer any static state. It’s much easier to tie libraries together (or tear them apart), test them independently and so forth. Once we start enforcing access control, it should be much clearer what the public API really is. All this without losing the flexibility and power of the original.
This is very encouraging, because it means Newspeakers can take advantage of the large body of Smalltalk code that already exists. Any useful Smalltalk library that is publicly available can be converted to Newspeak in pretty short order. It also means that Smalltalkers can take the plunge and migrate to Newspeak relatively easily.
Of course, I don’t expect all the world’s Smalltalkers to instantly convert to Newspeak. Even if they did, Newspeak would still be a niche language. For Newspeak to be a success, we need to reach out to programmers in a variety of communities. This post, however, is aimed squarely at the Smalltalk community.
There are no doubt many Smalltalk projects that are tied to a specific Smalltalk. There are also Smalltalkers who are too conservative, and don’t want to deal with any language changes.
The main issues one has are API differences between libraries; but this is no different than converting from one Smalltalk implementation to another.
The converted code may not be the most idiomatic Newspeak. The easiest conversion path sticks a bunch of related Smalltalk classes inside a Newspeak module class, without creating any interesting substructure. Nevertheless, the converted code is invariably better than the original. It becomes very clear what the code’s external dependencies are, what the module boundaries should be, who is responsible for initialization etc. There is no longer any static state. It’s much easier to tie libraries together (or tear them apart), test them independently and so forth. Once we start enforcing access control, it should be much clearer what the public API really is. All this without losing the flexibility and power of the original.
This is very encouraging, because it means Newspeakers can take advantage of the large body of Smalltalk code that already exists. Any useful Smalltalk library that is publicly available can be converted to Newspeak in pretty short order. It also means that Smalltalkers can take the plunge and migrate to Newspeak relatively easily.
Of course, I don’t expect all the world’s Smalltalkers to instantly convert to Newspeak. Even if they did, Newspeak would still be a niche language. For Newspeak to be a success, we need to reach out to programmers in a variety of communities. This post, however, is aimed squarely at the Smalltalk community.
There are no doubt many Smalltalk projects that are tied to a specific Smalltalk. There are also Smalltalkers who are too conservative, and don’t want to deal with any language changes.
Still, if you are (or were, in some happier time) a Smalltalker and want to move into the future rather than dwelling on the glorious past, I assert that Newspeak is for you. If you are using an open source Smalltalk, it is likely you could do better using Newspeak. Newspeak explicitly addresses Smalltalk’s weaknesses: modularity, security, interoperability. Of course, some people aren’t bothered by these weaknesses.
Tangent: Arguably, the Smalltalk community is, by natural selection, composed largely of such people; if they were bothered by Smalltalk’s deficiencies, they wouldn’t use it.
Newspeak should interest those who appreciate the power of Smalltalk but want to move forward.
Of course, you have to be an early adopter by nature. Things will evolve and change under your feet. The syntax will become less Smalltalk-ish over time. Most importantly, you’ll have to learn something new. This is good for your neurons. You may have to port some libraries you rely on. You may have to make changes so that you do not rely on libraries you wouldn’t want to port (like Morphic). However, the result will likely be a product that is easier to deploy, more visually appealing and better integrated with its surrounding environment. Your code will be much more maintainable and better structured.
I’ve written a simple guide that highlights how to go about converting Smalltalk to Newspeak. Give it a try!
Tangent: Arguably, the Smalltalk community is, by natural selection, composed largely of such people; if they were bothered by Smalltalk’s deficiencies, they wouldn’t use it.
Newspeak should interest those who appreciate the power of Smalltalk but want to move forward.
Of course, you have to be an early adopter by nature. Things will evolve and change under your feet. The syntax will become less Smalltalk-ish over time. Most importantly, you’ll have to learn something new. This is good for your neurons. You may have to port some libraries you rely on. You may have to make changes so that you do not rely on libraries you wouldn’t want to port (like Morphic). However, the result will likely be a product that is easier to deploy, more visually appealing and better integrated with its surrounding environment. Your code will be much more maintainable and better structured.
I’ve written a simple guide that highlights how to go about converting Smalltalk to Newspeak. Give it a try!
Saturday, June 19, 2010
Patterns as Objects in Newspeak
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.
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.
Subscribe to:
Posts (Atom)