Isomorphism is not Enough

Too often, I see arguments of the general form: “I can transform feature X into Y, and the reverse, while maintaining relevant properties. I have an isomorphism. Therefore, I don’t see the difference between X and Y.” For the arguments I’m likely to participate in, X and Y tend to be languages, features, abstractions, protocols, frameworks, or design patterns.

The problem with this line of argument: it assumes transformation is trivial in context, i.e. from the perspective of a language’s user.

For expressive equivalence, we need continuity and locality in addition to isomorphism. Assuming Px is a program from language X, and Py is a program from Y resulting from the translating Px:

  • continuity: every small change in a Px results in a small change in Py. Continuity can be expressed in terms of an asymptotic epsilon bound (as the change in Px approaches zero size, the change in Py also approaches zero).
  • locality: a bounded change in Px results in a change with a corresponding boundary in Py. Essentially, the transform respects modularity and encapsulation.

The mathematical terms to learn are homeomorphism and diffeomorphism.

Isomorphism is not enough. But it is a good place to start.

This entry was posted in Language Design. Bookmark the permalink.

3 Responses to Isomorphism is not Enough

  1. John Shutt says:

    There is, of course, a lot hidden in that phrase “relevant properties”; as I’ve noted elsewhere (about first-class objects), in practice it’s often impossible to recognize some relevant properties until one sees an example of their absence.

    But I agree wholehearted with what I take to be the basic message here, that when one is thinking “equivalence” and providing isomorphism, one is very likely to run afoul of inadequacies in continuity and locality. (This is, btw, very akin to my formal treatment of… perhaps I’d better find a neutral name for it (for discussion with you, anyway 🙂 ; the only thing that comes to mind instantly is the deeply uninspiring “meta-expressiveness”, so I’ll have to give it some thought)… using classes of “expressiveness” transformations to define topologies on two language systems (locality?), and then a third class of transformations to regulate the transformations from one system to the other (continuity?).)

  2. Continuity and locality seem like metrics of language similarity. i.e. as they approach zero, X becomes Y. Naturally, the difficulty of translating would also approach zero.

    But what is the point of having two practically identical languages?

    Why use multiple languages X and Y? Maybe because small changes in X do effect big changes in Y, or local changes in Y do create non-local changes in X.

    In other words, in part, it’s because such model transformations are not trivial that makes them so useful and interesting. 🙂

    • dmbarbour says:

      I do not suggest you’d want to use two expressively equivalent languages. But whether two languages (or two subsets of features) are expressively equivalent can be valuable information. There is also a relationship to `full abstraction`.

      I agree that the utility of a second language is sometimes to amplify expression. Another reason to have two languages is to control expression, e.g. to support optimization or real-time evaluation.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s