home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / object / 3301 < prev    next >
Encoding:
Text File  |  1992-08-22  |  6.1 KB  |  189 lines
  1. Newsgroups: comp.object
  2. Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!mips!mips!munnari.oz.au!metro!graham
  3. From: graham@maths.su.oz.au (Graham Matthews)
  4. Subject: Method Dispatching
  5. Message-ID: <graham.714545782@dumas>
  6. Sender: graham@maths.su.oz.au
  7. Nntp-Posting-Host: dumas.maths.su.oz.au
  8. Organization: School of Mathematics and Statistics, University of Sydney
  9. Date: Sun, 23 Aug 1992 04:56:22 GMT
  10. Lines: 177
  11.  
  12. I have recently been working on some object based extensions 
  13. to an algebraic programming language I have implemented.
  14. I decided to do an example - to write a class for the Rational 
  15. field and its elements. This article talks of a problem I
  16. have encountered in doing so - a problem which is perhaps 
  17. pervasive in object oriented programming, even if not explicitly
  18. so.
  19.  
  20. Lets say we want to represent our rational field elements
  21. as pairs <a,b>, a giving the enumerator, b the denominator
  22. in the standard way.
  23.  
  24. Say we want to implement rational multiplication, and the 
  25. ability to index a rational to extract the enumerator and
  26. denominator. i.e: we want to be able to write
  27.  
  28.     a * b
  29.  
  30. where a and b are elements of the rational field, and
  31.  
  32.     a[1]
  33.     a[2]
  34.  
  35. where a is an element of the rational field.
  36.  
  37. So we have two generic "function" (imagine operators as
  38. functions) signatures,
  39.  
  40.     *    :    ratelt, ratelt -> ratelt
  41.     []    :    ratelt, integer -> integer
  42.  
  43. So now I envisage writing a class (type) to implement these 
  44. function signatures. So I write,
  45.  
  46.     class ratelt
  47.  
  48.         representation: Tuple< integer, integer >;
  49.  
  50.         * := 
  51.             function( a, b )
  52.                 return < a[1] * b[1], a[2] * b[2] >;
  53.             end function;
  54.  
  55.         [] :=
  56.             function( a, i )
  57.                 return a[i];
  58.             end function;
  59.  
  60.     end class;
  61.  
  62. NOTE: 
  63. i) the "representation : Tuple.." is meant to indicate how
  64. instances of this class are to be represented. The problem
  65. of how to indicate this forms the basis of my problem, so
  66. read on.
  67. ii) the notation <..> constructs a tuple.
  68. iii) I have cast the example in terms of generic functions
  69. a la CLOS, but the examples could be easily re-written
  70. in other notations and my point would remain the same.
  71.  
  72. Ok so far this seems fine, but there is a problem with it
  73. which is demonstrated by the following example. Say I now
  74. have two rational field elements, a and b, and I write,
  75.  
  76.     temp := a * b;
  77.  
  78. Lets trace what happens here :-
  79.  
  80. a) the function binder takes the types of a and b and looks for
  81. a function with the name "*" and the argument specification
  82. "ratelt, ratelt". The function binder returns successfully
  83. with the function "*" in class ratelt as the target function.
  84.  
  85. b) function "*" in class ratelt is invoked. The first thing it
  86. does is the operation "a[1]".
  87.  
  88. c) the function binder takes the types of a and 1 and looks for
  89. a function with the name "[]" and the argument specification
  90. "ratelt, integer". The function binder returns successfully with
  91. the function "[]" in class ratelt as the target function.
  92.  
  93. d) the function "[]" in class ratelt is invoked. The first thing
  94. it does is the operation "a[i]".
  95.  
  96. e) the function binder takes the types of a and 1 and looks for
  97. a function with the name "[]" and the argument specification
  98. "ratelt, integer". The function binder returns successfully with
  99. the function "[]" in class ratelt as the target function.
  100.  
  101. f) the function "[]" in class ratelt is invoked. The first thing
  102. it does is the operation "a[i]".
  103.  
  104. ...
  105.  
  106. NOTE the infinite loop here.
  107.  
  108. Now this loop is caused by the fact that in step c) what we really
  109. want to do is use our *representation* and look for a function with
  110. the name "[]" and argument specification "tuple, integer"! The
  111. function binder would pick up tuple indexing as system supplied
  112. and at just do it (the system I work with supplies tuples as a
  113. fundamental data structure).
  114.  
  115. So the question is how can the function binder know when it is time
  116. to use the representation and forget the typing information. The
  117. answer is not at all clear. Clearly you don't want to do that all the
  118. time as otherwise the original "temp := a * b" would never get to
  119. the function "*" in class ratelt. If we used the representation
  120. immediatley we would try to multiply two tuples. At some point in
  121. this lookup chain we want to change to the representation and forget
  122. the type. Where is this point?
  123.  
  124. You may ask how this problem is handled in an object oriented language
  125. and the answer is that it is left to the programmer, although not 
  126. obviously so. A programmer would write the ratelt class as follows,
  127.  
  128.     class ratelt
  129.  
  130.         val : Tuple< integer, integer >;
  131.  
  132.         * := 
  133.             function( a, b )
  134.                 return < a[1] * b[1], a[2] * b[2] >;
  135.             end function;
  136.  
  137.         [] :=
  138.             function( a, i )
  139.                 return a.val[i];
  140.             end function;
  141.  
  142.     end class;
  143.  
  144. NOTE: once again the notation for "val : Tuple..." will vary from
  145. language to language but my point remains the same.
  146.  
  147. In the "[]" function the programmer uses "a.val" instead
  148. of "a". "val" is basically a name for the representation of a ratelt
  149. and the programmer is forced to explicitly note where he/she wishes
  150. to start using the representation rather than the type information
  151. (it is not of course presented in such terms in the object oriented 
  152. literature, but this is what is happening).
  153.  
  154. While I do not like forcing the programmer to deal with the change 
  155. to a representation based lookup I see no way to avoid it as I cannot
  156. see an (efficient) algorithm whereby the system can do it automatically.
  157. I can see an inefficient algorithm I think.
  158.  
  159. You may wonder why I am asking this question, well I am asking it
  160. because I am interested in partial re-use of class methods. I really
  161. want to write my ratelt class as follows,
  162.  
  163.     class ratelt
  164.  
  165.         representation : Tuple< integer, integer >;
  166.  
  167.         * := 
  168.             function( a, b )
  169.                 return < a[1] * b[1], a[2] * b[2] >;
  170.             end function;
  171.  
  172.         [] := given by Tuple.[]
  173.  
  174.     end class;
  175.  
  176. Or something like that (ideally in fact I just want the system
  177. to figure out how [] is implemented since it knows the element
  178. representation). I want to re-use tuple.[] much more obviously 
  179. than having to have a name for the representation (ie. a variable
  180. in the class) and go through that.
  181.     
  182. Comments?
  183.  
  184. graham
  185. --
  186. Graham Matthews                 And it's true we are immune
  187. Pure Math, Uni.Sydney, Oz       When fact is fiction and T.V. is reality
  188. graham@maths.su.oz.au
  189.