[r6rs-discuss] [Formal] Ambiguous call/cc-behaviour of list
r6rs at jdev.users.panix.com
Wed Oct 4 15:14:54 EDT 2006
On Thu, Sep 28, 2006 at 07:19:35PM -0400, AndrevanTonder wrote:
> Consider fully specifying the list operations by inlining a reference
> implementation for each as part of the descriptive text. This should
> be easy, since these reference specifications are all very short.
> I do not know if there is any reliable way of fixing the ambiguity
> via prose.
The implementation would still be allowed to apply the procedure to the
list elements in any order.
So, let's say there's some snazzy parallelizing implementation, where
the order of evaluation can change from one moment to the next (system
loads, phase of the moon, &c). Does a continuation have to remember
which elements are and aren't considered to have been applied yet, and
replay the same alleged order of execution if used multiple times?
If it doesn't, then consider this transformation on currently valid
implementations of map:
(define (cmap map)
(lambda (f . ls)
(map (lambda (x)
(if (car x) (caar x)
(let ((v (apply f (cdr x)))) (set-car! x (list v)) v)))
(apply map (lambda xs (cons #f xs)) ls))))
That is, if a continuation is reused, the element in question will be
considered to lie at the end of the current evaluation order. (Or
at least that's what I'm trying to do here.) If this is used with
nondeterminism-by-call/cc, least surprise will be violated.
If that looks sort of like delay/force, it's because it started as this:
(define (pmap map)
(lambda (f . ls)
(map force (apply map (lambda xs (delay (apply f xs))) ls))))
But then I realized that I don't know what's supposed to happen when
a continuation within a delayed expression is reused. Most Schemes
I've seen discard its value and return the earlier one, but UMB Scheme
changes the promise to the new value. A smaller example:
(let* ((again #t) (ks #f) (l '())
(p (delay (call-with-current-continuation
(lambda (k) (set! ks k) 0)))))
(set! l (cons (force p) l))
(if again (begin (set! again #f) (ks 1)))
(cons (force p) l))
Certainly the continuation is required to ignore its argument if
a _different_ (presumably nested) activation of force has already
succeeded (and UMB does this), but it's not clear to me that that
applies to the same one.
On the other hand, I haven't schemed much in a few years now, so I could
be missing something obvious.
(let ((C call-with-current-continuation)) (apply (lambda (x y) (x y)) (map
((lambda (r) ((C C) (lambda (s) (r (lambda l (apply (s s) l)))))) (lambda
(f) (lambda (l) (if (null? l) C (lambda (k) (display (car l)) ((f (cdr l))
(C k))))))) '((#\J #\d #\D #\v #\s) (#\e #\space #\a #\i #\newline)))))
More information about the r6rs-discuss