Re: SoA Vs OO

From: Joachim Durchholz (jo_at_durchholz.org)
Date: 07/14/04 

Date: Wed, 14 Jul 2004 16:27:47 +0200

Mark S. Hathaway wrote:

> I am really enjoying this conversation about TYPEs.
> This is very enlightening for me.

Thanks :-)

>>>> "Joachim Durchholz" <jo@durchholz.org> wrote:
>>>>
>>>> OO classes don't support ADTs very well anyway, as I found (to my
>>>> dismay). They do the encapsulation aspect very well, but I found
>>>> that support for axiom checking is *very* important, and even
>>>> Eiffel's exceptional support in the form of
>>>> preconditions/postconditions/Design by Contract isn't quite enough.
>
> They enable the construction of a system of types, encapsulated
> of course, which relate. This has to be considered more powerful
> than simple Fortran integers and characters.

Agreed.
However, the key point is "a system of types ... *which relate*".
Not all relevant type relationships are subtypes. Sometimes you need to
specify that any type or its supertype is OK. Sometimes you need to
specify that the type must be equal to a template parameter (or a
subtype, or a supertype). Sometimes you need to specify things like "at
run-time, I don't care which type these two parameters have, but B must
be the same type as A, and descendant of COMPARABLE" - this latter
example is the typical contract for less-than and similar comparison
operators, and cannot be expressed using subtyping.

> It seems to me Eiffel is trying, along with Ada, to get to
> the aspects of type which relate to the dynamic execution
> of an algorithm (or something like that).

Eiffel is trying to enforce Design by Contract, which is a somewhat
formalized variation of the Liskov Substitution Principle.

> Language warts, they've all got 'em. What are ya gonna do?

Live with them until I find a better language :-)

>> Then I looked for ways of improving the postconditions. I found that
>> Eiffel was lacking anonymous functions; with these, postcondition
>> checking would have been simple.
>
> "anonymous functions" relate to types how?

Not to types but to assertion checking.

For example, the signature of 'equal' in STRING read something like this
(some technical details snipped):
   equal (other: like Current): BOOLEAN
   ensure
     sematics:
       Result =
         (length = other.length)
         and
           (length = 0
           or else item (1) = other.item (1)
                   and (substring (2)).equal (other.substring (2)))

Now look at this monster. It's (essentially) a recursive rewrite of the
definition of equality. However, for lack of higher-order functions, the
recursion is done by hand, and since each of the checks recursively
calls 'equal', running this with postcondition checking enabled gives us
at least quadratic behaviour. If 'substring' uses 'equal' in its
postconditions, it can get far worse.

In an FPL, you simply stick together a few HOFs and are done. That's
both more concise and easier to read.

>> Then I realized that such postconditions would be executable by
>> themselves... and I wondered: "why not move that postcondition into
>> the executable body of the function itself?" I realized that the
>> typical and oft-bemoaned Eiffel idiom
>> the_attribute: INTEGER
>> set_the_attribute (new_value: INTEGER) is do
>> the_attribute := new_value
>> ensure
>> attribute_set: the_attribute = new_value
>> end
>> with its semantically equivalent body and postcondition was not
>> limited to just simple setter and getter subroutines in a class, it
>> would apply to any function I'd care to fully specify in its
>> postcondition! And that in a language that had full subroutine
>> specification via pre/postconditions in its ideals...
>
> Does it feel right that you should be dealing with type issues
> via algorithmic means, rather than OO or static typing techniques?

Static typing and OO do nothing to ensure that an attribute setter
function "does the right thing". For example, the above postcondition is
quite silly, but it does have one advantage: if a subclass redefines the
attribute into a function, the 'set_the_attribute' procedure must made
the appropriate adjustments so the the 'attribute_set' postcondition is
fulfilled.

The bad thing about this kind of postcondition is that it should also
specify something along the lines of "all attributes *except*
'the_attribute' remain unchanged". (It *could* have been incorporated
into the language, but it's not technically simple... and then there's
the question whether those "all attributes" are those in the defining
class, those added in intermediate classes, or those in the redefining
subclass. Mutability is a mess, not just because it breaks referential
transparency but also because it's difficult to really nail the
semantics down and leave no stone unturned.)

>> Then came the problems with what FPLers call "open recursion", and
>> what OOers consider the core of OO: overriding and dynamic dispatch
>> (C++ people know this under the flag of "virtual functions"). It
>> turned out that STRING would have difficulties ensuring their
>> postconditions in subclasses, particularly those routines that called
>> other routines from STRING. We found we couldn't specify which kinds
>> of redefinition were OK in a STRING subclass and which weren't - at
>> least not in the form of postconditions, we had to resort to commentary.
>
> Can you give us an example of such a problem and where the
> language failed? I'm not familiar with Eiffel or FPLs, so
> this has me in the dark.

It's somewhat intricate, and I forgot too many details to reproduce the
problem with the required accuracy.

