是否有一个与Python生成器相当的lisp等效项? [英] Is there a straightforward lisp equivalent of Python's generators?

查看:61
本文介绍了是否有一个与Python生成器相当的lisp等效项?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

在Python中,您可以编写以下代码:

def firstn(n):
     num = 0
     while num < n:
         yield num
         num += 1

这与lisp等效吗?

解决方案

现有软件包

使用 GENERATORS 系统www.quicklisp.org/beta/"rel =" nofollow noreferrer> Quicklisp .然后,使用包:generators(或者最好先定义您自己的包).

 (ql:quickload :generators)
(use-package :generators)
 

为随机值定义一个无限生成器:

 (defun dice (n)
  (make-generator ()
    ;; repeatedly return a random value between 1 and N
    (loop (yield (1+ (random n))))))
 

使用生成器:

 (loop
   with dice = (dice 6)
   repeat 20
   collect (next dice))

=> (1 2 6 1 1 4 4 2 4 3 6 2 1 5 6 5 1 5 1 2)
 

但是请注意该库的作者怎么说:

尽管据我所知,这个图书馆更像是一个有趣的玩具 确实有效.我不认为我曾经在应用程序代码中使用过它, 尽管我认为可能会小心.

另请参见

  • ITERATE 包提供了一种定义生成器,可在其迭代工具中使用.

  • SERIES 包在其上提供了类似于流的数据结构和操作.

  • Snakes 库(据我所知与GENERATORS相同) .

  • 迭代器 (defun dice (n) (lambda () (1+ (random n))))

    然后,等价于next只是对dice生成的thunk的调用:

     (loop
       with dice = (dice 6)
       repeat 20
       collect (funcall dice))
     

    这是首选的方法,特别是因为不需要像生成器那样依赖定界的延续.您的示例涉及一个状态,该状态不是 dice 示例所必需的(存在一个隐藏的状态会影响random,但这是另一回事了).这是计数器通常的实现方式:

     (defun first-n (n)
      (let ((counter -1))
        (lambda ()
          (when (< counter n)
            (incf counter)))))
     

    高阶函数

    或者,您设计一个生成器,该生成器接受由生成器为每个值调用的回调函数.可以使用任何funcallable,它允许调用方保留对代码执行的控制:

     (defun repeatedly-throw-dice (n callback)
      (loop (funcall callback (1+ (random n)))))
     

    然后,您可以按以下方式使用它:

     (prog ((counter 0) stack)
      (repeatedly-throw-dice 6 
        (lambda (value)
          (if (<= (incf counter) 20)
            (push value stack)
            (return (nreverse stack))))))
     

    请参见 PROG 的文档.

    do-traversal成语

    数据源提供了一种自定义的方式来生成值(例如,匹配常规字符串中的表达式)还定期提供一个抽象其控制流的宏.您将按以下方式使用它:

     (block 'outer
      (let ((counter 0) stack)
        (do-repeatedly-throw-dice (value 6)
    
          ;; For each iteration of the infinite loop,
          ;; VALUE is bound to a new random value.
    
          (if (<= (incf counter) 20)
            (push value stack)
            (return-from 'outer (nreverse stack))))))
     

    与上述内容的区别在于,该块被明确命名.这是因为通常可以期望DO-X在其主体周围定义一个NIL块,这意味着任何封闭的NIL块均被阴影覆盖. 隐式的NIL块使您可以轻松退出迭代:

      (let ((counter 0)  stack)
       (do-repeatedly-throw-dice (value 6)
         (if (<= (incf counter) 20)
           (push value stack)
           (return (nreverse stack))))))
     

    该宏的可能实现是将主体包装为lambda形式,并使用上面定义的基于回调的版本:

     (defmacro do-repeatedly-throw-dice ((var n) &body body)
      `(block nil (repeatedly-throw-dice ,n (lambda (,var) ,@body))))
     

    也可以直接扩展为循环:

     (defmacro do-repeatedly-throw-dice ((var n) &body body)
      (let ((max (gensym)) (label (make-symbol "NEXT")))
        `(prog ((,max ,n) ,var)
            ,label
            (setf ,var (1+ (random ,max)))
            (progn ,@body)
            (go ,label))))
     

    上述形式的宏扩展步骤:

     (BLOCK 'OUTER
      (LET ((COUNTER 0) STACK)
        (PROG ((#:G16053 6) VALUE)
         #:NEXT (SETF VALUE (1+ (RANDOM #:G16053)))
                (PROGN (IF (<= (INCF COUNTER) 20)
                          (PUSH VALUE STACK)
                          (RETURN-FROM 'OUTER (NREVERSE STACK))))
                (GO #:NEXT))))
     

    绑定

    广义上讲,构建具有高阶函数或直接具有do-宏的生成器会得到相同的结果.您可以彼此实现(个人而言,我更喜欢先定义宏,然后再使用宏定义函数,但是相反的做法也很有趣,因为您可以重新定义函数而无需重新编译宏的所有用法).

    但是,仍然存在差异:宏在迭代之间重用相同的变量,而闭包每次都引入新的绑定.例如:

     (let ((list))
      (dotimes (i 10) (push (lambda () i) list))
      (mapcar #'funcall list))
     

    ....返回:

     (10 10 10 10 10 10 10 10 10 10)
     

    Common Lisp中的大多数(如果不是全部)迭代器通常都像这样 1 起作用,对于有经验的用户来说应该不会感到惊讶(反之则是令人惊讶的是,实际上).如果dotimes是通过重复调用闭包来实现的,则结果将有所不同:

     (defmacro my-dotimes ((var count-form &optional result-form) &body body)
      `(block nil
         (alexandria:map-iota (lambda (,var) ,@body) ,count-form)
         ,result-form))
     

    使用上面的定义,我们可以看到:

     (let ((list))
      (my-dotimes (i 10) (push (lambda () i) list))
      (mapcar #'funcall list))
     

    ...返回:

     (9 8 7 6 5 4 3 2 1 0)
     

    为了获得与标准dotimes相同的结果,您只需要在构建闭包之前创建一个新的绑定即可:

     (let ((list))
      (dotimes (i 10) 
        (let ((j i))
          (push (lambda () j) list))))
     

    此处j是一个新的绑定,其值是在 creation 关闭时i的当前值; j永不突变,因此闭包将不断返回相同的值. 如果愿意,您总是可以从宏中引入内部let,但这很少这样做.


    1 :请注意 DOTIMES 不需要每次迭代都重新绑定,也不需要在每个步骤都改变相同的绑定:"dotimes是否在每次迭代中建立新的var绑定还是是否依赖于实现取决于实现首先在var上建立一次绑定,然后在以后的任何迭代中将其分配." 为了便于移植,有必要假设最坏的情况(即突变,碰巧是大多数情况(所有?)的实现),并手动重新绑定迭代变量(如果要在以后捕获并重用它们).

    In Python you can write this:

    def firstn(n):
         num = 0
         while num < n:
             yield num
             num += 1
    

    What is the lisp equivalent of this?

    解决方案

    Existing package

    Download, install and load the GENERATORS system with Quicklisp. Then, use package :generators (or preferably, define your own package first).

    (ql:quickload :generators)
    (use-package :generators)
    

    Define an infinite generator for random values:

    (defun dice (n)
      (make-generator ()
        ;; repeatedly return a random value between 1 and N
        (loop (yield (1+ (random n))))))
    

    Use the generator:

    (loop
       with dice = (dice 6)
       repeat 20
       collect (next dice))
    
    => (1 2 6 1 1 4 4 2 4 3 6 2 1 5 6 5 1 5 1 2)
    

    Note however what the author of the library says:

    This library is more of an interesting toy, though as far as I know it does work. I dont think I have ever used this in application code, though I think that with care, it could be.

    See also

    • The ITERATE package provides a way to define generators for use inside its iteration facility.

    • The SERIES package provide stream-like data structures and operations on them.

    • The Snakes library (same approach as GENERATORS as far as I know).

    • Iterators in generic-cl

    Closures

    In practice, CL does not rely that much on generators as popularized by Python. What happens instead is that when people need lazy sequences, they rely on closures:

    (defun dice (n)
      (lambda ()
        (1+ (random n))))
    

    Then, the equivalent of next is simply a call to the thunk generated by dice:

    (loop
       with dice = (dice 6)
       repeat 20
       collect (funcall dice))
    

    This is the approach that is preferred, in particular because there is no need to rely on delimited continuations like with generators. Your example involves a state, which the dice example does not require (there is a hidden state that influences random, but that's another story) . Here is how your counter is typically implemented:

    (defun first-n (n)
      (let ((counter -1))
        (lambda ()
          (when (< counter n)
            (incf counter)))))
    

    Higher-order functions

    Alternatively, you design a generator that accepts a callback function which is called by your generator for each value. Any funcallable can be used, which allows the caller to retain control over code execution:

    (defun repeatedly-throw-dice (n callback)
      (loop (funcall callback (1+ (random n)))))
    

    Then, you can use it as follows:

    (prog ((counter 0) stack)
      (repeatedly-throw-dice 6 
        (lambda (value)
          (if (<= (incf counter) 20)
            (push value stack)
            (return (nreverse stack))))))
    

    See documentation for PROG.

    do-traversal idiom

    Instead of building a function, data sources that provides a custom way of generating values (like matches of a regular expressions in a string) also regularly provide a macro that abstracts their control-flow. You would use it as follows:

    (block 'outer
      (let ((counter 0) stack)
        (do-repeatedly-throw-dice (value 6)
    
          ;; For each iteration of the infinite loop,
          ;; VALUE is bound to a new random value.
    
          (if (<= (incf counter) 20)
            (push value stack)
            (return-from 'outer (nreverse stack))))))
    

    The difference with the above is that the block is explicitely named. This is because DO-X usually can be expected to define a NIL block around their body, which means that any enclosing NIL block is shadowed. The implicit NIL block allows you to exit from the iteration easily:

     (let ((counter 0)  stack)
       (do-repeatedly-throw-dice (value 6)
         (if (<= (incf counter) 20)
           (push value stack)
           (return (nreverse stack))))))
    

    A possible implementation for the macro is to wrap the body in a lambda form and use the callback-based version defined above:

    (defmacro do-repeatedly-throw-dice ((var n) &body body)
      `(block nil (repeatedly-throw-dice ,n (lambda (,var) ,@body))))
    

    Directly expanding into a loop would be possible too:

    (defmacro do-repeatedly-throw-dice ((var n) &body body)
      (let ((max (gensym)) (label (make-symbol "NEXT")))
        `(prog ((,max ,n) ,var)
            ,label
            (setf ,var (1+ (random ,max)))
            (progn ,@body)
            (go ,label))))
    

    One step of macroexpansion for above form:

    (BLOCK 'OUTER
      (LET ((COUNTER 0) STACK)
        (PROG ((#:G16053 6) VALUE)
         #:NEXT (SETF VALUE (1+ (RANDOM #:G16053)))
                (PROGN (IF (<= (INCF COUNTER) 20)
                          (PUSH VALUE STACK)
                          (RETURN-FROM 'OUTER (NREVERSE STACK))))
                (GO #:NEXT))))
    

    Bindings

    Broadly speaking, building a generator with higher-order functions or directly with a do- macro gives the same result. You can implement one with the other (personally, I prefer to define first the macro and then the function using the macro, but doing the opposite is also interesting, since you can redefine the function without recompiling all usages of the macro).

    However, there is still a difference: the macro reuses the same variable across iterations, whereas the closure introduces a fresh binding each time. For example:

    (let ((list))
      (dotimes (i 10) (push (lambda () i) list))
      (mapcar #'funcall list))
    

    .... returns:

    (10 10 10 10 10 10 10 10 10 10)
    

    Most (if not all) iterators in Common Lisp tend to work like this1, and it should not come as a surprise for experienced users (the opposite would be surprising, in fact). If dotimes was implemented by repeatedly calling a closure, the result would be different:

    (defmacro my-dotimes ((var count-form &optional result-form) &body body)
      `(block nil
         (alexandria:map-iota (lambda (,var) ,@body) ,count-form)
         ,result-form))
    

    With the above definition, we can see that:

    (let ((list))
      (my-dotimes (i 10) (push (lambda () i) list))
      (mapcar #'funcall list))
    

    ... returns:

    (9 8 7 6 5 4 3 2 1 0)
    

    In order to have the same result with the standard dotimes, you only need to create a fresh binding before building the closure:

    (let ((list))
      (dotimes (i 10) 
        (let ((j i))
          (push (lambda () j) list))))
    

    Here j is a fresh binding whose value is the current value of i at closure creation time; j is never mutated so the closure will constantly return the same value. If you wanted to, you could always introduce that inner let from the macro, but this is rarely done.


    1: Note that the specification for DOTIMES does not require that bindings are fresh at each iteration, or only mutates the same binding at each step: "It is implementation-dependent whether dotimes establishes a new binding of var on each iteration or whether it establishes a binding for var once at the beginning and then assigns it on any subsequent iterations." In order to write portably, it is necessary to assume the worst-case scenario (i.e. mutation, which happens to be what most (all?) implementations do) and manually rebind iteration variables if they are to be captured and reused at a later point.

    这篇关于是否有一个与Python生成器相当的lisp等效项?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