Monday, January 31, 2011

simple approach to OO and exploding equirecursive types

While trying to port the graph algorithms (Kosaraju's algorithm / topological sort) I got to a point where I really wanted some imperative set/map objects, so I combined a 'class' using alists (for map) and lists (for set) with a few 'methods' put into records.

After playing with it for a while, I found a fairly neat way to do method calls and object layouts:

(define (set-class)

  (define (in self x)
    (let loop ((l self.list))
      (match l with
        () -> #f
        (hd . tl) -> (if (eq? hd x)
                         #t
                         (loop tl)))))
  (define (add self x)
    (if (self::in x)
        #u
        (set! self.list (list:cons x self.list))))
  
  (define (get self)
    self.list)

  (let ((methods {in=in add=add get=get}))
    (define (new l)
      {o=methods list=l})
    new
    ))

This leads to an efficient object layout very similar to Python's: one slot identifies the object type, the other slots hold instance variables.  To support this, I added a reader hack that translates


(var::method arg0)

into

(var.o.method var arg0)

The result is something that I'm pretty sure will act just like Python's duck typing... for example a generic output function may call the 'write' method on an object, and its type will reflect that need: for a write method of a particular signature.  Instead of 'o' I'd probably use a slot name like '__methods__'... this suggests standard repr/str interfaces, and the other duck-typed protocols that Python makes such good use of.

Pretty cool, huh?

Well, as soon as I tried actually using this code, the inferencer fell to its knees. I'm not kidding. It went from a 30 second compile to a 20 minute compile, eating up over a GB of memory.  Hmmmm... looks like my quick-and-easy implementation of μ-types has problems, surprise.  I think I was 'asking for it' by calling each method with a 'self' argument... each method call has to unify the object type twice.  And storing objects inside of other objects doesn't help, either.

Back to the textbook.  I'm hoping that reading this paper again will help.

1 comment:

  1. Actually, it didn't require a reader hack, just a 'manual' macro. And I would probably add some more syntactic sugar for the class definition, getting rid of the manual record construction in there.

    ReplyDelete