However, there's a similar problem for another class. Take a look at
this (slight variations from original syntax):

   abstract class ITERATOR
     initialize is abstract
     step is abstract
     finished: BOOLEAN is abstract
     clean_up is abstract
     iterate is
       do
         initialize
         while not finished do
            step
         end
         clean_up
       end

Subclasses are supposed to fill in implementations for 'initialize',
'step', 'finished', and 'clean_up', and maybe add some attributes so
that the loop has some state it can work on. Anybody creating an object
of such a subclass then has a precanned loop and need call only
'iterate', and subclass implementors need not think about loop syntax
(which is somewhat beastly and quite remote from the "while" I gave
above - that's why ITERATOR was written in the first place).

Now the interesting point:

what is the postcondition of 'iterate'?
Heck, there's a quite tight regime on 'iterate': it must call the
various functions in a rather rigid order. We *should* be able to nail
this semantics down so that subclasses that override 'iterate' will get
exceptions if they do it the wrong way.

There *are* ways to do this kind of stuff using just preconditions and
postconditions. The resulting code, however, it ugly and hard to understand.

... hmm, I think I remember now. It's nasty.

Assume this framework:

   class COMPARABLE is
     op "<" (other: like Current): BOOLEAN is abstract
     op "=" (other: like Current): BOOLEAN is abstract
     op ">" (other: like Current): BOOLEAN is
       do
         Result := not (Current < other or Current = other)
       end
   end

Now if somebody is doing a subclass, how do we make sure that he knows
that it's enough to override "<" and "="?
COMPARABLE is trivial. When classes get larger and have dozens of
routines, and implement interfaces that aren't so well-known as that of
COMPARABLE, the question of which routine to override can require a
quite intimate look at the source code of all ancestor classes.

Well, deriving directly from COMPARABLE is actually not a real problem.
After all, the compiler will emit error messages if we write a subclass
and don't provide implementations for all those 'abstract' routines.
However, the real COMPARABLE class looks a bit different, to provide
default implementations:

   class COMPARABLE is
     op "<" (other: like Current): BOOLEAN is
       do
         Result := not (Current > other or Current = other)
       end
     op "=" (other: like Current): BOOLEAN is
       do
         Result := standard_is_equal (other)
         -- 'standard_is_equal' is the ordinary field-by-field
         -- comparison that's predefined in the language.
       end
     op ">" (other: like Current): BOOLEAN is
       do
         Result := not (Current < other or Current = other)
       end
   end

Now it ain't so clear where to override, no?

>> In other words, deriving a class from an existing one turned from "THE
>> central way of reusing code" to "mostly useless, better served by
>> other means".
>
> Again, can you show us an example, at least in pseudo-code of
> the 'other means'?

Hmm... take a look at SML functors :-)

I.e. you need parametric types, where the parameters can be entire
modules, possibly even written ad-hoc in an in-line fashion.

>> It was a quite sobering experience, I can say!
>
> Sounds like a wonderful thing, but perhaps frustrating at the
> same time.

Indeed. It was one of the most interesting things I have done in my career.

> Seek the truth, for the truth shall set you free; even if it
> gives you a headache first.

Indeed :-)

>> Today, I think those languages that separated interface inheritance
>> (i.e. proper subtyping) from code reuse (in whatever form) made the
>> better choice.
>
> Hmmm.
>
> Does that mean you don't care for Smalltalk?

Technically, interface and implementation inheritance are strictly
decoupled since there is no such thing as interface inheritance in
Smalltalk. The type of a Smalltalk object is the set of messages it
responds to, plus the semantics that defines those responses; since that
type is not written down anywhere, most people think that Smalltalk is a
typeless language.
The type of a Smalltalk object is, hence, a subtype of all those message
sets that you care to recognize.

Actually I don't care about Smalltalk despite perfect decoupling of
interface and implementation inheritance. I'm a static typing guy, and
Smalltalk has run-time typing. (I also have some reservations about
efficiency, but these are minor.)

> Doesn't it always lead back to the basic question of how one is
> to express not only the type of a piece of data or of a group
> of things (class), but of the whole dynamic use of information
> within an algorithmic environment? I know that sounds kind of
> like wholistic mumbo-jumbo, but isn't that what we're seeking,
> a more perfect complete type system? Or, put another way, a good
> language which lets you do the work without having to worry about
> bad side effects or unreadable code?

>> In summary: DbC constrains OO subtypes so that they can be captured in
>> functional, nonpolymorphic code - why, then, have OO polymorphism in
>> the first place?
>
>
>>> Is there any implementation of "axiom checking" that you could point
>>> to?
>
>
>> Any functional language.
>> At least in a sense... I'm not yet deep enough into any of them to say
>> for sure :-)
>
> Which ones have you been checking into?
> Which ones impress most, so far?

Oooh, I'm going to make enemies with that ;-))

