diff options
Diffstat (limited to 'slib.texi')
| -rw-r--r-- | slib.texi | 1138 |
1 files changed, 553 insertions, 585 deletions
@@ -2,6 +2,7 @@ @c %**start of header @setfilename slib.info @settitle SLIB +@include version.txi @setchapternewpage on @c Choices for setchapternewpage are {on,off,odd}. @paragraphindent 2 @@ -26,7 +27,7 @@ This file documents SLIB, the portable Scheme library. Copyright (C) 1993 Todd R. Eigenschink@* -Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998 Aubrey Jaffer +Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998, 1999 Aubrey Jaffer Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice @@ -50,16 +51,43 @@ except that this permission notice may be stated in a translation approved by the author. @end ifinfo +@node Top, The Library System, (dir), (dir) + @titlepage @title SLIB @subtitle The Portable Scheme Library -@subtitle Version 2c3 +@subtitle Version @value{SLIBVERSION} @author by Aubrey Jaffer - @page + +@noindent +@dfn{SLIB} is a portable library for the programming language +@dfn{Scheme}. It provides a platform independent framework for using +@dfn{packages} of Scheme procedures and syntax. As distributed, SLIB +contains useful packages for all Scheme implementations. Its catalog +can be transparently extended to accomodate packages specific to a site, +implementation, user, or directory. + +@noindent +More people than I can name have contributed to SLIB. Thanks to all of +you! +@sp 1 +@quotation +SLIB @value{SLIBVERSION}, released @value{SLIBDATE}.@* +Aubrey Jaffer <jaffer @@ ai.mit.edu>@* +@ifset html +<A HREF="http://swissnet.ai.mit.edu/~jaffer/SLIB.html"> +@end ifset +@url{http://swissnet.ai.mit.edu/~jaffer/SLIB.html} +@ifset html +</A> +@end ifset +@end quotation + +@ifclear html @vskip 0pt plus 1filll Copyright @copyright{} 1993 Todd R. Eigenschink@* -Copyright @copyright{} 1993, 1994, 1995, 1996, 1997, 1998 Aubrey Jaffer +Copyright @copyright{} 1993, 1994, 1995, 1996, 1997, 1998, 1999 Aubrey Jaffer Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice @@ -74,28 +102,17 @@ Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions, except that this permission notice may be stated in a translation approved by the author. +@end ifclear @end titlepage - -@node Top, The Library System, (dir), (dir) - @ifinfo -@cindex SLIB +@noindent @dfn{SLIB} is a portable library for the programming language -@cindex Scheme @dfn{Scheme}. It provides a platform independent framework for using -@dfn{packages} of Scheme procedures and syntax. -@cindex packages -@cindex package -As distributed, SLIB contains useful packages for all implementations. -Its catalog can be transparently extended to accomodate packages -specific to a site, implementation, user, or directory. - -@quotation -Aubrey Jaffer <jaffer@@ai.mit.edu>@* -@i{Hyperactive Software} -- The Maniac Inside!@* -@url{http://swissnet.ai.mit.edu/~jaffer/SLIB.html} -@end quotation +@dfn{packages} of Scheme procedures and syntax. As distributed, SLIB +contains useful packages for all Scheme implementations. Its catalog +can be transparently extended to accomodate packages specific to a site, +implementation, user, or directory. @end ifinfo @menu @@ -112,28 +129,6 @@ Aubrey Jaffer <jaffer@@ai.mit.edu>@* @node The Library System, Scheme Syntax Extension Packages, Top, Top @chapter The Library System -@iftex -@section Introduction - -@noindent -@cindex SLIB -@dfn{SLIB} is a portable library for the programming language -@cindex Scheme -@dfn{Scheme}. It provides a platform independent framework for using -@dfn{packages} of Scheme procedures and syntax. -@cindex packages -@cindex package -As distributed, SLIB contains useful packages for all implementations. -Its catalog can be transparently extended to accomodate packages -specific to a site, implementation, user, or directory. - -@quotation -Aubrey Jaffer <jaffer@@ai.mit.edu>@* -@i{Hyperactive Software} -- The Maniac Inside!@* -@url{http://swissnet.ai.mit.edu/~jaffer/SLIB.html} -@end quotation -@end iftex - @menu * Feature:: SLIB names. * Requesting Features:: @@ -608,7 +603,14 @@ An integer 1 larger that the largest value which can be returned by @end defvr @defvr Constant most-positive-fixnum -The immediate integer closest to positive infinity. +In implementations which support integers of practically unlimited size, +@var{most-positive-fixnum} is a large exact integer within the range of +exact integers that may result from computing the length of a list, +vector, or string. + +In implementations which do not support integers of practically +unlimited size, @var{most-positive-fixnum} is the largest exact integer +that may result from computing the length of a list, vector, or string. @end defvr @defvr Constant slib:tab @@ -630,7 +632,7 @@ Displays the versions of SLIB and the underlying Scheme implementation and the name of the operating system. An unspecified value is returned. @example -(slib:report-version) @result{} slib "2c3" on scm "5b1" on unix +(slib:report-version) @result{} slib "@value{SLIBVERSION}" on scm "5b1" on unix @end example @end defun @@ -648,7 +650,7 @@ Writes the report to file @file{filename}. @example (slib:report) @result{} -slib "2c3" on scm "5b1" on unix +slib "@value{SLIBVERSION}" on scm "5b1" on unix (implementation-vicinity) is "/home/jaffer/scm/" (library-vicinity) is "/home/jaffer/slib/" (scheme-file-suffix) is ".scm" @@ -1763,7 +1765,7 @@ In order to use syntax-case from an interactive top level, execute: @ftindex repl (repl:top-level macro:eval) @end lisp -See the section Repl (@xref{Repl}) for more information. +See the section Repl (@pxref{Repl}) for more information. To check operation of syntax-case get @file{cs.indiana.edu:/pub/scheme/syntax-case}, and type @@ -1951,7 +1953,7 @@ identity. Also known as ``send-to-super''.@refill @deffn Procedure print obj port A default @code{print} operation is provided which is just @code{(format -@var{port} @var{obj})} (@xref{Format}) for non-instances and prints +@var{port} @var{obj})} (@pxref{Format}) for non-instances and prints @var{obj} preceded by @samp{#<INSTANCE>} for instances. @end deffn @@ -1959,7 +1961,7 @@ A default @code{print} operation is provided which is just @code{(format The default method returns the number of elements in @var{obj} if it is a vector, string or list, @code{2} for a pair, @code{1} for a character and by default id an error otherwise. Objects such as collections -(@xref{Collections}) may override the default in an obvious way.@refill +(@pxref{Collections}) may override the default in an obvious way.@refill @end defun @@ -1975,7 +1977,7 @@ retrieves a value from a generalized location and the corresponding setter operation stores a value into the location. Only the getter is named -- the setter is specified by a procedure call as below. (Dylan uses special syntax.) Typically, but not necessarily, getters are -access operations to extract values from Yasos objects (@xref{Yasos}). +access operations to extract values from Yasos objects (@pxref{Yasos}). Several setters are predefined, corresponding to getters @code{car}, @code{cdr}, @code{string-ref} and @code{vector-ref} e.g., @code{(setter car)} is equivalent to @code{set-car!}. @@ -2038,7 +2040,8 @@ value is unspecified. @subsection Examples @lisp -;;; These definitions for PRINT and SIZE are already supplied by +;;; These definitions for PRINT and SIZE are +;;; already supplied by (require 'yasos) (define-operation (print obj port) @@ -2075,11 +2078,12 @@ value is unspecified. (format #t "Discarding ~s~%" value)) (define (make-filtered-cell value filter) - (object-with-ancestors ((cell (make-cell value))) - ((store! self newValue) - (if (filter newValue) - (store! cell newValue) - (discard self newValue))))) + (object-with-ancestors + ((cell (make-cell value))) + ((store! self newValue) + (if (filter newValue) + (store! cell newValue) + (discard self newValue))))) (define-predicate array?) (define-operation (array-ref array index)) @@ -2090,9 +2094,12 @@ value is unspecified. (object ((array? self) #t) ((size self) num-slots) - ((array-ref self index) (vector-ref anArray index)) - ((array-set! self index newValue) (vector-set! anArray index newValue)) - ((print self port) (format port "#<Array ~s>" (size self)))))) + ((array-ref self index) + (vector-ref anArray index)) + ((array-set! self index newValue) + (vector-set! anArray index newValue)) + ((print self port) + (format port "#<Array ~s>" (size self)))))) (define-operation (position obj)) (define-operation (discarded-value obj)) @@ -2112,7 +2119,8 @@ value is unspecified. (set! most-recent-discard value)) ((discarded-value self) most-recent-discard) ((print self port) - (format port "#<Cell-with-history ~s>" (fetch self)))))) + (format port "#<Cell-with-history ~s>" + (fetch self)))))) (define-access-operation fetch) (add-setter fetch store!) @@ -2199,7 +2207,7 @@ missing input. @noindent Here are the higher-level syntax types and an example of each. -Precedence considerations are omitted for clarity. @xref{Grammar +Precedence considerations are omitted for clarity. See @ref{Grammar Rule Definition} for full details. @deftp Grammar nofix bye exit @example @@ -2885,7 +2893,7 @@ Print a floating-point number in exponential notation. @samp{%e} prints between mantissa and exponont. @item @samp{g}, @samp{G} -Print a floating-point number in either normal or exponential notation, +Print a floating-point number in either fixed or exponential notation, whichever is more appropriate for its magnitude. Unless an @samp{#} flag has been supplied trailing zeros after a decimal point will be stripped off. @samp{%g} prints @samp{e} between mantissa and exponont. @@ -2917,7 +2925,7 @@ are output. @c Print the value of a pointer. @c @item @samp{n} -@c Get the number of characters printed so far. @xref{Other Output Conversions}. +@c Get the number of characters printed so far. See @ref{Other Output Conversions}. @c Note that this conversion specification never produces any output. @c @item @samp{m} @@ -3526,8 +3534,9 @@ ERROR: getopt->parameter-list "unrecognized option" "-?" @defun filename:match?? pattern @defunx filename:match-ci?? pattern -Returns a predicate which returns true if its string argument matches -(the string) @var{pattern}, false otherwise. Filename matching is like +Returns a predicate which returns a non-false value if its string argument +matches (the string) @var{pattern}, false otherwise. Filename matching +is like @cindex glob @dfn{glob} expansion described the bash manpage, except that names beginning with @samp{.} are matched and @samp{/} characters are not @@ -3551,8 +3560,39 @@ matched by including it as the first or last character in the set. @example @end example +@end defun +@defun filename:substitute?? pattern template +@defunx filename:substitute-ci?? pattern template +Returns a function transforming a single string argument according to +glob patterns @var{pattern} and @var{template}. @var{pattern} and +@var{template} must have the same number of wildcard specifications, +which need not be identical. @var{pattern} and @var{template} may have +a different number of literal sections. If an argument to the function +matches @var{pattern} in the sense of @code{filename:match??} then it +returns a copy of @var{template} in which each wildcard specification is +replaced by the part of the argument matched by the corresponding +wildcard specification in @var{pattern}. A @code{*} wildcard matches +the longest leftmost string possible. If the argument does not match +@var{pattern} then false is returned. + +@var{template} may be a function accepting the same number of string +arguments as there are wildcard specifications in @var{pattern}. In +the case of a match the result of applying @var{template} to a list +of the substrings matched by wildcard specifications will be returned, +otherwise @var{template} will not be called and @code{#f} will be returned. +@example +((filename:substitute?? "scm_[0-9]*.html" "scm5c4_??.htm") + "scm_10.html") +@result{} "scm5c4_10.htm" +((filename:substitute?? "??" "beg?mid?end") "AZ") +@result{} "begAmidZend" +((filename:substitute?? "*na*" "?NA?") "banana") +@result{} "banaNA" +((filename:substitute?? "?*?" (lambda (s1 s2 s3) (string-append s3 s1))) "ABZ") +@result{} "ZA" +@end example @end defun @defun replace-suffix str old new @@ -3594,6 +3634,8 @@ dos @item vms @item +amigados +@item system @item *unknown* @@ -3630,16 +3672,6 @@ only argument. If @var{file} is a string, result of @code{(current-output-port)} as its third argument. @end defun -@defun batch:apply-chop-to-fit proc arg1 arg2 @dots{} list -The procedure @var{proc} must accept at least one argument and return -@code{#t} if successful, @code{#f} if not. -@code{batch:apply-chop-to-fit} calls @var{proc} with @var{arg1}, -@var{arg2}, @dots{}, and @var{chunk}, where @var{chunk} is a subset of -@var{list}. @code{batch:apply-chop-to-fit} tries @var{proc} with -successively smaller subsets of @var{list} until either @var{proc} -returns non-false, or the @var{chunk}s become empty. -@end defun - @noindent The rest of the @code{batch:} procedures write (or execute if @code{batch-dialect} is @code{system}) commands to the batch port which @@ -3650,9 +3682,9 @@ code: (adjoin-parameters! @var{parms} (list 'batch-port @var{port})) @end example -@defun batch:system parms string1 string2 @dots{} -Calls @code{batch:try-system} (below) with arguments, but signals an -error if @code{batch:try-system} returns @code{#f}. +@defun batch:command parms string1 string2 @dots{} +Calls @code{batch:try-command} (below) with arguments, but signals an +error if @code{batch:try-command} returns @code{#f}. @end defun @noindent @@ -3661,17 +3693,32 @@ translated into the batch dialect and @code{#f} if not. In the case of the @code{system} dialect, the value is non-false if the operation suceeded. -@defun batch:try-system parms string1 string2 @dots{} +@defun batch:try-command parms string1 string2 @dots{} Writes a command to the @code{batch-port} in @var{parms} which executes the program named @var{string1} with arguments @var{string2} @dots{}. @end defun +@defun batch:try-chopped-command parms arg1 arg2 @dots{} list +breaks the last argument @var{list} into chunks small enough so that the +command: + +@example +@var{arg1} @var{arg2} @dots{} @var{chunk} +@end example + +fits withing the platform's maximum command-line length. + +@code{batch:try-chopped-command} calls @code{batch:try-command} with the +command and returns non-false only if the commands all fit and +@code{batch:try-command} of each command line returned non-false. +@end defun + @defun batch:run-script parms string1 string2 @dots{} Writes a command to the @code{batch-port} in @var{parms} which executes the batch script named @var{string1} with arguments @var{string2} @dots{}. -@emph{Note:} @code{batch:run-script} and @code{batch:try-system} are not the +@emph{Note:} @code{batch:run-script} and @code{batch:try-command} are not the same for some operating systems (VMS). @end defun @@ -3775,10 +3822,10 @@ Here is an example of the use of most of batch's procedures: " printf(\"hello world\\n\");" " return 0;" "@}" ) - (batch:system my-parameters "cc" "-c" "hello.c") - (batch:system my-parameters "cc" "-o" "hello" + (batch:command my-parameters "cc" "-c" "hello.c") + (batch:command my-parameters "cc" "-o" "hello" (replace-suffix "hello.c" ".c" ".o")) - (batch:system my-parameters "hello") + (batch:command my-parameters "hello") (batch:delete-file my-parameters "hello") (batch:delete-file my-parameters "hello.c") (batch:delete-file my-parameters "hello.o") @@ -3791,7 +3838,7 @@ Produces the file @file{my-batch}: @example #!/bin/sh -# "my-batch" build script created Sat Jun 10 21:20:37 1995 +# "my-batch" script created by SLIB/batch Sun Oct 31 18:24:10 1999 # ================ Write file with C program. mv -f hello.c hello.c~ rm -f hello.c @@ -3964,12 +4011,168 @@ thus can reduce loading time. The following will write into @section Time and Date @menu +* Time Zone:: * Posix Time:: 'posix-time * Common-Lisp Time:: 'common-lisp-time @end menu +@noindent +If @code{(provided? 'current-time)}: + +@noindent +The procedures @code{current-time}, @code{difftime}, and +@code{offset-time} deal with a @dfn{calendar time} datatype +@cindex time +@cindex calendar time +which may or may not be disjoint from other Scheme datatypes. + +@defun current-time +Returns the time since 00:00:00 GMT, January 1, 1970, measured in +seconds. Note that the reference time is different from the reference +time for @code{get-universal-time} in @ref{Common-Lisp Time}. +@end defun + +@defun difftime caltime1 caltime0 +Returns the difference (number of seconds) between twe calendar times: +@var{caltime1} - @var{caltime0}. @var{caltime0} may also be a number. +@end defun + +@defun offset-time caltime offset +Returns the calendar time of @var{caltime} offset by @var{offset} number +of seconds @code{(+ caltime offset)}. +@end defun + +@node Time Zone, Posix Time, Time and Date, Time and Date +@subsection Time Zone + +(require 'time-zone) + +@deftp {Data Format} TZ-string + +POSIX standards specify several formats for encoding time-zone rules. + +@table @t +@item :@i{<pathname>} +If the first character of @i{<pathname>} is @samp{/}, then +@i{<pathname>} specifies the absolute pathname of a tzfile(5) format +time-zone file. Otherwise, @i{<pathname>} is interpreted as a pathname +within @var{tzfile:vicinity} (/usr/lib/zoneinfo/) naming a tzfile(5) +format time-zone file. +@item @i{<std>}@i{<offset>} +The string @i{<std>} consists of 3 or more alphabetic characters. +@i{<offset>} specifies the time difference from GMT. The @i{<offset>} +is positive if the local time zone is west of the Prime Meridian and +negative if it is east. @i{<offset>} can be the number of hours or +hours and minutes (and optionally seconds) separated by @samp{:}. For +example, @code{-4:30}. +@item @i{<std>}@i{<offset>}@i{<dst>} +@i{<dst>} is the at least 3 alphabetic characters naming the local +daylight-savings-time. +@item @i{<std>}@i{<offset>}@i{<dst>}@i{<doffset>} +@i{<doffset>} specifies the offset from the Prime Meridian when +daylight-savings-time is in effect. +@end table + +The non-tzfile formats can optionally be followed by transition times +specifying the day and time when a zone changes from standard to +daylight-savings and back again. + +@table @t +@item ,@i{<date>}/@i{<time>},@i{<date>}/@i{<time>} +The @i{<time>}s are specified like the @i{<offset>}s above, except that +leading @samp{+} and @samp{-} are not allowed. + +Each @i{<date>} has one of the formats: + +@table @t +@item J@i{<day>} +specifies the Julian day with @i{<day>} between 1 and 365. February 29 +is never counted and cannot be referenced. +@item @i{<day>} +This specifies the Julian day with n between 0 and 365. February 29 is +counted in leap years and can be specified. +@item M@i{<month>}.@i{<week>}.@i{<day>} +This specifies day @i{<day>} (0 <= @i{<day>} <= 6) of week @i{<week>} (1 +<= @i{<week>} <= 5) of month @i{<month>} (1 <= @i{<month>} <= 12). Week +1 is the first week in which day d occurs and week 5 is the last week in +which day @i{<day>} occurs. Day 0 is a Sunday. +@end table +@end table + +@end deftp + +@deftp {Data Type} time-zone +is a datatype encoding how many hours from Greenwich Mean Time the local +time is, and the @dfn{Daylight Savings Time} rules for changing it. +@end deftp + +@defun time-zone TZ-string +Creates and returns a time-zone object specified by the string +@var{TZ-string}. If @code{time-zone} cannot interpret @var{TZ-string}, +@code{#f} is returned. +@end defun + +@defun tz:params caltime tz +@var{tz} is a time-zone object. @code{tz:params} returns a list of +three items: +@enumerate 0 +@item +An integer. 0 if standard time is in effect for timezone @var{tz} at +@var{caltime}; 1 if daylight savings time is in effect for timezone +@var{tz} at @var{caltime}. +@item +The number of seconds west of the Prime Meridian timezone @var{tz} is at +@var{caltime}. +@item +The name for timezone @var{tz} at @var{caltime}. +@end enumerate + +@code{tz:params} is unaffected by the default timezone; inquiries can be +made of any timezone at any calendar time. + +@end defun + +@noindent +The rest of these procedures and variables are provided for POSIX +compatability. Because of shared state they are not thread-safe. + +@defun tzset +Returns the default time-zone. + +@defunx tzset tz +Sets (and returns) the default time-zone to @var{tz}. + +@defunx tzset TZ-string +Sets (and returns) the default time-zone to that specified by +@var{TZ-string}. + +@code{tzset} also sets the variables @var{*timezone*}, @var{daylight?}, +and @var{tzname}. This function is automatically called by the time +conversion procedures which depend on the time zone (@pxref{Time and +Date}). +@end defun + +@defvar *timezone* +Contains the difference, in seconds, between Greenwich Mean Time and +local standard time (for example, in the U.S. Eastern time zone (EST), +timezone is 5*60*60). @code{*timezone*} is initialized by @code{tzset}. +@end defvar + +@defvar daylight? +is @code{#t} if the default timezone has rules for @dfn{Daylight Savings +Time}. @emph{Note:} @var{daylight?} does not tell you when Daylight +Savings Time is in effect, just that the default zone sometimes has +Daylight Savings Time. +@end defvar -@node Posix Time, Common-Lisp Time, Time and Date, Time and Date +@defvar tzname +is a vector of strings. Index 0 has the abbreviation for the standard +timezone; If @var{daylight?}, then index 1 has the abbreviation for the +Daylight Savings timezone. +@end defvar + + +@node Posix Time, Common-Lisp Time, Time Zone, Time and Date @subsection Posix Time @example @@ -4297,14 +4500,14 @@ in schmooz comments. @menu * Bit-Twiddling:: 'logical * Modular Arithmetic:: 'modular -* Prime Testing and Generation:: 'primes -* Prime Factorization:: 'factor +* Prime Numbers:: 'factor * Random Numbers:: 'random +* Fast Fourier Transform:: 'fft * Cyclic Checksum:: 'make-crc * Plotting:: 'charplot * Root Finding:: 'root * Commutative Rings:: 'commutative-ring -* Determinant:: +* Determinant:: 'determinant @end menu @@ -4502,7 +4705,7 @@ Example: @end lisp @end defun -@node Modular Arithmetic, Prime Testing and Generation, Bit-Twiddling, Mathematical Packages +@node Modular Arithmetic, Prime Numbers, Bit-Twiddling, Mathematical Packages @section Modular Arithmetic @code{(require 'modular)} @@ -4584,184 +4787,18 @@ Returns (@var{k2} ^ @var{k3}) mod @var{modulus}. @end defun -@node Prime Testing and Generation, Prime Factorization, Modular Arithmetic, Mathematical Packages -@section Prime Testing and Generation - -@code{(require 'primes)} -@ftindex primes - -This package tests and generates prime numbers. The strategy used is -as follows: - -@itemize @bullet -@item -First, use trial division by small primes (primes less than 1000) to -quickly weed out composites with small factors. As a side benefit, this -makes the test precise for numbers up to one million. -@item -Second, apply the Miller-Rabin primality test to detect (with high -probability) any remaining composites. -@end itemize - -The Miller-Rabin test is a Monte-Carlo test---in other words, it's fast -and it gets the right answer with high probability. For a candidate -that @emph{is} prime, the Miller-Rabin test is certain to report -"prime"; it will never report "composite". However, for a candidate -that is composite, there is a (small) probability that the Miller-Rabin -test will erroneously report "prime". This probability can be made -arbitarily small by adjusting the number of iterations of the -Miller-Rabin test. - -@defun probably-prime? candidate -@defunx probably-prime? candidate iter -Returns @code{#t} if @code{candidate} is probably prime. The optional -parameter @code{iter} controls the number of iterations of the -Miller-Rabin test. The probability of a composite candidate being -mistaken for a prime is at most @code{(1/4)^iter}. The default value of -@code{iter} is 15, which makes the probability less than 1 in 10^9. - -@end defun - -@defun primes< start count -@defunx primes< start count iter -@defunx primes> start count -@defunx primes> start count iter -Returns a list of the first @code{count} odd probable primes less (more) -than or equal to @code{start}. The optional parameter @code{iter} -controls the number of iterations of the Miller-Rabin test for each -candidate. The probability of a composite candidate being mistaken for -a prime is at most @code{(1/4)^iter}. The default value of @code{iter} -is 15, which makes the probability less than 1 in 10^9. - -@end defun -@menu -* The Miller-Rabin Test:: How the Miller-Rabin test works -@end menu - -@node The Miller-Rabin Test, , Prime Testing and Generation, Prime Testing and Generation -@subsection Theory - -Rabin and Miller's result can be summarized as follows. Let @code{p} -(the candidate prime) be any odd integer greater than 2. Let @code{b} -(the "base") be an integer in the range @code{2 ... p-1}. There is a -fairly simple Boolean function---call it @code{C}, for -"Composite"---with the following properties: -@itemize @bullet - -@item -If @code{p} is prime, @code{C(p, b)} is false for all @code{b} in the range -@code{2 ... p-1}. - -@item -If @code{p} is composite, @code{C(p, b)} is false for at most 1/4 of all -@code{b} in the range @code{ 2 ... p-1}. (If the test fails for base -@code{b}, @code{p} is called a @emph{strong pseudo-prime to base -@code{b}}.) - -@end itemize -For details of @code{C}, and why it fails for at most 1/4 of the -potential bases, please consult a book on number theory or cryptography -such as "A Course in Number Theory and Cryptography" by Neal Koblitz, -published by Springer-Verlag 1994. - -There is nothing probablistic about this result. It's true for all -@code{p}. If we had time to test @code{(1/4)p + 1} different bases, we -could definitively determine the primality of @code{p}. For large -candidates, that would take much too long---much longer than the simple -approach of dividing by all numbers up to @code{sqrt(p)}. This is -where probability enters the picture. - -Suppose we have some candidate prime @code{p}. Pick a random integer -@code{b} in the range @code{2 ... p-1}. Compute @code{C(p,b)}. If -@code{p} is prime, the result will certainly be false. If @code{p} is -composite, the probability is at most 1/4 that the result will be false -(demonstrating that @code{p} is a strong pseudoprime to base @code{b}). -The test can be repeated with other random bases. If @code{p} is prime, -each test is certain to return false. If @code{p} is composite, the -probability of @code{C(p,b)} returning false is at most 1/4 for each -test. Since the @code{b} are chosen at random, the tests outcomes are -independent. So if @code{p} is composite and the test is repeated, say, -15 times, the probability of it returning false all fifteen times is at -most (1/4)^15, or about 10^-9. If the test is repeated 30 times, the -probability of failure drops to at most 8.3e-25. - -Rabin and Miller's result holds for @emph{all} candidates @code{p}. -However, if the candidate @code{p} is picked at random, the probability -of the Miller-Rabin test failing is much less than the computed bound. -This is because, for @emph{most} composite numbers, the fraction of -bases that cause the test to fail is much less than 1/4. For example, -if you pick a random odd number less than 1000 and apply the -Miller-Rabin test with only 3 random bases, the computed failure bound -is (1/4)^3, or about 1.6e-2. However, the actual probability of failure -is much less---about 7.2e-5. If you accidentally pick 703 to test for -primality, the probability of failure is (161/703)^3, or about 1.2e-2, -which is almost as high as the computed bound. This is because 703 is a -strong pseudoprime to 161 bases. But if you pick at random there is -only a small chance of picking 703, and no other number less than 1000 -has that high a percentage of pseudoprime bases. - -The Miller-Rabin test is sometimes used in a slightly different fashion, -where it can, at least in principle, cause problems. The weaker version -uses small prime bases instead of random bases. If you are picking -candidates at random and testing for primality, this works well since -very few composites are strong pseudo-primes to small prime bases. (For -example, there is only one composite less than 2.5e10 that is a strong -pseudo-prime to the bases 2, 3, 5, and 7.) The problem with this -approach is that once a candidate has been picked, the test is -deterministic. This distinction is subtle, but real. With the -randomized test, for @emph{any} candidate you pick---even if your -candidate-picking procedure is strongly biased towards troublesome -numbers, the test will work with high probability. With the -deterministic version, for any particular candidate, the test will -either work (with probability 1), or fail (with probability 1). It -won't fail for very many candidates, but that won't be much consolation -if your candidate-picking procedure is somehow biased toward troublesome -numbers. - - -@node Prime Factorization, Random Numbers, Prime Testing and Generation, Mathematical Packages -@section Prime Factorization +@node Prime Numbers, Random Numbers, Modular Arithmetic, Mathematical Packages +@section Prime Numbers @code{(require 'factor)} @ftindex factor +@ftindex primes - -@defun factor k -Returns a list of the prime factors of @var{k}. The order of the -factors is unspecified. In order to obtain a sorted list do -@code{(sort! (factor k) <)}.@refill -@end defun - -@emph{Note:} The rest of these procedures implement the Solovay-Strassen -primality test. This test has been superseeded by the faster -@xref{Prime Testing and Generation, probably-prime?}. However these are -left here as they take up little space and may be of use to an -implementation without bignums. - -See Robert Solovay and Volker Strassen, @cite{A Fast Monte-Carlo Test -for Primality}, SIAM Journal on Computing, 1977, pp 84-85. - -@defun jacobi-symbol p q -Returns the value (+1, @minus{}1, or 0) of the Jacobi-Symbol of exact -non-negative integer @var{p} and exact positive odd integer -@var{q}.@refill -@end defun - -@defun prime? p -Returns @code{#f} if @var{p} is composite; @code{#t} if @var{p} is -prime. There is a slight chance @code{(expt 2 (- prime:trials))} that a -composite will return @code{#t}.@refill -@end defun - -@defun prime:trials -Is the maxinum number of iterations of Solovay-Strassen that will be -done to test a number for primality. -@end defun - +@c @include factor.txi -@node Random Numbers, Cyclic Checksum, Prime Factorization, Mathematical Packages +@node Random Numbers, Fast Fourier Transform, Prime Numbers, Mathematical Packages @section Random Numbers @code{(require 'random)} @@ -4773,7 +4810,7 @@ A pseudo-random number generator is only as good as the tests it passes. George Marsaglia of Florida State University developed a battery of tests named @dfn{DIEHARD} (@url{http://stat.fsu.edu/~geo/diehard.html}). @file{diehard.c} has a bug which the patch -@url{ftp://swissnet.ai.mit.edu/pub/users/jaffer/diehard.c.pat} corrects. +@url{http://swissnet.ai.mit.edu/ftpdir/users/jaffer/diehard.c.pat} corrects. SLIB's new PRNG generates 8 bits at a time. With the degenerate seed @samp{0}, the numbers generated pass DIEHARD; but when bits are combined @@ -4781,87 +4818,49 @@ from sequential bytes, tests fail. With the seed @samp{http://swissnet.ai.mit.edu/~jaffer/SLIB.html}, all of those tests pass. -It would be better if there were no bad seeds. For now, use seeds of at -least 30 bytes. +@c @include random.txi -@deffn Procedure random n -@deffnx Procedure random n state -Accepts a positive integer or real @var{n} and returns a number of the -same type between zero (inclusive) and @var{n} (exclusive). The values -returned have a uniform distribution.@refill -The optional argument @var{state} must be of the type produced by -@code{(make-random-state)}. It defaults to the value of the variable -@code{*random-state*}. This object is used to maintain the state of the -pseudo-random-number generator and is altered as a side effect of the -@code{random} operation.@refill -@end deffn +If inexact numbers are supported by the Scheme implementation, +@file{randinex.scm} will be loaded as well. @file{randinex.scm} +contains procedures for generating inexact distributions. -@defvar *random-state* -Holds a data structure that encodes the internal state of the -random-number generator that @code{random} uses by default. The nature -of this data structure is implementation-dependent. It may be printed -out and successfully read back in, but may or may not function correctly -as a random-number state object in another implementation.@refill -@end defvar +@c @include randinex.txi -@deffn Procedure make-random-state -@deffnx Procedure make-random-state state -Returns a new object of type suitable for use as the value of the -variable @code{*random-state*} and as a second argument to -@code{random}. If argument @var{state} is given, a copy of it is -returned. Otherwise a copy of @code{*random-state*} is returned.@refill -@end deffn -If inexact numbers are supported by the Scheme implementation, -@file{randinex.scm} will be loaded as well. @file{randinex.scm} -contains procedures for generating inexact distributions.@refill +@node Fast Fourier Transform, Cyclic Checksum, Random Numbers, Mathematical Packages +@section Fast Fourier Transform -@deffn Procedure random:uniform state -Returns an uniformly distributed inexact real random number in the -range between 0 and 1. -@end deffn +@code{(require 'fft)} +@ftindex fft -@deffn Procedure random:solid-sphere! vect -@deffnx Procedure random:solid-sphere! vect state -Fills @var{vect} with inexact real random numbers the sum of whose -squares is less than 1.0. Thinking of @var{vect} as coordinates in -space of dimension @var{n} = @code{(vector-length @var{vect})}, the -coordinates are uniformly distributed within the unit @var{n}-shere. -The sum of the squares of the numbers is returned.@refill -@end deffn +@defun fft array +@var{array} is an array of @code{(expt 2 n)} numbers. @code{fft} +returns an array of complex numbers comprising the @dfn{Discrete Fourier +Transform} of @var{array}. -@deffn Procedure random:hollow-sphere! vect -@deffnx Procedure random:hollow-sphere! vect state -Fills @var{vect} with inexact real random numbers the sum of whose -squares is equal to 1.0. Thinking of @var{vect} as coordinates in space -of dimension n = @code{(vector-length @var{vect})}, the coordinates are -uniformly distributed over the surface of the unit n-shere.@refill -@end deffn +@defunx fft-1 array +@code{fft-1} returns an array of complex numbers comprising the inverse +Discrete Fourier Transform of @var{array}. +@end defun -@deffn Procedure random:normal -@deffnx Procedure random:normal state -Returns an inexact real in a normal distribution with mean 0 and -standard deviation 1. For a normal distribution with mean @var{m} and -standard deviation @var{d} use @code{(+ @var{m} (* @var{d} -(random:normal)))}.@refill -@end deffn +@code{(fft-1 (fft @var{array}))} will return an array of values close to +@var{array}. -@deffn Procedure random:normal-vector! vect -@deffnx Procedure random:normal-vector! vect state -Fills @var{vect} with inexact real random numbers which are independent -and standard normally distributed (i.e., with mean 0 and variance 1). -@end deffn +@example +(fft '#(1 0+i -1 0-i 1 0+i -1 0-i)) @result{} -@deffn Procedure random:exp -@deffnx Procedure random:exp state -Returns an inexact real in an exponential distribution with mean 1. For -an exponential distribution with mean @var{u} use (* @var{u} -(random:exp)).@refill -@end deffn +#(0.0 0.0 0.0+628.0783185208527e-18i 0.0 + 0.0 0.0 8.0-628.0783185208527e-18i 0.0) + +(fft-1 '#(0 0 0 0 0 0 8 0)) @result{} + +#(1.0 -61.23031769111886e-18+1.0i -1.0 61.23031769111886e-18-1.0i + 1.0 -61.23031769111886e-18+1.0i -1.0 61.23031769111886e-18-1.0i) +@end example -@node Cyclic Checksum, Plotting, Random Numbers, Mathematical Packages +@node Cyclic Checksum, Plotting, Fast Fourier Transform, Mathematical Packages @section Cyclic Checksum @code{(require 'make-crc)} @@ -5016,7 +5015,7 @@ non-zero, and positive real number @var{prec}, returns a real @var{x} for which @code{abs}(@var{f}(@var{x})) is less than @var{prec}; or returns @code{#f} if such a real can't be found. -If @code{prec} is instead a negative integer, @code{newton:find-root} +If @var{prec} is instead a negative integer, @code{newton:find-root} returns the result of -@var{prec} iterations. @end defun @@ -5040,7 +5039,7 @@ real number @var{prec}, returns a complex number @var{z} for which @code{magnitude}(@var{f}(@var{z})) is less than @var{prec}; or returns @code{#f} if such a number can't be found. -If @code{prec} is instead a negative integer, @code{laguerre:find-root} +If @var{prec} is instead a negative integer, @code{laguerre:find-root} returns the result of -@var{prec} iterations. @end defun @@ -5052,38 +5051,89 @@ positive real number @var{prec}, returns a complex number @var{z} for which @code{magnitude}(@var{f}(@var{z})) is less than @var{prec}; or returns @code{#f} if such a number can't be found. -If @code{prec} is instead a negative integer, +If @var{prec} is instead a negative integer, @code{laguerre:find-polynomial-root} returns the result of -@var{prec} iterations. @end defun +@defun secant:find-root f x0 x1 prec +@defunx secant:find-bracketed-root f x0 x1 prec +Given a real valued procedure @var{f} and two real valued starting +points @var{x0} and @var{x1}, returns a real @var{x} for which +@code{(abs (f x))} is less than @var{prec}; or returns +@code{#f} if such a real can't be found. + +If @var{x0} and @var{x1} are chosen such that they bracket a root, that is +@example +(or (< (f x0) 0 (f x1)) + (< (f x1) 0 (f x0))) +@end example +then the root returned will be between @var{x0} and @var{x1}, and +@var{f} will not be passed an argument outside of that interval. + +@code{secant:find-bracketed-root} will return @code{#f} unless @var{x0} +and @var{x1} bracket a root. + +The secant method is used until a bracketing interval is found, at which point +a modified @i{regula falsi} method is used. + +If @var{prec} is instead a negative integer, @code{secant:find-root} +returns the result of -@var{prec} iterations. + +If @var{prec} is a procedure it should accept 5 arguments: @var{x0} +@var{f0} @var{x1} @var{f1} and @var{count}, where @var{f0} will be +@code{(f x0)}, @var{f1} @code{(f x1)}, and @var{count} the number of +iterations performed so far. @var{prec} should return non-false +if the iteration should be stopped. +@end defun + @node Commutative Rings, Determinant, Root Finding, Mathematical Packages @section Commutative Rings Scheme provides a consistent and capable set of numeric functions. Inexacts implement a field; integers a commutative ring (and Euclidean -domain). This package allows the user to use basic Scheme numeric -functions with symbols and non-numeric elements of commutative rings. +domain). This package allows one to use basic Scheme numeric functions +with symbols and non-numeric elements of commutative rings. @code{(require 'commutative-ring)} @ftindex commutative-ring @cindex ring, commutative -The @dfn{commutative-ring} package makes @code{+}, @code{-}, @code{*}, -@code{/}, and @code{^} @dfn{careful} in the sense that any non-numeric +The @dfn{commutative-ring} package makes the procedures @code{+}, +@code{-}, @code{*}, @code{/}, and @code{^} @dfn{careful} in the sense @cindex careful -arguments which it cannot reduce appear in the expression output. In -order to see what working with this package is like, self-set all the -single letter identifiers (to their corresponding symbols). +that any non-numeric arguments they do not reduce appear in the +expression output. In order to see what working with this package is +like, self-set all the single letter identifiers (to their corresponding +symbols). @example (define a 'a) @dots{} (define z 'z) @end example -Or just @code{(require 'self-set)}. Now for some sample expressions: + +Or just @code{(require 'self-set)}. Now try some sample expressions: @example +(+ (+ a b) (- a b)) @result{} (* a 2) +(* (+ a b) (+ a b)) @result{} (^ (+ a b) 2) +(* (+ a b) (- a b)) @result{} (* (+ a b) (- a b)) +(* (- a b) (- a b)) @result{} (^ (- a b) 2) +(* (- a b) (+ a b)) @result{} (* (+ a b) (- a b)) +(/ (+ a b) (+ c d)) @result{} (/ (+ a b) (+ c d)) +(^ (+ a b) 3) @result{} (^ (+ a b) 3) +(^ (+ a 2) 3) @result{} (^ (+ 2 a) 3) +@end example + +Associative rules have been applied and repeated addition and +multiplication converted to multiplication and exponentiation. + +We can enable distributive rules, thus expanding to sum of products +form: +@example +(set! *ruleset* (combined-rulesets distribute* distribute/)) + (* (+ a b) (+ a b)) @result{} (+ (* 2 a b) (^ a 2) (^ b 2)) (* (+ a b) (- a b)) @result{} (- (^ a 2) (^ b 2)) (* (- a b) (- a b)) @result{} (- (+ (^ a 2) (^ b 2)) (* 2 a b)) @@ -5093,7 +5143,7 @@ Or just @code{(require 'self-set)}. Now for some sample expressions: (/ (- a b) (- c d)) @result{} (- (/ a (- c d)) (/ b (- c d))) (/ (- a b) (+ c d)) @result{} (- (/ a (+ c d)) (/ b (+ c d))) (^ (+ a b) 3) @result{} (+ (* 3 a (^ b 2)) (* 3 b (^ a 2)) (^ a 3) (^ b 3)) -(^ (+ a 2) 3) @result{} (+ 8 (* a 12) (* (^ a 2) 6) (^ a 3)) +(^ (+ a 2) 3) @result{} (+ 8 (* a 12) (* (^ a 2) 6) (^ a 3)) @end example Use of this package is not restricted to simple arithmetic expressions: @@ -5105,13 +5155,6 @@ Use of this package is not restricted to simple arithmetic expressions: (- (+ (* a e i) (* b f g) (* c d h)) (* a f h) (* b d i) (* c e g)) @end example -The @dfn{commutative-ring} package differs from other extension -mechanisms in that it automatically, using properties true of all -commutative rings, simplifies sum and product expressions containing -non-numeric elements. One need only specify behavior for @code{+} or -@code{*} for cases where expressions involving objects reduce to numbers -or to expressions involving different non-numeric elements. - Currently, only @code{+}, @code{-}, @code{*}, @code{/}, and @code{^} support non-numeric elements. Expressions with @code{-} are converted to equivalent expressions without @code{-}, so behavior for @code{-} is @@ -5123,6 +5166,55 @@ the more restrictive Euclidean (Unique Factorization) Domain. @cindex Unique Factorization @cindex Euclidean Domain +@heading Rules and Rulesets + +The @dfn{commutative-ring} package allows control of ring properties +through the use of @dfn{rulesets}. + +@defvar *ruleset* +Contains the set of rules currently in effect. Rules defined by +@code{cring:define-rule} are stored within the value of *ruleset* at the +time @code{cring:define-rule} is called. If @var{*ruleset*} is +@code{#f}, then no rules apply. +@end defvar + +@defun make-ruleset rule1 @dots{} +@defunx make-ruleset name rule1 @dots{} +Returns a new ruleset containing the rules formed by applying +@code{cring:define-rule} to each 4-element list argument @var{rule}. If +the first argument to @code{make-ruleset} is a symbol, then the database +table created for the new ruleset will be named @var{name}. Calling +@code{make-ruleset} with no rule arguments creates an empty ruleset. +@end defun + +@defun combined-rulesets ruleset1 @dots{} +@defunx combined-rulesets name ruleset1 @dots{} +Returns a new ruleset containing the rules contained in each ruleset +argument @var{ruleset}. If the first argument to +@code{combined-ruleset} is a symbol, then the database table created for +the new ruleset will be named @var{name}. Calling +@code{combined-ruleset} with no ruleset arguments creates an empty +ruleset. +@end defun + +Two rulesets are defined by this package. + +@defvr Constant distribute* +Contain the ruleset to distribute multiplication over addition and +subtraction. +@defvrx Constant distribute/ +Contain the ruleset to distribute division over addition and +subtraction. + +Take care when using both @var{distribute*} and @var{distribute/} +simultaneously. It is possible to put @code{/} into an infinite loop. +@end defvr + +You can specify how sum and product expressions containing non-numeric +elements simplify by specifying the rules for @code{+} or @code{*} for +cases where expressions involving objects reduce to numbers or to +expressions involving different non-numeric elements. + @defun cring:define-rule op sub-op1 sub-op2 reduction Defines a rule for the case when the operation represented by symbol @var{op} is applied to lists whose @code{car}s are @var{sub-op1} and @@ -5144,8 +5236,8 @@ that value will replace the two arguments in arithmetic (@code{+}, The operations @code{+} and @code{*} are assumed commutative; hence both orders of arguments to @var{reduction} will be tried if necessary. -The following rule is the built-in definition for distributing @code{*} -over @code{+}. +The following rule is the definition for distributing @code{*} over +@code{+}. @example (cring:define-rule @@ -5749,7 +5841,7 @@ to. If @var{filename} is @code{#f} a temporary, non-disk based database will be created if such can be supported by the underlying base table implelentation. If the database cannot be created as specified @code{#f} is returned. For the fields and layout of descriptor tables, -@xref{Catalog Representation} +@ref{Catalog Representation} @end defun @defun open-database filename mutable? @@ -6676,6 +6768,31 @@ The table is created as ascii text and written to the file named by @var{destination} is the primary key for a row in the table named *printers*. @end table +The report is prepared as follows: + +@itemize @bullet +@item +@code{Format} (@pxref{Format}) is called with the @code{header} field +and the (list of) @code{column-names} of the table. +@item +@code{Format} is called with the @code{reporter} field and (on +successive calls) each record in the natural order for the table. A +count is kept of the number of newlines output by format. When the +number of newlines to be output exceeds the number of lines per page, +the set of lines will be broken if there are more than +@code{minimum-break} left on this page and the number of lines for this +row is larger or equal to twice @code{minimum-break}. +@item +@code{Format} is called with the @code{footer} field and the (list of) +@code{column-names} of the table. The footer field should not output a +newline. +@item +A new page is output. +@item +This entire process repeats until all the rows are output. +@end itemize +@end deffn + Each row in the table *reports* has the fields: @table @asis @@ -6705,30 +6822,6 @@ The printer name. The procedure to call to actually print. @end table -The report is prepared as follows: - -@itemize @bullet -@item -@code{Format} (@pxref{Format}) is called with the @code{header} field -and the (list of) @code{column-names} of the table. -@item -@code{Format} is called with the @code{reporter} field and (on -successive calls) each record in the natural order for the table. A -count is kept of the number of newlines output by format. When the -number of newlines to be output exceeds the number of lines per page, -the set of lines will be broken if there are more than -@code{minimum-break} left on this page and the number of lines for this -row is larger or equal to twice @code{minimum-break}. -@item -@code{Format} is called with the @code{footer} field and the (list of) -@code{column-names} of the table. The footer field should not output a -newline. -@item -A new page is output. -@item -This entire process repeats until all the rows are output. -@end itemize -@end deffn @node Database Browser, , Database Reports, Relational Database @@ -7304,6 +7397,7 @@ operation is equivalent to * Dynamic Data Type:: 'dynamic * Hash Tables:: 'hash-table * Hashing:: 'hash, 'sierpinski, 'soundex +* Object:: 'object * Priority Queues:: 'priority-queue * Queues:: 'queue * Records:: 'record @@ -7637,7 +7731,7 @@ Dylan(TM) language, but with a different interface. They have @dfn{elements} indexed by corresponding @dfn{keys}, although the keys may be implicit (as with lists).@refill -New types of collections may be defined as YASOS objects (@xref{Yasos}). +New types of collections may be defined as YASOS objects (@pxref{Yasos}). They must support the following operations: @itemize @bullet @item @@ -7709,10 +7803,10 @@ collection; they are potentially more efficient. @defun reduce proc seed . collections A generalization of the list-based @code{comlist:reduce-init} -(@xref{Lists as sequences}) to collections which will shadow the +(@pxref{Lists as sequences}) to collections which will shadow the list-based version if @code{(require 'collect)} follows @ftindex collect -@code{(require 'common-list-functions)} (@xref{Common List +@code{(require 'common-list-functions)} (@pxref{Common List Functions}).@refill @ftindex common-list-functions @@ -7726,7 +7820,7 @@ Examples: @end defun @defun any? pred . collections -A generalization of the list-based @code{some} (@xref{Lists as +A generalization of the list-based @code{some} (@pxref{Lists as sequences}) to collections.@refill Example: @@ -7737,7 +7831,7 @@ Example: @end defun @defun every? pred . collections -A generalization of the list-based @code{every} (@xref{Lists as +A generalization of the list-based @code{every} (@pxref{Lists as sequences}) to collections.@refill Example: @@ -7758,7 +7852,7 @@ Returns the number of elements in @var{collection}. @end defun @defun Setter list-ref -See @xref{Setters} for a definition of @dfn{setter}. N.B. +See @ref{Setters} for a definition of @dfn{setter}. N.B. @code{(setter list-ref)} doesn't work properly for element 0 of a list.@refill @end defun @@ -7939,7 +8033,7 @@ unspecified. -@node Hashing, Priority Queues, Hash Tables, Data Structures +@node Hashing, Object, Hash Tables, Data Structures @subsection Hashing @code{(require 'hash)} @@ -8076,7 +8170,12 @@ Some cases in which the algorithm fails (Knuth): @end defun -@node Priority Queues, Queues, Hashing, Data Structures +@node Object, Priority Queues, Hashing, Data Structures +@subsection Macroless Object System +@include objdoc.txi + + +@node Priority Queues, Queues, Object, Data Structures @subsection Priority Queues @code{(require 'priority-queue)} @@ -8454,8 +8553,8 @@ Example: @node Lists as sets, Lists as sequences, List construction, Common List Functions @subsubsection Lists as sets -@code{eq?} is used to test for membership by all the procedures below -which treat lists as sets.@refill +@code{eqv?} is used to test for membership by procedures which treat +lists as sets. @defun adjoin e l @code{adjoin} returns the adjoint of the element @var{e} and the list @@ -8653,6 +8752,7 @@ Example: @defun has-duplicates? lst returns @code{#t} if 2 members of @var{lst} are @code{equal?}, @code{#f} otherwise. + Example: @lisp (has-duplicates? '(1 2 3 4)) @@ -8663,6 +8763,23 @@ Example: @end lisp @end defun +The procedure @code{remove-duplicates} uses @code{member} (rather than +@code{memv}). + +@defun remove-duplicates lst +returns a copy of @var{lst} with its duplicate members removed. +Elements are considered duplicate if they are @code{equal?}. + +Example: +@lisp +(remove-duplicates '(1 2 3 4)) + @result{} (4 3 2 1) + +(remove-duplicates '(2 4 3 4)) + @result{} (3 4 2) +@end lisp +@end defun + @node Lists as sequences, Destructive list operations, Lists as sets, Common List Functions @subsubsection Lists as sequences @@ -8688,7 +8805,7 @@ operation (the combination is left-associative). For example, using @code{+}, one can add up all the elements. @code{reduce} allows you to apply a function which accepts only two arguments to more than 2 objects. Functional programmers usually refer to this as @dfn{foldl}. -@code{collect:reduce} (@xref{Collections}) provides a version of +@code{collect:reduce} (@pxref{Collections}) provides a version of @code{collect} generalized to collections.@refill Example: @@ -8871,7 +8988,7 @@ mutation is undefined. @deffn Procedure nconc args @code{nconc} destructively concatenates its arguments. (Compare this with @code{append}, which copies arguments rather than destroying them.) -Sometimes called @code{append!} (@xref{Rev2 Procedures}).@refill +Sometimes called @code{append!} (@pxref{Rev2 Procedures}).@refill Example: You want to find the subsets of a set. Here's the obvious way: @@ -9471,34 +9588,7 @@ with @var{new2} @dots{}. @code{(require 'line-i/o)} @ftindex line-i -@defun read-line -@defunx read-line port -Returns a string of the characters up to, but not including a newline or -end of file, updating @var{port} to point to the character following the -newline. If no characters are available, an end of file object is -returned. @var{port} may be omitted, in which case it defaults to the -value returned by @code{current-input-port}.@refill -@end defun - -@defun read-line! string -@defunx read-line! string port -Fills @var{string} with characters up to, but not including a newline or -end of file, updating the port to point to the last character read or -following the newline if it was read. If no characters are available, -an end of file object is returned. If a newline or end of file was -found, the number of characters read is returned. Otherwise, @code{#f} -is returned. @var{port} may be omitted, in which case it defaults to -the value returned by @code{current-input-port}.@refill -@end defun - -@defun write-line string -@defunx write-line string port -Writes @var{string} followed by a newline to the given port and returns -an unspecified value. Port may be omited, in which case it defaults to -the value returned by @code{current-input-port}.@refill -@end defun - - +@c @include lineio.txi @node Multi-Processing, , Line I/O, Procedures @@ -9531,7 +9621,7 @@ unspecified.@refill @deffn Procedure kill-process! Kills the current process and runs the next process from @code{process:queue}. If there are no more processes on -@code{process:queue}, @code{(slib:exit)} is called (@xref{System}). +@code{process:queue}, @code{(slib:exit)} is called (@pxref{System}). @end deffn @@ -9929,8 +10019,7 @@ unspecified.@refill * Debug:: To err is human ... * Breakpoints:: Pause execution * Trace:: 'trace -* System Interface:: 'system and 'getenv -* Time Zone:: +* System Interface:: 'system, 'getenv, and 'net-clients @end menu @@ -9988,7 +10077,7 @@ much improved. @quotation Notice that the neccessity for truncating output eliminates -Common-Lisp's @xref{Format} from consideration; even when variables +Common-Lisp's @ref{Format} from consideration; even when variables @code{*print-level*} and @code{*print-level*} are set, huge strings and bit-vectors are @emph{not} limited. @end quotation @@ -10185,7 +10274,7 @@ To untrace, type @end defun -@node System Interface, Time Zone, Trace, Session Support +@node System Interface, , Trace, Session Support @subsection System Interface @noindent @@ -10205,159 +10294,14 @@ integer status code. @end defun @noindent -If @code{(provided? 'current-time)}: - -@noindent -The procedures @code{current-time}, @code{difftime}, and -@code{offset-time} deal with a @dfn{calendar time} datatype -@cindex time -@cindex calendar time -which may or may not be disjoint from other Scheme datatypes. - -@defun current-time -Returns the time since 00:00:00 GMT, January 1, 1970, measured in -seconds. Note that the reference time is different from the reference -time for @code{get-universal-time} in @ref{Common-Lisp Time}. -@end defun - -@defun difftime caltime1 caltime0 -Returns the difference (number of seconds) between twe calendar times: -@var{caltime1} - @var{caltime0}. @var{caltime0} may also be a number. -@end defun - -@defun offset-time caltime offset -Returns the calendar time of @var{caltime} offset by @var{offset} number -of seconds @code{(+ caltime offset)}. -@end defun - -@node Time Zone, , System Interface, Session Support -@subsection Time Zone - -(require 'time-zone) - -@deftp {Data Format} TZ-string - -POSIX standards specify several formats for encoding time-zone rules. - -@table @t -@item :@i{<pathname>} -If the first character of @i{<pathname>} is @samp{/}, then -@i{<pathname>} specifies the absolute pathname of a tzfile(5) format -time-zone file. Otherwise, @i{<pathname>} is interpreted as a pathname -within @var{tzfile:vicinity} (/usr/lib/zoneinfo/) naming a tzfile(5) -format time-zone file. -@item @i{<std>}@i{<offset>} -The string @i{<std>} consists of 3 or more alphabetic characters. -@i{<offset>} specifies the time difference from GMT. The @i{<offset>} -is positive if the local time zone is west of the Prime Meridian and -negative if it is east. @i{<offset>} can be the number of hours or -hours and minutes (and optionally seconds) separated by @samp{:}. For -example, @code{-4:30}. -@item @i{<std>}@i{<offset>}@i{<dst>} -@i{<dst>} is the at least 3 alphabetic characters naming the local -daylight-savings-time. -@item @i{<std>}@i{<offset>}@i{<dst>}@i{<doffset>} -@i{<doffset>} specifies the offset from the Prime Meridian when -daylight-savings-time is in effect. -@end table - -The non-tzfile formats can optionally be followed by transition times -specifying the day and time when a zone changes from standard to -daylight-savings and back again. - -@table @t -@item ,@i{<date>}/@i{<time>},@i{<date>}/@i{<time>} -The @i{<time>}s are specified like the @i{<offset>}s above, except that -leading @samp{+} and @samp{-} are not allowed. - -Each @i{<date>} has one of the formats: - -@table @t -@item J@i{<day>} -specifies the Julian day with @i{<day>} between 1 and 365. February 29 -is never counted and cannot be referenced. -@item @i{<day>} -This specifies the Julian day with n between 0 and 365. February 29 is -counted in leap years and can be specified. -@item M@i{<month>}.@i{<week>}.@i{<day>} -This specifies day @i{<day>} (0 <= @i{<day>} <= 6) of week @i{<week>} (1 -<= @i{<week>} <= 5) of month @i{<month>} (1 <= @i{<month>} <= 12). Week -1 is the first week in which day d occurs and week 5 is the last week in -which day @i{<day>} occurs. Day 0 is a Sunday. -@end table -@end table - -@end deftp - -@deftp {Data Type} time-zone -is a datatype encoding how many hours from Greenwich Mean Time the local -time is, and the @dfn{Daylight Savings Time} rules for changing it. -@end deftp - -@defun time-zone TZ-string -Creates and returns a time-zone object specified by the string -@var{TZ-string}. If @code{time-zone} cannot interpret @var{TZ-string}, -@code{#f} is returned. -@end defun - -@defun tz:params caltime tz -@var{tz} is a time-zone object. @code{tz:params} returns a list of -three items: -@enumerate 0 -@item -An integer. 0 if standard time is in effect for timezone @var{tz} at -@var{caltime}; 1 if daylight savings time is in effect for timezone -@var{tz} at @var{caltime}. -@item -The number of seconds west of the Prime Meridian timezone @var{tz} is at -@var{caltime}. -@item -The name for timezone @var{tz} at @var{caltime}. -@end enumerate - -@code{tz:params} is unaffected by the default timezone; inquiries can be -made of any timezone at any calendar time. - -@end defun - -@noindent -The rest of these procedures and variables are provided for POSIX -compatability. Because of shared state they are not thread-safe. - -@defun tzset -Returns the default time-zone. - -@defunx tzset tz -Sets (and returns) the default time-zone to @var{tz}. - -@defunx tzset TZ-string -Sets (and returns) the default time-zone to that specified by -@var{TZ-string}. +If @code{system} is provided by the Scheme implementation, the +@dfn{net-clients} package provides interfaces to common network client +programs like FTP, mail, and Netscape. -@code{tzset} also sets the variables @var{*timezone*}, @var{daylight?}, -and @var{tzname}. This function is automatically called by the time -conversion procedures which depend on the time zone (@pxref{Time and -Date}). -@end defun +@code{(require 'net-clients)} +@ftindex net-clients -@defvar *timezone* -Contains the difference, in seconds, between Greenwich Mean Time and -local standard time (for example, in the U.S. Eastern time zone (EST), -timezone is 5*60*60). @code{*timezone*} is initialized by @code{tzset}. -@end defvar - -@defvar daylight? -is @code{#t} if the default timezone has rules for @dfn{Daylight Savings -Time}. @emph{Note:} @var{daylight?} does not tell you when Daylight -Savings Time is in effect, just that the default zone sometimes has -Daylight Savings Time. -@end defvar - -@defvar tzname -is a vector of strings. Index 0 has the abbreviation for the standard -timezone; If @var{daylight?}, then index 1 has the abbreviation for the -Daylight Savings timezone. -@end defvar +@c @include nclients.txi @node Extra-SLIB Packages, , Session Support, Other Packages @@ -10388,8 +10332,8 @@ sites are: @table @asis @item SLIB-PSD is a portable debugger for Scheme (requires emacs editor). @lisp -swissnet.ai.mit.edu:pub/scm/slib-psd1-3.tar.gz -prep.ai.mit.edu:pub/gnu/jacal/slib-psd1-3.tar.gz +http://swissnet.ai.mit.edu/ftpdir/scm/slib-psd1-3.tar.gz +ftp.gnu.org:pub/gnu/jacal/slib-psd1-3.tar.gz ftp.maths.tcd.ie:pub/bosullvn/jacal/slib-psd1-3.tar.gz ftp.cs.indiana.edu:/pub/scheme-repository/utl/slib-psd1-3.tar.gz @end lisp @@ -10412,6 +10356,19 @@ Kellom\"aki, pk@@cs.tut.fi. The Lisp Pointers article describing PSD @node About SLIB, Index, Other Packages, Top @chapter About SLIB +@ifinfo +@noindent +More people than I can name have contributed to SLIB. Thanks to all of +you! + +@quotation +SLIB @value{SLIBVERSION}, released @value{SLIBDATE}.@* +Aubrey Jaffer <jaffer @@ ai.mit.edu>@* +@i{Hyperactive Software} -- The Maniac Inside!@* +@url{http://swissnet.ai.mit.edu/~jaffer/SLIB.html} +@end quotation +@end ifinfo + @menu * Installation:: How to install SLIB on your system. * Porting:: SLIB to new platforms. @@ -10419,14 +10376,18 @@ Kellom\"aki, pk@@cs.tut.fi. The Lisp Pointers article describing PSD * Copyrights:: Intellectual propery issues. @end menu -@noindent -More people than I can name have contributed to SLIB. Thanks to all of -you. - @node Installation, Porting, About SLIB, About SLIB @section Installation + +@ifset html +<A NAME="Installation"> +@end ifset +@ifset html +</A> +@end ifset + Check the manifest in @file{README} to find a configuration file for your Scheme implementation. Initialization files for most IEEE P1178 compliant Scheme Implementations are included with this distribution. @@ -10490,11 +10451,11 @@ Your customized version should then be loaded as part of your scheme implementation's initialization. It will load @file{require.scm} from the library; this will allow the use of @code{provide}, @code{provided?}, and @code{require} along with the @dfn{vicinity} -functions (these functions are documented in the section -@xref{Require}). The rest of the library will then be accessible in a -system independent fashion.@refill +functions (these functions are documented in the section @ref{Require}). +The rest of the library will then be accessible in a system independent +fashion.@refill -Please mail new working configuration files to @code{jaffer@@ai.mit.edu} +Please mail new working configuration files to @code{jaffer @@ ai.mit.edu} so that they can be included in the SLIB distribution.@refill @@ -10505,7 +10466,7 @@ All library packages are written in IEEE P1178 Scheme and assume that a configuration file and @file{require.scm} package have already been loaded. Other versions of Scheme can be supported in library packages as well by using, for example, @code{(provided? 'rev3-report)} or -@code{(require 'rev3-report)} (@xref{Require}).@refill +@code{(require 'rev3-report)} (@pxref{Require}).@refill @ftindex rev3-report The module name and @samp{:} should prefix each symbol defined in the @@ -10547,6 +10508,13 @@ not have the time to fish through 10000 diffs to find your 10 real fixes. @node Copyrights, , Coding Standards, About SLIB @section Copyrights +@ifset html +<A NAME="Copyrights"> +@end ifset +@ifset html +</A> +@end ifset + This section has instructions for SLIB authors regarding copyrights. Each package in SLIB must either be in the public domain, or come with a @@ -10561,7 +10529,7 @@ need to add your copyright or send a disclaimer. In order to put code in the public domain you should sign a copyright disclaimer and send it to the SLIB maintainer. Contact -jaffer@@ai.mit.edu for the address to mail the disclaimer to. +jaffer @@ ai.mit.edu for the address to mail the disclaimer to. @quotation I, @var{name}, hereby affirm that I have placed the software package @@ -10586,7 +10554,7 @@ revisions of that module. Make sure no employer has any claim to the copyright on the work you are submitting. If there is any doubt, create a copyright disclaimer and have your employer sign it. Mail the signed disclaimer to the SLIB -maintainer. Contact jaffer@@ai.mit.edu for the address to mail the +maintainer. Contact jaffer @@ ai.mit.edu for the address to mail the disclaimer to. An example disclaimer follows. @subheading Explicit copying terms @@ -10606,7 +10574,7 @@ from those already in the file. Make sure no employer has any claim to the copyright on the work you are submitting. If there is any doubt, create a copyright disclaimer and have your employer sign it. Mail the signed disclaim to the SLIB -maintainer. Contact jaffer@@ai.mit.edu for the address to mail the +maintainer. Contact jaffer @@ ai.mit.edu for the address to mail the disclaimer to. @end itemize |