пусть vs определит использование в продолжениях - PullRequest
Новая
       60

пусть vs определит использование в продолжениях

0 голосов
/ 03 сентября 2018

Я пытался понять выполнение call / cc в этом примере: 

(let ((x (call/cc (lambda (k) k))))
    (x (lambda (ignore) "hi")))

, что дает значение "hi".

Выполнение описывается в документ как:

Возьмите значение, свяжите его с x и примените значение x к значению (лямбда (игнорировать) "привет").

Я могу понять, что продолжение, зафиксированное в let , будет означать «Возьми значение, свяжи его с x», потому что это то, что let делает, но НЕ «применяет значение х "часть.

Итак, я ожидал, что результат будет просто , привязывающим x к (lambda (ignore) "hi"), а не применяющим it.

Например, define работает как положено: 

(define x (call/cc (lambda (k) k)))
(x (lambda (ignore) "hi"))

Он определяет x как это значение, но не применяется it.

Может ли кто-нибудь объяснить разницу между let и , определяющими в этом случае?

Вероятно, объяснение этого также поможет понять, что происходит: 

(let ((x (call/cc (lambda (k) k)))) (+ (x 1) 1))

Я ожидал, что он свяжет x с 1 и просто оценит до 2, но он говорит, что ожидает процедуру .

РЕДАКТИРОВАТЬ: Я считаю, что работа , что еще предстоит сделать, на самом деле bind x и оценивает выражение let также. В этом случае это имеет смысл. Кроме того, это означает, что (let ((x (call/cc (lambda (k) k)))) (+ (x 1) 1)) никогда нельзя заставить работать.

РЕДАКТИРОВАТЬ: Действительно, так оно и работает. Вы можете посмотреть это видео, которое объясняет этот пример. Я думаю, что это можно неофициально суммировать, так как «let» - это больше, чем «define» в том смысле, что оно должно выполнять и выражение.

Ответы [ 3 ]

0 голосов
/ 03 сентября 2018 
(let ((x (call/cc (lambda (k) k))))    ; binds x to the value of (call/cc ...)
    (x (lambda (ignore) "hi")))        ; applies x to the value of (lambda ...)

переводится как 

