4.3.1 · 명시적인 대안

첫 성공에서 멈추지 않고 모든 성공을 남긴다.

평가기에서 대안을 데이터로 다루면 모든 유한한 선택을 검사하고 성공한 결과를 모두 반환할 수 있습니다.

생각해 볼 질문

성공 하나 뒤에도 남은 대안을 유지하면 평가가 어떻게 달라질까요?

유한한 탐색 공간을 명시적인 선택 리스트로 표현하기
요구 조건을 적용하기 전에 각 대안 평가하기
술어를 만족하는 모든 값 남기기
탐색 순서를 숨기지 않고 조합 열거하기

첫 번째 탐색은 인용된 식 트리를 받습니다. evaluate는 한 번에 트리 하나씩 해석하고, search는 그 결과 값에 acceptable?을 적용하며 실패와 성공 뒤에도 스캔을 계속합니다. 섣부른 확정으로 남은 대안을 버리지 않습니다.

두 번째 프로그램은 두 선택 위치를 명시적으로 드러냅니다. scan-y는 하나의 x에 대해 모든 y를 검사하고, scan-x는 모든 x에 대해 그 작업을 반복합니다. 제곱의 합이 25가 되는 모든 쌍을 반환하는 과정은 유한한 비결정적 탐색을 리스트를 생성하는 평범한 제어로 드러냅니다.

SICP 코드UTF-8 686 / 1,048,576바이트

(begin
  (define (evaluate expression)
    (if (number? expression)
        expression
        (let ((operator (car expression))
              (left (evaluate (cadr expression)))
              (right (evaluate (caddr expression))))
          (cond ((eq? operator '+) (+ left right))
                ((eq? operator '*) (* left right))))))
  (define (search alternatives acceptable?)
    (if (null? alternatives)
        '()
        (let ((value (evaluate (car alternatives))))
          (if (acceptable? value)
              (cons value (search (cdr alternatives) acceptable?))
              (search (cdr alternatives) acceptable?)))))
  (search '((+ 1 2) (* 2 3) (+ 4 5) (* 4 4)) odd?))

예제

결과—

출력: —
값: —
진단: —

실행 추적0 / 0 개 이벤트

예상 결과

첫 프로그램은 (3 9)를 반환합니다. 두 번째 프로그램은 ((3 4) (4 3))을 반환합니다.

실행 추적에서 볼 점

첫 번째 실행에서는 각 술어 판단 전에 evaluate를 따라가고 성공 뒤에도 남은 대안에 대해 재귀가 계속되는지 확인하세요. 두 번째 실행에서는 (1 1)부터 (4 4)까지 중첩된 선택 순서를 따라가며 허용된 두 쌍을 모두 찾으세요.

직접 해보기

프로그램을 수정하고 결과를 비교해 보세요.

첫 번째 술어를 even?으로 바꾸고 원래 대안 순서대로 유지되는 모든 값을 예상하세요.

힌트 보기

먼저 네 식 트리를 모두 평가하세요. 성공한 값이 있어도 스캔은 멈추지 않습니다.

이 수업 완료하기

이 장의 총 23개 수업 중 0개 완료0%