Как вы делаете letcc в Clojure?

Question

В книге The Seasoned Schemer - пишет автор следующий код:

(define intersectall 
    (lambda (lset) 
    (letcc hop 
     (letrec 
      ((A (lambda (lset) 
       (cond 
        ((null? (car lset)) (hop (quote()))) 
        ((null? (cdr lset)) (car lset)) 
        (else 
        (intersect (car lset) 
           (A (cdr lset)))))))) 
     (cond 
      ((null? lset) (quote())) 
      (else (A lset))))))) 

Здесь потенциально, как это может выглядеть в Clojure:

(defmacro letcc 
    [name & body] 
    `(letfn [(~name [arg#] 
      (throw (ex-info (str '~name) {:name '~name :value arg#})))] 
    (try ~@body 
      (catch clojure.lang.ExceptionInfo e# 
      (if (= '~name (:name (ex-data e#))) 
       (:value (ex-data e#)) 
       (throw e#)))))) 

(defn intersectall 
    [lset] 
    (letcc hop 
    (letfn [(A [lset] 
      (cond (empty? (first lset)) 
        (hop()) 
        (empty? (rest lset)) 
        (first lset) 
        :else 
        (intersect (first lset) (A (rest lset)))))] 
    (cond (empty? lset) 
      () 
      :else 
      (A lset))))) 

Мой вопрос: Как вы letcc в Clojure ?

Answer 1

фона

Ядра Clojure язык не поддерживает первый класс продолжений. Это и тот факт, что JVM не обеспечивает способ захвата текущего продолжения, означает, что нет способа реализовать letcc, что является удовлетворительным для всех ситуаций.

Однако в некоторых ситуациях можно реализовать продолжения. В частности, если у вас есть весь код (то есть код, в котором вы должны записывать продолжения), вы можете использовать стиль продолжения-прохождения (CPS). В принципе, вы добавляете дополнительный параметр для каждой функции. Этот параметр является функцией, которая представляет собой продолжение этого вызова. Вы «возвращаете» значение, вызывая функцию продолжения. Конечно, этот стиль - это боль, чтобы писать самостоятельно - но, к счастью, это преобразование, которое мы можем легко применить к конкретному коду с помощью макросов.

Сам по себе CPS непригоден для платформ, которые не выполняют оптимизацию хвостовых вызовов (TCO). Поскольку последний шаг любой функции в CPS заключается в вызове другой функции, без TCO стек быстро переполняется, за исключением самых тривиальных вычислений. Эта проблема может быть решена путем использования thunking и trampolining.

Solutions

Как я упоминал выше, вы можете написать превратить свой собственный КПС с помощью макросов. Тем не менее, я бы пригласил вас проверить мою библиотеку pulley.cps, которая уже делает это за вас. Есть альтернативы, но, насколько я знаю, pulley.cps единственная библиотека Clojure, которая обеспечивает все следующие:

• call-cc/let-cc
• Бесшовных звонков между «родным» (нетрансформированным) и трансформируют код
• Exception (try/catch/finally) поддержка
• binding формы (они правильно хвостовой рекурсией тоже!)
• Позволяет обеспечить CPS Versio п существующей собственной функции (это необходимо, если вы хотите, чтобы захватить продолжение в рамках этой функции)

Альтернатив включают в себя:

• delimc предоставляет библиотеку для делимитированных продолжений. Это не выглядит очень полным (например, binding не работает, поскольку он не понимает блок try/finally) и не был затронут через 4 года.
• algo.monads является монадной библиотекой для Clojure. Существует сильная и интересная связь между монадами и продолжениями, а algo.monads - продолжение монады.Хотя монадический стиль не совсем такой же понятен, он имеет то преимущество, что делает эффект более явным, что может помочь в инкапсуляции кода, который использует эффекты управления из кода, который этого не делает. Плюс, do обозначение (например, макрос domonad) сильно размывает линии между прямым и монадическим стилем.

Answer 2

Продолжение, пойманное (letcc hop ...) в вашем примере, используется как «продолжение вверх». Вместо этого можно было бы использовать имя return: (letcc return ... (return() ...). Когда вызывается продолжение с именем return, все выражение letcc оценивается значением, заданным return, которое затем возвращается в результате intersectall.

Это означает, что 1. продолжение продолжается (мы получаем return) и 2. продолжение используется только один раз. Когда эти условия соблюдены, можно реализовать letcc в терминах try и catch, как вы это сделали.

Так как я вижу это, написав макрос letcc, вы ответили на свой вопрос.

Теперь, когда Натан Дэвис упоминает, что есть другие варианты продолжения, но Clojure не поддерживает их напрямую.

Примечание: Существует связанный с этим вопрос здесь: The Seasoned Schemer, letcc and guile