* Tasks


* Notes

Quick notes on discrimination net generation in PCL
 Paul Khuong, Thu 2007-06-14

File: src/pcl/methods.lisp

(defun generate-discrimination-net-internal  ; L1147
    (gf methods types methods-function test-fun type-function)
    ...)
  gf
  methods          (_ordered by precedence)_ list
  types            (partial -- nil defaults to t) list of known types 
                   for req args
  methods-function called to generate code for final method call
                   args: list of matching methods
                         (hd = method; tl = next method list
                          if input ordered)
                         list of known *pcl* types for req args
  test-function    called to generate code for tests
                   (eql, class-eq, class)
                   args: position (position of tested arg in
                           req args; as per arg-info-precedence)
                         type: type of test
                            (eql [x])
                            (class [class])
                            (class-eq [class])
                         true-value: sexp to splice for true branch
                        false-value:   "   "    "    "  false  "
  type-function    called to further interpret the type for a given
                   specialiser (as generated by type-from-specializer
                   for class, class-eq, eql or t, or from
                   specialiser-type otherwise). Example usage (IIUC),
                   would be, in sealing, to transform a class into
                   class-eq for leaf classes.

 specializer-type should be extensible, and it already is!
 g-d-n should call an extensible function (maybe once PCL has
 bootstrapped) in methods-function (this one might be covered by the
 MOP, actually...) and in test-function. It's not very useful to be
 able to pass custom specialiser types if we can't generate the
 corresponding tests.

 (do-column (p-tail contenders known-types) ...) ; L1153
  p-tail           list of position to generate the tests for,
                    in order of precedence.
  contenders       list of methods that still have to be discriminated
                    against
  known-types      alist of position -> inferred types (*pcl* types,
                    expressed via saut-foo'ed type operators) for
                    discriminated positions, mostly in reverse order
                    of arg precedence 
  
 do-column drives the generation of the discrimination net (strategy),
  following the order given by the arg precedence list -- it works
  horizontally across the columns of methods (position <->
  column). contenders is only carried around to pass to
  methods-function and do-methods, and aren't used in do-column per
  se. known-types is only computed to pass to methods-function.

  When p-tail is empty, we have the final list of applicable methods,
  and methods-function is called (known-types must be regenerated
  in argument position order).

  If the specialiser for the most specific contender is T (car of
  contenders, assuming the list is ordered), we can just skip that
  argument position (so recurse on the rest). If not, call do-method,
  which will traverse the column of methods (vertically, across
  methods) and call do-column back to work on the remaining arguments.

 (do-methods (p-tail contenders known-type winners known-types) ...) ; L1169
  p-tail          same as do-column. Not used in do-method per se,
                   except to know which specialiser to look at in
                   methods.
  contenders      same as do-column. do-methods culls methods from it
                   w/ the tests.
  known-type      inferred type so far for the current arg position
  winners         list of methods that are potentially applicable
                   (haven't been eliminated w/ tests)
  known-types     same as in do-column

  do-methods generates the section of the dnet corresponding to a
  given argument position (tactical), testing in method precedence
  order. This generates a BST for disjoint sets, but a linear search
  for `concentric' specialisers, where we have to test for A, B or C,
  and A subclass B subclass C. It might be a good idea to detect that
  case and generate a BST there too. However, we'd lose the advantage
  of having a fast path for more specialised methods, and, for short
  sequences, would present harder to predict patterns. MI would also
  present a slight amount of hair.

  If there are no more contenders, there isn't any test left to do on
  that column, so call do-column back to work on the other positions.
  
  If there are contenders left, the first method in the list is the
  most specialised one (hopefully), so take it, get the associated
  specialiser, and find the corresponding type.

  Use specializer-applicable-using-type-p and the inferred type so far
  (known-type) to find whether it's applicable (implied true) or if it
  might be applicable (not implied false). Since we test for most
  specific first, I expect *most* test will be implied away. However,
  multiple inheritance fscks things up a bit, so we can't skip
  everything else in `true' branches: we still have to generate the
  right next-methods-list. A test is only generated (by calling
  test-fun) if we can't infer the test's result away, obviously.

  do-if is used to generate the code for both the true branch (do-if
  t) and the else branch (do-if nil). do-if recurses (with do-methods)
  on the other candidates methods, refining known-type if the test
  wasn't inferred away (would be redundant). In the true branch, the
  method corresponding to the tests is added to (the tail of) the
  winners, the known applicable methods. Since we only add to
  winners on successful tests, we never have to remove methods
  from winners (types are refined, never contradicted). OR
  specialisers might present a problem if the input methods aren't
  sorted here. winners respects the same relative order as the input
  list of methods.

(defun generate-discrimination-net  ; L1040
   (generic-function methods types sorted-p) ...) 
 ... is an ugly hack.
 
 gf, methods, types are the same as in g-d-n-internal
 sorted-p indicates whether the input methods are sorted. If they are
 not, g-d-n will attempt to sort them in its methods-function.
 Note that the ordering still affects the way the dnet is generated --
 we might be able to use that to generate a BST on concentric class
 specialisers.

 The methods-function passed to g-d-n-i simply outputs a (methods
 [sorted applicable methods] [known *pcl* types for required args]) form
 if sorted-p (input methods list sorted), or if it managed to sort
 them; (unordered-methods ...) otherwise. This might be a good place
 to allow extension, but the MOP might already offer the right tools
 for what would be possible here.

 test-fun is where the hair's at! It looks at the *already generated*
 code in true-value and false-value to generate its own test. mcase
 and scase are the same (mcase macroexpands to scase) gensym-less case
 macros. mcase indicates that the consequent forms are all
 methods/unordered-methods forms, while scase's lead to (some) more
 specialiser tests.

 When the type test is an eql-test, generate an mcase/scase as
 appropriate, collapsing cases together (from false-value) in a single
 case form if possible. Cases can be collapsed if the current test is
 an mcase (the test is an eql, the true-value a [unordered-]methods
 form and the false-value is either a methods form or an mcase) and
 the false-value is actually a case. In that case, all the eql tests
 are on the same argument, the specialised one with the least
 precedence (easy proof by induction on the # of cases in the mcase).
 Ironically, this is all for naught, since PCL compiles its mcase to
 conds. Finally, normal class tests (class/class-eq specializers) are
 compiled into straightforward if.

 This would *definitely* be a good place to call an extensible
 function (in conjunction with the already existing user-defined
 specialisers). This, or type-function should probably have access to
 known-type in order to further specialise tests (e.g. to transform a
 class test into a class-eq one for sealing).

 (types aren't frobbed with)

Plans for a rewrite of g-d-n(-i):
 Generate an abstract search tree in a first pass, using inferred
 information to specialise/rewrite it (probably using some sort of
 simple peephole-like extensible tree rewriting function). This would
 take care of the ugly and brittle mcase/scase/methods form stuff.
 Only then straightforwardly generate the corresponding code. To
 achieve that, we probably need to pass known-type around more in
 g-d-n-i and make the inference machinery,
 specializer-applicable-using-type-p (L1610) extensible. The rest can
 happen in g-d-n, in order to keep the interface to g-d-n-i as close
 to the original as possible... I'm not sure that is actually possible
 to achieve if we switch to the two-pass system. 

 Argument precedence computation probably also wants to be extensible:
 this would make, e.g., pattern matching, simpler and closer to
 CLOS (aside: seeing lists as conses probably breaks this a bit).