4.3.3 · Примеры недетерминированных программ

Головоломки на amb с возвратом при неудаче

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

Вопрос для размышления

Как программа может описывать допустимые ответы, когда протокол продолжений управляет порядком вариантов и поиском с возвратом?

Выбор одного значения с сохранением оставшихся вариантов в продолжении неудачи
Отклонение частичного или полного назначения вызовом текущего продолжения неудачи
Выражение ограничений различия и соседства независимо от управления перечислением
Сбор каждого конечного решения возобновлением после успеха
Повторное использование того же протокола choose для задачи числового поиска
Разделение конечного перечисления в глубину и справедливого бесконечного поиска

choose передает первый вариант в succeed и упаковывает оставшиеся варианты как next-failure. Каждый вложенный выбор этажа поэтому несет продолжение, способное возобновить работу точно на ближайшем неопробованном варианте. Когда выбраны пять этажей, предикат ограничения либо сообщает об одном решении, либо вызывает это продолжение. Решатель содержит факты головоломки, а choose и collect-solutions содержат протокол поиска.

Программа для пифагоровых троек повторно использует те же продолжения для числовых выборов. Ограничения упорядочения исключают перестановки, а равенство квадратов принимает две тройки в конечном диапазоне от 1 до 10. Оба примера используют конечные списки с поиском в глубину и фиксируют каждый выбор, достигнутый в этом диапазоне.

Код SICP2,098 из 1,048,576 байт UTF-8

(begin
  (define (choose options succeed fail)
    (if (null? options)
        (fail)
        (succeed
          (car options)
          (lambda ()
            (choose (cdr options) succeed fail)))))
  (define (distinct? values)
    (cond ((null? values) #t)
          ((member (car values) (cdr values)) #f)
          (else (distinct? (cdr values)))))
  (define (absolute value)
    (if (< value 0) (- value) value))
  (define floors '(1 2 3 4 5))
  (define (search succeed fail)
    (choose floors
      (lambda (baker fail-baker)
        (choose floors
          (lambda (cooper fail-cooper)
            (choose floors
              (lambda (fletcher fail-fletcher)
                (choose floors
                  (lambda (miller fail-miller)
                    (choose floors
                      (lambda (smith fail-smith)
                        (if
                          (and
                            (distinct?
                              (list baker cooper fletcher miller smith))
                            (not (= baker 5))
                            (not (= cooper 1))
                            (not (= fletcher 5))
                            (not (= fletcher 1))
                            (> miller cooper)
                            (not (= (absolute (- smith fletcher)) 1))
                            (not (= (absolute (- fletcher cooper)) 1)))
                          (succeed
                            (list (list 'baker baker)
                                  (list 'cooper cooper)
                                  (list 'fletcher fletcher)
                                  (list 'miller miller)
                                  (list 'smith smith))
                            fail-smith)
                          (fail-smith)))
                      fail-miller))
                  fail-fletcher))
              fail-cooper))
          fail-baker))
      fail))
  (define solutions '())
  (search
    (lambda (solution next-alternative)
      (set! solutions (append solutions (list solution)))
      (next-alternative))
    (lambda () solutions)))

(begin
  (define (choose options succeed fail)
    (if (null? options)
        (fail)
        (succeed
          (car options)
          (lambda ()
            (choose (cdr options) succeed fail)))))
  (define (distinct? values)
    (cond ((null? values) #t)
          ((member (car values) (cdr values)) #f)
          (else (distinct? (cdr values)))))
  (define (absolute value)
    (if (< value 0) (- value) value))
  (define floors '(1 2 3 4 5))
  (define (search succeed fail)
    (choose floors
      (lambda (baker fail-baker)
        (choose floors
          (lambda (cooper fail-cooper)
            (choose floors
              (lambda (fletcher fail-fletcher)
                (choose floors
                  (lambda (miller fail-miller)
                    (choose floors
                      (lambda (smith fail-smith)
                        (if
                          (and
                            (distinct?
                              (list baker cooper fletcher miller smith))
                            (not (= baker 5))
                            (not (= cooper 1))
                            (not (= fletcher 5))
                            (not (= fletcher 1))
                            (> miller cooper)
                            (not (= (absolute (- smith fletcher)) 1))
                            (not (= (absolute (- fletcher cooper)) 1)))
                          (succeed
                            (list (list 'baker baker)
                                  (list 'cooper cooper)
                                  (list 'fletcher fletcher)
                                  (list 'miller miller)
                                  (list 'smith smith))
                            fail-smith)
                          (fail-smith)))
                      fail-miller))
                  fail-fletcher))
              fail-cooper))
          fail-baker))
      fail))
  (define solutions '())
  (search
    (lambda (solution next-alternative)
      (set! solutions (append solutions (list solution)))
      (next-alternative))
    (lambda () solutions)))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Поиск по этажам возвращает (((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))). Числовой поиск возвращает ((3 4 5) (6 8 10)).

На что обратить внимание в трассе

Проследите один вызов choose до его замыкания next-failure, затем найдите ограничение, которое отклоняет текущее полное назначение и возобновляет работу с ближайшего варианта. При успехе отличайте сохранение решения от вызова next-alternative для продолжения перечисления. Сравните работу этого протокола для символьных назначений этажей и для числовых троек.

Попробуйте сами

Измените программу и сравните результат.

Добавьте головоломку о яхтах или задачу о сумме четырех переменных с помощью той же процедуры choose. Зафиксируйте, сколько полных кандидатов доходит до финального ограничения до и после переноса безопасных ограничений на более ранний этап.

Показать подсказку

Ограничение может вызвать текущее продолжение неудачи, как только становятся известны все нужные ему значения. Более раннее отклонение меняет объем работы, а не набор ответов.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%