defmacro and destructuring-bind Improvements

Efficiency

Checking the Argument List

Problem

In the following code

(declaim (ftype (function () (cons t (cons t (cons t null)))) g))
(defun g ()
  (list 1 2 3))

(defun f ()
  (let ((z (g)))
    #+no (setf (cdr z) nil)
    (destructuring-bind (a b c) z
      (values a b c))))

it can be known at compile time that z will always be a list of length 3. However, the (destructuring-bing (a b c) …) above macro-expand s to

(LET ((#:WHOLE13940 Z))
  (DECLARE (TYPE LIST #:WHOLE13940))
  (LET* ()
    (DECLARE (SB-EXT:MUFFLE-CONDITIONS SB-EXT:CODE-DELETION-NOTE))
    (LET ((#:ARGS13942 #:WHOLE13940))
      (UNLESS (SB-INT:PROPER-LIST-OF-LENGTH-P #:ARGS13942 3 3)
        (SB-KERNEL::ARG-COUNT-ERROR 'DESTRUCTURING-BIND 'NIL #:ARGS13942
                                    '(A B C) 3 3)))
    (LET* ((A (CAR #:WHOLE13940))
           (B (CAR (CDR #:WHOLE13940)))
           (C (CAR (CDR (CDR #:WHOLE13940)))))
      (VALUES A B C))))

which checks the argument list z at runtime. Note that the runtime check cannot be avoid if the possibility of z being mutated cannot be rule out. This would be the case if the (setf (cdr z) nil) fragment was not disabled.

Proposed Improvement

The proposed improvement consists in replacing the unconditional runtime check with a carefully designed runtime check that can be elided at compile time under certain circumstances.

In the above example, the "carefully designed" check would be of the form

(LET ((#:WHOLE13940 Z))
  (DECLARE (TYPE LIST #:WHOLE13940))
  (LET ((#:CHECKED13941 (check-proper-list-of-length #:WHOLE13940 3 3)))
    …))

The carefully designed part is that #:WHOLE13940 is only used once: in the check-proper-list-of-length call 1. This fact can be exploited by a deftransform for check-proper-list-of-length to conclude that WHOLE13940 is not mutated and that its derived type can be trusted. In certain cases, this type information can be used to perform the check at compile time and elide the check-proper-list-of-length call.

The improvement requires changes to the defmacro machinery due to the way argument checks are currently performed (can be seen in macro-expansion above).

This is closely related to Bug 327537 and the proposed solution would allow detecting some argument count errors in the check-proper-list-of-length deftransform at compile time.

Traversing the Argument List

Problem

With current parse-defmacro, the following code

(destructuring-bind (a b c d e) '(1 2 3 4 5)
  (values a b c d e))

macro-expand s to

(LET ((#:WHOLE13937 '(1 2 3 4 5)))
  (DECLARE (TYPE LIST #:WHOLE13937))
  (LET* ()
    (DECLARE (SB-EXT:MUFFLE-CONDITIONS SB-EXT:CODE-DELETION-NOTE))
    (LET ((#:ARGS13939 #:WHOLE13937))
      (UNLESS (SB-INT:PROPER-LIST-OF-LENGTH-P #:ARGS13939 5 5)
        (SB-KERNEL::ARG-COUNT-ERROR 'DESTRUCTURING-BIND 'NIL #:ARGS13939
                                    '(A B C D E) 5 5)))
    (LET* ((A (CAR #:WHOLE13937))
           (B (CAR (CDR #:WHOLE13937)))
           (C (CAR (CDR (CDR #:WHOLE13937))))
           (D (CAR (CDR (CDR (CDR #:WHOLE13937)))))
           (E (CAR (CDR (CDR (CDR (CDR #:WHOLE13937)))))))
      (VALUES A B C D E))))

This is wasteful since #:WHOLE13937 is traversed from the beginning for each parameter in the lambda list.

Proposed Solution

Change the defmacro machinery to emit expansions like

(LET ((#:WHOLE14169 '(1 2 3 4 5)))
  (DECLARE (TYPE LIST #:WHOLE14169))
  (LET* ((#:CHECKED14170 #:WHOLE14169) ; check omitted; see previous section
         (A (CAR #:CHECKED14170))
         (#:REST14171 (CDR #:CHECKED14170))
         (B (CAR #:REST14171))
         (#:REST14172 (CDR #:REST14171))
         (C (CAR #:REST14172))
         (#:REST14173 (CDR #:REST14172))
         (D (CAR #:REST14173))
         (#:REST14174 (CDR #:REST14173))
         (E (CAR #:REST14174))
         (#:REST14175 (CDR #:REST14174)))
    (DECLARE (MUFFLE-CONDITIONS SB-EXT:CODE-DELETION-NOTE))
    (VALUES A B C D E)))

This eliminates the problem of unnecessary traversals.

Type Checks in Traversal Code

Problem

The improved expansion in the previous section is still not optimal: even if the type of #:CHECKED14170 was derived precisely enough, that is (cons t (cons t …)) (which the mechanism discussed in *Checking the Argument List should allow), type derivation for cdr is too conservative to conclude that all #:REST* variables are of type cons. As a result, a type check is inserted for each #:REST*.

Proposed Solution

I don't see a reason why the method described in section *Checking the Argument List could not, in principle, be applied to cdr type derivation: if there are no references to the =cdr= of the cell besides the cdr there should be no need to derive types conservatively. "to the cdr of the cell" will probably be the hard part, but maybe the special case "all other references are via car" can be implemented with reasonable effort.

Correctness

[1]> (destructuring-bind (&whole boo blah (bla3 &optional foo bar &key bla4)
  bli &key ((:foo (foo2 foo3 foo4))) &allow-other-keys)
    '(1 (2 3 4 :bla4 5) 6)
  (list boo blah bla3 foo bar bla4 bli foo2 foo3 foo4))
((1 (2 3 4 :BLA4 5) 6) 1 2 3 4 5 6 NIL NIL NIL)
[4]> (destructuring-bind (&whole boo blah (bla3 &optional foo bar &key bla4)
                             bli &key ((:foo (foo2 foo3 foo4)) (list 1 2 3)) &allow-other-keys)
    '(1 (2 3 4 :bla4 5) 6)
  (list boo blah bla3 foo bar bla4 bli foo2 foo3 foo4))
((1 (2 3 4 :BLA4 5) 6) 1 2 3 4 5 6 1 2 3)

Maintainability

Problem

The current implementation of defmacro uses many special variables whose interactions across multiple functions are hard to understand or modify. In addition, the central helper function parse-defmacro-lambda-list is very long, complicated and contains lots of redundant code.

Proposed Solution

Split code for different lambda list sections into multiple functions and separate parsing logic from housekeeping and result construction.

A first step would be defining lambda list sections independently with declarative parsing rules:

(define-lambda-list-section (&environment :valid-depth (eql 0))
  "&ENVIRONMENT var
   Can appear at any position in a top-level lambda list but not in
   nested lambda lists."
  (let ((name (consume :type '(and symbol (not (or null keyword)))))) ; TODO legal-variable-name-p
    (values (variable name) 0 0 rest-var)))

(define-lambda-list-section (:required
                             :keyword nil
                             :before (&optional &rest &key &aux)
                             :guard (not (lambda-list-keyword-p head))) ; TODO consider only "active" lambda-list keywords
  "var-or-pattern*"
  (collect ((parameters))
    (do-parameters (var-or-pattern #'try-consume)
      (parameters (process-variable-or-nested-defmacro-lambda-list
                   var-or-pattern depth rest-var 'TODO-name 'TODO-context #'variable)))
    (let ((count (length (parameters))))
      (values (parameters) count count rest-var))))

(define-lambda-list-section (&rest
                             :aliases (&body)
                             :before (&key &aux))
  "{&REST | &BODY} var-or-pattern"
  (let ((var-or-pattern (consume)))
    (values (list (variable var-or-pattern)) 0 nil rest-var)))

Footnotes:

1 Of course, pkhuong came up with this idea.

Date: 2013-07-29T12:56+0200

Author: Jan Moringen

Org version 7.9.3d with Emacs version 24

Validate XHTML 1.0