мой CPS прав?

в "The Scheme Programming Language 4th Edition" есть пример, как показано ниже: 


(define product
  (lambda (ls)
    (call/cc
      (lambda (break)
        (let f ([ls ls])
          (cond
            [(null? ls) 1]
            [(= (car ls) 0) (break 0)]
            [else (* (car ls) (f (cdr ls)))]))))))
(product '(1 2 3 4 5)) => 120

(произведение '(7 3 8 0 1 9 5)) => 0

позже он преобразуется в CPS в 3.3, как показано ниже 


(define product
  (lambda (ls k)
    (let ([break k])
      (let f ([ls ls] [k k])
        (cond
          [(null? ls) (k 1)]
          [(= (car ls) 0) (break 0)]
          [else (f (cdr ls)
                   (lambda (x)
                     (k (* (car ls) x))))])))))
(продукт '(1 2 3 4 5) (лямбда (x) x)) => 120

(произведение '(7 3 8 0 1 9 5) (лямбда (х) х)) => 0

Я хочу сделать это сам, Соответствующий CPS ниже 


 (define (product ls prod break)
    (cond
      ((null? ls)
       (break prod))
      ((= (car ls) 0)
       (break 0))
      (else
        (product (cdr ls) (* prod (car ls)) break))))
(произведение '(1 2 3 4 5) 1 (лямбда (х) х)) => 120

(произведение '(1 2 0 4 5) 1 (лямбда (х) х)) => 0

Я хочу спросить, мой CPS прав? Т Заранее спасибо!

НАИЛУЧШИЕ ПОЖЕЛАНИЯ


continuations scheme continuation-passing
person abelard2008    schedule 04.07.2012    source источник
comment
Где ваши тест-кейсы? Это не должно быть легкомысленным вопросом. Если вы не знаете, как вызвать CPS-функцию, вы упустили что-то важное.   -  person dyoo    schedule 05.07.2012
comment
Кроме того, вы должны отметить, что функция, которую вы CPSed, не является исходной функцией продукта, а написана со стандартным аккумулятором. (define (pl acc) (if (null? l) acc (p (cdr l) (* acc (car l)))) — это не совсем та функция, которую вы преобразовали, но она близка. ( Мое определение f просто опускает ранний переход, когда мы достигаем нуля.) В любом случае, функция, которую вы преобразовали, продемонстрировала итеративную рекурсию, и вы можете видеть это, потому что ваша CPS-версия этого не делает. необходимо построить новые продолжения.   -  person dyoo    schedule 05.07.2012
comment
исходный случай здесь: scheme.com/tspl4/further.html# ./дальше:h4   -  person abelard2008    schedule 09.07.2012

Ответы (1)


arrow_upward
1
arrow_downward

Я думаю, что это правильная реализация:

(define inside-product #f)  ;; to demonstrate the continuation

(define (product ls prod break)
  (cond
    ((null? ls)
     (begin
       (set! inside-product prod)
       (prod 1)))
    ((= (car ls) 0)
     (break 0))
    (else
     (product (cdr ls) (lambda (x) (prod (* (car ls) x))) break))))

(define identity (lambda (x) x))

Идея CPS состоит в том, чтобы отслеживать рекурсию.

> (product (list 1 2 3) identity identity)
6
> (inside-product 4)
24
person Rajesh Bhat    schedule 04.07.2012
comment
К сожалению, я должен -1 это: set не используется! в исходном коде, и использование мутации здесь запутывает вопросы. - person dyoo; 05.07.2012
comment
Я использовал набор! специально, чтобы продемонстрировать продолжение. Когда достигнут конец списка, значение внутреннего продукта устанавливается в продолжение. Таким образом, после выполнения процедуры продукта, как показано в примере, значение внутреннего продукта устанавливается равным (лямбда (х) ((лямбда (х) ((лямбда (х) (идентичность (* 1 х))) ( * 2 х))) (* 3 х))) - person Rajesh Bhat; 05.07.2012
comment
Хммм ладно. Вопрос, который задал первоначальный вопросник, по-прежнему неоднозначен, поскольку ему или ей нужно сказать, какая функция была преобразована в CPS. Насколько я могу судить, prod должен быть аккумулятором в исходном вопросе. Тем не менее, в вопросе нет пре-CPS-преобразования оригинального исходного кода, который соответствует использованию prod таким образом. Так что чего-то не хватает в вопросе. - person dyoo; 07.07.2012
comment
В моем первоначальном вопросе prod — это число 1, поэтому я могу назвать продукт следующим образом: (product '(1 2 3 4 5) 1 (лямбда (x) x)) => 120, может быть, мое понимание CPS такое неправильно, Где я могу изучить CPS шаг за шагом, Заранее спасибо! - person abelard2008; 09.07.2012
comment
Вы можете посмотреть такие учебники, как «Языки программирования: применение и интерпретация», а также «Основы языков программирования». В обоих есть главы о CPS, если я правильно помню. Google для PLAI, и вы должны найти первый учебник в Интернете. - person dyoo; 09.07.2012