Re: safety | John David Stone | 13 Jan 1999 17:52 UTC |

Re: safety | Doug Currie | 13 Jan 1999 18:19 UTC |

Re: safety | John David Stone | 13 Jan 1999 18:35 UTC |

Re: safety

*John David Stone*13 Jan 1999 17:52 UTCFollowing up on Matthias Felleisen's concern about safety, I've prepared a list of preconditions and type constraints for the procedures in the SRFI-1 proposal. At some points, I use the phrase ``p accepts v as its kth argument'' to mean that a value v satisfies all of the type constraints and preconditions that the procedure p imposes on its kth argument. When p is unary I omit ``kth.'' Note that this is different from saying ``v satisfies p,'' which means that the value of the application of p to v is something other than #F. I found a few inconsistencies, trouble spots, and other things that I wanted to comment on. In the list below, I've marked each of these with a triple asterisk. --------------------------------------------------------------------------- MAKE-LIST The first argument is a non-negative integer. *** Incidentally, I think that it would be better for SRFI-1 to state that the default value of the fill element is unspecified, instead of requiring it to be #F. This would parallel the R5RS convention for MAKE-VECTOR. --------------------------------------------------------------------------- LIST-TABULATE The first argument is a non-negative integer. The second argument is a unary procedure that accepts any non-negative integer as an argument. --------------------------------------------------------------------------- .IOTA All arguments are real numbers. The STEP argument, if present, is not zero. --------------------------------------------------------------------------- IOTA. All arguments are real numbers. The STEP argument, if present, is not zero. --------------------------------------------------------------------------- CIRCULAR-LIST *** The SRFI-1 specification indicates that CIRCULAR-LIST always returns a list, but since the objects it returns do not satisfy the R5RS LIST? predicate I think this is misleading. I recommend changing `list' to `pair' in the syntax picture. --------------------------------------------------------------------------- LIST-COPY The argument is a list. --------------------------------------------------------------------------- ZIP All arguments are lists. *** The reference implementation uses MAP, which in turn imposes the condition that the lengths of all of the the lists are equal. The specification, however, implies that the lists can vary in length. --------------------------------------------------------------------------- FIRST The argument is a pair. --------------------------------------------------------------------------- SECOND The argument is a pair, and its cdr is also a pair. --------------------------------------------------------------------------- THIRD The argument is a pair, its cdr is a pair, and its cddr is a pair. --------------------------------------------------------------------------- FOURTH The argument is a pair, its cdr is a pair, its cddr is a pair, and its cdddr is a pair. --------------------------------------------------------------------------- FIFTH The argument is a pair, its cdr is a pair, its cddr is a pair, its cdddr is a pair, and its cddddr is a pair. --------------------------------------------------------------------------- SIXTH The argument is a pair, its cdr is a pair, its cddr is a pair, its cdddr is a pair, its cddddr is a pair, and its cdddddr is a pair. --------------------------------------------------------------------------- SEVENTH The argument is a pair, its cdr is a pair, its cddr is a pair, its cdddr is a pair, its cddddr is a pair, its cdddddr is a pair, and its cddddddr is a pair. --------------------------------------------------------------------------- EIGHTH The argument is a pair, its cdr is a pair, its cddr is a pair, its cdddr is a pair, its cddddr is a pair, its cdddddr is a pair, its cddddddr is a pair, and its cdddddddr is a pair. --------------------------------------------------------------------------- NINTH The argument is a pair, its cdr is a pair, its cddr is a pair, its cdddr is a pair, its cddddr is a pair, its cdddddr is a pair, its cddddddr is a pair, its cdddddddr is a pair, and its cddddddddr is a pair. --------------------------------------------------------------------------- TENTH The argument is a pair, its cdr is a pair, its cddr is a pair, its cdddr is a pair, its cddddr is a pair, its cdddddr is a pair, its cddddddr is a pair, its cdddddddr is a pair, its cddddddddr is a pair, and its cdddddddddr is a pair. --------------------------------------------------------------------------- TAKE The first argument is a list. The second argument is an integer. The absolute value of that integer is not greater than the length of that list. --------------------------------------------------------------------------- TAKE! The first argument is a list. The second argument is an integer. The absolute value of that integer is not greater than the length of that list. --------------------------------------------------------------------------- DROP The first argument is a list. The second argument is an integer. The absolute value of that integer is not greater than the length of that list. --------------------------------------------------------------------------- DROP! The first argument is a list. The second argument is an integer. The absolute value of that integer is not greater than the length of that list. --------------------------------------------------------------------------- LAST The argument is a non-empty list. --------------------------------------------------------------------------- LAST-PAIR The argument is a pair. --------------------------------------------------------------------------- UNZIP2 The argument is a list. Each element of that list is a list of length at least 2. --------------------------------------------------------------------------- UNZIP3 The argument is a list. Each element of that list is a list of length at least 3. --------------------------------------------------------------------------- UNZIP4 The argument is a list. Each element of that list is a list of length at least 4. --------------------------------------------------------------------------- UNZIP5 The argument is a list. Each element of that list is a list of length at least 5. --------------------------------------------------------------------------- APPEND! Every argument is a list. *** The SRFI-1 specification says that this procedure is intended as a linear-update variant of APPEND. R5RS says that the last argument in a call to APPEND need not be a list, but the SRFI-1 specification seems to require that it be a list, and the reference implementation gives the wrong answer unless the last argument is a pair. ;; Chez Scheme: > (append '(alpha beta) 'gamma) (alpha beta . gamma) > (append! '(alpha beta) 'gamma) (alpha beta . gamma) ;; SRFI-1 reference implementation: > (append! '(alpha beta) 'gamma) (alpha beta) --------------------------------------------------------------------------- REVERSE-APPEND Both arguments are lists. --------------------------------------------------------------------------- REVERSE-APPEND! Both arguments are lists. --------------------------------------------------------------------------- REVERSE! The argument is a list. --------------------------------------------------------------------------- UNFOLD Let's call the arguments P, F, G, and SEED. P is a unary procedure that accepts SEED as an argument and also accepts as an argument any value that G returns. F is a unary procedure that accepts SEED as an argument, provided that it satisfies P, and also accepts as an argument any value that G returns, if that value satisfies P. G is a unary procedure that accepts SEED as an argument, provided that it satisfies P, and also accepts aa an argument any value that it returns, if that value satisfies P. --------------------------------------------------------------------------- UNFOLD/TAIL Let's call the arguments P, F, G, E, and SEED. P is a unary procedure that accepts SEED as an argument and also accepts as an argument any value that G returns. F is a unary procedure that accepts SEED as an argument, provided that it satisfies P, and also accepts as an argument any value that G returns, if that value satisfies P. G is a unary procedure that accepts SEED as an argument, provided that it satisfies P, and also accepts aa an argument any value that it returns, if that value satisfies P. E is a unary procedure that accepts SEED as an argument, provided that it does not satisfy P, and also accepts as an argument any value that G returns, if that value does not satisfy P. --------------------------------------------------------------------------- FOLDL Let's call the arguments KONS, KNIL, and LIS1, ..., LISn. KONS is a procedure of arity n + 1. It accepts KNIL as its last argument, and also accepts as its last argument any value that it returns. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, KONS accepts every element of LISi as its ith argument. --------------------------------------------------------------------------- FOLDR Let's call the arguments KONS, KNIL, and LIS1, ..., LISn. KONS is a procedure of arity n + 1. It accepts KNIL as its last argument, and also accepts as its last argument any value that it returns. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, KONS accepts every element of LISi as its ith argument. --------------------------------------------------------------------------- PAIR-FOLDL Let's call the arguments KONS, KNIL, and LIS1, ..., LISn. KONS is a procedure of arity n + 1. It accepts KNIL as its last argument, and also accepts as its last argument any value that it returns. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, KONS accepts LISi and every non-empty tail sublist of LIS1 as its ith argument. --------------------------------------------------------------------------- PAIR-FOLDR Let's call the arguments KONS, KNIL, and LIS1, ..., LISn. KONS is a procedure of arity n + 1. It accepts KNIL as its last argument, and also accepts as its last argument any value that it returns. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, KONS accepts LISi and every non-empty tail sublist of LIS1 as its ith argument. --------------------------------------------------------------------------- REDUCEL The first argument (let's call it F) is a binary procedure. The second argument is a right identity of F. The third argument (let's call it LIS) is a list. Either it is empty, or F accepts as its second argument the first element of LIS and accepts as its first argument any of the other elements of LIS. F also accepts as its second argument any value that it returns. --------------------------------------------------------------------------- REDUCER The first argument (let's call it F) is a binary procedure. The second argument is a right identity of F. The third argument (let's call it LIS) is a list. Either it is empty, or F accepts as its second argument the last element of LIS and accepts as its first argument any of the other elements of LIS. F also accepts as its second argument any value that it returns. --------------------------------------------------------------------------- APPEND-MAP Let's call the arguments F, LIS1, ..., LISn. F is a procedure of arity n that returns only lists. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, F accepts every element of LISi as its ith argument. --------------------------------------------------------------------------- APPEND-MAP! Let's call the arguments F, LIS1, ..., LISn. F is a procedure of arity n that returns only lists. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, F accepts every element of LISi as its ith argument. --------------------------------------------------------------------------- MAP! Let's call the arguments F, LIS1, ..., LISn. F is a procedure of arity n. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, F accepts every element of LISi as its ith argument. *** The SRFI-1 specification says that MAP! is a linear-update variant of MAP. R5RS requires all the list arguments in an invocation of MAP to have the same length. The SRFI-1 specification of MAP! does not mention this constraint, and the reference implementation does not enforce it. --------------------------------------------------------------------------- MAP-IN-ORDER Let's call the arguments F, LIS1, ..., LISn. F is a procedure of arity n. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, F accepts every element of LISi as its ith argument. *** The SRFI-1 specification says that MAP-IN-ORDER is a variant of MAP. R5RS requires all the list arguments in an invocation of MAP to have the same length. The SRFI-1 specification of MAP-IN-ORDER does not mention this constraint, and the reference implementation does not enforce it. --------------------------------------------------------------------------- PAIR-FOR-EACH Let's call the arguments F, LIS1, ..., LISn. F is a procedure of arity n. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, F accepts LIS1 and every non-empty tail sublist of LISi as its ith argument. *** The SRFI-1 specification says that PAIR-FOR-EACH is a variant of FOR-EACH. R5RS requires all the list arguments in an invocation of FOR-EACH to have the same length. The SRFI-1 specification of PAIR-FOR-EACH does not mention this constraint, and the reference implementation does not enforce it. --------------------------------------------------------------------------- FILTER-MAP Let's call the arguments F, LIS1, ..., LISn. F is a procedure of arity n. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, F accepts every element of LISi as its ith argument. *** The SRFI-1 specification says that FILTER-MAP is a variant of MAP. R5RS requires all the list arguments in an invocation of MAP to have the same length. The SRFI-1 specification of FILTER-MAP does not mention this constraint, and the reference implementation does not enforce it. --------------------------------------------------------------------------- FILTER The first argument is a unary procedure. The second argument is a list. That unary procedure accepts every element of that list as its argument. --------------------------------------------------------------------------- FILTER! The first argument is a unary procedure. The second argument is a list. That unary procedure accepts every element of that list as its argument. --------------------------------------------------------------------------- REMOVE The first argument is a unary procedure. The second argument is a list. That unary procedure accepts every element of that list as its argument. --------------------------------------------------------------------------- REMOVE! The first argument is a unary procedure. The second argument is a list. That unary procedure accepts every element of that list as its argument. --------------------------------------------------------------------------- PARTITION The first argument is a unary procedure. The second argument is a list. That unary procedure accepts every element of that list as its argument. --------------------------------------------------------------------------- PARTITION! The first argument is a unary procedure. The second argument is a list. That unary procedure accepts every element of that list as its argument. --------------------------------------------------------------------------- FIND The first argument is a unary procedure. The second argument is a list. That unary procedure accepts every element of that list as its argument. --------------------------------------------------------------------------- FIND-TAIL The first argument is a unary procedure. The second argument is a list. That unary procedure accepts every element of that list as its argument. --------------------------------------------------------------------------- ANY Let's call the arguments PRED, LIS1, ..., LISn PRED is a procedure of arity n. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, PRED accepts every element of LISi as its ith argument. --------------------------------------------------------------------------- EVERY Let's call the arguments PRED, LIS1, ..., LISn PRED is a procedure of arity n. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, PRED accepts every element of LISi as its ith argument. --------------------------------------------------------------------------- LIST-INDEX Let's call the arguments PRED, LIS1, ..., LISn PRED is a procedure of arity n. For every integer i from 1 to n, LISi is a list. For every integer i from 1 to n, PRED accepts every element of LISi as its ith argument. --------------------------------------------------------------------------- DEL Let's call the arguments ELT=, X, and LIS. ELT= is a binary procedure. LIS is a list. ELT= accepts X as its first argument and accepts every element of LIS as its second argument. --------------------------------------------------------------------------- DELQ The second argument is a list. --------------------------------------------------------------------------- DELV The second argument is a list. --------------------------------------------------------------------------- DELETE The second argument is a list. --------------------------------------------------------------------------- DEL! Let's call the arguments ELT=, X, and LIS. ELT= is a binary procedure. LIS is a list. ELT= accepts X as its first argument and accepts every element of LIS as its second argument. --------------------------------------------------------------------------- DELQ! The second argument is a list. --------------------------------------------------------------------------- DELV! The second argument is a list. --------------------------------------------------------------------------- DELETE! The second argument is a list. --------------------------------------------------------------------------- DEL-DUPLICATES The first argument is a binary procedure. The second argument is a list. That binary procedure accepts every element of that list as either of its arguments. --------------------------------------------------------------------------- DELQ-DUPLICATES The argument is a list. --------------------------------------------------------------------------- DELV-DUPLICATES The argument is a list. --------------------------------------------------------------------------- DELETE-DUPLICATES The argument is a list. --------------------------------------------------------------------------- DEL-DUPLICATES! The first argument is a binary procedure. The second argument is a list. That binary procedure accepts every element of that list as either of its arguments. --------------------------------------------------------------------------- DELQ-DUPLICATES! The argument is a list. --------------------------------------------------------------------------- DELV-DUPLICATES! The argument is a list. --------------------------------------------------------------------------- DELETE-DUPLICATES! The argument is a list. --------------------------------------------------------------------------- MEM Let's call the arguments ELT=, X, and LIS. ELT= is a binary procedure. LIS is a list. ELT= accepts X as its first argument and accepts every element of LIS as its second argument. --------------------------------------------------------------------------- ASS Let's call the arguments KEY=, KEY, and ALIST. KEY= is a binary procedure. ALIST is an association list (i.e., a list of pairs). KEY= accepts KEY as its first argument and accepts the car of every element of ALIST as its second argument. --------------------------------------------------------------------------- ACONS The third argument is an association list. --------------------------------------------------------------------------- ALIST-COPY The argument is an association list. --------------------------------------------------------------------------- ALIST-DELETE Let's call the arguments KEY=, KEY, and ALIST. KEY= is a binary procedure. ALIST is an association list. KEY= accepts KEY as its first argument and accepts the car of every element of ALIST as its second argument. --------------------------------------------------------------------------- DEL-ASS Let's call the arguments KEY=, KEY, and ALIST. KEY= is a binary procedure. ALIST is an association list. KEY= accepts KEY as its first argument and accepts the car of every element of ALIST as its second argument. --------------------------------------------------------------------------- DEL-ASSQ The second argument is an association list. --------------------------------------------------------------------------- DEL-ASSV The second argument is an association list. --------------------------------------------------------------------------- DEL-ASSOC The second argument is an association list. --------------------------------------------------------------------------- ALIST-DELETE! Let's call the arguments KEY=, KEY, and ALIST. KEY= is a binary procedure. ALIST is an association list. KEY= accepts KEY as its first argument and accepts the car of every element of ALIST as its second argument. --------------------------------------------------------------------------- DEL-ASS! Let's call the arguments KEY=, KEY, and ALIST. KEY= is a binary procedure. ALIST is an association list. KEY= accepts KEY as its first argument and accepts the car of every element of ALIST as its second argument. --------------------------------------------------------------------------- DEL-ASSQ! The second argument is an association list. --------------------------------------------------------------------------- DEL-ASSV! The second argument is an association list. --------------------------------------------------------------------------- DEL-ASSOC! The second argument is an association list. --------------------------------------------------------------------------- -- ====== John David Stone - Lecturer in Computer Science and Philosophy ===== ============== Manager of the Mathematics Local-Area Network ============== ============== Grinnell College - Grinnell, Iowa 50112 - USA ============== ========== xxxxxx@math.grin.edu - http://www.math.grin.edu/~stone/ =========