diff options
Diffstat (limited to 'slib.texi')
| -rw-r--r-- | slib.texi | 498 |
1 files changed, 323 insertions, 175 deletions
@@ -1,7 +1,7 @@ \input texinfo @c -*-texinfo-*- @c %**start of header @setfilename slib.info -@settitle SLIB +@settitle slib @include version.txi @setchapternewpage on @c Choices for setchapternewpage are {on,off,odd}. @@ -11,6 +11,31 @@ @syncodeindex tp cp @c %**end of header +@copying +@noindent +This manual is for SLIB (version @value{SLIBVERSION}, @value{SLIBDATE}), +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. + +@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 the Front-Cover Texts being ``A GNU Manual,'' +and with the Back-Cover Texts as in (a) below. A copy of the +license is included in the section entitled ``GNU Free Documentation +License.'' + +(a) The FSF's Back-Cover Text is: ``You have freedom to copy and modify +this GNU Manual, like GNU software. Copies published by the Free +Software Foundation raise funds for GNU development.'' +@end quotation +@end copying + @dircategory The Algorithmic Language Scheme @direntry * SLIB: (slib). Scheme Library @@ -23,95 +48,23 @@ @parskip 4pt plus 1pt @end iftex -@ifinfo -This file documents SLIB, the portable Scheme library. - -Copyright (C) 1993 Todd R. Eigenschink@* -Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002 Aubrey Jaffer - -Permission is granted to make and distribute verbatim copies of -this manual provided the copyright notice and this permission notice -are preserved on all copies. - -@ignore -Permission is granted to process this file through TeX and print the -results, provided the printed document carries copying permission -notice identical to this one except for the removal of this paragraph -(this paragraph not being relevant to the printed manual). - -@end ignore -Permission is granted to copy and distribute modified versions of this -manual under the conditions for verbatim copying, provided that the entire -resulting derived work is distributed under the terms of a permission -notice identical to this one. - -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 ifinfo - -@node Top, The Library System, (dir), (dir) - @titlepage @title SLIB @subtitle The Portable Scheme Library -@subtitle Version @value{SLIBVERSION} -@author by Aubrey Jaffer +@subtitle Version @value{SLIBVERSION}, @value{SLIBDATE} +@author 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 <agj @@ alum.mit.edu>@* -@ifset html -<A HREF="http://swiss.csail.mit.edu/~jaffer/SLIB.html"> -@end ifset -@url{http://swiss.csail.mit.edu/~jaffer/SLIB.html} -@ifset html -</A> -@end ifset -@end quotation - @vskip 0pt plus 1filll -Copyright @copyright{} 1993 Todd R. Eigenschink@* -Copyright @copyright{} 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000 Aubrey Jaffer - -Permission is granted to make and distribute verbatim copies of -this manual provided the copyright notice and this permission notice -are preserved on all copies. - -Permission is granted to copy and distribute modified versions of this -manual under the conditions for verbatim copying, provided that the entire -resulting derived work is distributed under the terms of a permission -notice identical to this one. - -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. +@insertcopying @end titlepage +@contents + @ifnottex -@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. -@end ifnottex +@node Top, The Library System, (dir), (dir) +@top SLIB + +@insertcopying @menu * The Library System:: How to use and customize. @@ -124,10 +77,19 @@ implementation, user, or directory. * About SLIB:: Install, etc. * Index:: @end menu +@end ifnottex @node The Library System, Universal SLIB Procedures, Top, Top @chapter The Library System +@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. + @menu * Feature:: SLIB names. * Require:: @@ -152,6 +114,12 @@ are properties of the Scheme implementation being used. The following @dfn{intrinsic feature}s detail what sort of numbers are available from an implementation: +@ftindex inexact +@ftindex rational +@ftindex real +@ftindex complex +@ftindex bignum + @itemize @bullet @item 'inexact @@ -220,14 +188,14 @@ Informs SLIB that @var{feature} is supported in this session. (provided? 'foo) @result{} #t @end example -@c @defvar *features* +@c @defvar slib:features @c Is a list of symbols denoting features present in this implementation. -@c @var{*features*} can grow as modules are @code{require}d. -@c @footnote{The variables @var{*modules*} and @var{*features*} were +@c @var{slib:features} can grow as modules are @code{require}d. +@c @footnote{The variables @var{*modules*} and @var{slib:features} were @c originally modeled on variables of the same names in common-lisp. But @c the distinction between features native to an implementation versus @c those provided by loading files was not useful. The symbols in -@c @var{*features*} now indicate the presence of a capability regardless +@c @var{slib:features} now indicate the presence of a capability regardless @c of how it was provided.} @c @end defvar @@ -865,11 +833,11 @@ slib "@value{SLIBVERSION}" on scm "5b1" on unix (implementation-vicinity) is "/usr/local/lib/scm/" (library-vicinity) is "/usr/local/lib/slib/" (scheme-file-suffix) is ".scm" -loaded *features* : +loaded slib:features : trace alist qp sort common-list-functions macro values getopt compiled -implementation *features* : +implementation slib:features : bignum complex real rational inexact vicinity ed getenv tmpnam abort transcript with-file @@ -1149,7 +1117,7 @@ The following procedures were present in Scheme until R4RS They are provided by all SLIB implementations. @defvr Constant t -Derfined as @code{#t}. +Defined as @code{#t}. @end defvr @defvr Constant nil @@ -2740,7 +2708,7 @@ call graph of grammar rules effectively instantiate the sytnax tree. @noindent The JACAL symbolic math system -(@url{http://swiss.csail.mit.edu/~jaffer/JACAL.html}) uses +(@url{http://swiss.csail.mit.edu/~jaffer/JACAL}) uses @t{precedence-parse}. Its grammar definitions in the file @file{jacal/English.scm} can serve as examples of use. @@ -2867,10 +2835,10 @@ The @var{ruleset} argument must be a list of rules as constructed by @code{prec:define-grammar} and extracted from @var{*syn-defs*}. The token @var{delim} may be a character, symbol, or string. A -character @var{delim} argument will match only a character token; i.e. a -character for which no token-group is assigned. A symbols or string -will match only a token string; i.e. a token resulting from a token -group. +character @var{delim} argument will match only a character token; +i.e. a character for which no token-group is assigned. A symbol or +string will match only a token string; i.e. a token resulting from a +token group. @code{prec:parse} reads a @var{ruleset} grammar expression delimited by @var{delim} from the given input @var{port}. @code{prec:parse} @@ -4817,9 +4785,11 @@ match the arguments to @code{encode-universal-time}. @menu * Bit-Twiddling:: 'logical * Modular Arithmetic:: 'modular +* Irrational Integer Functions:: +* Irrational Real Functions:: * Prime Numbers:: 'factor * Random Numbers:: 'random -* Fast Fourier Transform:: 'fft +* Discrete Fourier Transform:: 'dft * Cyclic Checksum:: 'crc * Graphing:: * Solid Modeling:: VRML97 @@ -4835,8 +4805,9 @@ match the arguments to @code{encode-universal-time}. @node Bit-Twiddling, Modular Arithmetic, Mathematical Packages, Mathematical Packages @section Bit-Twiddling -@code{(require 'logical)} +@code{(require 'logical)} or @code{(require 'srfi-60)} @ftindex logical +@ftindex srfi-60 @noindent The bit-twiddling functions are made available through the use of the @@ -5114,13 +5085,168 @@ Returns the integer coded by the @var{bool1} @dots{} arguments. -@node Modular Arithmetic, Prime Numbers, Bit-Twiddling, Mathematical Packages +@node Modular Arithmetic, Irrational Integer Functions, Bit-Twiddling, Mathematical Packages @section Modular Arithmetic @include modular.txi -@node Prime Numbers, Random Numbers, Modular Arithmetic, Mathematical Packages +@node Irrational Integer Functions, Irrational Real Functions, Modular Arithmetic, Mathematical Packages +@section Irrational Integer Functions + +@include math-integer.txi + + +@node Irrational Real Functions, Prime Numbers, Irrational Integer Functions, Mathematical Packages +@section Irrational Real Functions + +@code{(require 'math-real)} +@ftindex math-real + +Although this package defines real and complex functions, it is safe +to load into an integer-only implementation; those functions will be +defined to #f. + +@defun real-exp @var{x} +@defunx real-ln @var{x} +@defunx real-log @var{y} @var{x} +@defunx real-sin @var{x} +@defunx real-cos @var{x} +@defunx real-tan @var{x} +@defunx real-asin @var{x} +@defunx real-acos @var{x} +@defunx real-atan @var{x} +@defunx atan @var{y} @var{x} + +These procedures are part of every implementation that supports +general real numbers; they compute the usual transcendental functions. +@samp{real-ln} computes the natural logarithm of @var{x}; +@samp{real-log} computes the logarithm of @var{x} base @var{y}, which +is @code{(/ (real-ln x) (real-ln y))}. If arguments @var{x} and +@var{y} are not both real; or if the correct result would not be real, +then these procedures signal an error. + +@end defun + + +@defun real-sqrt @var{x} + +For non-negative real @var{x} the result will be its positive square +root; otherwise an error will be signaled. + +@end defun + + +@defun real-expt x1 x2 + +Returns @var{x1} raised to the power @var{x2} if that result is a real +number; otherwise signals an error. + +@code{(real-expt 0.0 @var{x2})} + +@itemize @bullet +@item +returns 1.0 for @var{x2} equal to 0.0; +@item +returns 0.0 for positive real @var{x2}; +@item +signals an error otherwise. +@end itemize + +@end defun + + +@defun quo x1 x2 +@defunx rem x1 x2 +@defunx mod x1 x2 + +@var{x2} should be non-zero. + +@example + (quo @var{x1} @var{x2}) ==> @var{n_q} + (rem @var{x1} @var{x2}) ==> @var{x_r} + (mod @var{x1} @var{x2}) ==> @var{x_m} +@end example + +where @var{n_q} is @var{x1}/@var{x2} rounded towards zero, +0 < |@var{x_r}| < |@var{x2}|, 0 < |@var{x_m}| < |@var{x2}|, @var{x_r} +and @var{x_m} differ from @var{x1} by a multiple of @var{x2}, +@var{x_r} has the same sign as @var{x1}, and @var{x_m} has the same +sign as @var{x2}. + +From this we can conclude that for @var{x2} not equal to 0, + +@example + (= @var{x1} (+ (* @var{x2} (quo @var{x1} @var{x2})) + (rem @var{x1} @var{x2}))) + ==> #t +@end example + +provided all numbers involved in that computation are exact. + +@example + (quo 2/3 1/5) ==> 3 + (mod 2/3 1/5) ==> 1/15 + + (quo .666 1/5) ==> 3.0 + (mod .666 1/5) ==> 65.99999999999995e-3 +@end example +@end defun + + +@defun ln @var{z} + +These procedures are part of every implementation that supports +general real numbers. +@samp{Ln} computes the natural logarithm of @var{z} + +In general, the mathematical function ln is multiply defined. The +value of ln @var{z} is defined to be the one whose imaginary part lies +in the range from -pi (exclusive) to pi (inclusive). + +@end defun + + +@defun abs x + +For real argument @var{x}, @samp{Abs} returns the absolute value of +@var{x}' otherwise it signals an error. + +@format +@t{(abs -7) ==> 7 +} +@end format + +@end defun + +@defun make-rectangular x1 x2 +@defunx make-polar x3 x4 + +These procedures are part of every implementation that supports +general complex numbers. Suppose @var{x1}, @var{x2}, @var{x3}, and +@var{x4} are real numbers and @var{z} is a complex number such that + + +@center @var{z} = @var{x1} + @var{x2}@w{i} = @var{x3} . e^@w{i} @var{x4} + +Then + +@format +@t{(make-rectangular @var{x1} @var{x2}) ==> @var{z} +(make-polar @var{x3} @var{x4}) ==> @var{z} +} +@end format + +where -pi < x_angle <= pi with x_angle = @var{x4} + 2pi n +for some integer n. + +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 @code{(require 'factor)} @@ -5130,7 +5256,7 @@ Returns the integer coded by the @var{bool1} @dots{} arguments. @include factor.txi -@node Random Numbers, Fast Fourier Transform, Prime Numbers, Mathematical Packages +@node Random Numbers, Discrete Fourier Transform, Prime Numbers, Mathematical Packages @section Random Numbers @cindex RNG @@ -5164,13 +5290,13 @@ tests pass. @include randinex.txi -@node Fast Fourier Transform, Cyclic Checksum, Random Numbers, Mathematical Packages -@section Fast Fourier Transform +@node Discrete Fourier Transform, Cyclic Checksum, Random Numbers, Mathematical Packages +@section Discrete Fourier Transform -@include fft.txi +@include dft.txi -@node Cyclic Checksum, Graphing, Fast Fourier Transform, Mathematical Packages +@node Cyclic Checksum, Graphing, Discrete Fourier Transform, Mathematical Packages @section Cyclic Checksum @code{(require 'crc)} @@ -6852,7 +6978,7 @@ signaled. The value returned is unspecified. (every (lambda (c) (memv c '(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9 - #\+ #\( #\ #\) #\-))) + #\+ #\( #\space #\) #\-))) (string->list d)))) string)) @end group @@ -10195,6 +10321,8 @@ pair. (Called @code{atom} in Common LISP.) @code{(require 'sort)} @ftindex sort +[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 @@ -10275,6 +10403,18 @@ 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. +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 +iteration. (For example, we only have one @code{null?} test per +iteration.) + +I gave serious consideration to producing Common-LISP-compatible +functions. However, Common LISP's @code{sort} is our @code{sort!} +(well, in fact Common LISP's @code{stable-sort} is our @code{sort!}; +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, @@ -10290,86 +10430,75 @@ The standard functions @code{<}, @code{>}, @code{char<?}, @code{char>?}, comparison functions. Think of @code{(less? x y)} as saying when @code{x} must @emph{not} precede @code{y}. +[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. + +All five functions take an optional @var{key} argument corresponding +to a CL-style @samp{&key} argument. A @var{less?} predicate with a +@var{key} argument behaves like: + +@lisp +(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. + +The @samp{!} variants sort in place; @code{sort!} returns its +@var{sequence} argument. + @defun sorted? sequence less? -Returns @code{#t} when the sequence argument is in non-decreasing order -according to @var{less?} (that is, there is no adjacent pair @code{@dots{} x -y @dots{}} for which @code{(less? y x)}). +@defunx sorted? sequence less? key +Returns @code{#t} when the sequence argument is in non-decreasing +order according to @var{less?} (that is, there is no adjacent pair +@code{@dots{} x y @dots{}} for which @code{(less? y x)}). Returns @code{#f} when the sequence contains at least one out-of-order -pair. It is an error if the sequence is not a list, vector, or -string. +pair. It is an error if the sequence is not a list or array +(including vectors and strings). @end defun @defun merge list1 list2 less? -This merges two lists, producing a completely new list as result. I -gave serious consideration to producing a Common-LISP-compatible -version. However, Common LISP's @code{sort} is our @code{sort!} (well, -in fact Common LISP's @code{stable-sort} is our @code{sort!}, 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. -@end defun - -@deffn {Procedure} merge! list1 list2 less? -Merges two lists, re-using the pairs of @var{list1} and @var{list2} to -build the result. If the code is compiled, and @var{less?} constructs -no new pairs, no pairs at all 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}, but you can't predict which. - -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 -iteration. (For example, we only have one @code{null?} test per -iteration.) - -@end deffn +@defunx merge list1 list2 less? key +Merges two sorted lists, returning a freshly allocated list as its +result. +@end defun -@defun sort sequence less? -Accepts either a list, vector, or string; and returns a new sequence -which is sorted. The new sequence is the same type as the input. -Always @code{(sorted? (sort sequence less?) less?)}. The original -sequence is not altered in any way. The new sequence shares its -@emph{elements} with the old one; no elements are copied. +@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}. @end defun -@deffn {Procedure} sort! sequence less? -Returns its sorted result in the original boxes. If the original -sequence is a list, no new storage is allocated at all. If the -original sequence is a vector or string, the sorted elements are put -back in the same vector or string. +@defun sort sequence less? +@defunx sort sequence less? key +Accepts a list or array (including vectors and strings) for +@var{sequence}; and returns a completely new sequence which is sorted +according to @var{less?}. The returned sequence is the same type as +the argument @var{sequence}. Given valid arguments, it is always the +case that: -Some people have been confused about how to use @code{sort!}, thinking -that it doesn't return a value. It needs to be pointed out that -@lisp -(set! slist (sort! slist <)) -@end lisp -@noindent -is the proper usage, not @lisp -(sort! slist <) +(sorted? (sort @var{sequence} @var{less?}) @var{less?}) @result{} #t @end lisp -@end deffn +@end defun -Note that these functions do @emph{not} accept a CL-style @samp{:key} -argument. A simple device for obtaining the same expressiveness is to -define +@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}. +@end defun -@lisp -(define (keyed less? key) - (lambda (x y) (less? (key x) (key y)))) -@end lisp -@noindent -and then, when you would have written -@lisp -(sort a-sequence #'my-less :key #'my-key) -@end lisp -@noindent -in Common LISP, just write -@lisp -(sort! a-sequence (keyed my-less? my-key)) -@end lisp -@noindent -in Scheme. @node Topological Sort, Hashing, Sorting, Sorting and Searching @subsection Topological Sort @@ -11379,13 +11508,23 @@ unspecified. @end menu @itemize @bullet +@ftindex srfi-2 @item SRFI-2 @ref{Guarded LET* special form} +@ftindex srfi-8 @item SRFI-8 @ref{Binding to multiple values} +@ftindex srfi-9 @item SRFI-9 @ref{Define-Record-Type} +@ftindex srfi-23 +@item SRFI-23 @code{(define error slib:error)} +@ftindex srfi-47 @item SRFI-47 @ref{Arrays} -@item SRFI-59 @ref{Vicinity} +@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} @end itemize @@ -11882,7 +12021,6 @@ http://www.sci.toyama-u.ac.jp/~iwao/Scheme/Jfilter/index.html @node About SLIB, Index, Other Packages, Top @chapter About SLIB -@ifnottex @noindent More people than I can name have contributed to SLIB. Thanks to all of you! @@ -11890,10 +12028,13 @@ you! @quotation SLIB @value{SLIBVERSION}, released @value{SLIBDATE}.@* Aubrey Jaffer <agj @@ alum.mit.edu>@* -@i{Hyperactive Software} -- The Maniac Inside!@* -@url{http://swiss.csail.mit.edu/~jaffer/SLIB.html} +@c @i{Hyperactive Software} -- The Maniac Inside!@* @end quotation -@end ifnottex + +Current information about SLIB can be found on SLIB's @dfn{WWW} home +page: + +@center @url{http://swiss.csail.mit.edu/~jaffer/SLIB} @menu * Installation:: How to install SLIB on your system. @@ -12322,6 +12463,11 @@ nothing to undermine it in the future. @node About this manual, , Copyrights, About SLIB @section About this manual +@menu +* Copying This Manual:: +* How to use this License for your documents:: +@end menu + @itemize @bullet @item Entries that are labeled as Functions are called for their return @@ -12339,6 +12485,8 @@ At the beginning of each section, there is a line that looks like using the package. @end itemize +@include fdl.texi + @ifinfo @node Index, , About SLIB, Top @unnumbered Index |