diff options
Diffstat (limited to 'slib.texi')
| -rw-r--r-- | slib.texi | 401 |
1 files changed, 150 insertions, 251 deletions
@@ -18,16 +18,16 @@ the portable Scheme library. @noindent @c Copyright (C) 1993 Todd R. Eigenschink@* -Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, -2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. +Copyright @copyright{} 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, +2002, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. @quotation Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no -Invariant Sections, with no Front-Cover Texts, and no Back-Cover -Texts. A copy of the license is included in the section entitled -``GNU Free Documentation License.'' +Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A +copy of the license is included in the section entitled ``GNU Free +Documentation License.'' @end quotation @end copying @@ -143,8 +143,8 @@ returns @code{#t} if the symbol @var{feature} is the @code{software-type}, the @code{scheme-implementation-type} @footnote{scheme-implementation-type is the name symbol of the running Scheme implementation (RScheme, |STk|, Bigloo, chez, Elk, gambit, -guile, JScheme, MacScheme, MITScheme, Pocket-Scheme, Scheme48, -Scheme->C, Scheme48, Scsh, T, umb-scheme, or Vscm). Dependence on +guile, JScheme, kawa, MacScheme, MITScheme, Pocket-Scheme, Scheme48, +Scheme->C, Scheme48, Scsh, SISC, T, umb-scheme, or Vscm). Dependence on scheme-implementation-type is almost always the wrong way to do things.}, or if @var{feature} has been provided by a module already loaded; and @code{#f} otherwise. @@ -275,8 +275,8 @@ The catalog can also be queried using @code{slib:in-catalog?}. Returns a @code{CDR} of the catalog entry if one was found for the symbol @var{feature} in the alist @code{*catalog*} (and transitively through any symbol aliases encountered). Otherwise, returns -@code{#f}. The format of catalog entries is explained in @ref{Library -Catalogs}. +@code{#f}. The format of catalog entries is explained in +@ref{Library Catalogs}. @end defun @@ -341,6 +341,7 @@ Note that file names indicated as @i{<path>} may have ``.scm'' or another suffix appended to them, depending on the specific Scheme system you are using. + @node Catalog Creation, Catalog Vicinities, Library Catalogs, The Library System @section Catalog Creation @@ -636,14 +637,12 @@ constructs may be to treat @code{provided?} as a macro. @include top-refs.txi - @node Module Analysis, , Top-level Variable References, Compiling Scheme @subsection Module Analysis @include vet.txi - @node Universal SLIB Procedures, Scheme Syntax Extension Packages, The Library System, Top @chapter Universal SLIB Procedures @@ -660,7 +659,6 @@ implementations as part of the @samp{*.init} files or by * Miscellany:: @end menu - @node Vicinity, Configuration, Universal SLIB Procedures, Universal SLIB Procedures @section Vicinity @@ -767,7 +765,6 @@ variable is used for messages and @code{program-vicinity}. @end defun - @node Configuration, Input/Output, Vicinity, Universal SLIB Procedures @section Configuration @@ -854,6 +851,7 @@ implementation *catalog* : @end example @end defun + @node Input/Output, System, Configuration, Universal SLIB Procedures @section Input/Output @@ -940,6 +938,20 @@ omitted, in which case it defaults to the value returned by @code{(current-output-port)}. @end deffn +@defun file-position port +@defunx file-position port #f +@var{port} must be open to a file. @code{file-position} returns the +current position of the character in @var{port} which will next be +read or written. If the implementation does not support +file-position, then @code{#f} is returned. + +@defunx file-position port k +@var{port} must be open to a file. @code{file-position} sets the +current position in @var{port} which will next be read or written. If +successful, @code{#f} is returned; otherwise @code{file-position} +returns @code{#f}. +@end defun + @defun output-port-width @defunx output-port-width port @@ -1015,26 +1027,27 @@ loop. @deffn {Procedure} slib:exit n @deffnx {Procedure} slib:exit Exits from the Scheme session returning status @var{n} to the system. -If @var{n} is omitted or @code{#t}, a success status is returned to the -system (if possible). If @var{n} is @code{#f} a failure is returned to -the system (if possible). If @var{n} is an integer, then @var{n} is -returned to the system (if possible). If the Scheme session cannot exit -an unspecified value is returned from @code{slib:exit}. +If @var{n} is omitted or @code{#t}, a success status is returned to +the system (if possible). If @var{n} is @code{#f} a failure is +returned to the system (if possible). If @var{n} is an integer, then +@var{n} is returned to the system (if possible). If the Scheme +session cannot exit, then an unspecified value is returned from +@code{slib:exit}. @end deffn @defun browse-url url Web browsers have become so ubiquitous that programming languagues should support a uniform interface to them. -If a @samp{netscape} browser is running, @code{browse-url} causes the -browser to display the page specified by string @var{url} and returns -#t. +If a browser is running, @code{browse-url} causes the browser to +display the page specified by string @var{url} and returns @code{#t}. If the browser is not running, @code{browse-url} starts a browser displaying the argument @var{url}. If the browser starts as a -background job, @code{browse-url} returns #t immediately; if the -browser starts as a foreground job, then @code{browse-url} returns #t -when the browser exits; otherwise it returns #f. +background job, @code{browse-url} returns @code{#t} immediately; if +the browser starts as a foreground job, then @code{browse-url} returns +@code{#t} when the browser exits; otherwise (if no browser) it returns +@code{#f}. @end defun @@ -1057,18 +1070,6 @@ Example: @end lisp @end defun -@defun expt n k -Returns @var{n} raised to the non-negative integer exponent @var{k}. - -Example: -@lisp -(expt 2 5) - @result{} 32 -(expt -3 3) - @result{} -27 -@end lisp -@end defun - @subsection Mutual Exclusion @@ -1159,7 +1160,6 @@ Syntax extensions (macros) included with SLIB. * Yasos:: 'yasos, 'oop, 'collect @end menu - @node Defmacro, R4RS Macros, Scheme Syntax Extension Packages, Scheme Syntax Extension Packages @section Defmacro @@ -1222,6 +1222,7 @@ Returns the result of expanding all defmacros in scheme expression @var{e}. @end defun + @node R4RS Macros, Macro by Example, Defmacro, Scheme Syntax Extension Packages @section R4RS Macros @@ -1253,6 +1254,7 @@ code expressions and definitions may contain macro definitions. The @code{current-input-port} and @code{current-output-port}. @end deffn + @node Macro by Example, Macros That Work, R4RS Macros, Scheme Syntax Extension Packages @section Macro by Example @@ -1281,9 +1283,10 @@ natively supported (most implementations) @end itemize @subsection Caveat -These macros are not referentially transparent (@pxref{Macros, , ,r4rs, -Revised(4) Scheme}). Lexically scoped macros (i.e., @code{let-syntax} -and @code{letrec-syntax}) are not supported. In any case, the problem +These macros are not referentially transparent +(@pxref{Macros, , ,r4rs, Revised(4) Scheme}). Lexically scoped macros +(i.e., @code{let-syntax} and @code{letrec-syntax}) are not supported. +In any case, the problem of referential transparency gains poignancy only when @code{let-syntax} and @code{letrec-syntax} are used. So you will not be courting large-scale disaster unless you're using system-function names as local @@ -1334,6 +1337,7 @@ involved in the matching and is not considered a pattern variable or literal identifier. @end defmac + @node Macros That Work, Syntactic Closures, Macro by Example, Scheme Syntax Extension Packages @section Macros That Work @@ -1525,9 +1529,6 @@ or inserted identifiers, then the big chunk will be copied unnecessarily. That shouldn't matter very often. - - - @node Syntactic Closures, Syntax-Case Macros, Macros That Work, Scheme Syntax Extension Packages @section Syntactic Closures @@ -1979,9 +1980,6 @@ of this proposal is derived from an earlier proposal by Alan Bawden. - - - @node Syntax-Case Macros, Define-Structure, Syntactic Closures, Scheme Syntax Extension Packages @section Syntax-Case Macros @@ -2103,7 +2101,6 @@ Send bug reports, comments, suggestions, and questions to Kent Dybvig (dyb @@ iuvax.cs.indiana.edu). - @node Define-Structure, Define-Record-Type, Syntax-Case Macros, Scheme Syntax Extension Packages @section Define-Structure @@ -2167,6 +2164,7 @@ red @end deffn + @node Define-Record-Type, Fluid-Let, Define-Structure, Scheme Syntax Extension Packages @section Define-Record-Type @@ -2230,6 +2228,15 @@ by the rules of lexical scoping) of its corresponding @url{http://srfi.schemers.org/srfi-8/srfi-8.html} @end defspec +@code{(require 'let-values)} or @code{(require 'srfi-11)} +@ftindex srfi-11 +@ftindex let-values + +@defspec let-values ((formals expression) ...) body @dots{} +@defspecx let-values* ((formals expression) ...) body @dots{} + +@url{http://srfi.schemers.org/srfi-11/srfi-11.html} +@end defspec @node Guarded LET* special form, Guarded COND Clause, Binding to multiple values, Scheme Syntax Extension Packages @@ -2317,7 +2324,6 @@ returns a list of all the characters it produces until the end. @end example - @node Yasos, , Guarded COND Clause, Scheme Syntax Extension Packages @section Yasos @@ -2385,9 +2391,6 @@ reasonable). See the L&FP paper for some suggestions. @end table - - - @node Yasos interface, Setters, Yasos terms, Yasos @subsection Interface @@ -2440,9 +2443,6 @@ and by default id an error otherwise. Objects such as collections @end defun - - - @node Setters, Yasos examples, Yasos interface, Yasos @subsection Setters @@ -2508,9 +2508,6 @@ value is unspecified. @end deffn - - - @node Yasos examples, , Setters, Yasos @subsection Examples @@ -2611,7 +2608,6 @@ value is unspecified. @end lisp - @node Textual Conversion Packages, Mathematical Packages, Scheme Syntax Extension Packages, Top @chapter Textual Conversion Packages @@ -2625,13 +2621,13 @@ value is unspecified. * HTTP and CGI:: Serve WWW sites * Parsing HTML:: 'html-for-each * URI:: Uniform Resource Identifier +* Parsing XML:: 'parse-xml or 'ssax * Printing Scheme:: Nicely * Time and Date:: * NCBI-DNA:: DNA and protein sequences * Schmooz:: Documentation markup for Scheme programs @end menu - @node Precedence Parsing, Format, Textual Conversion Packages, Textual Conversion Packages @section Precedence Parsing @@ -2718,8 +2714,8 @@ The JACAL symbolic math system @noindent Here are the higher-level syntax types and an example of each. -Precedence considerations are omitted for clarity. See @ref{Grammar -Rule Definition} for full details. +Precedence considerations are omitted for clarity. +See @ref{Grammar Rule Definition} for full details. @deftp Grammar nofix bye exit @example bye @@ -2857,6 +2853,7 @@ from a closed port. @findex current-input-port @end defun + @node Token definition, Nud and Led Definition, Ruleset Definition and Use, Precedence Parsing @subsection Token definition @@ -3209,7 +3206,7 @@ The ruleset in effect before @var{tk} was parsed is restored; @ifset html <A NAME="format"></A> @end ifset -@code{(require 'format)} +@code{(require 'format)} or @code{(require 'srfi-28)} @ftindex format @c The @file{format.scm} package was removed because it was not @@ -3219,7 +3216,6 @@ The ruleset in effect before @var{tk} was parsed is restored; @include format.texi - @node Standard Formatted I/O, Programs and Arguments, Format, Textual Conversion Packages @section Standard Formatted I/O @@ -3326,8 +3322,8 @@ if by increasing the precision. For @samp{%x} or @samp{%X}, prefix a leading @samp{0x} or @samp{0X} (respectively) to the result. This doesn't do anything useful for the @samp{%d}, @samp{%i}, or @samp{%u} conversions. Using this flag produces output which can be parsed by the -@code{scanf} functions with the @samp{%i} conversion (@pxref{Standard -Formatted Input}). +@code{scanf} functions with the @samp{%i} conversion +(@pxref{Standard Formatted Input}). @item @samp{0} @@ -3841,6 +3837,7 @@ errors. @end example @end defun + @node Command Line, Parameter lists, Getopt, Programs and Arguments @subsection Command Line @@ -4004,7 +4001,7 @@ system @end table @noindent -@file{batch.scm} uses 2 enhanced relational tables +The @samp{batch} module uses 2 enhanced relational tables (@pxref{Using Databases}) to store information linking the names of @code{operating-system}s to @code{batch-dialect}es. @@ -4252,14 +4249,19 @@ hello world @include html4each.txi -@node URI, Printing Scheme, Parsing HTML, Textual Conversion Packages +@node URI, Parsing XML, Parsing HTML, Textual Conversion Packages @section URI @include uri.txi +@node Parsing XML, Printing Scheme, URI, Textual Conversion Packages +@section Parsing XML + +@include xml-parse.txi + -@node Printing Scheme, Time and Date, URI, Textual Conversion Packages +@node Printing Scheme, Time and Date, Parsing XML, Textual Conversion Packages @section Printing Scheme @menu @@ -4268,7 +4270,6 @@ hello world * Pretty-Print:: 'pretty-print, 'pprint-file @end menu - @node Generic-Write, Object-To-String, Printing Scheme, Printing Scheme @subsection Generic-Write @@ -4317,7 +4318,6 @@ where @end deffn - @node Object-To-String, Pretty-Print, Generic-Write, Printing Scheme @subsection Object-To-String @@ -4440,6 +4440,7 @@ thus can reduce loading time. The following will write into (pprint-filter-file "code.scm" defmacro:expand* "exp-code.scm") @end lisp + @node Time and Date, NCBI-DNA, Printing Scheme, Textual Conversion Packages @section Time and Date @@ -4589,8 +4590,8 @@ Sets (and returns) the default time-zone to that specified by @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}). +conversion procedures which depend on the time zone +(@pxref{Time and Date}). @end defun @defvar *timezone* @@ -4750,6 +4751,7 @@ Notice that the values returned by @code{decode-universal-time} do not match the arguments to @code{encode-universal-time}. @end defun + @node Time Infrastructure, , Common-Lisp Time, Time and Date @subsection Time Infrastructure @@ -4778,7 +4780,6 @@ match the arguments to @code{encode-universal-time}. @include schmooz.texi - @node Mathematical Packages, Database Packages, Textual Conversion Packages, Top @chapter Mathematical Packages @@ -4801,7 +4802,6 @@ match the arguments to @code{encode-universal-time}. * Matrix Algebra:: 'determinant @end menu - @node Bit-Twiddling, Modular Arithmetic, Mathematical Packages, Mathematical Packages @section Bit-Twiddling @@ -4890,7 +4890,6 @@ of @var{mask} is 0. @subsection Integer Properties @defun logcount n -@defunx bit-count n Returns the number of bits in integer @var{n}. If integer is positive, the 1-bits in its binary representation are counted. If negative, the 0-bits in its two's-complement binary representation are counted. If 0, @@ -4907,6 +4906,22 @@ Example: @end lisp @end defun +@noindent +On @code{discuss@@r6rs.org} Ben Harris credits Simon Tatham with the +idea to have @code{bitwise-bit-count} return a negative count for +negative inputs. Alan Bawden came up with the succinct invariant. + +@defun bitwise-bit-count n +If @var{n} is non-negative, this procedure returns the number of 1 +bits in the two's-complement representation of @var{n}. Otherwise it +returns the result of the following computation: + +@lisp +(bitwise-not (bitwise-bit-count (bitwise-not @var{n}))) +@end lisp +@end defun + + @defun integer-length n Returns the number of bits neccessary to represent @var{n}. @@ -5083,8 +5098,6 @@ Returns the integer coded by the @var{bool1} @dots{} arguments. @end defun - - @node Modular Arithmetic, Irrational Integer Functions, Bit-Twiddling, Mathematical Packages @section Modular Arithmetic @@ -5245,7 +5258,6 @@ If an argument is not real, then these procedures signal an error. @end defun - @node Prime Numbers, Random Numbers, Irrational Real Functions, Mathematical Packages @section Prime Numbers @@ -5537,6 +5549,7 @@ in http://www.usb.org/developers/data/crcdes.pdf. @end defun + @node Graphing, Solid Modeling, Cyclic Checksum, Mathematical Packages @section Graphing @@ -5897,7 +5910,6 @@ temperatures around 5000.K. @include color.txi - @node Spectra, Color Difference Metrics, Color Spaces, Color @subsection Spectra @@ -6241,7 +6253,6 @@ perceptibility; the default, 2 and 1, for acceptability. @end defun - @node Color Conversions, Color Names, Color Difference Metrics, Color @subsection Color Conversions @@ -6332,7 +6343,6 @@ The integers @var{n1} and @var{n2} must be 10, 12, or 16. @end defun - @node Color Names, Daylight, Color Conversions, Color @subsection Color Names @@ -6431,18 +6441,12 @@ Resene Paints Ltd. @include daylight.txi - @node Root Finding, Minimizing, Color, Mathematical Packages @section Root Finding @code{(require 'root)} @ftindex root -@defun integer-sqrt y -Given a non-negative integer @var{y}, returns the largest integer -whose square is less than or equal to @var{y}. -@end defun - @defun newton:find-integer-root f df/dx x0 Given integer valued procedure @var{f}, its derivative (with respect to its argument) @var{df/dx}, and initial integer value @var{x0} for which @@ -6542,6 +6546,7 @@ iterations performed so far. @var{prec} should return non-false if the iteration should be stopped. @end defun + @node Minimizing, The Limit, Root Finding, Mathematical Packages @section Minimizing @@ -6551,6 +6556,7 @@ if the iteration should be stopped. @include minimize.txi + @node The Limit, Commutative Rings, Minimizing, Mathematical Packages @section The Limit @@ -6910,7 +6916,6 @@ Why relational database? For motivations and design issues see@* @include dbutil.txi - @node Table Operations, Database Interpolation, Using Databases, Relational Database @subsection Table Operations @@ -7246,6 +7251,7 @@ table. Subsequent operations to this table will signal an error. @end defop + @node Database Interpolation, Embedded Commands, Table Operations, Relational Database @subsection Database Interpolation @@ -7271,7 +7277,6 @@ associated with the smallest stored key is used. @end defun - @node Embedded Commands, Database Macros, Database Interpolation, Relational Database @subsection Embedded Commands @@ -7396,8 +7401,8 @@ Adds @var{domain-row} to the @dfn{domains} table if there is no row in the domains table associated with key @code{(car @var{domain-row})} and returns @code{#t}. Otherwise returns @code{#f}. -For the fields and layout of the domain table, @xref{Catalog -Representation}. Currently, these fields are +For the fields and layout of the domain table, +@xref{Catalog Representation}. Currently, these fields are @itemize @bullet @item domain-name @@ -7713,7 +7718,6 @@ ERROR: getopt->parameter-list "unrecognized option" "-?" @end example - @node Database Macros, Database Browser, Embedded Commands, Relational Database @subsection Database Macros @@ -7892,7 +7896,6 @@ without-documentation called @end example - @node Database Browser, , Database Macros, Relational Database @subsection Database Browser @@ -7942,7 +7945,6 @@ the symbol @var{table-name}. * Database Operations:: @end menu - @node Base Table, Catalog Representation, Relational Infrastructure, Relational Infrastructure @subsection Base Table @@ -8320,6 +8322,7 @@ which differs in column @var{index} or a lower indexed key; or false if no higher record is present. @end defop + @node Catalog Representation, Relational Database Objects, Base Table, Relational Infrastructure @subsection Catalog Representation @@ -8760,7 +8763,6 @@ associations as @var{alist}. This procedure is equivalent to: @end deffn - @node Basic Operations on Weight-Balanced Trees, Advanced Operations on Weight-Balanced Trees, Construction of Weight-Balanced Trees, Weight-Balanced Trees @subsection Basic Operations on Weight-Balanced Trees @@ -9090,8 +9092,6 @@ operation is equivalent to @node Data Structures, Sorting and Searching, Other Packages, Other Packages @section Data Structures - - @menu * Arrays:: 'array * Subarrays:: 'subarray @@ -9111,9 +9111,6 @@ operation is equivalent to * Records:: 'record @end menu - - - @node Arrays, Subarrays, Data Structures, Data Structures @subsection Arrays @@ -9264,12 +9261,7 @@ collection; they are potentially more efficient. @defun reduce proc seed collection1 @dots{} A generalization of the list-based @code{reduce-init} -(@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)} (@pxref{Common List -Functions}). -@ftindex common-list-functions +(@pxref{Lists as sequences}) to collections. Examples: @lisp @@ -9278,11 +9270,15 @@ Examples: (reduce union '() '((a b c) (b c d) (d a))) @result{} (c b d a). @end lisp + +@code{Reduce} called with two arguments will work as does the +procedure of the same name from @xref{Common List Functions}). +@ftindex common-list-functions @end defun @defun any? pred collection1 @dots{} -A generalization of the list-based @code{some} (@pxref{Lists as -sequences}) to collections. +A generalization of the list-based @code{some} +(@pxref{Lists as sequences}) to collections. Example: @lisp @@ -9383,9 +9379,6 @@ Here is a sample collection: @code{simple-table} which is also a @end lisp - - - @node Dynamic Data Type, Hash Tables, Collections, Data Structures @subsection Dynamic Data Type @@ -9424,15 +9417,12 @@ re-established by those continuations when they are invoked. The @code{dynamic-bind} macro is not implemented. - - @node Hash Tables, Object, Dynamic Data Type, Data Structures @subsection Hash Tables @include hashtab.txi - @node Object, Priority Queues, Hash Tables, Data Structures @subsection Macroless Object System @@ -9451,7 +9441,6 @@ The @code{dynamic-bind} macro is not implemented. @include queue.txi - @node Records, , Queues, Data Structures @subsection Records @@ -9583,7 +9572,6 @@ created the type represented by @var{rtd}. @end ignore - @node Sorting and Searching, Procedures, Data Structures, Other Packages @section Sorting and Searching @@ -9600,8 +9588,6 @@ created the type represented by @var{rtd}. * Sequence Comparison:: 'diff and longest-common-subsequence @end menu - - @node Common List Functions, Tree Operations, Sorting and Searching, Sorting and Searching @subsection Common List Functions @@ -9619,7 +9605,6 @@ optional arguments in some cases. * Non-List functions:: @end menu - @node List construction, Lists as sets, Common List Functions, Common List Functions @subsubsection List construction @@ -9683,10 +9668,6 @@ Example: @end defun - - - - @node Lists as sets, Lists as sequences, List construction, Common List Functions @subsubsection Lists as sets @@ -10152,7 +10133,6 @@ given identical arguments. @end example - @node Destructive list operations, Non-List functions, Lists as sequences, Common List Functions @subsubsection Destructive list operations @@ -10256,7 +10236,6 @@ The examples should suffice to show why this is the case. @end deffn - @node Non-List functions, , Destructive list operations, Common List Functions @subsubsection Non-List functions @@ -10318,90 +10297,14 @@ pair. (Called @code{atom} in Common LISP.) @node Sorting, Topological Sort, Chapter Ordering, Sorting and Searching @subsection Sorting -@code{(require 'sort)} +@code{(require 'sort)} or @code{(require 'srfi-95)} @ftindex sort +@ftindex srfi-95 [by Richard A. O'Keefe, 1991] -Many Scheme systems provide some kind of sorting functions. They do -not, however, always provide the @emph{same} sorting functions, and -those that I have had the opportunity to test provided inefficient ones -(a common blunder is to use quicksort which does not perform well). - -Because @code{sort} and @code{sort!} are not in the standard, there is -very little agreement about what these functions look like. For -example, Dybvig says that Chez Scheme provides -@lisp -(merge predicate list1 list2) -(merge! predicate list1 list2) -(sort predicate list) -(sort! predicate list) -@end lisp -@noindent -while MIT Scheme 7.1, following Common LISP, offers unstable -@lisp -(sort list predicate) -@end lisp -@noindent -TI PC Scheme offers -@lisp -(sort! list/vector predicate?) -@end lisp -@noindent -and Elk offers -@lisp -(sort list/vector predicate?) -(sort! list/vector predicate?) -@end lisp - -Here is a comprehensive catalogue of the variations I have found. - -@enumerate -@item -Both @code{sort} and @code{sort!} may be provided. -@item -@code{sort} may be provided without @code{sort!}. -@item -@code{sort!} may be provided without @code{sort}. -@item -Neither may be provided. -@item -The sequence argument may be either a list or a vector. -@item -The sequence argument may only be a list. -@item -The sequence argument may only be a vector. -@item -The comparison function may be expected to behave like @code{<}. -@item -The comparison function may be expected to behave like @code{<=}. -@item -The interface may be @code{(sort predicate? sequence)}. -@item -The interface may be @code{(sort sequence predicate?)}. -@item -The interface may be @code{(sort sequence &optional (predicate? <))}. -@item -The sort may be stable. -@item -The sort may be unstable. -@end enumerate - -All of this variation really does not help anybody. A nice simple merge -sort is both stable and fast (quite a lot faster than @emph{quick} sort). - I am providing this source code with no restrictions at all on its use -(but please retain D.H.D.Warren's credit for the original idea). You -may have to rename some of these functions in order to use them in a -system which already provides incompatible or inferior sorts. For each -of the functions, only the top-level define needs to be edited to do -that. - -I could have given these functions names which would not clash with any -Scheme that I know of, but I would like to encourage implementors to -converge on a single interface, and this may serve as a hint. The -argument order for all functions has been chosen to be as close to -Common LISP as made sense, in order to avoid NIH-itis. +(but please retain D.H.D.Warren's credit for the original idea). The code of @code{merge} and @code{merge!} could have been quite a bit simpler, but they have been coded to reduce the amount of work done per @@ -10415,15 +10318,6 @@ merge sort is @emph{fast} as well as stable!) so adapting CL code to Scheme takes a bit of work anyway. I did, however, appeal to CL to determine the @emph{order} of the arguments. -Each of the five functions has a required @emph{last} parameter which is -a comparison function. A comparison function @code{f} is a function of -2 arguments which acts like @code{<}. For example, - -@lisp -(not (f x x)) -(and (f x y) (f y z)) @equiv{} (f x z) -@end lisp - The standard functions @code{<}, @code{>}, @code{char<?}, @code{char>?}, @code{char-ci<?}, @code{char-ci>?}, @code{string<?}, @code{string>?}, @code{string-ci<?}, and @code{string-ci>?} are suitable for use as @@ -10433,9 +10327,14 @@ comparison functions. Think of @code{(less? x y)} as saying when [Addendum by Aubrey Jaffer, 2006] These procedures are stable when called with predicates which return -@code{#f} when applied to identical arguments. These procedures have -asymptotic time and space needs no larger than @i{O(N*log(N))}, where -@i{N} is the sum of the lengths of the sequence arguments. +@code{#f} when applied to identical arguments. + +The @code{sorted?}, @code{merge}, and @code{merge!} procedures consume +asymptotic time and space no larger than @i{O(N)}, where @i{N} is the +sum of the lengths of the sequence arguments. +The @code{sort} and @code{sort!} procedures consume asymptotic time +and space no larger than @i{O(N*log(N))}, where @i{N} is the length of +the sequence argument. All five functions take an optional @var{key} argument corresponding to a CL-style @samp{&key} argument. A @var{less?} predicate with a @@ -10445,8 +10344,8 @@ to a CL-style @samp{&key} argument. A @var{less?} predicate with a (lambda (x y) (@var{less?} (@var{key} x) (@var{key} y))) @end lisp -@c The @var{key} argument should be called at most one time for each -@c element. +All five functions will call the @var{key} argument at most once per +element. The @samp{!} variants sort in place; @code{sort!} returns its @var{sequence} argument. @@ -10471,9 +10370,8 @@ result. @defun merge! list1 list2 less? @defunx merge! list1 list2 less? key Merges two sorted lists, re-using the pairs of @var{list1} and -@var{list2} to build the result. If @code{merge!} is compiled, then -no new pairs will be allocated. The first pair of the result will be -either the first pair of @var{list1} or the first pair of @var{list2}. +@var{list2} to build the result. The result will be either +@var{list1} or @var{list2}. @end defun @defun sort sequence less? @@ -10491,12 +10389,13 @@ case that: @defun sort! sequence less? @defunx sort! sequence less? key -Returns @var{sequence} which has been mutated to order its elements -according to @var{less?}. If the argument @var{sequence} is a list -and @code{sort!} is compiled, then no new pairs will be allocated. If -the argument @var{sequence} is an array (including vectors and -strings), then the sorted elements are returned in the array -@var{sequence}. +Returns list, array, vector, or string @var{sequence} which has been +mutated to order its elements according to @var{less?}. Given valid +arguments, it is always the case that: + +@lisp +(sorted? (sort! @var{sequence} @var{less?}) @var{less?}) @result{} #t +@end lisp @end defun @@ -10769,7 +10668,6 @@ up here. * Metric Units:: Portable manifest types for numeric values. @end menu - @node Type Coercion, String-Case, Procedures, Procedures @subsection Type Coercion @code{(require 'coerce)} @@ -10832,7 +10730,6 @@ lower-case character. @end defun - @node String Ports, Line I/O, String-Case, Procedures @subsection String Ports @@ -11179,6 +11076,7 @@ namely @code{values}, @code{macro}, and @code{eval}. Description found in R4RS. @end defun + @node Transcripts, Rev2 Procedures, With-File, Standards Support @subsection Transcripts @@ -11192,9 +11090,6 @@ Redefines @code{read-char}, @code{read}, @code{write-char}, @end defun - - - @node Rev2 Procedures, Rev4 Optional Procedures, Transcripts, Standards Support @subsection Rev2 Procedures @@ -11257,7 +11152,6 @@ trailing @samp{?}. @end defun - @node Rev4 Optional Procedures, Multi-argument / and -, Rev2 Procedures, Standards Support @subsection Rev4 Optional Procedures @@ -11280,17 +11174,14 @@ For the specification of these optional procedures, @end deffn - - - @node Multi-argument / and -, Multi-argument Apply, Rev4 Optional Procedures, Standards Support @subsection Multi-argument / and - @code{(require 'multiarg/and-)} @ftindex multiarg -For the specification of these optional forms, @xref{Numerical -operations, , ,r4rs, Revised(4) Scheme}. +For the specification of these optional forms, +@xref{Numerical operations, , ,r4rs, Revised(4) Scheme}. @defun / dividend divisor1 @dots{} @end defun @@ -11299,9 +11190,6 @@ operations, , ,r4rs, Revised(4) Scheme}. @end defun - - - @node Multi-argument Apply, Rationalize, Multi-argument / and -, Standards Support @subsection Multi-argument Apply @@ -11316,14 +11204,12 @@ For the specification of this optional form, @end defun - @node Rationalize, Promises, Multi-argument Apply, Standards Support @subsection Rationalize @include ratize.txi - @node Promises, Dynamic-Wind, Rationalize, Standards Support @subsection Promises @@ -11498,6 +11384,7 @@ not created by the @code{call-with-values} procedure is unspecified. @end defun + @node SRFI, , Values, Standards Support @subsection SRFI @@ -11514,27 +11401,35 @@ unspecified. @item SRFI-8 @ref{Binding to multiple values} @ftindex srfi-9 @item SRFI-9 @ref{Define-Record-Type} +@ftindex srfi-11 +@item SRFI-11 @ref{Binding to multiple values} @ftindex srfi-23 @item SRFI-23 @code{(define error slib:error)} +@ftindex srfi-28 +@item SRFI-28 @ref{Format} @ftindex srfi-47 @item SRFI-47 @ref{Arrays} -@ftindex srfi-63 -@item SRFI-63 @ref{Arrays} @ftindex srfi-59 @item SRFI-59 @ref{Vicinity} @ftindex srfi-60 @item SRFI-60 @ref{Bit-Twiddling} @ftindex srfi-61 @item SRFI-61 @ref{Guarded COND Clause} +@ftindex srfi-63 +@item SRFI-63 @ref{Arrays} +@ftindex srfi-94 +@item SRFI-94 @ref{Irrational Integer Functions} and @ref{Irrational Real Functions} +@ftindex srfi-95 +@item SRFI-95 @ref{Sorting} @end itemize + @node SRFI-1, , SRFI, SRFI @subsubsection SRFI-1 @include srfi-1.txi - @node Session Support, System Interface, Standards Support, Other Packages @section Session Support @@ -11554,7 +11449,6 @@ is used by the @code{break} and @code{debug} packages. * Trace:: 'trace @end menu - @node Repl, Quick Print, Session Support, Session Support @subsection Repl @@ -11595,6 +11489,7 @@ catching lines and the following lines to your Scheme init file: (repl:top-level macro:eval) @end lisp + @node Quick Print, Debug, Repl, Session Support @subsection Quick Print @@ -11633,6 +11528,7 @@ procedures will be @code{write}n; procedures will be indicated by @samp{#[proc]}. @end defvar + @node Debug, Breakpoints, Quick Print, Session Support @subsection Debug @@ -11672,6 +11568,7 @@ Breakpoints (@pxref{Breakpoints}) all procedures @code{define}d at top-level in @file{file} @dots{}. @end deffn + @node Breakpoints, Trace, Debug, Session Support @subsection Breakpoints @@ -11752,6 +11649,7 @@ To unbreak, type @end lisp @end defun + @node Trace, , Breakpoints, Session Support @subsection Tracing @@ -12045,7 +11943,6 @@ page: * About this manual:: @end menu - @node Installation, The SLIB script, About SLIB, About SLIB @section Installation @@ -12075,7 +11972,7 @@ Build the SLIB catalog for the Scheme implementation. @subsection Unpacking the SLIB Distribution -If the SLIB distribution is a Linux RPM, it will create the SLIB +If the SLIB distribution is a GNU/Linux RPM, it will create the SLIB directory @file{/usr/share/slib}. If the SLIB distribution is a ZIP file, unzip the distribution to create @@ -12258,7 +12155,8 @@ e.g. mv dumpfile /usr/local/vscm/lib/scheme-boot SLIB comes with shell script for Unix platforms. @example -@exdent @b{ slib } [ scm | gsi | mzscheme | guile | slib48 | scheme48 | scmlit ] +@b{ slib } [ scheme | scm | gsi | mzscheme | guile + | scheme48 | scmlit | elk | sisc | kawa ] @end example @noindent @@ -12270,7 +12168,6 @@ implementation to run. Absent the argument, it searches for implementations in the above order. - @node Porting, Coding Guidelines, The SLIB script, About SLIB @section Porting @@ -12364,6 +12261,7 @@ Please @emph{do not} reformat the source code with your favorite beautifier, make 10 fixes, and send me the resulting source code. I do not have the time to fish through 10000 diffs to find your 10 real fixes. + @node Copyrights, About this manual, Coding Guidelines, About SLIB @section Copyrights @@ -12460,6 +12358,7 @@ nothing to undermine it in the future. @end flushleft @end quotation + @node About this manual, , Copyrights, About SLIB @section About this manual |