A software engineering problem: how would functional programming solve it?

Here is a simple software engineering problem that I have encountered the last few days. It's not something dramatic, but one that has made me stop development in search of elegant solutions. I am posting this here because I would like to see how functional programming languages would solve this problem.

Here is the problem: I am writing a GUI toolkit that reuses the Win32 API wrapped up in a set of C++ classes (the reason is that there is no GUI library that completely hides Win32 will reusing it - existing libraries either follow Win32 logic (ala WxWidgets) or provide their own implementation (ala Qt/Swing)). As you may know, Win32 is not object-oriented, nor does it have a well thought out/consistent interface. For example, although the menu bar is a screen object, it is not a window: all there is is a bunch of functions for creating a menu, redrawing it, adding menu items etc. But I want to have menus and other non-window Win32 items as widgets in the toolkit, for consistency reasons.

The problem lies in the organization of classes. I have 4 types of widgets:

  1. widgets with no children and no window: for example, menu items
  2. widgets with no children and window: for example, buttons
  3. widgets with children and no window: for example, menus (which have menu items as children)
  4. widgets with children and window: for example, forms

The object-oriented design solutions would be:

  1. make non-window classes unrelated to widgets; something I don't desire as it is a non-consistent solution (after all, a menu IS a widget)
  2. make a generic Widget class that has children and all window properties and ignore those properties for non-window widgets; a nasty solution.
  3. have 5 separate classes: Component, Container (extends Component), Window (extends Component), WindowedComponent (extends Component, Window), WindowedContainer (extends Container, Window), using multiple virtual inheritance or aggregation. I also don't like this solution because of namespace pollution and because it will be seen as complex by the library's users.
  4. have 3 separate classes: Component, Container (extends Component), and template class Window that can be parameterized by the type of superclass (Container or Component). I also don't like this solution, because a) templates are slow in compilation, b) bloat the size of code, c) all code has to be in the header file.

So what I am asking is how functional programming languages solve an issue like the above, which is an issue of code organization/clarity/reuse/taxonomy. I can't seem to find a good object-oriented solution to the problem, nor any of my colleagues/friends can. So I am asking if other programming paradigms have a better solution for this problem.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Tk (again...)

... there is no GUI library that completely hides Win32 will reusing it - existing libraries either follow Win32 logic (ala WxWidgets) or provide their own implementation (ala Qt/Swing).

Tk hides the details of Win32 programming model, but uses native widgets on both Windows and Mac. If you grab the Tile extension it will also pick up Win XP themes. It's also a darn sight easier to use than Qt, Swing or WxWidgets. Is there any specific reason why you wouldn't want to use it?

Other than that, pretty much every FP language will have some GUI toolkit, so I'd suggest having a look at what is out there. You also might want to look at Haskell's type-classes.

In the MSDN library under WIN

In the MSDN library under WIN32 API there is a description of how to use the basic C/SDK window system. (the mother of all window systems?) It seem very straight forward and easy to understand compared to MFC. The only problem is that you have to type in about 100 lines of ugly C code, or you can cut and paste the GENERIC.C sample and start adding your own call back functions, etc. I believe that there are respectable people who still use this system although I don’t know who they are.

Tk does not support the Model

Tk does not support the Model-View-Controller paradigm, does it? And most FP languages use either Gtk, or wxWidgets, or some other X-Window System-only toolkit, which does not directly show me how an FP language would solve the problem I have. WxWidgets does not hide Win32 details (for example, it uses message maps instead of overloading), and Gtk does not honour the constraints I have (for example, Gtk Buttons and Gtk MenuItems are containers).

I don't know if this helps, b

I don't know if this helps, but from an "engineering" point of view a window system is an interrupt handler. Such things are very closely related to the hardware and not ideal material for functional programming. On the other hand I have never seen an "oop wrap" of the WIN32 API that I really liked.

An Observation

You seem to be conflating two things - the model you want to present to the user and the model used for the implementation.

The issue with this is that the original architecture did not have a nice OO structure with its components well-related by a sensible inheritance structure.

You cannot build a *transparent* object model of what is an essentially ad-hoc component-based architecture without exposing the ad-hoc component-based nature of the underlying architecture.

As such, if you want to provide a nice OO structure containing inheritance for this collection of components, you'll need to use the underlying system only as an artifact of implementation, plastering over the "transparent model" to provide your own abstractions.

This will require some cruft in the implementation regardless of how you model the object hierarchy.