(let ((x #f))
  (set! x (call/cc (lambda (k) k)))
  (x (lambda (ignore) "hi")))

, который становится 

(let ((x #f))
  (set! x (lambda (ignore) "hi"))
  (x (lambda (ignore) "hi")))

и код с define переводит то же самое (в целях интерпретации этого фрагмента кода; с внутренним, не только верхнего уровня define s).

И let, и define оценивают выражение, чтобы узнать значение для привязки переменной - о чем вы спрашивали, как будто они как-то отличаются в этом отношении. Это не так.

Ваш третий фрагмент переводится как 

(let ((x #f))
  (set! x (call/cc (lambda (k) k)))
  (+ (x 1) 1))

, который становится 

(let ((x #f))
  (set! x 1)
  (+ (x 1) 1))

, который становится 

(let ((x #f))
  (+ (1 1) 1))
0 голосов
/ 04 сентября 2018

TL; DR: Реальная разница между define и let заключается в выражениях программы верхнего уровня, потому что define может быть сделано только один раз для идентификатора, и обычно между запросами верхнего уровня имеются запросы продолжения.

Я собираюсь использовать CPS в этом ответе. Определения для общих процедур, которые я использую: 

;; returns argument
(define halt values) 

;; call/cc in CPS version
(define (call/cc-k f k)
  (f (lambda (v k-ignore) (k v)) k))

let и define в процедуре делают подобные вещи: 

(let ()
  (define x (call/cc (lambda (k) k)))
  (x (lambda (ignore) "hi")))

; == 

(let ()
  (letrec ((x (call/cc (lambda (k) k)))
    (x (lambda (ignore) "hi")))

И то же самое в let становится: 

(let ()
  (let ((x 'undefined))
    (set! x (call/cc (lambda (k) k)))
    (x (lambda (ignore) "hi"))))

То же самое в CPS (хотя я пропустил обновление привязки, так как в этом коде теневое копирование тоже самое: 

((lambda (x k)
   (call/cc-k
    (lambda (k2 real-k) (real-k k2))
    (lambda (x)
      (x (lambda (ignore k2) (k2 "hi")) k))))
 'undefined halt)

;; ===

((lambda (x k)
   ((lambda (f5 k5) (f5 (lambda (v k-ignore) (k5 v)) k5))
    (lambda (k3 real-k) (real-k k3))
    (lambda (x)
      (x (lambda (ignore k2) (k2 "hi")) k))))
 'undefined halt)

;; ===

((lambda (x k)
   (define hi-k (lambda (x) (x (lambda (ignore k2) (k2 "hi")) k)))
   ((lambda (f5 k5) (f5 (lambda (v k-ignore) (k5 v)) k5))
    (lambda (k3 real-k) (real-k k3))
    hi-k))
 'undefined halt)


;; === this is starting to look like a combinator :-)

((lambda (x k)
   ((lambda (ignore k2) (k2 "hi"))
    (lambda (ignore k2) (k2 "hi")) k))
 'undefined halt)

;; ===

((lambda (x k)
   (k "hi"))
 'undefined halt)

;; ===

(halt "hi")

Пока ваша let версия делает это: 

(let ((x (call/cc (lambda (k) k))))
    (x (lambda (ignore) "hi")))


;;; === in terms of lambda instead of let

((lambda (x)
   (x (lambda (ignore) "hi")))
 (call/cc (lambda (k) k)))


;;; === in CPS

(call/cc-k
 (lambda (k real-k) (real-k k))
 (lambda (x)
   (x (lambda (ignore k2) (k2 "hi")) halt)))

;;; ===

(define hi-k (lambda (x) (x (lambda (ignore k2) (k2 "hi")) halt)))
((lambda (k real-k) (real-k k)) (lambda (v k-ignore) (hi-k v)) hi-k))


;;; ===

((lambda (ignore k2) (k2 "hi"))
 (lambda (ignore k2) (k2 "hi"))
 halt)

;;; ===

(halt "hi")

define, используемый на верхнем уровне, сильно отличается , и поскольку define нельзя сделать для одной и той же переменной дважды, ваш код в недопустимом коде Схемы для оценки верхнего уровня. Чтобы исправить это, мы переписываем его так: 

(define x #f)
(set! x (call/cc (lambda (k) k)))
(x (lambda (ignore) "hi"))

Я пропущу define и напишу CPS в продолжение: 

(call/cc-k
 (lambda (k real-k) (real-k k))
 (lambda (v)
   (set!-k x
           v
           (lambda (undefined)
             (x (lambda (ignore k2) (k2 "hi")) halt)))))

;;; ===

(define set-k (lambda (v)
                (set!-k x
                        v
                        (lambda (undefined)
                          (x (lambda (ignore k2) (k2 "hi")) halt)))))
(call/cc-k
 (lambda (k real-k) (real-k k))
 set-k)

;; ===

(define set-k (lambda (v)
                (set!-k x
                        v
                        (lambda (undefined)
                          (x (lambda (ignore k2) (k2 "hi")) halt)))))
((lambda (k real-k) (real-k k))
 (lambda (v k-ignore) (set-k v))
 set-k)


;; ===

(define set-k (lambda (v)
                (set!-k x
                        v
                        (lambda (undefined)
                          (x (lambda (ignore k2) (k2 "hi")) halt)))))
(set-k (lambda (v k-ignore) (set-k v)))

;; ===

(define set-k (lambda (v)
                (set!-k x
                        v
                        (lambda (undefined)
                          (x (lambda (ignore k2) (k2 "hi")) halt)))))
(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          (x (lambda (ignore k2) (k2 "hi")) halt)))

;; ===

(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          ((lambda (v k-ignore) (set-k v)) (lambda (ignore k2) (k2 "hi")) halt)))

;; ===

(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          (set!-k x
                  (lambda (ignore k2) (k2 "hi"))
                  (lambda (undefined)
                    (x (lambda (ignore k2) (k2 "hi")) halt)))))

;;; ===

(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          (set!-k x
                  (lambda (ignore k2) (k2 "hi"))
                  (lambda (undefined)
                    ((lambda (ignore k2) (k2 "hi")) (lambda (ignore k2) (k2 "hi")) halt)))))


;;; ===

(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          (set!-k x
                  (lambda (ignore k2) (k2 "hi"))
                  (lambda (undefined)
                    (halt "hi")))))

;;; ===

(halt "hi")

Однако это странно, поскольку, если вы попробуете это, вы ничего не получите вообще. Причина этого заключается в том, что выражения верхнего уровня разделены приглашениями продолжения. Таким образом, продолжение, пойманное call/cc для каждого оператора верхнего уровня, равно halt вместо остальной части программы. Давайте попробуем это: 

(call/cc-k
 (lambda (k real-k) (real-k k)) 
 (lambda (v)
   (set!-k x
           v
           halt)))

(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

(define set-k
  (lambda (v)
   (set!-k x
           v
           halt)))
((lambda (k real-k) (real-k k)) (lambda (v k-ignore) (set-k v)) set-k)
(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

(set-k (lambda (v k-ignore) (set-k v)))
(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

((lambda (v)
   (set!-k x
           v
           halt))
 (lambda (v k-ignore) (set-k v)))
(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
((lambda (v k-ignore) (set-k v))
 (lambda (ignore k2) (k2 "hi"))
 halt)

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
(set-k (lambda (ignore k2) (k2 "hi")))

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
((lambda (v)
   (set!-k x
           v
           halt))
 (lambda (ignore k2) (k2 "hi")))

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
(set!-k x (lambda (ignore k2) (k2 "hi")) halt)

Из-за подсказок продолжения полное продолжение не выполняется, и единственное, что на самом деле делает код, это установить x дважды.

Ваш последний пример не работает, потому что x переключился между продолжением и числом. 

(let ((x (call/cc (lambda (k) k))))
  (+ (x 1) 1))

;; in CPS

(call/cc-k
 (lambda (k real-k) (realk k))
 (lambda (x)
   (x 1 (lambda (v1)
          (+-k v1 1 halt)))))

;; ===

(define k (lambda (x)
            (x 1 (lambda (v1)
                   (+-k v1 1 halt)))))
((lambda (k real-k) (realk k))
 (lambda (v k-ignore) (k v))
 k)


;; ===

(define k (lambda (x)
            (x 1 (lambda (v1)
                   (+-k v1 1 halt)))))
(k (lambda (v k-ignore) (k v)))

;; ===

((lambda (x)
   (x 1 (lambda (v1)
          (+-k v1 1 halt))))
 (lambda (v k-ignore) (k v)))


;; ===

((lambda (v k-ignore) (k v))
 1
 (lambda (v1)
   (+-k v1 1 halt)))

;; ===

(k 1)

;; ===

((lambda (x)
            (x 1 (lambda (v1)
                   (+-k v1 1 halt))))
 1)


;; ===
(1 1 (lambda (v1) (+-k v1 1 halt)))

ERROR: 1 is not a procedure!

YMMV и, следовательно, все это может быть шумом, но во-вторых, call/cc просто смотрит на CPS-версию кода без необходимости писать CPS, понимая, как это работает, довольно легко. Удачного взлома!

0 голосов
/ 03 сентября 2018 
(let ((x (call/cc (lambda (k) k))))
    (x (lambda (ignore) "hi")))

call/cc принимает один аргумент, функцию, которая принимает один аргумент, и вызывает эту функцию. Переданный ему аргумент (продолжение) сам по себе является функцией одного аргумента, который при вызове заставляет call/cc возвращать свой аргумент. Если эта функция никогда не вызывается, call/cc возвращает любое значение, которое возвращает ее аргумент. Итак ... 

(let ((x (call/cc (lambda (k) k))))

В этот момент x содержит продолжение, которое при вызове со значением заставляет call/cc возвращать это значение. Даже если call/cc уже вышел, вызов этого продолжения заставит его снова перейти к этой точке. 

(x (lambda (ignore) "hi")))

И теперь это продолжение вызывается лямбда (назовите его A), который принимает один аргумент и возвращает «привет». Таким образом, он возвращается к 

    (let ((x (call/cc (lambda (k) k))))

и x теперь привязан к этой лямбде A, поскольку вызов продолжения действует как call/cc только что вернул его. 

(x (lambda (ignore) "hi")))

и теперь x, который является A, вызывается, игнорирует его аргумент и возвращает «привет». Пример использования define работает аналогично: x привязывается к одному значению, а затем, когда вызывается это значение, x привязывается к новому значению и вызывается с этим новым значением.

...