Упражнение SICP 3.52: нужен ли memo-proc с использованием Scheme (Guile)? - PullRequest
2 голосов
/ 03 мая 2019

Я делаю SICP ex 3.52. Я получаю правильные ответы на выражения «stream-ref» и «display-stream», а также получаю правильное значение «sum» после каждого выражения, данного в упражнении. Однако все это работает без использования оптимизации «memo-proc», представленной на странице 439 непосредственно перед перечисленным упражнением.

Я использую Guile в Linux, и единственным другим дополнением, которое я сделал в коде, было определение синтаксиса в верхней части кода для «cons-stream», включающее форму «задержки».

Возможно, я что-то неправильно понимаю, но я даже не вижу точки, в которой в исполнении вызывается "memo-proc". Есть ли что-то, что встроено в Guile, которое уже выполняет эту оптимизацию, обеспечиваемую "memo-proc", которая, согласно SICP, служит для реализации "задержки" в качестве специальной запоминающейся процедуры.

Вот запомненная процедура в SICP ...

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

Код для удобства ...

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
        (apply proc (map stream-car argstreams))
        (apply stream-map 
               (cons proc (map stream-cdr argstreams))))))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x) (newline) (display x))

(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
        low
        (stream-enumerate-interval (+ low 1) high))))

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter
                       pred
                       (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

И последовательность выражений для упражнения ...

(define sum 0)

(define (accum x) (set! sum (+ x sum)) sum)

(define seq
  (stream-map accum
              (stream-enumerate-interval 1 20)))

(define y (stream-filter even? seq))

(define z
  (stream-filter (lambda (x) (= (remainder x 5) 0))
                 seq))

(stream-ref y 7)

(display-stream z)

Я ожидаю результатов, перечисленных ниже, и получаю их.

(define sum 0) 
 ;; sum => 0 

 (define (accum x) 
   (set! sum (+ x sum)) 
   sum) 
 ;; sum => 0 

 (define seq (stream-map accum (stream-enumerate-interval 1 20))) 
 ;; sum => 1 

 (define y (stream-filter even? seq)) 
 ;; sum => 6 

 (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) 
                          seq)) 
 ;; sum => 10 

 (stream-ref y 7) 
 ;; sum => 136 
 ;; => 136 

 (display-stream z) 
 ;; sum => 210 
 ;; => (10 15 45 55 105 120 190 210) 

Однако я получаю эти результаты, не используя "memo-proc". Однако без оптимизации "memo-proc" я бы ожидал получить "сумму" 15 при:

(define z (stream-filter (lambda (x) (= (remainder x 5) 0)) 
                          seq)) 
;; sum => 10 

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

1 Ответ

2 голосов
/ 03 мая 2019

Я делаю упражнения с Racket (с пакетом SICP), и реализация потоков по умолчанию запоминается (см .: Запоминают ли потоки Racket свои элементы? ).Я полагаю, что Guile делает то же самое.

Возможно, поэтому в вопросе говорится "подумать", поскольку нет простого способа проверить незапамятное поведение.

В главе 4 мы реализуемСамим языком, для ex 4.18 вы можете реализовать потоки с нуля.Используя эти наивные потоки, я получаю следующий результат для этого упражнения:

Naive Streams
=============
    sum after stream-ref: 162
    sum after display-stream: 362

И после добавления реализации memo-proc в этом разделе:

Naive Streams with Memo-Proc
============================
    sum after stream-ref: 136
    sum after display-stream: 210

Обновление: На значение 'sum' в разные моменты времени выполнения влияет не только запоминание.Это также зависит от того, используете ли вы «нечетные» потоки в стиле SICP или более обычные «четные» потоки и, если вы используете современную схему, от того, используете ли вы встроенную карту и фильтр или те из текста.

+----------------+-------------+-------------+--------------+--------------+
|                | SICP Scheme | SICP Scheme | Racket With  | Racket With  |
|                |    With     |   Without   |    Text's    |   Built in   |
| sum after:     | Memoization | Memoization | Map & Filter | Map & Filter |
+----------------+-------------+-------------+--------------+--------------+
| define accum   |        0    |       0     |        0     |        0     |
+----------------+-------------+-------------+--------------+--------------+
| define seq     |        1    |       1     |        0     |        0     |
+----------------+-------------+-------------+--------------+--------------+
| define y       |        6    |       6     |        6     |        0     |
+----------------+-------------+-------------+--------------+--------------+
| define z       |       10    |      15     |       10     |        0     |
+----------------+-------------+-------------+--------------+--------------+
| stream-ref     |      136    |     162     |      136     |      136     |
+----------------+-------------+-------------+--------------+--------------+
| display-stream |      210    |     362     |      210     |      210     |
+----------------+-------------+-------------+--------------+--------------+

Подробнее о «нечетных» и «четных» потоках см. Обоснование SRFI схемы 41 .

Я добавил код, использованный выше, в GitHub .

...