If I were designing a model to expose to the user, I would have a base Component class and a subclass of that called CompoundComponent which added a collection of sub-components. I'd then have a Window class (probably inheriting from CompoundComponent, because it would have it's own set of child components - e.g., scroll bar widgets, title bars, etc.) with a secondary collection of Components called "contents" that holds what's contained in the window. I'd then place Menus, Buttons, Forms, etc., in the external facing object model in a way that makes sense in this model. So what if a Button is a Window in Win32? It doesn't need to be one for 99% of your users, so don't expose that use fo the component. Do the same analysis for the other primitive Win32 components. Build a sane object model for the user and leave the Win32 cruft where it belongs - the implementation world.

Again, you cannot build a *transparent* object model of what is an essentially ad-hoc component-based architecture without exposing the ad-hoc component-based nature of the underlying architecture.

Separating interface and implementation 101

(If you want an overview of the main message of this long post, read fadrian's post which was posted while I was writing the following mini-essay.)

First, I'll note that this is not actually a programming language question, and despite appearances, it's not even a question about comparison between paradigms — it's really about How to Design Programs, a subject for which many of the principles transcend any specific paradigm.

It sounds as though the best approach here will be somewhere between #3 and #4, but that the problems with such approaches has more to do with limitations of C++ than the appropriateness of the conceptual designs. For example, all of the problems mentioned with approach #4 would be non-issues in a language with a good polymorphic type system (e.g. ML, OCaml, Haskell). In addition, some of the complexity in #3 comes from the need to use multiple inheritance merely to provide common interfaces across a set of classes.

Unfortunately, C++ fails to explicitly separate interface inheritance from implementation inheritance, which means that it's up to the programmer to organize code in a way that hides implementation details, as opposed to relying on the language to do so. This means that a price is paid in terms of implementation complexity, merely for hiding implementation details. (In C++, Real Programmers implement their own implementation hiding mechanisms, and some of the most famous books about C++ focus heavily on such techniques.)

Regardless of what language or paradigm you're using, you should start out by being careful to distinguish between the design of the interface to your library, and its implementation. In C++, it can be difficult to avoid confusing the two, and this often results in confused design. With proper separation, the problems of complexity and namespace pollution don't arise, because the interface will only provide what's actually needed by clients of the class to get the job done, and nothing more. This means every feature of the interface can be justified by saying "you need that to be able to...", not "we had to put that in because the implementation..."

So, the first task is to forget entirely about the implementation, and look at what makes sense for clients of these classes. Don't think about code reuse or the organization of the implementation, think only about interfaces. The interface should not contain anything which has to be explained in terms of the implementation — that's what leads to complexity and namespace pollution.

As part of this process, you should be careful to avoid allowing the bad design of Windows to contaminate your interface design. Factoring the design around an abstraction called a "Window", so that e.g. a Button ends up being some kind of Window, presupposes a great number of design choices related to what a Window is. If the goal is to require that users think in terms of Microsoft's abstractions, fine, but that's an external limitation on the design which constrains the possible solutions.

At the very least, in the design phase you will be better off treating a Window as an hidden implementation detail, so that if you do decide to expose some version of that abstraction to your users, you do so with a better understanding of its relationship to your design, which should be more clearly factored than that of Windows.

As another example here, the idea in #4 of having a Window class as a template parameterized by Container or Component seems wrong from the library user's perspective. How would you explain to a library user why such a design was chosen, without resorting to talking about implementation details that should be hidden? Of course, it's possible that you might use such a design internally in order to achieve code reuse, but if there's a reason to expose that detail to library users, it hasn't been made clear.

What needs to be examined are the operations that need to be performed on concrete objects such as buttons, menus, menu items, etc., and how best to factor those operations for users of the library, so that they can use common interfaces to access the different kinds of objects, where that makes sense. This is actually a standard OO design exercise, which seems to have been confused in the question by implementation details relating to C++ and Windows.

From the problem description given, it seems that a likely solution at the interface level might involve as few as three interfaces: in the language of approach #3, these would be some variation of Component, Container, and Window (bearing in mind that "Window" is an interface whose purpose hasn't yet clearly been defined). It seems likely that Container and Window would be subtypes of Component.

Once the interface design work has been done, the result should be a suitable interface for users of the library. The next task is figuring out how to express that interface design in the target language. Even in C++, expressing an interface design is not that difficult. If the result does end up with interfaces that cut across classes (as seems likely), it might very well make sense to use multiple virtual inheritance to implement that, but that should be expressed purely at the interface level, e.g. using multiple virtual inheritance from pure abstract classes (a.k.a. interfaces).

In Java, you'd use Java's explicit interface mechanism to implement something like this; in Haskell, you might use typeclasses; in OCaml, you might use structural subtyping. The functional languages also tend to have a number of other ways of expressing this sort of thing (e.g. functors, units), because of the flexibility of higher order functions and their ability to parameterize behavior.

The part where things will start to get messy in C++ is in implementation. That's nothing to do with object-orientation, it's purely to do with the limitations of C++. Having to suck up messy implementation details is part of the deal with the devil you make when using C++. (Like most deals with the devil, any perceived upside is purely illusory.)

Again in terms of the implementation described in approach #3, the widget implementations might map to interfaces as follows:

Widget Supported Interfaces
Menu items   Component
Buttons Window
Menus Container
Forms Container, Window

Note that although it might be useful to have implementation classes such as WindowedContainer or WindowedComponent to support reuse of code in the implementation of some widgets, that doesn't necessarily mean that these classes should be exposed to users of the library, except possibly to help them achieve code reuse in implementing new widgets of their own. In that case, it should be recognized and made clear that the purpose of such classes is reuse of implementation, and that they do not represent part of the client code interface to widgets.

Note further that if a class such as Form is implemented by inheriting from a WindowedContainer class, then ideally, that implementation inheritance should be hidden from users of the Form class. Strategies to do this sort of thing are standard fare in the C++ literature, see e.g. Coplien or Alexandrescu. If you choose to forgo such strategies, then you have to recognize that you're making an optimization choice which results in less clearly delineated boundaries between interface and implementation, which results in leakage of implementation concerns into the client's code. In C++, this has consequences related to header file dependencies and so on, so forgoing such encapsulation puts the usability of the resulting library very much at risk. You wouldn't need to worry about this sort of thing in a higher-level language.

I've provided some suggestions phrased in fairly OO-sounding terms. However, don't be misled into thinking that such solutions are unique to OO. Separating interface from implementation is a basic design strategy, which ironically, most OO languages do a particularly poor job of: they conflate interface and implementation at multiple levels, most damagingly in the inheritance mechanism.

If you really want to understand these issues, your best bet is to forget about OO, and look at the ways in which truly abstract interfaces can be created with higher-order functions — both "manually", as well as via related mechanisms such as functors (e.g. in ML) and units (in PLT Scheme; see here for a gentler introduction). Given familiarity with such systems, the shortcomings in OO languages in these areas become clear, and it is easier to avoid the traps which the design flaws in OO languages create.

The overriding point in all of this is that designs should first be done conceptually, and abstractions should be designed, well, abstractly. Once you've done that, the rest is just a matter of expressing the abstractions in your chosen language. The functional languages have an advantage here for many reasons — they're higher level, and more expressive both in terms of abstraction capabilities and their type systems; but even if it weren't for that, the mere fact that they don't have fundamental errors in the design of their core abstraction mechanisms is a huge benefit.


[Edit: another nice introduction to some of the issues I've touched on above can be found in Matthias Felleisen's Components and Types.]

Allow me

To second this comment.

Thanks a lot for the replies,

Thanks a lot for the replies, they are really appreciated.

My answer

Since the specified problem states that you're building on top of the Win32 API, I really doubt that you're going to be able to avoid imperitive programming. My advice in this specific instance would be to use a language like Ocaml which supports both imperitive and OO programming, and do things the obvious way.

That being said, I think there's an interesting area of debate: how could/should you design a proper functional GUI library? I'm assuming that you'd have a fundamental imperitive monad to do the actual I/O, something of the form (in Ocaml's types):

val putpixel: x:int -> y:int -> color:int -> unit

I'm thinking of splitting the drawing of the various GUI widgets from handling their behavior. So take the scroll bar widget. There would be two "objects" associated with the scroll bar. One would be the function to draw the scroll bar in it's current position. The other object would be a listener- so when you clicked on the scroll bar to move it, the listener would change the current set of drawable objects- replacing the current scroll bar drawing function with a new scroll bar drawing function that draws the scroll bar in it's new place. Especially as the scroll bar listener object also changes other how other drawing functions, for example the drawing function of the text field associated with the scoll bar.

Fudgets

Fudgets are one example of a functional approach to a GUI API (for X Windows, not MS Windows, but the principles are similar).

Another

Another is YAMPA and Fruit, which is built on top. They are basically the same, with slightly different formal semantics. However, they both lack a solid set of real-world combinators that actually makes gui programming easy. A similar approach is being pursued by Adam and Eve (mentioned here on LtU at some point), but staying a little closer to the tried and tested gui models.

also look at qtk for mozart

It's also worth looking at the Qtk library. It's wonderfully simple though perhaps not as elegant as Fruit.