[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: safety



        Following 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  ==============
==========  stone@xxxxxxxxxxxxx - http://www.math.grin.edu/~stone/  =========