dynamic method look-up?

dynamic method look-up?

[Eijiro Sumii]

Hello, everyone.  I'm sorry that I don't write French version.  I know
very little about French language.  (Though I'm not very good at
English, either.)

I have a question about the implementation of method invocation in
ocaml.  Whenever I compile a tiny program like the following one by
ocamlopt with `-S' option (on any platform),

    let invoke_foo obj = obj # foo;;
  	
    class c1 () =
      method foo = 123
    end;;
    
    class c2 () =
      method foo = 456
      method bar = "abc"
    end;;
    
    let o1 = new c1 ();;
    let o2 = new c2 ();;
    
    print_int ((invoke_foo o1) + (invoke_foo o2));;
    print_newline ();;

the assembly code generated by ocamlopt seems to contain an ascii
string "foo" and to use it at runtime.  Is the method `foo'
dynamically looked up before its invocation?  If it is, isn't there a
more efficient way than dynamic method look-up to implement method
invocation?  (something like index passing in Ohori's polymorphic
record calculus [1], or implicitly generating and passing some
fuctions like a coercion function and a put function in Hofmann &
Pierce's positive subtyping [2])

// Eijiro Sumii <sumii@yl.is.s.u-tokyo.ac.jp>
// 
// Kobayashi Laboratory, Department of Information Science,
// Faculty of Science, University of Tokyo

[1] Atsushi Ohori. A polymorphic record calculus and its
compilation. ACM Transactions on Programming Languages and Systems,
Vol 17, No 6, Pages 844-895.

[2] @inproceedings   (HofmannPierce94a,
author       =   "Martin Hofmann and Benjamin Pierce" ,
title        =   "Positive Subtyping",
booktitle    =   "Proceedings of Twenty-Second Annual ACM Symposium on
                  Principles of Programming Languages",
year         =   "1995" ,
month        =   jan,
publisher    =   "ACM" ,
pages        =   "186--197",
note         =   "Full version in {\em Information and Computation}, 
                  volume 126, number 1, April 1996. 
                  Also available as University of Edinburgh technical
                  report ECS-LFCS-94-303, September 1994."
)

Re: dynamic method look-up?

[Didier Remy]

> the assembly code generated by ocamlopt seems to contain an ascii
> string "foo" and to use it at runtime.  

Yes it does.  But the string "foo" is only used at load time to create some
runtime tables.

> Is the method `foo' dynamically looked up before its invocation?  

1. The offset at which the method is stored is not always known statically
(this is difficult with multiple inheritance and separate compilation).

2. However, there are just a few (fix number) of indirections through a
dictionary to find the exact code to execute. (This is nothing like
searching for the method in an A-list.)

> If it is, isn't there a
> more efficient way than dynamic method look-up to implement method
> invocation?  

The actual schema is not inefficient.  It could still be improved using
static analyses to find methods calls to objects whose classes are
statically known (as is currently done for functions).

> (something like index passing in Ohori's polymorphic
> record calculus [1], 

The compilation method of [1] relies on the types of records to uniquely
determine their representation.  It does not apply to Ocaml that also allows
subtyping.  Subtyping changes the types of objects without changing their
representation in a way that contradicts the previous condition.  Roughtly,
({a = 1; b = 2} :> {a : int}) has the same time as {a = 1} but should
clearly have a different representation.

Indeed, it is important that subtyping behaves as the identity to keep
sharing, since in particular objects may have mutable fields. 

> or implicitly generating and passing some
> fuctions like a coercion function and a put function in Hofmann &
> Pierce's positive subtyping [2])

I am not sure that [2] can help here.  Moreover, we just do not want to pass
coercion functions, which would destroy sharing.

    Didier.