Arc Forumnew | comments | leaders | submitlogin
3 points by stefano 6016 days ago | link | parent

The CLOS solution is pretty similar to the Ruby solution: it checks the type passed to the function and dispatch to the correct function. The big difference is that CLOS looks at all the arguments, while Ruby only at the first argument (the object). The CLOS approach seems to me the best to solve the problem, but I think that applying it to functions as basic as car would kill performance without a really good optimizer.


3 points by almkglor 6016 days ago | link

> The CLOS solution is pretty similar to the Ruby solution: it checks the type passed to the function and dispatch to the correct function. The big difference is that CLOS looks at all the arguments, while Ruby only at the first argument (the object)

IMO the difference is big enough for CLOS Way != Ruby Way. ^^

Still, I wonder - how does CLOS implement this? How about for variadic functions?

> but I think that applying it to functions as basic as car would kill performance without a really good optimizer.

Hmm. I've been trying to grok through dynamic dispatching speedup techniques - the Sun Self papers are pretty good, Sun's index doesn't have the papers themselves but you can ask Google for them.

-----

2 points by stefano 6015 days ago | link

> Still, I wonder - how does CLOS implement this?

I think that for every method with the same name an hash table indexed on the types of the argument is created, and when the method is called, a lookup is made on the table.

> Hmm. I've been trying to grok through dynamic dispatching speedup techniques - the Sun Self papers are pretty good, Sun's index doesn't have the papers themselves but you can ask Google for them.

I've found those papers in the past (a few weeks ago), but I've never found the will to read them, they are written for people already in the compilers' world and I'm still learning the basics about compilers. BTW, a good type inferencer + a good function inliner could solve the problem, but I wouldn't know even where to start to implement them :(.

-----

2 points by almkglor 6015 days ago | link

The gist of the papers are mostly this:

Use a "Polymorphic Inline Cache" (PIC). Basically if a piece of code could call several different methods, we figure out which one it is, then we create a copy of the calling function which does the type checking at the top and specialize all method calls to that type:

  (defm method ((t n my-type))
    (my-type::method n))
  (defm method ((t n your-type))
    (your-type::method n))
  (defm other-meth ((t n my-type))
    (my-type::other-meth n))
  (defm other-meth ((t n your-type))
    (your-type::other-meth n))

  (def general-function (n)
    (+ (method n) (other-meth n)))

  (general-function (your-type-creator 42))
  ===>
    (do
      (def general-function (n)
        (if (isa n 'your-type)
          (+ (your-type::method n) (your-type::other-meth n))
          (+ (method n) (other-meth n))))
      (general-function (your-type-creator 42)))
Everything else in the papers that go beyond the PIC is mostly about debugging and making the PIC lazy.

Edit:

Okay, I've been thinking. Basically the call* table is about specializing on 'apply, and we might think of 'defcall as:

  (defcall type (val . params)
    (code))
  ==>
  (defm apply ((t val type) . params)
    (code))
Could we possibly generalize this at the language level and make a PIC, say in arc2c/SNAP?

-----

1 point by stefano 6014 days ago | link

To do the optimization when we see

  (general-function (your-type-creator 42))
we need a type inferencer to discover the return type of your-type-creator. The cache should also be able to change. For example I could write:

(general-function (your-type-creator 42))

(set your-type-creator another-type-creator)

(general-function (your-type-creator 42))

Now the optimization doesn't work if the cache doesn't change. This seems a rare case, though, and it's useless to optimize rare cases.

-----

1 point by almkglor 6014 days ago | link

Actually we don't: general-function is actually defined this way:

  (with (PIC (table) ;init empty table
         num-calls 0
         orig-fn
         (fn (n)
           (+ (method n) (other-meth n))))
    (def general-function (n)
      ((aif
         ; don't infer type: just look at the runtime type
         (PIC:type n)
            it
         (is optimization-trigger-level** (++ num-calls))
            (do (= num-calls 0)
                (= (PIC:type n)
                   (optimize* orig-fn (type n))))
            orig-fn)
        n)))
Basically s/type inference/just look at it directly/

-----

1 point by eds 6015 days ago | link

> Still, I wonder - how does CLOS implement this? How about for variadic functions?

I don't think CLOS lets you check types on &rest, &optional, or &key parameters. So you couldn't use CLOS for the current behavior of '+.

Also note that CLOS only works on methods with "congruent lambda lists", that is, methods with the same number of required, optional, and keyword arguments. So you can't have

  (defmethod foo ((a type-a)) ...)
  (defmethod foo ((b type-b) &optional (c ...)) ...)

-----

1 point by almkglor 6015 days ago | link

ah, I see. So I suppose this greatly simplifies things then.

Hmm. This certainly seems easier to hack into arc. We could have each method start with a generic function whose lambda list we have to match.

As an aside, currently the base of Arc lambda lists are simply &rest parameters (i.e. optional parameters are converted into rest parameters with destructuring). Should we match on the plain rest parameters or should we properly support optionals?

-----