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:

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.

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!

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.

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!

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.

A Nest of Classes

Nested classes, like classes and OO in general, come to us from Scandinavia. The language Beta introduced nested classes in a stunningly elegant way; Java popularized nested classes in a rather different way; and Newspeak builds on them pervasively, in a manner similar to Beta, but still distinct. In this post, I want to explore these variations on nested classes.

Traditional OO is built on classes. We note an obvious property:

(1) Classes contain methods.

Beta’s core idea is something they call a pattern. A pattern in this context has nothing to do with pattern matching as we know it in functional programming. Instead, a pattern unifies classes and methods (and types and functions and procedures, but never mind all that).

Since class = pattern = method, we can perform some substitutions on the remark given above

(2) Patterns contain patterns.

This is true in Beta, even if reading this right now, you aren’t clear what it means. Let’s do a few other substitutions of equals for equals:

(3) Classes contain classes.
(4) Methods contain classes.
(5) Methods contain methods

Item (3) gives us member classes (using Java terminology); (4) gives us local classes; and (5) gives us nested procedures, like Pascal used to have.

The nice things is that all of these features come for free! This is the power of composition. Furthermore, they are all governed by consistent rules, because they fall out of the same definitions.

One can push this even further - the language gBeta unifies patterns with mixins as well.

But wait - isn’t this going a bit too far? After all, there is abundant evidence suggesting that the distinction between nouns and verbs, or objects and procedures, is fundamental to human cognition. I know some very good (former) Beta programmers who confess that the uniformity can be confusing.

That is why Newspeak doesn’t unify classes and methods this way. However, thinking about the unification is valuable even if you don’t go through with it. It will help you produce a consistent and flexible result.

To be fair, there is a school of thought that argues that different things must be kept very different, and that they can then be specialized so that they are finely tuned to a specific need. The Modula-3 report made this point nicely with the following quote:

Look into any carpenter's tool-bag and see how many different hammers, chisels, planes and screw-drivers he keeps there - not for ostentation or luxury, but for different sorts of jobs.
- Robert Graves and Alan Hodges

Language design isn't carpentry however.

Beta’s ideas served as inspiration for Java’s nested classes. However, Java is a language in the mainstream tradition, with a philosophy closer to Modula than to Beta. When nested classes were being added to Java, Java already had distinct concepts for classes, methods and variables, and even distinct namespaces for them. This makes it hard to ensure that the rules are uniform and consistent. One tries; some of the smartest people I’ve ever met recommend building tables and cross checking systematically - but really, it is incredibly difficult.

Hence, the rules for nested classes are quite different from those for methods nested in classes for example. Consider the effect of a modifier such as final. A final class means one thing (a class that may not be subclassed) a final variable another (an immutable variable) and a final method yet another (a method that may not be overridden).

One of the most important discrepancies has to do with the instance vs. static distinction. A static variable is property of a class, but an instance variable is a property of a specific instance. Conceptually, this is true of methods as well - instance methods are considered a property of an object. That is why they must be dynamically bound - two objects might have different methods. Therein lies the power of object-oriented programming. However, in Java, a nested class is never a property of an individual object. This is different from Beta (and Newspeak) and carries major implications.

If a class is a property of an object, then virtual classes arise naturally. Furthermore, the power of polymorphism applies to classes as well. Since we can abstract over objects, we can abstract over their members; those members are typically methods, which is why object oriented and functional programming are not as a different as some would make them out to be. If the members of an object (rather than a class) can be classes, we can abstract over classes. This can help avoid the difficulties that dependency injection frameworks try so awkwardly to address. We’ve realized these benefits in Newspeak.

Altogether, lack of uniformity prevents a language’s constructs from composing together easily to produce an exponential takeoff in expressivity. Instead, the rules themselves compose, yielding an exponential takeoff in interactions between the them. That is why simplicity is so crucial in language design.

Newspeak obtains its power not from unifying classes and methods, but from unifying the mechanisms by which they are referenced. Names are always treated the same - as properties of objects, which are therefore late bound and subject to override by a single set of rules.

a. A name refers to the nearest lexically enclosing declaration of that name, if there is one; otherwise, it refers to a declaration inherited from the immediately surrounding classes’ superclass.

b. Every declaration is subject to override; if you override a declaration in a subclass, it takes effect wherever the overridden declaration is used.

That’s it. Note that for a name defined by an enclosing class to be visible, it must be declared in the lexically surrounding environment; it isn’t enough for it to be inherited. You must be able to see the declaration in the surrounding classes. If you don’t see it, it isn’t there.

This is deliberate, and different from the rules you may know from Java (assuming you ever figured out what those really are) or even Beta. One advantage of this rule is that you cannot capture a name referred to in a nested class when you add a member to a superclass.

