Более подходящая абстракция Common Lisp для реализации "саморекурсивного let" - PullRequest
Новая
       68

Более подходящая абстракция Common Lisp для реализации "саморекурсивного let"

1 голос
/ 23 октября 2019

Вчера я столкнулся с этой pipe библиотекой для общего lisp. В некоторой степени это выглядит как абстракция ленивых последовательностей clojure, поэтому я решил использовать его для реализации классического (и классного) примера clojure рекурсивного ленивого определения последовательности Фибоначчи в Common Lisp (для чисто образовательных целей).

, чтовот как это выглядит в clojure: 

(def fibs (lazy-cat [0 1] (map +' fibs (rest fibs))))

(nth fibs 100)
;;=> 354224848179261915075N

, что довольно просто, но проблема в том, что он сохраняет, возможно, огромную ленивую последовательность в глобальной области видимости навсегда, поэтому с некоторыми взломами я переписал ее, чтобы она могла бытьиспользуется внутри let привязки: 

(let [f (memoize (fn [f] 
                   (lazy-cat [0 1] 
                             (let [data (f f)]
                               (map +' data (rest data))))))
      fibs (f f)]
  (nth fibs 100))

;;=> 354224848179261915075N

вся вещь memoize и (f f) состоит в том, чтобы эмулировать рекурсию данных в let.

, затем я реализовал ее, используя тот же подходв CL.

сначала некоторые утилиты: 

;; analogue of `list*` for pipes
(defmacro make-pipe* (x1 &rest xs)
  (if xs
      `(pipes:make-pipe ,x1 (make-pipe* ,@xs))
      x1))

;; wraps function so that it always returns the result of its first invocation
(defun once (f)
  (let ((called (cons nil nil)))
    (lambda (&rest args)
      (if (car called)
          (cdr called)
          (let ((res (apply f args)))
            (setf called (cons t res))
            res)))))

;; map over two pipes
(defun pipe-map2 (fn pipe1 pipe2)
  (if (or (eq pipe1 pipes:+empty-pipe+)
          (eq pipe2 pipes:+empty-pipe+))
      pipes:+empty-pipe+
      (pipes:make-pipe (funcall fn (pipes:pipe-head pipe1) (pipes:pipe-head pipe2))
                       (pipe-map2 fn (pipes:pipe-tail pipe1) (pipes:pipe-tail pipe2)))))

, а затем здесь идет фактическая реализация: 

(let* ((f (once (lambda (f) 
                  (make-pipe* 0 1 
                              (let ((data (funcall f f)))
                                (pipe-map2 #'+ data (pipes:pipe-tail data)))))))
       (fibs (funcall f f)))
  (pipes:pipe-values fibs 10))
;;=> (0 1 1 2 3 5 8 13 21 34 55 . #<CLOSURE (LAMBDA () :IN PIPE-MAP2) {10096C6BBB}>)

ок. оно работает. Но вопрос в том, что, поскольку обычный lisp предоставляет гораздо больше утилит для метапрограммирования и контроля компиляции, чем у clojure, существуют ли какие-либо подходящие, которые могли бы сделать «саморекурсивный let» (как я это называю) более элегантным, устраняя необходимость в уродливом хаке с незаблокированнымвызовы функций, желательно избегать изменяемого состояния (хотя я не уверен, что это вообще возможно)?

Ответы [ 2 ]

3 голосов
/ 24 октября 2019

после некоторой медитации у меня есть такое решение: 

(defmacro letr ((name val) &body body)
  (let ((f-name (gensym)))
    `(let ((,name (symbol-macrolet ((,name (funcall ,f-name ,f-name)))
                    (let* ((,f-name (once (lambda (,f-name) ,val))))
                      ,name))))
       ,@body)))

, которое фактически переписывает исходное решение с помощью symbol-macrolet

, что можноиспользуется следующим образом: 

CL-USER> (letr (fibs (make-pipe* 0 1 (pipe-map2 #'+ fibs (pipes:pipe-tail fibs))))
           (pipes:pipe-values fibs 10))
;;=> (0 1 1 2 3 5 8 13 21 34 55 . #<CLOSURE (LAMBDA () :IN PIPE-MAP2) {1001D3FCBB}>)

, который расшифровывается следующим образом: 

(LET ((FIBS
       (SYMBOL-MACROLET ((FIBS (FUNCALL #:G596 #:G596)))
         (LET* ((#:G596
                 (ONCE
                  (LAMBDA (#:G596)
                    (CONS 0
                          #'(LAMBDA ()
                              (CONS 1
                                    #'(LAMBDA ()
                                        (PIPE-MAP2 #'+ (FUNCALL #:G596 #:G596)
                                                   (PIPES:PIPE-TAIL
                                                    (FUNCALL #:G596
                                                             #:G596)))))))))))
           (FUNCALL #:G596 #:G596)))))
  (PIPES:PIPE-VALUES FIBS 10))

, конечно, его можно использовать только в довольно узком поле ситуаций, где рекурсив (funcall f f)задерживается, как в этом случае. в противном случае это приводит к бесконечному восстановлению, вызывающему поток стека. (Хотя я почти уверен, что это все равно можно улучшить)

0 голосов
/ 24 октября 2019

Если у вас есть рекурсивная функция с 2 аргументами, то у вас должна быть такая особенность, как [f arg1 arg2], а затем, используя свое решение, вы должны рекурсивно подобным (f f arg1 arg2). Вы можете сделать эту вещь короче, если вы используете вспомогательную функцию и переменную: 

(defn memo [f]
  (let [v (volatile! nil)]
    (vreset! v (memoize (fn [& args] (apply f @v args))))))

Так что теперь вы можете сделать: 

(let [f (memo (fn [this arg1 arg2] (this arg1 arg2)))] (f arg1 arg2))

Так что это делает аргумент вызова рекурсии на 1 аргумент короче,то есть вам не нужно звонить, чтобы идти (f f), просто (f).

...