Lambda-list pattern

[ghost]

This is a first pass at a lambda-list pattern. It works, but I think there currently are three issues, i) I've used the 'variable-symbol' type instead of 'variablep' in order to exclude keywords and lambda-list-keywords. ii) I had resort to the ugly trick of creating list and then binding them inside patterns using '<>'; it's likely that you can think of a better way to accomplish this (in function compile-destructuring-pattern). iii) The loops inside recurse-maadi are not upper-bound.

[guicho271828]

I am inactive untill the deadline of a conference paper, so I can't verify this commit until then. sorry for the delay!

[ghost]

Sweet. I just timed it and lambda-list beats destructuring-bind in SBCL by a factor of 3 :D

[guicho271828]

that's amazing :o would you also add some test cases to t/ ?

[ghost]

Done. I realized I have no way for binding patterns lexically though. This seems to be a more fundamental issue.

Edit: Never mind. I meant to say 'parallel-y' as in let. I realize now that destructuring is infact done sequentially, and that the following is perfectly valid code,

(destructuring-bind (a &optional (b a)) ...) 

[guicho271828]

patterns, lexically? I don't get it.

[guicho271828]

1 more day before the deadline, I will reconsider that later. I will merge it anyways. Thank you for the contribution!

[guicho271828]

Finally I have the time to test this by myself! What kind of benchmark script are you using? I want to add the results to the benchmarking pages on the wiki.

[guicho271828]

Well, I reimplemented destructuring-pattern based on your logic in #16 . A few improvements include:

• its now implemented using trivia pattern matcher itself.
• Use of either 'variable-symbol' or 'variablep' limits the nestability of patterns, for example you cannot further destruct a required argument into vector elements, structure-object slots, etc. Each pattern element can now be an arbitrary subpattern.

