Re: unification

[stefan <stefan.tampe@spray.se>]

Hi,

This will give some ideas of how I prefere to handle
unification. I add a few extra instructions. And I do not
expect you to swallow that. But at least it is a beutiful 
idea.

Consider an example of a unifing matcher e.g.

(def f ((a _) a) 
       ((c b) b))

currently this compiles to

,x f

Disassembly of #<procedure f (arg121)>:

   0    (assert-nargs-ee/locals 25)
   2    (unify-init)
   3    (br :L142)                      ;; -> 19
   7    (local-ref 0)                   ;; `arg121'
   9    (unify-cons)
  10    (local-set 1)                   ;; `a'
  12    (unify-cons)
  13    (drop)
  14    (make-eol)                      ;; ()
  15    (unify-eq)
  16    (local-ref 1)                   ;; `a'
  18    (return)
  19    (br :L143)                      ;; -> 36
  23    (local-ref 0)                   ;; `arg121'
  25    (unify-cons)
  26    (local-set 3)                   ;; `c'
  28    (unify-cons)
  29    (local-set 2)                   ;; `b'
  31    (make-eol)                      ;; ()
  32    (unify-eq)
  33    (local-ref 2)                   ;; `b'
  35    (return)
  36    (toplevel-ref 1)                ;; `error'
  38    (object-ref 2)                  ;; "no match in f"
  40    (tail-call 1)

2 initiates and stors the (br :L142) location if we need to jump to the 
next match, then executes 7  (this can be made better)

7.  pushes argument
9.  do a unifying cons. essentially (push cdr) (push car)
    but the unifying flavor. if not a cons go to L142 and initiate
10. set a to the pushed car and pop the car
12. do another cons sequence
13. pop
14. push '() and then check if eq? with the cdr
then the resulting code is executed.

if there is a failure we jump to 19, initiates the new next jump as :L143
and continue as before.

here is the code for unify-cons in c.


#define UNIFY_MODDED				\
  {						\
  if(!unify_modded)				\
    unify_modded = (int) SCM_UNPACK(gp_newframe());	\
  }

#define UNIFY_FAIL				\
  {						\
    if(!unify_modded)				\
      gp_unwind(FI_TO_SCM(unify_modded));	\
    ip = match_next;				\
    sp = stack_next;				\
    NEXT;					\
  }

VM_DEFINE_INSTRUCTION(123, unify_cons, "unify-cons",0,0,0)
{
  gp_lookup(GP_GETREF(*sp));
  sp--;
  if(GP_CONS(gp_ret.ref))
    {
      PUSH(GP_UNREF(gp_ret.id + 3));
      PUSH(GP_UNREF(gp_ret.id + 1));
      NEXT;
    }	  
  if(gp_ret.val == 0) //variable
    {
      SCM *ref;
      UNIFY_MODDED;
      ref = GP_GETREF(gp_mk_cons());
      gp_set_ref(gp_ret.id,GP_UNREF(ref));
      PUSH(GP_UNREF(ref + 3));
      PUSH(GP_UNREF(ref + 1));	    
      NEXT;
    }
  
  UNIFY_FAIL;
}

Have fun
/Stefan