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

The source of this problem is not only in chaining itself: redefining standard functions will almost always lead to problems when distinct libraries redefine the same function. That's why other languages have module systems. Moreover, another problem arises from this chaining: performance. The more the chain is long, the more function calls it will need to get the original behavior. Were you thinking about a multimethod dispatch such that of CLOS?


3 points by almkglor 6013 days ago | link

> The source of this problem is not only in chaining itself: redefining standard functions will almost always lead to problems when distinct libraries redefine the same function.

But this should be supported. For instance, in C++, you can redefine the "standard function" operator+ :

  Foo something(Foo a, Foo b){
      return a + b;
  }
Or in Ruby, you can redefine the "standard function" each:

  a = Foo.new()
  a.each{ |i|
    puts i
  }
C++ does it by strict static typing, while Ruby does it by attaching to the object. Neither way feels very Arcish; what is a better Arc solution?

> Were you thinking about a multimethod dispatch such that of CLOS?

Possibly, if we can hack this into Arc somehow.

-----

3 points by stefano 6013 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). 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 6013 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 6012 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 6011 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 6011 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 6010 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 6011 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 6011 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?

-----