The linear-update procedures in SRFI 1 indeed seem to be underspecified as it is not clear when the result list is constructed.
Should the linear-update procedures become part of an official standard, quite some work has to be done. I would specify the procedures in a way that entering the same continuation (of the higher-order argument) a second time or modifying the list in between is an error. Am Mi., 10. Jan. 2024 um 00:49 Uhr schrieb Bradley Lucier <[email protected] >: > I found the following "linear update" procedures that take procedural > arguments: > > append-map! f clist1 clist2 ... -> value > map! f list1 clist2 ... -> list > filter! pred list -> list > partition! pred list -> [list list] > remove! pred list -> list > take-while! pred clist -> list > span! pred list -> [list list] > break! pred list -> [list list] > delete! x list [=] -> list > delete-duplicates! list [=] -> list > alist-delete! key alist [=] -> alist > lset-union! = list1 ... -> list > lset-intersection! = list1 list2 ... -> list > lset-difference! = list1 list2 ... -> list > lset-xor! = list1 ... -> list > lset-diff+intersection! = list1 list2 ... -> [list list] > > I looked at the implementation of filter! in the sample implementation, > which is very elegant: > > (define (filter! pred lis) > (check-arg procedure? pred filter!) > (let lp ((ans lis)) > (cond ((null-list? ans) ans) ; Scan looking for > ((not (pred (car ans))) (lp (cdr ans))) ; first cons of > result. > > ;; ANS is the eventual answer. > ;; SCAN-IN: (CDR PREV) = LIS and (CAR PREV) satisfies PRED. > ;; Scan over a contiguous segment of the list that > ;; satisfies PRED. > ;; SCAN-OUT: (CAR PREV) satisfies PRED. Scan over a contiguous > ;; segment of the list that *doesn't* satisfy PRED. > ;; When the segment ends, patch in a link from PREV > ;; to the start of the next good segment, and jump to > ;; SCAN-IN. > (else (letrec ((scan-in (lambda (prev lis) > (if (pair? lis) > (if (pred (car lis)) > (scan-in lis (cdr lis)) > (scan-out prev (cdr lis)))))) > (scan-out (lambda (prev lis) > (let lp ((lis lis)) > (if (pair? lis) > (if (pred (car lis)) > (begin (set-cdr! prev lis) > (scan-in lis (cdr > lis))) > (lp (cdr lis))) > (set-cdr! prev lis)))))) > (scan-in ans (cdr ans)) > ans))))) > > This sample implementation can be screwed up if pred captures and > replays its continuation. > > My understanding of the term "linear update" (and I have to admit I > haven't found very many references to this term other than in SRFI 1) is > that having pred capture and replay its continuation is a violation of > the "linear update" assumption that the only pointer to the list > argument lis (and presumably all following pairs in the list, although I > don't remember whether this is stated explicitly in SRFI 1) is lis > itself, so having the pred procedure capture and replay its continuation > violates the "linear update" assumption, and a user doing such a thing > can go pound sand. > > My question: Is this analysis correct? > > My secondary question: Should one restrict the programming of filter! to > be the same as filter just to "save" someone who decides to use call/cc > in pred? > > Brad >
