Room 101

A place to be (re)educated in Newspeak

Tuesday, April 19, 2022

Bitrot Revisited: Local First Software and Orthogonal Synchronization

This post is based on a invited talk I gave recently at the Programming 22 conference.

The talk wasn't recorded but I've recorded a reprise at:

The definition of insanity not withstanding, I decided to revisit a topic I have discussed many times before: Objects as Software Services. In particular, I wanted to relate it to recent work others have been doing.

The earliest public presentation I gave on this at the DLS in 2005. There are recordings of talks I gave at Google and Microsoft Research, as well as several blog posts ( March 2007, April 2008, April 2009, January 2010 and April 2010). You can also download the original write up.

The goal is software that combines the advantages of old-school personal computing and modern web-based applications. There are two parts to this.

First, software should be available at all times. Like native apps, software should be available even if the network is slow, unreliable or absent, or if the cloud is otherwise inaccessible (say due to denial-of-service, natural disaster, war or whatever). And, like a cloud app, it should be accessible from any machine at any location (modulo network access if it hasn't run there before). Recently, this idea has started to get more attention under the name local-first software.

Tangent: I've proposed a number of terms for closely related ideas in older posts such as Software Objects, Rich Network Enabled Clients, Network Serviced Applications and Full-Service Computing, but whatever name gets traction is fine with me.

Second, software should always be up-to-date (this is where Bitrot comes in). That means we always want to run the latest version available, just like a web page. This implies automatically updating application code over the network without disrupting the end-user. This latter point goes well beyond the idea of local-first software as I've seen it discussed.

Let's take these two goals in order.
  • For offline availability, one has to store the application and its data locally on the client device. However, unlike classical personal computing, the data has to be made available, locally, to multiple clients. Now we have multiple replicas of our data, and they have to be kept in sync somehow. My proposal was to turn that responsibility over to the programming language via a concept I dubbed Orthogonal Synchronization. The idea was to extend the concept of orthogonal persistence, which held that the program would identify which fields in every data structure were deemed persistent, and the system would take care of serializing and deserializing their contents, recursively. With orthogonal synchronization, the data would not only be persisted automatically, but synchronized.
  • To keep the software up-to-date without disrupting the user, we want good support for dynamic software update. When the application code changes, we update the app live. How do we know when the code changes? Well, code is just data, albeit of a particular kind. Hence we sync it, just like any other persistent data. We reuse much of the same orthogonal synchronization mechanism, and since we sync both code and data at the same time, we can migrate data seamlessly whenever the code and data format changes. As I've discussed in the past, this has potentially profound implications for versioning, release cycles and software development. All this goes well beyond the focus of local-first software, and is way outside the scope of this post. See the original materials cited above for more on that aspect.
There's only one small problem: merge conflicts. The natural tendency is to diff the persistent representations to compute a set of changes and detect conflicts. An alternative is to record changes directly, whenever setters of persistent objects are called. Either way, we are comparing the application state at the level of individual objects. This is very low level; it is an extensional approach, which yields no insight into the intention of the changes. As an example, consider a set, represented as an array of elements and an integer indicating the cardinality of the set. If two clients each add a distinct object to the set, we find that they both have the same set object, but the arrays differ. The system has no way to resolve the conflict in a satisfactory manner: choosing either replica is wrong. If one understands the intention of the change, one could decide to resolve the conflict by performing both additions on the original set.

Local first computing approaches this problem differently. It still needs to synchronize the replicas. However, the problem of conflicts is elegantly defined away. The idea is to use Conflict-free Replicated Data Types (CRDTs) for all shareable data, and so conflicts cannot arise. This is truly brilliant as far as it goes. And CRDTs go further than one might think.

CRDT libraries record intentional changes at the level of the CRDT object (in our example, the set, assuming we use a CRDT implementation of a set); sync is then just the union of the change sets, and no conflicts arise. However, the fact that no formal conflict occurs does not necessarily mean that the result is what we actually expect. And CRDTs don't provide a good solution for code update.

Can we apply lessons from CRDTs to orthogonal synchronization? The two approaches seem quite contradictory: CRDTs fly in the face of orthogonal persistence/synchronization. The 'orthogonal' in these terms means that persistence/synchronization is orthogonal to the datatype being persisted/synced. You can persist/sync any datatype. In contrast, using CRDTs for sync means you have to use specific datatypes. One conclusion might be that orthogonal sync is just a bad idea. Maybe we should build software services by using CRDTs for data, and structured source control for code. However, perhaps there's another way.

Notice that the concept of capturing intentional changes is distinct from the core idea of CRDTs. It's just that, once you have intentional changes, CRDTs yield an exceptionally simple merge strategy. So perhaps we can use orthogonal sync, but incorporate intentional change data and then use custom merge functions for specific datatypes. CRDTs could fit into this framework; they'd just use a specific merge strategy that happens to be conflict-free. However, we now have additional options. For example, we can merge code with a special strategy that works a bit like traditional source control (we can do better, but that's not my point here). As a default merge strategy when no intent is specified, we could treat setter operations on persistent slots as changes and just ask the user for help in case of conflict. We always have the option to specify an alternate strategy such as last-write-wins (LWW).

How might we specify what constitutes an intentional change, and what merge strategy to use? One idea is to annotate mutator methods with metadata indicating that they are changes associated with a given merge strategy. Here is what this might look like for a simple counter CRDT:

class Counter = (| count ::= 0. |)(
public value = (^count)
public increment (* :crdt_change: *) = (
count: count + 1
public decrement (* :crdt_change: *) = (
count: count - 1
The metadata tag (crdt_change in this case) identifies a tool that modifies the annotated method so that calls are recorded as change records with salient information (name of called method, timestamp, arguments) as well as a merge method that processes such changes according to a standardized API.

Now, to what extent is this orthogonal sync anymore? Unlike orthogonal persistence, we can't just mark slots as persistent and be done; we have to provide merge strategies. Well, since we have a default, we can still argue that sync is supported regardless of datatype. Besides, quibbling over terminology is not the point. We've gained real flexibility, in that we can support both CRDTs and non-CRDTs like code. And CRDT implementations don't need to incorporate special code for serialization and change reporting. The system can do that for them based on the metadata.

I've glossed over many details. If you watch the old talks, you'll see many issues discussed and answered. Of course, the proof of the pudding is in creating such a system and building working applications on top. I only managed to gather funding for such work once, which is how we created Newspeak, but that funding evaporated before we got very far with the sync problem. Sebastián Krynski worked on some prototypes, but again, without funding it's hard to make much progress. Nevertheless, there is more recognition that there is a problem with traditional cloud-based apps. As the saying goes: this time it's different.

Thursday, August 12, 2021

How is a Programmer Like a Pathologist?

Blogging platforms like Blogger are totally inadequate, because they don't support embedding interactive code in posts. So this is just an indirection for the real post at:

Sunday, May 24, 2020

Bits of History, Words of Advice

"Why do you jackasses use these inferior linguistic vehicles when we have something here that’s so
precious, so elegant, which gives me so much pleasure? How can you be so blind and so foolish?"
That debate you’ll never win, and I don’t think you ought to try.

- Alan Perlis, 1978

In the late 1970s, researchers at Xerox Parc invented modern computing.  Of course, there were others
elsewhere - but Parc made a vastly disproportionate contribution.

A large part of that was done in, and based upon, the Smalltalk programming language. Forty years
ago, Smalltalk's dynamic update and reflection capabilities were more advanced than in any
mainstream language today. The language leveraged those capabilities to provide an IDE that in
many ways still puts the eclipses, black holes, red dwarfs and other travesties that currently
masquerade under that term to shame.  The Smalltalk image provided a much better Docker than

Smalltalk and Smalltalkers invented not only IDEs, but window systems and their related paraphernalia
(pop-up menus, scroll bars, the bit-blt primitives that make them possible) as well as GUI builders,
unit testing, refactoring and agile development (ok, so nobody's perfect).

And yet, today Smalltalk is relegated to a small niche of true believers.  Whenever two or more
Smalltalkers gather over drinks, the question is debated: Why? 

The answer is unknowable, since we cannot run parallel universes and tweak things to see which
makes a difference

 I did describe such an alternate universe in a talk in 2016; it may be the best talk I ever gave.

Nevertheless, I think we can learn something from looking into this question. I'll relate parts of history
that I deem relevant, as I know them. I'm sure there are inaccuracies in the account below.
There are certainly people who were closer to the history than I.  My hope is that they'll expand on my
comments and correct me as needed. I'm sure I'll be yelled at for some of this. See if I care.

On with the show.

Lack of a Standard. Smalltalk had (and still has) multiple implementations - more so than much
more widely used languages. In a traditional business, having multiple sources for a technology
would be considered an advantage. However, in Smalltalk's case, things proved to be quite different. 

Each vendor had a slightly different version - not so much a different language, as a different platform.
In particular, Smalltalk classes do not have a conventional syntax; instead, they are defined via
reflective method invocation. Slight differences in the reflection API among vendors meant that the
program definitions themselves were not portable, irrespective of other differences in APIs used by the

There were of course efforts to remedy this. Smalltalk standardization efforts go back to the late 80s,
but were pushed further in the 90s. Alas, in practice they had very little impact.

Newspeak of course, fixed this problem thoroughly, along with many others. But we were poorly funded
after the 2008 crash, and never garnered much interest from the Smalltalk community.
The community's lack of interest in addressing weaknesses in the Smalltalk-80 model will be a
recurring theme throughout this post.

Business model. Smalltalk vendors had the quaint belief in the notion of "build a better mousetrap
and the world will beat a path to your door".  Since they had built a vastly better mousetrap, they
thought they might charge money for it. 

This was before the notion of open source was even proposed; though the Smalltalk compilers, tools
and libraries were provided in source form; only the VMs were closed source.

Alas, most software developers would rather carve their programs onto stone tablets using flint tools
held between their teeth than pay for tools, no matter how exquisite. Indeed, some vendors charged
not per-developer-seat, but per deployed instance of the software. Greedy algorithms are often
suboptimal, and this approach was greedier and less optimal than most. Its evident success speaks
for itself.

In one particularly egregious and tragic case, I'm told ParcPlace declined an offer from Sun
Microsystems to allow ParcPlace Smalltalk to be distributed on Sun workstations. Sun would pay a per
machine license fee, but it was nowhere near what ParcPlace was used to charging.

Eventually, Sun developed another language; something to do with beans, I forget. Fava, maybe?
Again, dwell on that and what alternative universe might have come about.

Performance and/or the illusion thereof.

Smalltalk was and is a lot slower than C, and more demanding in terms of memory. In the 1980s and
early 1990s, these were a real concern. In the mid-1990s, when we worked on Strongtalk, Swiss
banks were among our most promising potential customers. They already had Smalltalk applications
in the field. They could afford to do so where others could not. For example, they were willing to equip
their tellers with powerful computers that most companies found cost-prohibitive - IBM PCS with a
massive 32Mb of memory! 

It took a long time for implementation technology to catch up, and when it did, it got applied to lesser
languages. This too was a cruel irony. JITs originated in APL, but Smalltalk was also a pioneer in that
field (the Deutsch-Schiffman work), and even more so Self, where adaptive JITs were invented. 

Strongtalk applied Self's technology to Smalltalk, and made it practical. 

Examples: Self needed 64Mb, preferably 96, and only ran on Sun workstations. Strongtalk ran in 8Mb
on a PC. This mattered a lot. And Strongtalk had an FFI, see below.

Then, Java happened.  Strongtalk was faster than Java in 1997, but Strongtalk was acquired by Sun;
the VM technology was put in the service of making Java run fast.  

The Smalltalk component of Strongtalk was buried alive until it was too late. By the time I finally got it
open-sourced , bits had rotted or disappeared, the system had no support, and the world had moved on.
And yet, the fact that the Smalltalk community took almost no interest in the project is still telling.

Imagine if all the engineering efforts sunk into the JVM had focused on Smalltalk VMs.

It's also worth dwelling on the fact that raw speed is often much less relevant than people think.
Java was introduced as a client technology (anyone remember applets?). The vision was programs
running in web pages. Alas, Java was a terrible client technology. In contrast, even a Squeak
interpreter, let alone Strongtalk, had much better start up times than Java, and better interactive
response as well. It also had much smaller footprint. It was a much better basis for performant client
software than Java. The implications are staggering. 

On the one hand, Netscape developed a scripting language for the browser. After all Java wouldn't cut
it. Sun gave them permission to use the Java name for their language.  You may have heard of this
scripting language; it's called Javascript. 

Eventually, people found a way to make Javascript fast. Which people? Literally some of the same
people who made Strongtalk fast (Lars Bak), using much the same principles.

Imagine if Sun had a workable client technology. Maybe the Hot Java web browser would still be

On the other hand, the failure of Java on the client led to an emphasis on server side Java instead.
This seemed like a good idea at the time, but ultimately commoditized Sun's product and contributed
directly to Sun's downfall. Sun had a superb client technology in Strongtalk, but the company's
leadership would not listen. 

Of course, why would they? They had shut down the Self project some years earlier to focus on Java.
Two years later, they spent an order of magnitude more money than it cost to develop Self, to buy back
essentially the same technology so they could make Java performant.

Interaction with the outside world.

Smalltalk had its unique way of doing things. Often, though not always, these ways were much better
than mainstream practice. Regardless, it was difficult to interact with the surrounding software
environment. Examples:

FFIs. Smalltalk FFIs were awkward, restrictive and inefficient. After all, why would you want to reach
outside the safe, beautiful bubble into the dirty dangerous world outside?

We addressed this back in the mid-90s in Strongtalk, and much later, again, in Newspeak.  

Windowing. Smalltalk was the birthplace of windowing. Ironically, Smalltalks continued to run on top
of their own idiosyncratic window systems, locked inside a single OS window. 

Strongtalk addressed this too; occasionally, so did others, but the main efforts remained focused on
their own isolated world, graphically as in every other way. Later, we had a native UI for Newspeak as

Source control. The lack of a conventional syntax meant that Smalltalk code could not be managed
with conventional source control systems. Instead, there were custom tools. Some were great - but
they were very expensive.

In general, saving Smalltalk code in something so mundane as a file was problematic. Smalltalk used
something called file-out format, which is charitably described as a series of reflective API calls, along
with meta-data that includes things like times and dates when the code was filed out. This compounded
the source control problem.

Deployment. Smalltalk made it very difficult to deploy an application separate from the programming
environment. The reason for this is that Smalltalk was never a programming language in the traditional
sense. It was a holistically conceived programming system. In particular, the idea is that computation
take place among communicating objects, which all exist in some universe,  a "sea of objects". Some
of these object know how to create new ones; we call them classes (and that is why there was no
syntax for declaring a class, see above).

What happens when you try to take some objects out of the sea in which they were created (the IDE)?
Well, it's a tricky serialization problem.  Untangling the object graph is very problematic.

If you want to deploy an application by separating it from the IDE (to reduce footprint, or protect your IP,
or avoid paying license fees for the IDE on each deployed copy) it turns out to be very hard.

The Self transporter addressed this problem in a clever way. Newspeak addressed it much more
fundamentally and simply, both by recognizing that the traditional linguistic perspective need not
contradict the Smalltalk model, and by making the language strictly modular.

The problem of IP exposure is much less of a concern today. It doesn't matter much for server based
applications, or for open source software. Wasted footprint is still a concern, though in many cases you
can do just fine. Avi Bryant once explained to me how he organized the server for the late, great
Dabble DB. It was so simple you could just cry, and it performed like a charm using Squeak images.
Another example of the often illusory focus on raw performance.

So why didn't Smalltalk take over the world? 

With 20/20 hindsight, we can see that from the pointy-headed boss perspective, the Smalltalk value
proposition was: 

Pay a lot of money to be locked in to slow software that exposes your IP, looks weird on screen and
cannot interact well with anything else; it is much easier to maintain and develop though!

On top of that, a fair amount of bad luck.

And yet, those who saw past that, are still running Smalltalk systems today with great results; efforts to
replace them with modern languages typically fail at huge cost.

All of the problems I've cited have solutions and could have been addressed. 
Those of us who have tried to address them have found that the wider world did not want to listen -
even when it was in its own best interest. This was true not only of short sighted corporate leadership,
but of the Smalltalk community itself.  

My good friends in the Smalltalk community effectively ignored both Strongtalk and Newspeak.
It required commitment and a willingness to go outside their comfort zone.

I believe the community has been self-selected to consist of those who are not bothered by Smalltalk's
initial limitations, and so are unmotivated to address them or support those who do. In fact, they often
could not even see these limitations staring them in the face, causing them to adopt unrealistic
business policies that hurt them more than anyone else.

Perhaps an even deeper problem with Smalltalk is that it attracts people who are a tad too creative and
imaginative; organizing them into a cohesive movement is like herding cats.

Nevertheless, Smalltalk remains in use, much more so than most people realize. Brave souls continue
to work on Smalltalk systems, both commercial and open source. Some of the issues I cite have been
addressed to a certain degree, even if I feel they haven't been dealt with as thoroughly and effectively
as they might. More power to them. Likewise, we still spend time trying to bring Newspeak back to a
more usable state. Real progress is not made by the pedantic and mundane, but by the dreamers who
realize that we can do so much better.

Eppur si muove

Monday, January 06, 2020

The Build is Always Broken

Programmers are always talking about broken builds: "The build is broken", "I broke the build" etc. However, the real problem is that the very concept of the build is broken. The idea that every time an application is modified, it needs to be reconstructed from scratch is fundamentally flawed. A practical problem with the concept is that it induces a very long and painful feedback loop during development. Some systems address this by being wicked fast. They argue that even if they compile the world when you make a change, it's not an issue since it'll be done before you know it. One problem is that some systems get so large that this doesn't work anymore. A deeper problem is that even if you rebuild instantly, you find that you need to restart your application on every change, and somehow get it back to the stage where you were when you found a problem and decided to make a change. In other words, builds are antithetical to live programming. The feedback loop will always be too long. Fundamentally, one does not recreate the universe every time one changes something. You don't tear down and reconstruct a skyscraper everytime you need to replace a light bulb. A build, no matter how optimized, will never give us true liveness It follows that tools like make and its ilk can never provide a solution. Besides, these tools have a host of other problems. For example, they force us to replicate dependency information that is already embedded in our code: things like imports, includes, uses or extern declarations etc. give us the same file/module level information that we manually enter into build tools. This replication is tedious and error prone. It is also too coarse grain, done at the granularity of files. A compiler can manage these dependencies more precisely, tracking what functions are used where for example. Caveats: Some tools, like GN, can be fed dependency files created by cooperating compilers. That is still too coarse grain though. In addition, the languages these tools provide have poor abstraction mechanisms (compare make to your favorite programming language) and tooling support (what kind of debugger does your build tool provide?). The traditional response to the ills of make is to introduce additional layers of tooling of a similar nature, like Cmake. Enough!

A better response is to produce a better DSL for builds. Internal DSLs, based on a real programming language, are one way to improve matters. Examples are rake and scons, which use Ruby and Python respectively. These tools make defining builds easier - but they are still defining builds, which is the root problem I am concerned with here. So, if we aren't going to use traditional build systems to manage our dependencies, what are we to do? We can start by realizing that many of our dependencies are not fundamental; things like executables, shared libraries, object files and binaries of whatever kind. The only thing one really needs to "build" is source code. After all, when you use an interpreter, you can create only the source you need to get started, and then incrementally edit/grow the source. Using interpreters allows us to avoid the problems of building binary artifacts. The cost is performance. Compilation is an optimization, albeit an important, often essential, one. Compilation relies on a more global analysis than an interpreter, and on pre-computing the conclusions so we need not repeat work during execution. In a sense, the compiler is memoizing some of the work of the interpreter. This is literally the case for many dynamic JITs, but is fundamentally true for static compilation as well - you just memoize in advance. Seen in this light, builds are a form of staged execution, and the binary artifacts that we are constantly building are just caches. One can address the performance difficulties of interpreters by mixing interpretation with compilation. Many systems with JIT compilers do exactly that. One advantage is that we don't have to wait for the optimization before starting our application. Another is that we can make changes, and have them take effect immediately by reverting to interpretation, while re-optimizing. Of course, not all JITs do that; but it has been done for decades, in, e.g., Smalltalk VMs. One of the many beauties of working in Smalltalk is that you rarely confront the ugliness of builds. And yet, even assuming you have an engine with a JIT that incrementally (re)optimizes code as it evolves, you may still be confronted with barriers to live development, barriers that seem to require a build. Types. What if your code is inconsistent, say, due to type errors? Again, there is no need for a build step to detect this. Incremental typecheckers should catch these problems the moment inconsistent code is saved. Of course, incremental typecheckers have traditionally been very rare; it is not a coincidence that live systems have historically been developed using dynamically typed languages. Nevertheless, there is no fundamental reason why statically typed languages cannot support incremental development. The techniques go back at least as far as Cecil; See this paper on Scala.js for an excellent discussion of incremental compilation in a statically typed language. Tests. A lot of times, the build process incorporates tests, and the broken build is due to a logical error in the application detected by the tests. However, tests are not themselves part of the build, and need not rely on one - the build is just one way to obtain an updated application. In a live system, the updated application immediately reflects the source code. In such an environment, tests can be run on each update, but the developer need not wait for them. Resources. An application may incorporate resources of various kinds - media, documentation, data of varying kinds (source files or binaries, or tables or machine learning models etc.). Some of these resources may require computation of their own (say, producing PDF or HTML from documentation sources like TeX or markdown), adding stages that are seldom live or incremental. Even if the resources are ready to consume, we can induce problems through gratuitous reliance on file system structure. The resources are typically represented as files. The deployed structure may differ from the source repository. Editing components in the source repo won't change them in the built structure. It isn't easy to correct these problems, and software engineers usually don't even try. Instead, they lean on the build process more and more. It doesn't have to be that way. We can treat the resources as cached objects and generate them on demand. When we deploy the application, we ensure that all the resources are precomputed and cached at locations that are fixed relative to the application - and these should be the same relative locations where the application will place them during development in case of a cache miss. The software should always be able to tell where it was installed, and therefore where cached resources stored at application-relative locations can be found. The line of reasoning above makes sense when the resource is accessed via application logic. What about resources that are not used by the application, but made available to the user? In some cases, documentation and sample code and attached resources might fall under this category. The handling of such resources is not part of the application proper, and so it is not a build issue, but a deployment issue. That said, deployment is simply computation of a suitable object to serialized to a given location, and should be viewed in much the same way as the build; maybe I'll elaborate on that in separate post. Dealing with Multiple Languages. Once we are dealing with multiple languages, we may be pushed into using a build system because some of the languages do not support incremental development. Assuming that the heart of our application is in a live language, we should treat other languages as resources; their binaries are resources to be dynamically computed during development and cached.


  • Builds kill liveness.
  • Compilation artifacts are a form of cached resource, the result of staged execution.
  • To achieve liveness in industrial settings, we need to structure our development environments so that any staging is strictly an optimization
    • Staged results should be cached and invalidated automatically when the underlying basis for the cached value is out of date.
    • This applies regardless of whether the staged value is a resource, a shared library/binary or anything else. 
    • The data necessary to compute the cached value, and to determine the cache's validity, must be kept at a fixed location, relative to the application. 

It's high time we build a new, brave, build-free world.

Saturday, January 12, 2019

Much Ado About Nothing

What sweet nothing does the title refers to? It could be about null, but it in fact will say nothing about that. The nothing in question is whitespace in program text. Specifically, whether whitespace should be significant in a programming language.

My instinct has always been that it should not. Sadly, there are always foolish souls who will not accept my instinct as definitive evidence, and so one must stoop to logical arguments instead.

Significant whitespace, by definition, places the burden of formatting on the programmer. In return, it can be leveraged to reduce syntactic noise such as semicolons and matching braces. The alleged
benefit is that in practice, programmers often deal with both formatting and syntactic noise, so eliminating one of the two is a win.

However, this only holds in a world without civilized tooling, which in turn may explain the fondness for significant whitespace, as civilized tooling (and anything civilized, really),  is scarce. Once you assume proper tooling support, a live pretty printer can deal with formatting as you type, so there is no reason for you to be troubled by formatting. So now you have a choice between two inconveniences. Either:

  • You use classical syntax, and programmers learn where to put the semicolons and braces,  and stop worrying about formatting, Or
  • You make whitespace significant, cleanup the syntax, and have programmers take care of the formatting.

At this point, you might say this a matter of personal preference, and can devolve into the kind of religious argument we all know and love. To tip the scales, pray consider the line of reasoning below. I don’t recall encountering it before which is what motivated this post.

In the absence of significant whitespace, a pretty printing (aka code formatting) is an orthogonal concern. We can choose whatever pretty printing style we like and implement a tool to enforce it.  Such a pretty-printer/code-formatter can be freely composed with any code source we have - a programmer typing into an editor, an old repository, and most importantly, other tools that spit out code - whether they transpile into our language or generate code in some other way.

Once whitespace is significant, all those code sources have to be cognizant of formatting.  The tool writer has to be worried about both syntax and formatting, whereas before only syntax was a concern.

You might argue that the whitespace is just another form of syntax; the problem is that it is not always context-free syntax. For example, using indentation to nest constructs is context sensitive, as the number of spaces/tabs (or backspaces/backtabs) depends on context.

In short, significant whitespace (or at least significant indentation) is a tax on tooling. Taxing tooling not only wastes the time and energy of tool builders - it discourages tooling altogether. And so, rather than foist significant whitespace on a language, think in terms of a broader system which includes tools. Provide a pretty printer with your language (like in Go).  Ideally, there's a version of the pretty printer that live edits your code as you type.

As a bonus,  all the endless discussions about formatting Go away, as the designers of Go have noted.  Sometimes the best way to address a problem is to define it away.

There. That was mercifully brief, right? Nothing to it.

Saturday, October 06, 2018

Reified Generics: The Search for the Cure

Many have argued that run time access to generic type information is very important. A very bitter debate about this ensued when we added generics to Java. The topic recurs whenever one designs a statically typed object oriented language. Should one reify generic types, or erase them? Java chose erasure, .Net and Dart chose reification, and all three solutions are in my mind unsatisfactory for various reasons, including but not limited to the handling of erasure or its presumed alter ego, reification.

Pedantic note 1: Throughout this post, I will use the terms erasure and reification as shorthand for erasure and reification of generic type information.

In a well designed object-oriented language, erasure and reification are not contradictory at all. This statement might bear some explanation, so here we go ...

A while back, I discussed the problem of shadow language constructs. I gave examples of shadow constructs such as Standard ML modules, traditional imports etc. Here is another: reified generics.

Generics introduce a form a shadow parameterization. Programming languages all have a perfectly good mechanism for declaring parameterized constructs and invoking them. You may have heard of it - it is widely known by the name function, and it goes back to the 17th century.

Pedantic note 2: Yes, programming language functions are usually not mathematical functions. The parameterization mechanism is however, essentially the same.

Generics introduce a different form of formal and actual parameters. There is a purpose to that: static analysis. However, when languages try to provide run time access to these parameters (i.e., reification of generics), we are creating a lobotomized twin of the existing runtime parameter passing system. A new, redundant, confusing and costly set of mechanisms is added to the run time in order to declare, pass, store and access these parameters.

The first guiding principle of any solution is to avoid shadow constructs. We already have parameterization support, let's use it.

Generics are functions from types to types, typically classes to classes.

Pedantic note 3: If your language is prototype based, generics might be considered functions between prototypes. If your language has primitive types - well, you're up the creek without a paddle anyway. There is no justification for primitive types in an object oriented language.

If classes are expressions, we can write reified generics as ordinary functions. Here's some sample pseudo-code. It's given in a quasi-standard syntax, so I don't waste time explaining Newspeak syntax.

public var List = (function(T) {  
   return class {
    var hd, tl;
       class Link {
         public datum;
         public next;
       public elementType() { return T}
       public add(e) {
           var tmp := Link new.
           tmp.datum := e;
  := hd;
           tl := hd;
           hd := tmp;
           return e;

 Here's a summary of what the above means:
  • We declare a variable named List, initialized to a closure.
  • The closure takes a class T as a parameter and returns a class as its result.
  • The result class is specified via a class expression, which implements a linked list.
  • The class expression includes a nested class declaration, Link.
  • The method memoize() is called on the closure to, well, memoize it. Memoize() returns a memoized version of its receiver.
Each call to List() returns a list class specialized to the actual parameter of List(). We can create a list of integers by saying

var lst := List(Integer).new();

and we can dynamically check what type of elements lst holds

lst.elementType(); // returns Integer, the class object reifying the integer type.

The reified element type is shared among all instances of a given list class, because it is stored in the closure surrounding the class. We avoid duplicating classes with the same parameters - this is just function memoization (and I assume a memoize() method on closures for this purpose). All this works independent of any static types. We are just using standard runtime mechanisms like closures, memoized functions, objects representing classes and yes, class expressions. Smalltalk had these, in essence, over 40 years ago.

What if I don't have class expressions? Well, don't you know that everything should be an expression? Besides, this works fine if you have the ability to define classes reflectively like Smalltalk, or have properly defined nested classes like Newspeak, though it may be a bit more verbose and require more library support to be palatable.

Now let's add types. In the code below, type annotations are completely optional, and have absolutely no runtime effect. They are shown in blue.

public var List = (function(T : Class) {  
   return class {
    var hd, tl : Link;
       class Link {
         public datum : T;
         public next : Link;
       public elementType() : Class { return T}
       public add:(e : T) : T {
           var tmp: Link := Link new.
           tmp.datum := e;
  := hd;
           tl := hd;
           hd := tmp;
           return e;

You may notice one odd thing - we use the name of the formal parameter to the closure, T, as a type. This is justified by the following rule.

Rule 1: In any method or closure m, a formal parameter T of type Class (or any subtype thereof) implicitly defines a type variable T which is in scope in type expressions from the point T is declared to the end of the method/closure.

Next, we need to be able to use the information given by the declaration of List when we write types like List[Integer]. We use the following rule.

Rule 2: If e is an expression of function type with parameter(s) of type Class and return type Class, e's name can be used inside a type expression as a type function; an invocation of the type function e[T1, ..., Tn] denotes the type of the instances of the class returned by the value expression
e(T1, ..., Tn).

We can then write, and typecheck

var lst : List[Integer] := List(Integer).new();
var i : Integer := lst.add(3) + 4;

Oh, and we can still do this:

lst.elementType(); // returns Integer, the class object reifying the integer type.

Similarly, if you wish to create new instances of the incoming type parameters, you should be able to do that in the above regime - though you will have to confront the fact that different subtypes may have different constructors and plan around that explicitly - say, by defining a common construction interface for these types.

The beauty of this scheme is that no runtimes were harmed in the making of this reified generic type system. The type system is completely optional. And this is my point: reification was there all along. The typechecker simply needs to understand this fact and leverage it. The basic approach would work with any language with types reified as values, regardless of whether it has generics.

Interestingly, we now have reification of generics, and erasure, at the same time. The two are not in conflict. Reification is supported by the normal runtime mechanisms, independent of types, which are optional and always erased, carrying no runtime cost or semantics.

Reification of generics is now a choice for library implementers. If they think it is worthwhile to pay the costs, so that, for example, someone can cheaply test if a collection is a collection of integers or a collection of strings, they are free to do so.

If they don't want to pay a price for reification but still want to typecheck generics, they can do that too. Nothing prevents one from explicitly declaring type parameters (as opposed to the implicit ones derived from the class-valued value parameters used for reification).

Tangent, TL; DR: Now is the time to mention that traditional reification of generics - that is, runtime support for a shadow parameterization mechanism - is a disaster. It hurts performance in both space and time; Just ask the brave VM engineers who struggled with these issues on the Dart VM. Mitigating that introduces enormous complexity into the runtime and requires a huge effort, which would be better spent doing something good and useful instead.

In systems designed to support multiple programming languages, reification brings a different problem. All languages must deal with the complexity of reification; worse they must conform to the expectations of the reified generic type system of the "master language" (C# or Java, for example).

Consider .Net, the poster child of generic reification. Originally, .Net was intended to be a multi-language system, but dynamic language support there has suffered, in no small part due to reification. Visual Basic was a huge success until .Net came along and made it conform to C#. And what Iron Ruby/Python programmer ever enjoyed being forced to feed type arguments (whatever those might be) into a collection they are creating?

In contrast, the JVM was conceived as a monolingual system. Sun management deluded themselves that Java was the ultimate programming language (though yours truly did try to hint, ever so gently, that further progress in PL was at least conceivable). And yet, the JVM has become home to a wide variety of languages. This is due to multiple factors, invokedynamic not the least among them. But erasure plays a crucial and underappreciated role here as well. If not for erasure, the JVM would have the above-mentioned problems wrt dynamic languages, just like .Net.

Of course, generics have many issues that are independent of reification. The great difficulties with generics come up when they interact with subtyping. All the problems of variance, as well as inference, are rooted in that interaction. If you are happy with any existing approach, you should be able to incorporate it into the above reification strategy - but I am not aware of any pre-existing generic design that I would consider satisfactory.

I think I may now have a plausible approach to the typing issues, but the margins of this blog are too narrow to contain it.  A follow up post will either make it all clear, or confess that it hasn't worked out. The above comments on reification stand on their own in any case.