From these very simple rules (and the lack of a global namespace) we get virtual classes, mixins, class hierarchy inheritance, and powerful modularity, as I’ve described in a number of forums.

There is the small issue of specifying this behavior precisely, and beyond that, the small matter of making it work. These are not totally trivial. The spec describes the rules. As for the implementation, I plan to describe it in a paper; in the meantime, the source is out there. You want to look at changes we’ve made to the Squeak Interpreter, in particular the pushImplicitReceiver byte code as implemented in Squeak’s Interpreter class.

I hope I have convinced you that nested classes are at once simpler and more powerful than you might have imagined. As always, keeping language design simple results in a more powerful language.

Patterns of Dynamic Typechecking

Dynamic type tests are ubiquitous in programming. Regardless of whether the programming language is statically or dynamically typed, object-oriented or functional, the need to establish what sort of value you are dealing with at run time is always there.

In object oriented languages constructs like Java’s instanceOf (or C# typeOf, or Smalltalk isKindOf:) serve this need - as do casts.

Some functional languages put a large emphasis on being “completely statically typed”. In fact, these languages rely heavily on dynamic typechecking in the guise of pattern matching. Somewhere in the middle lie constructs like typecase.

In most languages, constructs for dynamic typechecking undermine data abstraction. They allow one to test for the implementation type of a value. Checking whether an object is an instance of a particular class, or pattern matching against a specific datatype constructor suffer from this problem. In contrast, testing whether a value supports an interface is harmless. Dynamically typed languages don’t support that however.

An old trick is to add methods that support these kind of type queries. Where you might, in Java, define a class A that implements an interface T, you would simply define a method isT on A, that returns true. The problem is that you then need to define a version of isT that returns false for all other types that you might possibly encounter. To be safe, you’d add isT to Object. This is monkey patching of the highest order, and readers of this blog know my view “People don’t let Primitive Primates Program”.

However, there is an out. Define the default version of doesNotUnderstand: to check if the method name is of the form isX, where X has the form of a type identifier. If so, return false. Now all you need to do is define isT for the classes that actually support the T interface. Credit to Peter Ahe for proposing this. It’s in the current Newspeak implementation.

Pattern matching is much more general than isT however; using isT is equivalent to a simple nullary pattern - except for this annoying issue with data abstraction.

Recently, we’ve seen approaches that overcome the data abstraction problem: Scala and F# introduce pattern matching mechanism that allow you to preserve data abstraction. It was Scala’s influence, combined with demand from users at Cadence, that prompted me to examine the idea of supporting pattern matching in Newspeak.

One can’t just go graft a pattern matching construct on to Newspeak however. The only operations allowed in Newspeak are message sends. If we can’t express the matching constructs via messages, they cannot go into the language. This led me to the idea of pattern literals: a special syntax for patterns, that denotes a pattern object. We already have special syntax for number objects, string objects, closure objects etc., so adding pattern objects fits in quite naturally. The nice thing about such an approach is that patterns are first class values. Patterns can be abstracted over in methods, stored in slots and data structures, serialized to disk or what have you. You can’t do that with a pattern in ML or Haskell.

So what exactly would pattern matching in Newspeak look like? Well, Felix Geller has recently completed his masters thesis at HPI Potsdam on just that question. Felix has implemented an experimental language extension supporting pattern literals and integrated it into the Newspeak IDE. The new language features should be available in the next Newspeak refresh (coming to a computer near you, summer 2010).

In the new extension (NS3) patterns are matched against objects via a protocol very similar to Scala’s extractors, thereby preserving data abstraction. However, there is no special construct for pattern matching. Instead, complex patterns can be composed out simpler ones using combinators.

Of course, a quick scan of the literature shows that the functional community got there first. Mark Tullsen proposed first class patterns with combinators for Haskell a decade ago, and there are several other papers dealing with the idea. However, having a proposal does not guarantee that a feature is in fact included in a language; in practice, none of the popular functional languages supports first class patterns.

First class patterns combined with data abstraction are a potent combination. We mean to use them as first class queries that can be sent to objects of various sorts - ordinary in-memory collections, or databases, or logic programs. This is reminiscent of LINQ, except that the queries are first class so they can be abstracted over. You can write code that takes queries as parameters, accepts queries as input from the user, serializes and deserializes queries to persistent storage (allowing you to do meta-queries) and so on. And the beauty of a language like Newspeak is that all this requires but a fraction of the machinery you need in a mainstream setting.

Felix’s thesis will soon be available as a technical report. I am reluctant to steal his thunder before that, but once the report is out, I'll put out a follow up post that illustrates how this works and why it is neat.

The Brave New World of Full Service Computing

I’ve been trying to explain this for some six years with little success, but I’ll try again. It may be easier this time.

For the past generation, we have been living in a world of self-service computing, more commonly knows as personal computing. The person using/owning a personal/self service computer is responsible for managing that computer themselves. All the digital chores - installing and updating software, preventing malware infection, backing up storage etc. are the user’s responsibility. Most users hate that.

Worse, most users really can’t handle these chores at all. They run ancient versions of applications because they are deathly afraid to tamper with anything that somehow works. Their computers are warrens of digital disease, crawling with viruses. Their data is rarely backed up properly.

The evolution of network technology enables a new model: full service computing. Full service computing means that you abdicate a level of fine control over the computer to a service that handles your digital housekeeping. I discussed some implications of this in a post back in January.

You still choose applications that you want - but you must get them from the service; the service installs these applications for you; it keeps them up to date as long as you use the service; and it it ensures that they are safe to use. The service also backs up your data automagically, allowing you to easily search through old versions as needed. In the extreme case, the service actually provides you with the computers you use. That helps it ensure seamless software/hardware compatibility.

We can increasingly see vignettes of this brave new world. Web apps running in the cloud are one step in this direction; web apps storing data locally are a step further. A complete platform designed to hide the raw machine from the user is even closer to this vision. Such platforms started out in the world of mobile phones, and are clawing their way upwards from there: Android and iPhone/iPad. Windows 7 mobile is quite similar to the iPhone model (odd, isn’t it?). And ChromeOS is not dissimilar.

Tangent: How does Google keep Android and ChromeOS aligned? It doesn’t - I believe they are making it up as they go along. Eventually they should converge.

We still haven't seen an integration of the app store model with backup, but it can't be that far off. An option for MobileMe(insert Apple trademark here) subscribers to have an image of their iPad backed up on Apple's servers and browsable via a Time Machine (and again, Apple trademark) style interface is easy to imagine. This can then extend to data you want to share collaboratively, while still retaining a local copy for offline use.

In time, most users will gravitate away from the self service computers they use today to software service platforms. This goes hand in hand with simpler UIs such as the iPad’s. One of the technical features in this evolution is the disappearance of the file system in favor of a searchable database of objects, as I mentioned in a previous post.

Tangent: The move from personal computing to software services accessed via simpler devices is what is truly significant about the iPad. Those who worry about details such as whether it has a camera or Flash are completely missing the point.

All this is already happening, which makes it easier to explain the idea of objects as software services (see the video) now than in 2004/2005. Consider the trend of programming languages toward a pure object model: all data are objects.

Tangent: This is orthogonal to functional programming. Objects can be immutable, as in, e.g., Avarice.

So, we now have programs dealing with objects in primary storage running on platforms whose secondary storage consists of objects as well. Initially, programmers find that they must explicitly manage the transition of data from primary to secondary storage.

The programmer’s task is simplified if that transition can be automated. This is an old idea known as orthogonal persistence. The Achilles’ heel of orthogonal persistence was the divergence of in-memory data representation and persistent data representation. This argued for manual management of the transition between primary and secondary storage.

However, circumstances are changing. The difference between transient (in-memory) and persistent (secondary storage) representations was driven by several factors, none of which apply in the full service computing model.

The first factor was that programs changed their internal representation while persistent data lived forever. Orthogonal persistence broke down when old data became incompatible with program data structures.

In our brave new world, programs co-evolve with their data so this is not an issue. The service manages both the application and secondary storage, updating them in lock step. Thus, we have data that is not only orthogonally persistent, but orthogonally synchronized.

The second factor was that persistent data formats were a medium of exchange between different programs with different internal data representations. This relied on the file system, may it rest in peace. The new applications are in fact compelled to keep their persistent data in silos tied to the application, and communicate with other applications in constrained ways.

This sets the stage for a model where programs are written in a purely object oriented language that supports orthogonal synchronization of both programs and data. This model eases the programmer’s task, and sits perfectly in the world of full service computing.

I have been discussing language support for this vision of software services publicly since my talk at DLS 2005, and privately long before. Newspeak’s modularity and reflection features dovetail perfectly with that.

Newspeak allows programs to be represented as objects; these objects are compact and self contained, thanks to the modularity of Newspeak code. Newspeak programs can be updated on the fly, atomically. Together, these two features provide a foundation for synchronizing programs. And the Newspeak VM supports shallow object immutability, which helps us synchronize data. On this basis, we have implemented experimental support for orthogonal synchronization, though it is very immature. I hope that in the future, we can provide an open software service based on this idea.

Of course, the radical edge the objects as software services vision is the complete abolishment of versions for libraries as well as applications. That is, I admit, untested, controversial and futuristic. However, with respect to applications, it is already starting to happen.