While the standard &optional syntax is (var default supplied-p), it supports (pattern default supplied-p).

  (defclass person ()
       ((name :initarg :name :reader name)
        (age :initarg :age)))

  (match (list (make-instance 'person :name :guicho) (vector :mar 28 1990))
        ((lambda-list (person name) &optional ((and birthday (vector month day year)) (vector :jan 1 1970)))
         (list name birthday month day year)))

;; --> (:GUICHO #(:MAR 28 1990) :MAR 28 1990)

  (match (list (make-instance 'person :name :guicho))
        ((lambda-list (person name) &optional ((and birthday (vector month day year)) (vector :jan 1 1970)))
         (list name birthday month day year)))

;; --> (:GUICHO #(:JAN 1 1970) :JAN 1 1970)

[ghost]

I didn't do extensive benchmarking, but these two patterns are definitely faster than SBCL's destructuring-bind,

(let ((lst '(1 :b 2)) (tmp 0))
     (time (dotimes (_ 1000)
         (match lst
           ((λlist a &key b) (incf tmp b)))))
     (time (dotimes (_ 1000)
         (destructuring-bind (a &key b) lst
           (incf tmp b)))))

(let ((lst '(1 (2 3))) (tmp 0))
     (time (dotimes (_ 1000)
         (match lst
           ((λlist a (λlist b c)) (incf tmp b)))))
     (time (dotimes (_ 1000)
         (destructuring-bind (a (b c)) lst
           (incf tmp b)))))

While the new keyword pattern compiler is theoretically less efficient than the earlier quasi-destructive getf! one, it seems to be faster if the number of keyword arguments are low. (SBCL too seems to use a similar backend.)

[ghost]

Hmm, are you okay with syntactic differences between,

(lambda-list a &optional b)
(lambda-list a &optional ((list 2 3)))

Is there a similar way by which patterns can be matched to keyword arguments ?

[guicho271828]

in standard CL, the semantics of &key is itself complex: &key var | ( { var | (keywordname var) } [default [suppliedp]]).

Nesting a pattern to a keyword parameter is available only to the (keywordname var) form, since otherwise it cannot specify which keyword can be used. So, although it is slightly complex, we can use the following:

(match (list 0 :a (vector 1 2))
  ((lambda-list x &key ((a (vector y z)) (vector -1 -2) supplied-p))
    (list x y z supplied-p)))

;; -> (0 1 2 T)

(match (list 0)
  ((lambda-list x &key ((a (vector y z)) (vector -1 -2) supplied-p))
    (list x y z supplied-p)))

;; -> (0 -1 -2 NIL)

Otherwise only a simple variable-binding is allowed, same as the previous implementation:

(match (list 0 :a (vector 1 2))
  ((lambda-list x &key a)
    (list x a)))

;; ->(0 #(1 2))

(match (list 0)
  ((lambda-list x &key a)
    (list x a)))

;; -> (0 NIL)

(match (list 0 :a (vector 1 2))
  ((lambda-list x &key (a (vector) supplied-p)) 
    (list x a supplied-p)))

;;-> (0 #(1 2) T)

(match (list 0)
  ((lambda-list x &key (a (vector) supplied-p)) 
    (list x a supplied-p)))

;;-> (0 #() NIL)

I now see why the past code uses getf!, it is to avoid the use of iterative getf which is O(n^2) if I'm correct? Sorry for not noticing this, but I was skeptical if the additional consing by copy-list would not harm the performance. It would be possible to intelligently switch between two behaviors depending on the length of the keyword params.

[guicho271828]

For optional arguments, you don't need additional parenthesis since the position is clear.

(lambda-list a &optional b)
(lambda-list a &optional (list 2 3))

[guicho271828]

sorry I was wrong, it should be ((list 2 3)) as you pointed out. yes, this is required because it should distinguish between (var default suppliedp) and (list 2 3). In addition, ((list 2 3) default suppliedp) works.

[guicho271828]

Another thing I noticed is the special handling of guard in the previous code. Guard is a level2 pattern which might be already compiled away into guard1 (level1 pattern), so there is no point in handling them.

[guicho271828]

https://github.com/guicho271828/trivia/blob/master/level2/derived3.lisp#L161 This contains a separate compiler function for the keywords, now we can cleanly apply the optimization.

[ghost]

The getf! thing was popping out keywords as it found them. Actually, come to think of it, it probably wasn't even better off theoretically. Linear time would be cool, but I'm not sure if that can be accomplished without the use of hash-tables or some other clever data-structure. I should've taught about this before implementing. The new pattern is definitely much cleaner :)

The new keyword pattern matching syntax is confusing, but I don't see how you can do something better. Thanks for cleaning up the implementation :)

[ghost]

The special handling of 'guard' was meant to handle patterns on &optional/&key variables; the new syntax is definitely better.

Also, can sub-patterns be compiled before the parent ?

[guicho271828]

can sub-patterns be compiled before the parent ?

you can, by (mapcar #'pattern-expand-all subpatterns) , but they are fully expanded in the end anyways, so it wont be necessary. Only the fundamentally complex patterns like and pattern would need this.

[guicho271828]

benchmarking

This is cool, ~x6 speedup?

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  11,484 processor cycles
  0 bytes consed

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  58,386 processor cycles
  0 bytes consed

[ghost]

Sweet. Yeah, that's about the speedup I get as well. It's kind strange that we do indeed see a speedup. SBCL's destructuring-bind is essentially doing the same thing as lambda-list.

[ghost]

Aren't patterns also 'lexically scoped' ? Calling pattern-expand inside a pattern breaks that rule (vis a vis macros).

[guicho271828]

"lexically" and "scope" is a word for variables. A pattern may contain variables but it may also contain others.

pattern-expand is an analogue to macroexpand, so this is just a compile-time utility and it does nothing related to runtime, just in case.

[ghost]

Macros too are bound lexically at compile-time. Macros/Macrolets are written under the explicit assumption that they won't be macroexpand-1 'ed from those explicitly outside the scope.

To extend the analogy, I was assuming a 'patternlet' for guard inside lambda-list earlier.

[guicho271828]

alright, now I understand what you mean, yes variable patterns are lexically bound in that sense. For example,

(match (list 1 2)
  ((list x (= (* 2 x)))
    t))

returns t. (= pattern expands to guard, guard is creating a binding, which is further compiled into guard1 primitive)

[guicho271828]

first-order "local" patterns are not currently assumed, but thanks to the inner use of lisp-namespace (yes, another work of mine) which provides a convenient way to bind pattern definition (dynamically, though), it is possible to implement pattern-let.

https://github.com/guicho271828/lisp-namespace

Edit: Oh I now remember that I already have defined pattern-let automatically.

[guicho271828]

hm, not actually. your aim is something like this?

(pattern-let ((my-local-pattern (x y z) <some code which expands macros>))
   (match something
     ((my-local-pattern ...)
      ))

it should work in compile time, so it introduces another difficulty.

the pattern-let automatically defined by lisp-namespace can be used in a dynamic scope, so it can only be used in a context like this:

(defpattern mypattern (arg)
   (pattern-let ((vec1 (lambda (x) `(vector ,x)))) ;; dynamically binds a pattern that is locally available
      (patten-expand-all arg)))

(pattern-expand '(mypattern (vec1 3)) ;; -> some pattern with (vec1 3) converted to (vector 3)

(pattern-expand '(vec1 3)) ;; -| error pattern-not-found , since vec1 is defined only locally

[ghost]

Ah but pattern-let is defined before calling; I was imagining a re-binding within the pattern itself.

Previously, lambda-list 'implicitly' redefined 'guard', such that

(guard (var &optional default supplied) ...) 

did not follow the semantics of the canonical pattern. This came with the assumption that lambda-list could lexically rebind 'guard' locally, without affecting the pattern-expansion. Basically, is there a guarantee that pattern-expand is called on a tree before being called on its children (assuming that no pattern explicitly calls pattern-expand-1 on any of its child patterns) ?

For example,

(lambda-list a &optional (guard (b 2) (eql b 'a)))

would have been valid if 'lambda-list' were expanded before 'guard' (because of the implicit lexical rebinding). It would've raised an error if 'guard' was expanded before 'lambda-list'. Is 'commutativity', in the sense that of order of pattern expansion, a requirement ? I can imagine the trivia-optimizer breaking this assumption, but the answer seems to be no otherwise.

[guicho271828]

interesting topic... patterns are basically meant to be expanded in normal order (as in macros) -- expanded from the top, left to right. I wrote and has a special handling, but even and uses pattern-expand (fully expand the pattern by 1 level) only, not pattern-expand-all which expands the inner patterns (expands more than 2 levels). See here. Therefore, the commutativity is maintained in the current implementation.

Although it is maintained, this is unintentional, and I think breaking the commutativity is ok. Indeed, breaking the commutativity is required for implementing a "local pattern" like this (same as what I posted previously):

(defpattern mypattern (arg)
   (pattern-let ((vec1 (lambda (x) `(vector ,x))))
      (patten-expand-all arg)))

This requires pattern-expand-all because, if I replace pattern-expand-all with pattern-expand, local patterns nested more than 2 levels would not be recognized, e.g., expansion of (mypattern (vec1 3)) succeeds but (mypattern (and (vec1 3))) fails.

Optimizer would not see the unexpanded patterns. The input to the optimizer should consist of guard1 and or1 primitives only, and so does its output. Therefore you don't have to worry about it.

[ghost]

Ah, you're right; pattern-let does exactly what I meant. I guess the rest of it makes sense.

It'd be cool have consistent local-patterns though (without commutativity). Would using labels instead of macrolet in namespace-let, fix this ?

There also seems to be a bug in lisp-namespace; the macro

(trivia.level2.impl::pattern-let ((vec1 (lambda (x) `(vector ,x))))
     (pattern-expand-all arg))

expands into,

(PROGN
 (LET ((#:TEMP835 (LAMBDA (X) `(VECTOR ,X))))
   (DECLARE (TYPE (PATTERN-TYPE) #:TEMP835))
   (MACROLET ((SYMBOL-PATTERN (&WHOLE LISP-NAMESPACE::WHOLE LISP-NAMESPACE::X)
                (IF (EQUAL LISP-NAMESPACE::X ''VEC1)
                    '#:TEMP835
                    LISP-NAMESPACE::WHOLE)))
     (PROGN (PATTERN-EXPAND-ALL ARG)))))

The type declaration here is missing the package information for some reason.

[guicho271828]

Thanks for pointing it out, fixed now. intern is always dangerous and requires a special care...

(PROGN
 (LET ((#:TEMP773 (LAMBDA (X) `(VECTOR ,X))))
   (DECLARE (TYPE (TRIVIA.LEVEL2.IMPL::PATTERN-TYPE) #:TEMP773))
   (MACROLET ((TRIVIA.LEVEL2.IMPL::SYMBOL-PATTERN
                  (&WHOLE LISP-NAMESPACE::WHOLE LISP-NAMESPACE::X)
                (IF (EQUAL LISP-NAMESPACE::X ''VEC1)
                    '#:TEMP773
                    LISP-NAMESPACE::WHOLE)))
     (PROGN (PATTERN-EXPAND-ALL ARG)))))

[guicho271828]

Now I added the longed inline pattern feature to trivia, whose idea is described here. This corresponds to a splicing-comma of a quasiquote. For example, a trivial inline pattern @ directly inlines the given patterns, i.e. (and (@ a b c)) is equivalent to (and a b c). This requires a special handling, in particular, inline patterns should be expanded eagerly, regardless of the position of the pattern. For this purpose, I added another construct defpattern-inline.

See another example using @@ pattern below. @@ duplicates a given sequence of patterns and splice them into the original pattern.

(vector 1 (@@ 10 _) 11)
;; inline-pattern-expand -->
(vector 1 _ _ _ _ _ _ _ _ _ _ 11)

inline-pattern-expand expands inline patterns only, from the leaf to the root (opposite to the normal patterns).

Now pattern-expand-all calls inline-pattern-expand and pattern-expand alternatingly, since a normal pattern may produce an inline pattern.

[guicho271828]

Your idea on local patterns is so interesting, because it gives a way to add a convenient local pattern for arrays. See, for example, how such a pattern could implement LU-decomposition beautifully (if given additional interface array-setf and matrix-sub, and local patterns element and displaced):

;; array : N*N input matrix
;; LU : N*N result matrix 
;; kth iteration: processing bottom-right (N-k)*(N-k) sub-matrix

(match* (array LU)
  (((array (element   k     k     ckk-a)  (displaced k     (k N) ck*-a)
           (displaced (k N) k     c*k-a)  (displaced (k N) (k N) c**-a))
    (array (element   k     k     ckk-lu) (displaced k     (k N) ck*-lu)
           (displaced (k N) k     c*k-lu) (displaced (k N) (k N) c**-lu)))
   (array-setf c*k-lu (map 'vector (lambda (cjk) (/ cjk ckk)) c*k-a))
   (array-setf c**-lu (matrix-sub c**-a (elementwise-prod ck*-a c*k-lu)))))

[ghost]

Hmm, but that can probably be implemented with just a defpattern no ? I mean the patterns don't really bind previously defined patterns.

Digression: Here's a version of the recursive-lu that actually works (modulo type-checks) in Matlisp :)

(defun recursive-lu! (M &optional (ret M))
  (if (< (dimensions M 0) 2) ret
      (recursive-lu! #i(ger!(-1, M[1:, 0], scal!(/ M[0, 0], M[0, 1:]), M[1:, 1:])) ret)))

[guicho271828]

I'm not familier with matrix libraries, but that seems useful and interesting. thanks!