(long) programming by extension (was: How to write TYPECASE in Ada 95?)

[Samuel Mize <smize@imagin.net>]

Mike Silva <mjsilva@jps.net> wrote:
> 
> Samuel Mize wrote in message <7av52o$62g@news3.newsguy.com>...
> <...>
>>Remember, tagged types are NOT a facility for object-oriented
>>programming.  Together with other facilities in the language, they
>>support that idiom.  However, tagged types are a facility for
>>programming by extension, in a much more general form than many
>>object-oriented languages provide.
> 
> This intrigues me greatly, but being an Ada neophyte and not having that
> much OOP background in general I don't know what it means.  Would anybody
> care to offer an explanation, or point me in the direction of one.  Thanks
> much.

I don't have an appropriate pointer to an existing discussion (I'd be
interested to see them too).

Instead of replying by email, I'll be long-winded here on the net, so
others can chime in with additions or corrections.  Note that the
early part of this covers the basics of defining abstractions in
functional programming, to motivate building up to programming by
extension toward the end.

- - - - -
Programming by Extension means programming a large system so that new
processing cases can be handled by adding new code, without having to
recode any existing modules.  Language support is extremely helpful
for true programming by extension.

Object-oriented development is a very specific way of analyzing,
designing and coding a system.  It provides a way to program by
extension -- that's one of its selling points -- but it brings along
a lot of other baggage too.

Sometimes you want that baggage.  That's why "object-oriented"
technology exists.  But sometimes you just want to do plain functional
programming, and be able to extend the system later without having to
recode the existing part.  Ada supports this also.

The Ada 95 Rationale describes how Ada supports programming by
extension, but it doesn't really define the term.  Here's a concrete
example of programming by extension.  I'll motivate it by showing the
intermediate manual steps that lead to programming by extension.

Consider a windowing user interface.  You have a main loop that looks
at events, like mouse clicks, and calls the appropriate routine to
handle the event, passing that routine a pointer to the window that
owns the part of the screen where the event occurred.

The simple-minded approach would be to put all the code into the loop.
Applying functional abstraction, we can define some procedures like
Draw and Process_Mouse_Click, and call those procedures in the event
loop.  Now, if we put them into a separate package, we can change the
procedures without having to recode or recompile the loop:

   package Windows is
      type Window is ...

      procedure Draw (W: Window);
      procedure Process_Mouse_Click (W: Window);
   end Windows;
   - - - - - -
   with Windows;
   procedure Event_Loop is
      W: Windows.Window;
      E: Event; -- defined somewhere else
   begin
      loop
         Get_Event (E);
         Get_Current_Window (W);
         case E is
            when Draw_Window => Draw (W);
            when Click => Process_Mouse_Click (W);
         end case;
      end loop;
   end Event_Loop;

However, if you add a new kind of window, you will change the Window
type.  That means you will have to recompile the event loop, and
you will have to recode all the procedures in package Windows.  That's
not a big deal for this small, trivial example, but in a large system
it can be a significant cost.

Note that Ada is often used in life-critical systems like avionics,
where each unit goes through a long and expensive validation of the
compiled object code.  This must be redone if the unit is recompiled,
even if the source code is not changed.

So, we want to completely isolate the event loop.  We can do this by
making Window a pointer that can point at any kind of window, so that
Event_Loop won't have to be recompiled when we add a new kind of window.

In C, you would do that by declaring Window as a pointer to void.  The
actual window data structures would all start with an integer.  The
window procedures, like Draw, would typecast that to pointer-to-integer
to see the integer, and use that integer to pick the right type to cast
the pointer to in order to handle the event.  This is (very) roughly
how the X-windows system handles windows.

You can do the same thing in Ada 95 or C++, but it's wiser to use the
language-provided features.  I'll describe Ada's in a moment.

And even then, you'll still have a big case statement full of
type-specific code in each window routine.

