Lambda the Ultimate

one of the problems mentioned in the blog post, that of provenance, is valid for any 'primitive' or 'common as dirt' type so the argument has been made about String too, even by regular non-ivory-tower folks :-) and A. Rossberg's last comment i think nicely tries to get at the crux of the nut there.

at least, any language that doesn't support something like Haskell's newtype is kind of a train wreck looking to keep on happening. :-(

I remember of a C coding guideline from a long time ago which said: don't use boolean, use enum: if latter you realize that in fact things are not always 'true' or 'false' and that you need a third value, it creates less refactoring(*).

*: adding value in enums still sucks in C due to its incredibly poor 'switch' statement but that's a different issue..

I may be mistaken, but the C coding guideline's reason for avoiding Booleans is different from Bob Harper's. He's saying that reducing something to a boolean often throws away information that you actually need later.

For example, here's an example of how Java's "instanceof" throws away useful information:

if (o instanceof Box) {
   Box b = (Box) o;
   ...
}

The "instanceof" expression reduces to a boolean, which means you still need to perform an unsafe cast in the body of the "if". C# does a bit better:

Box b = o as Box;
if (b != null) {
   ...
}

Ignoring for a moment the problem with "null" in general, C#'s "as" operator preserves the information you need.

Corrected link: here

Its a religious thing, I've also heard that OO is also responsible global warming.

There are plenty of problems that decompose better using OO than FP, and vice versa. I usually stop reading when they assert that OO is somehow a form of imperative programming, but it is rather orthogonal.

His exposition on dynamic versus static is better. At least there he employs humor and sarcasm. Now there's a tired battle... I get why you'd want to be fundamentalist when teaching freshman fp, but I'd say it's going a bit too far to declare OO as the anti-matter of the modular programming universe... Of course, there's nothing like a bit of controversy to attract readership. Funny how this is making the rounds on the web as "end of OO?". I can only guess that Bob's intention is not quite so dramatic(and wrong)...

C

I think it reasonable to say that OO is a form of imperative programming. I believe we should use names other than "OO" to describe models that aren't imperative. In its history, OO refers most often to a model of synchronous message passing. It would be quite convenient if we all agreed this was a defining characteristic of 'OO' that distinguishes it from FBP, Actors, multi-agent programming, reactive dataflow, et cetera.

I have designed plenty of declarative languages that are based on objects and inheritance, what other name do you suggest I use to describe my work? There are many out there that think inheritance and/or subtyping (nominal and structural) != OO, but I believe at least "implies OO" if not equals.

It isn't difficult to find something other than 'OO' to describe a new system. Just take two or three major elements of your paradigm, cut the cruft, then stick them together (e.g. Constraint Imperative, Concurrent Constraint, Communicating Sequential Process, Declarative Object, Reactive Object). Presto. Now you have a handle by which people can grasp, explain, tweet, and google your programming model.

Just take a few minutes to find something that hasn't been used before, preferably with an acronym that hasn't been used before (to avoid conflicts like 'Functional Reactive Programming' vs. 'Functional Relational Programming', or 'Concept Oriented Programming' vs. 'Context Oriented Programming').

You are hardly suffering from a dearth of creativity.

Let a hundred schools of programming flourish?

These labels put emphasis on the school and not the language. I would prefer to treat each language separately and enumerate its attributes (e.g., OO event imperative). I'm not trying to create a new paradigm, I'm just mashing paradigms up together, where the paradigms happen to be extracted from a bunch of other languages. Even the word paradigm is wrong, we should talk in terms of language aspects or features.

OO is a feature of a language that supports inheritance in any form including implementation, type, prototype. Prototype is a feature of an OO language whose inheritance occurs by cloning objects. Declarative is a vague feature that hides control flow details, logic is a more specific declarative feature where control flow is hidden via a proof engine, functional feature hides control flow via lambda reduction. Imperative exposes side effects and makes order relevant. And so on...

These labels put emphasis on the school and not the language.

You should label your language, too. ;)

I would prefer to treat each language separately and enumerate its attributes (e.g., OO event imperative). [...] OO is a feature of a language that supports inheritance

