Saturday, January 02, 2010

Avarice and Sloth

Are these my new year resolutions? No (ok; maybe, but we won't go there), they are the names of two hypothetical programming languages.

The world is slowly digesting the idea that object-oriented and functional programming are not contradictory concepts. They are orthogonal, and can be arranged to be rather complementary. In that light, I’ve been dwelling on the idea of a purely functional subset of Newspeak: Avarice.

There is only one place in Newspeak where mutable state can be introduced: slot declarations. Newspeak supports both mutable and immutable slots. For example,

x ::= 0.

introduces a mutable slot; the declaration implicitly introduces both getter and setter methods (named x and x: respectively). An immutable slot declaration looks like this

y = 0.

In this case, only a getter is created, so there is no way to modify y after its introduction.

Disallow mutable slots, and you’re almost there.

There is one catch - the order of slot initialization is observable, and so you might detect a slot in its uninitialized state.

x = y.

y = 0.

will set x to nil. So much for referential transparency.

However, we also have simultaneous slot declarations, which are a bit like letrec. Alas, they aren’t implemented, and the spec needs tightening. Nevertheless, whatever variant we implement will prevent you from observing the uninitialized value of a slot. Once we add this feature, we can subset Newspeak and produce Avarice.

Of course, to make it work, we’d need to change a lot of the libraries. So maybe this is a little speculative at this point. This post will get even more speculative as we go along.

There is one more little nagging issue: reflection. What happens if we reflectively modify our program?

One answer is that we don’t; if we are serious about referential transparency, we cannot tolerate this sort of thing. This means that reflection is restricted to introspection, just like Java and C#. That’s still more than one get in existing pure functional programming.

Another answer is that we allow reflective change; we’re only functional at the base level, not the meta-level.

Note that the language doesn’t dictate a choice here: it depends what reflective library your implementation provides. In principle, you can provide multiple libraries, i.e., one that only supports introspection, and one that does the full thing. Lots to think about here.

Even restricted to introspection, Avarice would be rather different from most purely functional languages. It would carry none of the cultural baggage commonly associated with such languages: no currying, no Hindley-Milner type inference (indeed, no mandatory type system at all), no quasi-mathematical syntax. Is such a beast workable? Well, Erlang is. However, Avarice would also be object-oriented. Who knows, it might be the best of both worlds.

By now, my remaining readers are wondering what I’ve been smoking. Well, I don’t smoke, but red wine is good for you. In that spirit, we can take things further.

What if we make things lazy, like Haskell? This is not a Newspeak subset anymore - the semantics are rather different. However, syntactically, this language is identical to Avarice. We’ll call the lazy language Sloth, in contrast to its eager, dare I say even greedy, cousin Avarice. Sloth would be purely functional, and at the same time purely object oriented.

At this point, Avarice and Sloth are just imaginary constructions. They only exist in my mind, in this post, and in these slides. However, they make a nice thought experiment, and I hope to make them real in the fullness of time.

Regardless, sooner or later, someone will build a purely functional object oriented language. It will probably have a Javanese syntax and be rather hacky; but I hope Avarice and Sloth will be out there as well, for those who appreciate the finer things in life.

9 comments:

  1. Interesting post. I have actually been toying with doing the same kind of subsets for Ioke - both the lazy and strict versions.

    ReplyDelete
  2. I guess you're aware of the VPRI's FONC project, which is building what they call a Combined Object Lambda Architecture (COLA).

    The current implementation (Pepsi - not the real thing) seems to be moving in the right direction. I have reservations about other aspects of the project, but it may be worth a look.

    ReplyDelete
  3. Rob,

    Yes, well aware of the work at VPRI.

    ReplyDelete
  4. I would say OO and FP are dual, rather than orthogonal, and it would be interesting to see what a language which made that duality look rather trivial would actually look like.

    ReplyDelete
  5. Hi Roly,

    It's been a long time :-)

    Let me clarify what I meant.

    One can structure programs around data or around operations, and those are indeed dual. OO programs are primarily structured around data (objects), and functional programs primarily around operations (functions). But so are procedural programs - FP doesn't add anything there.

    Hence, the duality you refer to is not what makes FP special - after all, the operation-centric view is available in Fortran as well.

    Another characteristic of FP is the use of higher order functions. But we have those in OOP as well (at least, in the more civilized languages).

    What is most characteristic/special in FP is the absence of side effects. And *that* is orthogonal to the organizational paradigm that OOP promotes.

    ReplyDelete
  6. there's no reason for introspection to modify the data at the meta level, purely functional derivation should suffice. concepts like zippers and attribute grammars make it easy to rewrite complex hierarchies of data immutably with imperative or declarative metaphors.

    ReplyDelete
  7. and I should add that I think this is especially true in context because several versions of a module can coexist in the same runtime.

    ReplyDelete
  8. Hi Nothingmuch,

    The position you advocate is legitimate, as far as it goes. But it can get challenging when you implement a debugger, for example. Or if you want to evolve large quantities of long lived data. Actually recomputing the known universe is unattractive, tough you may be able to avoid it while maintaining the illusion that you do. Since pure functional languages have little tradition of reflection (even introspection), there is a need to experiment.

    ReplyDelete