CODEWITHSUNDEEP
immutabilitycallcc
Aly
Aly

Reputation: 935

call/cc iterators without mutability

I'm working in a Scheme-like language which completely lacks any forms of mutable cells (such as Scheme's set! or OCaml's ref). Ideally, I want to implement generators so that the "result" of the generator is just it returning normally. This means generators and iterators would be typed something like (pseudo-code):

Generator (receive : Type) (yield : Type) (return : Type) = Fix(fun (nextStep : Type) =>
  (receive, (yield, nextStep) -> ⊥) -> return
)

Iterator (yield : Type) = Generator ⊤ yield ⊤

In Scheme, I can implement such an iterator that yields numbers 0 through 10:

(define (seqTo10 y)
  (define (go i yl)
    (if (< i 10)
        (go (+ i 1) (call/cc (lambda (cont) (yl (list i cont)))))))
  (go 0 y))

The problem becomes consuming the results of these iterators without set!. If I try something like:

(define (seqSum seq)
  (call/cc (lambda (return)
             (define (sum t n)
               (apply
                (lambda (i x) (sum (+ t i) x))
                (call/cc (lambda (k)
                           (n k)
                           (return t)))))
             (sum 0 seq))))

Because in this situation, n is a continuation (representing the next step of the iterator), when go exits normally, it returns to the first frame outside a looped call/cc: the frame where t is 0. This causes (seqSum seqTo10) to be 0, rather than my desired 45.

My question is: can I keep this behavior for Generators and Iterators (specifically where normal termination of the generator/iterator specifies the terminal value), but consume and accumulate their results without set!?

Upvotes: 0

Views: 94

Answers (0)

Related Questions