That is a reasonable position, but you would be clearer to use 'inheritance' rather than 'OO', since that is what you mean. (I believe most people understand 'OO' to mean a whole package of features. The problem is: there is no consensus on which package.)

There are programming models with inheritance that most would not call OO. Typeclasses can inherit other typeclasses. I've read about a rules-based programming system that involved prototyping (clone and tweak) of prior 'rulebooks'. Frame oriented programming probably should be included.

Declarative is a vague feature that hides control flow details

I found an operational definition for 'declarative' that I've been very satisfied with: a language is 'declarative' to the extent its expressions are commutative and idempotent.

The 'hiding' of control flow is implied: if control flow is obvious in the syntax, then expressions are not commutative.

the word paradigm is wrong, we should talk in terms of language aspects or features

Well, 'it depends'. Certainly, we could talk of a language in terms of its lower level features, just as we could talk of a vehicle in terms of chassis, windshield, engine, and seating. But paradigms are rather convenient ways to describe languages, just as 'car' or 'truck' or 'airplane' are convenient ways to describe vehicles. I rather favor Peter Van Roy's view on 'concept' and 'paradigm'.

Object-oriented is much more precise in terms of metaphors being used than inheritance, which is simply a mechanism. People are incredibly sensitive to the number of metaphors they can learn about, and creating a new one to describe every variation on object would be disastrous. We already have too many language labels that seem like buzz/hype/jargon. Using object-oriented to describe a language that is oriented around objects is not a stretch by any means, while if you introduce a term like frame you can only communicate that with a few people.

If you're arguing that 'inheritance' is even more hand-wavy than 'OO', then you really should be looking for some new terms.

Communication requires that the other person understands what you're saying. Using "object oriented" tells your audience to assume Java or C# or whatever 'OO' language they're familiar with, and tweak the concept from there (based on the other things you've said). As a local example, you can glance below to see what neelk assumes to be part of the 'OO' package, and though you or I may disagree, the point remains that we already have assumptions about 'OO'.

If what you mean by 'object' is significantly different than other people assume, you're just sewing confusion. Using 'OO' to avoid confusion is almost certainly a mistake, no matter how good your intentions. Worse: if they disagree that your objects are what they understand to be 'objects', you may even alienate your audience. For example, I'm quite willing to debate your notion that inheritance implies OO, though I am resisting. Too many discussions devolve into debates over definitions.

If you introduce a term like 'frame', you'll have the advantage that there are fewer initial assumptions and connotations about what it means. People will be confused, but in a good, honest way: they're confused because they aren't assuming they know what you're talking about well enough to skip clarification.

So terminology is incredibly audience sensitive, I can agree with that. But I disagree that this is about precision, rather its about cultural nuance.

If I'm talking to a roomful of object people (say at OOPSLA or perhaps ECOOP), then they will be believe what I'm talking about relates to objects, even if it doesn't look like the objects they are used to themselves. Actually, they are used to objects that don't look like their objects, there is no resistance there. If I'm talking to an ICFP or POPL audience, I have to be more careful b/c, not being object people, they have rigid preconceived notions of what objects are.

I think you could get away with it there because they've already accepted 'object' to be pretty much utterly devoid of meaning, what with every paper having a different definition, so they focus on your other statements.

Stretching definitions mostly serves to weaken them. The term 'definite' means 'bounded with precision', and that's what a definition should be. Could you define 'object'? Or is it just a hand-wavy notion that means whatever you want it to mean?

Object people have a strong sense about what objects are, there are criteria to calling something an object that have to do with object thinking. You can't call a lambda an object, even if it manifests in C# as an object instance. On the other hand, you could call anything that allows to divided the world into a set of inter-related nouns an object.

Can you define 'object'?

Just to let you know: I could easily divide the world into inter-related nouns with logic programming or relational model.

I don't believe logic and relations are far off from objects. To "be" something is definitely a predicate, while a table describes an object and its relationships. However, you don't normally program with objects in a logic programming language even though you could, while relational has long been known to be very related to object.

This debate about what an object is very old. Objects are really just a part of object thinking, which itself means thinking about your problems being solved by a bunch of cooperating related objects. The objects then have identities and existences, we could think of them as little people running around to get things done. This is obviously very different from function thinking.

1) Milkshakes don't bring boys to your yard.

