Понимание сдвига / сброса в ракетке

Question

Я представляю две наивные реализации foldr в рэкет

Этот первый испытывает недостаток в надлежащем вызове хвоста и проблематичен для больших значений xs

(define (foldr1 f y xs)
  (if (empty? xs)
      y
      (f (car xs) (foldr1 f y (cdr xs)))))

(foldr1 list 0 '(1 2 3))
; => (1 (2 (3 0))

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

(define (foldr2 f y xs)
  (define (aux k xs)
    (if (empty? xs)
        (k y)
        (aux (lambda (rest) (k (f (car xs) rest))) (cdr xs))))
  (aux identity xs))

(foldr2 list 0 '(1 2 3))
; => (1 (2 (3 0)))

Смотря на racket/control Я вижу, что ракетка поддерживает первоклассные продолжения. Мне было интересно, если это было возможно / выгодно выразить вторую реализацию foldr с помощью shift а также reset, Я немного поигрался с этим, и мой мозг просто вывернулся наизнанку.

Пожалуйста, предоставьте подробное объяснение с любым ответом. Я ищу общее понимание здесь.

Answer 1

Disclaimers:

1. The “problem†of foldr you are trying to solve is actually its main feature.
2. Fundamentally, you cannot process a list in reverse easily and the best you can do is reverse it first. Your solution with a lambda, in its essence, is no different from a recursion, it’s just that instead of accumulating recursive calls on the stack you are accumulating them explicitly in many lambdas, so the only gain is that instead of being limited by the stack size, you can go as deep as much memory you have, since lambdas are, likely, allocated on the heap, and the trade off is that you now perform dynamic memory allocations/deallocations for each “recursive callâ€.

Now, with that out of the way, to the actual answer.

---

Let’s try to implement foldr keeping in mind that we can work with continuations. Here is my first attempt:

(define (foldr3 f y xs)
  (if (empty? xs)
    y
    (reset 
      (f (car xs) (shift k (k (foldr3 f y (cdr xs))))))))
  ; ^ Set a marker here.
  ;    ^ Ok, so we want to call `f`.
  ;               ^ But we don’t have a value to pass as the second argument yet.
  ;                 Let’s just pause the computation, wrap it into `k` to use later...
  ;                 And then resume it with the result of computing the fold over the tail.

If you look closely at this code, you will realise, that it is exactly the same as your foldr – even though we “pause†the computation, we then immediately resume it and pass the result of a recursive call to it, and this construction is, of course, not tail recursive.

Ok, then it looks like we need to make sure that we do not resume it immediately, but rather perform the recursive computation first, and then resume the paused computation with the recursive computation result. Let’s rework our function to accept a continuation and call it once it has actually computed the value that it needs.

(define (foldr4 f y xs)
  (define (aux k xs)
    (if (empty? xs)
      (k y)
      (reset
        (k (f (car xs) (shift k2 (aux k2 f y (cdr xs))))))))
  (reset (shift k (aux k xs))))

The logic here is similar to the previous version: in the non-trivial branch of the if we set a reset marker, and then start computing the expression as if we had everything we need; however, in reality, we do not have the result for the tail of the list yet, so we pause the computation, “package it†into k2, and perform a (this time tail-) recursive call saying “hey, when you’ve got your result, resume this paused computationâ€.

If you analyse how this code is executed, you’ll see that there is absolutely no magic in it and it works simply by “wrapping†continuations one into another while it traverses the list, and then, once it reaches the end, the continuations are “unwrapped†and executed in the reverse order one by one. In fact, this function does exactly the same as what foldr2 does – the difference is merely syntactical: instead of creating explicit lambdas, the reset/shift pattern allows us to start writing out the expression right away and then at some point say “hold on a second, I don’t have this value yet, let’s pause here and return laterâ€... but under the hood it ends up creating the same closure that lambda would!

I believe, there is no way to do better than this with lists.

Another disclaimer: I don’t have a working Scheme/Racket interpreter with reset/shift implemented, so I didn’t test the functions.