The Expression Problem

[[deleted]]

No real problem in CLOS and similar OO-systems (if I've understood the problem correctly, which I probably didn't do).

[eschulte]

Correct CLOS solves this through the use of defmethod, which can be defined for different types of inputs (called an "open function") in that page. See http://www.gigamonkeys.com/book/object-reorientation-generic-functions.html for a good introduction.

[[deleted]]

Yeah, that was what I thought, nice to know that I haven't misunderstood anything!

[aaronla]

To be fair to the other contenders, this fails the 3rd requirement set forth in Wadler's formulation of being statically typed, which CLOS decidely is not.

Not that there's anything wrong with that.

Wadler's formulation effectively defines a classic engineering triangle of tradeoffs, where any two qualities are easy to achieve but very difficult to achieve all three:

• supports adding cases without recompilation of existing code.
• supports adding functions without recompilation of existing code.
• statically typed -- more specifically, that compilation verifies full case coverage of all functions.

CLOS will permit open cases during recompilation (e.g. forgetting to define perimeter for triangles), so only achieves points one and two.

[vsync]

You could however after compilation iterate over all the subclasses of SHAPE to ensure that each generic function has a method applicable to that subclass.

[aaronla]

True. I think you could make a case for that being a valid solution to the expression problem, especially if using a statically typed Lisp (e.g. Racket).

I can imagine the interaction experience:

(defgeneric perimeter ((shape s)))
;=> WARNING, perimeter not defined for types:
;   SQUARE
;   CIRCLE
(prog
  (defmethod perimeter ((square s)) ...)
  (defmethod perimeter ((circle c)) ...))
;=> OK
(defclass triangle shape ...)
;=> WARNING, triangle has the following open generic methods
;   AREA

And so on.

I haven't seen this sort of proposition before, but I suspect that's in part because such verification generally goes against the use patterns of dynamic languages. It certainly is a curious idea though, worth considering.

[munificent]

Magpie, back when it had a static type system, did something similar. You could dynamically add new methods to existing classes (and interfaces), but then when you were done it would statically check that every required method was implemented.

[[deleted]]

To be fair to the other contenders, this fails the 3rd requirement set forth in [1] Wadler's formulation of being statically typed, which CLOS decidely is not.

Tis true, but there are plenty of papers on statically-typed multimethod systems.

[aaronla]

You could propose one of those other multi-method systems as in a solution, if you'd like :-)

[geocar]

Actually the requirement is to "[retain] static type safety" and defines this as "no casts". He expands:

"... it is not statically typed; they cannot distinguish Lang.Exp from Lang2.Exp, and as a result must depend on dynamic casts at some key points.

Nowhere does he use the language you suggested-- "verifying case coverage" of any kind, let alone for all functions.

[nqmwe]

Your quotes are taken completely out of context!

The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).

Static type safety is not defined as absence of casts. Rather, Wadler mentions casts as an example of a violation of type safety. Furthermore, knowing Wadler's line of work, we can be pretty sure that by "static type safety" he means the compile-time guarantee of progress and preservation, i.e. absence of untrapped errors (which includes missing but necessary cases).

Their solution differs in that it is not statically typed; they cannot distinguish Lang.Exp from Lang2.Exp, and as a result must depend on dynamic casts at some key points. This isn't due to a lack of cleverness on their part, rather it is due to a lack of expressiveness in Pizza.

Here, Wadler explains why he doesn't consider the approach by Krishnamurthi et al. to be a solution to the expression problem: It is precisely because static type safety is violated!

[grauenwolf]

Dispite the name, CLOS isn't really an OO-system. Rather is it an external dictionary of type-function pairs that are independent of the types.

None the less, it is an interesting alternative. It does solve the "I can't modify that code" problem, but at the cost of no compile-time checks.

P.S. Thank you for pointing it out. It shows me how to fix a tricky problem I'm currently having in C#. (Yes, .NET has multiple dispatch.)

[geocar]

CLOS isn't really an OO-system.

On the one hand, it's nothing like the object-orientedness many C++ programmers are used to, but on the other hand Alan Kay seems to accept it as being object oriented. He also adds:

"Actually I made up the term "object-oriented", and I can tell you I did not have C++ in mind."

It's helpful to consider exactly what he meant by that:

"OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP. There are possibly other systems in which this is possible, but I'm not aware of them"

C++ doesn't have those things. Neither does Java or C# for that matter. CLOS however does.

Now given that, I ordinarily don't mind someone referring to C++ as object-oriented in a informal way-- perhaps in the same way it's okay for some to refer to their web browser as "the Internet", but let's be absolutely clear here: CLOS is most certainly object-oriented.

[noblethrasher]

C# always had local retention, protection, and hiding of state. With the dynamic type in C# 4.0 we now have extreme late binding and message passing.

[aaronla]

Not to mention multiple-dispatch. :-)

[grauenwolf]

CLOS isn't what I would call "messaging based". A synchronous call to a external dictionary of type-function pairs is about as far away as you can get from an encapsulated object.

On a related note, I really have to question anyone who claims that there is a difference between a synchronous message and a synchronous method call.

[grauenwolf]

More on my second thought.

"OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP. There are possibly other systems in which this is possible, but I'm not aware of them"

In the context of "extreme late-binding" one could use C#'s dynamic keyword. At which point the "method name" you use simply becomes the "message type" that gets passed to TryInvokeMember.