2) You don't have lovely lady humps.

3) whatever...I am being silly.

My point is that what people most often refer to something as is not nearly as important as internalizing a concept and then attaching a symbol to that concept.

What is important depends on your goal: to understand a concept, or to communicate it. In the latter case, it is important to understand whether a symbol already has meaning to most people, and it is important to use that symbol for the broadly accepted meaning.

Anyhow, I don't believe this is a case of 'pop culture'. Go back and look at the main language designs by which people understand 'OO': Smalltalk, Simula, CLOS, Objective C, C++, C#, Java. Even OOHaskell is heavily imperative (using IORefs as the basis of identity). When I crack open my book 'A Theory of Objects' by Martin Abadi and Luca Cardelli, guess what I find? imperative extensions from lambda-calculus. When Benjamin Pierce extends lambda-calculus to support OO in TaPL, I'm sure you can guess what he adds... 'Imperative' is very widely accepted to be part of the concept of OO, and that property is what is embedded in our educational materials on the subject, in history, in research. This is not 'pop culture'.

The first object-oriented language, Simula, didn't have `message passing' and it already captured the essential aspects of O-O -- later languages didn't change things all that much. IIRC, SmallTalk introduced the notion of synchronous message passing (and while you can call procedure calls `sync. msg passing', it seems an overkill. IMHO).

But I agree with your main point.

Procedure calls aren't synchronous message-passing... unless you have first-class procedures. The main distinction is that, with message passing, the recipient is not statically coupled to the sender.