Smalltalk. (No static typing. No static whatever. Simply not my world: I
like to statically verify my code. Also has a rather long learning curve
- you get results quickly, but just being able to code in Smalltalk
(which I do) doesn't make you a Smalltalk programmer (which I am not).)

Haskell. (Nice. No module system though: type classes are just what I'm
looking for, but instantiating one seems to be a bit complicated. Also,
I'm quite uneasy with the performance predictability if lazy evaluation
is the default - I don't think that laziness is less efficient per se,
but I fear that it will be far more difficult to predict how fast a
given piece of code will run.)

SML. (Syntax isn't as nice as that of Haskell. Elaborate module
instantiation system. I'm still in the process of checking.)

Cecil. (Functional + OO. Very impressive work in the area of dynamic
dispatch. OO really integrated, not just tacked on as with O'Caml.
Unfortunately, just a research compiler, neither suited nor intended for
productive (read: commercial) work. Which is galling, since the language
is already good enough for that.)

Mozart/Oz. (No static typing, but some other very interesting
properties, though most are unrelated to typing. "Multi-paradigm" in
that it integrates all programming paradigms that I heard of, plus a few
that I didn't know before: linear, functional, imperative, OO,
constraint-based, all with and without concurrency where the distinction
matters - linear and functional code is semantically equivalent whether
running concurrently or not, so no need to differentiate at the language
level.)

Alice. (SML on the Mozart engine.)

Plus several papers - Kim Bruce, Luca Cardelli, and others.

>> Though I have to admit that FPLs aren't satisfactory in this respect.
>> There is no mainstream FPL that can verify axiomatic definitions (and
>> some of the idioms that were thought to be monads turned out to
>> disobey the monad laws, for example, so there's grounds for the
>> assumption that such axiomatic checking might be an advantage).
>>
>> I'd very much like to have such a language, but I don't think a viable
>> one is available at this time.
>
> What do you see as missing from the FPLs you've looked at?

See above :-)

Well, in most cases the problem is that the FPLs aren't fully geared up
for productive use. More nitty-gritty stuff like availability of Eclipse
plug-ins for the language, library repositories, and similar stuff. (I'm
trying to get things ahead for SML right now. We'll see whether that
helps or not.)

> In what ways do you see your current favorite FPLs as being
> superior to C, C++, Java, Smalltalk, S#, etc.?

I have no single favourite FPL right now. I'd like to have SML with
Haskell syntax and Mozart networking. Alice is SML with networking, and
I'll have to live with the syntax :-) (besides, the SML syntax isn't
*that* bad, Oz is worse and OCaml put me off.)

Those imperative languages?
C: Abomination. Chasing dangling pointers and buffer overflows, and do
everything on the lowest abstraction level.
C++: I'm constantly in a state of amazement about this language. It gets
a few things right that C got wrong (enum support, namespaces, templates
even if they aren't perfect), yet it manages to carry some of the worst
C warts (no GC, buffer overruns) and combine that with doing some
essential OO and non-OO things plain wrong (header files, implementation
stuff in the header files, by-default non-virtual functions,
constructors can't call virtual functions (horror!), no proper support
for diamond inheritance, exceptions during construction will cause a
memory leak unless you go to ridiculous lengths).
Java: nice but far too verbose, its multiple inheritance support is a
bad joke, and it didn't have generics. (Not sure how the current release
*with* generics works. I heard of type holes though...)
Smalltalk: No static typing, not my playground. YMMV.
S#: Don't know, I never heard of that.
Eiffel: Nice but horrible holes in the type system. It recently acquired
higher-order functions and closures, which multiplies the opportunities
for introducing type errors. Besides, it needs explict type annotations
on every entity, and writing a shorthand for a type means you have to
define an entire new class, which tends to bog one down in
administratrivia. Eiffel is a collection of extremes: extremely
ingenious features combined with extreme and fatal flaws.

Regards,
Jo

Relevant Pages

  • Re: SoA Vs OO
    ... Live with them until I find a better language :-) ... running this with postcondition checking enabled gives us ... but it does have one advantage: if a subclass redefines the ... > Does that mean you don't care for Smalltalk? ...
    (comp.object)
  • Re: Lisp or Smalltalk for Specific Suicide Mission (er...Project)?
    ... > Smalltalk is easier to learn and use, ... > There's nothing in the Lisp world (or in any other language, ... > I also wouldn't use Lisp for the web site part unless you have a very ... I would guess that if you're doing NLP ...
    (comp.lang.lisp)
  • OOs Place in History
    ... Under the topic of " How to interview a Smalltalk consultant?", ... The term "object" has one meaning in everyday language and a different ... A quantum, for example, an electron, does not have this characteristic. ... In the programming language and environment ToonTalk, ...
    (comp.lang.smalltalk)
  • Re: dynamic type checking - a pauline conversion?
    ... > Documentation being out of date isn't a dynamic language issue. ... > documentation is always a good thing in both static and dynamic languages. ... You want to say that Smalltalk doesn't exactly separate ... I will unequivocally agree that for advanced programming ...
    (comp.object)
  • Re: SoA Vs OO
    ... In an OO language, there would also be m methods ... > Typical FPLs don't even have inheritance, ... >> WindowWithScrollBar class. ... > Yet when the subclass declares a GdiHandle member, ...
    (comp.object)