The next step is to make the routines in Windows nothing BUT the case
statement, and extract all the code out to type-specific packages for
each window type.  Something like:

   package Basic_Window is
      type Window is
         record
           Kind: Integer := 1;
           ...
         end record;
      procedure Draw (W: Window);
      procedure Process_Mouse_Click (W: Window);
   end Basic_Window;
   - - - - - -
   package Alert_Window is -- border flashes red
      type Window is
         record
           Kind: Integer := 2;
           ...
         end record;
      procedure Draw (W: Window);
      procedure Process_Mouse_Click (W: Window);
   end Alert_Window;
   - - - - - -
   package Windows is
      type Window is private;

      procedure Draw (W: Window);
      procedure Process_Mouse_Click (W: Window);
   private
      type Hidden_Window_Type;
      type Window is access Hidden_Window_Type;
   end Windows;
   - - - - - -
   with Basic_Window;
   with Alert_Window;
   package body Windows is

      type Hidden_Window_Type is
         record
           Kind: Integer := 2;
         end record;

      type Kind_Of_Window is (Basic, Alert);

      -- - - - -
      function To_Basic (W: Hidden_Window_Type)
         return Basic_Window.Window is ...
      -- probably an instance of Unchecked_Conversion
      
      ----------
      procedure Draw (W: Window) is
      begin
         case W.all.Kind is
            when 1
              => Basic_Window.Draw (To_Basic (W.all));
            ...

Now, if you add a new kind of window, you create a new package and
update the case statements in Windows.  You only compile the new
package and the body of Windows.  You have almost achieved programming
by extension; you have come about as close as possible manually.

The Programming-by-Extension facilities in Ada 95 let you eliminate
the package Windows.  If Basic_Window.Window is a "tagged" type, your
event loop's calls to Basic_Window.Draw will be interpreted as being
calls to the appropriate Draw for the actual type of Window involved.

Another feature of the Programming-by-Extension facilities in Ada 95
is that, when you derive a new type from a tagged type, you can re-use
the "parent" type's procedures, if they still apply.  For example,
suppose that both Basic and Alert windows process mouse clicks the
same way; the only difference is how they draw the window.  Your code
would look like:

   package Basic_Window is
      type Window is tagged
         record
           ...
         end record;

      procedure Draw (W: Window);
      procedure Process_Mouse_Click (W: Window);
   end Basic_Window;

   - - - - - -
   with Basic_Window;
   package Alert_Window is -- border flashes red

      type Window is new Basic_Window.Window with
           Flashes_Per_Second: Integer;
         end record;

      -- Draw is "inherited" -- the Draw from package Basic_Window
      --    will be used for objects of this type

      procedure Process_Mouse_Click (W: Window);

   end Alert_Window;

   ----
   with Basic_Window;
   procedure Event_Loop is
      E: Event; -- defined somewhere else

      function Get_Current_Window
         return Basic_Window.Window'Class is ...

      procedure Handle_Event (W: Basic_Window.Window'Class) is
      begin
         case E is
            when Draw_Window => Basic_Window.Draw (W);
            when Click => Basic_Window.Process_Mouse_Click (W);
         end case;
      end Handle_Event;

   begin
      loop
         Get_Event (E);
         Handle_Event (Get_Current_Window);
      end loop;
   end Event_Loop;

Note that, in Event_Loop, we don't know how much memory an arbitrary
window may need, so we can't just declare an object of type
Basic_Window.Window'Class.  Instead, we make it a parameter to a
helper procedure.  Its size may vary at run time, but the compiler
and run-time system take care of that "behind the scenes."

NOW we have programming by extension available for this system!

To add a new kind of window, we create a new type that extends
Basic_Window.Window (or Alert_Window.Window).  We don't have to recode,
or even recompile, ANYTHING -- not the window packages, not event loop,
NOTHING!  The Ada compiler and run-time take care of calling the right
Draw or Process_Mouse_Click routines, based on the actual type of the
window returned by Get_Current_Window.

I hope you find this extended sketch useful.  

You can do the same general thing in C++, but you have to make the
window type a class, and each new window type a subclass of that
class.  An instance of the class is an "object."  The terms "class"
and "object" carry a lot of connotations that may not be true in all
cases, for instance that the item in question is a discrete entity
that exists in its own right, or that the "classes" involved form a
meaningful taxonomy and not just a hierarchy that reflects some
implementation concern.

I believe there are semantic constraints and extra coding effort if
you use C++ for non-object-oriented programming by extension, but I am
not familiar enough with the language to give you specific details.
(Anyone else?)

Best,
Sam Mize

-- 
Samuel Mize -- smize@imagin.net (home email) -- Team Ada
Fight Spam: see http://www.cauce.org/ \\\ Smert Spamonam