I think defining OO in such a way that imperative programming is characteristic is a mistake. True, much OOP is done in the imperative model, but there are many research languages developed under the OO banner that emphasize good support for functional programming (Cecil, my advisor's language, is one; so is Scala). Prominent OO designers like Josh Bloch recommend developers avoid state whenever possible, and many approaches to OO and concurrency emphasize purely functional objects.

So what IS characteristic of OO? As discussed in a prior thread, William Cook argues the defining characteristic of OO is procedural data abstraction (i.e. dynamic dispatch): each object (conceptually) carries with it the procedures necessary to use it; different objects with the same interface can be implemented differently. Of course Cook's essay was just summarizing and repackaging the best understanding of an often misunderstood topic; his definition matches the main formal models of OO (and incidentally, most of those formal models are functional).

There are many other features of OO that often come along for the ride, such as mutable state and inheritance. But, building dynamic dispatch into the language (as opposed to coding it up with a bunch of lambdas, which is of course is possible and is done where necessary in functional languages) is the one thing that separates languages commonly considered "OO" from those that are not.

Arguably, dynamic dispatch is also what distinguishes OO in terms of engineering. For example, if you look at object-oriented design patterns, nearly all of them involve interfaces and dispatch; relatively few require inheritance or state.

Even when favoring use of 'pure' objects, you're ultimately relying upon the side-effects from method-calls, which also introduces the issue of time (before the effect, after the effect). That is, objects will still represent/proxy elements in the 'environment' even if your application contains nothing except pure objects.

Every model I've ever read for OO (including Pierce's, Cardelli's, OOHaskell, etc.) introduces state and side-effects. I am curious what your experience is that you call these models 'functional'.

Dynamic dispatch doesn't really distinguish objects. You can get that with pure, first-class functions. What distinguishes objects is behavior hiding and side-effects. Most design-patterns are for managing this hidden behavior... or executing it.

If objects are used to model I/O, then yes, you will rely on side-effects from method calls. That does not mean that objects are fundamentally imperative, any more than functions are imperative just because they are sometimes used to model I/O (or other stateful abstractions). The point is: many object-oriented programs have a substantial number of objects that are pure; objects can be used either to model state, or not--just like procedures or functions. Therefore I argue state is not characteristic.

Regarding OO models, the simplest ones are all purely functional. That includes Pierce (FJ and the other simple models in TAPL), the simpler Abadi/Cardelli models, and Fisher/Mitchell's models. Most of these models were extended with state later. But my opinion is that the simpler models do capture the essence of objects--the state extensions are mostly uninteresting once you understand the object model--and I guess that the reason they were presented first, is that their developers also thought this characteristic of objects was the most important to model.

More broadly, Sean is not the only OO researcher who have studied or developed purely functional object-oriented languages; there are many of us. While there might still be some debate about the exact definition of OO in this group, I can promise you many of them would strongly object to limiting objects to imperative models.

Of course first-class functions can be used to implement dynamic dispatch, but it is still possible to characterize objects that way. An object is what you get when you package together a group of functions to abstract a piece of data or a function. This definition admittedly includes an element of intent (the "to abstract..." part) but that intent is usually easy to determine from context. From a programming language point of view, just look for a convenient syntax for a record of functions and you've basically identified OO languages.

Regarding design patterns, look at the list from GoF. Most have nothing to do with state, including factories, adapter, bridge, composite, decorator, facade, chain of responsibility, strategy, template method, and visitor. All these are useful with functional objects. Flyweight (hash-consing) is in fact fundamentally about functional programming!

Some patterns are clearly stateful: observer, state, memento, interpreter, and probably mediator. But the patterns that depend on state or are only useful in a stateful system are clearly a minority.

I'm not going to argue that most OO programs aren't stateful; clearly they are. But that doesn't mean OO has to be imperative, definitionally.

If objects are used to model I/O, then yes, you will rely on side-effects from method calls. That does not mean that objects are fundamentally imperative, any more than functions are imperative just because they are sometimes used to model I/O (or other stateful abstractions).

There is a huge difference between explicitly 'modeling' side-effects (as with a monad) and implicitly executing them as part of evaluation, just as there is a huge difference between thinking about a war and causing one. Functions are imperative (and better called 'procedures') if they are used to implicitly execute IO as in ML, Lisp, etc.

The point is: many object-oriented programs have a substantial number of objects that are pure

My point is: it only takes ONE that isn't, no matter how many layers of 'pure' indirection. And, in fact, most object-oriented programs and patterns (including those you named) rely on the fact that there are some objects that are not pure. It doesn't matter whether they internalize state, only that they interact with state in an imperative manner. Even observing a sensor or manipulating an actuator can qualify as 'stateful'.

A language is imperative if its evaluation steps through time - i.e. if there is a logical 'before' and 'after' each step, and order matters. There are non-imperative approaches to expressing side-effects, but they aren't embraced in any OO language I know about. And, rather than polluting the concept space, I would rather keep it that way - anyone attempting non-imperative objects should use a name other than 'OO'.

I can promise you many of them would strongly object to limiting objects to imperative models.

OO languages are de facto imperative. A few whining academics won't make a difference.

Why do they try? Are they trying to ride old buzzwords for funding? To publish at OO conferences? Seriously, the many little agendas to use 'OO' for EVERYTHING stretch its definition to the point of uselessness. Nobody agrees on the definition because there isn't one - no clear limits on the concept. I could play frisbee with a dog and call it OO. I think we should say 'enough!' and draw some lines so we can make sane distinctions, even if that's going to piss a few people off.

Ah, you are using the term imperative in the strong sense (having any imperative features) rather than in the sense of "emphasizing imperative programming more than functional programming." Sorry, I misunderstood.

I would still argue this is orthogonal to the important aspects of OO, though you are right that at least all industrially relevant OO languages are imperative in this sense. I don't want to toot my own horn too aggressively, but I'm currently developing a language, Plaid, in which all effects are explicitly described in permissions (somewhat similar to Haskell's monads, but permitting a few more convenient forms of composition) and thus there is no "before" or "after" other than what is defined by permission flow. Plaid is object-oriented in every sense that I think is meaningful, but the way it handles state would, I think, lead you to call it non-imperative. Do you really think that is disqualifying? To me object-oriented is still a reasonable term for a language that has objects, methods, an inheritance-like composition mechanism, and state that happens to be handled in a way somewhat similar to monads.

And yes, there is a definition of OO: Cook's. Based on conversations at OO conferences, I think most OO researchers (the experts in the relevant field) more or less agree with it; it also seems to categorize most languages (including Plaid) in the intuitive way, and it matches the emphasis of OO formal models. To me, therefore, that definition makes a lot of sense, and there is no need to bring imperative programming into it.

But at this point we should perhaps just agree to disagree. It looks like some aspects of this conversation have come up before, with Tim Sweeney suggesting a definition similar to Cook's.

Put four 'OO' language designers in a room and they'll give you four different, vehement, arguments about what it means to be 'OO'. I just want to have one definition so that I know what people mean when they say 'OO'. I don't really care that it be imperative, but that is one of the only properties that is common across every 'OO' model I've seen. (Even your 'dispatch' doesn't hold up to scrutiny of multi-methods, predicate or rules-based dispatch, and other esoteric forms I've seen.)

I've not read much of Cook's work, but in the 2009 paper his very first example for objects in that paper is imperative set operations:

a = Insert(Empty, 1)
b = Insert(a, 3)
print a(3) -- results in true

Oh, and here's his definition for 'object' in OO (section 3.10):

An object is a value exporting a procedural interface to data or behavior. Objects use procedural abstraction for information hiding, not type abstraction.

If we want to go with Cook's definition, then fine, but resist cherry picking the bits you like best so you can shoehorn your language into 'OO' as though the label had intrinsic value. If everyone did that, why, we'd be right where we are today.

I'm not cherry picking from Cook's paper; the example is purely functional if you read the surrounding context, which includes the definition of Insert (copied below) and states "Inserting n into a set s creates a function that tests for equality with n or membership in the functional set s." It looks like instead you found a typo; I guess either print a(3) should be false, or print b(3) was meant.

Insert(s, n) = \i. (i = n or s(i))

Some may prefer slightly different definitions, but I think something like Cook's definition is the closest you'll get to a consensus.

After reviewing the paper again, I grant it's likely a typo.

I think something like Cook's definition is the closest you'll get to a consensus.

Maybe, though the Nygaard classification and Kay's definitions for OO also have a lot of followers, and Cook's definition would receive a lot of objections from the 'OO can support multi-methods' or 'OO means inheritance' camps.

One aspect I find missing in most discussions of OO is the wide variety of programming styles that are possible in most of the current object-oriented programming languages. As a quick perusal of the daily WTF can demonstrate, there is a lot of bad code out there. And given its status as the dominant paradigm, there is a lot of bad OO code out there. But another consequence of keeping this dominant status for so long is that we (as an industry) have learned some lessons about what works and what doesn't. Minimize mutability, avoid class inheritance, avoid ambient authority (usually stated as "apply dependency injection"), stratify your dependencies (the "law of demeter"), specify behaviour via unit tests, etc., are common slogans among the thinking object-oriented programmers.

I believe it would do good for programming language researchers to spend some time investigating the state of the art in modern OO development. I can do no better than recommend Nat Pryce and Steve Freeman's book, Growing Object Oriented Software Guided by Tests, as a thorough demonstration of the best in modern OO programming.

That is not to say, at all, that object-orientation is superior to other models of computer programming. I personally agree with Harper that functional programming should be the first style students encounter.

You also left off Persistence Ignorance, and real-time structured design/object-oriented engineering patterns like Processor-Actuator, Watchdog, and so on that provide heuristics that substitute for first-class control theory in languages.

I personally agree with Harper that functional programming should be the first style students encounter.

The emphasis has to be on how new thoughts are learned. If the idea isn't embedded deep enough, then students will misunderstand it and you will get a cargo cult culture. We shouldn't really focus on what's first, so much as sequencing and identifying "threshold concepts". Debating what CS1 should look like ad nauseum is the domain of empire builders and foot draggers, and we shouldn't have the patience for listening to either group drone on.

The trouble with OO is that it has a set of features that conspire to defeat nearly any kind of equational reasoning: OO features open recursion, the pervasive use of higher-order values, and reflection.

1) Open recursion (aka inheritance) means that you cannot define a type as closed collection of values, which means that you cannot reason inductively about programs. (The validity of induction as a principle of reasoning relies on a closed-world assumption.)

2) When you can't do induction, the usual move is try reasoning coinductively. However, in practice you can't do this for OO programs. The reason is that objects are intrinsically higher-order, since the signature of an object is the signature of its methods, and methods take objects as arguments. As a result, an object's signature will often feature contravariant occurrences of the same object type. Consequently, predicates lifted