Оператор `amb` как макрос или процедура? - PullRequest
Новая
       51

Оператор `amb` как макрос или процедура?

5 голосов
/ 24 апреля 2011

На этой странице есть комментарий после поста, который дает очень короткую реализацию amb как процедуры: 

(define (amb-backtrack)
  (error "no solution found"))

(define (amb . args)
  (call/cc (lambda (return)
             (let ((backtrack amb-backtrack))
               (map (lambda (x)
                      (call/cc (lambda (k)
                                 (set! amb-backtrack k)
                                 (return x))))
                    args)
               (backtrack 'fail)))))

Но я обычно вижу amb, реализованный в виде макроса - в FAQ по schemers.org, а также в книге Дорай Ситарам : 

(define amb-fail '*)

(define initialize-amb-fail
  (lambda ()
    (set! amb-fail
      (lambda ()
        (error "amb tree exhausted")))))

(initialize-amb-fail)

(define-macro amb
  (lambda alts...
    `(let ((+prev-amb-fail amb-fail))
       (call/cc
        (lambda (+sk)

          ,@(map (lambda (alt)
                   `(call/cc
                     (lambda (+fk)
                       (set! amb-fail
                         (lambda ()
                           (set! amb-fail +prev-amb-fail)
                           (+fk 'fail)))
                       (+sk ,alt))))
                 alts...)

          (+prev-amb-fail))))))

Итак - версия макроса длиннее и немного сложнее для понимания. Я не мог видеть никаких преимуществ по сравнению с версией процедуры, и, конечно, я бы предпочел использовать процедуру, а не макрос. Я что-то пропустил?

1 Ответ

6 голосов
/ 24 апреля 2011

Разница в том, что вызов процедуры всегда оценивает все аргументы. 

(amb 1 (very-expensive-computation))

при версии процедуры amb выполнит very-expensive-computation, а затем выдаст 1.Если для всех дальнейших вычислений достаточно указать 1, то вы потратили много времени на вычисления, значение результата которых никогда не используется.Еще худшие вещи случаются, как @Eli Barzilay упоминает в комментарии, когда amb используется для моделирования бесконечного недетерминизма, такого как генерация всех натуральных чисел.

Макро версия избегает этого, и поэтому ее поведениеближе к недетерминированным языкам программирования, таким как Prolog.

...