Arc Forum | Better ways to implement protect (dynamic-wind)?

Arc Forum

Better ways to implement protect (dynamic-wind)?

3 points by dido 4734 days ago | 5 comments

While working on implementing this feature for the Arcueid interpreter, it astounded me just how messy protect made the once-elegant ccc, on-err, and err functions. I basically had to take note of all functions registered by protect on the continuations that used them, and then stacked up these functions for execution whenever a continuation was called or an exception was raised, and doing this basically tripled the number of lines of code needed to implement ccc and exceptions, and I'm left with the feeling that there must be a better way to implement it.

Googling implementations for dynamic-wind (which is basically what Arc's protect is all about) comes up with links to something called the Hanson-Lamping algorithm, which appears to be only vaguely referenced as an unpublished manuscript. There's a brief appendix that purports to describe the algorithm in an edition of the Scheme48 manual:

http://www.cs.hmc.edu/~fleck/envision/scheme48/meeting/node7.html

but the code does not actually execute either the before or after thunks under any circumstances of code execution if I understand the code correctly, and the explanation given is extremely sketchy, at least to me. It's certainly not enough for me to understand the algorithm well enough to be able to implement it.

I'd like to see a proper explanation of the ideas behind this algorithm, or other alternative algorithms for implementing dynamic-wind with call/cc and exception primitives that are otherwise unaware of it.

2 points by rocketnia 4733 days ago | link

Here's some indentation for that code:

  (define *here* (list #f))
  (define original-cwcc call-with-current-continuation)
  
  (define (call-with-current-continuation proc)
    (let ((here *here*))
      (original-cwcc
        (lambda (cont)
          (proc (lambda results
                  (reroot! here)
                  (apply cont results)))))))
  
    (define (dynamic-wind before during after)
    (let ((here *here*))
      (reroot! (cons (cons before after) here))
      (call-with-values during
        (lambda results
          (reroot! here)
          (apply values results)))))
  
  (define (reroot! there)
    (if (not (eq? *here* there))
      (begin (reroot! (cdr there))
             (let ((before (caar there)) (after (cdar there)))
               (set-car! *here* (cons after before))
               (set-cdr! *here* there)
               (set-car! there #f)
               (set-cdr! there '())
               (set! *here* there)
               (before)))))

For easier reading, here's the same thing in Arc (untested):

  (= here* '(no-befores-or-afters . nil))
  (= orig-ccc ccc)
  
  ; This overwrites the original.
  (def ccc (body)
    (let here here*
      (orig-ccc:fn (cont)
        
        ;; With multiple value return
        ;(body:fn results
        ;  reroot.here
        ;  (apply cont results))
        
        ; Without
        (body [do reroot.here
                  cont._])
        )))
  
  (def dynamic-wind (before during after)
    (let here here*
      (reroot:cons (cons before after) here)
      
      ;; With multiple value return
      ;(call-with-values during
      ;  (fn results
      ;    reroot.here
      ;    (apply values results)))
      
      ; Without
      (do1 (during)
           reroot.here)
      
      ))
  
  (def reroot (there)
    (unless (is here* there)
      (reroot cdr.there)
      (let ((before . after) . ignored-parent) there
        (= car.here* (cons after before))
        (= cdr.here* there)
        (= car.there 'no-befores-or-afters)
        (= cdr.there nil)
        (= here* there)
        (before)))))

This is exactly the same technique I mentioned in the other thread. The language originally doesn't support dynamic-wind, but this code hides the original 'ccc and replaces it with one that manually traverses a global stack of 'dynamic-wind handlers. Good to know this is called Hanson-Lamping. :-p

If the language has built-in exceptions, this particular implementation isn't friendly with them. It doesn't do anything to intercept them! ^_^ To repair this in Arc, we would replace (do1 ...) with (after ...) above.

On the other hand, a language that defines 'dynamic-wind this way can implement exceptions in terms of the replaced 'ccc.

-----

1 point by dido 4733 days ago | link

Thanks for that... The Scheme version has even more parentheses and was much harder to understand. I'm starting to see how the algorithm works, and I'll see if this comes out cleaner than the kludge I came up with and incorporated into Arcueid 0.0.5. What I plan to do is restore the very simple continuation invocation it used to have, then wrap it up that way. Exceptions are of course simple enough to implement by using ccc, and implementing them on top of the ccc that supports dynamic-wind should provide us with exceptions that support dynamic-wind as well.

By the way, I haven't seen the orig-cc:fn idiom before. So even a special form like fn works with ssyntax. So I suppose it would not do to just expand it into ((compose orig-cc fn) ...), and we have to actually make it a real function composition.

-----

2 points by Pauan 4732 days ago | link

"So I suppose it would not do to just expand it into ((compose orig-cc fn) ...), and we have to actually make it a real function composition."

Not so. If you look at line 29 in ac.scm you'll see this:

  ; the next three clauses could be removed without changing semantics
  ; ... except that they work for macros (so prob should do this for
  ; every elt of s, not just the car)
  ((eq? (xcar (xcar s)) 'compose) (ac (decompose (cdar s) (cdr s)) env))
  ((eq? (xcar (xcar s)) 'complement)
   (ac (list 'no (cons (cadar s) (cdr s))) env))
  ((eq? (xcar (xcar s)) 'andf) (ac-andf s env))

For those not familiar with the Arc compiler, what it's doing is basically these transformations:

  ((compose foo bar) 1) -> (foo (bar 1))

  ((complement foo) 1)  -> (no (foo 1))

  ((andf foo bar) 1)    -> (let g1 1 (and (foo g1) (bar g1)))

If you wish for compose, complement, and andf to work on macros and special forms like fn, your compiler will need to do a similar transformation. The catch is that this transformation only works in functional position:

  (map no:do (list 1 2 3 nil nil)) ;; doesn't work

It's all very hacky and whatnot, macros aren't very clean at all in Arc. The other catch is that it hardcodes the symbols 'compose, 'complement, and 'andf, but my Nu compiler fixes that.

-----

3 points by dido 4732 days ago | link

I figured that out and my compiler now does that transformation for compose in:

https://github.com/dido/arcueid/commit/f998de0ba562103cee6a7...

Will see if we can't apply the same for complement and andf in the same way. :)

-----

1 point by rocketnia 4733 days ago | link

As a follow-up editorial...

The complex interactions are actually all natural consequences of a language that doesn't even have dynamic wind and exceptions in the first place. Because with 'ccc, people can and probably will build these systems themselves, multiple times, in ways that break each other and threaten to fragment the community... ultimately leading to their standardization. IMO, a procedural language with 'ccc is a dubious start if the 100-year goal is a simpler language than Scheme.

-----