Re: Procedure types and dynamic binding

[rjh@cs.purdue.EDU (Bob Hathaway)]

> 
> But this assumes no type or error checking at all.  By dynamic 
> parameterization I meant with runtime type and error checking.  
>
>    The same runtime type and error checking will occur with
>    the unrestricted pointers.  When an operation is applied
>    to the object pointed to, the type of that object will
>    be used to determine which code to invoke or to prove
>    the existence of a run-time error.  Now I see no reason
>    why we can't say "pointer to TYPE_1 or TYPE_2 (etc.)",
>    thus introducing a new form of restricted pointer, but
>    what we are dealing with here is the need to store 
>    any type of object whatsoever.  Clearly, unrestricted 
>    pointers, with their associated run-time costs, should 
>    only be used when their power is absolutely necessary. 

I'm still not sure what this means.  Do you mean passing 
unrestricted pointers to procedures and then selecting the 
procedure via overloading (ad-hoc polymorphism) at runtime?
I meant allowing polymorphic parameters to a particular subprogram, 
such as
        procedure test (parameter : polymorphic; ...) is ...
which defeats static typechecking of parameter and uses a 
type attribute in the body of test.  This also brings up the issue of 
name vs. structural equivalence of runtime typechecking in both cases,
but the usual Ada rules could apply.   Either approach allows 
considerable power but adding runtime typechecking is not a trivial
extension, as discussed earlier.  But I agree a more powerful parameter
passing mechanism is highly desirable.

>> For static typechecking of data we can use a pointer to a tagged variant 
>> record to distinguish types.  This assumes foreknowledge of the types in 
>> the variant but at least allows subprograms to distinguish objects.   
>
>    What you describe is a hack which would provide (less cleanly) the
>    power provided by the form of restricted pointer described above.
>
>    This is inappropriate to the problem under discussion, which 
>    assumes the need to program a polymorphic stack without foreknowledge
>    of the types of objects to be stacked.

I agree, I thought you were talking about unbound pointers; insufficient
semantics of unrestricted pointers was given.

>> but what about dynamically parameterized operations?  Ada has an address 
>> type applicable to function and task type addresses but this is 
>> implementation dependent and there is no defined typechecking mechanism 
>> for the subprogram parameter structure as there is with procedural 
>> variables.  Unbound pointers to functions have the same consequences.  
>> While tasks can allow procedural abstraction, better is a higher order 
>> construct such as procedural variables.
>
>     I have described in earlier articles mechanisms by which the
>     desired effects can be achieved in a more intuitive manner.
>
>     Please provide a concrete example in which the provided
>     mechanisms would prove inadequate.

Ok.  Here is an (uncommented fast prototype) example which could easily 
apply to Ada Adts as well.  This is similar to a project I once worked 
on here and similar constructs have appeared throughout the literature.
This does not however, give away any trade secrets.  There are many 
possibilities such as type inference of the generic parameters (ML), 
full static declarations of generics (current Ada), or dynamic checking 
via arbitrary polymorphism but these are superfluous to procedural 
variables.  For the Ada-9X extension, generic declarations would be used.
Now, ignoring interface boundaries below, SHORT_PRINT and LONG_PRINT can 
be statically typechecked with the declaration of PRINT_ELEMENT, a 
procedural variable.  For an Ada example, parameterize the visible 
operations with a stack type and add the usual interfaces and declarations.

--=========================================================================
-- class STACK
--
--    Provides a simple example of procedural variables.
--=========================================================================
class STACK (ELEMENT_TYPE, FCFS, LCLS, SHORT_PRINT, LONG_PRINT) is

  procedure INSERT (ELEMENT : ELEMENT_TYPE); -- INSERT (ELEMENT : polymorphic);
  procedure POP () return ELEMENT_TYPE;
  procedure MAKE_SHORT_PRINT ();
  procedure MAKE_LONG_PRINT ();
  procedure PRINT ();
  procedure MAKE_fCFS ()...
    ...

on entry  ...   -- called at block entry.
on exit   ...   -- called at block exit.
exception ...
private   ...
end STACK;

class body STACK is
    --
    -- PRINT_PROCEDURE_TYPE
    --
    --    A procedural type used to implement the print operation.
    --    These could be in the private part of the class.
    --
    type  PRINT_PROCEDURE_TYPE is procedure (ELEMENT : ELEMENT_TYPE) 
                                          := SHORT_PRINT;
    -- 
    -- PRINT_ELEMENT
    --
    --  A procedural variable invoked by the PRINT operation.
    --
    PRINT_ELEMENT            : PRINT_PROCEDURE_TYPE;

    type INTERNAL_STACK_TYPE is
                record
                        BODY : array ... of ELEMENT_TYPE;
                        TOP  : NATURAL;
                end record;

    INTERNAL_STACK           : INTERNAL_STACK_TYPE;

procedure PRINT is
    begin
        -- 
        -- For each element in the stack
        --      print element
        -- 
        for  INDEX in INTERNAL_STACK .BODY'FIRST .. INTERNAL_STACK .TOP  loop
            PRINT_ELEMENT (INTERNAL_STACK .BODY (INDEX));
        end loop;
    end insert;

--
-- MAKE_SHORT_PRINT
--
--    Set procedural instance variable PRINT_ELEMENT to parameter 
--    SHORT_PRINT so subsequent calls to PRINT by this instance 
--    will invoke SHORT_PRINT.   Could also use a generic 
--    subprogram parameter to supply a new print routine, or ...
--    Parameters SHORT_PRINT and LONG_PRINT will have to be assignment
--    compatible with type PRINT_PROCEDURE_TYPE;
--
procedure MAKE_SHORT_PRINT is
    begin
        PRINT_ELEMENT := SHORT_PRINT;
    end MAKE_SHORT_PRINT;

procedure MAKE_LONG_PRINT is
    begin
        PRINT_ELEMENT := LONG_PRINT;
    end MAKE_SHORT_PRINT;

...
end STACK;


Now, a call to print an instance of this class will at first result in 
invocation of the SHORT_PRINT parameter.  But programmers can make
subsequent calls to PRINT for this instance use long_print
through a call to MAKE_LONG_PRINT.  Each instance can parameterize
its print subprogram to output its data as desired.   Other tricks 
could be used but this method avoids the use of case statements and 
is a simple use of procedural variables.  It also provides static 
typechecking of the print operation since only procedures with the 
same parameter structure as PRINT_ELEMENT will match.

In more complicated examples parameterizable operations for each Adt 
instance could simplify the program considerably, such as by avoiding
nested case statements.

>>  Now set up your abstraction to provide a "current node" concept,
>>  along with operations like DESCEND_LEFT, DESCEND_RIGHT, and ASCEND.
>>  This can be implemented either via parent pointers or via a secret
>>  stack which holds the path of descent used to reach the current node.
> 
>> Yes this would work, but leaves programmers to build their own traversal 
>> routines.  My idea was to provide a mechanism allowing programmers to specify
>> a procedural invocation in a single, simple statement and have the Adt
>> select and carry out the operation implicitly.
>
>   But wasn't the basis of your argument the claim that the usual
>   preorder, postorder, and inorder traversal schemes may not be
>   enough?  The solution to this question is clearly to proceed
>   as I have described.  Perhaps you could clarify the problem
>   under consideration and the precise nature of your solution...
>

I hope the example above clarified the idea.  On the subject of
classes, another construct to change operations could be invented but
procedural variables provide a simple mechanism.


                                    Bob Hathaway
                                    rjh@purdue.edu