Lambda the Ultimate

thanks... didn't copy and paste the title.

He names the textbooks in the second paragraph of the paper.

I also noticed he didn't cite Pierce [edit: as an offender], but I could not find my copy of Pierce's book in my mountain of books to look at what he said. Thanks. [edit: He does make a reference to Pierce on page 5, in praise.]

Whoops, I skipped the second paragraph. ;-)

But even the examples he gives in the second paragraph are not convincing (at least as quoted). The issue is that the term "abstract data type" is often overloaded. It is often used in the broader sense of "abstract type", and indeed Java classes are abstract types, so I don't think they're necessarily wrong (although I'm basing this judgment just on the quotes he gives).

Cook's notion of ADT is a different, more traditional one (an abstract type together with a set of operations on values of that type), which is indeed very different from objects or classes.

(an abstract type together with a set of operations on values of that type), which is indeed very different from objects or classes.

In a language like Common Lisp, where there's no syntactic difference between function calls and method calls (via generic functions), aren't ADTs a special case of classes?

This example class is an abstract type with a set of operations:

(defclass my-adt () ())
(defun make-adt () (make-instance 'my-adt))
(defmethod do-the-adt ((adt my-adt)) (print "an ADT!"))

(do-the-adt (make-adt))

(You lose a bit of abstraction, because you can peek into objects, but I think that's more a matter of programmer discipline than a genuine difference.)

You lose a bit of abstraction, because you can peek into objects, but I think that's more a matter of programmer discipline than a genuine difference.

Well, enforcing this kind of abstraction is the whole point of data abstraction as a language feature. Otherwise you could say that even assembly language provides for ADTs.

Provided you trust the other programmers, and they don't peek into objects, are there any benefits to ADTs over objects and generic functions?

(Edit: by generic functions I mean the same concept as multimethods.)

(Update: I just realized that this question is probably much too broad, so feel free to ignore it ;-)

I don't even trust myself when it comes to programming non-trivial systems. ;-)

Apart from that I would say that generic functions are mostly orthogonal to ADTs, so I don't really know what to answer.

You are making a syntactic argument about methods versus function and its not really the key issue. The question is whether an operation has access to only one representation or multiple representations.

The important is that you have raised the question of how multimethods fit into the picture. I avoided this question because I'm not sure I have a perfect answer. Multimethods can provide capabilities of both objects and ADTs. They don't provide the same degree of encapsulation as pure ADTs. Exactly how mutlimethods fit into the picture is something I don't know right now.

Would a module system solve the encapsulation problem? You only expose the methods that you want people to be able to call.

Interesting that he does not mention CTM, as he himself seems to have had some influence on its presentation of OOP. Previously on LtU, although I don't think PvR was a member at that time.

Anyway, I do think this is very important material, and I don't think it's widely understood in industry, although I would have thought that it was widely understood by now among PL researchers. I can't comment on the state of current textbooks.

I think this is pretty out of touch:

One other way to break encapsulation in Java is through the use of reflection, although this is not common when writing most programs. Reflection is useful when writing meta-tools (e.g. debuggers) and program generators. However, use of reflection appears to be growing more widespread.

I defy you to find even one significant contemporary Java program that does not use reflection extensively (whether directly or via libraries/frameworks). To say that it is "growing more widespread" is to be about ten years too late, IMHO.

To say that it is "growing more widespread" is to be about ten years too late, IMHO.

It depends on your viewpoint. Annotations are one form of reflection, and code that writes code is another form of reflection. Annotations are being used in more places today than debuggers and program generators. They are used to tag code with additional notes for static analysis (see Bill Pugh's JSR for Null input and output guarantees), or to notify an environment that an object has a specific role in a program's control flow and scope, etc. Some of these uses, while known in theory to be practical use cases for reflection, are discouraged in practice, due to high overhead of run-time reflection API calls on the JVM or CLR.

Also, David Barbour recently asked me about the performance of reflection in distributed systems, and I've been working on an answer for him. This is a very different beast from those use cases.

More precisely, use of reflection via annotation is largely confined to startup in most practical uses cases, rather than throughout an applications main loop. The most popular dependency-injection and persistence frameworks for Java (Spring and Hibernate) now strongly encourage use of annotations for program configuration. (Previously, these frameworks used reflection via magic names in XML files.) The trick is that all of the reflective overhead occurs at program startup. It would indeed be very rare to find an enterprise application written in the last five years that doesn't use reflection at some point.

To be precise as well...

Annotations that augment control flow and scope at runtime, such as JBoss Seam Bijection "subversion of control" annotations, are the runtime "ongoing peformance hits". Seam does allow you to avoid paying this penalty at run-time, but you lose expressive power. If not used too frequently, the performance loss won't be noticeable except the most performance-demanding situations (think Black Friday online shopping), because most time will be made-up for by Seam's 2nd-tier caching support.

The trick is that all of the reflective overhead occurs at program startup.

Change program startup with load time. In a pluggable architecture, which is any enterprise application, components will be added on the fly. Think OSGi hotswapping. Cost is amortized, and also, with reflection, you can't possibly resolve all dependencies a large application will ever need .

Yes, I did exchange many detailed comments on Concepts, Techniques, and Models before it was published. The authors were very receptive to my suggestions, and I like the way they interpreted the material in the context of Oz. I love the book and recommend it without reservation, including the parts about objects and ADTs. I didn't think of it as an undergraduate PL textbook, because it is so focused on the Oz language. But I know it is sometimes used as a PL textbook.

As for my comments on reflection, I suppose that might be a case of academic understatement. I think many Java programs are written without reflection, but its clear that most large successful libraries/systems use reflection in one way or another. I take this both as a sign of the flexibility of Java and also a clue about what we need next.

I didn't think of it as an undergraduate PL textbook, because it is so focused on the Oz language. But I know it is sometimes used as a PL textbook.

To be honest, it is just as important that CS undergraduates read an Introduction to Programming textbook that uses terminology correctly.

In college, my friend and I did a curriculum assessment of our CS program, and one of the things we dropped from the assessment was complaints about reading material, as it really fit under curriculum evaluation (judging individual professors' abilities to pick the right reading material for their subject domain). The weird thing about this is that the books for low-level courses are often picked out by the faculty as a whole, since there are usually many sections. Yet, politically, it is tough to say in an assessment, "these books damage brains."

Bottom line: There are a lot more Introduction to Programming textbooks than there are Programming Languages textbooks, and many start with the wrong explanations of things, making upper-level courses partly an exercise in unlearning broken definitions. Usually the ensuing code that illustrates these broken definitions also stinks.

The way I interpreted his statements was that an object is precisely as observable as you choose to make it.

For example, if an "integer set" object had a method or methods that allowed you to enumerate its members (preferably in order), you're able to make an "observable equality" check between two such integer set objects.

Depending on how far you mean to carry the term "pure", a lot of practical programs can be written that way (as he mentions with respect to Smalltalk).

The way I interpreted his statements was that an object is precisely as observable as you choose to make it.

Isn't this characteristic of an ADT as well?

Agreed--I was responding to the parent post's claim that objects are not observable.

Colin, your argument about 'integer set' objects starts by assuming that there are special language constructs called 'integers' that support primitive intrinsic identity comparisons. You then use this to argue that some language constructs can support identity comparisons.

In a 'pure' OOP system, integers could be represented (as Church numbers, if nothing else), but one could never determine from within the system whether an object is a 'true' integer object vs. an impostor object being used in place of an integer that will act outside expectations based on circumstances. A very simple impostor would be an integer-variable object that references another integer object - which may be another impostor. One could not compare sets for true identity given those circumstances.

I agree, and had not fully thought out how "far" one had to go to be "pure". In such a context, testing for equality would be testing for bisimulation (as mentioned in the paper), which should drive me off to do more reading about things I'm unfamiliar with.

Thanks for helping me think about this more clearly.

Heh, my claim certainly is terribly vague and insufficiently precise, and I'm not that well versed in Object Oriented thought. :-)

You can certainly make an object more observable by exposing (parts of) it's internal representation, by exposing some way of iterating over the elements of a set, for example. But in the process you also constrain the possible representations or even possible objects themselves. To take the example from the paper, you certainly cannot iterate over arbitrary infinite (computable) sets.

So I guess what I meant by "pure OO" is the interface that allows the maximal freedom of representation. Whether or not this is an appropriate definition, I don't know.

Not that anybody should care, but the project I referred to was an automata library similar in overall design to HaLeX, although mine appeared about a year earlier and didn't have the graphical capabilities. You can read the paper here and download the code here, although it's rather bit-rotten.

The idea is pretty simple, really. Instead of a more traditional programmer's representation of a finite automaton, represent an automaton using the traditional definition from a math textbook: namely a start state, transition function, and characteristic function for the set of final states.

data DFA st ab = DFA st (st -> ab -> st) (st -> Bool) 

trues_div3 :: DFA Int Bool
trues_div3 =  DFA 0 delta (==0)
  where
    delta st True  = (st + 1) `mod` 3
    delta st False =  st

In fact, assuming that such an automaton is finite and that the type of st is appropriate, it's possible to do anything and everything you could do with a traditional table-based representation, such as compare two automata for equality. This idea seems somewhat obvious, but HaLeX is the only other paper/bit of software that I know of that takes this approach.

However, my more "pure OO" representation that I later discovered was

data DFA' ab = DFA' (ab -> DFA' ab) Bool

trues_div3' :: DFA' Bool
trues_div3' = state 0 
  where
    state n = DFA' (\x -> if x 
                            then state ((n+1) `mod` 3)
                            else state n) 
                   (n == 0)

And alas, you can't really do much with this representation other than run it, and compute certain very simple constructions such as intersection:

isect :: DFA' ab -> DFA' ab -> DFA' ab
isect (DFA' dx fx) (DFA' dy fy) = DFA' (\ab -> isect (dx ab) (dy ab)) (fx && fy)

You certainly cannot compare two automata for equality in this revised representation.

Yes, you need some concept of identity in order to check equality using bisimulation or other technique. I think it is bad to use a primitive notion of identity, but instead add an observation to your states that maps them onto some more basic type that can be compared for identity. In this case the tag could be String or Int.

data OODFA id ab = OODFA id (ab -> OODFA id ab) Bool


... but I don't like that both the type of id can lie (by having an erroneous instance of Ord for example) and the id values can lie (by failing to preserve a 1-1 property inside a given automaton).

By comparison, in the "textbook" representation only the type of st can lie. The values themselves are more reliable. (Although I suppose you could use a quotient type for the type of st, and then choose a transition function that isn't well-defined with respect to the equivalence relation.)

Due to the ability to represent infinite automata, both representations allow for arbitrary Turing-computable functions, as you could build up a state that remembers the entire string and then accept or reject that state based on some arbitrary computation over the entire string. So neither representation is really adequate anyway, which a traditional table-based approach comes closer to achieving.

I wonder what the upsides to the OODFA representation with identity are, if any.

What is LtU-folk?

I read quite a few FP mailing lists, and I often see confusion on PLT basics such as why currying is useful. I even see Ph.D.s on these mailing lists give lame answers compared to Richard Bird's (who would also not only tell you why currying is useful, but when it might make something needlessly complicated and when it is effectively essential). I even see basic confusion on the Haskell wiki at times, or on Planet Haskell; people will use category theory terms incorrectly, and it will confuse me because I have to decode what they are saying.

The analogy I think of here is with the business world. Lots of Fortune 500 execs subscribe to Harvard Business Review, even though this report is filled with "brushing your teeth and eating your veggies promotes good hygeine"-style research, because, well, it's true, and no matter how many times they learn something, people forget, forget, forget.

Apart from that, I thought this paper fit the flow of main page discussion -- which is the real reason I decided to make a story out of it.

I didn't take the claim about LtU-folk to imply that the item was not a good choice for the home page, merely as an observation why the author should be given some slack...

I wasn't criticizing your post. I was just pointing out that the article seems to be targeted at people who are not aware of one of the most fundamental differences between OO and FP---a difference that, to some extent at least, is prominently explained in Pierce's book, which I would view as a very standard textbook for "LtU folk". So I suspect the target audience does not have a large intersection with LtU readers, but I could be totally mistaken.

You'd be surprised how many PL researchers either haven't read Pierce or have skipped over the OO chapters. My other complaint is that studying operational semantics of OO, like Featherweight Java and Cardelli's book, does not provide very much intuition about what OO really is.

I think I see the confusion you're referring to.

Based on a quick glance, I would say that Gibbons' notion of ADT is not the same as either CLU ADTs or objects or OO-style interfaces. Viewed through the lens of ML (my favorite lens), his notion is really "the signature of a first-class ML module (coded as an existential)". In contrast, a CLU ADT is analogous to "a (restricted form of) ML module". Gibbons' notion is superficially similar in certain ways to an OO-style interface, but really different. In an OO interface you can only talk (recursively) about the type of all objects that satisfy the interface you're defining, whereas in Gibbons' ADT, the method types talk about a particular implementation type.

One could express the confusion as it regards Mitchell and Plotkin's slogan "abstract types have existential type". The word have is critical. CLU ADTs are essentially modules that have (i.e. are classified by) an existential type, whereas Gibbons's "ADTs" are the existential types themselves.

I'm glad to see this important point highlighted at the end of Cook's article:

To me it is unfortunate that Liskov also wrote that "CLU is an object-oriented language in the sense that it focuses attention on the properties of data objects and encourages programs to be developed by considering abstract properties of data." I believe that there is no technically or historically meaningful sense in which CLU is an object-oriented language. I do believe that modern object-oriented languages have been influenced by CLU (especially in the encapsulation of representation) but this does not make CLU into an object-oriented language.

Again, though, I suspect this point is much more controversial in OO circles than in FP ones.

Oleg, I'm confused. Which paper of ours are you referring to? Our ICFP'09 paper with Georg Neis? If so, I should say that proving representation independence for ordinary existential-based ADTs was not a contribution of our paper...that's due to Reynolds and, later, Mitchell. Our contribution was merely to prove it in the setting of a language with non-parametric features. But maybe I misunderstand you.

Regarding existentials, I did not mean to imply that existentials are the only way of formalizing ADTs, merely that the notion of "abstract data type" that Cook is using is the traditional CLU-style one, and CLU ADTs conform pretty closely to terms of existential type. Indeed, existentials have limitations, and in my work on recursive and mixin modules, I was forced to abandon them in favor of a more flexible mechanism (RTG).

The link is again to the paper. Should it be this talk?

That looks like a link to the paper.

I think you meant to link to this pdf?

smarter programmers are a more important outcome of PL studies than smarter languages.

That's a very good point. I thought that this is one of the the main rationales for teaching PLT.

John has also repeatedly emphasized to me the importance of the fact that objects permit information hiding, as distinct from data abstraction. For example, a hash table offers a programmer access to an abstract state, whereas in constrast a memoized function uses hidden state.

I understand what you're getting at, but I'm not sure this distinction is really that clear. Both cases involve hiding information, the difference is in what kind of information you are hiding.

The best description I can come up with is the old static/dynamic distinction: one approach hides some of the information that was known before runtime (implementation), the other hides some of the information that was known only after runtime (data state).

Unfortunately, this distinction is vulnerable to the usual static/dynamic quibbles: what to do about models of software execution where the idea of before and after runtime is less distinct, i.e. those using heavy metaprogramming with less conceptual difference between implementation state and data state.

It is harder to convince someone who says "We don't need no stinking implementation invariants!" that there is a meaningful difference between the different forms of data abstraction.

the OOP approach forces youu to write more flexible code everywhere, but I'd spin this as the OOP approach being less flexible about what you can write.

As a library writer, I have to ask, who is the you that you are referring to?

David Barbour mentioned impostor types earlier. However, that's a pessimistic example. A much better example that explains the 'WHY' of OO and also deals directly with your criticism is the GoF Composite Pattern. In the earlier days of OO, OOP was sold as the best theoretical technique for building GUIs. The magic behind OO's "right tool for the right job" as it applies to GUIs is precisely the Composite pattern. More often than not, the degree to which a GUI toolkit is successful is the degree to which it enforces an object-oriented Composite structure. Even better if it enforces it in a sane way.

The major selling point is that client callers do not know how complex the internal structure of a composite is. This allows clients to talk to the composite with simple interfaces. This is the best "system building" example of what Cook calls the autognosis principle in the paper.

As a library writer, I have to ask, who is the you that you are referring to?

That quote referred to 'you' the language user - either as a library writer or a library user.

The major selling point is that client callers do not know how complex the internal structure of a composite is.

If you're designing a panel that can house arbitrary heterogeneous elements, then by all means, use an existential type with a simple interface. You can do the composite pattern without OOP.

David Barbour mentioned impostor types earlier. However, that's a pessimistic example.

That 'pessimistic example' was to prove a point in context, and would better be taken as pessimism against 'pure OO' rather than against 'OO'. We thrive on useful distinctions. "Everything is a" is neither useful, nor a distinction. I favor languages, such as Erlang, that provide both Algebraic Data Types and Objects (or Processes, as the case may be).

The magic behind OO's "right tool for the right job" as it applies to GUIs is precisely the Composite pattern.

With this, both my hobby horse and I must disagree.

The OO composite pattern is a poor tool for GUIs. Good GUIs have a great deal of pressure to violate the composite pattern and treat the collection of elements as just that - a collection of fine-grained elements. The reasons are manifold: high-performance occlusion and zoom-ability, collision-detection (at least for mouse inputs), subscriptions with minimal invalidations, exposing precise and fine-grained capabilities to achieve capability-UI principles, ability to transform and compose (select, join, map, union, etc.) UIs for mashups, portals, style, accessibility.

One 'right' tool for this job is functional (or logic) reactive programming, which can maintain (in soft real-time) both the scene-graph and the procedures executed upon user-input. OO still serves a role in defining and exposing initial user-input capabilities (which might be combined procedurally) and in supplying bound data sources to which the scene-graph functionally reacts. Functional reactive offers flexible and reusable composition, great potential for partial-evaluation, internal caching with minimal re-evaluation and low-latency reaction to invalidation (better than polling), safe parallelization, superior multi-cast, distribution, disruption tolerance and real-time properties, reduced energy consumption properties compared to polling largely static content, and high potential to reduce temporal coupling (the dependence of a service's quality upon the time it was requested).

We too often implement the observer pattern and visitor-pattern ('folds') over OO composites, and the results are often monolithic, a challenge to compose, difficult to modularize, unsafe under concurrency, and require either too much explicit caching or too many periodic recomputes (pick one!). Use of composite pattern for UI is essentially requiring another use of visitor pattern, this time drawing to a 'viewport' or 'screen' object.

Any OOP language would do well to provide 'pure'-functional and functional-reactive layers as messaging and plumbing elements respectively. A language consisting of 'pure' OO strikes me as painful.

The OO composite pattern is a poor tool for GUIs.

I don't think the composite pattern is limited to its OO implementation. Having GUI elements that assemble some arbitrary Widgets into a bigger Widget seems like a pretty fundamental idea that can be integrated successfully with functional reactive programming.

I don't think the composite pattern is limited to its OO implementation.

Yes, it is true. The Composite pattern's formal definition was given by Ondrej Rypacek in Objects Versus Abstract Data Types:
Bialgebraically.

Having GUI elements that assemble some arbitrary Widgets into a bigger Widget seems like a pretty fundamental idea that can be integrated successfully with functional reactive programming.

I think you and David both misunderstood my point here, and I am trying to think of how to better express it. Suffice to say, you and him haven't said anything obviously wrong to me.

Let me rebuttal this way: Composite pattern is not a good way to link two things that may in fact be two entirely different parts of a problem domain. David appears to be grinding an axe against programmers who do this. I would never do this, as it creates unnecessary domain coupling and limits visualization effects, such as foreground-to-background and background-to-foreground layer effects. I attribute this problem to the Panel layout synthesis paradigm, which hides from the programmer the constraints that link Panels and their children to each other and thus provide the physical screen real estate each object is given to draw itself. David makes a good point about explicit caching, which is to say that an object needs to provide a explicit hook to the environment to describe when the rendering engine needs to reconsider it. In functional reactive programming, cause and effect is inverted by description, so that this hook is implicit.

Composite pattern is not a good way to link two things that may in fact be two entirely different parts of a problem domain. David appears to be grinding an axe against programmers who do this.

It is often very difficult to distinguish 'parts of a problem domain'. The divisions that seem natural depend far too much upon which perspective we're taking, which 'hat' we're wearing, and that may easily vary from one moment to another. From any given viewpoint, some concerns are well defined while others are cross-cutting.

At some point in any particular model one encounters 'primitive' elements that are loosely defined by their behavior and properties. The Composite Pattern is probably useful for constructing these 'primitive elements'. The model, then, need only concern itself with the interface to them.

But a problem domain is not defined by a 'particular' model. A problem domain is described by many models, often more than one per 'perspective', none of them definitive, every single one of them interacting.

Program development for a 'problem domain' requires developing these many models, tweaking rules and assumptions. If the rules and assumptions are scattered across OOP or functional code, each tweak must be similarly scattered. One might say that the ideal form of program development for interacting with arbitrary 'problem domains' is the ability to create and apply 'rulebooks' (sets of rules) that modify or override rules in other rulebooks, akin to a massive game of Nomic [wikipedia] . . . except (ideally) with automated detection for consistency (type safety being one sort of consistency) and automated execution of the rules.

Only logic programming and variations (including constraint logic programming, and rules-based programming) are among those I acknowledge as suitable for arbitrary problem domain programming.

Logic reactive programming could merge several databases and data-sources, transform these data sources into a database describing widgets and display elements and interaction elements based on a collection of rules. Add constraint-logic and one can also add layout rules for the widgets and construct a layout.

Rules-based programming (loosely 'when XYZ do ABC' or 'while XYZ periodically ABC' - bindings between observations and desired actions or effects) isn't quite so useful for the raw GUI development because (for scalability, multi-operator collaboration, and zoom-ability) you want to avoid a situation where merely viewing the GUI has significant side-effects on the world (outside of possibly turning on sensor devices). Also, capability UI principles suggest that primitive operator capabilities ought to be exposed precisely and controlled by intention, rather than through arcane magical gestures and rules (unless you're writing certain classes of adventure game...).

However, rules-based programming would certainly help administrators and operators express their own command+control demands on the world, in a manner that could (and probably should) persist between GUI access. If supervision is required for safety of a rule, of course, one could simply define the rule with 'supervision' provisions in its observation element (the problem domain must be extended to include a model of the operator).

OOP and functional still have their places when it comes to modeling of services, computations, modularity, security, distribution, etc. They make for very useful primitives in describing how a computation service interacts with the problem domain. However, they are unsuitable for more than fragmented application. A function might describe part of a rule, and an OO element might define a primitive user-command capability that can be provided via binding a button or textbox or joystick, but one needs something more powerful for the glue.

In this broader scheme, Composite Pattern no place at all. Composite Pattern is a vestigial artifact that comes from attempting to work around the limitations and weaknesses of OOP for problem domain modeling - and, generally, failing. The contexts in which one might apply Composite Pattern, the forces leading to its use, and the role it fulfills, are better realized by escaping the OOP paradigm.

The basic idea of assembling elements into larger elements fits quite naturally into both functional and OO.

In functional, composites are (usually) described by structurally recursive (or co-recursive) data types. One might usefully combine GUI elements (e.g. images, grip and pull gestures, buttons, data bindings, text) into larger GUI elements (e.g. Google map areas) that are then usable as elements in this manner.

In that design - which is a Composite, but is not Composite Pattern - the internal structure of the combined widgets is exposed directly to both the graphics engine and the programmers.

This exposure gives a great deal of freedom to tweak and transform and compose widgets both externally and internally (e.g. add new widgets into the Google Map area allowing you to tell a robot to 'go there!', add routes, etc.). It also allows the graphics engine itself to optimize and 'flatten' abstractions based on partial occlusions of the widget collection, to tweak layouts based on the properties of the output device, to selectively refine (and optimize) the reactive program based on the view-port, etc.

The 'Composite Pattern' is a subtly different beast. In every explanation I have ever read on Composite Pattern, it is about treating 'parts' exactly the same as the 'whole'. This means eliminating the distinction between them - the ability to look 'inside' an element and see (or transform) its internal structure.

It is, indeed, possible to use 'Composite Pattern' in functional programming. A potential example is 'Image = Time -> PixelPosition -> Color'. Note the 'Image' is defined as a function, not as a data structure. One may easily compose images into new images by this definition (e.g. to overlay circles, use translucent elements, hook elements side-by-side), and the users of the image won't be able to distinguish the composite without 'sufficiently smart' pattern recognition. In OO Composite Pattern, there are similar interface properties... e.g. one might define an OO output composite as 'interface IDrawMyself { void Draw(Time T, Screen S); }'.

Data binding, such that the image is drawn to reflect the outside world, may usefully be part of either of these (though keeping 'Time' separate remains useful for real-time interpolations and minimizing state manipulations).

For a UI, of course, you'd need to add some extra interface elements to handle user inputs - intercepting and forwarding mouse clicks, accepting or redirecting user 'focus', handling 'selections', etc. - it's quite a mess when you start looking at all the interfaces the Composite Pattern UI must provide explicitly. By the time you've added all these interfaces, your 'functional' approach will look a great deal like a record of functions - much like the OOP design described in this topic's paper.

With Composite Pattern interfaces, you cannot peek or tweak 'inside' a composite widget. Internal composition is not available to you. External composition can still be performed quite easily, though, via manipulating or wrapping 'Time' and 'Screen' (or PixelPosition). For example, one can rotate, warp, stretch, manipulate opacity, hue, brightness, place two items side-by-side, place one atop another, etc.

If careful, you might be able to perform something similar to 'internal' compositions via a combination of pattern recognition and interjection. This pattern-recognition is aided if the composite pattern essentially 'draws' at a high level (strings, polygons, bezier curves, buttons, etc.). However, one still cannot readily leverage internal structure - i.e. one cannot distinguish whether a given string or button comes directly from the object or from an object it composes internally.

There are, of course, intermediate forms between data-structured composites and 'Composite Pattern' with arbitrary degrees of structured interleave. A Screen might accept an 'IDrawMyself' object along with an internal box, (interface ICanvas { ... void DrawInnerElement(IDrawMyself, Region). }) allowing it to decide whether to draw that specific object based on visibility properties of the given 'Region', and simplifying UI routing and interactions with these elements.

But, despite the ability to formulate hybrids, I think it worth recognizing the properties of Composite Pattern as a subset of composition in general and distinct from data-structured composites.

Nice explanation.

With Composite Pattern interfaces, you cannot peek or tweak 'inside' a composite widget.

Which goes back to my point that you should not use the Composite Pattern if you need to do this. Your point about requiring Visitors, instead of refactoring as the real essence of the problem domain is discovered, is noted. This is a cost question I can't answer well. Yes, refactorings are automated. But if a test breaks, you must fix it. Refactorings are done in steps, and a refactoring of this nature in my experience is not a one-step refactoring. Those constraints in the Panel layout synthesis technique, that bound the viewport for an object, become a guard and invariant. That's a lot to refactor!

[Aside: Constraints are hard to test and preserve. Most constraint breakages are modularity problems that refactoring tools are unaware of. See Jonathan Edwards' OOPSLA '09 paper for an example.]

In WPF, the major problem has to do with the fact they created this artificial concept of logical trees and visual trees, and coupled the two together in subtle ways. I've read articles where people tried to do certain layering effects and were bending over backwards to fit WPF's model, rather than step back and look at the problem in the way MS Researcher Sean McDirmid has with Bling.

In a functional setting, I was imagining a value of existential type representing a general Widget's behavior. A compositing widget would general elements satisfying this interface and combine them into a composite satisfying the same interface. So I think I was talking about the actual Composite Pattern and not just "composition". To integrate this with FRP, I was imagining the dataflow configuration would be setup via the Widget interface.

With Composite Pattern interfaces, you cannot peek or tweak 'inside' a composite widget.

Peaking past the interface isn't the only way to achieve the properties you've mentioned. The interface can expose "reactive values" so that, for example, the render pipeline doesn't need to traverse the Widget hierarchy every frame.

The interface can expose "reactive values" so that, for example, the render pipeline doesn't need to traverse the Widget hierarchy every frame.

But the render pipeline needs to be aware of what reactive values to check, or the reactive values have to reduce down to something the render engine can understand/be notified of (think: InvalidateMeasure and InvalidateArrange messages an object can send to the rendering engine in WPF, or the even more monolithic Control.Invalidate message in WinForms). There has to be an explicit hook to the environment.

[Aside: Also, WinForms underlying APIs, GDI+ and User32, are not really expressive enough to do anything more than Control.Invalidate, for reasons that can cause the Window Manager to just lock-up due to thrashing on composites' callback paint functions getting mercilessly called back to hell.)

I didn't really follow this or at least see how it affects what I'd written. In my setup, a Widget exposes something like a scene graph node as a reactive value. The renderer just monitors these values, which have a structure which allows for efficient culling, etc.

a compositing widget would [take] elements satisfying this interface and combine them into a composite satisfying the same interface

Ah, yes, that would be Composite Pattern. I apologize for the confusion; it was unclear to me from your prior discussion.

to integrate this with FRP, I was imagining the dataflow configuration would be setup via the Widget interface

As an aside, it would be far more convenient to achieve FRP the other way around: set up the Widget interface via a data-binding (synchronous dataflow) configuration. FRP [at least of the first-class variety] curries very nicely: {bind-apply Function DataSource} takes a pure Function and a reactive DataSource and returns a reactive value - potentially another function whose output depends on both further inputs and the dynamic state of DataSource.

A Widget, then, would be a record of reactive functions - some of which might return procedures to be executed - without any need for explicit weaving of the data bindings. FRP-computed procedures (as distinct from procedures that gather their data at time of execution) are theoretically quite useful, offering a great deal of flexibility and some very powerful JIT, partial-evaluations, disruption tolerance, caching, and liveness properties.

Given that any explicit reactive setup would need to cut across widget interfaces in each composite layer, the above variation saves more than a little hassle.

Peaking past the interface isn't the only way to achieve the properties you've mentioned. The interface can expose "reactive values" so that, for example, the render pipeline doesn't need to traverse the Widget hierarchy every frame.

While performance was a concern, it was hardly the only property with which I'm greatly concerned. Internal composition is equally important. Capability UI principles are useful.

In my current line of work, I need to combine widget elements as a matter of course. For example, a simple widget - a context menu - ought to depend on which unmanned system you're controlling, which payloads are on that system, the state of those payloads, which operator configuration is active, the state of that configuration (including recent alerts, active missions, etc.), the current operator selection or 'hand', any objects under the mouse, distance to those objects and obstacles between operator focus and the platform, etc.

The same is true for hover-text, frame menus, HUD, and so on. Maps are not an exception, but at least map implementations have a long history of supporting user-provided components (i.e. via adding points, lines, polygons, volumes, images, layers, etc.).

The programming tools I have at work, of course, are very far from what I desire... but they certainly have made me think deeply about what I desire.

The basic idea of exposing a 'broader' interface for each generic widget - an interface to expose reactive values and efficient rendering, for example, and another to allow drag and drop, and another to support user selection, and another to support command clicks and double-clicks, and another to support fragments of gesture recognition, and another to accept keyboard focus and process inputs, etc. - can be made to work.

However, this approach is ultimately a very painful, uphill battle against the OOP paradigm. One is facing the traditional Expression Problem.

The fact is that the set of basic widgets (menus, maps, texts, buttons, volumes, lines, polygons, canvases, text inputs, dialogs, etc.) tend to be relatively constant. Most 'new' widgets are formed by composing primitive widgets, as opposed to creating something entirely new. [Edit: Of course, any forward thinking widget set guarantees the required flexibility is available by providing at least one or two 'widgets' with low-level drawing functions (e.g. an SVG image map, and an opaque media-type/plugin-selector object). These flexible elements can support developers who like to surf the bleeding edges of technology (without crashing against craggy walls and becoming bloody smears) - the cost of these opaque widgets, of course, is the loss of internal composition and performance and ease-of-use. Any very-common use of such opaque 'interface-based' widgets is thus a fine target for later becoming a primitive widget, similar to how 'video' and 'image map' is being added to HTML5. Macros and Frameworks serve a similar role in extending a programming language to meet new requirements.]

Similarly to the widget set, the set of basic UI interactions (click, double-click, drag and drop, rendering, keyboard focus, minimize and maximize, selections, etc.) is also relatively stagnant. Occasionally someone comes along and invents a new UI interaction (e.g. gesture recognition) that requires some widespread manipulations, but most 'new' interactions (e.g. one-click shopping, zoom, navigation) are composed as simple protocols atop already supported interactions.

So, from the above two features, one might believe that UI is 'neutral' towards the Expression Problem. OOP minimizes the impact of adding entirely new widgets, and Functional minimizes the impact of supporting new interactions atop a given set of command capabilities, but neither of these sets vary all that often.

However, upon taking into account the desire for internal composition and re-composition - various mashups, injections, style transforms, accessibility transforms, adding elements to the correct locations in a context menu, overriding elements, removing or disabling elements, etc. - that neutrality vanishes. The ability to add arbitrary new internal composition greatly favors a functional or logic-programming design that exposes structure for the common 'types'.

In the Composite Pattern design, each new mashup, injection, style transform, partial override etc. would tend to require either a new 'interface' or some very powerful pattern recognition that can intercept outputs from the widget interfaces.

I kind of have in mind code that says "in accessibility mode, change all text to 24pt font, except for the copyright notices." Is that the sort of thing you mean?

However, this approach is ultimately a very painful, uphill battle against the OOP paradigm. One is facing the traditional Expression Problem.

I agree, but one of the things I'd like in a language is a more canonical solution to the expression problem.

I kind of have in mind code that says "in accessibility mode, change all text to 24pt font, except for the copyright notices." Is that the sort of thing you mean?

Yes. Or, similarly, "add this new menu 'Abc' to the right of 'File' if it exists, but as far to the left as possible..." or "Place button B near Submit..." or "Modify every occurrence of the word 'xyzzy' to appear in bold".

By 'internal composition', in general, I mean the ability to create a new structure by selectively accepting, replacing, transforming, and combining the elements composing one or more other structures. By 'external composition', one creates a new structure by wrapping, chaining, linking, embedding, tiling, etc. multiple other structures as whole elements. Only internal composition requires that composites be exposed and a distinction between primitives and composites.

one of the things I'd like in a language is a more canonical solution to the expression problem

Indeed.

I can think of a number of partial solutions (open functions and datatypes, horizontal subclassing, various forms of export/import inversion allowing service modules to import from multiple independent clients - my language uses require/provide/combine) but most of these run into issues of modularity, dynamic configuration, code ownership, security.

I've my doubts we'll ever find a fully satisfactory answer to the expression problem in-the-large, but even partial solutions should go a long way (especially if you add automated code distribution and communication of 'implicit' context).

I'm with you now - I make a similar distinction between open box (or clear box - slightly different) and closed box methods. Open box / internal methods are in general more powerful, but closed box / external methods typically have better isolation properties and are easier to reason about. With regard to GUI programming, internal methods may be appropriate for the layouts used in a particular application, but I think the core GUI library should consist of well encapsulated abstractions.

There is no such thing as "accessibility mode" in a user composable interface. Accessibility is a huge topic, but it ultimately boils down to making content available to user's in a way they can consume it. This goes beyond knowing their hardware configuration or OS or whether they are browsing the web via terminal. It literally means user control. However, the W3C has simplified (well, techincally, complicated through legalese language) the meaning of accessibility to mean what they can describe in a declarative format and push responsibility for understanding new media to the hypermedia engine and some gold standard that describes what canonical media people can use.

Some accessibility and human-computer interaction features could be automated, however. Such as the KDE Project's Okular document viewer's ability to trim the margins of a document. These wide margins in most PDF documents make sense when they are typeset for printing a big book, but not when your goal is to read text on an LCD monitor or ebook reader device.

Bottom line: User composable interface means the environment is modular enough for the user to control its representation. Accessibility mode implies there is some sort of guard that allows you to pick from a set of configurations (at least to me). Symbolics Genera is probably the closest OSes have come yet to this ideal. If you want to read more, buy copies of Your Wish Is My Command and Watch What I Do.

Arguably HTML 1.0 was more "accessible" than the current standard. At least in 1.0 the users could pick their own fonts, font colors, font sizes, and background colors, and reliably command their browser to ignore the red text on green background that some idiot page designer specified without thinking about color-blind users.

As HTML has gotten more complex, the user's browser configuration has gotten less and less respected. In fact, doing ANY browser configuration now is generally a way to BREAK webpages. Even if you go through the rigmarole now with 'important' keyword and proxies that do DHTML rewriting and the whole business, someone will still screw you over by using a layered graphic on a higher layer, or a box specified in pixels, without scroll bars, to hide text that you have so laboriously forced your system to display large enough to read.

I really want a browser where I can make a simple command to the rendering engine to guarantee that AT LEAST all the text actually gets rendered somewhere on the page, in a known minimum size, with some reasonable contrast between the text and background, in a location where the text is the ONLY thing rendered (ie, no background graphics or overlayed tables) and in a place that will not move relative to the rest of the page as I scroll around, even (especially!) if the rendering engine has to ignore specified sizes, placements, animations, etc, layer orders, etc, to do it.

The very fact that it's gotten hard to even list all the different ways that webpages can obscure text now indicates the real problem with accessibility.

Ray

Apologies.

I was having issues posting to LtU that day. This wound up appearing thrice. Sorry.

A potential example is 'Image = Time -> PixelPosition -> Color'

With Composite Pattern interfaces, you cannot peek or tweak 'inside' a composite widget.

Image : Time -> Polygon -> (Maybe Color, Maybe Image)

The Image function could be implemented as tree of Image function branches terminating at Polygon which are contained within a Pixel.

Generalize to take slices of composition which are not only by area:

Image : Time -> Compositor -> (Maybe Color, Maybe Image)

I completely disagree with the idea that the methods in an object are a "representation". I've heard this before, and it only makes sense if you are thinking purely from an ADT viewpoint in which the type of a value is its representation. But the interface of an object is analogous to the ADT signature. Nobody is going to complain the the ADT signature is somehow a representation that needs to be hidden.

How could you construct new objects that work with existing (hidden) code if the representation of those objects was hidden? The fact that you can create impostors is because the representation of objects is known. There are other viewpoints you can take, but clearly in some sense their representation is known.

Edit: Stated another way, there are reasons to want to hide the actual type of a value as it prevents impostors. With object interfaces you implicitly support construction of new classes of objects. Obviously methods cannot be inspected, so in another sense representation is hidden.

Yes, this is perhaps the key difference between ADTs and Objects. With ADTs you cannot create impostors but with objects you can. Whether or not this is a good thing depends on whether you want control or flexibility. Of course, by using the name "impostor" you are making a value judgment.

But I still insist that the interface is what matters. I would say that an ADT has two types: an interface and a hidden representation type. Objects only have one: the interface. There is no representation type.

The flip side of the coin, I think, comes from this part of your essay that I thought could've been stronger:

Unlike abstract data types, many people find objects to be deeply disturbing. They are fundamentally higher-order, unlike abstract data types. With an object, you are never quite certain what it is going to do: What method is being called? What kind of object is it really?

On the other hand, many people find objects to be deeply appealing in their simplicity and flexibility. They do not require complex type systems. Inheritance allows recursive values to be extended in powerful ways.

The fact that objects are autognostic, so that they can only know themselves, is also confusing. On the one hand, it interferes with desirable optimizations that require inspection of multiple representations. One solution is to expose representational details in the object’s interface, which limits flexibility.
The benefits of autognosis are often subtle and only realized as a system grows and evolves.

The essence of good object-oriented design is elimination of guards. The benefits of autognosis are only realized if the objects collaborating with one another are atomic, indivisible entites in the problem domain. For this reason, autognosis pairs off with finite state automata in describing the structure of object-oriented programs. With the finite state automata architectural constraint, popular in real-time object-oriented systems engineering, the sender of a message does not need to know what state the receiver is in. This provides robust decoupling between the sender and receiver, as they are now not dependent on each other's implementation and their information details can be hid via encapsulation. Thus, there is nothing "confusing" about the autognostic principle. It is simple math.

I would also add that an alternative to exposing representation details is to model things of things, and thus make everything a representation detail customizable by the environment. This is a system-level approach, whereas the object-level approach you describe derives its inflexibility from its allowance to its consumers to use guards.

From this angle, everything looks asynchronous, just as Alan Kay described:

Somewhere in all of this, I realized that the bridge to an object-based system could be in terms of each object as a syntax directed interpreter of messages sent to it. In one fell swoop this would unify object-oriented semantics with the ideal of a completely extensible language. The mental image was one of separate computers sending requests to other computers that had to be accepted and understood by the receivers before anything could happen. In today's terms every object would be a server offering services whose deployment and discretion depended entirely on the server's notion of relationsip with the servee.

and

Smalltalk's design--and existence--is due to the insight that everything we can describe can be represented by the recursive composition of a single kind of behavioral building block that hides its combination of state and process inside itself and can be dealt with only through the exchange of messages.

Edit: The most basic kind of "Impostor" (a useful term) is when a client caller depends on an implementation detail (the object's internal state-process), thus creating a non-obvious guard. The object is in one state, but the client is assuming the object to be in another state. Rather than refactor the problem domain model, a guard is typically added to explicitly check the state of the object before sending a message to it. This is simply bad design, or big ball of mud. The more crazy form of Impostor is the one the object capability model researchers came up with, and it is not a value judgment so much as a security riddle.

Edit #2: Also, you said "many people find objects to be deeply disturbing". Then, as rhetorical questions, you gave: "What method is being called? What kind of object is it really?" The second question you do a great job addressing in the paper, with several good rules for how to use a language like Java in a pure OO manner. However, the former isn't addressed, but my push back to those deeply disturbed by objects would be "Why do you care?" If your code needs to stop the world to know what method is going to be called, then it will never be simple and robust. That's why the finite state automata architectural constraint complements the autognosis principle.