使用少量运算符来表达大量内容

Question

Paul Graham在他的书On Lisp中强调Lisp是“可扩展的语言”。他说，这意味着逐步建立更高的语言接口，以便能够有效地讨论或分析应用程序。这就产生了一种正交语言。其中，您可以通过以多种不同的方式组合少量的运算符来表达大量内容。作为一个实验，我想尝试并扩展一个更有用的序列函数，即remove。

暂时搁置涉及非序列数据类型的扩展(如从数组、哈希表或属性列表中删除元素)，仍然有扩展关键字选择的空间。例如，没有基于元素的索引从序列中删除元素的内置规定。沿着这些思路，程序员可能希望使用类似于(lambda (elt idx) (= elt idx))的测试来删除其值与其索引相同的元素。非扩展的方法是简单地使用您自己的迭代函数(其他一百个难以记住的实用程序中的一个)，但是利用内置函数并扩展它们似乎更加简洁、可重用和高效。

直接的问题是，只有当存在给定的搜索项时，remove才适用，并且remove-if需要一个只接受一个元素作为参数的谓词(而不是元素及其索引)。我要探索的方法试图将不同的选项合并到一个remove-sequence函数中，其中序列是唯一必需的参数，其他所有内容都是针对特定类型的所需删除量身定做的关键字。因此，搜索项是在:item关键字中指定的，根据需要，一个或两个参数boolean :test可以同时包括元素和索引。在后一种情况下，一个简单的调用可能类似于(remove-sequence '(3 1 2 4) :test (lambda (elt idx) (= x i)))删除第三个元素。

我从一个函数开始，该函数似乎适用于SBCL中的以下示例：

(require :sb-introspect)

(defun remove-sequence (sequence &key item (test #'eql) from-end (start 0)
                         (end (length sequence)) (count (length sequence)) (key #'identity))
  (cond (item
           (remove item sequence :test test :from-end from-end
                                 :start start :end end :count count :key key))
        ((= (length (sb-introspect:function-lambda-list test)) 1)
           (remove-if test sequence :from-end from-end
                                    :start start :end end :count count :key key))
        ((= (length (sb-introspect:function-lambda-list test)) 2)
           (let* ((delta (if from-end -1 +1))
                  (initial-index (if from-end (length sequence) -1))
                  (closure (let ((index initial-index))
                             (lambda (element)
                               (setf index (+ index delta))
                               ;(print (list element index))
                               (funcall test element index)))))
             (remove-if closure sequence :from-end from-end
                                         :start start :end end :count count :key key)))
        (t (error "in remove-sequence macro"))))

(remove-sequence '(1 2 4 1 3 4 5) :test #'> :item 3) =>  (4 3 4 5)
(remove-sequence '(1 2 3 4 5 6) :test #'evenp :count 2 :from-end t) =>  (1 2 3 5)
(remove-sequence '(3 1 2 4) :test #'(lambda (elt idx) (= elt idx))) =>  (3 1 4)

然而，我在将它转换成宏时遇到了麻烦，到目前为止，它看起来像下面这样。(它在宏展开时生成错误。)

(defmacro remove-sequence (sequence &key item test from-end start end count key)
  (let ((tst (when test `(:test ,test)))
        (frm-nd (when from-end `(:from-end ,from-end)))
        (strt (when start `(:start ,start)))
        (nd (when end `(:end ,end)))
        (cnt (when count `(:count ,count)))
        (ky (when key `(:key ,key)))
        (test-fn (if test test #'eql)))
    (cond (`,item
             `(remove ,item ,sequence ,@tst ,@frm-nd ,@strt ,@nd ,@cnt ,@ky))
          ((= (length (sb-introspect:function-lambda-list test-fn)) 1)
             `(remove-if ,test-fn ,sequence ,@frm-nd ,@strt ,@nd ,@cnt ,@ky))
          ((= (length (sb-introspect:function-lambda-list test-fn)) 2)
             (let* ((delta (if `,from-end -1 +1))
                    (initial-index (if `,from-end (length `,sequence) -1))
                    (closure (let ((index initial-index))
                               (lambda (element)
                                 (setf index (+ index delta))
                                 ;(print (list element index))
                                 (funcall test-fn element index)))))
                `(remove-if ,closure ,sequence ,@frm-nd ,@strt ,@nd ,@cnt ,@ky)))
          (t (error "in remove-sequence macro")))))

这个问题能解决吗？或者有没有更好的方式来写它？更普遍的是，添加十几个关键字有没有坏处？例如，我至少想为:duplicates和:destructive添加布尔关键字，而其他关键字可能与非序列参数相关。感谢您的任何有经验的见解。

Answer 1

这是你的函数签名：

(sequence &key 
  item 
  (test #'eql) 
  from-end 
  (start 0)
  (end (length sequence)) 
  (count (length sequence))
  (key #'identity))

为许多不同的操作提供高级接口有一些好处，但您也必须注意性能。在上面的代码中，每次调用函数时都会调用两次(length sequence)。如果该函数仅用于向量，则可以，但在列表的情况下，您将执行两次线性遍历。在算法复杂度方面，这不是一个问题，因为在最坏的情况下，remove预计在时间和空间上是线性的。但就运行时间而言，在很多情况下，最坏的情况没有出现，但您的实现花费了太多时间。

在标准的REMOVE函数中，:END的默认值是nil，它在这里有特殊的含义(序列的结尾)，而不需要实际计算索引。处理列表的函数可以在不遍历整个列表的情况下利用该信息；例如，当count为1时，应该发生的事情大致如下：

(defun remove-first (item list)
  (if (endp list)
      nil
      (if (equalp (first list) item)
          (rest list)
          (cons (first list) 
                (remove-first item (rest list))))))

在实践中，您可以期望代码不依赖于尾递归消除：

(defun remove-first (item list)
  (loop
     with stack = nil
     for (head . tail) on list
     do (if (equalp head item)
            (return
              (dolist (e stack tail)
                (push e tail)))
            (push head stack))))

您甚至可以使用无限列表：

USER> (setf *print-circle* t)
T

USER> (remove-first 3 '#1=(1 2 3 4 5 6 . #1#))
(1 2 . #1=(4 5 6 1 2 3 . #1#))

总而言之，Common Lisp中非常有趣的一件事是，更高级别的标准函数/抽象具有可预测的、毫不奇怪的资源使用。尽管没有这样指定，但我希望非玩具实现中的map不会因为递归调用等原因而导致大型列表上的堆栈溢出。这可能是改进现有代码的一种方法。

Answer 2

正如Rainer Joswig上面评论的那样，宏:test参数是一个被理解为函数指示器的列表，而不是函数对象。在将其传递给sb-introspect之前将其转换为函数: function -lambda-list应该可以修复错误。有更多经验的人可能会评论symbol-function和coerce是否涵盖了所有可能的情况：

(defmacro remove-sequence (sequence &key item (test '(function eql)) from-end start end count (key '(function identity)))
  (let ((tst (when test `(:test ,test)))
        (frm-nd (when from-end `(:from-end ,from-end)))
        (strt (when start `(:start ,start)))
        (nd (when end `(:end ,end)))
        (cnt (when count `(:count ,count)))
        (ky (when key `(:key ,key)))
        (test-fn (cond ((symbolp (second test)) (symbol-function (second test)))
                       ((eq (first test) 'lambda) (coerce test 'function))
                       ((eq (first test) 'function) (coerce (second test) 'function))
                       (t (error "Malformed :test function ~A" test))))
        (key-fn  (cond ((symbolp (second key)) (symbol-function (second key)))
                       ((eq (first key) 'lambda) (coerce key'function))
                       ((eq (first key) 'function) (coerce (second key) 'function))
                       (t (error "Malformed :key function ~A" key)))))
   (cond (`,item
            `(remove ,item ,sequence ,@tst ,@frm-nd ,@strt ,@nd ,@cnt ,@ky))
         ((= 1 (length (sb-introspect:function-lambda-list test-fn)))
            `(remove-if ,test ,sequence ,@frm-nd ,@strt ,@nd ,@cnt ,@ky))
         (t (let* ((delta (if `,from-end -1 +1))
                   (initial-index (if `,from-end (length `,sequence) -1))
                   (closure (let ((index initial-index))
                              (lambda (element)
                                (setf index (+ index delta))
                                ;(print (list element index))
                                (funcall test-fn (funcall key-fn element) index)))))
              `(remove-if ,closure ,sequence ,@frm-nd ,@strt ,@nd ,@cnt ,@ky))))))

请注意，在下一个草案中仍有变量捕获的问题需要处理。

另一个问题涉及sb-introspect:function-lambda-list返回的arg列表的长度。如果:test函数只有一个参数，则remove-if是正确的扩展。如果它有两个或多个参数，那么展开就是remove (如果还有:item关键字)，或者是带有闭包的remove-if (否则)。不需要只检查两个参数。事实上，许多可接受的:测试函数的lambda列表都长于2(例如#'>).

* (remove-sequence '(1 2 4 1 3 4 5) :test #'> :item 3)
 (4 3 4 5)
* (remove-sequence '(1 2 3 4 5 6) :test #'evenp :count 2 :from-end t)
 (1 2 3 5)
* (remove-sequence '(3 1 2 4) :test (lambda (elt idx) (= elt idx)))
 (3 4)
* (defun element=index (elt idx)
     (= elt idx)) ELEMENT=INDEX
* (remove-sequence '(3 1 2 4) :test 'element=index)
 (3 4)
*