Earlier this month I spoke at the International Computer Science Festival in Krakow. Krakow is a beautiful city with several universities, and it is becoming a high tech center, with branches of companies like IBM and Google. The CS festival draws well over a thousand participants; the whole thing is organized by students. While much of the program was in Polish, there were quite a few talks in English.
Among these was Chad Fowler’s talk on Ruby. Chad is a very good speaker, who did an excellent job of conveying the sense of working in a dynamic language like Ruby. Almost everything he said would apply to Smalltalk as well.
One of the points that came up was the custom, prevalent in Ruby and in Smalltalk, of extending existing classes with new methods in the service of some other application or library. Such methods are often referred to as extension methods in Smalltalk, and the practice is supported by tools such as the Monticello source control system.
As an example, I’ll use my parser combinator library, which I’ve described in previous posts. To define a production for an if statement, you might write:
if:: tokenFromSymbol: #if.
then:: tokenFromSymbol: #then.
ifStat:: if, expression, then, statement.
assuming that productions for expression and statement already exist. The purpose of the rules if and then is to produce a tokenizing parser that accepts the symbols #if and #then respectively. It might be nicer to just write:
ifStat:: #if, expression, #then, statement.
and have the system figure out that, in this context, you want to denote a parser for a symbol by the symbol directly, much as you would when writing the BNF.
One way of achieving this would be to actually go and add the necessary methods to the class Symbol, so that symbols could behave like parsers. I know otherwise intelligent people who are prepared to argue for this approach. As I said, Smalltalkers would call these additions extension methods, but I find the more informal term monkey patching conveys a better intuition.
Typically, one wants to deliver a set of such methods as a unit, to be installed when a certain class or library gets loaded. So these changes are often provided as a patch that is applied dynamically. Not a problem in Smalltalk or Ruby or Python (though I gathered from the Pythoners in Krakow that they, to their credit, frown on the practice).
Apparently, there is a need to explain why monkey patching is a really bad idea. For starters, the methods in one monkey’s patch might conflict with those in some other monkey’s patch. In our example, the sequencing operator for parsers conflicts with that for symbols.
A mere flesh wound, says our programming primate: I usually don’t get conflicts, so I’ll pretend they won’t happen. The thing is, as thing scale up, rare occurrences get more frequent, and the costs can be very high.
Another problem is API bloat. You can see this in Squeak images, where a lot of monkeying about has taken place over the years. Classes like Object and String are polluted with dozens of methods contributed by enterprising individuals who felt that their favorite convenience method is something the whole world needs to benefit from.
Even in your own code, one needs to exercise restraint lest your API becomes obese with convenience methods. Big APIs eat up memory for both people and machinery, reducing responsiveness as well as learnability.
Then there is the small matter of security. If you are free to patch the definition of a class like String (typically on the fly when their code gets loaded), what’s to stop malicious macaques from replacing critical methods with really damaging stuff?
The counter argument is that in many cases (though not in this example), the patch is designed to avoid the use of typecase/switch/instance-of constructs, which bring their own set of evils to the table.
Extractors are a new approach to pattern matching developed by Martin Odersky for Scala. They overcome the usual difficulty with pattern matching, which is that it violates encapsulation by exposing the implementation type of data, just like instance-of. It may be part of the answer here as well.
However, many monkey patches are motivated by a desire for syntactic sugar, as the example shows. Extractors won’t help here.
A variety of language constructs have been devised to deal with this and related situations. Class boxes and selector namespaces in Smalltalk dialects, context oriented programming in Lisp and Smalltalk, static extension methods in C# and even Haskell type classes are related. These mechanisms don’t all provide the same functionality of course. I confess that I find none of them attractive. Each comes at a price that is too high for what it provides.
For example, C# extension methods rely on mandatory typing. Furthermore, they would not address the example above, because we need the literal symbols we use in the grammar to behave like parsers when passed into the parser combinator library code, not just in the lexical scope of the grammar.
Haskell type classes are much better. They would work for this problem (and many others), but also rely crucially on mandatory typing.
Class boxes are dynamic, but again only effect the immediate lexical scope. The same is true of simple formulations of selector namespaces. Richer versions let you import the desired selectors elsewhere, but I find this gets rather baroque. I'm not sure how COP meshes with security; so far it seems too complex for me to consider.
I’ve contemplated a change to the Newspeak semantics that would accommodate the above example, but it hasn’t been implemented, and I have mixed feelings about it. If a literal like #if is interpreted as an invocation of a factory method on Symbol, then we can override Symbol so that it supports the parser combinators. This only effects symbols created in a given scope, but isn’t just syntactic sugar like the C# extension methods suggested above.
Of course, this can be horribly abused; one shudders to think what a band of baboons might make of the freedom to redefine the language’s literals. On the other hand, used judiciously, it is great for supporting domain specific languages.
So far, I have no firm conclusions about how to best address the problems monkey patching is trying to solve. I don’t deny that it is expedient and tempting. Much of the appeal of dynamic languages is of course the freedom to do such things. The contrast with a language like Java is instructive. Adding a method to String is pretty much impossible. One has to sacrifice one’s first-born to the gods of the JCP and wait seven years for them to decide whether to add the method or not. I’m not endorsing that model either: I know it only too well.
Regardless, given my flattering portrayals of primate practices, you may deduce that my main comment on monkey patching is “just say no”. The problems it induces far outweigh its benefits. If you feel tempted, think hard about design alternatives. One can do better.
Sunday, March 23, 2008
Sunday, February 17, 2008
Cutting out Static
Most imperative languages have some notion of static variable. This is unfortunate, since static variables have many disadvantages. I have argued against static state for quite a few years (at least since the dawn of the millennium), and in Newspeak, I’m finally able to eradicate it entirely. Why is static state so bad, you ask?
Static variables are bad for security. See the E literature for extensive discussion on this topic. The key idea is that static state represents an ambient capability to do things to your system, that may be taken advantage of by evildoers.
Static variables are bad for distribution. Static state needs to either be replicated and sync’ed across all nodes of a distributed system, or kept on a central node accessible by all others, or some compromise between the former and the latter. This is all difficult/expensive/unreliable.
Static variables are bad for re-entrancy. Code that accesses such state is not re-entrant. It is all too easy to produce such code. Case in point: javac. Originally conceived as a batch compiler, javac had to undergo extensive reconstructive surgery to make it suitable for use in IDEs. A major problem was that one could not create multiple instances of the compiler to be used by different parts of an IDE, because javac had significant static state. In contrast, the code in a Newspeak module definition is always re-entrant, which makes it easy to deploy multiple versions of a module definition side-by-side, for example.
Static variables are bad for memory management. This state has to be handed specially by implementations, complicating garbage collection. The woeful tale of class unloading in Java revolves around this problem. Early JVMs lost application’s static state when trying to unload classes. Even though the rules for class unloading were already implicit in the specification, I had to add a section to the JLS to state them explicitly, so overzealous implementors wouldn’t throw away static application state that was not entirely obvious.
Static variables are bad for for startup time. They encourage excess initialization up front. Not to mention the complexities that static initialization engenders: it can deadlock, applications can see uninitialized state, and unless you have a really smart runtime, you find it hard to compile efficiently (because you need to test if things are initialized on every use).
Static variables are bad for for concurrency. Of course, any shared state is bad for concurrency, but static state is one more subtle time bomb that can catch you by surprise.
Given all these downsides, surely there must be some significant upside, something to trade off against the host of evils mentioned above? Well, not really. It’s just a mistake, hallowed by long tradition. Which is why Newspeak has dispensed with it.
It may seem like you need static state, somewhere to start things off, but you don’t. You start off by creating an object, and you keep your state in that object and in objects it references. In Newspeak, those objects are modules.
Newspeak isn’t the only language to eliminate static state. E has also done so, out of concern for security. And so has Scala, though its close cohabitation with Java means Scala’s purity is easily violated. The bottom line, though, should be clear. Static state will disappear from modern programming languages, and should be eliminated from modern programming practice.
Static variables are bad for security. See the E literature for extensive discussion on this topic. The key idea is that static state represents an ambient capability to do things to your system, that may be taken advantage of by evildoers.
Static variables are bad for distribution. Static state needs to either be replicated and sync’ed across all nodes of a distributed system, or kept on a central node accessible by all others, or some compromise between the former and the latter. This is all difficult/expensive/unreliable.
Static variables are bad for re-entrancy. Code that accesses such state is not re-entrant. It is all too easy to produce such code. Case in point: javac. Originally conceived as a batch compiler, javac had to undergo extensive reconstructive surgery to make it suitable for use in IDEs. A major problem was that one could not create multiple instances of the compiler to be used by different parts of an IDE, because javac had significant static state. In contrast, the code in a Newspeak module definition is always re-entrant, which makes it easy to deploy multiple versions of a module definition side-by-side, for example.
Static variables are bad for memory management. This state has to be handed specially by implementations, complicating garbage collection. The woeful tale of class unloading in Java revolves around this problem. Early JVMs lost application’s static state when trying to unload classes. Even though the rules for class unloading were already implicit in the specification, I had to add a section to the JLS to state them explicitly, so overzealous implementors wouldn’t throw away static application state that was not entirely obvious.
Static variables are bad for for startup time. They encourage excess initialization up front. Not to mention the complexities that static initialization engenders: it can deadlock, applications can see uninitialized state, and unless you have a really smart runtime, you find it hard to compile efficiently (because you need to test if things are initialized on every use).
Static variables are bad for for concurrency. Of course, any shared state is bad for concurrency, but static state is one more subtle time bomb that can catch you by surprise.
Given all these downsides, surely there must be some significant upside, something to trade off against the host of evils mentioned above? Well, not really. It’s just a mistake, hallowed by long tradition. Which is why Newspeak has dispensed with it.
It may seem like you need static state, somewhere to start things off, but you don’t. You start off by creating an object, and you keep your state in that object and in objects it references. In Newspeak, those objects are modules.
Newspeak isn’t the only language to eliminate static state. E has also done so, out of concern for security. And so has Scala, though its close cohabitation with Java means Scala’s purity is easily violated. The bottom line, though, should be clear. Static state will disappear from modern programming languages, and should be eliminated from modern programming practice.
Monday, December 31, 2007
More on Modules
My posts seem to raise more questions than they answer. This is as it should be, in accordance with the Computational Theologist Full Employment Act. In this post, I’ll try and answer some of the questions that arose from my last one.
How does one actually hook modules together and get something going? As I mentioned before, module definitions are top level classes - classes that are defined in a namespace, rather than in another class.
Defining a top level class makes its name available in the surrounding namespace. More precisely, it causes the compiler to define a getter method with the name of the class on the namespace; the method will return the class object.
Since a module definition is just a class, one needs to instantiate it, by calling a constructor - which is a class side method. Continuing with the example from the previous post:
MovieLister finderClass: ColonDelimitedMovieFinder
Now this isn’t quite realistic, since ColonDelimitedMovieFinder probably needs access to things like collections and files to do its job. So it’s probable that it takes at least one parameter itself. The typical situation is that a module definition takes a parameter representing the necessary parts of the platform libraries. It might look something like this:
ColonDelimitedMovieFinder usingLib: platform = (
|
OrderedCollection = platform Collections OrderedCollection.
FileStream = platform Streams FileStream.
|
)...
So we’d really create the application this way:
MovieLister finderClass: (ColonDelimitedMovieFinder usingLib: Platform new)
where Platform is a predefined module that provides access to the built-in libraries.
Bob Lee points out that if I change MovieLister so that it takes another parameter, I have to update all the creation sites for MovieLister, whereas using a good DIF I only declare what needs to be injected and where.
In many cases, I could address this issue by declaring a secondary constructor that feeds the second argument to the primary one.
Say we changed MovieLister because it too needed access to some platform library:
class MovieLister usingLib: platform finderClass: MovieFinder = ...
We might be able to define a secondary constructor
class MovieLister usingLib: platform finderClass: MovieFinder = (
...
): (
finderClass: MovieFinder = (
^usingLib: Platform new finderClass: MovieFinder
)
)
There are however two situations where this won’t work in Newspeak.
One is inheritance, because subclasses must call the primary constructor. I showed how to deal with that in one of my August 2007 posts - don’t change the primary constructor - change the superclass.
class MovieLister finderClass: MovieFinder = NewMovieLister usingLib: Platform new finderClass: MovieFinder
(...)
The other problematic case is for module definitions. In most cases, the solutions above won’t help; they won’t be able to provide a good default for the additional parameter, because they won’t have access to the surrounding scope. For this last situation I have no good answer yet. I will say that the public API of a top level module definition should be pretty stable, and the number of calls relatively few.
So overall, I think Bob makes an important point - DIFs give you a declarative way of specifying how objects are to be created. On the other had, it gets a bit complicated when different arguments are needed in different places, or if we don’t want to compute so many things up front at object creation time. Guice has mechanisms to help with that, but I find them a bit rich for my blood. In those cases, I really prefer to specify things naturally in my code.
Another advantage of abstracting freely over classes is that you can inherit from classes that are provided as parameters.
class MyCollections usingLib: platform = (
| ArrayList = platform ArrayList. |
)(
ExtendedArray List = ArrayList (...)
)
Now, depending what library you actually provide to MyCollections as an argument, you can obtain distinct subclasses (in fact, there’s an easier way to do this, but this post is once again getting too long). Correct me if I’m wrong, but I don’t think a DIF helps here.
You can also do class hierarchy inheritance: modify an entire library embedded within a module by subclassing it and changing only what’s needed. This is somewhat less modular (inheritance always causes problems) but the tradeoff is well worth it in my opinion.
I spoke about class hierarch inheritance at JAOO, and will likely speak about it again in one or more of my upcoming talks on Newspeak, at Google in Kirkland on January 8th, at FOOL on January 13th, or at Lang.Net 2008 in Redmond in late January.
I’m trying to make each of these talks somewhat different, but they will necessarily have some overlap. I hope that some of these talks will make it onto the net and make these ideas more accessible.
How does one actually hook modules together and get something going? As I mentioned before, module definitions are top level classes - classes that are defined in a namespace, rather than in another class.
Defining a top level class makes its name available in the surrounding namespace. More precisely, it causes the compiler to define a getter method with the name of the class on the namespace; the method will return the class object.
Since a module definition is just a class, one needs to instantiate it, by calling a constructor - which is a class side method. Continuing with the example from the previous post:
MovieLister finderClass: ColonDelimitedMovieFinder
Now this isn’t quite realistic, since ColonDelimitedMovieFinder probably needs access to things like collections and files to do its job. So it’s probable that it takes at least one parameter itself. The typical situation is that a module definition takes a parameter representing the necessary parts of the platform libraries. It might look something like this:
ColonDelimitedMovieFinder usingLib: platform = (
|
OrderedCollection = platform Collections OrderedCollection.
FileStream = platform Streams FileStream.
|
)...
So we’d really create the application this way:
MovieLister finderClass: (ColonDelimitedMovieFinder usingLib: Platform new)
where Platform is a predefined module that provides access to the built-in libraries.
Bob Lee points out that if I change MovieLister so that it takes another parameter, I have to update all the creation sites for MovieLister, whereas using a good DIF I only declare what needs to be injected and where.
In many cases, I could address this issue by declaring a secondary constructor that feeds the second argument to the primary one.
Say we changed MovieLister because it too needed access to some platform library:
class MovieLister usingLib: platform finderClass: MovieFinder = ...
We might be able to define a secondary constructor
class MovieLister usingLib: platform finderClass: MovieFinder = (
...
): (
finderClass: MovieFinder = (
^usingLib: Platform new finderClass: MovieFinder
)
)
There are however two situations where this won’t work in Newspeak.
One is inheritance, because subclasses must call the primary constructor. I showed how to deal with that in one of my August 2007 posts - don’t change the primary constructor - change the superclass.
class MovieLister finderClass: MovieFinder = NewMovieLister usingLib: Platform new finderClass: MovieFinder
(...)
The other problematic case is for module definitions. In most cases, the solutions above won’t help; they won’t be able to provide a good default for the additional parameter, because they won’t have access to the surrounding scope. For this last situation I have no good answer yet. I will say that the public API of a top level module definition should be pretty stable, and the number of calls relatively few.
So overall, I think Bob makes an important point - DIFs give you a declarative way of specifying how objects are to be created. On the other had, it gets a bit complicated when different arguments are needed in different places, or if we don’t want to compute so many things up front at object creation time. Guice has mechanisms to help with that, but I find them a bit rich for my blood. In those cases, I really prefer to specify things naturally in my code.
Another advantage of abstracting freely over classes is that you can inherit from classes that are provided as parameters.
class MyCollections usingLib: platform = (
| ArrayList = platform ArrayList. |
)(
ExtendedArray List = ArrayList (...)
)
Now, depending what library you actually provide to MyCollections as an argument, you can obtain distinct subclasses (in fact, there’s an easier way to do this, but this post is once again getting too long). Correct me if I’m wrong, but I don’t think a DIF helps here.
You can also do class hierarchy inheritance: modify an entire library embedded within a module by subclassing it and changing only what’s needed. This is somewhat less modular (inheritance always causes problems) but the tradeoff is well worth it in my opinion.
I spoke about class hierarch inheritance at JAOO, and will likely speak about it again in one or more of my upcoming talks on Newspeak, at Google in Kirkland on January 8th, at FOOL on January 13th, or at Lang.Net 2008 in Redmond in late January.
I’m trying to make each of these talks somewhat different, but they will necessarily have some overlap. I hope that some of these talks will make it onto the net and make these ideas more accessible.
Sunday, December 16, 2007
Lethal Injection
Some months ago, I wrote a couple of posts about object construction and initialization. I made the claim that so-called dependency-injection frameworks (DIFs) are completely unnecessary in a language like Newspeak, and promised to expand on that point in a later post. Four months should definitely qualify as “later”, so here is the promised explanation.
I won’t explain DIFs in detail here - read Martin Fowler’s excellent overview if you need an introduction. The salient information about DIFs is that they are used to write code that does not have undue references to concrete classes embedded in it. These references are usually calls to constructors or static methods. These concrete references create undue intermodule dependencies.
The root of the problem DIFs address is that mainstream languages provide inadequate mechanisms to abstract over classes.
Terminology rant: DIFs should more properly be called dependee-injection frameworks. A dependency is a relationships between a dependent (better called depender) and a dependee. The dependencies are what we do not want in our code; we certainly don’t want to inject more of them. Instead, DIFs inject instances of the dependees, so the dependers don’t have to create them.
DIFs require you write your code in a specific way, where you avoid creating instances of dependees. Instead, you make sure that there is a way to provide the dependee instance (in DIF terminology, to inject it) from outside the object. You then tell the framework where and what to inject. The reason injection traffics in instances rather than the classes themselves is because there’s no good way to abstract over the classes.
Having recapped DIFs, lets move on to Newspeak. Newspeak modules are defined in namespaces. Namespaces are simply objects that are required to be deeply immutable; they are stateless.
Tangent: This ensures that there is no global or static state in Newspeak, which gives us many nice properties.
Namespaces are organized like Java packages, as an inversion of the internet domain namespace. Unlike Java packages, sub-namespaces can see their enclosing namespace.
A module is a top-level class, that is, a class defined directly within a namespace. Newspeak classes can nest arbitrarily, so a module can contain an entire class library or framework, which can in turn be subdivided into subsystems to any depth. Nested classes can freely access the lexical scope of their enclosing class.
Modules, like all classes, are reified as objects that support constructor methods. Recall that in Newspeak, a constructor invocation is indistinguishable from an ordinary method invocation. Objects are constructed by sending messages to (invoking virtual methods on) another object. That object may or may not be a class; it makes no difference. Hence all the usual abstraction mechanisms in the language apply to classes - in particular, parameterization.
Here is a trivial top level class, modeled after the motivating example for DIFs given in Fowler’s article:
The idea is that MovieLister supports one method, moviesDirectedBy:, which takes a string that contains the name of a director and returns a collection of movies directed by said director. The point of Fowler’s example is that there is an undesirable dependency on a class, ColonDelimitedMovieFinder, embedded in MovieLister. If we want to use a different database, we need to change the code.
However, this code won’t actually work in Newspeak. The reason is that the enclosing namespace is not visible inside a Newspeak module. Any external dependencies must be made explicit by passing them to the module as parameters to a constructor method. These parameters could be other modules, namespaces, or classes and instances of any kind.
In this specific case, ColonDelimitedMovieFinder cannot be referenced from MovieLister. If we try and create a MovieLister by writing: MovieLister new, creation will fail with a message not understood error on ColonDelimitedMovieFinder. We’d have to declare a constructor for MovieLister with the movie finder as a parameter:
At this point, we can immediately see that we can replace ColonDelimitedMovieFinder with any class that supports the same interface, which was the object of the entire exercise. Newspeak won’t let you create a module with concrete external dependencies, because that wouldn’t really be a module, would it?
In Newspeak code in a module doesn’t have any concrete external dependencies, and no dependees need to be injected. What’s more we can subclass or mix-in any class coming in as a parameter - something a DIF won’t handle.
What about a subsystem within a module? What if I don’t want it using the same name binding as the enclosing module? I can explicitly parameterize my subsystem, though that requires pre-planning.
I can also override any class binding in a subclass. Newspeak is message-based, so all names are late-bound. Hence any reference to the name of a class can be overridden in a subclass. Classes can be overridden by methods or slots or other classes in any combination. So even if you do not explicitly parameterize your code to allow for another class to be used to construct an object, you can still override the binding of the class name as necessary.
In summary, Newspeak is designed to support, even induce, loose coupling. That’s the point of message based programming languages. DIFs are an expedient technique to reduce code coupling in the sad world of mainstream development, but in a language like Newspeak, they are pointless.
I won’t explain DIFs in detail here - read Martin Fowler’s excellent overview if you need an introduction. The salient information about DIFs is that they are used to write code that does not have undue references to concrete classes embedded in it. These references are usually calls to constructors or static methods. These concrete references create undue intermodule dependencies.
The root of the problem DIFs address is that mainstream languages provide inadequate mechanisms to abstract over classes.
Terminology rant: DIFs should more properly be called dependee-injection frameworks. A dependency is a relationships between a dependent (better called depender) and a dependee. The dependencies are what we do not want in our code; we certainly don’t want to inject more of them. Instead, DIFs inject instances of the dependees, so the dependers don’t have to create them.
DIFs require you write your code in a specific way, where you avoid creating instances of dependees. Instead, you make sure that there is a way to provide the dependee instance (in DIF terminology, to inject it) from outside the object. You then tell the framework where and what to inject. The reason injection traffics in instances rather than the classes themselves is because there’s no good way to abstract over the classes.
Having recapped DIFs, lets move on to Newspeak. Newspeak modules are defined in namespaces. Namespaces are simply objects that are required to be deeply immutable; they are stateless.
Tangent: This ensures that there is no global or static state in Newspeak, which gives us many nice properties.
Namespaces are organized like Java packages, as an inversion of the internet domain namespace. Unlike Java packages, sub-namespaces can see their enclosing namespace.
A module is a top-level class, that is, a class defined directly within a namespace. Newspeak classes can nest arbitrarily, so a module can contain an entire class library or framework, which can in turn be subdivided into subsystems to any depth. Nested classes can freely access the lexical scope of their enclosing class.
Modules, like all classes, are reified as objects that support constructor methods. Recall that in Newspeak, a constructor invocation is indistinguishable from an ordinary method invocation. Objects are constructed by sending messages to (invoking virtual methods on) another object. That object may or may not be a class; it makes no difference. Hence all the usual abstraction mechanisms in the language apply to classes - in particular, parameterization.
Here is a trivial top level class, modeled after the motivating example for DIFs given in Fowler’s article:
public class MovieLister = (
|
private movieDB = ColonDelimitedMovieFinder from:’movies.txt’.
|)
(
public moviesDirectedBy: directorName = (
^movieDB findAll select:[:m |
m director = directorName
].
)
The idea is that MovieLister supports one method, moviesDirectedBy:, which takes a string that contains the name of a director and returns a collection of movies directed by said director. The point of Fowler’s example is that there is an undesirable dependency on a class, ColonDelimitedMovieFinder, embedded in MovieLister. If we want to use a different database, we need to change the code.
However, this code won’t actually work in Newspeak. The reason is that the enclosing namespace is not visible inside a Newspeak module. Any external dependencies must be made explicit by passing them to the module as parameters to a constructor method. These parameters could be other modules, namespaces, or classes and instances of any kind.
In this specific case, ColonDelimitedMovieFinder cannot be referenced from MovieLister. If we try and create a MovieLister by writing: MovieLister new, creation will fail with a message not understood error on ColonDelimitedMovieFinder. We’d have to declare a constructor for MovieLister with the movie finder as a parameter:
public class MovieLister finderClass: MovieFinder = (
|
private movieDB = MovieFinder from:’movies.txt’.
|)
(
public moviesDirectedBy: directorName = (
^movieDB findAll select:[:m |
m director = directorName
].
)
At this point, we can immediately see that we can replace ColonDelimitedMovieFinder with any class that supports the same interface, which was the object of the entire exercise. Newspeak won’t let you create a module with concrete external dependencies, because that wouldn’t really be a module, would it?
In Newspeak code in a module doesn’t have any concrete external dependencies, and no dependees need to be injected. What’s more we can subclass or mix-in any class coming in as a parameter - something a DIF won’t handle.
What about a subsystem within a module? What if I don’t want it using the same name binding as the enclosing module? I can explicitly parameterize my subsystem, though that requires pre-planning.
I can also override any class binding in a subclass. Newspeak is message-based, so all names are late-bound. Hence any reference to the name of a class can be overridden in a subclass. Classes can be overridden by methods or slots or other classes in any combination. So even if you do not explicitly parameterize your code to allow for another class to be used to construct an object, you can still override the binding of the class name as necessary.
In summary, Newspeak is designed to support, even induce, loose coupling. That’s the point of message based programming languages. DIFs are an expedient technique to reduce code coupling in the sad world of mainstream development, but in a language like Newspeak, they are pointless.
Tuesday, September 25, 2007
Executable Grammars
Way back in January, I described a parser combinator library I’d built in Smalltalk. Since then, we’ve moved from Smalltalk to Newspeak, and refined the library in interesting ways.
The original parser combinator library has been a great success, but grammars built with it were still polluted by two solution-space artifacts. One is the need to use self sends, as in
id := self letter, [(self letter | [self digit]) star]
In Newspeak, self sends can be implicit, and so this problem goes away. We could write
id:: letter, [(letter | [digit]) star]
The other problem is the use of blocks. We’d much rather have written
id:: letter, (letter | digit) star
The solution is to have the framework pre-initialize all slots representing productions with a forward reference parser that acts as a stand-in for the real parser that will be computed later.
When the tree of parsers representing the grammar has been computed, it will contain stand-ins exactly in those places where forward references occurred due to mutual recursion. When such a parser gets invoked, it looks up the real parser (now stored in the corresponding slot) and forwards all parsing requests to it.
Our parsers are now entirely unpolluted by solution-space boilerplate, so I feel justified in calling them executable grammars. They really are executable specifications, that can be shared among all the tools that need access to a language’s grammar.
Below is a small but complete grammar in Newspeak:
class ExampleGrammar1 = ExecutableGrammar (
|
digit = self charBetween: $0 and: $9.
letter = (self charBetween: $a and: $z) | (self charBetween: $A and: $Z).
id = letter, (letter | digit) star.
identifier = tokenFor: id.
hat = tokenFromChar: $^.
expression = identifier.
returnStatement = hat, expression.
|
) ()
If you want to understand all the details, check out this paper; if you can, you might also look at my JAOO 2007 talk, which also speculates on how we can make things look even nicer, e.g.:
class ExampleGrammar3 = ExecutableGrammar (
|
digit = $0 - $9.
letter = ($a - $z) | ($A - $Z).
id = letter, (letter | digit) star.
identifier = tokenFor: id.
expression = identifier.
returnStatement = $^, expression.
|
)()
The original parser combinator library has been a great success, but grammars built with it were still polluted by two solution-space artifacts. One is the need to use self sends, as in
id := self letter, [(self letter | [self digit]) star]
In Newspeak, self sends can be implicit, and so this problem goes away. We could write
id:: letter, [(letter | [digit]) star]
The other problem is the use of blocks. We’d much rather have written
id:: letter, (letter | digit) star
The solution is to have the framework pre-initialize all slots representing productions with a forward reference parser that acts as a stand-in for the real parser that will be computed later.
When the tree of parsers representing the grammar has been computed, it will contain stand-ins exactly in those places where forward references occurred due to mutual recursion. When such a parser gets invoked, it looks up the real parser (now stored in the corresponding slot) and forwards all parsing requests to it.
Our parsers are now entirely unpolluted by solution-space boilerplate, so I feel justified in calling them executable grammars. They really are executable specifications, that can be shared among all the tools that need access to a language’s grammar.
Below is a small but complete grammar in Newspeak:
class ExampleGrammar1 = ExecutableGrammar (
|
digit = self charBetween: $0 and: $9.
letter = (self charBetween: $a and: $z) | (self charBetween: $A and: $Z).
id = letter, (letter | digit) star.
identifier = tokenFor: id.
hat = tokenFromChar: $^.
expression = identifier.
returnStatement = hat, expression.
|
) ()
If you want to understand all the details, check out this paper; if you can, you might also look at my JAOO 2007 talk, which also speculates on how we can make things look even nicer, e.g.:
class ExampleGrammar3 = ExecutableGrammar (
|
digit = $0 - $9.
letter = ($a - $z) | ($A - $Z).
id = letter, (letter | digit) star.
identifier = tokenFor: id.
expression = identifier.
returnStatement = $^, expression.
|
)()
Wednesday, August 15, 2007
Object Initialization and Construction Revisited
In my last post, which discussed object initialization and construction, I had promised to come back to the topic and clarify it with concrete examples. I've finally found time to do that; hopefully I will dispel some of the misunderstandings that the last post engendered, no doubt replacing them with fresh, deeper misunderstandings.
Below is a standard example - a class representing points in the plane. What’s non-standard is that it is written in Newspeak, an experimental language in the style of Smalltalk, which I and some of my colleagues are working on right now. In cases where the syntax is non-obvious, I’ll use comments (Pascal style, like so: (* this is a comment *)) to show how a similar construct might be written in a more conventional (and less effective) notation.
this declaration introduces the class Point2D. The class name is immediately followed by a message pattern (method signature for readers of Javanese) x: i y: j. This pattern describes the primary constructor message for the class. The pattern introduces two formal parameters, i and j, which are in scope in the class body. The result of sending this message to the class is a fresh instance, e.g.:
yields a new instance of Point2D with x = 42 and y = 91. The message causes a new instance to be allocated and executes the slot initializers for that instance, in this case
The slots are accessed only through automatically generated getters (x and y) and setters (x: and y:).
How is all this different from mainstream constructors?
Because an instance is created by sending a message to an object, and not by some special construct like a constructor invocation, we can replace the receiver of that message with any object that responds to that message. It can be another class (say, an implementation based on polar coordinates), or it can be a factory object that isn’t a class at all.
Here is a method that takes the class/factory as a parameter
We can invoke this so:
but also so:
where Polar2D might be written as follows:
Here, Polar2D has a secondary constructor, a class method x:y:, which will be invoked by makePoint:.
You cannot do this with constructors or with static factories; you simply cannot abstract over them.
You could use reflection in Java, passing the Class object as a parameter and then searching for a constructor or static method matching the desired signature. Even then, you would have to commit to using a class. Here we can use any object that responds to the message x:y:.
Using Java core reflection in this case is awkward and verbose, and historically hasn’t been available on configurations like JavaME. And it doesn’t work well with proxy objects either (see the OOPSLA 2004 paper we wrote for details). What’s more, you may not have the right security permissions to do it. The situation is not much better with the VM from the makers of Zune (tm) either.
Zune is a trademark of Microsoft Corporation. Microsoft is also a trademark of Microsoft Corporation. But GNU’s not Unix
Alternatively, you could also define the necessary factory interface, implement it with factory classes, create factory objects and only pass those around. You’d have to do this for every class of course, whether you declared it or not. This is tedious, error prone, and very hard to enforce. The language should be doing this for you.
So far, we’ve shown how to manufacture instances of a class. What about subclassing? This is usually where things get sticky.
Here’s a class of 3D points
One detail that’s new here is the superclass clause: Point3D inherits from Point2D, and calls Point2D’s primary constructor. This is a requirement, enforced dynamically at instance creation time. It helps ensure that an object is always completely initialized.
Unlike Smalltalk, one cannot call a superclass’ constructors on a subclass. This prevents you from partially instantiating an object, say by writing:
without initializing z as intended. Also, unlike Smalltalk, there’s no instance method that does the initialization on behalf of the class object. So you cannot initialize an object multiple times, unless the designer deliberately creates an API to allow it. The idea is to ensure every object is initialized once and only once, but without the downsides associated with constructors.
Preventing malicious subclasses from undermining the superclass initialization takes care. We’re still considering potential solutions. The situation is no worse than in Java, it seems, and we may be able to make it better.
A different concern is that the subclass must call the primary constructor of the superclass. So what happens when I want to change the primary constructor? Say I want to change Point2D to use polar representation. Can I make rho:theta: the primary constructor? How can I do this without breaking subclasses of Point2D, such as Point3D? We can't do it directly yet (though we should have a fix for that in not too long), but I can redefine Point2D
as
Now anyone who uses a Point2D gets a point in polar representation, while preserving the existing interface. And anyone who wants to can of course create polar points using the secondary constructor. I can also arrange for that constructor to return instances of Polar2D directly:
If you find this interesting, you might want to read a short position paper I wrote for the Dynamic Languages Workshop at ECOOP. It only deals with one specific issue regarding the interaction of nested classes and inheritance, and it’s a just a position paper describing work in progress, but if you’ve gotten this far, you might take a look.
I still haven’t explained why I see no need for dependency inversion frameworks. The short answer is that because Newspeak classes nest arbitrarily, we can define a whole class library nested inside a class, and parameterize that class with respect to any external classes the library depends on. That probably needs more explanation; indeed, I think there’s a significant academic paper to be written on the subject. Given the length of this post, I won’t expand on the topic just yet.
Below is a standard example - a class representing points in the plane. What’s non-standard is that it is written in Newspeak, an experimental language in the style of Smalltalk, which I and some of my colleagues are working on right now. In cases where the syntax is non-obvious, I’ll use comments (Pascal style, like so: (* this is a comment *)) to show how a similar construct might be written in a more conventional (and less effective) notation.
class Point2D x: i y: j = (
(* Javanese version might look like this :
class Point2D setXY(i, j) { ...} *)
(*A class representing points in 2-space” *)
|
public x ::= i.
public y ::= j.
|
) ( (* instance side *)
public printString = (
ˆ ’ x = ’, x printString, ’ y = ’, y printString
)
)
this declaration introduces the class Point2D. The class name is immediately followed by a message pattern (method signature for readers of Javanese) x: i y: j. This pattern describes the primary constructor message for the class. The pattern introduces two formal parameters, i and j, which are in scope in the class body. The result of sending this message to the class is a fresh instance, e.g.:
Point2D x: 42 y: 91
(* In Javanese, you might write Point2D.setXY(42, 91);
But don’t even think of interpreting setXY as a static method!
*)
yields a new instance of Point2D with x = 42 and y = 91. The message causes a new instance to be allocated and executes the slot initializers for that instance, in this case
x ::= i.
y ::= j.
The slots are accessed only through automatically generated getters (x and y) and setters (x: and y:).
How is all this different from mainstream constructors?
Because an instance is created by sending a message to an object, and not by some special construct like a constructor invocation, we can replace the receiver of that message with any object that responds to that message. It can be another class (say, an implementation based on polar coordinates), or it can be a factory object that isn’t a class at all.
Here is a method that takes the class/factory as a parameter
makePoint: pointFactory = (
(* In Javanese:
makePoint(pointFactory) {
return pointFactory.setXY(100, 200)
}
*)
^pointFactory x: 100 y: 200
)
We can invoke this so:
makePoint: Point2D
but also so:
makePoint: Polar2D
where Polar2D might be written as follows:
class Polar2D rho: r theta: t = (
(* A class representing points in 2-space”*)
|
public rho ::= r.
public theta ::= t.
|
) ( (* instance side *)
public x = ( ^rho * theta cos) (* emulate x/y interface *)
public y = (^rho * theta sin)
...
public printString = (
ˆ ’ x = ’, x printString, ’ y = ’, y printString
)
) : ( (* class side begins here*)
public x: i y: j = (
| r t |
t := i arcCos.
r := j/ t sin.
ˆrho: r theta: t
)
)
Here, Polar2D has a secondary constructor, a class method x:y:, which will be invoked by makePoint:.
You cannot do this with constructors or with static factories; you simply cannot abstract over them.
You could use reflection in Java, passing the Class object as a parameter and then searching for a constructor or static method matching the desired signature. Even then, you would have to commit to using a class. Here we can use any object that responds to the message x:y:.
Using Java core reflection in this case is awkward and verbose, and historically hasn’t been available on configurations like JavaME. And it doesn’t work well with proxy objects either (see the OOPSLA 2004 paper we wrote for details). What’s more, you may not have the right security permissions to do it. The situation is not much better with the VM from the makers of Zune (tm) either.
Zune is a trademark of Microsoft Corporation. Microsoft is also a trademark of Microsoft Corporation. But GNU’s not Unix
Alternatively, you could also define the necessary factory interface, implement it with factory classes, create factory objects and only pass those around. You’d have to do this for every class of course, whether you declared it or not. This is tedious, error prone, and very hard to enforce. The language should be doing this for you.
So far, we’ve shown how to manufacture instances of a class. What about subclassing? This is usually where things get sticky.
Here’s a class of 3D points
class Point3D x: i y: j z: k = Point2D x: i y: j (
(* A class representing points in 3-space *)
| public z ::= k. |
) (* end class header *)
( (*begin instance side *)
public printString = (
ˆsuper printString, ’ z = ’, z printString
)
)
One detail that’s new here is the superclass clause: Point3D inherits from Point2D, and calls Point2D’s primary constructor. This is a requirement, enforced dynamically at instance creation time. It helps ensure that an object is always completely initialized.
Unlike Smalltalk, one cannot call a superclass’ constructors on a subclass. This prevents you from partially instantiating an object, say by writing:
Point3D x: 1 y: 2 (* illegal! *)
without initializing z as intended. Also, unlike Smalltalk, there’s no instance method that does the initialization on behalf of the class object. So you cannot initialize an object multiple times, unless the designer deliberately creates an API to allow it. The idea is to ensure every object is initialized once and only once, but without the downsides associated with constructors.
Preventing malicious subclasses from undermining the superclass initialization takes care. We’re still considering potential solutions. The situation is no worse than in Java, it seems, and we may be able to make it better.
A different concern is that the subclass must call the primary constructor of the superclass. So what happens when I want to change the primary constructor? Say I want to change Point2D to use polar representation. Can I make rho:theta: the primary constructor? How can I do this without breaking subclasses of Point2D, such as Point3D? We can't do it directly yet (though we should have a fix for that in not too long), but I can redefine Point2D
as
class Point2D x: i y: j = Polar2D rho: ... theta: ... = ()()
: ( “class side begins here”
(* secondary constructor *)
public rho: r theta: t = (
ˆx: r * t cos y: r * t sin
)
)
Now anyone who uses a Point2D gets a point in polar representation, while preserving the existing interface. And anyone who wants to can of course create polar points using the secondary constructor. I can also arrange for that constructor to return instances of Polar2D directly:
public rho: r theta: t = (
ˆPolar2D rho: r theta: t
)
If you find this interesting, you might want to read a short position paper I wrote for the Dynamic Languages Workshop at ECOOP. It only deals with one specific issue regarding the interaction of nested classes and inheritance, and it’s a just a position paper describing work in progress, but if you’ve gotten this far, you might take a look.
I still haven’t explained why I see no need for dependency inversion frameworks. The short answer is that because Newspeak classes nest arbitrarily, we can define a whole class library nested inside a class, and parameterize that class with respect to any external classes the library depends on. That probably needs more explanation; indeed, I think there’s a significant academic paper to be written on the subject. Given the length of this post, I won’t expand on the topic just yet.
Sunday, June 24, 2007
Constructors Considered Harmful
In mainstream object oriented programming languages, objects are created by invoking constructors. This is rather ironic, since you can say a lot about constructors, but you cannot honestly say that they are object oriented. Ok, so what? Isn’t “object-oriented” just an old buzzword? If constructors work well, who cares?
Of course, the problem is that constructors don’t work very well all. Understanding why helps to understand what “object oriented” really means, and why it is important.
Constructors come with a host of special rules and regulations: they cannot be overridden like instance methods; they need to call another constructor, or a superclass constructor etc. Try defining mixins in the presence of constructors - it’s tricky because the interface for creating instances gets bundled with the interface of the instances themselves.
The basic issue is a failure of abstraction, as Dave Ungar put it in his OOPSLA keynote in 2003.
Suppose we have a constructor C(x) and code that creates objects by calling it. What happens if we find that we actually need to return an instance of a class other than C? For example, we might want to lazily load data from secondary storage, and need to return some sort of placeholder object that behaves just like a C, but isn’t? What if we want to avoid reallocating a fresh object, and use a cached one instead?
So it’s clear that you don’t want to publicize your constructors to the clients of your API, as all they can do is tie you down.
The standard recommended solution is to use a static factory. This however, does nothing to help the other victims of constructors - their callers. As a consumer of an API, you don’t want to use constructors: they induce a tight coupling between your code and specific implementations. You can’t abstract over static methods, just as you can’t abstract over constructors. In both cases, there is no object that is the target of the operation and a conventional interface declaration cannot describe it. The absence of an object means that constructors don’t have the benefits objects bring - dynamic binding of method calls chief among these. Which is why constructors and static methods don’t work well, and incidentally, aren’t object oriented.
Having dismissed constructors and static factories, it seems we need to define a factory class whose instances will support an interface that includes a method that constructs the desired objects. How will you create the factory object? By calling a constructor? Or by defining a meta-factory? After how many meta-meta-meta- .. meta-factories do you give up and call a constructor?
What about using a dependency injection framework (DIF)? Ignoring the imbecilic name, I think that if you’re stuck with a mainstream language, that may be a reasonable work around. It requires a significant degree of preplanning, and makes your application dependent on one more piece of machinery that has nothing to do with the actual problem the application is trying to solve. On the positive side, it helps guarantee employment for software engineers. That said, it’s important to understand that DIFs are just a work around for a deficiency in the underlying language.
So why not get rid of constructors and have a class declaration create a factory object instead? Well, Smalltalk did just that a generation ago. Every time you define a class, you define the factory object for its instances. I won’t explain the Smalltalk metaclass hierarchy here. Suffice to say that it is a thing of beauty, resolving a potential infinite regress with an elegant circularity.
Despite this, Smalltalk still does not provide an ideal solution for creating and initializing instances. While it preserves abstraction, it does not easily enable the class to ensure that every instance will always be properly initialized, or that initialization will take place only once. To be sure, these are difficult goals, and Java, despite enormous efforts and complexity focused on these goals, does not fully achieve them either. However, it comes close - at the cost of abstraction failure brought about by the use of constructors.
So can we do better? Of course. The solution combines elements of Scala constructors (which are cleaner than Java constructors) with elements of the Smalltalk approach.
Scala defines a class as a parametric entity, with formal parameters that are in scope in the class body. The class name, together with its formal parameters, define the primary constructor of the class. This allows the instance to initialize itself, accessing the parameters to the constructor without exposing an initialization method that can be called multiple times on an instance. The latter is one of the problems in Smalltalk.
We use a similar device to provide access to the constructor parameters from within the instance. However, we require that the class provide a method header for its primary constructor. Instead of creating instances by a special construct (constructor invocation) as in Java or Scala, we create them via method invocation. The class declaration introduces a factory object that supports the primary constructor as an instance method.
Because we create objects only by invoking methods on other objects, we preserve abstraction. We can create objects by invoking the constructor method on a parameter. We can always define alternative factory objects that support the same constructor method with different behavior, and pass them instead of the class. Furthermore, using a message based programming language, references to the class’ name are always virtual, and can be overridden.
Unlike Smalltalk, the factory class is not a subclass of the superclass factory class. This prevents the possibility of calling superclass constructors and thereby creating partially initialized objects (doing this requires special effort in Smalltalk - one has to manually override the superclass constructors so that they fail; this is tedious and error prone, and not done much in practice).
I know I should be writing examples to make this all clear. However, this post is getting long, so that will wait for another post. I’ll be speaking about some of this work next month a the dynamic language workshop at ECOOP. By then, I imagine I’ll put out some examples of what we’ve been doing these past few months.
Of course, the problem is that constructors don’t work very well all. Understanding why helps to understand what “object oriented” really means, and why it is important.
Constructors come with a host of special rules and regulations: they cannot be overridden like instance methods; they need to call another constructor, or a superclass constructor etc. Try defining mixins in the presence of constructors - it’s tricky because the interface for creating instances gets bundled with the interface of the instances themselves.
The basic issue is a failure of abstraction, as Dave Ungar put it in his OOPSLA keynote in 2003.
Suppose we have a constructor C(x) and code that creates objects by calling it. What happens if we find that we actually need to return an instance of a class other than C? For example, we might want to lazily load data from secondary storage, and need to return some sort of placeholder object that behaves just like a C, but isn’t? What if we want to avoid reallocating a fresh object, and use a cached one instead?
So it’s clear that you don’t want to publicize your constructors to the clients of your API, as all they can do is tie you down.
The standard recommended solution is to use a static factory. This however, does nothing to help the other victims of constructors - their callers. As a consumer of an API, you don’t want to use constructors: they induce a tight coupling between your code and specific implementations. You can’t abstract over static methods, just as you can’t abstract over constructors. In both cases, there is no object that is the target of the operation and a conventional interface declaration cannot describe it. The absence of an object means that constructors don’t have the benefits objects bring - dynamic binding of method calls chief among these. Which is why constructors and static methods don’t work well, and incidentally, aren’t object oriented.
Having dismissed constructors and static factories, it seems we need to define a factory class whose instances will support an interface that includes a method that constructs the desired objects. How will you create the factory object? By calling a constructor? Or by defining a meta-factory? After how many meta-meta-meta- .. meta-factories do you give up and call a constructor?
What about using a dependency injection framework (DIF)? Ignoring the imbecilic name, I think that if you’re stuck with a mainstream language, that may be a reasonable work around. It requires a significant degree of preplanning, and makes your application dependent on one more piece of machinery that has nothing to do with the actual problem the application is trying to solve. On the positive side, it helps guarantee employment for software engineers. That said, it’s important to understand that DIFs are just a work around for a deficiency in the underlying language.
So why not get rid of constructors and have a class declaration create a factory object instead? Well, Smalltalk did just that a generation ago. Every time you define a class, you define the factory object for its instances. I won’t explain the Smalltalk metaclass hierarchy here. Suffice to say that it is a thing of beauty, resolving a potential infinite regress with an elegant circularity.
Despite this, Smalltalk still does not provide an ideal solution for creating and initializing instances. While it preserves abstraction, it does not easily enable the class to ensure that every instance will always be properly initialized, or that initialization will take place only once. To be sure, these are difficult goals, and Java, despite enormous efforts and complexity focused on these goals, does not fully achieve them either. However, it comes close - at the cost of abstraction failure brought about by the use of constructors.
So can we do better? Of course. The solution combines elements of Scala constructors (which are cleaner than Java constructors) with elements of the Smalltalk approach.
Scala defines a class as a parametric entity, with formal parameters that are in scope in the class body. The class name, together with its formal parameters, define the primary constructor of the class. This allows the instance to initialize itself, accessing the parameters to the constructor without exposing an initialization method that can be called multiple times on an instance. The latter is one of the problems in Smalltalk.
We use a similar device to provide access to the constructor parameters from within the instance. However, we require that the class provide a method header for its primary constructor. Instead of creating instances by a special construct (constructor invocation) as in Java or Scala, we create them via method invocation. The class declaration introduces a factory object that supports the primary constructor as an instance method.
Because we create objects only by invoking methods on other objects, we preserve abstraction. We can create objects by invoking the constructor method on a parameter. We can always define alternative factory objects that support the same constructor method with different behavior, and pass them instead of the class. Furthermore, using a message based programming language, references to the class’ name are always virtual, and can be overridden.
Unlike Smalltalk, the factory class is not a subclass of the superclass factory class. This prevents the possibility of calling superclass constructors and thereby creating partially initialized objects (doing this requires special effort in Smalltalk - one has to manually override the superclass constructors so that they fail; this is tedious and error prone, and not done much in practice).
I know I should be writing examples to make this all clear. However, this post is getting long, so that will wait for another post. I’ll be speaking about some of this work next month a the dynamic language workshop at ECOOP. By then, I imagine I’ll put out some examples of what we’ve been doing these past few months.
Subscribe to:
Posts (Atom)