[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Recursive slot specialization proposal

This note proposes an extension to the defmethod mechanism of CLOS to
allow method specialization to refer (recursively) to the structure of
slot values.  This idiom has arisen in the course of translating an ML
program into a dialect of lisp which exploits the "HOPE-style" pattern
matching facilities of ML.

In ML, a concrete type is given by specifying functions which
construct its elements.  For example, to say that the new type
"my_boolean" is built from the two constants "my_true" and "my_false"
one would write

	type  my_bool = my_true | my_false;;

[People familiar with ML will note that this is non-standard syntax.
It comes from the Formel implementation, which is not the same as
standard ML.  Standard ML is better!]  Similarly, to say that lists
are built out of my_nil and my_cons one writes:

	rectype * my_list = my_nil | my_cons of * # * my_list ;;

[The * is a prefix "type argument" indicating that my_list is a
polymorphic type.]  When types are defined in this manner it is
possible to define functions by cases on the constructors used.  For
example,

	is_empty = fun  my_nil . my_true
	 	   |	my_cons (_) . my_false
	;;   

and 

	hd_is_true = fun my_cons (my_true,_) . my_true
	             |   _ . my_false 
	;;

[The _ character is a "wildcard" pattern---it matches anything.]

In our translation into CLOS we have used classes for the "concrete
types" and subclasses with appropriate slot arguments to represent the
constructors and their arguments.  In this idiom it is easy to use the
defmethod construct to define functions such as "is_empty" above, but it
is less natural to define functions which exploit the recursive
structure of patterns such as "head_is_true".

Our response to this problem has been to provide a quick and
temporary interpreted solution.  We introduce a few new constructs
which we think make the code easy to read.  Then we expand them
at load time into if-then-else chains, and don't use defmethod
at all.  There are a few simple things we could do to shorten
the if-then-else chains, and we could produce defmethods to do
the split on top-level structure.  But the most efficient,
clean, and compatible solution would be to reach in and change
defmethod so it can handle arbitrarily deep trees of patterns
to be matched against actual parameter instances.  Since we
don't have the time to do that ourselves, we are advertising
this idea to see what comments we get.

The defmethod construct has the following structure (and more):
    (defmethod <fn_name> ( <pattern_list> ) <body>)
where

    <pattern_list> ::= <CLOS pattern>
		   |   <CLOS pattern> <pattern_list>.

The existing pattern grammar is:

    <CLOS pattern> ::= <var>
		   |   (<var> <class_name>)
		   |   (<var> (eql <form>))

Here is the pattern grammar we have in mind:

    <CLOS pattern> ::= <var>
		   |   (eql <form>)
		   |   (as <var> <CLOS pattern>)
		   |   (<class_name> { <slot_name> <CLOS pattern> }* )

The meaning of a <CLOS pattern> is:
  1. <Var> matches any object.
     As a result of the match, <var> will be bound to the object.
  2. (Eql <form>) matches only those objects which are "eql" in
     the sense of Common LISP to the value of <form>, evaluated in
     the context of any bindings established by an enclosing level
     of pattern matching.
  3. (As <var> <CLOS_pattern>) matches any object which matches
     <CLOS_pattern>.  In case of success, <var> will be bound to
     the matching object.
  4. (<class_name> { <slot_name> <CLOS_pattern> }* ) matches any object
     of class <class_name>, as determined by the standard predicate for
     <class_name>, as long as that object, in each slot specified
     as <slot_name>, has a value matching the corresponding <CLOS_pattern>.
     In case of a match, the bindings established by the subpatterns
     will hold for the whole pattern.

The main feature of this grammar is the recursion.  A secondary
feature is the role of the class name, which we put first because we
treat the class name as a type constructor.  In fact, to improve on
the make-instance syntax we add

    <form> ::= (<class_name> ( { (<slot_name> <form>) }* ))

to the grammar for forms so that the class of the constructed
instance is more prominent and instance construction is less obtrusive.

Here are two code enclosures, an ML function and its Lisp translation.
The function takes a term of a version of the lambda calculus
and returns its string representation.  Since we don't have a
modified defmethod, in the Lisp code we use the following idiom:
   (defun-pattern <fn_name> ( <arg_name_list> )
     (pattern-let <expr, usually arg_name>
	((<CLOS pattern> <action>)
	 ... ))).
This is interpreted to mean
   1. Compute <expr>, then match it against <CLOS pattern>s
      from first to last, taking the first match that succeeds.
   2. Evaluate the corresponding <action> in an environment
      having the bindings established during the match.

[disclaimer:  this code was somewhat "simplified" by hand.  It
was derived from running code...]

let unparse environment bind preterm = rec_unparse bind preterm 
	whererec rec_unparse bind =
  fun	free_var s . Id_to_string s
  |     context_var s . Id_to_string s
  |	bound_var y . nth_boundvar y bind
  |	primitive_constant X . (Primitive_constant_to_string X)
  |	ap (X, Y) . (Ap_to_string (rec_unparse bind X)
				  (rec_unparse bind Y))
  |	ap (ap ( (primitive_constant phi),
                 X),
            lambda(binder_name,Y)) .		% \binder_name:X.Y %
	let name = new_name (Id_or_int_to_string binder_name) bind
	in (Lambda_form_to_string
              name
              (rec_unparse bind X)
              (rec_unparse (name.bind) Y))
  |	ap (ap ( (primitive_constant all),
                 X),
            lambda(binder_name,Y)) .		% forall binder_name:X.Y %
	let name = new_name (Id_or_int_to_string binder_name) bind
	in (Generalization_to_string name
				     (rec_unparse bind X)
				     (rec_unparse (name . bind) Y))
  |     ap (ap (ap (primitive_constant either, X),
                lambda(binder_name,Y)),
            Z) .				% (either binder_name:X.Y) Z %
        (Ap_of_fn_or_gen_to_string
             (rec_unparse bind
                          (ap (ap (primitive_constant either, X),
                               lambda (binder_name, Y))) )
	     (rec_unparse bind Z))
  |	lambda(binder_name,X) . 
		let name = new_name (Id_or_int_to_string binder_name) bind
		in (Untyped_lambda_form_to_string
                        name
			(rec_unparse (name.bind) X))
  |	abbrev_instance(id,ilist,prelist) . error `action omitted`
  |	abbrev_arg n . Abbrev_arg_to_string n
  |	match_var s . Match_var_to_string s ;;

;;; unparse
;;;   Return string representation of a preterm.
;;;
(defun-pattern unparse (env bind preT)
  (pattern-let preT
    (((free_var id s) (Id_to_string s))
     ((context_var id s) (Id_to_string s))
     ((bound_var deBruijn_index y) (nth_boundvar y bind))
     ((primitive_constant p_constant c) (Primitive_constant_to_string c))
     ((ap fn M arg N)
      (Ap-to-string (unparse env bind M) (unparse env bind N)) )
     ((ap fn (ap fn (primitive_constant p_constant phi)
		 arg A)
	  arg (lambda_form binder x
			   body b))	; \ x : A . b
      (let ((name (new_name (Id_or_int_to_string x) bind)))
	(Lambda_form-to-string name
			       (unparse env bind A)
			       (unparse env (name . bind) b) )))
     ((ap fn (ap fn (primitive_constant p_constant all)
		 arg A)
	  arg (lambda_form binder x
			   body b))	; forall x : A . b
      (let ((name (new_name (Id_or_int_to_string x) bind)))
	(Generalization-to-string name
			       (unparse env bind A)
			       (unparse env (name . bind) b) )))
     ((ap fn (ap fn (ap fn (primitive_constant p_constant either)
			arg A)
		 arg (lambda_form binder x
				  body b))
	  arg N)			; (either x : A . b) N
      (Ap_of_fn_or_gen-to-string x A b N))
     ((lambda_form binder x
		   body b)
      (Untyped_lambda_form-to-string x b))
     ((abbrev_instance id name
		       binding_vars vars
		       actuals terms)
      ;; [ name < vars > terms ]
      (Abbrev_instance-to-string env bind name vars terms))
     ((abbrev_arg arg_num n_minus_one)
      (Abbrev_arg-to-string (princ-to-string n_minus_one)))
     ((match_var id s) (Match_var-to-string s)) )) )

We have been using the recursive CLOS patterns in our code
and have been finding them quite useful.  We would like to know
how much interest there is in this kind of extension.

We should also add that we are new to the commonloops/CLOS community.
If these issues have been discussed before please let us know
politely.

Thanks,

	Bruce Esrig & Jim Hook
	esrig%oravax.uucp@svax.cs.cornell.edu