Description

certik

opened on Aug 11, 2024

Issue body actions

We should implement runtime polymorphism, using virtual function tables. Here is the simplest example:

# Base class
class A:
    def myprint():
        print("A")

def f(a: A):
    a.myprint()

The function f accepts the base class and calls the virtual function myprint. This will get fully compiled to ASR and to LLVM, without knowing any subclasses. Then later we call it like this:

# subclass
class B(A):
    def myprint():
        print("B")

def main():
    a: A = A()
    b: B = B()
    c: B = B()
    f(a)
    f(b)
    f(c)

The call f(a) will print "A", the call f(b) will print "B".

Steps to get it implemented:

• Work on a branch
• Add a virtual flag to ASR's methods. Mark every method as virtual in LPython.
• In the LLVM backend, create a virtual function table, and call myprint via the table in the function f
• The class instantiation a = A() will create and populate the virtual function table
• To get started, just create the virtual function table every time, so once for b and another time for c. Then later as an optimization we will share it.

Note: the instances c and b both share the same virtual function table. The compiler will create the virtual function table just once for the type B. Then all instances (b and c above) just have a pointer to this same (shared) table.

To be figured out: it is not clear when this virtual function table is created. One option is at start time of the program. Another option is at the first instantiation of B into b, and reused for the second instantiation (c).

Activity

1. certik commented on Aug 11, 2024

   

   certik

   on Aug 11, 2024

   ContributorAuthor

   More actions

   Let's explore how to do it via an ASR -> ASR pass. For that, the input ASR is with methods with the virtual flag. The output ASR must have explicit virtual function table and calls into it. Let's first write an example that compiles today, that implements the above example. Roughly:

   # Base class
   class A:
       def myprint2():
           print("A")
       def myprint():
           print("A")
   
   def f(a: A):
       a.myprint()
   
   # subclass
   class B(A):
       def myprint():
           print("B")
   
   def main():
       a: A = A()
       b: B = B()
       c: B = B()
       f(a)
       f(b)
       f(c)
   
   main()

   Output:

   # Base class
   class A:
       def __init__(self):
           self.VMT = [Pointer to A.myprint2, Pointer to A.myprint]
       def myprint2():
           print("A")
       def myprint():
           print("A")
   
   def f(a: A):
       a.VMT[1](a)
   
   # subclass
   class B(A):
       def __init__(self):
           super(self).VMT = [Pointer to A.myprint2, Pointer to B.myprint]
       def myprint():
           print("B")
   
   def main():
       a: A = A()
       b: B = B()
       c: B = B()
       f(a)
       f(b)
       f(c)
   
   main()

   If this is not fully clear, then let's start with C. Implement the "Output" in C, with function pointers.
2. certik commented on Aug 11, 2024

   

   certik

   on Aug 11, 2024

   ContributorAuthor

   More actions

   Let's write this as an ASR->ASR pass that takes the "Input" above and converts it to the "Output" above.

   An ASR->ASR pass will be easy to debug, we just print it as Python or Fortran code and can easily see how the compiler implements the feature. This keeps the door open to later do a different ASR pass: that implements compile time polymorphism where the subclass is known. Also there might be other optimizations possible, since we implement all this at ASR level: for example all kinds of function inlining and other simplifications if we know things at compile time.

   Notes: later we can merge this ASR->ASR pass with the LLVM backend. This will speedup compilation, but it will make the backend more complex, so let's do that later, if we want to. It will make it harder to debug. It might also disallow some ASR optimizations, since we will only be implementing it in the backend.

   We can also consider merging this ASR->ASR pass with the frontend (with the AST->ASR pass), but that will mean we can't represent polymorphism in ASR directly at higher level, the AST->ASR would already lower this high level feature. And that means that it would close the door to later add compile time polymorphism for cases where the compiler knows the subclass. So I would not do that.

Issue actions